[RL Note] Q 学习:离轨策略下的时序差分控制

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 学习是离轨的,但它估计的是未知策略的动作价值,因此不需要重要度采样比来修正不同策略在动作选择上的差异。