时序差分方法求解强化学习任务——基于同轨策略的时序差分控制(SARSA算法)

目录

上一节介绍了时序差分方法的策略评估过程以及相比于蒙特卡洛方法，时序差分方法的优势。本节将介绍时序差分方法中具有代表性的方法：基于同轨策略的时序差分控制——SARSA算法。

回顾：时序差分方法的策略评估过程

时序差分方法的最大特点就是更新的实时性，不同于蒙特卡洛方法在策略评估过程中 至少完整执行一次情节 后才能执行动量更新计算 → \to → 而是仅需要一个步骤(一次状态转移过程)，就可以根据状态转移的变化信息( V ( S t + 1 ) , R t + 1 V(S_{t+1}),R_{t+1} V(St+1​),Rt+1​)对当前时刻 t t t的价值函数 V ( S t ) V(S_t) V(St​)进行动量更新计算： V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t ) ] V(S_t) \gets V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] V(St​)←V(St​)+α[Rt+1​+γV(St+1​)−V(St​)] 这种方法不仅缩短了价值函数 V ( S t ) V(S_t) V(St​)在迭代过程中的更新周期；并且减小了内存空间的消耗。

但同为通过采样近似求解价值函数的方法，时序差分方法同样面临和蒙特卡洛方法类似的问题： 在某确定状态下，某动作 a a a发生的概率极低——导致状态/状态-动作二元组很难被访问完整 的问题。 该问题在‘蒙特卡洛方法求解强化学习任务——蒙特卡洛评估基本介绍’中提到传送门 因此，基于迭代方式中的策略变化，时序差分方法同样可以分为两种方式——同轨策略与离轨策略。

SARSA：基于同轨策略的时序差分控制

在蒙特卡洛方法求解强化学习任务——基于非试探性出发假设的蒙特卡洛控制中介绍过，为了能够生成更多可能性的状态\状态-动作二元组(以便 存在概率被访问到)，将控制过程中的策略分为两部分：

• 行为策略(behaviour policy)：用于生成样本的策略；
• 目标策略(target policy)：用于策略改进的策略；

在SARSA算法中使用的是同轨策略——行为策略和目标策略共用同一个策略，在SARSA算法视角中是如何实现这一过程的？ 构建场景如下：

• 设定某一时刻 t t t的状态与状态转移后的下一时刻状态分别为 S t , S t + 1 S_t,S_{t+1} St​,St+1​；
• 在 S t , S t + 1 S_t,S_{t+1} St​,St+1​状态下分别对应一个在该状态下有意义的动作组成的动作集合，记为 A ( S t ) , A ( S t + 1 ) \mathcal A(S_t),\mathcal A(S_{t+1}) A(St​),A(St+1​)；
• 由于是同轨策略——因此保证在 S t , S t + 1 S_t,S_{t+1} St​,St+1​状态下选择动作的策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)满足 软性策略 的要求： a ∈ A ( s ) → π ( a ∣ s ) > 0 \begin{aligned} a \in \mathcal A(s) \to \pi(a \mid s) > 0 \end{aligned} a∈A(s)→π(a∣s)>0​ 多说一句，这里的 π ( a ∣ s ) \pi(a \mid s) π(a∣s)是一个2维矩阵，它存储了所有的状态-动作二元组的条件概率分布信息。 其中 m m m表示动作集合 A \mathcal A A中包含动作的数量； n n n表示状态集合 S \mathcal S S中包含状态的数量； π ( a ∣ s ) = ( π ( a 1 ∣ s 1 ) π ( a 1 ∣ s 2 ) ⋯ π ( a 1 ∣ s n ) π ( a 2 ∣ s 1 ) π ( a 2 ∣ s 2 ) ⋯ π ( a 2 ∣ s n ) ⋮ ⋮ ⋱ ⋮ π ( a m ∣ s 1 ) π ( a m ∣ s 2 ) ⋯   π ( a m ∣ s n ) ) \pi(a \mid s) = \begin{pmatrix} \pi(a_1 \mid s_1) & \pi(a_1 \mid s_2) & \cdots & \pi(a_1 \mid s_n) \\ \pi(a_2 \mid s_1) & \pi(a_2 \mid s_2) & \cdots & \pi(a_2 \mid s_n) \\ \vdots & \vdots & \ddots & \vdots \\ \pi(a_m \mid s_1) & \pi(a_m \mid s_2) & \cdots\ & \pi(a_m \mid s_n) \\ \end{pmatrix} π(a∣s)=⎝⎜⎜⎜⎛​π(a1​∣s1​)π(a2​∣s1​)⋮π(am​∣s1​)​π(a1​∣s2​)π(a2​∣s2​)⋮π(am​∣s2​)​⋯⋯⋱⋯ ​π(a1​∣sn​)π(a2​∣sn​)⋮π(am​∣sn​)​⎠⎟⎟⎟⎞​

SARSA算法的实现思路

初始化部分：

