时序差分（TD）相关算法之Sarsa算法介绍

算法概述

在介绍了用于估计给定策略state value（状态值）的经典TD算法后，在此基础上介绍包括Sarsa、expected Sarsa、n step Sarsa等在内的算法，它们是Sarsa基本算法的变形，以及q learning算法。Sarsa及其变形用于估计给定策略的action value（动作值），进行policy evaluation（策略评估），结合policy improvement（策略改进）可找到最优策略；q learning直接求解optimal action value（最优动作值）从而找到最优策略。

Sarsa算法

1. 算法功能与形式：之前的TD算法估计state value，而Sarsa算法可直接估计action value。算法基于数据（experience），假设数据形式为一个集合，每个时刻$t$对应的经验是$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ 。算法更新公式为：
   • 对于当前访问的状态动作对$(s_t,a_t)$，$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-\alpha [q_t(s_t,a_t)-(r_{t+1}+\gamma q_t(s_{t+1},a_{t+1}))]$ ，与TD算法形式类似，只是将对状态值$v(s_t)$的估计变为对动作值$q(s_t,a_t)$的估计。
   • 对于未访问的状态动作对，$q$值保持不变。
   • Sarsa是state action reward state action五个单词首字母的缩写，因算法用到了$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$这些数据，即sars a。
2. 解决的数学问题与收敛性：Sarsa算法求解的是基于action value表达的贝尔曼公式$q_{\pi }(s,a)=E[r+\gamma q_{\pi }(s^{\prime },a^{\prime })]$ ，刻画了不同action value之间的关系。其收敛性定理与TD算法类似，当满足针对learning rate ${\alpha }_t$的一定条件时，$q_t(s,a)$会收敛到$q_{\pi }(s,a)$ 。
3. 结合策略改进的Sarsa算法：结合策略改进的算法也称为Sarsa，在大多数情况下，提到Sarsa即指此算法。
   • 对于每个episode（片段），若当前状态不是目标状态：在$t$时刻，根据当前策略采取动作$a_t$，得到奖励$r_{t+1}$并跳到下一个状态$s_{t+1}$ ，在$s_{t+1}$状态根据当前策略进行动作采样得到$a_{t+1}$，获取所需的experience。
   • 基于experience进行$q$值更新（$q$ value update，即policy evaluation，策略评估），计算对应的$q$值。
   • 立刻进行策略更新（policy update，即policy improvement，策略改进），采用$ϵ$-greedy策略（不是完全贪婪策略），给$q$值大的动作较大概率，给其他动作较小概率。然后用新策略生成新的experience并不断迭代。
   • 该算法有两个步骤，$q$值更新后立刻进行策略更新，与传统的policy evaluation不同（传统policy evaluation需大量数据准确估计action value），此算法基于generalized policy evaluation iteration思想（类似policy iteration分为policy evaluation和policy improvement两个步骤，但实际中可能只计算一步或几步policy evaluation就切换到策略更新）。
4. 算法示例：
   • 任务为从特定状态（左上角状态）出发找到到达目标状态的路径，与之前网格世界任务不同（之前关注每个状态的最优策略，此次只关注从特定状态到目标的策略或路径）。
   • 从初始不好的策略开始，使用Sarsa算法找到的最优策略，从左上角出发，沿概率较大方向能到达目标，但其他状态可能未达最优策略，存在找到的路径不是最短或最优的可能性（若要找所有状态的最优策略需探索所有state action pair，此任务仅进行了500次探索，即500个episode）。
   • 图示分析：横坐标为episode index（片段索引），代表500个episode。第一个图纵坐标为每个episode的total reward（总奖励），开始时策略不好，奖励较低（可能撞墙或进入不良区域得到负奖励），随策略改善奖励增大但未超过零（因采用$ϵ$-greedy策略会有负奖励）；第二个图纵坐标为episode length（片段长度），开始时策略不好，到达目标需很多步，随策略改进，到达目标的步数减少。