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

就像做通信的都绕不过信息论，要研究增强学习也跑不掉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

关于作者

阿稳, 豆瓣, 算法工程师

推荐系统；数据挖掘；算法架构及实现的可扩展性；R环境编程

如果你的问题已经能从我的博客中得到解答，就最好不过了：http://www.wentrue.net/blog/

SlideShare 豆瓣 新浪微博 Twitter LinkedIn