[RL Notes] Q 学习：离轨策略下的时序差分控制
Contents
1. Q 学习
Q 学习是一种离轨策略下时序差分控制算法，它的更新规则为
\begin{equation}
Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[R_{t+1} + \gamma \max_{a}Q(S_{t+1}, a) – Q(S_t, A_t) \big] \tag{1}
\end{equation}
式 $(1)$ 在更新待学习的动作价值函数 $Q$ 时，采用了对最优动作价值函数 $q_*$ 的直接近似，而与行动策略无关。
Q 学习算法的流程如下所示。
Q 学习（离轨策略下的时序差分控制）算法，用于预测 $\pi \approx \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(S, A) \leftarrow Q(S, A) + \alpha \big[R + \gamma \max_{a}\;Q(S’, a) – Q(S, A) \big]$
$S \leftarrow S’$
直到 $S$ 是终止状态
2. Sarsa 与 Q 学习
回顾 Sarsa 预测算法 的更新规则
\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{2}
\end{equation}
它使用的 $A_{t+1}$ 来自行动策略。注意到式 $(2)$ 和动作价值的贝尔曼方程
\begin{equation}
q_\pi(s, a) = \sum_{s’} \sum_{r} p(s’, r | s, a) \Big[ r + \gamma \sum\limits_{a’} \pi(a’|s’) q_\pi (s’, a’) \Big] \tag{3}
\end{equation}
的相似性，式 $(2)$ 中的 $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ 和式 $(3)$ 中的 $r + \gamma \sum_{a’} \pi(a’|s’) q_\pi (s’, a’)$ 有着类似地结构。Sarsa 实际上一个基于采样求解贝尔曼方程的算法。
Q 学习也是一种基于采样求解贝尔曼方程的算法，但它求解的是贝尔曼最优方程
\begin{equation}
q_*(s, a) = \sum_{s’} \sum_{r} p(s’, r | s, a) \Big[ r + \gamma \max_{a} q_* (s’, a’) \Big] \tag{4}
\end{equation}
最优方程使得 Q 学习能够直接学习 $q_*$，而不必在策略改善和策略评估之间来回切换。
由此可见，Sarsa 基于贝尔曼方程，可以将它看成是一种基于采样的策略迭代，使用贝尔曼方程计算特定策略的动作价值。而 Q 学习基于贝尔曼最优方程，可以将它看成是一种基于采样的价值迭代，迭代式地应用贝尔曼最优方程。只要所有“动作-状态”二元组都可以持续更新，Q 学习就能正确收敛。
3. 离轨策略
由式 $(2)$ 可见，Sarsa 通过行动策略自举下一个时刻的动作 $A_{t+1}$，行动策略和目标策略一致，是一种同轨策略的控制方法。
由式 $(3)$ 可见，Q 学习自举了状态 $S_{t+1}$ 下具有最大动作价值的动作 $\max_{a}Q(S_{t+1}, a)$，自举的动作相当于是从最优策略中采样，而不是从行动策略中采样。可见 Q 学习学到的是所能选择的最优动作，而不是实际选择的动作，因此它是一种离轨策略的控制方法。Q 学习的目标策略始终是对当前价值的贪婪策略，而它的行动策略可以是任意能够持续访问所有“动作-状态”二元组的策略，如 $\varepsilon$-贪心。
回顾智能体的目标策略 $\pi(A|S)$ 定义了在给定状态 $S$ 下选择每个动作 $A$ 的概率，结合动作价值函数，可以计算给定状态下的回报为
\begin{equation}
\sum_{a’} \pi(a’|S_{t+1}, a’) = \mathbb{E}_{\pi}[G_{t+1}|S_{t+1}]
\end{equation}
因为 Q 学习的目标策略始终是对当前价值的贪婪策略，智能体在给定状态下选择所有非最大价值动作的概率为 $0$，故而该状态下的期望回报就等于该状态下最大的动作价值。虽然 Q 学习是离轨的，但它估计的是未知策略的动作价值，因此不需要重要度采样比来修正不同策略在动作选择上的差异。