3 时序差分算法
动态规划算法是在已知 MDP 的情况下直接求解最优策略。但在大多数情况下，我们无法知道环境的奖励函数 \(\mathcal{R}\) 和状态转移函数 \(\mathcal{P}\) ，此时，需要通过与环境交互采样数据并学习。这类强化学习算法统称为无模型的强化学习（model-free reinforcement learning）。
时序差分方法
时序差分方法是一种在黑箱环境估计策略价值函数的方法。
回顾 蒙特卡洛方法 ：
从任意初始状态 \(s_t\) 开始，根据策略 \(\pi\) 选取动作与环境不断交互直至结束，可以获得一轮的回报 \(G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots + \gamma^n r_{t+n}\) 。根据此轮回报，可以如下更新一次状态价值函数：
显然，多轮迭代后， \(V(s_t)\) 将收敛至 \(G_t\) ，即状态 \(s_t\) 的期望回报。上式中的 \(\alpha\) 称为学习率。
蒙特卡洛方法必须等一轮交互结束后才能获得回报 \(G_t\) ，才能更新一次状态价值函数 \(V(s_t)\) ，效率很低。
时序差分方法的动机就是优化 \(G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots + \gamma^n r_{t+n}\) 这一项，改成 \(r_t + \gamma V(s_{t+1})\) 。
这就不用等一轮交互结束了，交互一次获得 \(r_t\) 即可。
因为 \(V(s)\) 是趋近真值的，所以用 \(V(s_{t+1})\) 代替 \(r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1}r_{t+n}\) 是可行的。
强化学习的目的是获得一个最优的策略。
一般而言，策略的好坏都与动作价值函数 \(Q^{\pi}(s,a)\) 估计的准确程度正相关。比如说贪心策略 \(\pi\left(a|s\right) = 1, a=\arg\max_{a}Q^{\pi}(s,a)\) ； \(\varepsilon\) -greedy 策略
Note
一般用带点随机的策略，比如 \(\varepsilon\) -greedy，因为我们需要尽可能多的 (s,a) 组合所对应的 \(Q(s,a)\) 数据。
所以，在黑箱环境里，强化学习要学的就是动作价值函数 \(Q(s,a)\) 。怎么学？就用上述时序差分算法：
Thinking
这里省略了策略 \(\pi\) 。在动作价值函数更新的过程中，策略也在不断地优化。
如果用 > 表示某个策略优于另一个策略的话，则有
Sarsa 算法
Sarsa 算法就是基于以上思路的一个基本算法。
先获得随机初始状态 \(s\) ，用策略 \(\pi\) 生成一个动作 \(a\) ，执行动作后环境反馈一个回报 \(r\) 和状态 \(s'\) ，再根据策略 \(\pi\) 获得下一个动作 \(a'\) ，更新一次动作价值函数：
反复迭代直至一轮结束（环境终止、到达最大时间步等）。再重新生成随机初始状态，继续迭代。
多步 Sarsa 算法
| 方法 | 公式 | 迭代频率 | 收敛所需更新次数 |
|---|---|---|---|
| 蒙特卡洛 | \(Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha[G_t-Q(s_t,a_t)]\) | 慢，一轮完整交互后才能更新 | 少， \(G_t\) 无偏地反应了动作价值 |
| Sarsa | \(Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha[r_t+Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]\) | 快，一次交互后就能更新 | 多， \(Q(s_{t+1},a_{t+1})\) 是有偏的 |
多步 Sarsa 算法就是两者折中，各取其长，既避免了过慢的交互频率，也有一个较快的收敛速度：
Q-learning 算法
Q-learning 同样基于时序差分算法，但在 \(G_t\) 的处理上，不是直接用 \(r_t + \gamma Q(s_{t+1},a_{t+1})\) 代替（此处动作 \(a_{t+1}\) 是在状态 \(s_{t+1}\) 上根据策略 \(\pi\) 生成的），而是用基于贪心策略的 \(r_t + \gamma\max_{a'\in\mathcal{A}} Q(s_{t+1},a')\) 代替：
| 方法 | 流程 |
|---|---|
| Sarsa | 初始随机状态 s，遵循策略 \(\pi\) 生成动作 a，交互获得奖励 r 和新状态 s'，再遵循策略 \(\pi\) 生成动作 a' ，用 r 和 \(Q(s',a')\) 更新一次 \(Q(s,a)\) ，执行动作 a' |
| Q-learning | 初始随机状态 s，遵循策略 \(\pi\) 生成动作 a，交互获得奖励 r 和新状态 s'，再遵循贪心策略生成动作 a' ，用 r 和 \(\max_{a'}Q(s',a')\) 更新一次 \(Q(s,a)\) ，不执行动作 a' ，而是遵循策略 \(\pi\) 生成动作 a'' 并执行 |
这里需要介绍一下在线/离线策略算法的概念：
在线与离线策略算法
| 名字 | 定义 | 例子 |
|---|---|---|
| 行为策略（behavior policy） | 用来采样数据的策略 | 时序差分方法中，根据新状态 s' 生成动作 a' 的策略 |
| 目标策略（target policy） | 被优化的策略 | 时序差分方法中，根据初始状态 s 生成动作 a 的策略 |
| 在线策略（on-policy）算法 | 行为策略和目标策略相同 | Sarsa 算法 |
| 离线策略（off-policy）算法 | 行为策略和目标策略不同 | Q-learning 算法 |
我们现在思考一个比较重要的问题：为什么在线策略算法不能重复使用过往样本，而离线策略算法可以？
关键在于对 \(G_t = r_t + \cdots\) 的估计上。
用 \(r_t+\gamma Q^{\pi_t}(s_{t+1},a_{t+1})\) 只能估计在状态 \(s_t\) 下执行动作 \(a_t\) 后，遵循策略 \(\pi_t\) 的期望回报，当策略已经迭代到 \(\pi_{t+n}\) 时，由于 \(\pi_{t+n} \gg \pi_{t}\) ，用 \(\pi_t\) 估计的数据无法帮助策略进一步迭代提升了。
用 \(r_t + \gamma\max_{a'}Q^{\pi_k}(s_{t+1},a')\) 可以估计在状态 \(s_t\) 下执行动作 \(a_t\) 后，遵循最新策略 \(\pi_k\) 的期望回报。
// TODO 理解更深了之后再来更新。