就像做通信的都绕不过信息论，要研究增强学习也跑不掉MDP。

增强学习的基础理论：马尔科夫决策过程（MDP）

通过MDP可以符号化地定义一个多状态带时延反馈的增强学习过程。一个MDP包括一个状态集合S，一个操作集合A，一个反馈函数R：S×A->R，以及一个状态迁移概率函数T(s,a,s’): S×A->S。可以结合前文的图1里来理解这里符号的意义。

这个模型的求解很简单，要输出的最优策略其实是一个状态到操作的映射函数S->A，即在什么状态下应采用什么操作是确定的（根据短时平稳性假设，至少是短时确定的）。为得到这样的策略，我们首先需要定义在状态s时不同操作所能获得的期望收益，并把这个收益最大化。以下公式即定义了这个期望最大的收益（这里使用的是无限视野带衰减的目标函数）：

获得这个最大收益时所采取的策略：

这两个迭代式，在T和R都已知的情况下，可以通过初始化，然后迭代计算使得结果收敛，过程跟pagerank的计算差不多。而根据是对V*进行迭代还是对进行迭代又产生了值迭代和策略迭代两种算法。性能上稍有不同，结果是一致的。值迭代又可以演化出增强学习的代表性算法Q-learning。

MDP是一个很理想化的模型，它假设了我们事先对环境的完全了解（转移概率函数T及反馈函数R），而增强学习要解决的问题恰恰是对环境信息的未知。虽然MDP模型并不具有现实可用的意义，但通过它我们定义了一整套的符号系统以及问题解决的途径，极大地简化了对问题的描述与求解。在理论上解决了一些抽象层面的问题后（如收敛性、计算复杂度），要把它推广到现实的应用，只要着眼于解决对T及R函数的估计或替代即可。那些看似没有实用价值的数学模型的意义就在于此。

一般情况下MDP的求解

在现实应用中，MDP的环境模型（T及R函数）的参数是未知的，所以增强学习的过程可以化归为一个参数估计问题，只要能通过逐步得到的数据迭代地修正模型参数或算法参数，就可以直接利用通过MDP推导得到的结果。要实现这个目的，也有两种方式：model-based（学习模型的参数并把估计得到的模型应用于策略输出）和model-free（不断根据数据输入调整策略的输出，而无需估计具体的模型）的。两种实现方式各有千秋，一般来说model-free的方法需要更多的迭代步数才能收敛，但需要更少的环境知识，而model-based的方法则正好相反。由于这里主要是概念性的描述，欲求更多细节与方法实现的，可参看文后的文献。

增强学习潜在的应用场景

由于增强学习解决的是一类问题，所以它在自适应控制、机器人控制、博弈等等领域都有广泛的应用。从增强学习与有监督学习的对比可以看到，增强学习特别适用于那些没有启动数据的环境。搞推荐系统的朋友，这个时候你是不是瞬间就想到了冷启动问题。

博弈论的情景

以我粗浅的理解，可以把博弈论所讨论的问题理解为群体式的增强学习。每一个agent都与其它agent交互，并把对方的反馈视为环境的输入，agent必须学习在这个环境里最优的生存法则。比增强学习更为复杂的是，这个时候的环境是非稳定的，你在调整策略的同时，其它agent也在调整着自身的策略。一个著名的例子是囚徒困境的实验，多位社会精英为自己的agent设计出理想的增强学习型算法，但最后获胜的却是最简单的策略：以牙还牙。个中的奥妙颇是耐人寻味，在multi-agent博弈的环境里，非线性的因素是不可建模亦不可被预测到的，回归到最基本的策略往往能得到出人意表的效果，虽然它缺乏学习（实际也可能是群体学习筛选的结果），它却也省去了过拟合的烦恼。延伸来说，如果你不能掌控一个系统的复杂性，用启发式的策略做一些力所能及的事情，比你搭建一个同样复杂的系统试图去理解它是更为合理的。

结文

到此，增强学习的基本概念与模型算是摆在面前了，应该不会有下文了，将来如果有，也会结合着我自己的实践体会来写。虽说只是一个缩略版，这些模式对于实际要做的事情也没有直接的帮助，但我们需要这样的对问题建构的范式，以设计出符合自己系统需要的模型来。

参考文献：

【1】Reinforcement learning: A survey;  Kaelbling, L.P. and Littman, M.L. and Moore, A.W.; Arxiv preprint cs/9605103; 1996

增强学习同时是一个心理学及机器学习的概念。我们很多知识的习得都是通过增强学习的机制完成的，其最基本的形态无异于你训练小狗帮你捡回扔出的网球时所采取的形式。正如很多机器学习理论都从生物认知系统或群体系统中获得启发一样，增强学习也从中汲取了营养并发展成一个独立的分支。但是跟其它机器学习领域不一样的地方在于，它更多的是一类问题（而非一些技术）的集合。