• Q ( s , a ) Q(s,a) Q(s,a)：它包含状态集合 S \mathcal S S内的任意状态 s s s 和 每个状态 s s s条件下有意义的任意动作 a a a 组成 状态-动作二元组，每个二元组都有对应的状态-动作价值函数 q ( s , a ) q(s,a) q(s,a)，最终将所有的 q ( s , a ) q(s,a) q(s,a)收集起来，构成 Q ( s , a ) Q(s,a) Q(s,a)。 Q ( s , a ) Q(s,a) Q(s,a)可以理解成一个集合，也可以理解成一个矩阵。也称作 Q − T a b l e Q-Table Q−Table； 实际上，也可以将'状态集合'中的任意状态和'动作集合'中的任意动作进行组合，即便这种组合方式可能会存在‘某些二元组’没有意义。 例如打篮球，‘防守状态’和‘投球’这个状态-动作二元组就没有意义，既然是防守状态，手上是没有球的;投球必然手上是有球的，手上有球那还能叫防守状态吗~ 为什么说我们的Q-Table中即便存在这种二元组，也不影响更新呢 -> 因为由于这种二元组是不可能发生的，因此这种二元组的价值函数Q(s,a)也不可能更新，即一直是'初始化状态'。 常见的 Q − T a b l e Q-Table Q−Table初始化：0或者任意实数 R \mathbb R R，
• π ( a ∣ s ) \pi(a \mid s) π(a∣s)：在策略评估过程执行动作 a a a的选择时，一定要保证该策略是 软性策略；通常做法是对 初始化的 Q ( s , a ) Q(s,a) Q(s,a)进行策略改进，再通过 ϵ \epsilon ϵ-贪心策略将策略改进结果优化为软性策略。

策略评估部分：

• 在 t t t时刻 s = S t s = S_t s=St​状态下，根据软性策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)从动作集合 A ( S t ) \mathcal A(S_t) A(St​)中以非零概率选择一个动作 A t A_t At​；
• 执行 A t A_t At​动作，系统自动将状态 S t S_t St​转移至 S t + 1 S_{t+1} St+1​状态，并得到奖励 R t + 1 R_{t+1} Rt+1​；
• 在 t + 1 t+1 t+1时刻 s = S t + 1 s = S_{t+1} s=St+1​状态下，再次使用软性策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)从动作集合 A ( S t + 1 ) \mathcal A(S_{t+1}) A(St+1​)中以非零概率选择一个动作 A t + 1 A_{t+1} At+1​；
• (核心步骤) 此时得到 A t + 1 A_{t+1} At+1​后，我们不执行该动作(即不获取后续转移状态 S t + 2 S_{t+2} St+2​和奖励 R t + 2 R_{t+2} Rt+2​)，而是直接计算状态-动作价值函数 Q ( S t + 1 ， A t + 1 ) Q(S_{t+1}，A_{t+1}) Q(St+1​，At+1​)；
• 在得到 R t + 1 , Q ( S t + 1 ， A t + 1 ) R_{t+1},Q(S_{t+1}，A_{t+1}) Rt+1​,Q(St+1​，At+1​)后，使用增量更新方法对 Q ( S t ， A t ) Q(S_{t}，A_{t}) Q(St​，At​)进行更新； Q ( S t , A t ) ← Q ( S t , A t ) + α ( R t + 1 + γ Q ( S t + 1 , A t + 1 ) − Q ( S t , A t ) ) Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)) Q(St​,At​)←Q(St​,At​)+α(Rt+1​+γQ(St+1​,At+1​)−Q(St​,At​)) 至此，策略评估部分结束，我们得到了该迭代步骤下更新后的 Q ( S t , A t ) Q(S_t,A_t) Q(St​,At​)；

策略改进部分：

• 使用贪心方法选择状态-动作价值函数 Q ( S t , A t ) Q(S_t,A_t) Q(St​,At​)最大结果对应的动作 A ′ A' A′： A ′ = arg ⁡ max ⁡ a Q ( S t , A t )    ⟺    Q ( S t , A ′ ) = m a x Q ( S t , A t ) A'= \underset {a}{\arg\max}Q(S_t,A_t)\iff Q(S_t,A')=maxQ(S_t,A_t) A′=aargmax​Q(St​,At​)⟺Q(St​,A′)=maxQ(St​,At​) 此时的策略结果为如下格式： π ( a ∣ s ) = { 1 a = A ′ 0 a ≠ A ′ \begin{aligned} \pi(a\mid s) = \left\{ \begin{array}{ll} 1\quad a = A' \\ 0\quad a \neq A' \\ \end{array} \right. \end{aligned} π(a∣s)={1a=A′0a​=A′​​ 这很明显是一个确定性策略(马尔可夫奖励过程中介绍过，传送门)，但 下一次迭代 我们还需要使用该策略去执行策略评估，因此我们需要将该策略由 确定性策略 → \to → 软性策略。
• 这里我们仍然使用 ϵ \epsilon ϵ-贪心策略对策略改进结果进行优化： π ′ ( a ∣ s ) = { 1 − ϵ + ϵ ∣ A ( s ) ∣ a = A ′ ϵ ∣ A ( s ) ∣ a ≠ A ′ \begin{aligned} \pi'(a\mid s) = \left\{ \begin{array}{ll} 1 - \epsilon + \frac{\epsilon}{\mid \mathcal A(s)\mid}\quad a = A' \\ \frac{\epsilon}{\mid \mathcal A(s)\mid} \quad\quad\quad\quad a \neq A' \end{array} \right. \end{aligned} π′(a∣s)={1−ϵ+∣A(s)∣ϵ​a=A′∣A(s)∣ϵ​a​=A′​​

当前步骤( S t → S t + 1 S_t \to S_{t+1} St​→St+1​)结束， s = S t + 1 s = S_{t+1} s=St+1​，继续执行步骤( S t + 1 → S t + 2 S_{t+1} \to S_{t+2} St+1​→St+2​)…直到 s s s达到当前情节的终结状态 S T S_T ST​结束。 这只是一次情节遍历结束，我们也可以多遍历几次情节，只要在最外层套一个for循环即可。

下一节将介绍Q-learning方法——基于离轨策略的时序差分控制。

相关参考： 【强化学习】(SARSA) 时序差分-同轨策略TD控制 深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著