深化进修

深化进修是一种试错方法,其目标是让软件智能体特定状况中可以接纳回报最大化的方法。深化进修马尔可夫计划进程状况中主要运用的技能是动态计划(Dynamic Programming)。风行的深化进修方法包罗自顺应动态计划(ADP)、时间差分(TD)进修、形态-举措-回报-形态-举措(SARSA)算法、Q 进修、深度深化进修(DQN);其运用包罗下棋类游戏、板滞人掌握和义务调治等。

简介

深化进修是一种试错方法,其目标是让软件智能体特定状况中可以接纳回报最大化的方法。深化进修马尔可夫计划进程状况中主要运用的技能是动态计划(Dynamic Programming)。风行的深化进修方法包罗自顺应动态计划(ADP)、时间差分(TD)进修、形态-举措-回报-形态-举措(SARSA)算法、Q 进修、深度深化进修(DQN);其运用包罗下棋类游戏、板滞人掌握和义务调治等。

举例来说,让我们思索进修下象棋的题目。监视进修状况下的智能体(agent)需求被睹告每个所处的位置的准确举措,可是供应这种反应很不实行。没有教师反应的状况下,智能体需求进修转换模子来掌握本人的举措,也可以要学会预测对手的举措。但假设智能体取得的反应欠好也不坏,智能体将没有来由偏向于任何一种举动。当智能体下了一步好棋时,智能体需求晓得这是一件好事,反之亦然。这种反应称为奖励(reward)或深化(reinforcement)。象棋如许的游戏中,智能体只要游戏完毕时才会收到奖励/深化。其他状况中,奖励可以会更频繁。

深化进修的基本因素,我们对其区分举行定义:

  • 智能体(Agent):可以接纳举动的智能个体;比如,可以完毕送达的无人机,或者视频游戏中朝目标举动的超级马里奥。深化进修算法便是一个智能体。而实行生存中,谁人智能体便是你。
  • 举动(Action):A是智能体可以接纳的举动的汇合。一个举动(action)确实是一目清楚的,可是应当当心的是智能体是从可以的举动列外中举行挑选。电子游戏中,这个举动列外可以包罗向右飞驰或者向左飞驰,向高因由跳或者向低处跳,下蹲或者站住不动。股市中,这个举动列外可以包罗买入,卖出或者持有任何有价证券或者它们的变体。处理空中遨游的无人机时,举动选项包罗三维空间中的许众速率和加速率。
  • 状况(Environment):指的便是智能体行走于此中的天下。这个状况将智能体目今的形态和举动举措输入,输出是智能体的奖励和下一步的形态。假如你是一个智能体,那么你所处的状况便是可以处理举动和决议你一系列举动的结果的物理法则和社会规矩。
  • 形态(State,S):一个形态便是智能体所处的精细即时形态;也便是说,一个精细的地方和时候,这是一个精细的即时配备,它可以将智能体和其他主要的误事物联系起来,比如东西、仇敌和或者奖励。它是由状况返回的目今情势。你是否曾过失的时间呈现过失的地方?那无疑便是一个形态了。
  • 奖励(Reward,R):奖励是我们权衡某个智能体的举动成败的反应。比如,视频游戏中,当马里奥碰到金币的时分,它就会博得分数。面临任何既定的形态,智能体要以举动的方式向状况输出,然后状况会返回这个智能体的一个新形态(这个新形态会受到基于之前形态的举动的影响)和奖励(假如有任何奖励的话)。奖励可以是即时的,也可以是迟滞的。它们可以有用地评估该智能体的举动。

以是,状况便是可以将目今形态下接纳的举措转换成下一个形态和奖励的函数;智能体是将新的形态和奖励转换成下一个举动的函数。我们可以知悉智能体的函数,可是我们无法知悉状况的函数。状况是一个我们只可看到输入输出的黑盒子。深化进修相当于智能体实验迫近这个状况的函数,如许我们就可以向黑盒子状况发送最大化奖励的举动了。

当然,奖励并不是深化进修的专利。马尔科夫计划进程(MDP)中最优计谋的定义也涉及到奖励。 最佳计谋是最大化预期总回报的计谋。 深化进修的义务是运用察看到的奖励来进修再目今状况中的最优(或接近最优)计谋。 这里我们假设智能体没有任何先验常识, 念象一下,玩一个你不晓得的规矩的新游戏; 颠末一百次尊驾的举措之后,你的对手发布:“你输了。”,这确实便是深化进修。

