强化学习读书笔记（8）上| 用表格方法规划和学习

本讲为需要环境模型的model-based强化学习方法（如DP和启发式搜索）和不需要环境模型的model-free方法（比如MC和TD）提供一个统一的论述框架。基于模型的方法依赖规划（planning）作为其主要组成部分，而无模型方法主要依赖于学习（learning）。

Models and Planning

环境模型指agent可以用来预测环境如何响应其行为的任何事物。给定状态和动作，模型可以产生对结果下一状态和下一奖励的预测。如果模型是随机的，那么有几种可能的下一个状态和下一个奖励，每个都有一定的发生概率。有一些模型会产出所有可能性以及他们的概率，这种叫做分布模型（distribution model）。另一种是每次根据概率值采样产生一种可能性，这种叫做采样模型（sample model）。

模型可以用来模仿或仿真真实经验。给定一个初始状态和动作，采样模型可以产出一个可能的状态转移而分布模型可以产出所有可能的状态转移和他们发生的概率。而给定一个初始状态和策略，采样模型可以直接产出一个整个的episode而分布模型可以产出所有可能的episode以及他们发生的概率。所有的例子中模型都是用来模仿环境来产生仿真经验的。

规划（Planning）这个词在这里是指把模型作为输入通过与模型环境的交互产生或者改进一个策略的计算过程。在人工智能中有两种方式来进行规划：

State-space planning：从状态空间中搜索出一个最优的策略或者到达目标的最优路径。动作导致从状态到状态的转换，并且值函数在状态上计算；

plan-space planning：通过计划空间进行搜索。比如进化算法和partial-order planning。（计划空间方法很难有效地应用于强化学习中关注的随机序列决策问题，因此不再进一步考虑）

本章要描述的统一框架是指所有的状态空间计划算法都共享一种架构，同样适用于本书讲到的学习算法。两个基本思想：（1）所有状态空间规划方法都将计算值函数作为改进策略的关键中间步骤，（2）通过仿真经验来计算更新或者是backup操作。

学习算法和规划算法的核心是通过back up更新操作来估计价值函数。区别在于规划算法使用的是模型产生的仿真数据而学习算法是使用环境产生的真实数据。而他们都符合这个框架也就代表他们之间的很多算法可以直接通用。学习算法只需要使用经验数据作为输入，因此他们通常能够同时用在仿真数据和真实数据上。比如下面介绍了一个简单的基于一步表格Q-learning算法以及从采样模型产生的样本上的例子，这个方法叫做random-sample one-step tabular Q-planning，和一步表格Q-learning算法收敛条件相同。

Dyna: Integrated Planning,

Acting, and Learning

因为规划是通过在线与环境交互的，一些有趣的情景会发生。和环境交互获得的新信息可能会改变模型从而与规划算法交流。决策和模型的学习都是非常消耗计算力的操作，因此需要将当前算力分配给这两个部分。首先来定义一个简单的整合了在线规划agent需要的所有函数的框架Dyna-Q。

在规划的 agent中，实际经验至少有两个作用：它可用于改进模型（使其更准确地匹配真实环境），并且可用于直接改进值函数和的策略。前者称为模型学习model-learning（间接法），后者称为直接强化学习direct reinforcement learning（直接法）。

优缺点：间接法通常可以在experience数量有限的情况下更加充分地利用它们，得到更好的策略；直接法更加简单，而且间接法有可能模型本身有偏差。

Dyna算法思路如下图所示：

中间栏代表了agent与环境之间的基本互动，从而产生的真实经验的轨迹。图左侧的箭头表示从真实的经验中改进值函数和策略的直接RL。右边是基于模型的流程。该模型从实际经验中学习，并产生模拟经验。search control指代为模型生成的仿真经验选择起始状态和动作的过程。最后，通过将强化学习方法应用于模拟经验来实现规划。一般来说强化学习算法都可以应用在仿真经验和真实经验中。学习和规划的有很多的相同点，唯一的不同是经验的来源。

从概念上讲，规划，行为，模型学习和直接RL在Dyna agent中同时发生。在Dyna-Q中，行为，模型学习和直接RL过程几乎不需要计算。每个步骤中的剩余时间可用于规划过程，这本身就是计算密集型过程。在下面框中的Dyna-Q的伪代码算法中，Model（s,a）表示状态-动作对（s，a）的（预测的下一状态和奖励）的内容。直接RL，模型学习和规划分别通过步骤（d），（e）和（f）实施。如果省略（e）和（f），则剩余算法将是one-step tabular Q-learning。

When the Model Is Wrong

前面的例子中，环境状态都是固定不变的。然而模型是可能出错的，比如环境本身随机性很强，因此只有很少的样本被观察到；比如值函数是使用函数估计的，而估计函数不够合理；再比如环境是不断变化的，而新的最佳行为还未被观测到。当模型出错时，Planning可能会算出一个次优的策略。有的时候，次优的策略能够很快检测到模型的误差，从而重新探索找到最优解。这往往发生在该模型在预测更大的奖励或更好的状态转换上相比实际过于乐观的，因为这样原策略会发现自己行不通了，从而去寻找更好的方案。而更困难的情形是当环境变得比以前更好的时候，因为之前正确的策略不会再进行优化。这种情形下模型的错误有可能很长时间甚至永远都不会被察觉。

