高级人工智能-第十章-强化学习

高级人工智能第十章史忠植中国科学院计算技术研究所强化学习2024/2/181内容提要引言强化学习模型动态规划蒙特卡罗方法时序差分学习Q学习强化学习中的函数估计应用2024/2/182引言人类通常从与外界环境的交互中学习。所谓强化〔reinforcement〕学习是指从环境状态到行为映射的学习，以使系统行为从环境中获得的累积奖励值最大。在强化学习中，我们设计算法来把外界环境转化为最大化奖励量的方式的动作。我们并没有直接告诉主体要做什么或者要采取哪个动作,而是主体通过看哪个动作得到了最多的奖励来自己发现。主体的动作的影响不只是立即得到的奖励，而且还影响接下来的动作和最终的奖励。试错搜索(trial-and-errorsearch)和延期强化(delayedreinforcement)这两个特性是强化学习中两个最重要的特性。2024/2/183引言强化学习技术是从控制理论、统计学、心理学等相关学科开展而来，最早可以追溯到巴甫洛夫的条件反射实验。但直到上世纪八十年代末、九十年代初强化学习技术才在人工智能、机器学习和自动控制等领域中得到广泛研究和应用，并被认为是设计智能系统的核心技术之一。特别是随着强化学习的数学根底研究取得突破性进展后，对强化学习的研究和应用日益开展起来，成为目前机器学习领域的研究热点之一。2024/2/184引言强化思想最先来源于心理学的研究。1911年Thorndike提出了效果律〔LawofEffect〕：一定情景下让动物感到舒服的行为，就会与此情景增强联系〔强化〕，当此情景再现时，动物的这种行为也更易再现；相反，让动物感觉不舒服的行为，会减弱与情景的联系，此情景再现时，此行为将很难再现。换个说法，哪种行为会“记住”，会与刺激建立联系，取决于行为产生的效果。动物的试错学习,包含两个含义：选择〔selectional〕和联系〔associative〕，对应计算上的搜索和记忆。所以，1954年，Minsky在他的博士论文中实现了计算上的试错学习。同年，Farley和Clark也在计算上对它进行了研究。强化学习一词最早出现于科技文献是1961年Minsky的论文“StepsTowardArtificialIntelligence”，此后开始广泛使用。1969年，Minsky因在人工智能方面的奉献而获得计算机图灵奖。2024/2/185引言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。2024/2/186内容提要引言强化学习模型动态规划蒙特卡罗方法时序差分学习Q学习强化学习中的函数估计应用2024/2/187主体强化学习模型i:inputr:rewards:statea:action状态sisi+1ri+1奖励ri环境动作

aia0a1a2s0s1s2s32024/2/188描述一个环境〔问题〕Accessiblevs.inaccessibleDeterministicvs.non-deterministicEpisodicvs.non-episodicStaticvs.dynamicDiscretevs.continuousThemostcomplexgeneralclassofenvironmentsareinaccessible,non-deterministic,non-episodic,dynamic,andcontinuous.2024/2/189强化学习问题Agent-environmentinteractionStates,Actions,RewardsTodefineafiniteMDPstateandactionsets:SandAone-step“dynamics”definedbytransitionprobabilities(MarkovProperty):rewardprobabilities:EnvironmentactionstaterewardRLAgent2024/2/1810与监督学习比照ReinforcementLearning–Learnfrominteractionlearnfromitsownexperience,andtheobjectiveistogetasmuchrewardaspossible.Thelearnerisnottoldwhichactionstotake,butinsteadmustdiscoverwhichactionsyieldthemostrewardbytryingthem.RLSystemInputsOutputs(“actions”)TrainingInfo=evaluations(“rewards”/“penalties”)SupervisedLearning–Learnfromexamplesprovidedbyaknowledgableexternalsupervisor.2024/2/1811强化学习要素Policy:stochasticruleforselectingactionsReturn/Reward:thefunctionoffuturerewardsagenttriestomaximizeValue:whatisgoodbecauseitpredictsrewardModel:whatfollowswhatPolicyRewardValueModelofenvironmentIsunknownIsmygoalIsIcangetIsmymethod2024/2/1812在策略Π下的Bellman公式Thebasicidea:So:

Or,withouttheexpectationoperator:isthediscountrate2024/2/1813Bellman最优策略公式2024/2/1814MARKOVDECISIONPROCESS

k-armedbanditgivesimmediaterewardDELAYEDREWARD?CharacteristicsofMDP:asetofstates:Sasetofactions:Aarewardfunction:R:SxA

RAstatetransitionfunction:T:SxA

∏(S)

T(s,a,s’):probabilityoftransitionfromstos’usingactiona2024/2/1815MDPEXAMPLE:TransitionfunctionStatesandrewardsBellman

Equation:(Greedypolicyselection)2024/2/1816MDPGraphicalRepresentationβ,α:T(s,action,s’)SimilaritytoHiddenMarkovModels(HMMs)2024/2/1817动态规划

DynamicProgramming-ProblemAdiscrete-timedynamicsystemStates{1,…,n}+terminationstate0ControlU(i)TransitionProbabilitypij(u)AccumulativecoststructurePolicies2024/2/1818FiniteHorizonProblemInfiniteHorizonProblemValueIteration动态规划

DynamicProgramming–IterativeSolution

2024/2/1819动态规划中的策略迭代/值迭代policyevaluationpolicyimprovement“greedification”PolicyIterationValueIteration2024/2/1820动态规划方法TTTTTTTTTTTTT2024/2/1821自适应动态规划(ADP)Idea:usetheconstraints(statetransitionprobabilities)betweenstatestospeedlearning.Solve

=valuedetermination.Nomaximizationoveractionsbecauseagentispassiveunlikeinvalueiteration.usingDPLargestatespacee.g.Backgammon:1050equationsin1050variables2024/2/1822ValueIterationAlgorithmANALTERNATIVEITERATION:(Singh,1993)(Importantformodelfreelearning)StopIterationwhenV(s)differslessthanє.Policydifferenceratio=<2єγ/(1-γ)

(Williams&Baird1993b)2024/2/1823PolicyIterationAlgorithm

Policiesconvergefasterthanvalues.Whyfasterconvergence?

2024/2/1824ReinforcementLearning…DeterministictransitionsStochastictransitionsistheprobabilitytoreachingstatejwhentakingactionainstateistart3211234+1-1Asimpleenvironmentthatpresentstheagentwithasequentialdecisionproblem:Movecost=0.04(Temporal)creditassignmentproblemsparsereinforcementproblemOfflinealg:actionsequencesdeterminedexanteOnlinealg:actionsequencesisconditionalonobservationsalongtheway;Importantinstochasticenvironment(e.g.jetflying)2024/2/1825ReinforcementLearning…M=0.8indirectionyouwanttogo0.2inperpendicular0.1left0.1rightPolicy:mappingfromstatestoactions3211234+1-10.7053211234+1-1

0.8120.762

0.868

0.912

0.660

0.655

0.611

0.388Anoptimalpolicyforthestochasticenvironment:utilitiesofstates:EnvironmentObservable(accessible):perceptidentifiesthestatePartiallyobservableMarkovproperty:Transitionprobabilitiesdependonstateonly,notonthepathtothestate.Markovdecisionproblem(MDP).PartiallyobservableMDP(POMDP):perceptsdoesnothaveenoughinfotoidentifytransitionprobabilities.2024/2/1826ModelFreeMethodsModelsoftheenvironment:T:SxA

∏(S)

andR:SxARDoweknowthem?Dowehavetoknowthem?MonteCarloMethodsAdaptiveHeuristicCriticQLearning2024/2/1827MonteCarlo策略评价Goal:learnVp(s)

underPandRareunknowninadvanceGiven:

somenumberofepisodesunderpwhichcontainsIdea:AveragereturnsobservedaftervisitstosEvery-VisitMC:averagereturnsforeverytimesisvisitedinanepisodeFirst-visitMC:averagereturnsonlyforfirsttimesisvisitedinanepisodeBothconvergeasymptotically123452024/2/1828蒙特卡罗方法

