强化学习算法之表格型方法

免模型预测方法

蒙特卡洛策略评估

蒙特卡洛方法是基于采样的方法，给定策略，我们让智能体与环境进行交互，可以得到很多轨迹。求出所有轨迹的回报的平均值，就可以知道某一个策略对应状态的价值。

蒙特卡洛方法使用经验平均回报（empirical mean return）的方法来估计，它不需要马尔可夫决策过程的状态转移函数和奖励函数，并且不需要像动态规划那样用自举（根据其他估算值来更新估算值的思想称为自举）的方法。蒙特卡洛方法有一定的局限性，它只能用在有终止的马尔可夫决策过程中。

增量式蒙特卡洛方法：

动态规划方法：

蒙特卡洛方法相比动态规划方法是有一些优势的。首先，蒙特卡洛方法适用于环境未知的情况，而动态规划是有模型的方法。 蒙特卡洛方法只需要更新一条轨迹的状态，而动态规划方法需要更新所有的状态。状态数量很多的时候（比如100万个、200万个），我们使用动态规划方法进行迭代，速度是非常慢的。这也是基于采样的蒙特卡洛方法相对于动态规划方法的优势。

时序差分

时序差分可以参考巴甫洛夫的条件反射实验：小狗会对盆里面的食物无条件产生刺激，分泌唾液。一开始小狗对于铃声这种中性刺激是没有反应的，可是我们把铃声和食物结合起来，每次先给它响一下铃，再给它喂食物，多次重复之后，当铃声响起的时候，小狗也会开始流口水。盆里的肉可以认为是强化学习里面那个延迟的奖励，声音的刺激可以认为是有奖励的那个状态之前的状态。多次重复实验之后，最后的奖励会强化小狗对于声音的条件反射，它会让小狗知道这个声音代表着有食物，这个声音对于小狗也就有了价值，它听到这个声音就会流口水。

当中性刺激（铃声）与无条件刺激（食物）相邻反复出现的时候，中性刺激也可以引起无条件刺激引起的唾液分泌，然后形成条件刺激。 我们称这种中性刺激与无条件刺激在时间上面的结合为强化，强化的次数越多，条件反射就会越巩固。小狗本来不觉得铃声有价值的，经过强化之后，小狗就会慢慢地意识到铃声也是有价值的，它可能带来食物。更重要的是当一种条件反射巩固之后，我们再用另外一种新的刺激和条件反射相结合，还可以形成第二级条件反射，同样地还可以形成第三级条件反射。

时序差分是介于蒙特卡洛和动态规划之间的方法，它是免模型的，不需要马尔可夫决策过程的转移矩阵和奖励函数。 此外，时序差分方法可以从不完整的回合中学习，并且结合了自举的思想。

时序差分方法的目的是对于某个给定的策略，在线（online）地算出它的价值函数，即一步一步地（step-by-step）算。

最简单的算法是一步时序差分（one-step TD），即 TD(0)。每往前走一步，就做一步自举，用得到的估计回报（estimated return）来更新上一时刻的值：

估计回报被称为时序差分目标（TD target），时序差分目标是带衰减的未来奖励的总和。时序差分目标由两部分组成：

1. 我们走了某一步后得到的实际奖励；
2. 我们利用了自举的方法，通过之前的估计来估计，并且加了折扣因子，即。

时序差分目标是估计，有两个原因：

1. 时序差分方法对期望值进行采样；
2. 时序差分方法使用当前估计的而不是真实的。

时序差分误差（TD error）。类比增量式蒙特卡洛方法，给定一个回合，我们可以更新来逼近真实的回报，具体更新公式为：

上式体现了强化的概念。

我们对比一下蒙特卡洛方法和时序差分方法。在蒙特卡洛方法里面，是实际得到的值（可以看成目标），因为它已经把一条轨迹跑完了，可以算出每个状态实际的回报。时序差分不等轨迹结束，往前走一步，就可以更新价值函数。 如下图所示，时序差分方法只执行一步，状态的值就更新。蒙特卡洛方法全部执行完之后，到了终止状态之后，再更新它的值。

接下来，进一步比较时序差分方法和蒙特卡洛方法。

1. 时序差分方法可以在线学习（online learning），每走一步就可以更新，效率高。蒙特卡洛方法必须等游戏结束时才可以学习。
2. 时序差分方法可以从不完整序列上进行学习。蒙特卡洛方法只能从完整的序列上进行学习。
3. 时序差分方法可以在连续的环境下（没有终止）进行学习。蒙特卡洛方法只能在有终止的情况下学习。
4. 时序差分方法利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率。蒙特卡洛方法没有假设环境具有马尔可夫性质，利用采样的价值来估计某个状态的价值，在不是马尔可夫的环境下更加有效。

例如，我们想获得开车去公司的时间，每天上班开车的经历就是一次采样。假设我们今天在路口 A 遇到了堵车， 时序差分方法会在路口 A 就开始更新预计到达路口 B、路口 C ⋯⋯⋯⋯，以及到达公司的时间； 而蒙特卡洛方法并不会立即更新时间，而是在到达公司后，再更新到达每个路口和公司的时间。 时序差分方法能够在知道结果之前就开始学习，相比蒙特卡洛方法，其更快速、灵活。

