[RL Note] Sarsa:同轨策略下的时序差分控制

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$ 是终止状态