许众繁杂的范畴,深化进修是完成高程度智能体的独一可行方法。比如,玩游戏时,人们很难供应对大宗位置的准确和同等的评估——而若我们直接从示例中教练评估函数则这些新闻是必需的——相反,游戏中智能体可以获胜或糜烂时被睹告,而且可以运用这些新闻来进修评估函数,使得该函数可以对任何给定位置的获胜概率举行合理准确的估量。

一般来说,深化进修的计划有三种:

  1. 基于效用的智能体(utility-based agent)进修形态的效用函数,并用它来挑选最大化效用预期的操作;
  2. Q进修智能体(Q-learning agent)进修举措效用函数——又称Q函数——给出给定形态下接纳给定举措的预期效用;
  3. 反射智能体(reflex agent)进修葱〈态直接映照到操作的计谋。

基于效用的智能体必需具有状况模子才干做出计划,因为它必需晓得其方法将会导致什么形态。只要如许,它才干将效用函数运用于结果形态。另一方面,Q-learning智能体可以将预期效用与其可用挑选举行比较,而不需求晓得结果,于是它不需求状况模子。但因为Q-learning中智能体不晓得本人所处的状况,Q-learning智能体无法举行预测,这会告急限制他们的进修才能。

深化进修也可以分为被动进修和主动进修。被动进修中智能体的计谋是固定的,义务是进修形态(或形态 - 方法配对)的效用,也可以涉及到进修状况模子。主动进修主要涉及的题目是探究:智能体必需尽可以众地体验其状况,以便进修怎样外现。

[描画根源:Russell, S. J., & Norvig, P. (2010). Artificial Intelligence (A Modern Approach). ]

[描画根源:深化进修的基本看法与代码完成|中文字幕AV ]

开展历史

深化进修的开展历史并不长。深化进修的根底也才不过 50 众年历史。1953年,运用数学家Richard Bellman提出动态计划数学表面和方法,此中的贝尔曼条件(Bellman condition)是深化进修的根底之一。到20世纪50年代末,人们开端运用「最优掌握(optimal control)」这一术语。1957年,Richard Bellman提出了马尔可夫计划进程,准确的了解马尔可夫计划进程对进修深化进修至关主要。到了60年代,「深化」和「深化进修」的看法开端工程文献中呈现。1963年,Andreae 开辟出 STeLLA 系统,可以通过与状况交互举行试错进修;Donald Michie 描画了 MENACE——一种试错进修系统。这是早期简单的探爽速研讨。1975年,John Holland 基于挑选原理阐述了自顺应系统的一般表面。他的著作《自然系统和人工系统中的自顺应(Adaptation in Natural and Artificial Systems)》的出书是人工智能范畴的主要事情之一,除了对深化进修研讨的影响,书中还普及了遗传算法,促进了搜寻与优化的研讨。

1977年,1977年,Paul Werbos先容了一种求解自顺应动态计划的方法,该方法厥后被称为自顺应校正计划(Adaptive Critic Designs)。自顺应校正计划有许众同义词,包罗近似动态计划(Approximate Dynamic Programming),渐近的动态计划(Asymptotic Dynamic Programming),自顺应动态计划(Adaptive Dynamic Programming),启示式动态计划(Heuristic Dynamic Programming),神经动态计划(Neuro-Dynamic Programming)。奠定了厥后的动态计划、深化进修的根底。Sutton于1988年先容了一类特别用于预测的增量进修进程 - 也便是说,运用过去不完备晓得的系统的履本来预测其未来方法。这即是时序差分法,关于大大都实行天下的预测题目,时间差分方法比当时的古板方法需求更少的内存和更少的峰值盘算,而且它们可以发生更准确的预测。

1989年,Watkins本人的博士论文(Learning from delayed rewards)中最早提出Q进修算法。1991年,Lovejoy 研讨结果部可观测马尔可夫计划进程(POMDP)。1992年,Watkins和Dayan板滞进修的一个技能条记(Technical note)给出了Q进修的收敛性标明,标清楚当所有的形态都能重复拜访时,Q函数最终会收敛到最优Q值。 1995年D. P. Bertsekas 和 J. N. Tsitsiklis议论了一类用于不确定条件下的掌握温序次计划的动态计划方法。 这些方法具有处理恒久以后因为形态空间较大或缺乏准确模子而难以处理的题目的潜力,他们将计划所基于的状况外述为马尔可夫计划进程,这即是目前深度进修范畴风行的深化进修的雏形。

