《动手学强化学习》学习笔记【三】

时序差分算法

对于大部分强化学习现实场景（例如电子游戏或者一些复杂物理环境），其马尔可夫决策过程的状态转移概率（即模型）是无法被完整表述的。在这种情况下，智能体只能和环境进行交互，通过采样到的数据来学习，在上一篇的结尾，我们提到了蒙特卡洛方法，这就是一个不基于模型的强化学习方法。

然而，由于采样具有不确定性，MC 方法的方差挺大的。因此我们提出了时序差分算法（TD），这是一种用来估计策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想：时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。

我们先不假思索地给出 TD 算法的表达式：

$v_{T+1}(s_t) = V_T(s_t)-\alpha[v_T(s_t)-[r_{T+1}+\gamma v_T(s_{t+1})]]$

其中 $v_T$ 表示在第 $T$ 时间步上对于状态价值的估计，而 $s_t$ 表示在轨迹的第 $t$ 步上采样得到的状态。

我们一般把 $\alpha$ 后边的一坨称作 TD Error，而一坨之中的后者称其为 TD Target.

观察这个式子，我们不难得出以下结论：（1）TD 算法利用了梯度下降的思想，使得 $v_T$ 不断朝着 TD Target 的方向去逼近；（2）并且当 TD Error 最终为零时，$v_T$ 会收敛到 $v_\pi$，将 $v_\pi$ 代入上式不难求得。

TD 算法本质上就是在没有模型的情况下求解贝尔曼公式，即估计给定 $\pi$ 的状态函数。尽管 TD 算法并不能直接用于找寻最优策略，但他是后续算法开展的基石。将 TD 和 MC 两个方法对比，结果如下：

TD/Sarsa learning	MC learning
Online: TD learning is online. It can update the state/action values immediately after receiving a reward.	Offline: MC learning is offline. It has to wait until an episode has been completely collected, and updates them all.
Continuing tasks: Since TD learning is online, it can handle both episodic and continuing tasks.	Episodic tasks: Since MC learning is offline, it can only handle episodic tasks that have terminate states.
Bootstrapping: TD bootstraps because update relies on the previous estimate of this value. Hence, it requires initial guesses and has bias.	Non-bootstrapping: MC is not bootstrapping, because it can directly estimate state/action values without any initial guess. It is unbiased estimate method.
Low estimation variance: TD has lower variance than MC because there are fewer random variables. For instance, Sarsa requires ( $R_{t+1}, S_{t+1}, A_{t+1}$ ).	High estimation variance: To estimate ( $q_\pi(s_t, a_t)$ ), we need samples of ( $R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$ ), there are $

Sarsa

对于状态价值函数的策略评估已经可以通过时序差分算法实现，那么在不知道奖励函数和状态转移函数的情况下，该怎么进行策略提升呢？答案是可以直接用时序差分算法来估计动作价值函数：

$Q_{T+1}(s_t,a_t) = Q_T(s_t,a_t) - \alpha[Q_T(s_t,a_t)-[r_{T+1}+\gamma Q_T(s_{t+1},a_{t+1})]]$

求解出了动作价值函数，我们就可以贪心地选择价值最高的动作，去更新我们的策略 $\pi$ 了 — — 当然也可以采用 $\epsilon-Greedy$ 的方式去做个平衡。但其实本质上和 TD 算法是一样的，都是提供了一个无模型的方法解贝尔曼公式。

除此以外，Sarsa 也有两种变式。Expected Sarsa 采用对下一步动作的回报取期望的形式，这样可以简化掉一个估计量（$a_{t+1}$）；n-step Sarsa 采用了将 Sarsa 和 Monte Carlo 相结合的方式，尝试多往后边儿采样 n steps，这样对回报的估值就越精准，越来越接近无偏的期望值。

Q 学习

除了 Sarsa，还有一种非常著名的基于时序差分算法的强化学习算法 — — Q-learning。Q-learning 和 Sarsa 的最大区别在于其时序差分更新方式为：

$Q_{T+1}(s_t,a_t) = Q_T(s_t,a_t) - \alpha[Q_T(s_t,a_t)-[r_{T+1}+\gamma \max_{a\in A} Q_T(s_{t+1},a)]]$

其实本质来说，就是从求解贝尔曼方程转为求解贝尔曼最优方程。

在线策略算法与离线策略算法

我们先给出行为策略和目标策略的定义：

• 采样数据的策略为行为策略（behavior policy），是用来收集数据的。
• 称用这些数据来更新的策略为目标策略（target policy），是最后要用的。

其中，在线策略（on-policy）算法表示行为策略和目标策略是同一个策略；而离线策略（off-policy）算法表示行为策略和目标策略不是同一个策略。离线策略的优势是：如果有之前别人拿其他策略积累得到的经验，我们可以直接拿过来用以自身学习；如果采用 Greedy 的策略，探索性就会较弱，不能穷举所有的 $(s,a)$。

举个例子，Sarsa 是典型的在线策略算法，而 Q-learning 是典型的离线策略算法。原因在于：观察 Q-learning 的更新公式可知，当给定 $(s_{t+1},a_{t+1})$ 时，$r_{t+1}$ 和 $s_{t+1}$ 是与策略无关的，仅与环境有关；那么我们完全可以采取另一种探索性更强的行为策略 $\pi_B$，根据 $s_t$ 去采样一个 $a_t$，最后用来优化我们的 Q-learning 对应的目标策略 $\pi_T$ —— 选择 $Q_T$ 最大的那个动作即可。

总体来讲，更新依赖行为策略 $\pi(a|s)$ 的概率分布的算法不适合 On-Policy.

总结

不管是 Sarsa/Q-learning，TD 算法的核心都是让当前的动作价值函数 $Q_T$ 去逼近目标价值函数 $\bar{Q}_T$ . 不同算法之间的 $\bar Q_T$ 如下：