Dyna-Q+算法就使用了启发算法来解决这个问题。如果长期没有经过某个状态，那么这个状态的模型发生变化的可能性就越大。因此，为了激励这些长期没有采纳的行为，Dyna-Q+为它们适当的增加奖励，让agent更倾向选择它们。通过这样的方式增加了探索的代价，但也在需要探索的时候带来了明显的收益。

Prioritized Sweeping

上节介绍的Dyna的agent是随机等概率的从以往访问过的状态动作对中选择下一个产生仿真经验的起始状态。但是这样往往不是最好的选择，如果规划能够重点关注某些状态转移和更新会更好。

带优先级的扫描（Prioritized Sweeping）基本思想：优先更新那些停止状态附近的状态，或者可以说是得到更新的状态的上一步状态。以“value改变量”作为指标，对访问过的state-action pair进行优先级排序。构造一个Priority Queue（优先级队列），存储每次满足条件的state-action pair。

伪代码：

注意：P表示更新的幅度，当P小于阈值θ时，就不执行循环了（因为优先级队列为空）；当P大于阈值θ时，则从(S,A)出发向前回溯，将它们加入到优先级队列中，再循环从优先级队列中取出状态进行更新。

prioritized sweeping只是提高规划效率的一种方法，但不是最好的方法。将其扩展到不确定环境下，便受到了期望值的限制，会浪费很多时间在计算低概率的转移上。在下一讲中，我们将说到：在很多情况下，采样更新（sample updates）明显减小了计算量，其结果很接近真实的value function。

实例：Maze 迷宫

1 Dyna Maze

如下图所示，在迷宫的47个状态中的每个状态中，有四个动作：向上，向下，向右和向左，它们将agent确定性地带到相应的相邻状态；移动被障碍物或迷宫的边缘阻挡，则停止不动。所有过渡的奖励都是零，进入目标状态的过程+1。在达到目标状态（G）之后，用户返回到开始状态（S）以开始新的片段。

2 Blocking Maze

环境改变：最初，从开始到目标，到屏障右侧有一条短路径，（左图）；在1000个时间步之后，短路径被“阻挡”，并且沿着屏障的左侧打开更长的路径（右图）。

3 Shortcut Maze

这是一种环境变好的情形：最初，最佳路径是围绕屏障的左侧（左图）；然而，在3000步之后，沿着右侧打开较短的路径，而不会干扰较长的路径（右图）。

4 Prioritized Sweeping on Mazes

环境跟Dyna Maze相同。

代码编写：

参考https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/blob/master/chapter08/maze.py

定义优先级队列：

定义环境、动作：

设置Dyna参数

Dyna-Q

Blocking Maze

Shortcut Maze

Prioritized Sweeping

结果分析：

1． Dyna Maze

对比图中n=0(没有planning)和n=5,n=50(有planning),显然，有规划的agent发现解决方案的速度比非规划用户快得多。Planning 和 learning在 Dyna-Q中相辅相成，model learning 不断调整 model 以获得更精确的Planning，而learning 不断提升value和 Policy，两者叠加，加速了算法是收敛速度。

2 Blocking Maze

图的第一部分显示两个Dyna agent都在1000步内找到了短路径。当环境发生变化时，图表变得平坦，表明agent没有获得奖励的时期，因为他们在阻碍后面徘徊。然而，过了一段时间，他们便能够找到新的开口和新的最佳行为。

3 Shortcut Maze

该图显示环境变化后常规Dyna-Q agent并未切换到捷径，且从未发现捷径的存在。它的模型表示没有捷径，所以规划得越多，向右走并发现它的可能性就越小。Dyna-Q+在Dyna-Q的基础上，对每组state-action 距离自身最近一次出现的消失时间进行了统计，然后认为消失时间越久的state-action越容易发生变化，他的model就越可能出错。在shortcut maze中，Dyna-Q+的表现比Dyna-Q 好。

4 Prioritized Sweeping on Mazes

Prioritized Sweeping可显着提高在迷宫任务中找到最佳解决方案的速度，通常为5到10倍。

小结

本讲为需要环境模型的model-based强化学习方法和不需要环境模型的model-free方法提供一个统一的论述框架。Planning 需要环境模型（model)。distribution model包括所有state的转移和action 带来的reward。sample model根据概率生成一系列的state 和reward。动态规划需要distribution model来计算expected update。通常sample model比distribution model容易获得。我们已经接触了状态空间规划方法中的许多变化维度。一个方面是更新大小的变化。更新越小，规划方法的增量就越多。最小的更新包括one-step sample updates，如Dyna。另一个重要方面是更新的分布。Prioritized sweeping的重点是最近有value变化的前一个state。下一讲我们将继续对这一章进行介绍。

参考：

1.R.Sutton et al.Reinforcement learning:An introduction,1998

2. https://blog.csdn.net/qq_25037903/article/details/82469170

3. https://blog.csdn.net/LagrangeSK/article/details/81556933

4.https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/blob/master/chapter08/maze.py

转载自 | 公众号 老薛带你学Python