时间差分方法提出几年后,Tesauro基于Sutton的TD-Lambda算法开辟了TD-Gammon,这是一个神经收集,通过与本人对立并从结果中进修,他将TD-Gammon用于步步高游戏,该顺序学会了专业人类玩家的程度上玩步步高游戏,大大超越了以前的所有盘算机顺序。1994年,Rummery和Niranjan一个名为“Modified Connectionist Q-Learning”(MCQ-L)的技能解释中提出了SARSA,这是一种进修马尔可夫计划进程计谋的算法。1996年,Bertsekas和Tsitsiklis发外了Neuro-dynamic programming论文,精细先容了神经动态计划算法的概略。1999年,为了可以举行牢靠的位置估量,Thrun等人提出蒙特卡罗定位方法,运用概率方法办理板滞人定位题目。他们的实证结果外明通过实行标明,所取得的方法可以不晓得其起始位置的状况下有用地定位挪动板滞人。与早期的基于网格的方法比较,它更速,更准确,内存更少。

2010年开端,深化进修技能(MDP 和动态计划)也被用于金融衍生品订价题目。2013年,来自DeepMind的Mnih等人NIPS发外了Playing atari with deep reinforcement learning论文,论文中主体应用深度进修收集(CNNs)直接从高维度的感受器输入(sensory inputs)提取有用特征,然后应用Q-Learning进修主体的最优计谋。这种联合深度进修的Q进修方法被称为深度Q进修(DQL)。2014年,Silver等人提出了确定性计谋梯度算法,用于延续举措的深化进修。 确定性计谋梯度具有特别吸引人的方式——它是举动代价函数的预期梯度。 这种简单的方式意味着对确定性计谋梯度的估量可以比对一般的随机计谋梯度估量更有用。2016年,Van Hasselt, H., Guez, A.提出了运用双Q-learning的深度深化进修。2017年10月,DeepMind发布最新深化版的AlphaGo Zero,这是一个无需用到人类专业棋谱的版本,比之前的版本都强大。通过自我对弈,AlphaGo Zero颠末三天的进修就超越了AlphaGo Lee版本的程度,21天后抵达AlphaGo Maseter的气力,40天内超越之前所有版本。2017年12月,DeepMind发布AlphaZero论文,进阶版的AlphaZero算法将围棋范畴扩展到国际象棋、日本象棋范畴,且无需人类专业常识就能击败各自范畴的天下冠军。 AAAI 2018 接纳论文列外中,来自阿尔伯塔大学深化进修和人工智能实行室 Sutton 等研讨者的一篇论文提出一种新的众步举措代价算法 Q(σ),该算法联合已有的时序差分算法,可带来更好功用。5月,DeepMind Nature Neuroscience 发外新论文,该研讨中他们依据神经科学中的众巴胺进修模子的扩展,夸张了众巴胺大脑最主要的智能区域即前额叶皮质发挥的全体感化,并据此提出了一种新型的元深化进修算法。

依据谷歌趋势上的数据来看,人们对深化进修的兴味下降过一段时间。深度进修的开展以及 AlphaGo 等成功运用的促进下,人们的兴味近来又重回高位。于是,深化进修颠着末几十年的实行室研讨和工程阶段之后,我们认为应当将其划入运用阶段。另外,也有许众板滞人公司曾经开端运用深化进修来教练啥菝板滞人。

主要事情

年份

事情

相关论文/Reference

1953

Richard Bellman提出贝尔曼条件(Bellman condition),这是深化进修的根底之一

Bellman, R. (1953). An introduction to the theory of dynamic programming.Rand Corporation Santa Monica Calif.

1956/1957

Bellman 先容了动态计划和马尔可夫计划进程(MDP)的看法

Bellman, R. (1957). A Markovian decision process. Journal of Mathematics and Mechanics, 679-684.

1963

Andreae 开辟出 STeLLA 系统(通过与状况交互举行试错进修);Donald Michie 描画了 MENACE (一种试错进修系统)

Andreae, J. (1963). STELLA: A Scheme for a Learning Machine.

1975

John Holland基于挑选原理阐述了自顺应系统的一般表面

Holland, J. H. (1992).Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence.MIT Press.

1977

Werbos 提出自顺应动态计划(ADP)

Werbos, P. (1977). Advanced forecasting methods for global crisis warning and models of intelligence. General System Yearbook, 25-38.

1988

R.S.Sutton 首次运用时间差分进修(TD 算法降生)

Sutton, R. (1988). Learning to predict by the methods of temporal differences.Machine Learning. 3 (1): 9–44.

1989

Watkins提出了Q进修

