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

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

可以用增强学习领域里一些常用的名词来非严格地定义它：一个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

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