蒙特卡洛方法求解强化学习任务——非试探性出发假设之同轨策略

目录

上一节针对试探性出发假设的缺陷，介绍了基于非试探性出发假设的蒙特卡洛控制方法。该方法以试探所有可能发生的状态-动作二元组为目标，将迭代过程中的策略划分为行动策略(behaviour policy)和目标策略(target policy)。本节将介绍基于这两种策略的蒙特卡洛控制算法——同轨策略(on-policy)

回顾：行动策略与目标策略

上一节提到，我们将将蒙特卡洛控制算法迭代过程中的策略划分为：

• 行动策略(behaviour policy)：用于构建情节时使用的策略，表示为 b ( a ∣ s ) b(a \mid s) b(a∣s)。例如某一个情节： S 0 , A 0 , R 1 , S 1 , A 1 , R 2 , . . . , S T − 1 , A T − 1 , R T , S T S_0,A_0,R_1,S_1,A_1,R_2,...,S_{T-1},A_{T-1},R_T,S_T S0​,A0​,R1​,S1​,A1​,R2​,...,ST−1​,AT−1​,RT​,ST​ 根据贝尔曼期望方程(Bellman Expectation Equation)的逻辑，情节中每一步动作(Action)的生成都需要策略的支撑，并且每一步的回报(Return)都是一个样本；
• 目标策略(target policy)：在策略改进过程中，我们使用贪心方法对创造最优状态-动作价值函数对应的动作进行选择，并构建成一个策略(本质上该策略针对每一个状态都是确定性策略)，表示为 π ( a ∣ s ) \pi(a \mid s) π(a∣s)。 π k ( a ∣ s ) = { 1 i f a ′ = arg ⁡ max ⁡ a q k − 1 ( s , a ) 0 o t h e r w i s e \begin{aligned} \pi_k(a\mid s) = \left\{ \begin{array}{ll} 1\quad if \quad a'= \mathop{\arg\max}\limits_{a}q_{k-1}(s,a)\\ 0\quad otherwise \end{array} \right. \end{aligned} πk​(a∣s)={1ifa′=aargmax​qk−1​(s,a)0otherwise​​

并且 b ( a ∣ s ) b(a \mid s) b(a∣s)必须是一个软性策略——在状态固定的条件下，对于该状态有意义的所有动作在该状态下 被选择的概率 > 0 > 0 >0恒成立。只有满足这个条件，才能达到试探所有可能动作的目的。

基于同轨策略的蒙特卡洛控制

同轨策略方法顾名思义：

• 在蒙特卡洛控制过程中，行动策略和目标策略相同；
• 均为软性策略；

其本质上整个控制过程只有一个策略，并要求这个策略是软性策略。目标已经明确，就是对当前迭代中的策略(策略改进后的策略)进行设计，使其成为软性策略即可。 为什么是对策略改进后的策略进行修正 -> 因为在生成情节和策略评估过程中，只是对策略进行使用，没有对策略进行更新。

回顾中提到，策略改进后的策略就是个确定性策略，如何将他设计为软性策略呢？这里介绍一种常用的设计方法—— ϵ \epsilon ϵ-贪心策略。

ϵ \epsilon ϵ-贪心策略 的基本思想是：仍然以较大概率去选择最优动作(确定性策略结果)，剩余概率平均分配给所有动作(包含最优动作自身)。其公式表示如下：

• 设 A ( s ) \mathcal A(s) A(s)为 s s s状态下有意义的动作集合， ϵ \epsilon ϵ表示一个较小的实数；
• 给定当前策略 π ( a ∣ s ) \pi(a\mid s) π(a∣s)和对应策略的状态-动作价值函数 q π ( s , a ) q_\pi(s,a) qπ​(s,a);

π ′ ( a ∣ s ) = { 1 − ϵ + ϵ ∣ A ( s ) ∣ i f a = arg ⁡ max ⁡ a q π ( s , a ) ϵ ∣ A ( s ) ∣ o t h e r w i s e \begin{aligned} \pi'(a\mid s) = \left\{ \begin{array}{ll} 1 - \epsilon + \frac{\epsilon}{\mid \mathcal A(s)\mid}\quad if \quad a = \mathop{\arg\max}\limits_{a}q_\pi(s,a)\\ \frac{\epsilon}{\mid \mathcal A(s)\mid} \quad\quad\quad\quad otherwise \end{array} \right. \end{aligned} π′(a∣s)={1−ϵ+∣A(s)∣ϵ​ifa=aargmax​qπ​(s,a)∣A(s)∣ϵ​otherwise​​

示例如下： 假设当前时刻状态 S t = s 1 S_t = s_1 St​=s1​，在 s 1 s_1 s1​状态下具有意义的动作集合 A ( s 1 ) \mathcal A(s_1) A(s1​)中包含3个动作 a 1 , a 2 , a 3 a_1,a_2,a_3 a1​,a2​,a3​： A ( s 1 ) = { a 1 , a 2 , a 3 } \mathcal A(s_1) = \{a_1,a_2,a_3\} A(s1​)={a1​,a2​,a3​} 针对3种动作的状态-动作价值函数如下：

S \mathcal S S A ( s 1 ) \mathcal A(s_1) A(s1​) q π ( S , A ( s 1 ) ) q_\pi(\mathcal S,\mathcal A(s_1)) qπ​(S,A(s1​))确定性策略 π ( a ∈ A ( s 1 ) ∣ S ) \pi(a \in \mathcal A(s_1) \mid \mathcal S) π(a∈A(s1​)∣S)软性策略 π ′ ( a ∈ A ( s 1 ) ∣ S ) \pi'(a \in \mathcal A(s_1) \mid \mathcal S) π′(a∈A(s1​)∣S) s 1 s_1 s1​ a 1 a_1 a1​12.9810.97 + 0.01 s 1 s_1 s1​ a 2 a_2 a2​11.8700.01 s 1 s_1 s1​ a 3 a_3 a3​10.5200.01

从策略迭代的角度观察，我们依然希望较大概率选择动作 a 1 a_1 a1​(因为 a 1 a_1 a1​的状态-动作价值函数最高)，假设以0.97的概率选择 a 1 a_1 a1​,将剩余的0.03平均分配给所有动作(这里的0.03就是 ϵ \epsilon ϵ)。 0.03 ∣ A ( s 1 ) ∣ = 0.03 3 = 0.01 \frac{0.03}{\mid\mathcal A(s_1)\mid} = \frac{0.03}{3} = 0.01 ∣A(s1​)∣0.03​=30.03​=0.01 至此，我们将策略改进后的确定性策略设计为软性策略。 七成？七成是人家的！...哈哈

软性策略符合策略改进定理证明

即便已经设计为软性策略，但实质上仍旧依据的是贪心策略(确定性策略)。在蒙特卡洛方法求解强化学习任务——基于试探性出发假设的蒙特卡洛控制一节中，我们已经验证了贪心策略(策略改进产生的新策略) 满足 蒙特卡洛控制方法中策略收敛的合理性 → π u p d a t e ≥ π n o w \to \pi_{update} \geq \pi_{now} →πupdate​≥πnow​ 。 那么软性策略是否满足策略收敛的合理性呢？

证明思路：

• 更新后的软性策略用 π ′ ( a ∣ s ) \pi'(a \mid s) π′(a∣s)表示： π ′ ( a ∣ s ) = { 1 − ϵ + ϵ ∣ A ( s ) ∣ i f a = arg ⁡ max ⁡ a q π ( s , a ) ϵ ∣ A ( s ) ∣ o t h e r w i s e \begin{aligned} \pi'(a\mid s) = \left\{ \begin{array}{ll} 1 - \epsilon + \frac{\epsilon}{\mid \mathcal A(s)\mid}\quad if \quad a = \mathop{\arg\max}\limits_{a}q_\pi(s,a)\\ \frac{\epsilon}{\mid \mathcal A(s)\mid} \quad\quad\quad\quad otherwise \end{array} \right. \end{aligned} π′(a∣s)={1−ϵ+∣A(s)∣ϵ​ifa=aargmax​qπ​(s,a)∣A(s)∣ϵ​otherwise​​
• 证明软性策略条件下的状态-动作价值函数 q π [ s , a π ′ ( a ∣ s ) ] ≥ q_\pi[s,a\pi'(a \mid s)] \geq qπ​[s,aπ′(a∣s)]≥当前状态的状态价值函数 V π ( s ) V_\pi(s) Vπ​(s)；
• 基于上一步条件，根据策略改进定理，直接证明： V π ′ ( a ∣ s ) ( s ) ≥ V π ( s ) V_{\pi'(a \mid s)}(s) \geq V_\pi(s) Vπ′(a∣s)​(s)≥Vπ​(s) 即 π ′ ( a ∣ s ) ≥ π \pi'(a \mid s) \geq \pi π′(a∣s)≥π。

具体证明如下：

• 将 q π [ s , π ′ ( a ∣ s ) ] q_\pi[s,\pi'(a \mid s)] qπ​[s,π′(a∣s)]展开成概率权重加和的形式： q π [ s , π ′ ( a ∣ s ) ] = ∑ a ∈ A ( s ) π ′ ( a ∣ s ) q π ( s , a ) q_\pi[s,\pi'(a \mid s)] = \sum_{a \in \mathcal A(s)}\pi'(a \mid s)q_\pi(s,a) qπ​[s,π′(a∣s)]=a∈A(s)∑​π′(a∣s)qπ​(s,a) 需要注意的部分(为什么可以转换成上述形式)： q π [ s , π ′ ( a ∣ s ) ] q_\pi[s,\pi'(a \mid s)] qπ​[s,π′(a∣s)]和动态规划求解强化学习任务——使用策略改进定理迭代求解策略π里面迭代求解过程中的 q π ( s , π ′ ( s ) ) q_\pi(s,\pi'(s)) qπ​(s,π′(s))非常相似，但 π ′ ( s ) \pi'(s) π′(s)是贪心策略下的最优策略，是确定性策略；它的展开式只有1项： q π ( s , π ′ ( s ) ) = max ⁡ a q π ( s , a ) q_\pi(s,\pi'(s)) = \mathop{\max}\limits_{a}q_{\pi}(s,a) qπ​(s,π′(s))=amax​qπ​(s,a) 但 π ′ ( a ∣ s ) \pi'(a \mid s) π′(a∣s)是软性策略，每个动作都有各自的概率分布结果，共 ∣ A ( s ) ∣ | \mathcal A(s)| ∣A(s)∣项。所以才能分解成上述形式。
• 将上述结果拆成2份： 最优动作对应概率较大的部分 → ( 1 − ϵ ) \to (1 - \epsilon) →(1−ϵ)部分； 所有动作均分剩余概率的部分 → ϵ \to \epsilon →ϵ 部分； ∑ a ∈ A ( s ) π ′ ( a ∣ s ) q π ( s , a ) = ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) q π ( s , a ) + ( 1 − ϵ ) max ⁡ a q π ( s , a ) \sum_{a \in \mathcal A(s)}\pi'(a \mid s)q_\pi(s,a) = \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)}q_\pi(s,a) + (1 - \epsilon) \mathop{\max}\limits_{a}q_\pi(s,a) a∈A(s)∑​π′(a∣s)qπ​(s,a)=∣A(s)∣ϵ​a∈A(s)∑​qπ​(s,a)+(1−ϵ)amax​qπ​(s,a)
• 主要关注 max ⁡ a q π ( s , a ) \mathop{\max}\limits_{a}q_\pi(s,a) amax​qπ​(s,a)，由于该结果是一个最大值结果，因此该值大于等于任意一个动作的状态-动作价值函数(这里提出一个1， a ∈ A ( s ) a \in \mathcal A(s) a∈A(s)省略)： max ⁡ a q π ( s , a ) ≥ q π ( s , a ) ( a ∈ A ( s ) ) ≥ 1 × q π ( s , a ) \begin{aligned} \mathop{\max}\limits_{a}q_\pi(s,a) & \geq q_\pi(s,a)(a \in \mathcal A(s)) \\ & \geq 1 \times q_\pi(s,a) \end{aligned} amax​qπ​(s,a)​≥qπ​(s,a)(a∈A(s))≥1×qπ​(s,a)​ 这里技巧性很强，需要大家注意一下，顺便体验一下'数学之美'。 这里对 系数 1做一些文章： 我们希望 系数 1通过变换能够具有以下功能：

1. 将 max ⁡ a q π ( s , a ) \mathop{\max}\limits_{a}q_\pi(s,a) amax​qπ​(s,a)的系数 ( 1 − ϵ ) (1 - \epsilon) (1−ϵ)消掉；
2. 变换出如下形状的格式； ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)} ∣A(s)∣ϵ​a∈A(s)∑​ 目的是与原式中第1项消去； ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) q π ( s , a ) \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)}q_\pi(s,a) ∣A(s)∣ϵ​a∈A(s)∑​qπ​(s,a) 带着上述思路，对 系数 1进行变换： 1 = 1 − ϵ 1 − ϵ = ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ 1 − ϵ \begin{aligned} 1 & = \frac{1 - \epsilon}{1 - \epsilon} \\ & = \frac{\sum_{a \in \mathcal A(s)}\pi(a \mid s) - \epsilon}{1 - \epsilon} \\ \end{aligned} 1​=1−ϵ1−ϵ​=1−ϵ∑a∈A(s)​π(a∣s)−ϵ​​ 讲解1： π ( a ∣ s ) \pi(a \mid s) π(a∣s)本质上是 s s s状态作为条件下，动作 a a a的概率分布。 ∑ a ∈ A ( s ) π ( a ∣ s ) \sum_{a \in \mathcal A(s)}\pi(a \mid s) ∑a∈A(s)​π(a∣s)表示动作 a a a在离散状态下对概率分布 π ( a ∣ s ) \pi(a \mid s) π(a∣s)求积分。积分结果必然为1。 (详见动态规划求解强化学习任务——策略评估[解析解]中条件概率密度积分) 讲解2： 将分子右侧的 ϵ \epsilon ϵ提出一个 ∣ A ( s ) ∣ |\mathcal A(s)| ∣A(s)∣；(目的是凑 ϵ ∣ A ( s ) ∣ \frac{\epsilon}{|\mathcal A(s)|} ∣A(s)∣ϵ​) ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ 1 − ϵ = ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ ∣ A ( s ) ∣ × ∣ A ( s ) ∣ 1 − ϵ \begin{aligned} \frac{\sum_{a \in \mathcal A(s)}\pi(a \mid s) - \epsilon}{1 - \epsilon} = \frac{\sum_{a \in \mathcal A(s)}\pi(a \mid s) - \frac{\epsilon}{|\mathcal A(s)|}\times |\mathcal A(s)| }{1 - \epsilon} \end{aligned} 1−ϵ∑a∈A(s)​π(a∣s)−ϵ​=1−ϵ∑a∈A(s)​π(a∣s)−∣A(s)∣ϵ​×∣A(s)∣​​ 继续探索， ∣ A ( s ) ∣ |\mathcal A(s)| ∣A(s)∣表示 s s s状态下有意义的动作集合的大小(集合内有效动作 a a a的数量)，是常数；并且该值等于 ∑ a ∈ A ( s ) \sum_{a \in \mathcal A(s)} ∑a∈A(s)​中累加的次数。即： ϵ ∣ A ( s ) ∣ × ∣ A ( s ) ∣ = ϵ ∣ A ( s ) ∣ + ϵ ∣ A ( s ) ∣ + . . . + ϵ ∣ A ( s ) ∣ ⏟ ∣ A ( s ) ∣ 个 = ∑ a ∈ A ( s ) ϵ ∣ A ( s ) ∣ \frac{\epsilon}{|\mathcal A(s)|}\times |\mathcal A(s)| = \underbrace{\frac{\epsilon}{|\mathcal A(s)|} + \frac{\epsilon}{|\mathcal A(s)|} + ... + \frac{\epsilon}{|\mathcal A(s)|}}_{|\mathcal A(s)|个} = \sum_{a \in \mathcal A(s)} \frac{\epsilon}{|\mathcal A(s)|} ∣A(s)∣ϵ​×∣A(s)∣=∣A(s)∣个 ∣A(s)∣ϵ​+∣A(s)∣ϵ​+...+∣A(s)∣ϵ​​​=a∈A(s)∑​∣A(s)∣ϵ​ 于此同时，由于分母 1 − ϵ 1 - \epsilon 1−ϵ也是常数，它不影响累加符号 ∑ a ∈ A ( s ) \sum_{a \in \mathcal A(s)} ∑a∈A(s)​操作，因此将分母也放到 ∑ a ∈ A ( s ) \sum_{a \in \mathcal A(s)} ∑a∈A(s)​内部： ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ 1 − ϵ = ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ ∣ A ( s ) ∣ × ∣ A ( s ) ∣ 1 − ϵ = ∑ a ∈ A ( s ) π ( a ∣ s ) − ∑ a ∈ A ( s ) ϵ ∣ A ( s ) ∣ 1 − ϵ = ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ ∣ A ( s ) ∣ 1 − ϵ \begin{aligned} \frac{\sum_{a \in \mathcal A(s)}\pi(a \mid s) - \epsilon}{1 - \epsilon} & = \frac{\sum_{a \in \mathcal A(s)}\pi(a \mid s) - \frac{\epsilon}{|\mathcal A(s)|}\times |\mathcal A(s)| }{1 - \epsilon} \\ & = \frac{\sum_{a \in \mathcal A(s)}\pi(a \mid s) - \sum_{a \in \mathcal A(s)}\frac{\epsilon}{|\mathcal A(s)|}}{1 - \epsilon} \\ & = \sum_{a \in \mathcal A(s)}\frac{\pi(a \mid s) -\frac{\epsilon}{|\mathcal A(s)|}}{1 - \epsilon} \end{aligned} 1−ϵ∑a∈A(s)​π(a∣s)−ϵ​​=1−ϵ∑a∈A(s)​π(a∣s)−∣A(s)∣ϵ​×∣A(s)∣​=1−ϵ∑a∈A(s)​π(a∣s)−∑a∈A(s)​∣A(s)∣ϵ​​=a∈A(s)∑​1−ϵπ(a∣s)−∣A(s)∣ϵ​​​ 整理一下，可以得到： 1 = ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ ∣ A ( s ) ∣ 1 − ϵ 1 = \sum_{a \in \mathcal A(s)}\frac{\pi(a \mid s) -\frac{\epsilon}{|\mathcal A(s)|}}{1 - \epsilon} 1=a∈A(s)∑​1−ϵπ(a∣s)−∣A(s)∣ϵ​​

• 将转换后的 max ⁡ a q π ( s , a ) ≥ 1 × q π ( s , a ) \mathop{\max}\limits_{a}q_\pi(s,a) \geq1 \times q_\pi(s,a) amax​qπ​(s,a)≥1×qπ​(s,a)带回到原式中： q π [ s , π ′ ( a ∣ s ) ] = ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) q π ( s , a ) + ( 1 − ϵ ) max ⁡ a q π ( s , a ) ≥ ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) q π ( s , a ) + ( 1 − ϵ ) ∑ a ∈ A ( s ) π ( a ∣ s ) − ϵ ∣ A ( s ) ∣ 1 − ϵ q π ( s , a ) \begin{aligned} q_\pi[s,\pi'(a \mid s)] & = \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)}q_\pi(s,a) + (1 - \epsilon) \mathop{\max}\limits_{a}q_\pi(s,a) \\ & \geq \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)}q_\pi(s,a) + (1 - \epsilon) \sum_{a \in \mathcal A(s)}\frac{\pi(a \mid s) -\frac{\epsilon}{|\mathcal A(s)|}}{1 - \epsilon}q_\pi(s,a) \end{aligned} qπ​[s,π′(a∣s)]​=∣A(s)∣ϵ​a∈A(s)∑​qπ​(s,a)+(1−ϵ)amax​qπ​(s,a)≥∣A(s)∣ϵ​a∈A(s)∑​qπ​(s,a)+(1−ϵ)a∈A(s)∑​1−ϵπ(a∣s)−∣A(s)∣ϵ​​qπ​(s,a)​ 将上式右侧展开( 1 − ϵ 1 - \epsilon 1−ϵ消去)： = ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) q π ( s , a ) − ϵ ∣ A ( s ) ∣ ∑ a ∈ A ( s ) q π ( s , a ) + ∑ a ∈ A ( s ) π ( a ∣ s ) q π ( s , a ) = \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)}q_\pi(s,a) - \frac{\epsilon}{|\mathcal A(s)|}\sum_{a \in \mathcal A(s)}q_\pi(s,a) + \sum_{a \in \mathcal A(s)}\pi(a\mid s)q_\pi(s,a) =∣A(s)∣ϵ​a∈A(s)∑​qπ​(s,a)−∣A(s)∣ϵ​a∈A(s)∑​qπ​(s,a)+a∈A(s)∑​π(a∣s)qπ​(s,a) 第1项和第2项消掉，最后只剩下： ∑ a ∈ A ( s ) π ( a ∣ s ) q π ( s , a ) = V π ( s ) \sum_{a \in \mathcal A(s)}\pi(a\mid s)q_\pi(s,a) = V_\pi(s) a∈A(s)∑​π(a∣s)qπ​(s,a)=Vπ​(s) 整理可得： q π [ s , π ′ ( a ∣ s ) ] ≥ V π ( s ) q_\pi[s,\pi'(a \mid s)] \geq V_\pi(s) qπ​[s,π′(a∣s)]≥Vπ​(s) 根据策略改进定理，可得： V π ′ ( a ∣ s ) ( s ) ≥ V π ( s ) ⇒ π ′ ( a ∣ s ) ≥ π V_{\pi'(a \mid s)}(s) \geq V_\pi(s) \Rightarrow \pi'(a \mid s) \geq \pi Vπ′(a∣s)​(s)≥Vπ​(s)⇒π′(a∣s)≥π

该证明保证了经过 ϵ \epsilon ϵ-贪心算法处理后的软性策略 π ′ ( a ∣ s ) \pi'(a \mid s) π′(a∣s)可以收敛到最优状态-动作价值函数 q ∗ ( s , a ) q_*(s,a) q∗​(s,a)和最优策略 π ∗ \pi_* π∗​。

同轨策略蒙特卡洛控制的算法实现

基于同轨策略的首次访问型(first-visit)， ϵ \epsilon ϵ-贪心策略的蒙特卡洛控制算法如下：

输入待评估的 ϵ \epsilon ϵ-贪心策略： π ( a ∣ s ) \pi(a \mid s) π(a∣s)初始化操作(Initialization operation)1. 对 ∀ s ∈ S , a ∈ A ( s ) \forall s \in \mathcal S,a \in \mathcal A(s) ∀s∈S,a∈A(s),初始化 Q ( s , a ) ∈ R Q(s,a) \in\mathbb R Q(s,a)∈R； 2.对 ∀ s ∈ S , a ∈ A ( s ) \forall s \in \mathcal S,a \in \mathcal A(s) ∀s∈S,a∈A(s),状态、动作二元组 ( s , a ) (s,a) (s,a)被统计次数 c o u n t ( s , a ) = 0 count(s,a) = 0 count(s,a)=0；3. ϵ ← ( 0 , 1 ) \epsilon \gets (0,1) ϵ←(0,1)为一个逐步递减的较小实数；算法过程(Algorithmic Process)4. repeat 对每一个情节： k = 0 , 1 , 2 , . . . k=0,1,2,... k=0,1,2,...5.   根据策略 π ( s ) \pi(s) π(s),从初始二元组( S 0 , A 0 S_0,A_0 S0​,A0​)开始，生成一个情节序列：      S 0 , A 0 , R 1 , S 1 , A 1 , R 2 , . . . , S T − 1 , A T − 1 , R T , S T S_0,A_0,R_1,S_1,A_1,R_2,...,S_{T-1},A_{T-1},R_T,S_T S0​,A0​,R1​,S1​,A1​,R2​,...,ST−1​,AT−1​,RT​,ST​6.   G ← 0 G \gets 0 G←0 7.    for 情节中的每一步(时刻) t = T − 1 → 0 t = T - 1 \to 0 t=T−1→0 do： 8.        G ← γ G + R t + 1 G \gets\gamma G + R_{t+1} G←γG+Rt+1​ 9.        if  ( S t , A t ) ∉ { S 0 , A 0 , S 1 , . . . , S t − 1 , A t − 1 } (S_t,A_t) \notin \{S_0,A_0,S_1,...,S_{t-1},A_{t-1}\} (St​,At​)∈/​{S0​,A0​,S1​,...,St−1​,At−1​} then 10.           c o u n t ( S t , A t ) ← c o u n t ( S t , A t ) + 1 count(S_t,A_t) \gets count(S_t,A_t) + 1 count(St​,At​)←count(St​,At​)+1 11.           Q ( S t , A t ) ← Q ( S t , A t ) + 1 c o u n t ( S t , A t ) ( G − Q ( S t , A t ) ) Q(S_t,A_t) \gets Q(S_t,A_t) + \frac{1}{count(S_t,A_t)}(G - Q(S_t,A_t)) Q(St​,At​)←Q(St​,At​)+count(St​,At​)1​(G−Q(St​,At​))12.           A ∗ ← arg ⁡ max ⁡ a Q ( S t , a ) A^* \gets \mathop{\arg\max}\limits_{a}Q(S_t,a) A∗←aargmax​Q(St​,a)13.          for  a ∈ A ( s ) a \in \mathcal A(s) a∈A(s) do14.              if a = = A ∗ a == A^* a==A∗ then15.                   π ( a ∣ S t ) ← 1 − ϵ + ϵ ∣ A ( s ) ∣ \pi(a\mid S_t) \gets 1 - \epsilon + \frac{\epsilon}{\mid\mathcal A(s)\mid} π(a∣St​)←1−ϵ+∣A(s)∣ϵ​16.              else17.                   π ( a ∣ S t ) ← ϵ ∣ A ( s ) ∣ \pi(a\mid S_t) \gets \frac{\epsilon}{\mid\mathcal A(s)\mid} π(a∣St​)←∣A(s)∣ϵ​18.              end if19.         end for20.      end if21.   end for输出结果 q ∗ = Q q_* = Q q∗​=Q， π ∗ = π \pi_* = \pi π∗​=π

我们观察过程可以看出，该算法和基于试探性出发假设的蒙特卡洛控制算法基本相同(忘记的小伙伴回去看一眼，传送门)，只是在每次策略改进结束后，将改进后的确定性策略设计成软性策略即可。

本节主要讲述了同轨策略方法的逻辑推导和算法过程，下一节将介绍离轨策略的相关知识。

相关参考： 【强化学习】蒙特卡洛方法-同轨VS离轨 【强化学习】 蒙特卡洛方法-同轨策略MC控制 深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著