机器学习笔记(十六)强化学习

 

16.强化学习

16.1任务与奖赏

强化学习（reinforcementlearning）的过程就是机器通过一系列的动作和环境交互，从而得到最佳的动作序列。图示：

强化学习任务用马尔可夫决策（Markov Decision Process，MDP）描述：机器处于环境E中，状态空间为X，其中每个状态x∈X是机器感知到的环境的描述；机器能采取的动作构成了动作空间A，若某个动作a∈A作用在当前状态x上，则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态；在转移到另一个状态的同时，环境会根据潜在的奖赏（reward）函数R反馈给机器一个奖赏。综合起来，强化学习任务对应了一个四元组E=<X,A,P,R>，其中P：X*A*X->R指定了状态转移概率；R:X*A*X->R指定了奖赏；在有的应用中，奖赏函数可能仅与状态转移有关，即R:X*X->R。

按照上面的形式化描述，就是给定状态转移概率P和奖赏R，机器通过动作空间A感知环境返回的状态空间X。文中给的西瓜例子可以配合理解。机器指的是学习程序，而环境则面对不同任务是不同，如在下棋对弈中，环境是棋盘与对手；在种西瓜任务中，环境是西瓜生长的自然世界。在环境中状态的转移、奖赏的返回时不受机器（程序）控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。

机器人下棋就是强化学习的表现。若将强化学习中的状态对应于监督学习中的示例，而动作对应于标记，则可看出，强化学习中的策略相当于监督学习中的分类器（当动作是离散的）或回归器（当动作是连续的），模型的形式并无差别。不同的是，在强化学习中并没有监督学习中的有标记样本（即示例-标记对），换言之，没有人直接告诉机器在什么状态下应该做什么动作，只有等到最终结果揭晓，才能通过反思之前的动作是否正确来进行学习。因此，强化学习在某种意义上可以看作具有延迟标记信息的监督学习问题。

实际上，个人感觉学习就是一个感知过程，监督学习有标记和强化学习根据最终结论来感知动作是否合适是一样的。

 

16.2K-摇臂**机

与一般监督学习不同，强化学习任务的最终奖赏要在多步动作之后才能观察到，那能否最大化单步奖赏，即仅考虑一步操作。当然即使是这个特例，强化学习和监督学习还是不同的，因为机器要通过尝试来发现各个动作产生的结果，而没有训练数据告诉机器应当做那个动作。一个是事前知道做什么动作，一个是事后才知道这个动作有什么后果。

要最大化单步奖赏需考虑两个方面：一是需知道每个动作带来的奖赏；二是要执行奖赏最大的动作。如果每个动作对应的奖赏是一个确定值，那么尝试所有的动作后就能找到奖赏最大的动作。不过，一般情况下，一个动作的奖赏是来自于一个概率分布，仅通过一次尝试并不能确切地获得平均奖赏值。看到这里，是不是有买**的熟悉感觉，每一次的**都存在一个概率分布，并不确定知道这次**的动作能带来什么回报。实际上，这种单步强化学习任务正是对应了一个理论模型，即K-摇臂**机（K-armed bandit）。K-摇臂**机有K个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币；当然，这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

若仅为获知每个摇臂的期望奖赏，则可采用仅探索（exploration-only）法：将所有的尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。若仅为执行奖赏最大的动作，则可采用仅利用（exploitation-only）法：按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。仅探索法能很好估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会；仅利用法则相反，它没有很好地估计摇臂期望奖赏，很可能经常选不到最优摇臂。因此，这两种方法都难以使最终的累积奖赏最大化。

事实上，探索（即估计摇臂的优劣）和利用（即选择当前最优摇臂）二者是矛盾的，因为尝试次数（即总投币数）有限，加强了一方则会自然削弱另一方，这就是强化学习所面临的探索-利用困境（Exploration-Exploitation dilemma）。显然，要使累积奖赏最大，则必须在探索和利用之间的达成较好的折中。探索每次的动作是平均选择一个摇臂，而利用则是选择历史积累最优的摇臂。下面两种方法是对探索和利用折中的方法。

对于离散状态空间、离散动作空间上的多步强化学习任务，一种直接的办法是将每个状态上动作的选择看作一个K-摇臂**机问题，用强化学习任务的累积奖赏来代替K-摇臂**机算法中的奖赏函数，即可将**机算法用于每个状态（一个状态相当于一个**机，每个状态上的动作相当于摇臂）：对每个状态分别记录各动作的尝试次数、当前平均累积奖赏等信息，基于**机算法选择要尝试的动作。不过这种方法没有考虑强化学习任务马尔可夫决策过程的结构。有效考虑马尔可夫决策过程的特性，方法将更好，如下节的有模型学习。

 

