蒙特卡洛树搜索方法介绍——算力聚焦方法(二) 反向聚焦(优先级遍历)

引言

上一节针对 D y n a − Q Dyna-Q Dyna−Q算法执行过程中的问题，介绍了算力聚焦思想以及 D y n a − Q + Dyna-Q+ Dyna−Q+算法思路。本节将继续介绍基于算力聚焦思想的另一种算法——优先级遍历算法。

回顾：算力聚焦思想 算力聚焦的自身矛盾

算力聚焦的矛盾问题本质上是探索(Exploration)与利用(Exploitation)的矛盾问题：

• 利用：在状态-动作对的选择过程中，使用算力聚焦思想提高 区分性，从而提高算力对 Q − t a b l e Q-table Q−table的更新效率；
• 探索：真实环境中可能存在某状态-动作对被选择概率很低，但这种状态-动作对也可能存在重要的信息，希望对各状态-动作对都能兼顾；

Dyna-Q+方法处理矛盾的思路

D y n a − Q + Dyna-Q+ Dyna−Q+方法主要通过探索自身定义出发构建假设：针对很久没有被访问过的状态-动作对，使用增加对应状态的奖励结果来增加该状态的状态转移频率。具体做法是构建一个关于奖励增量与未被访问的时间间隔之间的函数： R ← R + κ τ R \gets R + \kappa \sqrt{\tau} R←R+κτ ​

具体思路：

