1、增强学习 Reinforcement Learning 经典算法梳理 1：policy and value iteration前言就目前来看，深度增强学习（Deep Reinforcement Learning)中的很多方法都是基于以前的增强学习算法，将其中的 value function 价值函数或者 Policy function 策略函数用深度神经网络替代而实现。因此，本文尝试总结增强学习中的经典算法。本文主要参考：1 Reinforcement Learning: An Introduction；2 Reinforcement Learning Course by David Silv
2、er1 预备知识对增强学习有所理解，知道 MDP，Bellman 方程详细可见： Deep Reinforcement Learning 基础知识（DQN 方面）很多算法都是基于求解 Bellman 方程而形成：Value IterationPolicy IterationQ-LearningSARSA2 Policy Iteration 策略迭代Policy Iteration 的目的是通过迭代计算 value function 价值函数的方式来使 policy 收敛到最优。Policy Iteration 本质上就是直接使用 Bellman 方程而得到的：那么 Policy Iterati
3、on 一般分成两步：Policy Evaluation 策略评估。目的是 更新 Value FunctionPolicy Improvement 策略改进。 使用 greedy policy 产生新的样本用于第一步的策略评估。本质上就是使用当前策略产生新的样本，然后使用新的样本更新当前的策略，然后不断反复。理论可以证明最终策略将收敛到最优。具体算法：那么这里要注意的是 policy evaluation 部分。这里的迭代很重要的一点是需要知道 state 状态转移概率 p。也就是说依赖于 model 模型。而且按照算法要反复迭代直到收敛为止。所以一般需要做限制。比如到某一个比率或者次数就停止迭
4、代。3 Value Iteration 价值迭代Value Iteration 则是使用 Bellman 最优方程得到然后改变成迭代形式value iteration 的算法如下：那么问题来了：Policy Iteration 和 Value Iteration 有什么本质区别？为什么一个叫 policy iteration，一个叫 value iteration 呢？原因其实很好理解，policy iteration 使用 bellman 方程来更新 value，最后收敛的 value 即 v 是当前policy 下的 value 值（所以叫做对 policy 进行评估），目的是为了后面的
5、policy improvement 得到新的policy。而 value iteration 是使用 bellman 最优方程来更新 value，最后收敛得到的 value 即 v就是当前 state 状态下的最优的 value 值。因此，只要最后收敛，那么最优的 policy 也就得到的。因此这个方法是基于更新 value的，所以叫 value iteration。从上面的分析看，value iteration 较之 policy iteration 更直接。不过问题也都是一样，需要知道状态转移函数 p 才能计算。本质上依赖于模型，而且理想条件下需要遍历所有的状态，这在稍微复杂一点的问题上
6、就基本不可能了。4 异步更新问题那么上面的算法的核心是更新每个状态的 value 值。那么可以通过运行多个实例同时采集样本来实现异步更新。而基于异步更新的思想，DeepMind 出了一篇不错的 paper：Asynchronous Methods for Deep Reinforcement Learning。该文对于 Atari 游戏的效果得到大幅提升。5 小结Reinforcement Learning 有很多经典算法，很多算法都基于以上衍生。鉴于篇幅问题，下一个 blog 再分析基于蒙特卡洛的算法。增强学习 Reinforcement Learning 经典算法梳理 2：蒙特卡洛方法1
7、前言在上一篇文章中，我们介绍了基于 Bellman 方程而得到的 Policy Iteration 和 Value Iteration 两种基本的算法，但是这两种算法实际上很难直接应用，原因在于依然是偏于理想化的两个算法，需要知道状态转移概率，也需要遍历所有的状态。对于遍历状态这个事，我们当然可以不用做到完全遍历，而只需要尽可能的通过探索来遍及各种状态即可。而对于状态转移概率，也就是依赖于模型 Model，这是比较困难的事情。什么是状态转移？就比如一颗子弹，如果我知道它的运动速度，运动的当前位置，空气阻力等等，我就可以用牛顿运动定律来描述它的运动，进而知道子弹下一个时刻会大概在哪个位置出现。那
8、么这个基于牛顿运动定律来描述其运动就是一个模型 Model，我们也就可以知道其状态（空间位置，速度）的变化概率。那么基本上所以的增强学习问题都需要有一定的模型的先验知识，至少根据先验知识我们可以来确定需要多少输入可以导致多少输出。比如说玩 Atari 这个游戏，如果输入只有屏幕的一半，那么我们知道不管算法多么好，也无法训练出来。因为输入被限制了，而且即使是人类也是做不到的。但是以此同时，人类是无需精确的知道具体的模型应该是怎样的，人类可以完全根据观察来推算出相应的结果。所以，对于增强学习的问题，或者说对于任意的决策与控制问题。输入输出是由基本的模型或者说先验知识决定的，而具体的模型则可以不用考
9、虑。所以，为了更好的求解增强学习问题，我们更关注 Model Free 的做法。简单的讲就是如果完全不知道状态转移概率（就像人类一样），我们该如何求得最优的策略呢？本文介绍蒙特卡洛方法。2 蒙特卡洛方法蒙特卡洛方法只面向具有阶段 episode 的问题。比如玩一局游戏，下一盘棋，是有步骤，会结束的。而有些问题则不一定有结束，比如开赛车，可以无限的开下去，或者说需要特别特别久才能结束。能不能结束是一个关键。因为只要能结束，那么每一步的 reward 都是可以确定的，也就是可以因此来计算 value。比如说下棋，最后赢了就是赢了，输了就是输了。而对于结束不了的问题，我们只能对于 value 进行估
10、计。那么蒙特卡洛方法只关心这种能够较快结束的问题。蒙特卡洛的思想很简单，就是反复测试求平均。如果大家知道在地上投球计算圆周率的事情就比较好理解了。不清楚的童鞋可以网上找找看。那么如何用在增强学习上呢？既然每一次的 episode 都可以到结束，那么意味着根据：每一步的 reward 都知道，也就意味着每一步的 return Gt 都可以计算出来。这就好了。我们反复做测试，这样很多状态会被遍历到，而且不止一次，那么每次就可以把在状态下的 return 求和取平均。当 episode 无限大时，得到的数据也就接近于真实的数据。蒙特卡洛方法就是使用统计学的方法来取代 Bellman 方法的计算方法。
11、上面的算法叫 first-visit MC。也就是每一次的 episode 中 state 只使用第一次到达的 t 来计算 return。另一种方法就是 every-visit，就是每一次的 episode 中 state 只要访问到就计算 return 求平均。所以可以看到蒙特卡洛方法是极其简单的。但是缺点也是很明显的，需要尽可能多的反复测试，而且需要到每一次测试结束后才来计算，需要耗费大量时间。但是，大家知道吗？AlphaGo 就是使用蒙特卡洛的思想。不是蒙特卡洛树搜索，而是说在增强学习中使用蒙特卡洛方法的思想。AlphaGo 每次也是到下棋结束，而且只使用最后的输赢作为 return。所
12、以这也是非常神奇的事，只使用最后的输赢结果，竟然能够优化每一步的走法。3 使用蒙特卡洛方法来控制上面说的蒙特卡洛方法只是能够对当前的 policy 进行评估。那么大家记得上一个 blog 说的 policy iteration方法吗？我们可以在 policy iteration 中使用蒙特卡洛方法进行评估，然后使用 greedy policy 更新。那么依然是有两种做法。一种就是在一个 policy 下测试多次，评估完全，然后更新 policy，然后再做很多测试。另一种就是不完全评估，每次测试一次完就评估，评估完就更新：第一种做法：第二种做法：两种做法都能够收敛，那么显然第二种做法的速度更快。
13、那么再改进一点，就是改变 greedy policy 中 的值，使得不断变小趋于 0，这个时候最后得到的 policy 就是完全的最优 policy 了。这个算法就叫做 GLIE Monte-Carlo Control：其他变种：Monte Carlo with Exploring Starts,使用 Q(s,a),然后使用上面说的第二种做法，一次 episod 就更新一次policy，而且 policy 直接使用 Q 值。policy 的更新使用了 greedy，目的就是能够更好的探索整个状态空间。4 Off Policy Learning那么上面的方法一直是基于当前的 policy，为了探
14、索状态空间，采用一个次优的策略 greedy policy 来探索。那么是不是可以更直接的使用两个 policy。一个 policy 用来探索空间，也就是 behavior policy，另一个policy 就是为了达到最优 policy，叫做 target policy。那么这种方法就叫做 off policy learning。On-policy 的方法比较简单，off-policy 方法需要更多的概念和标记，比较不好理解，而且，由于 behaviour policy 和 target policy 不相关，这种方法比较不容易收敛。但是 off-policy 更强大，更通用，实际上的 on
15、-policy 方法就是 off-policy 方法的一个子集。比如，就可以使用 off-policy 从人类专家或者传统的控制算法来学习一个增强学习模型。关键是要找到两个 policy 之间的权重关系，从而更新 Q 值。关于 off-policy learning 的部分，之后结合 TD 方法再做分析。小结本次 blog 分析了一下蒙特卡洛方法。这种基于统计学的方法算法简单，但是更多的只能用于虚拟环境能进行无限测试的情况。并且 state 状态比较有限，离散的最好。基于这个方法，比如简单的五子棋（棋盘最好小一点），就可以用这个方法来玩玩了。增强学习 Reinforcement Learnin
16、g 经典算法梳理 3：TD 方法1 前言在上一篇 blog 中，我们分析了蒙特卡洛方法，这个方法的一个特点就是需要运行完整个 episode 从而获得准确的 result。但是往往很多场景下要运行完整个 episode 是很费时间的，因此，能不能还是沿着 bellman 方程的路子，估计一下 result 呢？并且，注意这里，依然 model free。那么什么方法可以做到呢？就是TD（temporal-difference 时间差分）方法。有个名词注意一下：boostraping。所谓 boostraping 就是有没有通过估计的方法来引导计算。那么蒙特卡洛不使用 boostraping，而
17、 TD 使用 boostraping。接下来具体分析一下 TD 方法2 TD 与 MC 的不同MC 使用准确的 return 来更新 value，而 TD 则使用 Bellman 方程中对 value 的估计方法来估计 value，然后将估计值作为 value 的目标值进行更新。也因此，估计的目标值的设定将衍生出各种 TD 下的算法。那么 TD 方法的优势有什么呢？每一步都可以更新，这是显然，也就是 online learning，学习快；可以面对没有结果的场景，应用范围广不足之处也是显而易见的，就是因为 TD target 是估计值，估计是有误差的，这就会导致更新得到 value 是有偏差的
18、。很难做到无偏估计。但是以此同时，TD target 是每一个 step 进行估计的，仅最近的动作对其有影响，而 MC 的 result 则受到整个时间片中动作的影响，因此 TD target 的方差 variance 会比较低，也就是波动性小。还是放一下 David Silver 的总结吧：那么 David Silver 的 ppt 中有三张图，很清楚的对比了 MC，TD 以及 DP 的不同：从上面可以很清楚的看到三者的不同。DP 就是理想化的情况，遍历所有。MC 现实一点，TD 最现实，但是TD 也最不准确。但是没关系，反复迭代之下，还是可以收敛的。整个增强学习算法也都在上面的范畴里：3 TD 算法