MonteCarloMethodsIdea:HoldstatisticsaboutrewardsforeachstateTaketheaverageThisistheV(s)Basedonlyonexperience

Assumesepisodictasks(Experienceisdividedintoepisodesandallepisodeswillterminateregardlessoftheactionsselected.)Incrementalinepisode-by-episodesensenotstep-by-stepsense.2024/2/1829Problem:Unvisited<s,a>pairs(problemofmaintainingexploration)Forevery<s,a>makesurethat:P(<s,a>selectedasastartstateandaction)>0(Assumptionofexploringstarts)蒙特卡罗方法

2024/2/1830MonteCarlo方法TTTTTTTTTTTTTTTTTTTT2024/2/1831蒙特卡罗控制HowtoselectPolicies:(Similartopolicyevaluation)

MCpolicyiteration:PolicyevaluationusingMCmethodsfollowedbypolicyimprovement

Policyimprovementstep:greedifywithrespecttovalue(oraction-value)function2024/2/1832时序差分学习

Temporal-Differencetarget:theactualreturnaftertimettarget:anestimateofthereturn2024/2/1833时序差分学习

(TD)Idea:DoADPbackupsonapermovebasis,notforthewholestatespace.Theorem:AveragevalueofU(i)convergestothecorrectvalue.Theorem:Ifisappropriatelydecreasedasafunctionoftimesastateisvisited(=[N[i]]),thenU(i)itselfconvergestothecorrectvalue2024/2/1834时序差分学习

TDTTTTTTTTTTTTTTTTTTTT2024/2/1835TD(l)–AForwardViewTD(l)isamethodforaveragingalln-stepbackupsweightbyln-1(timesincevisitation)l-return:

Backupusingl-return:2024/2/1836时序差分学习算法

TD()

Idea:updatefromthewholeepoch,notjustonstatetransition.Specialcases: =1:Least-mean-square(LMS),MontCarlo =0:TDIntermediatechoiceof(between0and1)isbest.Interplaywith…2024/2/1837时序差分学习算法2024/2/1838时序差分学习算法收敛性TD(

)Theorem:Convergesw.p.1undercertainboundariesconditions.Decrease

i(t)s.t.Inpractice,oftenafixedisusedforalliandt.2024/2/1839时序差分学习

TD2024/2/1840Q-Learning

Watkins,1989EstimatetheQ-functionusingsomeapproximator(forexample,linearregressionorneuralnetworksordecisiontreesetc.).DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedQ-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2024/2/1841Q-learningQ(a,i)Directapproach(ADP)wouldrequirelearningamodel.Q-learningdoesnot:Dothisupdateaftereachstatetransition:2024/2/1842ExplorationTradeoffbetweenexploitation(control)andexploration(identification)Extremes:greedyvs.randomacting (n-armedbanditmodels)Q-learningconvergestooptimalQ-valuesif*Everystateisvisitedinfinitelyoften(duetoexploration),*Theactionselectionbecomesgreedyastimeapproachesinfinity,and*Thelearningrateaisdecreasedfastenoughbutnottoofast (aswediscussedinTDlearning)2024/2/1843CommonexplorationmethodsInvalueiterationinanADPagent:OptimisticestimateofutilityU+(i)Є-greedymethodNongreedyactionsGreedyactionBoltzmannexplorationExplorationfuncR+ifn<Nuo.w.2024/2/1844Q-LearningAlgorithmSetForTheestimatedpolicysatisfies2024/2/1845Whatistheintuition?BellmanequationgivesIfandthetrainingsetwereinfinite,thenQ-learningminimizeswhichisequivalenttominimizing2024/2/1846A-Learning

Murphy,2003andRobins,2004EstimatetheA-function(advantages)usingsomeapproximator,asinQ-learning.DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedA-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2024/2/1847A-LearningAlgorithm

