《机器学习》笔记-强化学习（16）

刘才权

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

• 任务与奖赏
• K-摇臂赌博机
• 有模型学习
• 免模型学习
• 值函数近似
• 模仿学习

（一）任务与奖赏

以种西瓜为例。种瓜有许多步骤，从一开始的选种，到定期浇水、施肥、除草、杀虫，经过一段时间才能收获西瓜。通常要等到收获后，我们才知道种出的瓜好不好。若将得到好瓜作为辛勤种瓜劳动奖赏，则在种瓜过程中，当我们执行某个操作（例如，施肥）时，并不能立即获得这个最终奖励，甚至难以判断当前操作对最终奖赏的影响，仅能得到一个当前反馈（例如，瓜苗看起来更健壮了）。我们需多次种瓜，在种瓜过程中不断摸索，然后才能总结出比较好的种瓜策略。这个过程抽象出来，就是“强化学习”（Reinforcement Learning）。
下图给出了强化学习的一个简单图示，

强化学习任务通常用马尔科夫决策过程（Markov Decision Process，简称MDP）来描述：
* 机器处于环境E中；
* 状态空间为X，其中，每个状态x∈X是机器感知环境的描述，如在种瓜任务上，这就是当前瓜苗长势的描述；
* 机器能采取的动作构成动作空间A，如种瓜过程中有浇水、施不同的肥、使用不同农药等多种可供选择的动作；
* 若某个动作a∈A作用在当前状态x上，则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态，如瓜苗状态为缺水，若选择动作为浇水，则瓜苗长势会发生变化，瓜苗有一定概率恢复健康，也有一定概率无法恢复；
* 在转移到另一个状态的同时，环境会根据潜在的“奖赏”（reward）函数R反馈给机器一个奖赏。
综合起来，强化学习任务对应了四元组E=。下图给出了一个简单的例子，

需要注意“机器”与“环境”的界限，例如，在种西瓜任务中，环境是西瓜生长的自然世界；在下棋对弈中，环境是棋盘与对手；在机器人控制中，环境是机器人的躯体与物理世界。总之，在环境中的状态的转移、奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。
机器要做的是通过在环境中不断的尝试而学得一个“策略”（policy）π，根据这个策略，在状态x下就能得知要执行的动作a=π(x)，例如看到瓜苗状态是缺水时，能返回动作“浇水”。
策略有两种表示方法：
* 一种是将策略表示为函数π：X->A，确定性策略常用这种表示；
* 另一种是概率表示π：XxA->R，随机性策略常用这种表示，π(x, a)为状态x下选择动作a的概率，这里必须有∑π（x，a）=1；

策略的优劣取决于长期执行这一策略后得到的累积奖赏，例如某个策略使得瓜苗枯死，它的累积奖赏会很小，另一个策略种出了好瓜，他的累积奖赏会很大。在强化学习任务中，学习的目标是要找到能使长期累积奖赏最大化的策略。
大家也许已经感觉到强化学习与监督学习的差别。若将这里的“状态”对应为监督学习中的“示例”、“动作”对应“标记”，则可看出，强化学习中的“策略”实际上就相当于监督学习中的“分类器”（当动作是离散的）或“回归器”（当动作是连续的），模型的形式并无差别。但不同的是，在强化学习中并没有监督学习中的有标记样本（即“示例-标记”对），换言之，没有人直接告诉机器在什么状态下该做什么动作，只有等到最终结果揭晓，才能通过“反思”之前的动作是否正确来进行学习。因此，强化学习在某种意义上可看做具有“延迟标记信息”的监督学习问题。

（二）K-摇臂赌博机

与一般监督学习不同，强化学习任务的最终奖赏是在多步动作之后才能观察到，这里我们不妨先考虑比较简单的情形：最大化单步奖赏，即仅考虑一步操作。需要注意的是，即便在这样的简化情形下，强化学习仍与监督学习有明显不同，因为机器需要通过尝试来发现各个动作产生的结果，而没有训练数据告诉机器应该做哪个动作。
欲最大化单步奖赏需考虑两个方面，
* 一是需要知道每个动作带来的奖赏；
* 二是要执行奖赏最大的动作；

若每个动作对应的奖赏是一个确定值，那么尝试一遍所有的动作便能找出奖赏最大的动作。然而，更一般的情形是，一个动作的奖赏来自于一个概率分布，仅通过一次尝试并不能确切的获得平均奖赏。
实际上，单步强化学习任务对应了一个理论模型，即“K-摇臂赌博机”（K-armed bandit），如下图所示，

K-摇臂赌博机有K个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。
* 若仅为获知每个摇臂的期望奖赏，则可采用“仅探索”（exploration-only）法：将所有尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计；
* 若仅为执行奖赏最大的动作，则可采用“仅利用”（exploitation-only）法：按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。

显然，“仅探索”法能很好的估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会；“仅利用”法则相反，它没有很好的估计摇臂期望奖赏，很可能经常选不到最优摇臂。因此，这两种方法都难以使最终的累计奖赏最大化。
事实上，“探索”（即估计摇臂的优劣）和“利用”（即选择当前最优摇臂）是矛盾的，因为尝试次数（即总投币数）有限，加强了一方面则会削弱另一方，这就是强化学习所面临的“探索-利用窘境”（Exploration-Exploitation dilemma）。显然，欲累计奖赏最大，则必须在探索与利用之间达成较好的折中。

ε -贪心

ε -贪心基于一个概率来对探索和利用进行折中。

Softmax

Softmax算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。

（三）有模型学习

考虑多步强化学习任务，暂且先假定任务对应的马尔科夫决策过程四元组E=均为已知，这种情形称为“模型已知”，即机器已对环境进行了建模，能在机器内部模拟出与环境相同或相近的情况。在已知模型的环境中学习称为“有模型学习”（model-based Learning）。

（四）免模型学习

在现实的强化学习任务中，环境的转移概率、奖励函数往往很难得知，甚至很难知道环境中一共有多少状态。若学习算法不依赖于环境建模，则称为“免模型学习”（model-free learning），这比有模型学习要困难得多。

（五）值函数近似

前面我们一直假定强化学习任务是在有限状态空间上进行，每个状态可用一个编号来指代。然而，现实强化学习任务所面临的状态空间往往是连续的，有无穷多个状态。这该怎么办呢？
一个直接的想法是对状态空间进行离散化，将连续状态空间转化为有限离散状态空间，然后就能使用前面介绍的方法求解。遗憾的是，如何有效的对状态空间进行离散化是一个难题，尤其是在对状态空间进行搜索之前。
实际上，我们不妨直接对连续状态空间的值函数进行学习。

（六）模仿学习

在强化学习的经典任务设置中，机器所能获得的反馈信息仅有多步决策后的累积奖赏，但现实任务中，往往能得到人类专家的决策过程范例。例如在种瓜任务上得到农业专家的种植过程范例。从这样的范例中学习，称为“模仿学习”（imitation learning）。