跳转至

7.2-行动值估计:Sarsa

本节将介绍另一种名为Sarsa的TD算法，该算法可直接估计行动值。将上一节介绍的TD算法中的状态值替换为行动值就能得到Sarsa算法。

7.2.1算法描述

给定一个策略\(\pi\)，我们的目标是估计其行动值。如果有一些由\(\pi\)生成的经验样本：\((s_0, a_0, r_1, s_1, a_1, \ldots, s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, \ldots)\)。那么使用下面的Sarsa算法来估计行动值：

\[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],\tag{7.12}\]
\[q_{t+1}(s,a)=q_t(s,a),\quad\mathrm{for~all}(s,a)\neq(s_t,a_t),\]

\(\alpha_t(s_t, a_t)\)为学习率。此处\(q_t(s_t, a_t)\)是\(q_\pi(s_t, a_t)\)的估计值。在时刻\(t\)，只更新\((s_t, a_t)\)的 \(q\)值，其余状态的 \(q\)值保持不变。

Sarsa算法的重要性质如下。

  • 该算法为何命名为"Sarsa"？这是因为其每次迭代都需要经验样本\((s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})\)。Sarsa是"状态-动作-奖励-状态-动作"(state-action-reward-state-action)的缩写形式。该算法最早由文献[35]提出，其命名则由文献[3]确立。

  • 为什么Sarsa要这样设计？读者可能已经注意到Sarsa与\((7.1)\)式中的TD算法非常相似。实际上，只需将TD算法中的状态值替换为行动值，就得到了Sarsa算法。

  • Sarsa算法的数学本质是什么？与\((7.1)\)中的TD算法类似，Sarsa是一种用于求解如下所示贝尔曼方程的随机近似算法：

    \[q_\pi(s,a)=\mathbb{E}\left[R+\gamma q_\pi(S^{\prime},A^{\prime})|s,a\right],\quad\mathrm{for~all}(s,a).\tag{7.13}\]

    方程\((7.13)\)是以基于行动值表示的贝尔曼方程。具体证明见Box \(7.3\)。

  • Sarsa算法是否收敛？由于Sarsa是\((7.1)\)推广而来，其收敛性结果与定理\(7.1\)相似。

Info

定理7.2 (Sarsa算法的收敛性).给定一个策略\(\pi\)，基于\((7.12)\)式的 Sarsa算法，如果\(\sum_t \alpha_t(s, a) = \infty\)且\(\sum_t \alpha^2_t(s, a) < \infty\)对所有\((s, a)\)成立，那么\(q_t(s, a)\)几乎必然收敛到行动值 \(q_\pi(s, a)\)（当 \(t \to \infty\)时）。

该证明过程与定理7.1类似，此处从略。需满足对所有状态-动作对\((s, a)\)均有\(\sum_t \alpha_t(s, a) = \infty\)且\(\sum_t \alpha_t^2(s, a) < \infty\)的条件。特别地，\(\sum_t \alpha_t(s, a) = \infty\)要求每个状态-动作对必须被访问无限次（或足够多次）。其中，如果\((s, a) = (s_t, a_t)\)，那么\(\alpha_t(s, a) >0\)；否则\(\alpha_t(s, a) =0\)。

7.2.2基于Sarsa算法的最优策略学习

式(7.12)中的Sarsa算法只能估计一个给定策略的动作值。要想得到最优策略，我们需要将其与“策略改进步骤”相结合，结合之后的算法通常也称为Sarsa。

算7.1给出了伪代码。可以看到，每次迭代有两个步骤：第一步是值更新，即更新被访问的状态-动作的估计值；第二步是策略更新，即新的策略要选取最大价值的动作。值得注意的是，在值被更新之后，\(s_t\)的策略会被立即更新，而并不是在更新策略之前充分地评估当时的策略，这也是基于广义策略迭代的思想。此外，在策略更新后，该策略立即被用来生成下一个经验样本。这里的策略是\(\varepsilon\)-Greedy的，因此具有一定的探索性。

算法\(7.1\)

图\(7.2\)：Sarsa算法的演示示例。所有训练回合均从左上角状态开始，并在到达目标状态（蓝色单元格）时终止。目标是找到从起始状态到目标状态的最优路径。左图显示算法获得的最终策略，右图展示各训练回合的总奖励与路径长度。

图\(7.2\)展示了一个演示Sarsa算法的仿真示例。值得注意的是，这个例子中的任务和本书之前介绍的任务都不同。之前的任务是要学习每一个状态的最优策略，而这里的任务是要学习从特定状态出发到达目标状态的最优策略。前者的任务更难，因为它要找到所有状态的最优策略；后者的任务更简单，因为它只要找到部分状态的最优策略即可。这种任务在实际中也经常遇到，例如起始位置是住所，目标位置是学校，我们只需要学习那些每天下学可能经过的最优策略即可，而不需要关心十万八千里之外的位置的策略是什么。

  • 仿真设置：在本示例中，所有训练回合均从左上角状态开始，并在目标状态终止。奖励设置为\(r_{\text{target}} =0\)，\(r_{\text{forbidden}} = r_{\text{boundary}} = -10\)，以及\(r_{\text{other}} = -1\)。此外，对所有时间步\(t\)有\(\alpha_t(s, a) =0.1\)，且\(\epsilon =0.1\)。选取初始值为\(q_0(s, a) =0\)。由初始值导出的初始策略是均匀分布的，即对所有\(s,a\)有\(\pi_0(a|s) =0.2\)。

  • 学习到的策略：图7.2左图展示了Sarsa算法学习得到的最终策略。如图所示，该策略能够成功地从起始状态引导至目标状态。然而，其他部分状态的策略可能不是最优的(第三行第一列)，这是由于这些状态未被充分探索所致。

  • 每回合的回报：图\(7.2\)右上角子图展示了每个回合的回报逐渐变化的过程。可以看出，每回合的回报呈现逐步上升趋势，这是由于初始策略性能较差，因此频繁获得负奖励；随着策略不断优化，回报会不断增加。由于这个策略是\(\varepsilon\)-Greedy的，因此还是有概率选择不好的行动，所以在460个回合时回报突然降低。

  • 每回合长度：图7.2右下子图显示每回合的长度逐渐缩短。这是因为初始策略性能较差，在抵达目标前可能绕行较多。随着策略优化，轨迹长度随之减短。值得注意的是，每回合长度可能突然增加(例如第460个回合)，对应总奖励值也会急剧下降。这是由于策略采用\(\varepsilon\)-贪婪算法，存在选择非最优行动的可能性。解决这个问题的一个简单方法是使用衰减的，即初始时\(\varepsilon\)比较大，以使得策略有较强的探索性;随后\(\varepsilon\)逐渐趋近于0，从而增加策略的最优性，减少探索性。

最后，Sarsa算法还存在若干变体，例如Expected Sarsa。感兴趣的读者可参阅Box 7.4。

评论