强化学习的那些事（二）

背景

在上篇文章中，主要是定义了强化学习的相关概念，以及强化学习的建模过程和优化求解的目标。本篇主要是介绍强化学习目标优化的求解方法。其实我们在面对一个强化学习问题的时候有两种主要场景：一种是当前环境是已知的，另一种是当前环境是未知的。

环境已知和未知

什么是环境已知和未知呢？对于这个问题，我们可以这么理解这个事情。从稍微专业的角度来讲，就是需要具备这样的两个条件即可：1. 动作状态转移概率矩阵是已知的，还是未知的；2. 从某个状态通过某个动作到另外一个状态，回报是确定的还是不确定的。再更简单地理解这个问题，我们可以假设这样的两个场景。

对于第一个场景，我们很熟悉它是一个华容道的游戏。在这个游戏里面，状态就是当前每个将领的位置，动作就是需要移动的方向，从当前状态移动到另个状态的概率是可以假设的，因为可选择的动作空间很小，可以通过搜索所有的动作来进行暴力破解。

对于第二个场景，就是英雄联盟。在这样的环境当中，面对的状态是很不确定的，而且状态空间很巨大，动作也是各种情况。对于这样的情况，我们就认为它是一个环境未知的场景，采用传统的暴力方法是无法找到最优的打法的，是无法帮你上王者的。

上述两种场景，在强化学习领域都有相应的优化方法来解决。用图表示一下：

Model base的方法

model base的方法是用来解决环境已知的强化学习问题。其实说白了，当我们已知状态转移矩阵和状态动作回报，同时为了最大化回报。这个问题其实就是一个动态规划问题

。对于强化学习的动态规划问题，又可以分为策略迭代和值迭代

策略迭代

策略迭代包含策略预估和策略提升两个部分。在策略预估这个环节主要是需要基于当前策略，来预估出每个状态在当前策略下的一个回报，不断迭代直到最后收敛。然后再进入下一个环节：策略提升。在这个环节，基于当前每个状态的预估回报，选择最佳动作来更新状态策略直到每个状态的策略不变化。这样得到就是最后的最优策略。策略迭代的优缺点是：收敛速度快，但计算量大，适合状态空间较小的情况。

值迭代

值迭代实际上是没有给出策略，直接在预估出当前状态在最优策略下的回报值。这样最后就能直接选择出每个状态下的最优策略，不需要有策略提升这个环节。它的优缺点是：计算量小，但收敛会比较慢，适合大状态空间的计算。

Model Free的方法

model Free 方法就是在环境未知的情况下给出的强化学习解决方法。目前主要有两种解决方法：蒙特卡罗方法（MC），时间差分（TD）

蒙特卡罗方法

蒙特卡罗方法又叫统计模拟法，它是使用随机数或伪随机数来解决计算的问题。举个case。我们用小黑米铺满一个正方形，然后想要计算圆的面积怎么办？这个时候就用小黑米再铺满圆，然后数正方形的小黑米数和圆的小黑米数，小黑米的比值就是正方形和圆面积的比值。再比如，我们如果想知道某个状态下在策略pi的回报值R(s)，只需要有足够多的从s状态开始的回报值然后求平均，比如这样：

有5次的episode在同样的策略下的动作得到了最后如上图所示的回报。根据first MC methods，对出现过状态s的episode的累积回报取平均值，就有如下的公式：

动作值函数的MC估计也类似于状态值函数估计。在状态转移矩阵已知的情况下，策略估计后有了新的值函数，我们就可以进行策略提升，只需要看哪个动作能获得最大的累计期望回报即可。然而在环境未知，动作转移矩阵概率未知的情况下这是不可行的。因此我们需要预估动作值函数，即在状态s下采用动作a，后续遵循该策略下的期望累积回报也是用平均回报来进行估计。

另外一个问题是探索问题。我们可以这样理解，因为在环境未知的情况下，策略的迭代更新仅仅根据已经发生的事实来进行优化，会让策略在某种程度上陷入了局部的最优解。因为有很多状态和动作是没有发生的，但并不代表不会更优更好，所以在强化学习中也会需要借助E&E策略（探索和利用）。举个case，在某个确定的状态S0下可以执行a0，a1，a2三个动作。如果模型已经估计出两个Q函数值，如Q(s0,a0)，Q（s1,a1），且Q(s0,a0) > Q(s1,a1)，那么它在未来只会执行一个确定的动作a0，失去了其他的可能性。E&E策略的思想很简单，就是在每一次执行动作的时候都有一定的概率去执行一些其他动作，这样我们就可以获得所有动作的估计值，然后通过慢慢减少随机概率值来最终使得算法收敛。

基于以上MC方法的特点，我们给出MC方法的伪代码，大家感受一下：

Monte Carlo方法的优点是可以直接从经验中学习到策略，对所有状态s的估计都是独立的，不依赖其他状态的值函数。但是现在直接使用MC方法的情况很少，而较多的是采用TD算法（时间差分方法）。

时间差分方法

时间差分法（TD learning）有一个前提条件，是基于constant-alpha MC，它的状态值更新如下：

其中Rt是每个episode结束后获得的实际累积回报，alpha是学习率，这个式子的理解是我们用实际累积回报Rt作为状态值函数V(St)的估计值。实际操作是对每一个episode考察实际累积的回报Rt和当前估计的V(St)的偏差值，并用该偏差值乘以学习率来更新V(St)的新的估计值，有点类似于梯度下降的方法。现在我们将公式修改如下，把Rt换成了

利用真实的立即回报r_t+1和下一个状态的值函数V(St+1)来更新V(St)，这种方法就称为时间差分。由于我们没有状态转移概率，所以要利用多次实验来得到期望状态值函数估值。类似MC的方法，在足够多的实验后，状态值函数的估计是能够收敛于真实值的。

TD learning 分为on-policy和off-policy两类。这两类方法的区别在于on-policy方法是选择策略的方法和更新策略的方法是一致的；off-policy方法是选择策略的方法和更新策略的方法是不一致的。Sara算法便是一种on-policy方法，其伪代码如下：

另外一种算法叫Q-learning的TD方法。Q-learning算法和Sara算法最大的不同在于更新Q值的时候，直接使用了最大的Q(St+1,a)值，相当于采用了Q(St+1,a)值最大的动作,并且与当前执行的策略，即选用动作at时的策略无关。Q-learning的伪代码如下：

MC和TD的对比

结论

这篇文章主要是介绍了强化学习中model base 和 model free 这两种方法下常用的优化解决方法。在环境已知的情况下，常用的方法是策略迭代和值迭代两种方法，一个是适合有限的状态空间，一个是适合比较大的状态空间；在环境未知的情况下，常用的方法是MC和TD，一个是适合有结束状态的问题，一个是适合连续无结束状态的问题。这两种方法是强化学习问题解决的两种具有代表性，典型性的思路。

参考文献

https://www.cnblogs.com/jinxulin/p/3560737.html

https://www.cnblogs.com/jinxulin/p/5116332.html