• 一旦增加了奖励结果 R R R，必然影响对应的状态-动作价值函数 Q ( s , a ) Q(s,a) Q(s,a)；
• 根据策略改进中关于动作的贪心算法， Q ( s , a ) Q(s,a) Q(s,a)会影响动作的选择；
• 从增加状态转移至想要被访问状态的频率；
• 虽然动态特性函数 P ( s ′ , r ∣ s , a ) P(s',r \mid s,a) P(s′,r∣s,a)无法变化(真实环境因素影响)，但由于状态转移的频率增加，转移至 想要被访问状态 的 机会 明显增大。

其本质上是针对 D y n a − Q Dyna-Q Dyna−Q算法中探索(Exploration)部分处理不足产生的想法。

反向聚焦(优先级遍历算法) 思路构建

由于 D y n a − Q Dyna-Q Dyna−Q算法对状态-动作对的 纯随机选择 导致算力资源浪费的情况，介绍反向聚焦的核心思想：

• 在状态-动作对的选择过程中，给予它们 分别性。

具体想法是：如果将 D y n a − Q Dyna-Q Dyna−Q规划过程中的模拟经验与 Q − T a b l e Q-Table Q−Table的更新 集中在某些特定的状态-动作对上，这样规划过程会更加高效。

现在的问题已经转化为：如何挑选规划过程更加高效的状态-动作对，或者说如何定义某种状态-动作对，使规划过程更加高效。

基于上述问题，思考：强化学习求解的任务无非就是希望智能体能够状态转移至终结状态，即情节结束。 基于该思考，提出一个极端假设：

• 如果事先知道终结状态的信息，可以从终结状态开始寻找它的前继状态，得到前继状态，再继续寻找前继状态的前继状态，以此类推，直至当前状态。此时就知道下一次状态转移更希望选择哪个状态，从而调整当前策略对动作的选择，从而给 状态转移创造机会。 但并不是所有的问题都像‘迷宫问题’一样能够找到‘终结状态信息(迷宫出口)’。

上述假设之所以极端，是因为在真实情况下，我们可能无法找到 终结状态 的信息。因此，基于上述假设，可以提出一个 更一般的假设(反向聚焦)(Backward Focusing)：

• 相比于极端假设，我们不需要 只关注最优状态(终结状态)，只需要关注 优秀的状态-动作对 即可，或者说，定义一个规则：通过规则来判断哪些状态-动作对是优秀的，哪些不是优秀的即可。 好的状态-动作对的‘评判标准’是什么——自然是状态-动作价值函数Q(s,a)。

• 假设已经知道某一状态-动作对的 Q ( s , a ) Q(s,a) Q(s,a)是好的——此时已经得到一个不错的状态 s s s；以 s s s为目标，观察 哪些状态通过状态转移有机会转移至 s s s，这些状态被列为 重点观察对象，这些状态同样可以通过 Q ( s , a ) Q(s,a) Q(s,a)放入优先级队列中，排在最前面的自然是 转移至 s s s后收益最大的状态，以此类推。

该方法与 D y n a − Q + Dyna-Q+ Dyna−Q+方法相对应，其本质上是针对 D y n a − Q Dyna-Q Dyna−Q算法中利用(Exploitation)部分处理不足产生的想法。

反向聚焦算法执行过程

观察反向聚焦算法的执行过程： 输入部分(Input)：

• 折扣系数： γ \gamma γ；
• 超参数： θ \theta θ，用于处理优先级队列的排序问题；
• ϵ ∈ ( 0 , 1 ) \epsilon \in (0,1) ϵ∈(0,1)：用于构建 ϵ − \epsilon- ϵ−贪心策略；
• n n n：正整数，用于规划过程的遍历次数；

初始化部分(Initialization)：

• s ∈ S , a ∈ A ( s ) s \in \mathcal S,a \in \mathcal A(s) s∈S,a∈A(s)；
• Q − T a b l e → Q ( s , a ) ∈ R Q-Table \to Q(s,a) \in \mathbb R Q−Table→Q(s,a)∈R；
• 模拟环境： M o d e l ( s , a ) ∈ R Model(s,a) \in \mathbb R Model(s,a)∈R；
• 队列 P Q u e u e → N u l l PQueue \to Null PQueue→Null；

算法部分 学习过程：

• 结合非终结状态 S t S_t St​和对应在 Q − T a b l e Q-Table Q−Table中的 Q ( s , a ) ( a ∈ A ( S t ) ) Q(s,a)(a \in \mathcal A(S_t)) Q(s,a)(a∈A(St​))，构建一个基于 ϵ − \epsilon- ϵ−贪心算法的策略 π ( S t ) \pi(S_t) π(St​)；
• 从策略 π \pi π中选择一个动作 A t A_t At​；
• 执行动作 A t A_t At​，经过状态转移得到下一时刻状态 S t + 1 , R t + 1 S_{t+1},R_{t+1} St+1​,Rt+1​；
• 将确定性环境 ( S t + 1 , R t + 1 ) (S_{t+1},R_{t+1}) (St+1​,Rt+1​)存储在模拟环境对应位置 M o d e l ( S t , A t ) Model(S_t,A_t) Model(St​,At​)中； M o d e l ( S t , A t ) ← S t + 1 , R t + 1 Model(S_t,A_t) \gets S_{t+1},R_{t+1} Model(St​,At​)←St+1​,Rt+1​

至此，上述产生真实经验(Real Experience)过程与模型学习(Model Learning)过程和 D y n a − Q Dyna-Q Dyna−Q没有区分；但是在 直接强化学习过程(Direct Reinforcement Learning)中存在明显差异：

• 计算状态转移后，真实样本 S t + 1 , R t + 1 S_{t+1},R_{t+1} St+1​,Rt+1​产生的 增量信息 P P P： P ← ∣ R t + 1 + γ max ⁡ a Q ( S t + 1 , a ) − Q ( S t , A t ) ∣ P \gets \left|R_{t+1} + \gamma \mathop{\max}\limits_{a} Q(S_{t+1},a) - Q(S_t,A_t)\right| P←∣ ∣​Rt+1​+γamax​Q(St+1​,a)−Q(St​,At​)∣ ∣​
• 判断 P P P与超参数 θ \theta θ之间的大小关系： 如果 P > θ P>\theta P>θ，将 ( S t , A t ) (S_t,A_t) (St​,At​)以优先级 P P P插入队列； i f P > θ : ( S t , A t ) → P P Q u e u e if \quad P >\theta:(S_t,A_t) \xrightarrow{P} PQueue ifP>θ:(St​,At​)P ​PQueue

至此，学习过程 结束。相比 D y n a − Q Dyna-Q Dyna−Q算法，它删除了直接强化学习过程，而是以增量信息 P P P为评价标准，将其插入对应队列位置中。 由于绝对值的原因，转移后的价值函数信息并不一定比转移之前的好，只是说明两者之间的差距较大。

规划过程：

• 根据学习过程中增量信息 P P P的排序，选择第一顺位的状态动作对 ( s , a ) (s,a) (s,a)： s , a ← f i r s t ( P Q u e u e ) s,a \gets first(PQueue) s,a←first(PQueue)
• 通过模拟环境得到下一时刻的状态转移结果 s ′ , r s',r s′,r; s ′ , r ← M o d e l ( s , a ) s',r \gets Model(s,a) s′,r←Model(s,a)
• 针对模拟样本 ( s , a , s ′ , r ) (s,a,s',r) (s,a,s′,r)对 Q − T a b l e Q-Table Q−Table进行更新： Q ( s , a ) ← Q ( s , a ) + α [ r + γ max ⁡ a Q ( s ′ , a ) − Q ( s , a ) ] Q(s,a) \gets Q(s,a) + \alpha \left[r + \gamma \mathop{\max}\limits_{a} Q(s',a) - Q(s,a)\right] Q(s,a)←Q(s,a)+α[r+γamax​Q(s′,a)−Q(s,a)]

