分层强化学习

分层强化学习是强化学习领域中的一个分支。传统强化学习通过与环境的交互,进行试错(trial-and-error),从而不断优化策略(policy)。但是强化学习的一个重要不足就是维数灾难 (curse of dimensionality),当系统状态(state)的维度增加时,需要训练的参数数量会随之进行指数增长,这会消耗大量的计算和存储资源。 分层强化学习将复杂问题分解成若干子问题(sub-problem),通过分而治之(divide and conquer)的方法,逐个解决子问题从而最终解决一个复杂问题。这里的子问题分解有两种方法:①所有的子问题都是共同解决被分解的任务(share tasks);②不断把前一个子问题的结果加入到下一个子问题解决方案中(reuse tasks)。分层强化学习核心思想是通过算法结构设计对策略(policy)和价值函数(value function)施加各种限制(constraints),或者使用本身就可以开发这种限制的算法。

简介

分层强化学习是强化学习领域中的一个分支。传统强化学习通过与环境的交互,进行试错(trial-and-error),从而不断优化策略(policy)。但是强化学习的一个重要不足就是维数灾难 (curse of dimensionality),当系统状态(state)的维度增加时,需要训练的参数数量会随之进行指数增长,这会消耗大量的计算和存储资源。

分层强化学习将复杂问题分解成若干子问题(sub-problem),通过分而治之(divide and conquer)的方法,逐个解决子问题从而最终解决一个复杂问题。这里的子问题分解有两种方法:①所有的子问题都是共同解决被分解的任务(share tasks);②不断把前一个子问题的结果加入到下一个子问题解决方案中(reuse tasks)。分层强化学习核心思想是通过算法结构设计对策略(policy)和价值函数(value function)施加各种限制(constraints),或者使用本身就可以开发这种限制的算法。

常见的分层强化学习方法可以分成以下3类:①基于选项(options)的学习,②基于分层局部策略(hierarchical partial policy)的学习,③基于子任务(sub-task)的学习。接下来对这三类算法作简要介绍。

第一类,基于选项(Options)的分层强化学习:

选项是一个由三个元素构成的元组<I, π, β>。其中 π:S × A → [0, 1] 代表策略, 是一个基于状态空间(State space)和动作空间(Action space)的概率分布函数; β:S → [0, 1] 是终止条件,β(s)表示状态 s 有β(s)的概率终止并退出当前option;I ⊆ S 表示option的初始状态。

一个基于option的学习过程如下:agent首先初始化在某一状态,然后其选择某一option,然后按照这一option的策略π选择一个动作或者其他option,然后执行动作或者进入新的option,继续循环选择或者终止。

对于每一个状态s,可用的option用O(s)来表示,μ(s,o) 表示在状态s下,进入选项o的概率。基于选项的Q-learning更新方程如下:

第二类,基于分层局部策略(hierarchical partial policy)的学习:

这一类方法以分层抽象机 (Hierarchical abstract machines, HAMs)为代表,其核心思想是用抽象机对可以采取的策略进行限制。

HAMs拥有有限个抽象机的集合H,每个 h⊆H 都是一个HAM抽象机,它包括以下3部分:抽象机状态(states),状态转移方程(transition functions),初始化方程(start function)。

一个抽象机的状态空间S有4种不同的状态,分别是动作 (action), 调用 (call), 选择 (choice)和终止 (stop)。初始化方程,顾名思义,决定了抽象机的初始状态。当抽象机在action和call状态下时,状态转移方程决定抽象机的下一个状态,并获得相应奖励(reward)。

在一个HAM的状态空间中,Action意味着执行某一动作,Call的作用是选择下一个抽象机,Choice则是非确定性地选择抽象机的下一个状态,Stop则是终止当前抽象机,并恢复到调用前的抽象机。作为参考,此时HAM Q-learning的更新方程就变成了:

这里的Q值是它的扩展形式,Q([s,m], a)表示了在以下条件下的Q值:环境状态 s ,抽样机状态 m,以及当m是choice时所执行的动作a。下标 c 表示选择点(Choice point)。

第三类,基于子任务(sub-task)的学习:

基于子任务的学习以MAXQ价值函数分解(MAXQ value function decomposition)方法为代表。它由Dietterich在2000年提出。这种方法的思想是将一个马可夫决策过程 M 分解成多个子任务,解决了每个子任务也就解决了原本的复杂问题。每个子任务都有终止状态(terminal state) T, 子动作空间A。子任务的目标就是从某一初始状态不断执行动作,进入新状态,直至终止。