16.3有模型学习

就多步强化学习任务，如果假定任务对应的马尔可夫决策过程四元组E=<X,A,P,R>均为已知，则成为模型已知，即机器对已知环境进行了建模，能在机器内部模拟出与环境相同或近似的状况。在已知模型的环境中学习成为有模型学习（model-based learning）。用数学定义来说，对任意状态x*，x和动作a，在x状态下执行动作a转移到x*状态的概率P是已知的，该转移所带来的奖赏R也是已知的。还要加一个假设，状态空间X和动作空间A均为有限的。在有效的状态空间和动作空间下，转移概率和奖赏函数已知的情况下，就是有模型学习。

从算法可可看出，在模型已知时强化学习任务能归结为基于动态规划的寻优问题。与监督学习不同，这里不涉及泛化能力，而是为每一个状态找到最好的动作。

16.4免模型学习

在现实环境中，环境的转移概率、奖赏函数往往是未知的，甚至很难知道环境中一共有多少状态。若学习算法不依赖于环境剑魔，则成为免模型学习（model-free learning），比有模型学习困难。

1）蒙特卡罗强化学习

在免模型情形下，策略迭代算法首先遇到的问题是策略无法评估，这是由于模型未知而导致无法做全概率展开。此时，只能通过在环境中执行选择的动作，来观察转移的状态和得到的奖赏。受K摇臂**机的启发，一种直接的策略评估替代方式是多次采样，然后求取平均累积奖赏来作为期望累积奖赏的近似，这称为蒙特卡罗强化学习。由于采样必须为有限次数，因此该方法更适合于T步累积奖赏的强化学习任务。

另一方面，策略迭代算法估计的是状态值函数V，而最终的策略是通过状态-动作值函数Q来获得。当模型已知时，从V到Q是很简单的转换方法，而当模型未知时，这会出现困难。于是，将估计对象从V转变为Q，即估计每一对状态-动作的值函数。

此外，在模型未知的情形下，机器只能是从一个起始状态（或起始状态集合）开始探索环境，而策略迭代算法由于需对每个状态分别进行估计，因此在这种情形下是无法实现。综合起来，在模型未知的情形下，从起始状态出发，使用某种策略进行采样，执行该策略T步并获得轨迹：

2）时序差分学习

蒙特卡罗强化学习算法通过考虑采样轨迹，克服了模型未知给策略估计造成的困难。此类算法需在完成一个采样轨迹后再更新策略的值估计，而前面介绍的基于动态规划的策略迭代和值迭代算法在每执行一步策略后就进行值函数更新。两者相比，蒙特卡罗强化学习算法的效率低很多，这里主要问题是蒙特卡罗强化学习算法没有充分利用强化学习任务的MDP结构。时序差分（Temporal Difference，TD）学习则结合了动态规划与蒙特卡罗方法的思想，能做到更高效的免模型学习。

 

16.5值函数近似

上文强化学习任务是假定在有限状态空间上进行，每个状态可用给一个编号来指代；值函数则是关于有限状态的表格值函数（tabular value function），即值函数能表示为一个数组，输入i对应的函数值就是数组元素i的值，且更改一个状态上的值不会影响其他状态上的值。然而，现实强化学习任务所面临的状态空间往往是连续的，有无穷多个状态，这该怎么办？

一个直接的想法是对状态空间进行离散化，将连续状态空间转化为有限离散状态空间，然后就能使用前面介绍的方法求解。不过，如何有效地对状态空间进行离散化是一个难题，尤其是在对状态空间进行探索之前。

 

16.6模仿学习

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

本章总结，强化学习分类：第一层按照有无专家范例（或者监督学习和无监督学习）分类，可分为模仿学习（有直接模仿学习，逆强化学习）这样的监督性学习；无监督学习则可按照有限状态和无限状态做第二层分类，无限状态是值函数近似；有限状态按照单步和多步可做第三层分类，单步强化学习（K摇臂**机）和多步强化学习；多步强化学习根据是否模型已知可做第四层分类，有模型学习和无模型学习。无模型学习包括蒙特卡罗方法和时序差分方法。