我们可以把时序差分方法进行进一步的推广。之前是只往前走一步，即TD(0)。 我们可以调整步数（step），变成 步时序差分（-step TD）。比如 TD(2)，即往前走两步，利用两步得到的回报，使用自举来更新状态的价值。

如果， 即整个游戏结束后，再进行更新，时序差分方法就变成了蒙特卡洛方法。

步时序差分可写为：

得到时序差分目标之后，我们用增量式学习（incremental learning）的方法来更新状态的价值：

自举是指更新时使用了估计。蒙特卡洛方法没有使用自举，因为它根据实际的回报进行更新。 动态规划方法和时序差分方法使用了自举。

免模型控制方法

Sarsa：同策略时序差分控制

时序差分方法是给定一个策略，然后我们去估计它的价值函数。接着我们要考虑怎么使用时序差分方法的框架来估计Q函数，也就是 Sarsa 算法。

Sarsa 所做出的改变很简单，它将原本时序差分方法更新的过程，变成了更新，即：

上式是指我们可以用下一步的值来更新这一步的值。 Sarsa 直接估计 Q 表格，得到 Q 表格后，就可以更新策略。

如图 3.28 所示，我们先把当作目标值，即想要逼近的目标值。就是时序差分目标。

Q学习：异策略时序差分控制

Sarsa 是一种同策略（on-policy）算法，它优化的是它实际执行的策略，它直接用下一步会执行的动作去优化 Q 表格。同策略在学习的过程中，只存在一种策略，它用一种策略去做动作的选取，也用一种策略去做优化。所以 Sarsa 知道它下一步的动作有可能会跑到悬崖那边去，它就会在优化自己的策略的时候，尽可能离悬崖远一点。这样子就会保证，它下一步哪怕是有随机动作，它也还是在安全区域内。

Q学习是一种异策略（off-policy）算法。异策略在学习的过程中，有两种不同的策略：目标策略（target policy）和行为策略（behavior policy）。

目标策略是我们需要去学习的策略，一般用来表示。目标策略就像是在后方指挥战术的一个军师，它可以根据自己的经验来学习最优的策略，不需要去和环境交互。

行为策略是探索环境的策略，一般用来表示。行为策略可以大胆地去探索到所有可能的轨迹，采集轨迹，采集数据，然后把采集到的数据“喂”给目标策略学习。而且“喂”给目标策略的数据中并不需要，而 Sarsa 是要有的。行为策略像是一个战士，可以在环境里面探索所有的动作、轨迹和经验，然后把这些经验交给目标策略去学习。比如目标策略优化的时候，Q学习不会管我们下一步去往哪里探索，它只选取奖励最大的策略。

Q学习是异策略的时序差分学习方法，Sarsa 是同策略的时序差分学习方法。

Sarsa 在更新 Q 表格的时候，它用到的是。我们要获取下一个 Q 值的时候，是下一个步骤一定会执行的动作，这个动作有可能是-贪心方法采样出来的动作，也有可能是最大化 Q 值对应的动作，也有可能是随机动作，但这是它实际执行的动作。

但是 Q学习 在更新 Q 表格的时候，它用到的是 Q 值对应的动作 ，它不一定是下一个步骤会执行的实际的动作，因为我们下一个实际会执行的那个动作可能会探索。 Q学习默认的下一个动作不是通过行为策略来选取的，Q学习直接看Q表格，取它的最大化的值，它是默认为最佳策略选取的动作，所以 Q学习 在学习的时候，不需要传入，即的值。

ps：Sarsa 在计算时使用下一步实际执行的动作，而Q学习在计算时使用最优策略，即目前按照目前Q函数计算出最优价值的动作，但是实际执行的动作和Sarsa一样，使用-贪婪策略。

同策略和异策略的区别：

• Sarsa 是一个典型的同策略算法，它只用了一个策略，它不仅使用策略学习，还使用策略与环境交互产生经验。如果策略采用-贪心算法，它需要兼顾探索，为了兼顾探索和利用，它训练的时候会显得有点“胆小”。它在解决悬崖行走问题的时候，会尽可能地远离悬崖边，确保哪怕自己不小心探索了一点儿，也还是在安全区域内。此外，因为采用的是-贪心 算法，策略会不断改变（值会不断变小），所以策略不稳定。
• Q学习是一个典型的异策略算法，它有两种策略————目标策略和行为策略，它分离了目标策略与行为策略。Q学习可以大胆地用行为策略探索得到的经验轨迹来优化目标策略，从而更有可能探索到最佳策略。行为策略可以采用-贪心 算法，但目标策略采用的是贪心算法，它直接根据行为策略采集到的数据来采用最佳策略，所以 Q学习 不需要兼顾探索。

本文参考：第三章 表格型方法 (datawhalechina.github.io)

Github地址：MyShare/DRL/Q-table at master · TyroGzl/MyShare (github.com)

也可关注公众号【G的科研生活】，回复【DRL】获取源码