异策略时序差分强化学习

同策略强化学习：目标策略与行为策略相同，容易造成自举

异策略强化学习：目标策略与行为策略不同

前面讲的异策略蒙特卡罗强化学习，采样的时候应用的是策略 $b$，评估的策略是 $\pi$，但要乘上一个重要性权重

Q-learning 算法

$Q-learning$ 就是简化版本，同样是异策略，但不用乘上重要性权重

跟同策略时序差分强化学习的不同点：

现在要计算时序差分目标值，原本 $TD\ \ target=R_{t+1}+\gamma\cdot Q(s_{t+1},a_{t+1})$，其中是应用目标策略 $\pi$ 由当前状态 $s_{t+1}$ 产生动作 $a_{t+1}$

对于 $Q-learning$ 算法，不使用策略 $\pi$ 产生动作，而是使用所有的状态 $s_{t+1}$ 下的令动作值最大的动作：
这里就使用了其他的策略 $b$（并不知道具体是什么策略，也不 $care$），但与 $\pi$ 不同，故为异策略；策略 $b$ 是跟策略 $\pi$ 不相关的，因此很大程度上可以消除自举

（1） $Q-learning$ 算法（13-2）

1. 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，贪婪系数 $\epsilon=0.1$，最大迭代局数 $num\_episodes=1000$
2. 初始化：随机初始化动作值 $Q(s,a)$，根据动作值计算贪婪策略 $\pi(s)$
3. 过程：
4. $\qquad$ 循环：$episode=1\sim num\_episodes$
5. $\qquad \qquad$ 初始状态：$s=s_0$
6. $\qquad \qquad$ 循环：直到到达终止状态，即 $END=True$
7. $\qquad \qquad \qquad$ 选择动作：根据当前 $\epsilon$ 贪婪策略生成动作，$a=\pi_{\epsilon}(s)$
8. $\qquad \qquad \qquad$ 执行动作：$s,a,R,s',END$
9. $\qquad \qquad \qquad$ 策略评估： $Q(s,a)\leftarrow Q(s,a)+\alpha \left(R+\gamma \max_{a\in \mathbb{A}} Q(s',a)-Q(s,a)\right)$
10. $\qquad \qquad \qquad$ 策略改进：$\pi(s)=\arg \max _{a \in \mathbb{A}} Q(s, a)$
11. $\qquad \qquad \qquad$ 状态更新：$s \leftarrow s'$
12. 输出：最终策略 $\pi^*(s)$，最终动作值 $Q^*(s,a)$

说明：

（1）和 $Sarsa$ 算法的区别，不再用策略 $\pi$ 计算动作 $a'$；整个算法相当于有两个行为策略，一个是行为策略 $\pi_\epsilon$ 产生动作，另一个是策略评估时候用到的行为策略 $b$

（2）和 $Sarsa$ 算法的区别，$Sarsa$ 算法是 $Q-learning$ 算法的改进，$Sarsa$ 算法在更新 $Q$ 表格（策略评估）的时候所用的动作 $a'$ 是更新下一个 $Q$ 值一定会执行的动作

（3）$Q-learning$ 在更新 $Q$ 表格的时候所用的 $Q(s',a')$ 中对应的动作 $a'$ 不一定是下一步会执行的动作，因为它只将 $s \leftarrow s'$，在更新时的动作不是由行为策略 $\pi$ 产生的，它默认下一个动作就是下一个状态时对应 $Q$ 值最大的那个动作

（4）$Sarsa$ 算法（同策略算法）在更新时候比较“保守”，$Q-learning$ 算法（异策略算法）在更新时候比较“激进”，希望每一步都获得最大的奖励

期望 Sarsa 算法

$Q-learning$ 算法带了来新的问题，因为将 $Q(s_{t+1},a_{t+1})$ 变为 $\max_{a\in \mathbb{A}} Q(s',a)$，每次都取最大值，久而久之累计出现一个正向的偏置，导致最终的动作值 $Q$ 比真实值大

一种改进的方法就是用状态 $s_{t+1}$ 下所有的动作值的期望来代替最大动作值，目的是消除采样不均带来的影响。这种策略评估方式也可以看成是在 $Sarsa$ 算法中用状态 $S_{t+1}$ 下的所有动作值的期望（动作值的期望就是状态值）来代替动作值 $Q(s_{t+1},a_{t+1})$，所以它被称为期望 $Sarsa$（$Expected\ Sarsa$）算法
（1）期望 $Sarsa$ 算法（13-4）

1. 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，贪婪系数 $\epsilon=0.1$，最大迭代局数 $num\_episodes=1000$
2. 初始化：随机初始化动作值 $Q(s,a)$，根据动作值计算贪婪策略 $\pi(s)$
3. 过程：
4. $\qquad$ 循环：$episode=1\sim num\_episodes$
5. $\qquad \qquad$ 初始状态：$s=s_0$
6. $\qquad \qquad$ 循环：直到到达终止状态，即 $END=True$
7. $\qquad \qquad \qquad$ 选择动作：根据当前 $\epsilon$ 贪婪策略生成动作，$a=\pi_{\epsilon}(s)$
8. $\qquad \qquad \qquad$ 执行动作：$s,a,R,s',END$
9. $\qquad \qquad \qquad$ 策略评估： $Q(s,a)\leftarrow Q(s,a)+\alpha \left(R+\gamma \sum_{a\in \mathbb{A}}\pi(a \mid s') Q(s',a)-Q(s,a)\right)$
10. $\qquad \qquad \qquad$ 策略改进：$\pi(s)=\arg \max _{a \in \mathbb{A}} Q(s, a)$
11. $\qquad \qquad \qquad$ 状态更新：$s \leftarrow s'$
12. 输出：最终策略 $\pi^*(s)$，最终动作值 $Q^*(s,a)$

Double Q-learning 算法

$Q-learning$ 算法在策略评估中涵盖了取最大动作值的过程，这会带来一 个显著的正向偏置（$Positive\ \ Bias$）问题。正向偏置是指每次取值都比理论值要大，导致最终的结果偏大的现象。假设状态一动作对 $(s,a)$ 的理论动作值为 $Q(s,a)=0$，但策略评估过程中的估计动作值存在大于或小于零的情况，此时$Q-learning$ 算法总是会取最大的动作值来评估当前动作值，使得当前动作值发生一个正向偏置

于是提出了一种改进方法，成对学习（$Double\ Learning$）

（1）$Double\ Q-Learning$ 算法（13-5）

1. 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，贪婪系数 $\epsilon=0.1$，最大迭代局数 $num\_episodes=1000$
2. 初始化：随机初始化动作值 $Q_1(s,a)$ 和 $Q_2(s,a)$，根据动作值 $(Q_1+Q_2)$ 计算贪婪策略 $\pi(s)$
3. 过程：
4. $\qquad$ 循环：$episode=1\sim num\_episodes$
5. $\qquad \qquad$ 初始状态：$s=s_0$
6. $\qquad \qquad$ 循环：直到到达终止状态，即 $END=True$
7. $\qquad \qquad \qquad$ 选择动作：根据当前 $\epsilon$ 贪婪策略生成动作，$a=\pi_{\epsilon}(s)$
8. $\qquad \qquad \qquad$ 执行动作：$s,a,R,s',END$
9. $\qquad \qquad \qquad$ 策略评估： 各以 $0.5$ 的概率选择执行
10. $\qquad \qquad \qquad \qquad$ $Q_{1}(s, a) \leftarrow Q_{1}(s, a)+\alpha\left(R+\gamma Q_{2}\left(s', \arg \max _{a \in \mathbb{A}} Q_{1}\left(s', a\right)\right)-Q_{1}(s, a)\right)$
11. $\qquad \qquad \qquad \qquad$或
12. $\qquad \qquad \qquad \qquad$ $Q_{2}(s, a) \leftarrow Q_{2}(s, a)+\alpha\left(R+\gamma Q_{1}\left(s^{\prime}, \arg \max _{a \in \mathbb{A}} Q_{2}\left(s^{\prime}, a\right)\right)-Q_{2}(s, a)\right)$
13. $\qquad \qquad \qquad$ 策略改进：$\pi(s)=\arg \max _{a \in \mathbb{A}} (Q_1(s,a)+Q_2(s,a))$
14. $\qquad \qquad \qquad$ 状态更新：$s \leftarrow s'$
15. 输出：最终策略 $\pi^*(s)$，最终动作值 $Q^*(s,a)=(Q_1(s,a)+Q_2(s,a))/2$

说明：策略 $Q_1$ 和 $Q_2$ 是独立的，以此来消除自举

参考

• https://github.com/QiangLong2017