大话增强学习第一篇。本系列以口语化形式，讲述理解增强学习。
机器学习的类别
机器学习基本可以分为这么三类。
- 监督学习或半监督学习
- 非监督学习
- 增强学习
前两者更倾向于环境感知，而增强学习更倾向于智能决策。今天我们就来学习一下增强学习，也称强化学习，Reinforcement Learning。
增强学习和监督学习的区别是，
- 监督学习就像‘体育老师教体育课’，老师告诉你该做什么动作。
- 增强学习就像‘数学老师给体育课代课’，老师也不知道应该做什么动作，但是老师会评价谁做得好，什么动作好，什么动作差。
增强学习的理论基础是马尔科夫过程。我们挨个介绍。
马尔科夫过程(Markov process)
说人话，意思就是我由
现在很穷变为未来很富的概率，和我过去很穷或很富没关系。
好了，说完了。
马尔科夫决策过程(Markov Decision Process)
MDP模型
马尔科夫决策过程呢，就是要考虑如何由现在很穷变为未来很富。总得做点什么，比如努力学习，买彩票等动作。为方便描述，我们定义几个变量
S状态集合: {s1:现在很穷，s2:未来很富}
A动作集合: {a1:努力学习，a2:买彩票，a3:撩妹}
我们一般假设(本假设不一定成立)s1 -> a1 -> s2的概率比s1 -> a2 -> s2的概率要高。于是，我们有了概率P(s’,s,a)即在s进行a到达s’的概率。本文中我们的P都是1，不是1的情况也很好处理，概率加权即可。
由于努力学习不一定比买彩票有效，但是坚持不懈的努力学习总体而言还是比买彩票要好，所以家长们会在你努力学习后立刻给个小奖励R。一般而言R(a1)>R(a2)，R(a1)>R(a3)。
于是我们有了S, A, P, R。
大体讲完了，这个就是马尔科夫决策过程的模型。
然而，有时候我们不知道P，或者R；甚至有时候S或A都太多了。于是马尔科夫决策过程（简称MDP）又分为
- 知道所有决策信息(S, A, P, R)
- 知道部分决策信息
- 只知道(S, A)
- 只知道部分S（比如AlphaGo下围棋时，S超级大）
MDP决策
前面讲了模型，这里讲决策。即，我现在这样了，下一步该怎么办呢？我们需要有个策略(Policy)来指导做下一步动作。
对于低等动物，虽然它们也有一定的智商，可以进行决策，但是它们考虑的不长远。如金鱼永远只有一个策略，即有吃的就吃，喂多了金鱼就自己吃死了。人就不会这样，因为人考虑的更长远。这里，金鱼在做吃还是不吃这个决策时，只考虑了当前的激励R，没有考虑长远。
而人呢，人会考虑很多步，比如天色尚早晚点吃，或者太晚了吃了要变胖要不健康。即人考虑的是长期激励，即现在决策的激励和未来可能决策的激励都加起来。
$$ R_{0} + R_{1} + R_{2} + \cdots $$
然而，这就有问题了。不管我如何决策，这个加起来的值可能都很大，那我该如何决策呢？于是，从直觉出发，我们改进一下策略，过于考虑长远的东西没意义。我们即不只考虑眼前的激励，也不把所有的未来都严格考虑进来。我们加权，权重系数r在[0,1)之间。0就是金鱼，1就是脑瘫，0.5看着就不错。
$$ R_{0} + rR_{1} + r^{2}R_{2} + \cdots $$
上面这个公式就是价值函数v(s)，即在当前s下，我采取最优策略一直下去，可以得到的总的奖励。
- 有时候我们知道大结局，即v(s)，但不知道各个R
- 有时候我们知道各个R进而可以计算出v(s)。
可以看出来v(s)和a没有关系，即v(s)衡量的是当前状态的好坏，有点像下棋下到某个局势时，我们说这个有利于哪一方。
说人话，就是v(
我现在很穷)肯定小于v(我现在很富)。
那如何做决策呢？我们得把a加进来。既然v(s)衡量了s的优劣，那结合R(s,a)，P(s,a,s’)是不是就可以和v(s’)扯上关系了呢？怎么搞呢？听好了，重点来了。
我们假设到了s’后继续使用最优策略，既假设我们已经知道了v(s’)。在s到s’这个过程，我们引入自变量a。于是R0本来表示按照最优策略选择的a，现在我们把R0变成以a为自变量的函数。
$$ R_{s,a} + rR_{1} + r^{2}R_{2} + \cdots $$
上式就是针对动作的价值函数q(s,a)。相当于描述了，在现在这盘棋上，我这么走的优劣。那么v(s)和q(s,a)有什么关系呢？想象一下，在s时，我穷尽了各种走法a，最后得到了最佳走法，则可以认为v(s)就是最佳走法时的q(s,a)。即v(s)=max(q(s,a))。而q(s,a)=R(s,a)+r(v(s’))，于是，q(s,a)=R(s,a) + r * max(q(s’,a‘)))。这么一推导，是不是很简洁？连Bellman方程都没碰就把结果给搞出来了。其实就是个动态规划啦，我们吃货公司员工入门必备。
$$ q(s,a) = R(s,a) + r*max(q(s{’},a{’})) $$
这个就是大名鼎鼎的Q-Learning算法(严格来讲，Q-learning是一类算法)的一部分。
通俗解释，就是在当前棋局s，我选择a进入下一个棋局s’的评分，是我获得的行动激励R(s,a)和状态s’评分之和。r系数权衡了短期激励和长期激励。
如何选择最佳a呢？到Q矩阵里面找到s行，选最大的那个q(s,a)所对应的a即可，即argmax q(s,a)。
如何迭代q(s,a)
如果我们知道了已有的q(s’,a’)和R(s,a)，自然我们就可以计算出q(s,a)。但是，这是个鸡生蛋的问题。我们如何更新q(s,a)呢？这个问题其实等价于问Q learning是什么？
$$ q_{latest} = (1-a)q_{old} + aq_{new} = q_{old} + a(q_{new} - q_{old}) $$
很通俗地解释一下，相当于以前有个old的值，现在又发现了个new的值，该用哪一个呢？只用新的，相当于彻底放弃已有经验。只用老的，相当于不更新。各取一半，相当于取个平均。那就老规矩，加个权重，引入了权重a，得到了更新公式。a也被称为学习速率。
小结
总结一下，这个思想就是根据R(s,a)来迭代计算q(s,a），进而得到策略(argmax q)和v(s)。这是一种value function based algorithm。
增强学习是一类高级算法，人生也是如此。我们不能只看短期利益，需要权衡长期利益，从而变成人生大赢家。有些人蠢，就是不意识到长期利益的重要性。比如，有些人找工作时一看这个工作给的工资多，就去干了。另一些人还会考虑我干了这个工作以后会如何发展。这就是潜移默化地使用了增强学习做决策。
本文我们介绍了增强学习最重要的两个公式。
$$ q(s,a) = R(s,a) + r*max(q(s{’},a{’})) $$
$$ q_{latest} = (1-a)q_{old} + aq_{new} = q_{old} + a(q_{new} - q_{old}) $$
根据这个公式，机器人(Agent)不停的以一定策略探索环境，得到反馈，进而改进策略。这就是增强学习的基本思想，增强学习是一大类算法。
可如果我们不知道R(s,a)，该怎么办呢？请关注我的后续文章。
参考文献
David Silver目前（2017）是Google员工（严格来讲，是AlphaBet旗下DeepMind员工）。David Silver早年搞了个游戏公司做CTO，后来公司黄了，他去读了个RL方面的博士并任教一段时间。后来加入了DeepMind，再后来被Google收购了。他的教学资料很严谨易懂。