强化学习（时序差分法）
本文介绍了强化学习的时序差分法（Temporal-Difference, TD）。
1. 引言
回顾强化学习的目标：价值估计（预测问题）和策略寻优（控制问题）。在前面的的介绍中，我们分别介绍了两种基于价值的方法，动态规划法和蒙特卡洛法：
- 动态规划法（DP）：是 model-based 方法，包含策略评估和策略改进两步，策略评估用来进行价值估计（即预测问题），策略改进用来进行策略寻优（控制问题）。
- 蒙特卡洛法（MC）：是 model-free 方法，因为一般情况下我们无法得到具体模型（状态转移概率），因此通过采样完整序列后，通过 $G_t$ 来进行策略评估（价值估计）。
本节介绍第三种基于价值的方法：时序差分法（TD）。首先回顾一下价值函数的等式：
\[\begin{aligned} v_\pi(s) &= \mathbb{E}_\pi[G_t\vert S_t=s] & {MC}\\ &= \mathbb{E}_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})\vert S_t=s] & {TD}\\ &= \sum_a\pi(a\vert s) \sum_{s^\prime,r}p(r^\prime,r \vert s,a)(r+\gamma v_\pi(s^\prime)) & {DP}\ \end{aligned}\]可以看出，基于价值的方法可以根据价值函数的等式不同来划分，其中：
- 动态规划（DP）：是一种自举的方法。更新 $v_{k+1}$ 时采用上一步的 $v_k$ 进行组装，缺点：环境动态特性必须已知；
- 蒙特卡洛（MC）：是一种采样的方法。依据大数定律，让样本均值逼近期望，缺点：必须完整采集一幕；
- 时序差分（TD）：本章节介绍的方法。
蒙特卡洛方法必须要等整个序列结束之后才能计算得到这一次的回报 $G_{t}$，而时序差分（Temporal Difference, TD）只需要当前步结束即可进行计算。具体而言，是将 $G_t$ 根据其定义进行一步展开
\[\begin{aligned} G_t \doteq \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} &= R_{t+1}+\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2}\\ &= R_{t+1}+\gamma V_{t+1} \end{aligned}\]然后带入蒙特卡洛的价值函数增量更新策略，即
\[\begin{aligned} MC:\quad & v(S_t) \leftarrow v(S_t)+\alpha({\color{red}G_t}-v(S_t)) \\ TD:\quad & v(S_t) \leftarrow v(S_t)+\alpha({\color{red}R_{t+1}+\gamma v(S_{t+1})}-v(S_t)) \end{aligned}\]也就是说，时序差分算法用当前获得的奖励加上下一个状态的价值估计来作为在当前状态会获得的回报。这里我们将动态路径规划节的$\frac{1}{N(s)}$替换成了 $\alpha$ ，表示对价值估计更新的步长。可以将 $\alpha$ 取为一个常数，此时更新方式不再像蒙特卡洛方法那样严格地取期望。
时序差分算法用到了 $V(s_{t+1})$ 的估计值，可以证明它最终收敛到策略 $\pi$ 的价值函数，我们在此不对此进行展开说明。
2. 时序差分法
2.1. 同轨策略下的时序差分控制（SARSA）
\[\begin{aligned} V(S_t) & \leftarrow V(S_t)+\alpha(\underbrace{R_{t+1}}_{采样}+\gamma \underbrace{V(S_{t+1})}_{自举}-V(S_t))\\ Q(S_t,A_t) & \leftarrow Q(S_t,A_t)+\alpha(\underbrace{R_{t+1}}_{采样}+\gamma \underbrace{Q(S_{t+1},A_{t+1})}_{自举}-Q(S_t,A_t))\\ \end{aligned}\]上述更新方式即为 SARSA。
伪代码如下：
- Initialize $Q(s,a)$ arbitrarily
- Repeat (for each episode):
- Initialize $s$
- Repeat (for each step of episode):
- Choose $a$ from $s$ using policy derived from $Q$ (e.g., $\epsilon$-greedy)
- Take action $a$, observe $r$, $s^\prime$
- Choose $a^\prime$ from $s^\prime$ using policy derived from $Q$ (e.g., $\epsilon$-greedy)
- $\color{red}{Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma Q(s^\prime,a^\prime)-Q(s,a)]}$
- $\color{red}{s\leftarrow}s^\prime; a\leftarrow a^\prime$
- until $s$ is terminal
上述更新方式又被称为同轨策略（on-policy），因为其采样和更新的均为同一个策略。这个策略可以是任何策略，如 $greedy$ 贪婪策略、$\epsilon-greedy$ 贪婪策略，随机策略等。
从上面的伪代码可以看出，每次执行动作时，都是从一个策略中得到的。而更新 $Q(s,a)$ 的值时，也是使用的同一个策略得到的动作计算出的 $Q(s^\prime,a^\prime)$ 。此时，由于这个策略不一定是最优策略（一般肯定不是最优策略），那么对应的 $a^\prime$ 未必是$s^\prime$ 状态下的最优选择。如果策略采用 $\epsilon-greedy$ 贪婪策略，它需要兼顾探索和利用，因此训练的时候会显得有点“胆小”。所以说 SARSA 是一个偏向保守的方法，训练过程慢慢摸索会比较慢。
2.2. 离轨策略下的时序差分控制（Q-Learning）
实际上，在 $s^\prime$ 状态下，存在一个确定性策略（也即 $greedy$ 贪婪策略）
\[a^*=\pi(s^\prime) = argmax_a\; Q(s^\prime, a)\]此时有
\[max_{a^\prime}\; Q(s^\prime,a^\prime) = Q(s^\prime, a^*)\]更新 $Q(s,a)$ 时，不再根据当前策略进行采样，而是直接查阅已有的 Q table 找到当前状态下已知的最大 $Q(s^\prime, a)$，就使用这个值对应的 $a$ 来更新 $Q(s,a)$。这种更新方式即为 Q-Learning。
伪代码如下：
- Initialize $Q(s,a)$ arbitrarily
- Repeat (for each episode):
- Initialize $s$
- Repeat (for each step of episode):
- Choose $a$ from $s$ using policy derived from $Q$ (e.g., $\epsilon$-greedy)
- Take action $a$, observe $r$, $s^\prime$
- $\color{red}{Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma \mathop{\text{max}}\limits_{a^\prime} Q(s^\prime,a^\prime)-Q(s,a)]}$
- $\color{red}{s\leftarrow}s^\prime$
- until $s$ is terminal
Q-Learning 分离了目标策略与行为策略。一方面，在更新 $Q(s,a)$ 时，Q-Learning 采用 $greedy$ 更新策略作为行为策略探索得到的经验轨迹来优化目标策略，从而更有可能探索到最佳策略。而在实际执行时，采用 $\epsilon-greedy$ 行为策略来选取动作。
因此，Q-Learning 又被被称为离轨策略（off-policy）。
2.3. 期望SARSA
我们可以对 SARSA 进行改进，不再进行采样得到动作 $a^\prime$，而是对 $Q$ 进行加权平均，此时
\[Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma \mathbb{E}_\pi[Q(s^\prime,a^\prime)\vert s^\prime]-Q(s,a)]\]增加采样操作的好处在于可以提高计算的稳定性（因为期望更能反应当前状态的价值），但是代价是计算量增大（因为需要计算多个Q值后取平均）。
3. Deep Q-Network（DQN）
前面介绍的 Q-Learning 只能用于状态和动作的集合是有限的离散基且状态和动作数量较少的情况，状态和动作需要人工预先设计，Q函数值需要存储在一个二维表格中。实际应用中的场景可能会很复杂，很难定义出离散的状态；即使能够定义，数量也非常大，无法用数组存储。
对于强化学习来说，很多实际应用问题的输入数据是高维的，如图像，声音，算法要根据它们来选择一个动作执行以达到某一预期的目标。比如，对于自动驾驶算法，要根据当前的画面决定汽车的行驶方向和速度。经典的强化学习算法如 Q-Learning 需要列举出所有可能的情况（称为状态，这是对当前所处环境的抽象），然后进行迭代。 Q-Learning 的经典实现是列举出所有的状态和动作，构建 Q-Table，这是一个二维的表，然后迭代计算各种状态下执行各种动作的预期回报的最大值。对于高维的输入数据，显然是不现实的，因为如果直接以原始数据作为状态，维数太高，而且状态数量太多。
一种解决方案是从高维数据中抽象出特征，作为状态，然后用强化学习建模，但这种做法很大程度上依赖于人工特征的设计。如从画面中提取出目标的位置、速度等信息，也非常困难，这也是一个难题。
另一种方案是用一个函数来逼近价值函数，函数的输入是原始的状态数据，函数的输出是价值函数值。在有监督学习中，我们用神经网络来拟合分类或回归函数，同样的，也可以用神经网络可来拟合强化学习中的价值函数，这就是 DQN 的基本思想。
1
2
3
+----+ ---->Q(s,a1) +----+
s ---> |f(x)| ---->Q(s,a2) or s,ai --->|f(x)| ---->Q(s,ai)
+----+ ---->Q(s,a3) +----+
基于价值函数的深度强化学习的典型代表是DQN（深度Q网络），由DeepMind公司在2013年提出，2015年其改进型发表在Nature上。这种方法用卷积神经网络拟合价值函数，一般是Q函数。网络的输入为原始场景数据，如游戏的画面图像，输出为在这种场景下执行各种动作时所能得到的Q函数的极大值。
损失函数用神经网络的输出值与Q学习每次迭代时的更新值构造，是神经网络的输出值与Q函数估计值之间的误差，与Q学习中的更新项相同
\[L(\theta) = \mathbb{E}[(r+\gamma \mathop{\text{max}}\limits_{a^\prime} Q(s^\prime,a^\prime;\theta)-Q(s,a,\theta))^2]\]3.1. 经验回放（Replay Buffer）
和 Q-Learning 类似，DQN 可以通过执行动作来生成样本。具体而言，给定一个状态，用当前的神经网络进行预测，得到所有动作的 Q 函数，然后按照策略选择一个动作执行，得到下一个状态以及回报值，以此构造训练样本。但与普通的有监督学习不同，这里的训练样本是通过不停的执行动作而动态生成的。
监督学习一般要求训练样本之间是相互独立的，在强化学习中，经常遇到的是前后高度相关的状态序列。在某个状态下执行一个动作之后进入下一个状态，前后两个状态之间存在着明显的概率关系。
为了解决训练样本之间存在相关性，以及样本的概率分布不固定的问题，采用了经验回放机制，具体做法是，先把执行动作构造的训练样本存储到一个大的集合（replay-buffer，回放缓冲）中，在训练Q网络时每次从这个集合（replay-buffer，回放缓冲）中随机抽取出部分样本作为训练样本，以此打破样本之间的相关性。
随之而来的问题是，每个样本都是由不同的Q函数值对应的策略产生的。在回放缓冲中早期的样本中，由于Q值估计不准，对应的策略还比较幼稚；反之，样本越新对应的策略越优。因此，还需要额外设计样本选取的权重。
3.2. 分离拷贝
DQN 在随机尝试执行动作，生成训练样本的过程中，需要用当前的 Q 函数来计算训练样本的标签值，这存在着自身依赖。也即损失函数的前半部分
\[Y^Q = r+\gamma \mathop{\text{max}}\limits_{a^\prime} Q(s^\prime,a^\prime;\theta)\]与当前的 $Q(s,a,\theta)$ 有关系的。为了降低这种依赖关系，可以采用两个 DQN 代替原先的一个 DQN。对应的损失函数为
\[L(\theta) = \mathbb{E}[(r+\gamma \mathop{\text{max}}\limits_{a^\prime} Q(s^\prime,a^\prime;\theta_i^{-})-Q(s,a,\theta_i))^2]\]其中，$\theta_i^{-}$ 为第 $i$ 次迭代时用于计算目标 Q 函数值的 DQN 参数值，这个神经网络因此也称为目标网络；$\theta_i$ 则为当前网络的参数值。将目标网络与当前网络分离开来，当前网络的值在训练时每次都迭代更新，而目标网络则周期性的从当前Q网络同步过来，每多次迭代执行一次拷贝。
1
2
3
4
5
Q-Network Target Q-Network
+----+ ---->Q(s,a1) +----+ ---->Q(s',a1)
s ---> |f(x)| ---->Q(s,a2) s' ---> |f(x)| ---->Q(s',a2)
| θ | ---->... | θ- | ---->...
+----+ ---->Q(s,an) +----+ ---->Q(s',an)
3.3. 过高估计（Double DQN）
DQN中均使用了 max 操作，使得选择和评估一个动作值都会过高估计，为了解决这个问题，Double Q-learning 率先使用了两个值函数进行解耦，其互相随机的更新两个值函数，并利用彼此的经验去更新网络权重 $\theta$ 和 $\theta^{-}$。对应的损失函数为
4. 参考文献
[1] shuhuai008. bilibili【强化学习】(SARSA) 时序差分-同轨策略TD控制
[2] 莫烦. 什么是 Sarsa (强化学习)