[RL Notes] Sarsa:同轨策略下的时序差分控制
Contents [show]
1. 预测算法
通过 TD(0) 算法可以得到状态价值函数,而为了在广义策略迭代中使用时序差分方法,我们需要的是动作价值函数。
不同于 TD(0) 算法中只考虑状态之间的转换,现在要考虑“状态-动作”二元组之间的转换,并学习每个“状态-动作”二元组的价值。类似 TD(0) 对状态价值的更新,对“状态-动作”二元组价值的更新如下所示。
\begin{equation} Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t) \big] \tag{1} \end{equation}
式 (1) 所示的更新规则使用了五元组 (S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}),智能体在状态 S_t 选择动作 A_t,收到了收益 R_t 并进入状态 S_{t+1}。由于预测的是“状态-动作”二元组的价值,因此还需要知道 t+1 时刻选择的动作 A_{t+1},才能更新 (S_t, A_t) 的价值。A_{t+1} 可以通过所要评价的策略 \pi 来生成。上述算法称为 Sarsa 算法,取自五元组 (S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}) 的字母。
通过 Sarsa 算法,就可以学习某个特定策略的动作状态价值函数,以此进行策略评估。
2. 控制算法
基于 Sarsa 预测算法,可以很容易地得到一个同轨策略的控制算法——持续地估计行动策略 \pi 的动作价值函数 q_\pi,并以 q_\pi 为基础朝着贪心优化的方向改变 \pi。此外也可以采用 \varepsilon-贪心或 \varepsilon-软性策略。完整算法如下所示。
Sarsa(同轨策略下的 TD 控制)算法,用于估计 Q \approx q_\pi
对所有 s \in mathcal{S},a \in \mathcal{A}(s),任意初始化 Q(s, a),其中 Q(终止状态, \cdot) = 0
对每幕循环:
初始化 S
使用从 Q 得到的策略(例如 \varepsilon-贪心),在 S 处选择 A
对幕中的每一步循环:
执行动作 A,观察到 R, S’
使用从 Q 得到的策略(例如 \varepsilon-贪心),在 S’ 处选择 A’
Q(S, A) \leftarrow Q(S, A) + \alpha \big[ R + \gamma Q(S’, A’) – Q(S_t, A_t) \big]
S \leftarrow S’; \; A \leftarrow A’;
直到 S 是终止状态