(InefficientVersion)ForTheestimatedpolicysatisfies2024/2/1848DifferencesbetweenQandA-learningQ-learningAttimetwemodelthemaineffectsofthehistory,(St,,At-1)andtheactionAtandtheirinteractionOurYt-1isaffectedbyhowwemodeledthemaineffectofthehistoryintimet,(St,,At-1)

A-learningAttimetweonlymodeltheeffectsofAtanditsinteractionwith(St,,At-1)OurYt-1doesnotdependonamodelofthemaineffectofthehistoryintimet,(St,,At-1)

2024/2/1849Q-LearningVs.A-LearningRelativemeritsanddemeritsarenotcompletelyknowntillnow.Q-learninghaslowvariancebuthighbias.A-learninghashighvariancebutlowbias.ComparisonofQ-learningwithA-learninginvolvesabias-variancetrade-off.2024/2/1850POMDP局部感知马氏决策过程Ratherthanobservingthestateweobservesomefunctionofthestate.Ob–Observablefunction arandomvariableforeachstates.Problem:differentstatesmaylooksimilarTheoptimalstrategymightneedtoconsiderthehistory.2024/2/1851FrameworkofPOMDP

POMDP由六元组<S,A,R,P,Ω,О>定义。其中<S,A,P,R>定义了环境潜在的马尔可夫决策模型上，Ω是观察的集合，即系统可以感知的世界状态集合，观察函数О：S×A→PD〔Ω〕。系统在采取动作a转移到状态s′时，观察函数О确定其在可能观察上的概率分布。记为О〔s′,a,o〕。[1]

Ω可以是S的子集，也可以与S无关2024/2/1852POMDPsWhatifstateinformation(fromsensors)isnoisy?Mostlythecase!MDPtechniquesaresuboptimal!Twohallsarenotthesame.2024/2/1853POMDPs–ASolutionStrategySE:BeliefStateEstimator(CanbebasedonHMM)П:MDPTechniques2024/2/1854POMDP_信度状态方法Idea:Givenahistoryofactionsandobservablevalue,wecomputeaposteriordistributionforthestatewearein(beliefstate)Thebelief-stateMDPStates:distributionoverS(statesofthePOMDP)Actions:asinPOMDPTransition:theposteriordistribution(giventheobservation)OpenProblem:Howtodealwiththecontinuousdistribution?2024/2/1855TheLearningProcessofBeliefMDP2024/2/1856MajorMethodstoSolvePOMDP算法名称基本思想学习值函数Memorylesspolicies直接采用标准的强化学习算法Simplememorybasedapproaches使用k个历史观察表示当前状态UDM(UtileDistinctionMemory)分解状态，构建有限状态机模型NSM(NearestSequenceMemory)存储状态历史，进行距离度量USM(UtileSuffixMemory)综合UDM和NSM两种方法Recurrent-Q使用循环神经网络进行状态预测策略搜索Evolutionaryalgorithms使用遗传算法直接进行策略搜索Gradientascentmethod使用梯度下降（上升）法搜索2024/2/1857强化学习中的函数估计RLFASubsetofstatesValueestimateastargetsV(s)GeneralizationofthevaluefunctiontotheentirestatespaceistheTDoperator.isthefunctionapproximationoperator.2024/2/1858并行两个迭代过程值函数迭代过程值函数逼近过程HowtoconstructtheMfunction?Usingstatecluster,interpolation,decisiontreeorneuralnetwork?2024/2/1859FunctionApproximator:

V(s)=f(s,w)Update:Gradient-descentSarsa:

w

w+

a[rt+1+gQ(st+1,at+1)-Q(st,at)]

