增强学习系列之（一）：增强学习介绍

1. 什么是增强学习

增强学习是机器学习的一种。我们都知道，机器学习主要分监督学习、非监督学习、半监督学习、增强学习

从这个分类中我们就能看到，增强学习和我们平常主要接触的监督和非监督学习不太一样。监督和非监督学习的应用我们都很熟悉了，那增强学习可以应用在怎样的场景呢？

我们可以用增强学习让计算机自己去学着做事情，比如说让计算机学着去玩Flappy Bird，或者让计算机去计算数据，我们需要做的，我们不需要设置具体的策略，比如先飞到上面，再飞到下面，我们只是需要给算法定一个“小目标”！比如当计算机玩的好的时候，我们就给它一定的奖励，它玩的不好的时候，就给它一定的惩罚，在这个算法框架下，它就可以越来越好，超过人类玩家的水平。在这个系列的最后，就带着大家，实现一个这样的系统

1. 前言

1. 两个理论

我们先说两个看起来和增强学习不是很相关的例子（其实是相关的），一个是动态规划算法，一个是PageRank算法

动态规划算法我们大家其实都很熟悉了（动态规划算法其实是一个很大很大的坑）我们需要逐步的去找有最优子结构的状态，然后找到这些状态之间的求解的先后顺序，在状态之间构造一个有向无环图，来一步步地求解最后的问题

比如说最简单的，求费波纳齐数列，我们求解F(n)的时候，就需要有F(n-1)和F(n-2)两个状态

F(n) = F(n-1) + F(n-2)

对于这样一个问题，我们可以按照一定的步骤，一步一步求解，如果一个状态算过了，那就不需要算第二次

算法的感觉就是这样的

但有的时候我们其实是不清楚这个关系的，或者说问题根本就是有环的，那么这个时候我们该怎么办呢，最经典的例子就是Page-Rank算法，就是由Larry Page发明的，Google最先使用的网页排序算法
想要详细了解PageRank的同学可以点这个链接http://blog.jobbole.com/71431/，我在这里简单介绍一下

为什么介绍PageRank算法呢，因为增强学习和PageRank算法非常的像。比如一个机器人，它对环境是完全陌生的，它所有的行为的权重都是一样的。这个时候它需要对环境进行探索，它有的行为可以达到我们对它设置的奖励，有的行为可以到达我们对它设置的惩罚，那么它就可以修改它行为的权重，在迭代很多很多次之后，求出一个比较优的结果

2. 一个例子

比如我们现在来看一个机器人的例子，这个例子来自于[3]

我们把机器人放在一个完全陌生的房间里面，这个房间的布局如图所示，我们希望机器人能够自己学会走到目标的那个房间。

如果是传统的方法，我们就希望通过搜索，或者是记忆化的搜索（就是动态规划）在给出全局的布局后，我们就可以做路径规划了

但是如果这个房间的布局是未知的呢，这个时候我们就需要用增强学习的方法来尝试了

2. 总体介绍

所以说，从上面那个例子可以看到，增强学习的特征，就是从现有的状态出发，不断的优化自己的策略

我们先来介绍一些增强学习当中经常用到的术语

agent，是指训练当中的个体，就是我们训练的算法和参数的集合

environment，是指agent所处的环境

episode，是指一个完整的训练的阶段。从一次训练开始，到这次训练成功或者失败结束，是一个episode

step，是指一个episode当中的操作，每采取一次操作，就是一个step

state，是指agent在每个时刻所面临的状态

action，是指采取的那个操作究竟是什么

value，是指在这个时刻，我所能采取的各个动作，所具有的价值

用一个图来表示就是这样的

3 文绉绉的数学表示

在这个系统中，我们有一个状态集合S，行为集合A，策略pi，有了策略pi，我们就可以根据当前的状态，来选择下一刻的行为

$$a = \pi(s)$$

对于状态集合当中的每一个状态s，我们都有相应的回报值R(s)与之对应；对于状态序列中的每下一个状态，我们都设置一个衰减系数gamma

对于每一个策略pi,我们设置一个相应的权值函数

$$V^{\pi}(s_0)=E[R(s_0)+\gamma R(s_1)+ \gamma^2R(s_2)+\ldots|s_0=S,\pi]$$
这个表达式应该满足Bellman-Ford Equation，可以写成

$$V^{\pi}(s_0)=E[R(s_0)+\gamma V^{\pi}(s_1)]$$

4. 通俗的大白话

通俗的讲就是说，我需要判断一下当前的这个状态的价值是多少，从而让我可以选择最大化价值的那个状态来进行操作。当前状态的价值，就是之后的状态的价值的叠加，只不过越往后，噪声越大，就需要让他们的权重减小。而后面的所有状态的价值和，又可以写成下一个状态的价值。当前状态的reward我们是可以直接获得的，所以我们只需要计算下一个状态的权值函数就可以了，而这一点，我们通过神经网络来进行计算

2. 增强学习都有哪些策略

假设现在有这样一个场景。在一个游戏中我在某一个状态下有四种选择，可以向前后左右四个方向走。我需要知道往哪个方向走收益最大

1. 蒙特卡洛方法

简单而言，蒙特卡洛方法就是对这个策略所有可能的结果求平均。我们向前走了以后，再做一个action，根据这个式子，直到episode结束，求出收益的和，就是向前走这个动作的一个采样。我们再不断地在这个状态采样，然后来求平均。等到采样变得非常非常多的时候，我们的统计值就接近期望值了。所以蒙特卡洛方法是一个非常暴力，非常直观的方法。

2. 动态规划方法

这个其实就类似于我们在开篇的那个例子里面提到的。我们要确定向前走的这个动作的收益，那么就需要将它所有的子问题先全都计算完，然后取最大值，就是它的收益了。这个方法的好处就是效率高，遍历一遍就可以了；而缺点也很明显，需要子结构问题是一个有向无环图。要求

3. Temporal Difference（时间差分）

时间差分，简称TD，是对蒙特卡洛方法的一种简化，也是在实际中应用最多的一种算法

同样是要计算向前走的这个行为的价值的期望值，那么它就等于向前走了到达的那个状态的reward，加上它再转移到后继状态的期望值。有人会说这不就递归下去就是遍历了吗？不是，我们就观测前面一个状态，剩下的价值我们不去真的计算了，而是用神经网络来估算。这样我们不需要计算就可以得到它的价值了。这就是TD算法里面最简单的TD(0)算法

3. 用神经网络来对状态进行估算

对神经网络的简单介绍，可以戳这里

我们可以不了解神经网络具体是怎样工作的，我们只需要把它当成一个黑盒，输入是一个状态，输出是这个状态的价值。

有的同学可以比较疑惑，本来就没有训练数据，怎么进行训练呢

整个系统在运作过程中，通过现有的策略，产生了一些数据，获得的这些数据，在计算Reward值的时候会有所修正。然后我们用修正的值和状态，作为神经网络进行输入，再进行训练。最后的结果显示，这样做是可以收敛的，这就是这个算法最牛的地方！！

所以在加入了神经网络之后，各个部分之间的关系就变成了这样

4. 整个的算法流程

5. 参考资料

[1]http://blog.jobbole.com/71431/

[2]http://blog.csdn.net/songrotek/article/details/

[3]http://www.cnblogs.com/Leo_wl/p/5852010.html

[4]Mnih V, Kavukcuoglu K, Silver D, et al. Playing atari with deep reinforcement learning[J]. arXiv preprint arXiv:1312.5602, 2013.