《强化学习理论与应用》规划与蒙特卡洛树搜索

目录

模型、学习与规划8.18.3

决策时间规划8.2

Dyna-Q结构及其算法改进8.5

习题8.4小结1

在强化学习领域，根据MDP环境中是否包含完备的迁移概率，分为有模型和无模型方法。前面章节中的DP方法属于有模型方法，而MC、TD、n-步TD等方法属于无模型的方法。有模型方法将规划（planning）作为主要组成部分；在无模型方法将学习（learning）作为主要组成部分；

本章的重点并非是将两种方法进行区分，而是以一定的方法对它们进行有效的结合。引言8.1.1模型Agent可以通过模型来预测环境并作出反应，即在给定一个状态和动作时，通过模型，可以对下一状态和奖赏进行预测。如果模型是随机的，则存在多种可能的下一状态和奖赏。8.1模型、学习与规划（1）

模型通常可以分为分布模型和样本模型两种类型：分布模型（distributionmodel）

该模型可以生成所有可能的结果及其对应的概率分布。可以理解为，状态转移概率p已知，在状态s下执行动作a能够给出所有可能的下一状态和相应的转换概率，如DP算法。8.1模型、学习与规划（2）样本模型（samplemodel）

该模型能够从所有可能的情况中产生一个确定的结果。可以理解为，状态转移概率p未知，通过采样获取轨迹，如MC和TD算法。

从功能上讲，模型就是用于模拟环境和产生模拟经验的。与样本模型相比，分布模型包含更多的信息，只是现实任务中难以获得所有的状态转移概率。8.1模型、学习与规划（3）8.1.2学习

学习过程是从环境产生的真实经验中进行学习。根据经验的使用方法，学习过程可以分为直接强化学习和简介强化学习两种类型：直接强化学习（directRL）

在真实环境中采集真实经验，根据真实经验直接改进值函数或策略，不受模型偏差的影响。8.1模型、学习与规划（4）间接强化学习

在真实环境中采集真实经验，根据真实经验来构建和改进模拟模型（simulatedmodel），提高模拟模型精度，使其更接近真实环境。

间接强化学习包含模型学习和模型规划两个过程，通常能更充分地利用有限的经验。而直接强化学习是一种直接的学习，它更为简单，容易实现，不受模型构建带来的偏差影响。8.1模型、学习与规划（5）8.1.3规划

规划过程是基于模拟环境或经验模型，从模拟经验中改进值函数，实现改善策略的目的。学习和规划的核心都是通过迭代更新来评估值函数。

不同之处在于：在规划过程中，Agent并没有与真实环境进行交互。8.1模型、学习与规划（6）规划通常可分为：状态空间规划（state-spaceplanning）方案空间规划（plan-spaceplanning）

在强化学习领域，仅讨论状态空间规划。状态空间规划（以下所有状态空间规划都简称为规划）是在状态空间中寻找最优策略，值函数的计算都是基于状态的，通常将该规划方法视为“搜索”方法。8.1模型、学习与规划（7）所有规划算法都以计算值函数作为策略改进的中间关键步骤；所有规划算法都可以通过基于模型产生的模拟经验来计算值函数。规划的基本链式结构如下所示：

真实经验既可用于改进模拟模型，也可直接改进值函数或策略。8.1模型、学习与规划（8）8.1模型、学习与规划（9）图8.1规划Agent的角色图一种常用的规划算法——随机采样单步表格式Q-planning算法。8.1模型、学习与规划（10）目录

模型、学习与规划8.28.3

决策时间规划8.1

Dyna-Q结构及其算法改进8.5

习题8.4小结138.2.1Dyna-Q架构Dyna-Q架构将学习和规划有机结合在一起，是有模型和无模型方法的融合。在Dyna-Q架构中，规划方法为随机采样单步表格式Q-planning算法，直接强化学习方法为单步表格式Q-leaning算法，模型学习方法为确定环境下的表格式算法。

8.2Dyna-Q结构及其算法改进（1）

图8.2Dyna架构图8.2Dyna-Q结构及其算法改进（2）8.2Dyna-Q结构及其算法改进（3）例8.1

将Dyna-Q架构用于例4.1扫地机器人实例，比较算法中不同规划步数对实验效果的影响。扫地机器人在任何状态下，动作空间都为