Watkins, C. J. C. H. (1989). Learning from delayed rewards (Doctoral dissertation, King's College, Cambridge).

1991

Lovejoy 研讨结果部可观测马尔可夫计划进程(POMDP)

Lovejoy, W. S. (1991).A survey of algorithmic methods for partially observed Markov decision processes.Annals of Operations Research. 28(1):47–65.

1994

Tesauro et al.将深化进修和神经收集联合到了一同

Tesauro, G. (1995).Temporal Difference Learning and TD-Gammon.Communications of the ACM. 38 (3).

1994

Rummery提出SARSA

Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems (Vol. 37). University of Cambridge, Department of Engineering.

1996

Bertsekas提出神经动态计划(Neuro-Dynamic Programming)

Bertsekas, Dimitri P., and John N. Tsitsiklis. "Neuro-dynamic programming: an overview." Decision and Control, 1995., Proceedings of the 34th IEEE Conference on. Vol. 1. IEEE, 1995.

1999

Thrun等人提出蒙特卡罗定位方法

Dellaert, F.; Fox, D.; Burgard, W. and Thrun, S. (1999). Monte Carlo localization for mobile robots.Proceedings 1999 IEEE International Conference on Robotics and Automation. 2: 1322-1328.

2013

Mnih et al.提出深度Q进修(DQN)

Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602.

2014

Silver提出确定性计谋梯度进修(Policy Gradient Learning)

Silver, D.; Lever, G.; Heess, N.; Degris, T.; Wierstra, D. et al .(2014). Deterministic Policy Gradient Algorithms. ICML.

2016

AlphaGo(Silver et al.)成为深度深化进修运用的出名案例

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., ... & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484-489.

2016

Van Hasselt, H., Guez, A.运用双Q-learning的深度深化进修

Van Hasselt, H., Guez, A., & Silver, D. (2016, February). Deep Reinforcement Learning with Double Q-Learning. In AAAI (Vol. 16, pp. 2094-2100).

2017

DeepMind公司发布AlphaZero论文,进阶版的AlphaZero算法将围棋范畴扩展到国际象棋、日本象棋范畴,且无需人类专业常识就能击败各自范畴的天下冠军

Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., ... & Lillicrap, T. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv preprint arXiv:1712.01815.

2017

Sutton和Barto等学者提出了Q(σ)算法

Asis, K. D. et al.Multi-step Reinforcement Learning: A Unifying Algorithm.arXiv:1703.01327.

2018

DeepMindNature Neuroscience发外新论文提出了一种新型的元深化进修算法

Wang, J. X. et al. (2018). Prefrontal cortex as a meta-reinforcement learning system. Nature Neuroscience.

开展剖析

瓶颈

  • 深化进修的教练一般自有规矩的虚拟状况中举行,而实行天下往往要繁杂得众。
  • 斗嗽糍度慢,而且往往需求大宗样本举措根底。
  • 深化进修的商业运用仍然很有限,而且前景不明,相似于神经收集模子开展的早期阶段。
  • 目前风行的深度深化进修奖励函数计划艰难、采样服从底下(sample inefficiency),即使最合理的奖励也不行避免部分最优,因此教练难度大。

未来开展偏向

  • 需求更少数据的「一次性进修(one shot learning)」以及可以独立进修智能体举措的「离计谋进修(off policy learning)」的改良和完美值得等候。
  • 深化进修与深度进修等其它智能方法的联合会有一个灼烁的未来,可以将更众智能带进游戏、驾驶和板滞人等差别运用中。
  • 目前有基于模子的深度深化进修,试图进修状况的动态模子,可以大大进步采样服从(sample efficiency),从而进步进修服从。

Contributor: Yuanyuan Li, Mos Zhang

相关人物
塞巴斯蒂安 · 史朗
塞巴斯蒂安 · 史朗
Sebastian Thrun 是德国的立异者,企业家蕉蔟家和盘算机科学家。他是 Kitty Hawk Corporation 的首席施行官,也是 Udacity 的董事长兼联合创始人。此之前,他曾承当谷歌副总裁兼研讨员,斯坦福大学盘算机科学传授,之前是卡内基梅隆大学。谷歌,他创立了谷歌 X 和谷歌的主动驾驶汽车团队。
Volodymyr Mnih
Volodymyr Mnih
Andrew G. Barto
Andrew G. Barto
理查德S.萨顿
理查德S.萨顿
Richard S. Sutton 传授博士结业于马萨诸塞大学安姆斯特分校,现任阿尔伯塔大学盘算机科学传授。Sutton 传授被认为是当代盘算的深化进修创立者之一。他为该范畴做出了许众庞大奉献,包罗:时间差分进修(temporal difference learning)、计谋梯度方法(policy gradient methods)、Dyna 架构
John Hugh Andreae
John Hugh Andreae
简介
相关人物