7.3-行动值估计:n步Sarsa
本节介绍n-step Sarsa算法——Sarsa的推广形式。我们将看到，Sarsa与蒙特卡洛算法实际上是n-step Sarsa的两种极端情况。
首先回顾行动值的定义为：
其中\(G_t\)是折扣回报：
实际上，\(G_t\)也可以分解为不同形式：
上式中\(G_t = G^{(1)}_t = G^{(2)}_t = G^{(n)}_t = G^{(\infty)}_t\)的上标仅表示\(G_t\)的不同分解方式。它们本质上是相等的。将\(G^{(n)}_t\)的不同分解形式代入\((7.16)\)式中的\(q_\pi(s, a)\)会得到不同的算法。
-
当\(n=1\)，我们有
\[q_\pi(s,a)=\mathbb{E}[G_t^{(1)}|s,a]=\mathbb{E}[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})|s,a].\]求解该方程的相应随机近似算法为
\[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],\]即式\((7.12)\)中的Sarsa算法。
-
当\(n=\infty\)，我们有
\[q_\pi(s,a)=\mathbb{E}[G_t^{(\infty)}|s,a]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\ldots|s,a].\]求解该方程的对应算法为
\[q_{t+1}(s_t,a_t)=g_t\doteq r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\ldots,\]其中\(g_t\)是\(G_t\)的一个样本。实际上这就是蒙特卡洛算法，该算法通过从\((s_t, a_t)\)起始的回报来近似\((s_t, a_t)\)的行动值。
-
当\(n\)取一般的自然数时，我们有
\[q_\pi(s,a)=\mathbb{E}[G_t^{(n)}|s,a]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^nq_\pi(S_{t+n},A_{t+n})|s,a].\]求解上述方程的随机近似算法为
\[\begin{aligned}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 r_{t+2}+\cdots+\gamma^{n}q_{t}(s_{t+n},a_{t+n})\right)\right].\end{aligned}\tag{7.17}\]该算法称为n-step Sarsa。
综上所述，n-step Sarsa是一种更通用的算法：当\(n=1\)时退化为Sarsa算法；当\(n=\infty\)（通过设定\(\alpha_t=1\)）时则演化为MC学习算法。由于n-step Sarsa算法包含Sarsa与蒙特卡洛这两种极端情况，其性能介于两者之间便不足为奇。当\(n\)取值较大时，n步Sarsa接近蒙特卡洛，此时估计值具有较高的方差但偏差较小；当\(n\)取值较小时，n步Sarsa则接近Sarsa算法，此时估计值偏差较大但方差较低。
最后，这里介绍的n-Step Sarsa仅可用于评价一个给定的策略。为了得到最优策略，它需要与策略改进步骤结合，具体流程类似于Sarsa,这里不再赘述，更多信息可参见[3,第9章]。值得注意的是，在实现n-Step Sarsa算法时，我们需要经验样本\((s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, ..., r_{t+n}, s_{t+n}, a_{t+n})\)。由于我们在\(t\)时刻还无法拿到样本\((r_{t+n}, s_{t+n}, a_{t+n})\),因此必须等到t+n时刻才能更新\((s_t, a_t)\)的\(q\)值。为此，式\((7.17)\)可以被重新写为
其中\(q_{t+n}(s_t, a_t)\)是时刻 \(t+n\)对\(q_\pi(s_t, a_t)\)的估计值。