。机器人离开边界或撞到障碍物时，保持原地不变，得到+10的奖赏；到达充电桩时，得到+1的奖赏；捡到垃圾时，得到+5的奖赏；其他迁移情况，奖赏均为0。这里参数

，

，

。8.2Dyna-Q结构及其算法改进（4）

若每次实验都采用相同的初始种子来控制随机过程，则对于任意n值，第1个情节的步数都是完全相同的。而从第2个情节开始，n越大，收敛到最优策略的速度越快。当n=0时，采用的是无规划Agent，仅使用直接强化学习，即单步表格式Q-learning，学习速度最慢，大约需要25个情节才能得到最优策略。而当n=5时（5次规划方法），仅需5个情节；n=30时，仅需2个情节，即可得到最优策略。8.2Dyna-Q结构及其算法改进（5）例8.2将Dyna-Q架构应用于扫地机器人任务。在该任务中，Agent在不同的情节中采用n=0和n=50所获得的策略不同。因为与无规划Agent相比，规划Agent能更快地找到有效路径，所以当

n=50时，Dyna-Q算法值函数更新更快。

n=0和n=50时，第2个情节每个状态的策略8.2Dyna-Q结构及其算法改进（6）8.2.2优先遍历优先遍历是一种常用的提高规划效率的分布计算方法。在一定程度上，该方法可以避免随机选择状态和动作所导致的低效率问题。在使用优先遍历法时，用一个优先队列PQueue来存储值函数变化较大的状态-动作对

，并以动作值函数改变的大小（即TD误差）作为优先级P，来对其进行排序，然后依据该优先队列依次产生模拟经验。8.2Dyna-Q结构及其算法改进（7）当队列顶端的

被更新时，它对其前序

的影响也会被计算。如果这些影响超过某个阈值，就将相应的前序

也插入优先队列中（如果该

已经存在于队列中，则保留优先级高的）。通过优先遍历法，值函数变化的影响被有效地反向传播，直到消失。优先级P定义为单步TD误差（即Q-learning算法的TD误差），其计算迭代式为：8.2Dyna-Q结构及其算法改进（8）8.2Dyna-Q结构及其算法改进（9）例8.3在扫地机器人环境中，分别用n=10、n=30的Dyna-Q算法和优先遍历算法进行训练，将到达垃圾状态[8,5]和充电状态[1,6]的迁移奖赏均设置为+1，其他情况迁移奖赏均设置为-0.1，参数

，

，

。8.2Dyna-Q结构及其算法改进（10）

实验结果表明：

在除了到达垃圾和充电状态以外，其他奖赏都为负值的情况下，优先遍历算法运行效果好于Dyna-Q算法，能更快地找到最优路径。8.2Dyna-Q结构及其算法改进（11）

现在将设置改成：除了到达垃圾和充电状态以外，其他奖赏都为0。同样采用用n=10、n=30的Dyna-Q算法和优先遍历算法进行训练，运行结果如图所示：由图可以看出：当除了到达垃圾和充电状态以外，其他奖赏都为0时，优先遍历算法运行效果略低于Dyna-Q算法。8.2Dyna-Q结构及其算法改进（12）利用优先遍历算法的规划过程，对队列中的每个

值只进行了1次更新。与n=30的Dyna-Q算法相比，更新次数太少。特别是在开始阶段，第1个情节结束后，进行规划的次数仅为1次；在扫地机器人环境，涉及的状态空间较小（77个状态）。优先扫描算法在大状态空间中才能表现出其优势；当除了到达垃圾和充电状态以外，其他奖赏都为负时，优先遍历算法每步都会进行规划；而其他转移奖赏为0时，优先遍历算法只对靠近终止位置（垃圾和充电桩）的状态进行规划更新。8.2Dyna-Q结构及其算法改进（13）将优先遍历思想推广到随机性环境时，由于其采用的是期望更新，所以模型保存的是每一组

出现的次数以及它们下一状态

出现的次数（概率），可能需要耗费大量的时间。尤其是在缺乏分布模型的情况下，期望更新更难以实现的。相比较而言，采样更新能将整个回溯计算分解为更小的片段，每一部分对应一个转换，使计算能够聚焦于产生最大影响的片段上。尽管采样更新会引入方差，但通常在训练过程中，只需要耗费较少的计