可以用增强学习领域里一些常用的名词来非严格地定义它：一个agent，处于一个变化的环境中，通过试错与环境发生交互，慢慢适应环境并使得自己从环境获得的收益最大化的过程。

基本模型

描绘这个定义最贴切的图如下：

图1

图1描述的是一个agent与环境发生交互的过程：agent通过感知函数I和R来获得环境的输入，并依此从自己的行为集合B中选择操作a反馈给环境；环境依据当前的状态s与操作a，通过一个状态转移函数T(s,a,s’)跃迁到一个新的状态s’。至此完成了一步迭代。通过一步又一步的迭代，agent会慢慢学习到环境的分布或规则，从而得到一个策略——对于每种状态，都能给出收益最优的操作。是不是很像某些AI视频里小机器人在一个陌生环境里通过行走学习找到正确路径的场景。这里之所以存在一个输入函数I，而不是直接获取环境输入，是因为在某些场景里，agent对环境信息的输入感知是不充分的，如局部的、带噪音之类的，不过这里的讨论中I会是一个无差的函数。R是收益函数，简单的情景下它输出为：有（1）或无（0）。

基本假设

这个模型有两个基本的假设：1、环境是非确定性的，即状态转移函数T输出的是一个概率值，S×A->S是一种概率映射；2、环境是平稳的（状态转移函数T的输出概率分布是稳定的），或至少是短时平稳或变化缓慢的。

增强学习 vs. 有监督学习

增强学习面临的问题跟有监督学习不一样，它没有一批预先准备好的input/output数据集可供学习，它考虑的是在一个全新的、几乎没有什么信息可供参考的环境里，如何通过试错的方式来获得环境反馈的学习。因为没有离线的数据可作依据，所以，在线的实时的评估对于增强学习而言是极其重要的，这是一类一边学习一边评估的系统。

问题的求解

对于这个基本模型下的学习问题，即如何给出收益最大的行为输出，有两种求解的途径，一是通过遗传算法、遗传规划或其它搜索策略在求解空间中搜索问题的局部最优解；二是使用统计或动态规划的方法去估计在不同状态下采用不同操作所能获得的期望收益，并由此直接或间接的得到统计最优的行为输出。

优化目标

增强学习最终输出的是一个最优的行为策略，所以归根到底还是个优化问题，优化的目标函数通常有如下三种：

左式是一种有限视野的优化，它只考虑最近h步的收益期望，这个比较符合人做判断的方式，比如下象棋时的走一想三就是考虑了后续几步收益所给出的最优走法。中式应用比较广泛，是一种带衰减的无穷视野收益期望，无限的情况存在于理论的世界里，离当前时间点越远其重要性越低的假设既符合主观认识又能保证数学上的收敛，所以用于做理论推导是很合适的。右式是无穷视野的另一个版本。选择不同的优化目标函数能得到完全不同的行为策略。

Exploration vs. Exploitation

在Reinforcement Learning这个范畴里讨论学习问题通常都绕不开这个tradeoff问题，通俗地说这等同于每朝的太祖都会面临的问题：稳守江山还是开疆辟土。用一个k-arm bandit可以很形象的说明这个问题的普遍性。所谓1-arm bandit即我们常说的老虎机（水果机、赌博机），投一个硬币，按一下按钮或扳一下手柄，根据机器滚动组合的三个图案来决定你获得奖励或两手空空。k-arm bandit就是这次你面临k台老虎机，并且它们获奖的概率是不一样的，至于概率是多少，就需要你自己去试了。我们简化一下问题，假设你不用投硬币，但你只有n次玩的机会，每次玩你会获得1或0个奖励，那么为了你的收益最大化，你应该采用什么样的策略？

策略分析

直观的说，如果你已经预先知道了各台机器的获奖概率，你应该完全采用Exploitation式的策略，集中投注于概率最大的那台机器。在你完全没有一点关于概率的信息时，你应该先采用Exploration的方式去对各台机器做探索性的测试，以期获得足够的信息让你化归到最简单的Exploitation式策略。从算法的角度上去求解这个问题，通常有两种途径，一种是规范化的方法，把一些成熟的模型引入进来解决问题，如动态规划，学习自动机。另一种是特定性的方法，它们多是一些启发式的算法，如贪心算法，波尔兹曼搜索等等。

其实，k-arm bandit同时还是符合RL模型的最简单的形态：单状态的RL模型——你永远都只会面临同一种状态，以及k种操作的行为集，并且环境是稳定但非确定的。这个简单的模型在很多的机器学习和应用数学的领域都有讨论。

参考文献：

【1】Reinforcement learning: A survey;  Kaelbling, L.P. and Littman, M.L. and Moore, A.W.; Arxiv preprint cs/9605103; 1996

概念化“增强学习”（二）