Sarsa
引入
策略迭代
回忆 RL 动态规划 中的策略迭代算法，它的大致思想是，先使用基于 Bellman 方程改造而来的迭代算法（DP），估计当前策略 \pi 的动作价值：
Q_{k + 1}(s, a) = \sum_{s' \in \mathcal{S}} p(s' | s, a) \left[r(s, a, s') + \gamma \sum_{a' \in \mathcal{A}} \pi \left(a' \middle| s' \right) Q_k(s', a') \right]
反复执行上式，Q_k 可以收敛到 Q_{\pi}。
然后，基于策略提升定理，我们只需要构造这样的一个新的确定性策略：
\pi'(a | s) = \mathbb{1}_{\{a = \arg \max Q(s, \cdot)\}}.
这类策略迭代算法的过程是：估计、提升反复循环，直到收敛到最优策略 \pi^*。
上述策略迭代算法使用了环境的转移概率 p，但也可以改为无模型算法，改造方法类似于 Q-Learning，使用采样 s', a' 代替概率加权平均（可视为对期望的无偏估计），然后使用 EMA 来更新 Q_{\pi} 的估计：
Q_{k + 1}(s, a) = Q_k(s, a) + \alpha \left[ r(s, a) + \gamma Q_k(s', a') - Q_k(s, a) \right].
但是算法仍然需要经过“估计—提升”的循环，计算效率较低。
广义策略迭代
而 Sarsa 则属于广义策略迭代（generalized policy iteration）。
在策略迭代算法中，“估计—提升”循环导致了计算量的上升，Sarsa 直接把两个步骤拆碎、混合起来交替进行：
- 执行 s \xrightarrow{a} s'，获得奖励 r
- 使用 \epsilon-greedy 选出当前状态 s' 下能获得最大 Q 值估计 \hat{Q}(s', a') 的动作 a'（直接对动作提升）
- 直接用 EMA 更新 \hat{Q}(s, a)（估计）
- 令 s \leftarrow s', a \leftarrow a'，用于下一轮循环
直观上看，这里把 EMA 更新 Q 的过程也视为了一步“估计”，然后在反复的迭代中，局部的、错误的更新会被平均抹除，最终收敛到最优策略 Q^*。
BEYOND THE ARTICLE
读完了，有什么想法？
阅读已保存的问答示例，并循着引用回到原文。
— 本文完 — 返回文章列表