蒙特卡洛树搜索方法介绍——后台规划(background planning)与决策时规划(decision-time planning)

引言

上一节介绍了优先级遍历算法(反向聚焦)，本节将从规划执行时机的角度对算法进行解析。

后台规划 回顾：动态规划算法

在介绍后台规划之前，回顾一下动态规划算法的迭代过程： 动态规划算法如下表所示：

算法基于随机MDP的状态价值函数 V π ( s ) V_\pi(s) Vπ​(s)策略迭代算法输入(Input)初始策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)，动态特性函数 P P P，奖赏函数 r r r，折扣系数 γ \gamma γ初始化操作(Initialization operation)1. 对 ∀ s ∈ S \forall s \in \mathcal S ∀s∈S，初始化状态价值函数 V π ( s ) V_\pi(s) Vπ​(s)； 2. 阈值 θ \theta θ设置为一个较小的实数值；策略评估(Policy Evaluation)1. repeat 对每一轮策略评估 τ = 0 , 1 , 2 , ⋯ \tau=0,1,2,\cdots τ=0,1,2,⋯2.    d e l t a ← 0 delta \gets 0 delta←03.    for 每个状态 s s s do：4.        v ← V π ( s ) v \gets V_\pi(s) v←Vπ​(s)5.        V π ( s ) ← ∑ a ∈ A ( s ) π ( a ∣ s ) ∑ s ′ , r P ( s ′ , r ∣ s , a ) [ r + γ V π ( s ′ ) ] V_\pi(s) \gets \sum_{a \in \mathcal A(s)} \pi(a \mid s) \sum_{s',r}P(s',r \mid s,a)[r +\gamma V_\pi(s')] Vπ​(s)←∑a∈A(s)​π(a∣s)∑s′,r​P(s′,r∣s,a)[r+γVπ​(s′)]6.        d e l t a ← max ⁡ ( d a l t a , ∣ v − V π ( s ) ∣ ) delta \gets \max(dalta,\mid v -V_\pi(s) \mid) delta←max(dalta,∣v−Vπ​(s)∣)7.    end for8. until d e l t a < θ delta < \theta delta