[描述来源:Barto, A. G., & Mahadevan, S. (2003). Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 13(4), 341-379.

URL: https://link.springer.com/article/10.1023/A:1025696116075

描述来源:Driessens, K., Fern, A., & van Otterlo, M. (2005). Proceedings of the ICML'05 Workshop on Rich Representations for Reinforcement Learning. Bonn, Germany: University of Bonn.

URL:https://research.utwente.nl/en/publications/proceedings-of-the-icml05-workshop-on-rich-representations-for-re

描述来源:Sutton, R. S., Precup, D., & Singh, S. (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2), 181-211.

URL: http://www-anw.cs.umass.edu/~barto/courses/cs687/Sutton-Precup-Singh-AIJ99.pdf

描述来源:Parr, R., & Russell, S. J. (1998). Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems (pp. 1043-1049).

URL: https://papers.nips.cc/paper/1384-reinforcement-learning-with-hierarchies-of-machines

描述来源:Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. J. Artif. Intell. Res.(JAIR), 13, 227-303.

URL: http://www.jair.org/papers/paper639.html]

发展历史

1998年Parr和Russel提出了分层抽象机 (Hierarchical abstract machines, HAMs)的概念,它通过额外增加分层抽象机的状态空间对策略(policy)施加限制,巧妙地回避了传统强化学习的维度灾难问题,让当时的人们看到了强化学习算法在大规模问题下应用的可能性。紧接着第二年,Sutton等人提出基于选项(Options)的学习,这种方法在半马可夫决策过程(semi-markov decision process)的基础上利用新引入的选项概念,设法将复杂问题下庞大的状态空间(state space)和动作空间(action space)分割从而简化问题。2000年,Dietterich提出了MAXQ价值函数分解。这种方法的思想是将一个马可夫决策过程 M 分解成多个子任务,解决了每个子任务也就解决了原本的复杂问题。基于子任务分解的方法结构清晰,便于实现,目前已经成为分层强化学习领域最重要的基础算法之一。近年来,随着计算机计算能力的飞跃,深度学习在很多领域的应用取得了突破性进展。越来越多的学者尝试将分层强化学习和神经网络结合在一起,充分利用两者的优点,设计电子游戏的AI角色,谷歌Deep Mind团队也在2017年推出了基于游戏《星际争霸2》的SC2LE开发平台,相信未来在这一领域会有更多令人振奋的消息。

主要事件

年份事件相关论文
1998Parr和Russell提出了分层抽象机 (Hierarchical abstract machines, HAMs)。该方法用抽象机对可以采取的策略进行限制,从而简化问题。Parr, R., & Russell, S. J. (1998). Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems (pp. 1043-1049).
1999Sutton等人提出基于选项(Options)的分层强化学习Sutton, R. S., Precup, D., & Singh, S. (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2), 181-211.
2000Dietterich提出MAXQ价值函数分解方法,该方法通过分解子问题求解复杂问题Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. J. Artif. Intell. Res.(JAIR), 13, 227-303.
2013Ghafoorian等人提出利用蚁群算法启发式地寻找瓶颈(bottle neck)Ghafoorian, M., Taghizadeh, N., & Beigy, H. (2013, March). Automatic Abstraction in Reinforcement Learning Using Ant System Algorithm. In AAAI Spring Symposium: Lifelong Machine Learning.
2016Kulkarni等人提出构建两个层级的神经网络,顶层用于决策,底层用于执行实现Kulkarni, T. D., Narasimhan, K., Saeedi, A., & Tenenbaum, J. (2016). Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Advances in Neural Information Processing Systems (pp. 3675-3683).
2017Bacon等人提出利用神经网络训练寻找option之间的界限Bacon, P. L., Harb, J., & Precup, D. (2017). The Option-Critic Architecture. In AAAI (pp. 1726-1734).
2017Vezhnevets等人提出的Feudal networks使得决策的目标可以通过算法学习得到Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., & Kavukcuoglu, K. (2017). Feudal networks for hierarchical reinforcement learning. arXiv preprint arXiv:1703.01161.

发展分析

分层强化学习算是强化学习中最前沿的领域之一了。我们已经能够从一些应用中看到这种算法在大规模强化学习领域的潜在能力,比如Robocup, 足球机器人的移动、定位;还比如说游戏《蒙特祖玛的复仇》(Montezuma’s Revenge),传统强化学习在这款游戏的表现不尽如人意, 但是依靠分层强化学习,通过分层抽象,可以达到很好的效果。然而分层强化学习并没有深度学习那样级别的广泛应用,而且在理论层面,还有许多内容需要突破,比如将分层学习和神经网络的结合。

瓶颈

-分层抽象有时还需要人为设定目标才能达到好的结果,还不够智能

未来发展方向

英伟达刚刚在2017年12月发布了TITAN V显卡,浮点性能是上一代产品的9倍;量子计算机的研究也在步步进行。计算机硬件的飞速发展可能会将分层强化学习、深度学习带入一个全新的阶段,还记得2012年Alex让世界重新认识了深度学习。未来搭配速度更快的,甚至是量子计算机,也许真的会重新刷新我们对这个领域的认识,也许那一天就是真正的通用人工智能的到来。

Contributor: Keyu Qi

相关人物
理查德S.萨顿
理查德S.萨顿
Richard S. Sutton 教授博士毕业于马萨诸塞大学安姆斯特分校,现任阿尔伯塔大学计算机科学教授。Sutton 教授被认为是现代计算的强化学习创立者之一。他为该领域做出了许多重大贡献,包括:时间差分学习(temporal difference learning)、策略梯度方法(policy gradient methods)、Dyna 架构
斯图尔特·J·拉塞尔
斯图尔特·J·拉塞尔
Alexander Sasha Vezhnevets
Alexander Sasha Vezhnevets
托马斯 ·G· 迪特里克
托马斯 ·G· 迪特里克
Thomas G. Dietterich 是俄勒冈州立大学计算机科学荣誉教授。他是机器学习领域的创始人之一。他曾担任机器学习的执行编辑,并帮助共同创建了机器学习研究期刊。为了回应媒体对人工智能危害的关注,Dietterich 已被引用到广泛的媒体渠道,包括国家公共广播电台,商业内幕,微软研究院,CNET 和华尔街日报。
戴维·西尔弗
戴维·西尔弗
DeepMind 首席研究员,强化学习组负责人,领导了包括 AlphaGo、AlphaZero、能够玩 Atari 游戏的强化学习系统等项目的开发 ,他同时担任伦敦大学学院教授,教授「强化学习」课程。
Ronald Parr
Ronald Parr
简介
相关人物