【强化学习】7-时序差分方法
Categories: RL
目录
- 一、例子
- 二、TD Learning of [state values]
- 三、TD Learning of [action values]: Sarsa
- 四、TD Learning of [action values]: Expected Sarsa
- 五、TD Learning of [action values]: n-step Sarsa
- 六、TD Learning of [ optimal action values]: Q-learning⭐️
- 七、TD 算法总结及统一视角
- 参考
一、例子
在深入TD学习之前，我们先通过几个逐步复杂的例子，回顾如何使用Robbins-Monro (RM) 算法求解根查找问题。这将为理解TD算法打下基础。
- 示例1：简单均值估计
- 问题：计算 $w = \mathbb{E}[X]$，基于 $X$ 的独立同分布样本 ${x}$。
- 转化为求根问题：定义 $g(w) = w - \mathbb{E}[X] = 0$。
- 带噪声的观测：$\tilde{g}(w, \eta) = w - x = g(w) + \eta$。
- RM算法：$w_{k+1} = w_k - \alpha_k \tilde{g}(w_k, \eta_k) = w_k - \alpha_k (w_k - x_k)$。
- 示例2：函数均值估计
- 问题：计算 $w = \mathbb{E}[v(X)]$，基于样本 ${x}$。
- 定义：$g(w) = w - \mathbb{E}[v(X)]$，$\tilde{g}(w, \eta) = w - v(x)$。
- RM算法：$w_{k+1} = w_k - \alpha_k [w_k - v(x_k)]$。
- 示例3：更复杂函数的均值估计
- 问题：计算 $w = \mathbb{E}[R + \gamma v(X)]$，其中 $R, X$ 是随机变量，$\gamma$ 是常数，$v(\cdot)$ 是一个函数。
- 定义：$g(w) = w - \mathbb{E}[R + \gamma v(X)]$，$\tilde{g}(w, \eta) = w - [r + \gamma v(x)]$。
- RM算法：$w_{k+1} = w_k - \alpha_k [w_k - (r_k + \gamma v(x_k))]$。
以上三个问题都可以通过RM算法求解，看到这里已经能够发现，实际上 $R$ 就是 reward，$\gamma$ 就是折扣因子，而 $v$ 就是 state value。我们将看到，TD算法具有类似的表达形式。
二、TD Learning of [state values]
1. 算法描述
TD 算法是基于数据来实现的强化学习，所需的数据（or experience）即：遵循给定策略 $\pi$ 生成的轨迹 $(s_0, r_1, s_1, …, s_t, r_{t+1}, s_{t+1}, …)$ 或 ${(s_t, r_{t+1}, s_{t+1})}_t$。
TD 算法如下： \(\begin{align} v_{t+1}(s_t) &= v_t(s_t) - \alpha_t(s_t) \left[ v_t(s_t) - \left[ r_{t+1} + \gamma v_t(s_{t+1}) \right] \right] \label{eq:update} \\ v_{t+1}(s) &= v_t(s), \quad \forall s \neq s_t \label{eq:visit} \end{align}\) 其中 $t = 0, 1, 2, \ldots$。$v(s)$ 中的 $s$ 是指在 state space 当中的任何一个状态，任何一个状态 $s$ 都会有一个 $v$，这个 $v$ 是用来近似 state value $v_\pi(s)$ 的。在一个 episode 里的第 $t$ 时刻，访问到的状态即 $s_t$，$v_t(s_t)$ 是 $t$ 时刻对 $v_\pi(s_t)$ 的估计，$\alpha_t(s_t)$ 是在 $t$ 时刻针对状态 $s_t$ 的学习率。
公式 $\eqref{eq:update}$ 的目的是，在 $t$ 时刻，有了一个状态 $s_t$ 以及对应的 $v_t(s_t)$，我们要更新它得到 $v_{t+1}(s_t)$。公式 $\eqref{eq:visit}$ 的目的是，对于在 $t$ 时刻没有被访问的状态，它们的 $v_{t+1}(s)$ 保持不变。
对 TD 算法可以注释如下： \(\begin{equation} \underbrace{v_{t+1}(s_t)}_{\text{new estimate} } = \underbrace{v_t(s_t)}_{\text{current estimate} } - \alpha_t(s_t) \overbrace{\left[ v_t(s_t) - \underbrace{\left[ r_{t+1} + \gamma v_t(s_{t+1}) \right]}_{\text{TD target } \bar{v}_t} \right]}^{\text{TD error } \delta_t} \end{equation}\) 这里，$\bar{v}_t \doteq r_{t+1} + \gamma v_t(s_{t+1})$ 被称为 TD target。$\delta_t \doteq v_t(s_t) - [r_{t+1} + \gamma v_t(s_{t+1})] = v_t(s_t) - \bar{v}_t$ 被称为 TD error。很明显，新估计值 $v_{t+1}(s_t)$ 是当前估计值 $v_t(s_t)$ 和 TD error 的组合。
首先，为什么 $\bar{v}_t$ 被称为 TD target？这是因为算法驱使 $v(s_t)$ 向 $\bar{v}_t$ 靠近。我们有： \(\begin{equation} \begin{aligned} & v_{t+1}(s_t) = v_t(s_t) - \alpha_t(s_t)[v_t(s_t) - \bar{v}_t] \\ \Longrightarrow \quad & v_{t+1}(s_t) - \bar{v}_t = v_t(s_t) - \bar{v}_t - \alpha_t(s_t)[v_t(s_t) - \bar{v}_t] \\ \Longrightarrow \quad & v_{t+1}(s_t) - \bar{v}_t = [1 - \alpha_t(s_t)][v_t(s_t) - \bar{v}_t] \\ \Longrightarrow \quad & |v_{t+1}(s_t) - \bar{v}_t| = |1 - \alpha_t(s_t)| |v_t(s_t) - \bar{v}_t| \end{aligned} \end{equation}\) 由于 $\alpha_t(s_t)$ 是一个很小的正数，有： \(\begin{equation} 0 < 1 - \alpha_t(s_t) < 1 \end{equation}\) 因此： \(\begin{equation} \left|v_{t+1}(s_t) - \bar{v}_t\right| \leq \left|v_t(s_t) - \bar{v}_t\right| \end{equation}\) 这意味着 $v(s_t)$ 被驱使向 $\bar{v}_t$ 靠近。
其次，对 TD error 的解释是什么？ \(\begin{equation} \delta_t = v(s_t) - \left[r_{t+1} + \gamma v(s_{t+1})\right] \end{equation}\)
- 它是两个连续时间步之间的差异（时序差分）。
- 它反映了 $v_t$ 与 $v_\pi$ 之间的差距。为了看清楚这一点，记
由于： \(\begin{equation} \mathbb{E}[\delta_{\pi, t} | S_t = s_t] = v_\pi(s_t) - \underbrace{\mathbb{E}\left[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s_t\right]}_{v_\pi(s_t)} = 0 \end{equation}\)
- 如果 $v_t = v_\pi$，那么 $\delta_t$ 应该为零（在期望意义上）。
- 因此，如果 $\delta_t$ 不为零，那么 $v_t$ 不等于 $v_\pi$。
- TD误差可以被解释为创新（innovation），意味着从经验 $(s_t, r_{t+1}, s_{t+1})$ 中获得的新信息。
我们看到：
- TD 算法仅估计给定策略的状态价值。
- 它不估计动作价值。
- 它不搜索最优策略。
2. 算法分析
TD 算法实际上在数学上做了什么？它求解了给定策略 $\pi$ 的贝尔曼方程（在没有模型的情况下）。
贝尔曼方程的一种新表达形式
策略 $\pi$ 的状态价值定义为
\(\begin{equation} v_\pi(s) = \mathbb{E}[R + \gamma G | S = s], \quad s \in \mathcal{S} \end{equation}\) 其中 $G$ 是折扣回报。由于： \(\begin{equation} \mathbb{E}[G | S = s] = \sum_a \pi(a|s) \sum_{s'} p(s'|s, a) v_\pi(s') = \mathbb{E}[v_\pi(S') | S = s] \end{equation}\) 其中 $S’$ 是下一状态，我们可以将上式重写为： \(\begin{equation} v_\pi(s) = \mathbb{E}\left[ R + \gamma v_\pi(S') | S = s \right], \quad s \in \mathcal{S} \end{equation}\) 这是贝尔曼方程的另一种表达形式。它有时被称为贝尔曼期望方程，是设计和分析TD算法的重要工具。
使用RM算法求解上面的贝尔曼方程
首先我们定义： \(\begin{equation} g(v(s)) = v(s) - \mathbb{E}\left[ R + \gamma v_\pi(S') | s \right] \end{equation}\) 我们需要求解： \(\begin{equation} g(v(s)) = 0 \end{equation}\) $v_\pi(s)$ 就是上式的一个解。由于我们只能获得 $R$ 和 $S’$ 的样本 $r$ 和 $s’$，我们得到的带噪声观测是： \(\begin{equation} \begin{aligned} \tilde{g}(v(s)) &= v(s) - \left[ r + \gamma v_\pi(s') \right] \\ &= \underbrace{\left(v(s) - \mathbb{E}\left[ R + \gamma v_\pi(S') | s \right]\right)}_{g(v(s))} + \underbrace{\left(\mathbb{E}\left[ R + \gamma v_\pi(S') | s \right] - \left[ r + \gamma v_\pi(s') \right]\right)}_{\eta} \end{aligned} \end{equation}\) 因此，求解 $g(v(s)) = 0$ 的RM算法为： \(\begin{equation} \begin{aligned} v_{k+1}(s) &= v_k(s) - \alpha_k \tilde{g}(v_k(s)) \\ &= v_k(s) - \alpha_k \left(v_k(s) - \left[ r_k + \gamma v_{\color{blue}{\pi} }(s_k') \right]\right), \quad k = 1, 2, 3, \ldots \end{aligned} \label{eq:rm} \end{equation}\) 其中 $v_k(s)$ 是第 $k$ 步对 $v_\pi(s)$ 的估计；$r_k, s_k’$ 是在第 $k$ 步获得的 $R, S’$ 的样本。
公式 $\eqref{eq:rm}$ 中的 RM 算法有两个值得特别关注的假设。
- 我们必须有经验集 ${(s, r, s’)}$，其中 $k = 1, 2, 3, \ldots$。
- 我们假设对于任何 $s’$，$v_\pi(s’)$ 是已知的。
为了消除 RM 算法中的两个假设，我们可以修改它：
- 一个修改是将 ${(s, r, s’)}$ 改为 ${(s_t, r_{t+1}, s_{t+1})}$，这样算法就可以利用一个 episode 中的时序样本。
- 另一个修改是用一个估计值 $v_k(s’)$ 替换 $v_\pi(s’)$，因为我们事先不知道它。
3. 收敛性
这里直接给出其收敛条件：
如果对所有 $s \in \mathcal{S}$，有 $\sum_t \alpha_t(s) = \infty$ 且 $\sum_t \alpha_t^2(s) < \infty$，那么当 $t \to \infty$ 时，$v_t(s)$ 以概率 1 收敛到 $v_\pi(s)$。
- 该定理表明，对于给定的策略 $\pi$，状态价值可以通过 TD 算法得到。
- 条件 $\sum_t \alpha_t(s) = \infty$ 和 $\sum_t \alpha_t^2(s) < \infty$ 必须对所有 $s \in \mathcal{S}$ 成立。在 $t$ 时刻，$s = s_t$ 意味着 $s$ 在 $t$ 时刻被访问，那么此时 $\alpha_t(s) > 0$；否则，对所有其他 $s \neq s_t$，$\alpha_t(s) = 0$。这要求每个状态必须被访问无限次（或足够多次）。
- 学习率 $\alpha$ 通常被选为一个小的常数。在这种情况下，条件 $\sum_t \alpha_t^2(s) < \infty$ 不再成立。当 $\alpha$ 是常数时，仍然可以证明算法在期望意义上收敛。
4. TD 与 MC 的对比
| TD/Sarsa学习 | MC学习 |
|---|---|
| Online：TD 学习是在线的。它可以在收到奖励后立即更新状态/动作价值。 | Offline：MC 学习是离线的。它必须等到一个完整的幕收集完毕。 |
| Continuing tasks：由于 TD 学习是在线的，它可以处理 episodic tasks 和 continuing tasks。 | Episodic tasks：由于 MC 学习是离线的，它只能处理具有终止状态的 episodic tasks。 |
| Bootstrapping：价值的更新依赖于该价值的先前估计。因此，它需要初始猜测。 | Non-bootstrapping：它可以直接估计状态/动作价值，无需任何初始猜测。 |
| 估计方差低：TD 比 MC 方差低，因为涉及的随机变量更少。例如，Sarsa 需要 $R_{t+1}, S_{t+1}, A_{t+1}$。 | 估计方差高：要估计 $q_\pi(s_t, a_t)$，需要 $R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots$ 的样本。假设每个 episode 的长度为 $L$。可能有 $|\mathcal{A}|^L$ 种可能的 episode。 |
三、TD Learning of [action values]: Sarsa
1. 算法描述
上一节介绍的 TD 算法只能估计状态价值。接下来，我们介绍 Sarsa，一种可以直接估计动作价值的算法。
首先，我们的目标是估计给定策略 $\pi$ 的动作价值。假设有一些经验 ${(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})}_t$。我们可以使用以下 Sarsa 算法来估计动作价值： \(\begin{align} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[ q_t(s_t, a_t) - \left[ r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1}) \right] \right] \\ q_{t+1}(s, a) &= q_t(s, a), \quad \forall (s, a) \neq (s_t, a_t) \end{align}\) 其中 $t = 0, 1, 2, \ldots$。
- $q_t(s_t, a_t)$ 是对 $q_\pi(s_t, a_t)$ 的估计。
- $\alpha_t(s_t, a_t)$ 是依赖于 $s_t, a_t$ 的学习率。
- 为什么这个算法叫 Sarsa？因为算法的每一步都涉及到 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$。Sarsa 是状态-动作-奖励-状态-动作的缩写。
- Sarsa与之前的 TD 学习算法有什么关系？我们可以通过将 TD 算法中的状态价值估计 $v(s)$ 替换为动作价值估计 $q(s, a)$ 来得到Sarsa。因此，Sarsa 是 TD 算法的动作价值版本。
- Sarsa 算法在数学上做了什么？Sarsa 的表达式表明它是一个求解以下方程的随机近似算法：
这是用动作价值表示的贝尔曼方程的另一种表达形式。
2. 收敛性与伪代码
收敛条件类似：
如果对所有 $(s, a)$，有 $\sum_t \alpha_t(s, a) = \infty$ 且 $\sum_t \alpha_t^2(s, a) < \infty$，那么当 $t \to \infty$ 时，$q_t(s, a)$ 以概率 1 收敛到动作价值 $q_\pi(s, a)$。
强化学习的最终目标是找到最优策略。为此，我们可以将 Sarsa 与策略改进步骤结合起来。实际上，多数时候这个组合算法也被称为 Sarsa，伪代码如下：
\[\begin{equation*} \begin{aligned} & \text{For each episode, do} \\ & \quad \quad \text{If the current } s_t \text{ is not the target state, do} \\ & \quad \quad \quad \quad \text{Collect the experience } (s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}) \text{ : In particular, take action } a_t \text{ following } \pi_t, \\ & \quad \quad \quad \quad \text{generate } r_{t+1}, s_{t+1}, \text{ and then take action } a_{t+1} \text{ following } \pi_t(s_{t+1}). \\ & \quad \quad \quad \quad \text{Update q-value:} \\ & \quad \quad \quad \quad \quad \quad q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[q_t(s_t, a_t) - \left[r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})\right]\right] \\ & \quad \quad \quad \quad \text{Update policy:} \\ & \quad \quad \quad \quad \quad \quad \pi_{t+1}(a|s_t) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1) \quad \text{if } a = \arg\max_a q_{t+1}(s_t, a) \\ & \quad \quad \quad \quad \quad \quad \pi_{t+1}(a|s_t) = \frac{\epsilon}{|\mathcal{A}|} \quad \text{otherwise} \end{aligned} \end{equation*}\]其中：
- $s_t$ 的策略在 $q(s_t, a_t)$ 更新后立即更新。这是基于广义策略迭代的思想。
- 策略是 $\epsilon$-greedy 的，而不是贪婪的，以更好地平衡利用和探索。
四、TD Learning of [action values]: Expected Sarsa
Sarsa的 一个变体是 Expected Sarsa 算法：
\[\begin{align} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t) \Big[ q_t(s_t, a_t) - (r_{t+1} + \gamma \mathbb{E}[q_t(s_{t+1}, A)]) \Big] \\ q_{t+1}(s, a) &= q_t(s, a), \quad \forall (s, a) \neq (s_t, a_t) \end{align}\]其中 \(\begin{equation} \mathbb{E}[q_t(s_{t+1}, A)] = \sum_a \pi_t(a \mid s_{t+1}) q_t(s_{t+1}, a) \doteq v_t(s_{t+1}) \end{equation}\) 与 Sarsa 相比：
- TD target 从 Sarsa 中的 $r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$ 变为 Expected Sarsa 中的 $r_{t+1} + \gamma \mathbb{E}[q_t(s_{t+1}, A)]$。
- 需要更多计算。但这是有益的，因为它将 Sarsa 中的随机变量从 ${s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}}$ 减少到 ${s_t, a_t, r_{t+1}, s_{t+1}}$，降低了估计方差。
Expected Sarsa 在数学上解决了什么问题？它实际上是以下方程的随机近似算法求解： \(\begin{equation} q_\pi(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma \mathbb{E}_{A_{t+1} \sim \pi(S_{t+1})}[q_\pi(S_{t+1}, A_{t+1})] \mid S_t = s, A_t = a \right], \quad \forall s, a \end{equation}\) 上述方程是贝尔曼方程的另一种表达形式： \(\begin{equation} q_\pi(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a \right] \end{equation}\)
五、TD Learning of [action values]: n-step Sarsa
n-step Sarsa 可以统一 Sarsa 和蒙特卡洛（MC）算法。我们知道，动作价值的定义是： \(\begin{equation} q_\pi(s, a) = \mathbb{E}\left[ G_t \mid S_t = s, A_t = a \right] \end{equation}\) 折扣回报 $G_t$ 可以写成不同的形式：
\[\begin{equation*} \begin{aligned} \text{Sarsa} \quad \longleftarrow \quad & G_t^{(1)} = R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \\ & G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 q_\pi(S_{t+2}, A_{t+2}) \\ & \quad \quad \quad \vdots \\ \text{n-step Sarsa} \quad \longleftarrow \quad & G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n q_\pi(S_{t+n}, A_{t+n}) \\ \text{MC} \quad \longleftarrow \quad & G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots \end{aligned} \end{equation*}\]注意这里 $G_t = G_t^{(1)} = G_t^{(2)} = G_t^{(n)} = G_t^{(\infty)}$，上标仅表示 $G_t$ 的不同分解层次。
对比一下：
- Sarsa 旨在求解：
- MC 旨在求解：
- n-step Sarsa 旨在求解：
因此 n-step Sarsa 算法是： \(\begin{equation} \begin{array}{l} q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)\big[ q_t(s_t, a_t) - \left[ r_{t+1} + \gamma r_{t+2} + \ldots + \gamma^n q_t(s_{t+n}, a_{t+n}) \right] \big] \end{array} \end{equation}\) n-step Sarsa 更具一般性，因为当 $n=1$ 时，它变成 Sarsa 算法；当 $n=\infty$ 时，它变成 MC 算法。
对于 n-step Sarsa，它需要采集的数据是 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, \ldots, r_{t+n}, s_{t+n}, a_{t+n})$。由于在时刻 $t$，$(r_{t+n}, s_{t+n}, a_{t+n})$ 尚未收集，我们无法在时刻 $t$ 实现 n-step Sarsa。但是，在实现时，我们可以等到时刻 $t+n$ 再更新 $(s_t, a_t)$ 的 $q$ 值： \(\begin{equation} q_{\color{blue}{ {t+n} }}(s_t, a_t) = q_{\color{blue}{ {t+n-1} }}(s_t, a_t) - \alpha_{\color{blue}{ {t+n-1} }}(s_t, a_t) \big[ q_{\color{blue}{ {t+n-1} }}(s_t, a_t) - \left[ r_{t+1} + \gamma r_{t+2} + \ldots + \gamma^n q_{\color{blue}{ {t+n-1} }}(s_{t+n}, a_{t+n}) \right] \big] \end{equation}\) 由于 n-step Sarsa 包含了 Sarsa 和 MC 作为两个极端情况，其性能是 Sarsa 和 MC 的混合：
- 如果 $n$ 很大，其性能接近 MC，因此方差大但偏差小。
-
如果 $n$ 很小，其性能接近 Sarsa，因此由于初始猜测而具有较大的偏差，但方差相对较低。
- 最后，n-step Sarsa 也只用于策略评估，它可以与策略改进相结合以搜索最优策略。
六、TD Learning of [ optimal action values]: Q-learning⭐️
接下来，我们介绍 Q-learning，这是最广泛使用的 RL 算法之一。Sarsa 可以估计给定策略的动作价值，它必须与策略改进步骤结合才能找到最优策略。而 Q-learning 可以直接估计最优动作价值，从而得到最优策略。
1. 算法描述
Q-learning 的算法如下： \(\begin{align} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[ q_t(s_t, a_t) - \left[ r_{t+1} + \gamma \max_{a \in \mathcal{A} } q_t(s_{t+1}, a) \right] \right] \\ & q_{t+1}(s, a) = q_t(s, a), \quad \forall (s, a) \neq (s_t, a_t) \end{align}\) Q-learning 与 Sarsa 非常相似。它们仅在 TD target 上有所不同：
- Q-learning 中的 TD target 是 $r_{t+1} + \gamma \max_{a \in \mathcal{A} } q_t(s_{t+1}, a)$。
- Sarsa 中的 TD target 是 $r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$。
Q-learning 旨在解决什么数学问题？它旨在解决如下方程： \(\begin{equation} q(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma \max_a q(S_{t+1}, a) \Big| S_t = s, A_t = a \right], \quad \forall s, a \end{equation}\) 这是用动作价值表示的贝尔曼最优方程。
2. on-policy 和 off-policy
在进一步研究 Q-learning 之前，我们首先介绍两个重要概念：on-policy 和 off-policy。在强化学习中，存在两种策略：
- behavior policy，用于生成经验样本。
-
target policy，用于不断更新直至最优策略。
- 当 behavior policy 与 target policy 相同时，这种学习称为 on-policy。
- 当它们不同时，这种学习称为 off-policy。
off-policy 的优势：
- 它可以基于任何其他策略生成的经验样本来搜索最优策略。
- 例如，behavior policy 可以被选择为具有探索性的策略，如果我们想估计所有 state-action pairs 的动作价值，我们可以使用探索性强的策略，采用足够多的 episode 访问到每个 state-action pairs。
如何判断一个 TD 算法是 on-policy 还是 off-policy？
- 首先，检查算法在数学上做什么。
- 其次，检查实现该算法需要什么。
下面看一下之前学习过的三种算法：
Sarsa 是 on-policy
Sarsa 旨在求解给定策略 $\pi$ 的贝尔曼方程： \(\begin{equation} q_\pi(s, a) = \mathbb{E}\left[ R + \gamma q_\pi(S', A') | s, a \right], \quad \forall s, a \end{equation}\) 其中 $R \sim p(R|s, a)$, $S’ \sim p(S’|s, a)$, $A’ \sim \pi(A’|s’)$。
它的算法是： \(\begin{equation} q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[ q_t(s_t, a_t) - [r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})] \right] \end{equation}\) 这需要 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$：
- 如果 $(s_t, a_t)$ 给定，那么 $r_{t+1}$ 和 $s_{t+1}$ 不依赖于任何策略，由 $p(r|s,a)$ 和 $p(s’|s,a)$ 决定。
- $a_{t+1}$ 是遵循 $\pi_t(s_{t+1})$ 生成的。
- $\pi_t$ 既是 target policy 也是 behavior policy。
MC 是 on-policy
MC 方法旨在求解： \(\begin{equation} q_\pi(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma R_{t+2} + \ldots | S_t = s, A_t = a \right], \quad \forall s, a \end{equation}\) 其中样本是遵循给定策略 $\pi$ 生成的。MC 方法的实现是：
\(\begin{equation} q(s, a) \approx r_{t+1} + \gamma r_{t+2} + \ldots \end{equation}\) 一个策略被用来生成样本，这些样本又被用来估计该策略的动作价值。基于动作价值，进一步改进该策略，因此是 on-policy 的。
Q-learning 是 off-policy
Q-learning 旨在求解贝尔曼最优方程： \(\begin{equation} q(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma \max_a q(S_{t+1}, a) \mid S_t = s, A_t = a \right], \quad \forall s, a \end{equation}\) 其算法是： \(\begin{equation} q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[ q_t(s_t, a_t) - \left[ r_{t+1} + \gamma \max_{a \in \mathcal{A} } q_t(s_{t+1}, a) \right] \right] \end{equation}\) 这需要 $(s_t, a_t, r_{t+1}, s_{t+1})$。 如果 $(s_t, a_t)$ 给定，那么 $r_{t+1}$ 和 $s_{t+1}$ 不依赖于任何策略。而用于从 $s_t$ 生成 $a_t$ 的行为策略可以是任何策略。target policy 则用于收敛到最优策略。由于 Q-learning 是 off-policy，它可以以 off-policy 或 on-policy 的方式实现。
3. 伪代码
on-policy 版本，实际上和 Sarsa 很像：
\[\begin{equation*} \begin{aligned} & \text{For each episode, do} \\ & \quad \quad \text{If the current } s_t \text{ is not the target state, do} \\ & \quad \quad \quad \quad \text{Collect the experience } (s_t, a_t, r_{t+1}, s_{t+1}) \text{ : In particular, take action } a_t \text{ following } \pi_t(s_t), \\ & \quad \quad \quad \quad \text{generate } r_{t+1}, s_{t+1}. \\ & \quad \quad \quad \quad \text{Update q-value:} \\ & \quad \quad \quad \quad \quad \quad q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[ q_t(s_t, a_t) - \left[ r_{t+1} + \gamma \max_{a \in \mathcal{A} } q_t(s_{t+1}, a) \right] \right] \\ & \quad \quad \quad \quad \text{Update policy:} \\ & \quad \quad \quad \quad \quad \quad \pi_{t+1}(a|s_t) = 1 - \frac{\epsilon}{|\mathcal{A}|}(|\mathcal{A}| - 1) \quad \text{if } a = \arg\max_a q_{t+1}(s_t, a) \\ & \quad \quad \quad \quad \quad \quad \pi_{t+1}(a|s_t) = \frac{\epsilon}{|\mathcal{A}|} \quad \text{otherwise} \end{aligned} \end{equation*}\]off-policy 版本：
\[\begin{equation*} \begin{aligned} & \text{For each episode } \{ s_0, a_0, r_1, s_1, a_1, r_2, \dots \} \text{ generated by } \pi_b \text{ (behavior policy), do} \\ & \quad \quad \text{For each step } t=0,1,2, \dots \text{ of the episode, do} \\ & \quad \quad \quad \quad \text{Update q-value:} \\ & \quad \quad \quad \quad \quad \quad q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) \left[ q_t(s_t, a_t) - \left[ r_{t+1} + \gamma \max_{a \in \mathcal{A} } q_t(s_{t+1}, a) \right] \right] \\ & \quad \quad \quad \quad \text{Update target policy } \pi_T :\\ & \quad \quad \quad \quad \quad \quad \pi_{T,t+1}(a|s_t) = 1 \text{ if } a = \arg\max_a q_{t+1}(s_t, a) \\ & \quad \quad \quad \quad \quad \quad \pi_{T,t+1}(a|s_t) = 0 \quad \text{otherwise} \end{aligned} \end{equation*}\]七、TD 算法总结及统一视角
本章中介绍的所有算法都可以用一个统一的表达式表示：
\(\begin{equation} q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) [q_t(s_t, a_t) - \bar{q}_t] \end{equation}\) 其中 $\bar{q}_t$ 是 TD target。不同的 TD 算法有不同的 $\bar{q}_t$：
| 算法 | $\bar{q}_t$ 的表达式 |
|---|---|
| Sarsa | $\bar{q}_t = r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$ |
| n-step Sarsa | $\bar{q}_t = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^n q_t(s_{t+n}, a_{t+n})$ |
| Expected Sarsa | $\bar{q}_t = r_{t+1} + \gamma \sum_a \pi_t(a \mid s_{t+1}) q_t(s_{t+1}, a)$ |
| Q-learning | $\bar{q}_t = r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)$ |
| 蒙特卡洛 | $\bar{q}_t = r_{t+1} + \gamma r_{t+2} + \cdots$ |
其中，通过设置 $\alpha_t(s_t, a_t) = 1$ 从而 $q_{t+1}(s_t, a_t) = \bar{q}_t$，MC 方法也可以用这种统一表达式表示。
所有算法都可以被视为求解贝尔曼方程或贝尔曼最优方程的随机近似算法：
| 算法 | 旨在求解的方程 |
|---|---|
| Sarsa | 贝尔曼期望方程：$q_\pi(s,a) = \mathbb{E}[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t=s, A_t=a]$ |
| n-step Sarsa | 贝尔曼期望方程：$q_\pi(s,a) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + … + \gamma^n q_\pi(s_{t+n}, a_{t+n}) \mid S_t=s, A_t=a]$ |
| Expected Sarsa | 贝尔曼期望方程：$q_\pi(s,a) = \mathbb{E}[R_{t+1} + \gamma \mathbb{E}_{A_{t+1} }[q_\pi(S_{t+1}, A_{t+1})] \mid S_t=s, A_t=a]$ |
| Q-learning | 贝尔曼最优方程：$q(s,a) = \mathbb{E}[R_{t+1} + \max_a q(S_{t+1}, a) \mid S_t=s, A_t=a]$ |
| 蒙特卡洛 | 贝尔曼期望方程：$q_\pi(s,a) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + … \mid S_t=s, A_t=a]$ |