史忠植 高级人工智能(中科院)第十章

高级人工智能第十章史忠植中国科学院计算技术研究所强化学习ReinforcementLearning2012-04-26史忠植强化学习2内容提要引言强化学习模型动态规划蒙特卡罗方法时序差分学习Q学习强化学习中的函数估计应用2012-04-26史忠植强化学习3引言人类通常从与外界环境的交互中学习。所谓强化（reinforcement）学习是指从环境状态到行为映射的学习，以使系统行为从环境中获得的累积奖励值最大。在强化学习中，我们设计算法来把外界环境转化为最大化奖励量的方式的动作。我们并没有直接告诉主体要做什么或者要采取哪个动作,而是主体通过看哪个动作得到了最多的奖励来自己发现。主体的动作的影响不只是立即得到的奖励，而且还影响接下来的动作和最终的奖励。试错搜索(trial-and-errorsearch)和延期强化(delayedreinforcement)这两个特性是强化学习中两个最重要的特性。2012-04-26史忠植强化学习4引言强化学习技术是从控制理论、统计学、心理学等相关学科发展而来，最早可以追溯到巴甫洛夫的条件反射实验。但直到上世纪八十年代末、九十年代初强化学习技术才在人工智能、机器学习和自动控制等领域中得到广泛研究和应用，并被认为是设计智能系统的核心技术之一。特别是随着强化学习的数学基础研究取得突破性进展后，对强化学习的研究和应用日益开展起来，成为目前机器学习领域的研究热点之一。2012-04-26史忠植强化学习5引言强化思想最先来源于心理学的研究。1911年Thorndike提出了效果律（LawofEffect）：一定情景下让动物感到舒服的行为，就会与此情景增强联系（强化），当此情景再现时，动物的这种行为也更易再现；相反，让动物感觉不舒服的行为，会减弱与情景的联系，此情景再现时，此行为将很难再现。换个说法，哪种行为会“记住”，会与刺激建立联系，取决于行为产生的效果。动物的试错学习,包含两个含义：选择（selectional）和联系（associative），对应计算上的搜索和记忆。所以，1954年，Minsky在他的博士论文中实现了计算上的试错学习。同年，Farley和Clark也在计算上对它进行了研究。强化学习一词最早出现于科技文献是1961年Minsky的论文“StepsTowardArtificialIntelligence”，此后开始广泛使用。1969年，Minsky因在人工智能方面的贡献而获得计算机图灵奖。2012-04-26史忠植强化学习6引言1953到1957年，Bellman提出了求解最优控制问题的一个有效方法：动态规划（dynamicprogramming）Bellman于1957年还提出了最优控制问题的随机离散版本，就是著名的马尔可夫决策过程（MDP,Markovdecisionprocesse），1960年Howard提出马尔可夫决策过程的策略迭代方法，这些都成为现代强化学习的理论基础。1972年，Klopf把试错学习和时序差分结合在一起。1978年开始，Sutton、Barto、Moore，包括Klopf等对这两者结合开始进行深入研究。1989年Watkins提出了Q-学习[Watkins1989]，也把强化学习的三条主线扭在了一起。1992年，Tesauro用强化学习成功了应用到西洋双陆棋（backgammon）中，称为TD-Gammon。2012-04-26史忠植强化学习7内容提要引言强化学习模型动态规划蒙特卡罗方法时序差分学习Q学习强化学习中的函数估计应用2012-04-26史忠植强化学习8主体强化学习模型i:inputr:rewards:statea:action状态sisi+1ri+1奖励ri环境动作aia0a1a2s0s1s2s32012-04-26史忠植强化学习9描述一个环境（问题）Accessiblevs.inaccessibleDeterministicvs.non-deterministicEpisodicvs.non-episodicStaticvs.dynamicDiscretevs.continuousThemostcomplexgeneralclassofenvironmentsareinaccessible,non-deterministic,non-episodic,dynamic,andcontinuous.2012-04-26史忠植强化学习10强化学习问题Agent-environmentinteractionStates,Actions,RewardsTodefineafiniteMDPstateandactionsets:SandAone-step“dynamics”definedbytransitionprobabilities(MarkovProperty):rewardprobabilities:EnvironmentactionstaterewardRLAgent{}1Pr,forall,,().asstttPssssaassSaAs′+′′====∈∈{}11,,forall,,().assttttRErssaassssSaAs′++′′====∈∈2012-04-26史忠植强化学习11与监督学习对比ReinforcementLearning–Learnfrominteractionlearnfromitsownexperience,andtheobjectiveistogetasmuchrewardaspossible.Thelearnerisnottoldwhichactionstotake,butinsteadmustdiscoverwhichactionsyieldthemostrewardbytryingthem.RLSystemInputsOutputs(“actions”)TrainingInfo=evaluations(“rewards”/“penalties”)SupervisedLearning–Learnfromexamplesprovidedbyaknowledgableexternalsupervisor.2012-04-26史忠植强化学习12强化学习要素Policy:stochasticruleforselectingactionsReturn/Reward:thefunctionoffuturerewardsagenttriestomaximizeValue:whatisgoodbecauseitpredictsrewardModel:whatfollowswhatPolicyRewardValueModelofenvironmentIsunknownIsmygoalIsIcangetIsmymethod2012-04-26史忠植强化学习13在策略Π下的Bellman公式()1t1t4t23t2t1t4t33t22t1ttRrrrrrrrrrR++++++++++γ+=γ+γ+γ+=γ+γ+γ+=Thebasicidea:So:{}(){}sssVrEssRE)s(Vt1t1ttt=γ+===++πππOr,withouttheexpectationoperator:[]∑∑′γ+π=′π′′πasassass)s(VRP)a,s()s(Vγisthediscountrate2012-04-26史忠植强化学习14Bellman最优策略公式{}11()()()max(),max()ttttaAsaassssaAssVsErVsssaaPRVsγγ∗∗++∈∗′′∈′=+==′=+∑其中：V*：状态值映射S：环境状态R：奖励函数P：状态转移概率函数γ：折扣因子2012-04-26史忠植强化学习15马尔可夫决策过程MARKOVDECISIONPROCESS由四元组S，A，R，P定义。环境状态集S系统行为集合A奖励函数R：S×A→ℛ状态转移函数P：S×A→PD（S）记R（s，a，s′）为系统在状态s采用a动作使环境状态转移到s′获得的瞬时奖励值；记P（s，a，s′）为系统在状态s采用a动作使环境状态转移到s′的概率。2012-04-26史忠植强化学习16马尔可夫决策过程MARKOVDECISIONPROCESS马尔可夫决策过程的本质是：当前状态向下一状态转移的概率和奖励值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。因此在已知状态转移概率函数P和奖励函数R的环境模型知识下，可以采用动态规划技术求解最优策略。而强化学习着重研究在P函数和R函数未知的情况下，系统如何学习最优行为策略。2012-04-26史忠植强化学习17MARKOVDECISIONPROCESSCharacteristicsofMDP:asetofstates:Sasetofactions:Aarewardfunction:R:SxARAstatetransitionfunction:T:SxA∏(S)T(s,a,s’):probabilityoftransitionfromstos’usingactiona2012-04-26史忠植强化学习18马尔可夫决策过程MARKOVDECISIONPROCESS模型瞬时奖惩策略状态值函数2012-04-26史忠植强化学习19MDPEXAMPLE:TransitionfunctionStatesandrewardsBellmanEquation:(Greedypolicyselection)2012-04-26史忠植强化学习20MDPGraphicalRepresentationβ,α:T(s,action,s’)SimilaritytoHiddenMarkovModels(HMMs)highlowsearchwaitrechargesearchwaitSearchR,αwaitR,13,1−−β0,1SearchR,1α−SearchR,βwaitR,12012-04-26史忠植强化学习21ReinforcementLearning…DeterministictransitionsStochastictransitionsaijMistheprobabilitytoreachingstatejwhentakingactionainstateistart3211234+1-1Asimpleenvironmentthatpresentstheagentwithasequentialdecisionproblem:Movecost=0.04(Temporal)creditassignmentproblemsparsereinforcementproblemOfflinealg:actionsequencesdeterminedexanteOnlinealg:actionsequencesisconditionalonobservationsalongtheway;Importantinstochasticenvironment(e.g.jetflying)2012-04-26史忠植强化学习22ReinforcementLearning…M=0.8indirectionyouwanttogo0.2inperpendicular0.1left0.1rightPolicy:mappingfromstatestoactions3211234+1-10.7053211234+1-10.8120.7620.8680.9120.6600.6550.6110.388Anoptimalpolicyforthestochasticenvironment:utilitiesofstates:EnvironmentObservable(accessible):perceptidentifiesthestatePartiallyobservableMarkovproperty:Transitionproba