Integrating Learning and Planning（续）

Table Lookup Model

查表模型适用于MDP的P，R都为已知的情况。我们通过visit得到各状态行为的转移概率和奖励，把这些数据存入表中，使用时直接检索。状态转移概率和奖励计算方法如下：

$\hat{P}^a_{s,s'}=\frac{1}{N(s,a)}\sum_{t=1}^T 1(S_t,A_t,S_{t+1}=s,a,s')$P^s,s′a​=N(s,a)1​t=1∑T​1(St​,At​,St+1​=s,a,s′)

$\hat{R}^a_{s}=\frac{1}{N(s,a)}\sum_{t=1}^T 1(S_t,A_t=s,a)R_t$R^sa​=N(s,a)1​t=1∑T​1(St​,At​=s,a)Rt​

其中的$N(s,a)$N(s,a)表示state action pair$<s,a>$<s,a>在visit中出现的次数。

这里也可以采用如下变种：

• 在每个time-step：t，记录experience tuple：$<S_t, A_t, R_{t+1}, S_{t+1}>$<St​,At​,Rt+1​,St+1​>。

• 从模型采样构建虚拟经历时，从tuples中随机选择符合$<s,a,\cdot,\cdot>$<s,a,⋅,⋅>的一个tuple。

这种方法，不再以Episode为最小学习单位，而是以时间步（time-step）为单位，一次学习一个状态转换。

Planning with a Model

规划的过程相当于求解一个MDP的过程，即给定一个模型$M_\eta = <P_\eta, R_\eta>$Mη​=<Pη​,Rη​>，求解MDP$<S, A, P_\eta, R_\eta>$<S,A,Pη​,Rη​>，找到基于该模型的最优价值函数或最优策略，也就是在给定的状态s下确定最优的行为a。

我们可以使用之前介绍过的价值迭代，策略迭代方法；也可以使用树搜索方法（Tree Search）。

Sample-Based Planning

Sample-Based Planning使用Model生成采样数据，即一个time-step的虚拟经历。

有了这些虚拟采样，随后使用model-free RL方法来学习得到价值或策略函数。

Planning with an Inaccurate Model

由于实际经历的不足或者一些无法避免的缺陷，我们通过实际经历学习得到的模型不可能是完美的模型，即：$<P_\eta, R_\eta> = <P,R>$<Pη​,Rη​>=<P,R>

而model-based RL的性能取决于Model的准确度，如果Model不准确的话，往往只能得到一些次优解。

使用近似的模型解决MDP问题与使用价值函数或策略函数的近似表达来解决MDP问题并不冲突，他们是从不同的角度来近似求解MDP问题，有时候构建一个模型来近似求解MDP比构建一个近似的价值函数或策略函数要更加方便，这是model-based RL的可取之处。

同时由于个体经历的更新，模型处在一个动态变化的过程，当利用早期经历构建的模型后来被认为存在很大错误，不适用于当下经历的时候，需要放弃模型，转而使用model-free RL。

此外，可以在模型中，增加一些不确定性，以跳出次优解。

model-based RL适用于连续变量的状态和行为空间。

Dyna-Q Algorithm

当构建了一个环境的模型后，个体可以有两种经历来源：

• 实际经历(real experience)。

$S'\sim P_{s,s'}^a, R=R_s^a$S′∼Ps,s′a​,R=Rsa​

• 模拟经历(simulated experience)。

$S'\sim P_\eta(S' | S,A), R=R_\eta(R | S,A)$S′∼Pη​(S′∣S,A),R=Rη​(R∣S,A)

对于Model-Free RL来说，所有的知识都来源于real experience。

对于Model-Based RL来说，Model来源于real experience，而planning相关的知识来源于simulated experience。

于是我们很自然的想到，是否可以把real experience和simulated experience结合起来呢？

上图是Dyna算法的流程图。它从实际经历中学习得到模型，然后联合使用实际经历和模拟经历，一边学习，一边规划更新价值和（或）策略函数。

Dyna-Q算法流程如下：

Initialize $Q(s, a)$Q(s,a) and $Model(s, a)$Model(s,a) for all $s \in S$s∈S and $a \in A(s)$a∈A(s)
Do forever:

(a) $S \leftarrow$S← current (nonterminal) state
(b) $A \leftarrow \epsilon-greedy(S, Q)$A←ϵ−greedy(S,Q)
© Execute action A; observe resultant reward, R, and state S’
(d) $Q(S, A) \leftarrow Q(S, A)+\alpha[R+\gamma \max_a Q(S', a)-Q(S, A)]$Q(S,A)←Q(S,A)+α[R+γmaxa​Q(S′,a)−Q(S,A)]
(e) $Model(S, A) \leftarrow R,S'$Model(S,A)←R,S′(assuming deterministic environment)
(f) Repeat n times:

$S \leftarrow$S← random previously observed state
$A \leftarrow$A← random action previously taken in S
$R, S' \leftarrow Model(S, A)$R,S′←Model(S,A)
$Q(S, A) \leftarrow Q(S, A)+\alpha[R+\gamma \max_a Q(S', a)-Q(S, A)]$Q(S,A)←Q(S,A)+α[R+γmaxa​Q(S′,a)−Q(S,A)]

这个算法赋予了个体在与实际环境进行交互式时有一段时间用来思考的能力。其中的步骤：a,b,c,d和e都是从实际经历中学习，d过程是学习价值函数，e过程是学习模型。

在f步，给以个体一定时间（或次数）的思考。在思考环节，个体将使用模型，在之前观测过的状态空间中随机采样一个状态，同时从这个状态下曾经使用过的行为中随机选择一个行为，将两者带入模型得到新的状态和奖励，依据这个来再次更新行为价值函数。

上图是细化后的Dyna框架图。从上面的分析可以看出，Dyna与其说是一个算法，倒不如说是一个算法框架，两者的区别在于：框架的每个组成部分，可以采用不同的算法，只要各部分之间的关系不变，就还算是同一个框架。

上图比较了在Dyna算法中一次实际经历期间采取不同步数的规划时的个体表现。横坐标是Episode序号，纵坐标是特定Episode所花费的步数。可以看出，当直接使用实际经历时，个体在早期完成一个Episode需要花费较多步数，而使用5步或50步思考步数时，个体完成一个Episode与环境发生的实际交互的步数要少很多。不过到了后期，基本上就没什么差别了。

可以看出Dyna算法可以有效提升算法的收敛速度，但不会提高最终的性能。

上面的例子模拟了某时刻（虚线所示）环境发生了改变，变得更加困难，此时使用Dyna-Q算法在经历过一段时间的平台期后又找到了最优解决方案。在平台期，模型持续的给以个体原先的策略，也就是错误的策略，但个体通过与实际的交互仍然能够找到最优方案。

上二个例子表明，Dyn-Q算法赋予了个体一定的应对环境变化的能力，当环境发生一定改变时，个体一方面可以利用模型，一方面也可以通过与实际环境的交互来重新构建模型。

上2个示例图中的Q+算法与Q的差别体现在：Q+算法鼓励探索，给以探索额外的奖励。

Simulation-Based Search

Planning主要有两个用途：

• 改善policy或value function。这种方式通常叫做background planning。它不在乎当前的状态，而在乎对于所有状态都有效的policy或value function。

• 直接根据当前状态选择动作。这种方式通常叫做decision-time planning。它更在乎于当前状态。

这里以最简单的前向搜索(Forward Search)算法来讨论一下decision-time planning的特点。

上图是Forward Search的示意图，图中绿色方格节点指的是终止状态。

这种算法以当前状态$S_t$St​作为根节点构建了一个搜索树（Search Tree），使用MDP模型进行前向搜索。前向搜索不需要解决整个MDP，而仅仅需要构建一个从当前状态开始与眼前的未来相关的次级（子）MDP。这相当于一个登山运动员的登山问题，在某一个时刻，他只需要关注当前位置（状态）时应该采取什么样的行为才能更有利于登山（或者下撤），而不需要考虑第二天中饭该吃什么，那是登顶并安全撤退后才要考虑的事情。

从中可以看出，background planning相当于是广度优先遍历，虽然考虑的比较全面，但决策的深度较浅，而decision-time planning虽然只考虑当前状态的情况，但决策的深度较深（通常是一个完整的episode），相当于是深度优先遍历。

sample-based planning+Forward search就得到了Simulation-Based Search。

首先，从Model中采样，形成从当前状态开始到终止状态的一系列Episode：

$\{s_t^k, A_t^k, R_{t+1}^k, \dots, S_T^k\}_{k=1}^K\sim M_v${stk​,Atk​,Rt+1k​,…,STk​}k=1K​∼Mv​

有了这些Episode资源，我们可以使用Model-Free的强化学习方法，如果我们使用Monte-Carlo control，那么这个算法可以称作蒙特卡罗搜索(Monte-Carlo Search)，如果使用Sarsa方法，则称为TD搜索(TD Search)。

Monte-Carlo Search

我们首先看一下Simple Monte-Carlo Search的步骤：

• 给定一个模型M和一个模拟的策略$\pi$π。

• 针对行为空间里的每一个行为$a\in A$a∈A：

从这个当前状态$s_t$st​开始模拟出K个Episodes：

$\{s_t^k, a, R_{t+1}^k, S_{t+1}^k, A_{t+1}^k,\dots, S_T^k\}_{k=1}^K\sim M_v,\pi${stk​,a,Rt+1k​,St+1k​,At+1k​,…,STk​}k=1K​∼Mv​,π

使用平均收获（蒙特卡罗评估）来评估当前行为a的行为价值：

$Q(s_t, a)=\frac{1}{K}\sum_{k=1}^KG_t\xrightarrow[]{P} q_\pi(s_t, a)$Q(st​,a)=K1​k=1∑K​Gt​P​qπ​(st​,a)

• 选择一个有最大Q值的行为作为实际要采取的行为：

$a_t = \mathop{\arg\max}_{a\in A}Q(s_t, a)$at​=argmaxa∈A​Q(st​,a)

Simple Monte-Carlo Search的主要问题在于模拟出的Episodes的质量依赖于Model的质量，如果Model不准确，就会导致一系列的偏差，最终会导致结果的不准确。

我们可以采用优化领域常用的Evaluate/Improve方法来改进Monte-Carlo Search，于是就得到了Monte-Carlo Tree Search（MCTS）方法。

这里先看一下MCTS的Evaluation阶段的流程：

• 给定一个模型M。

• 从当前状态$s_t$st​开始，使用当前的模拟策略$\pi$π,模拟生成K个Episodes：

$\{s_t^k, a, R_{t+1}^k, S_{t+1}^k, A_{t+1}^k,\dots, S_T^k\}_{k=1}^K\sim M_v,\pi${stk​,a,Rt+1k​,St+1k​,At+1k​,…,STk​}k=1K​∼Mv​,π

• 构建一个包括所有个体经历过的状态和行为的搜索树。

• 对于搜索树种每一个状态行为对$(s,a)$(s,a)，计算从该$(s,a)$(s,a)开始的所有完整Episode收获的平均值，以此来估算该状态行为对的价值$Q(s,a)$Q(s,a):

$Q(s_t, a)=\frac{1}{N(s,a)}\sum_{k=1}^K \sum_{u=t}^T 1(S_u,A_u=s,a) G_u\xrightarrow[]{P} q_\pi(s, a)$Q(st​,a)=N(s,a)1​k=1∑K​u=t∑T​1(Su​,Au​=s,a)Gu​P​qπ​(s,a)

• 选择一个有最大Q值的行为作为实际要采取的行为：

$a_t = \mathop{\arg\max}_{a\in A}Q(s_t, a)$at​=argmaxa∈A​Q(st​,a)

MCTS的一个特点是在构建搜索树的过程中，更新了搜索树内状态行为对的价值，积累了丰富的信息，利用这些信息可以更新模拟策略，使得模拟策略得到改进。换句话说，MCTS的策略不是一成不变的。

MCTS的Simulation也是有讲究的。

首先，改进策略时要分情况对待：

• 树内（in-tree）确定性策略（Tree Policy）：对于在搜索树中存在的状态行为对，策略的更新倾向于最大化Q值，这部分策略随着模拟的进行是可以得到持续改进的。

• 树外（out-of-tree）默认策略（Default Policy）：对于搜索树中不包括的状态，可以使用固定的随机策略。

随着不断地重复模拟，状态行为对的价值将得到持续地得到评估。同时基于$\epsilon-greedy(Q)$ϵ−greedy(Q)的搜索策略使得搜索树不断的扩展，策略也将不断得到改善。