该部分为产生模拟经验与间接强化学习过程。相比于 D y n a − Q Dyna-Q Dyna−Q算法，该部分最大区别是将真实经验与模拟经验一视同仁——只要不是 P Q u e u e PQueue PQueue中的第一顺位，就没有机会执行强化学习过程。

• 遍历所有可能通过状态转移得到状态 s s s的所有状态-动作对 ( s ^ , a ^ ) (\hat s,\hat a) (s^,a^)； 这里可能会产生若干对 ( s ^ , a ^ ) (\hat s,\hat a) (s^,a^); { ( s 1 ^ , a 1 ^ ) , ( s 2 ^ , a 2 ^ ) , ⋯   } \{(\hat {s_1},\hat {a_1}),(\hat {s_2},\hat {a_2}),\cdots\} {(s1​^​,a1​^​),(s2​^​,a2​^​),⋯}
• r ^ ← s ^ , a ^ \hat r \gets \hat s,\hat a r^←s^,a^转移至状态 s s s的预期奖赏； 注意：这个条件实际上是‘非常苛刻’的: 状态-动作对 ( s ^ , a ^ ) (\hat s,\hat a) (s^,a^)在状态转移过程中可能存在若干种‘下一时刻状态’(包含状态 s s s)，但这里只要转移至状态 s s s的奖赏。 即每一对 ( s ^ , a ^ ) (\hat s,\hat a) (s^,a^)均对应一个 r ^ \hat r r^; { r 1 ^ , r 2 ^ , ⋯   } \{\hat {r_1},\hat {r_2},\cdots\} {r1​^​,r2​^​,⋯}
• 将所有产生的模拟样本计算增量结果： { ( s 1 ^ , a 1 ^ , r 1 ^ , s ) , ( s 2 ^ , a 2 ^ , r 2 ^ , s ) , ⋯   } P i ← ∣ r i ^ + γ max ⁡ a Q ( s , a ) − Q ( s i ^ , a i ^ ) ∣ ( i = 1 , 2 , ⋯   ) { P 1 , P 2 , ⋯   } \{(\hat {s_1},\hat {a_1},\hat {r_1},s),(\hat {s_2},\hat {a_2},\hat {r_2},s),\cdots\} \\ P_i \gets \left|\hat {r_i} + \gamma \mathop{\max}\limits_{a} Q(s,a) - Q(\hat {s_i},\hat {a_i})\right|(i = 1,2,\cdots) \\ \{P_1,P_2,\cdots\} {(s1​^​,a1​^​,r1​^​,s),(s2​^​,a2​^​,r2​^​,s),⋯}Pi​←∣ ∣​ri​^​+γamax​Q(s,a)−Q(si​^​,ai​^​)∣ ∣​(i=1,2,⋯){P1​,P2​,⋯}
• 对上述增量结果 P i P_i Pi​进行筛选，如果 P i > θ → P_i > \theta \to Pi​>θ→ 将 P i P_i Pi​对应的( s i ^ , a i ^ \hat {s_i},\hat {a_i} si​^​,ai​^​)加入到 P Q u e u e PQueue PQueue队列中。 i f P i > θ : ( s i ^ , a i ^ ) → P i P Q u e u e if \quad P_i >\theta:(\hat {s_i},\hat {a_i}) \xrightarrow{P_i} PQueue ifPi​>θ:(si​^​,ai​^​)Pi​ ​PQueue

算法结束。最终可得到优化后的 Q − T a b l e Q-Table Q−Table。 总结优先遍历算法的特点：

• 删除了真实经验对 Q − T a b l e Q-Table Q−Table更新的 特权：只要不是 P Q u e u e PQueue PQueue队列的第一顺位，都没有机会对 Q − T a b l e Q-Table Q−Table进行更新；
• 每一次规划过程内部有产生了一个嵌套循环，这导致每一次规划过程都可能产生 若干个新的状态-动作对加入队列以及一个最优状态-动作对从队列中产生，这种操作会导致早期增量结果较高的状态-动作对被极大程度地发掘其“价值潜力”。

下一节将介绍决策时间规划。

相关参考： 【强化学习】规划与学习-算力聚焦 深度强化学习原理、算法与PyTorch实战——刘全、黄志刚编著