wf(st,at,w)weightvectorStandardgradienttargetvalueestimatedvalueOpenProblem:Howtodesignthenon-linerFAsystemwhichcanconvergewiththeincrementalinstances?2024/2/1860Semi-MDPDiscretetimeHomogeneousdiscountContinuoustimeDiscreteeventsInterval-dependentdiscountDiscretetimeDiscreteeventsInterval-dependentdiscountAdiscrete-timeSMDPoverlaidonanMDPCanbeanalyzedateitherlevel.OneapproachtoTemporalHierarchicalRL2024/2/1861Theequations2024/2/1862Multi-agentMDPDistributedRLMarkovGameBestResponseEnvironmentactionstaterewardRLAgentRLAgent2024/2/1863三种观点问题空间主要方法算法准则合作多agent强化学习分布、同构、合作环境交换状态提高学习收敛速度交换经验交换策略交换建议基于平衡解多agent强化学习同构或异构、合作或竞争环境极小极大-Q理性和收敛性NASH-QCE-QWoLF最佳响应多agent强化学习异构、竞争环境PHC收敛性和不遗憾性IGAGIGAGIGA-WoLF2024/2/1864马尔可夫对策在n个agent的系统中，定义离散的状态集S〔即对策集合G〕，agent动作集Ai的集合A,联合奖赏函数Ri：S×A1×…×An→ℛ和状态转移函数P：S×A1×…×An→PD〔S〕。2024/2/1865基于平衡解方法的强化学习OpenProblem:Nashequilibriumorotherequilibriumisenough?TheoptimalpolicyinsinglegameisNashequilibrium.2024/2/1866ApplicationsofRLChecker’s[Samuel59]TD-Gammon[Tesauro92]World’sbestdownpeakelevatordispatcher[Critesatal~95]Inventorymanagement[Bertsekasetal~95]10-15%betterthanindustrystandardDynamicchannelassignment[Singh&Bertsekas,Nie&Haykin~95]OutperformsbestheuristicsintheliteratureCart-pole[Michie&Chambers68-]withbang-bangcontrolRoboticmanipulation[Grupenetal.93-]PathplanningRobotdocking[Lin93]ParkingFootball[Stone98]TetrisMultiagentRL[Tan93,Sandholm&Crites95,Sen94-,Carmel&Markovitch95-,lotsofworksince]Combinatorialoptimization:maintenance&repairControlofreasoning[Zhang&DietterichIJCAI-95]2024/2/1867仿真机器人足球应用Q学习算法进行仿真机器人足球2对1训练，训练的目的是试图使主体学习获得到一种战略上的意识，能够在进攻中进行配合[宋志伟,2003]2024/2/1868仿真机器人足球前锋A控球，并且在可射门的区域内，但是A已经没有射门角度了；队友B也处于射门区域，并且B具有良好的射门角度。A传球给B，射门由B来完成，那么这次进攻配合就会很成功。通过Q学习的方法来进行2对1的射门训练，让A掌握在这种状态情况下传球给B的动作是最优的策略；主体通过大量的学习训练〔大数量级的状态量和重复相同状态〕来获得策略，因此更具有适应性。2024/2/1869仿真机器人足球状态描述，将进攻禁区划分为个小区域，每个小区域是边长为2m的正方形，一个二维数组()便可描述这个区域。使用三个Agent的位置来描述2对1进攻时的环境状态，利用图10.11所示的划分来泛化状态。可认为主体位于同一战略区域为相似状态，这样对状态的描述虽然不精确，但设计所需的是一种战略层次的描述，可认为Agent在战略区域内是积极跑动的，这种方法满足了需求。如此，便描述了一个特定的状态；其中，是进攻队员A的区域编号，是进攻队员B的区域编号，是守门员的区域编号。区域编号计算公式为：。相应的，所保存的状态值为三个区域编号组成的对。前锋A控球，并且在可射门的区域内，但是A已经没有射门角度了；队友B也处于射门区域，并且B具有良好的射门角度。A传球给B，射门由B来完成，那么这次进攻配合就会很成功。通过Q学习的方法来进行2对1的射门训练，让A掌握在这种状态情况下传球给B的动作是最优的策略；主体通过大量的学习训练〔大数量级的状态量和重复相同状态〕来获得策略，因此更具有适应性。19图10.11进攻禁区内的位置划分072024/2/1870仿真机器人足球可选动作集确定为的策略通过基于概率的射门训练的学习来得到。的策略是，始终向受到威胁小，并且射门成功率高的区域带球。为了实现这一策略目标，可划分进攻区域为多个战略区，在每个战略区进行射门评价，记