高級人工智能-第十章-強化學(xué)習(xí)課件

第十章2024/12/11強化學(xué)習(xí)史忠植整體概述概述二點擊此處輸入相關(guān)文本內(nèi)容概述一點擊此處輸入相關(guān)文本內(nèi)容概述三點擊此處輸入相關(guān)文本內(nèi)容內(nèi)容提要引言強化學(xué)習(xí)模型動態(tài)規(guī)劃蒙特卡羅方法時序差分學(xué)習(xí)Q學(xué)習(xí)強化學(xué)習(xí)中的函數(shù)估計應(yīng)用2024/12/13強化學(xué)習(xí)史忠植引言

人類通常從與外界環(huán)境的交互中學(xué)習(xí)。所謂強化（reinforcement）學(xué)習(xí)是指從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，以使系統(tǒng)行為從環(huán)境中獲得的累積獎勵值最大。在強化學(xué)習(xí)中，我們設(shè)計算法來把外界環(huán)境轉(zhuǎn)化為最大化獎勵量的方式的動作。我們并沒有直接告訴主體要做什么或者要采取哪個動作,而是主體通過看哪個動作得到了最多的獎勵來自己發(fā)現(xiàn)。主體的動作的影響不只是立即得到的獎勵，而且還影響接下來的動作和最終的獎勵。試錯搜索(trial-and-errorsearch)和延期強化(delayedreinforcement)這兩個特性是強化學(xué)習(xí)中兩個最重要的特性。

2024/12/14強化學(xué)習(xí)史忠植引言

強化學(xué)習(xí)技術(shù)是從控制理論、統(tǒng)計學(xué)、心理學(xué)等相關(guān)學(xué)科發(fā)展而來，最早可以追溯到巴甫洛夫的條件反射實驗。但直到上世紀(jì)八十年代末、九十年代初強化學(xué)習(xí)技術(shù)才在人工智能、機器學(xué)習(xí)和自動控制等領(lǐng)域中得到廣泛研究和應(yīng)用，并被認(rèn)為是設(shè)計智能系統(tǒng)的核心技術(shù)之一。特別是隨著強化學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)研究取得突破性進(jìn)展后，對強化學(xué)習(xí)的研究和應(yīng)用日益開展起來，成為目前機器學(xué)習(xí)領(lǐng)域的研究熱點之一。2024/12/15強化學(xué)習(xí)史忠植引言強化思想最先來源于心理學(xué)的研究。1911年Thorndike提出了效果律（LawofEffect）：一定情景下讓動物感到舒服的行為，就會與此情景增強聯(lián)系（強化），當(dāng)此情景再現(xiàn)時，動物的這種行為也更易再現(xiàn)；相反，讓動物感覺不舒服的行為，會減弱與情景的聯(lián)系，此情景再現(xiàn)時，此行為將很難再現(xiàn)。換個說法，哪種行為會“記住”，會與刺激建立聯(lián)系，取決于行為產(chǎn)生的效果。動物的試錯學(xué)習(xí),包含兩個含義：選擇（selectional）和聯(lián)系（associative），對應(yīng)計算上的搜索和記憶。所以，1954年，Minsky在他的博士論文中實現(xiàn)了計算上的試錯學(xué)習(xí)。同年，F(xiàn)arley和Clark也在計算上對它進(jìn)行了研究。強化學(xué)習(xí)一詞最早出現(xiàn)于科技文獻(xiàn)是1961年Minsky的論文“StepsTowardArtificialIntelligence”，此后開始廣泛使用。1969年，Minsky因在人工智能方面的貢獻(xiàn)而獲得計算機圖靈獎。2024/12/16強化學(xué)習(xí)史忠植引言1953到1957年，Bellman提出了求解最優(yōu)控制問題的一個有效方法：動態(tài)規(guī)劃（dynamicprogramming）Bellman于1957年還提出了最優(yōu)控制問題的隨機離散版本，就是著名的馬爾可夫決策過程（MDP,Markovdecisionprocesse），1960年Howard提出馬爾可夫決策過程的策略迭代方法，這些都成為現(xiàn)代強化學(xué)習(xí)的理論基礎(chǔ)。1972年，Klopf把試錯學(xué)習(xí)和時序差分結(jié)合在一起。1978年開始，Sutton、Barto、Moore，包括Klopf等對這兩者結(jié)合開始進(jìn)行深入研究。1989年Watkins提出了Q-學(xué)習(xí)[Watkins1989]，也把強化學(xué)習(xí)的三條主線扭在了一起。1992年，Tesauro用強化學(xué)習(xí)成功了應(yīng)用到西洋雙陸棋（backgammon）中，稱為TD-Gammon。2024/12/17強化學(xué)習(xí)史忠植內(nèi)容提要引言強化學(xué)習(xí)模型動態(tài)規(guī)劃蒙特卡羅方法時序差分學(xué)習(xí)Q學(xué)習(xí)強化學(xué)習(xí)中的函數(shù)估計應(yīng)用2024/12/18強化學(xué)習(xí)史忠植主體強化學(xué)習(xí)模型i:inputr:rewards:statea:action狀態(tài)sisi+1ri+1獎勵ri環(huán)境動作

aia0a1a2s0s1s2s32024/12/19強化學(xué)習(xí)史忠植描述一個環(huán)境（問題）Accessiblevs.inaccessibleDeterministicvs.non-deterministicEpisodicvs.non-episodicStaticvs.dynamicDiscretevs.continuousThemostcomplexgeneralclassofenvironmentsareinaccessible,non-deterministic,non-episodic,dynamic,andcontinuous.2024/12/110強化學(xué)習(xí)史忠植強化學(xué)習(xí)問題Agent-environmentinteractionStates,Actions,RewardsTodefineafiniteMDPstateandactionsets:SandAone-step“dynamics”definedbytransitionprobabilities(MarkovProperty):rewardprobabilities:EnvironmentactionstaterewardRLAgent2024/12/111強化學(xué)習(xí)史忠植與監(jiān)督學(xué)習(xí)對比ReinforcementLearning–Learnfrominteractionlearnfromitsownexperience,andtheobjectiveistogetasmuchrewardaspossible.Thelearnerisnottoldwhichactionstotake,butinsteadmustdiscoverwhichactionsyieldthemostrewardbytryingthem.RLSystemInputsOutputs(“actions”)TrainingInfo=evaluations(“rewards”/“penalties”)SupervisedLearning–Learnfromexamplesprovidedbyaknowledgableexternalsupervisor.2024/12/112強化學(xué)習(xí)史忠植強化學(xué)習(xí)要素Policy:stochasticruleforselectingactionsReturn/Reward:thefunctionoffuturerewardsagenttriestomaximizeValue:whatisgoodbecauseitpredictsrewardModel:whatfollowswhatPolicyRewardValueModelofenvironmentIsunknownIsmygoalIsIcangetIsmymethod2024/12/113強化學(xué)習(xí)史忠植在策略Π下的Bellman公式Thebasicidea:So:

Or,withouttheexpectationoperator:isthediscountrate2024/12/114強化學(xué)習(xí)史忠植Bellman最優(yōu)策略公式2024/12/115強化學(xué)習(xí)史忠植MARKOVDECISIONPROCESS

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

RAstatetransitionfunction:T:SxA

∏(S)

T(s,a,s’):probabilityoftransitionfromstos’usingactiona2024/12/116強化學(xué)習(xí)史忠植MDPEXAMPLE:TransitionfunctionStatesandrewardsBellman

Equation:(Greedypolicyselection)2024/12/117強化學(xué)習(xí)史忠植MDPGraphicalRepresentationβ,α:T(s,action,s’)SimilaritytoHiddenMarkovModels(HMMs)2024/12/118強化學(xué)習(xí)史忠植動態(tài)規(guī)劃

DynamicProgramming-ProblemAdiscrete-timedynamicsystemStates{1,…,n}+terminationstate0ControlU(i)TransitionProbabilitypij(u)AccumulativecoststructurePolicies2024/12/119強化學(xué)習(xí)史忠植FiniteHorizonProblemInfiniteHorizonProblemValueIteration動態(tài)規(guī)劃

DynamicProgramming–IterativeSolution

2024/12/120強化學(xué)習(xí)史忠植動態(tài)規(guī)劃中的策略迭代/值迭代policyevaluationpolicyimprovement“greedification”PolicyIterationValueIteration2024/12/121強化學(xué)習(xí)史忠植動態(tài)規(guī)劃方法TTTTTTTTTTTTT2024/12/122強化學(xué)習(xí)史忠植自適應(yīng)動態(tài)規(guī)劃(ADP)Idea:usetheconstraints(statetransitionprobabilities)betweenstatestospeedlearning.Solve

=valuedetermination.Nomaximizationoveractionsbecauseagentispassiveunlikeinvalueiteration.usingDPLargestatespacee.g.Backgammon:1050equationsin1050variables2024/12/123強化學(xué)習(xí)史忠植ValueIterationAlgorithmANALTERNATIVEITERATION:(Singh,1993)(Importantformodelfreelearning)StopIterationwhenV(s)differslessthan?.Policydifferenceratio=<2?γ/(1-γ)

(Williams&Baird1993b)2024/12/124強化學(xué)習(xí)史忠植PolicyIterationAlgorithm

Policiesconvergefasterthanvalues.Whyfasterconvergence?

2024/12/125強化學(xué)習(xí)史忠植ReinforcementLearning…DeterministictransitionsStochastictransitionsistheprobabilitytoreachingstatejwhentakingactionainstateistart3211234+1-1Asimpleenvironmentthatpresentstheagentwithasequentialdecisionproblem:Movecost=0.04(Temporal)creditassignmentproblemsparsereinforcementproblemOfflinealg:actionsequencesdeterminedexanteOnlinealg:actionsequencesisconditionalonobservationsalongtheway;Importantinstochasticenvironment(e.g.jetflying)2024/12/126強化學(xué)習(xí)史忠植ReinforcementLearning…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/12/127強化學(xué)習(xí)史忠植ModelFreeMethodsModelsoftheenvironment:T:SxA

∏(S)

andR:SxARDoweknowthem?Dowehavetoknowthem?MonteCarloMethodsAdaptiveHeuristicCriticQLearning2024/12/128強化學(xué)習(xí)史忠植MonteCarlo策略評價Goal:learnVp(s)

underPandRareunknowninadvanceGiven:

somenumberofepisodesunderpwhichcontainsIdea:AveragereturnsobservedaftervisitstosEvery-VisitMC:averagereturnsforeverytimesisvisitedinanepisodeFirst-visitMC:averagereturnsonlyforfirsttimesisvisitedinanepisodeBothconvergeasymptotically123452024/12/129強化學(xué)習(xí)史忠植蒙特卡羅方法

MonteCarloMethodsIdea:HoldstatisticsaboutrewardsforeachstateTaketheaverageThisistheV(s)Basedonlyonexperience

Assumesepisodictasks(Experienceisdividedintoepisodesandallepisodeswillterminateregardlessoftheactionsselected.)Incrementalinepisode-by-episodesensenotstep-by-stepsense.2024/12/130強化學(xué)習(xí)史忠植Problem:Unvisited<s,a>pairs(problemofmaintainingexploration)Forevery<s,a>makesurethat:P(<s,a>selectedasastartstateandaction)>0(Assumptionofexploringstarts)蒙特卡羅方法

2024/12/131強化學(xué)習(xí)史忠植MonteCarlo方法TTTTTTTTTTTTTTTTTTTT2024/12/132強化學(xué)習(xí)史忠植蒙特卡羅控制HowtoselectPolicies:(Similartopolicyevaluation)

MCpolicyiteration:PolicyevaluationusingMCmethodsfollowedbypolicyimprovement

Policyimprovementstep:greedifywithrespecttovalue(oraction-value)function2024/12/133強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)

Temporal-Differencetarget:theactualreturnaftertimettarget:anestimateofthereturn2024/12/134強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)

(TD)Idea:DoADPbackupsonapermovebasis,notforthewholestatespace.Theorem:AveragevalueofU(i)convergestothecorrectvalue.Theorem:Ifisappropriatelydecreasedasafunctionoftimesastateisvisited(=[N[i]]),thenU(i)itselfconvergestothecorrectvalue2024/12/135強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)

TDTTTTTTTTTTTTTTTTTTTT2024/12/136強化學(xué)習(xí)史忠植TD(l)–AForwardViewTD(l)isamethodforaveragingalln-stepbackupsweightbyln-1(timesincevisitation)l-return:

Backupusingl-return:2024/12/137強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)算法

TD()

Idea:updatefromthewholeepoch,notjustonstatetransition.Specialcases: =1:Least-mean-square(LMS),MontCarlo =0:TDIntermediatechoiceof(between0and1)isbest.Interplaywith…2024/12/138強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)算法2024/12/139強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)算法收斂性TD(

)Theorem:Convergesw.p.1undercertainboundariesconditions.Decrease

i(t)s.t.Inpractice,oftenafixedisusedforalliandt.2024/12/140強化學(xué)習(xí)史忠植時序差分學(xué)習(xí)

TD2024/12/141強化學(xué)習(xí)史忠植Q-Learning

Watkins,1989EstimatetheQ-functionusingsomeapproximator(forexample,linearregressionorneuralnetworksordecisiontreesetc.).DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedQ-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2024/12/142強化學(xué)習(xí)史忠植Q-learningQ(a,i)Directapproach(ADP)wouldrequirelearningamodel.Q-learningdoesnot:Dothisupdateaftereachstatetransition:2024/12/143強化學(xué)習(xí)史忠植ExplorationTradeoffbetweenexploitation(control)andexploration(identification)Extremes:greedyvs.randomacting (n-armedbanditmodels)Q-learningconvergestooptimalQ-valuesif*Everystateisvisitedinfinitelyoften(duetoexploration),*Theactionselectionbecomesgreedyastimeapproachesinfinity,and*Thelearningrateaisdecreasedfastenoughbutnottoofast (aswediscussedinTDlearning)2024/12/144強化學(xué)習(xí)史忠植CommonexplorationmethodsInvalueiterationinanADPagent:OptimisticestimateofutilityU+(i)?-greedymethodNongreedyactionsGreedyactionBoltzmannexplorationExplorationfuncR+ifn<Nuo.w.2024/12/145強化學(xué)習(xí)史忠植Q-LearningAlgorithmSetForTheestimatedpolicysatisfies2024/12/146強化學(xué)習(xí)史忠植Whatistheintuition?BellmanequationgivesIfandthetrainingsetwereinfinite,thenQ-learningminimizeswhichisequivalenttominimizing2024/12/147強化學(xué)習(xí)史忠植A-Learning

Murphy,2003andRobins,2004EstimatetheA-function(advantages)usingsomeapproximator,asinQ-learning.DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedA-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2024/12/148強化學(xué)習(xí)史忠植A-LearningAlgorithm

(InefficientVersion)ForTheestimatedpolicysatisfies2024/12/149強化學(xué)習(xí)史忠植DifferencesbetweenQandA-learningQ-learningAttimetwemodelthemaineffectsofthehistory,(St,,At-1)andtheactionAtandtheirinteractionOurYt-1isaffectedbyhowwemodeledthemaineffectofthehistoryintimet,(St,,At-1)

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

2024/12/150強化學(xué)習(xí)史忠植Q-LearningVs.A-LearningRelativemeritsanddemeritsarenotcompletelyknowntillnow.Q-learninghaslowvariancebuthighbias.A-learninghashighvariancebutlowbias.ComparisonofQ-learningwithA-learninginvolvesabias-variancetrade-off.2024/12/151強化學(xué)習(xí)史忠植POMDP部分感知馬氏決策過程

Ratherthanobservingthestateweobservesomefunctionofthestate.Ob–Observablefunction arandomvariableforeachstates.Problem:differentstatesmaylooksimilarTheoptimalstrategymightneedtoconsiderthehistory.2024/12/152強化學(xué)習(xí)史忠植FrameworkofPOMDP

POMDP由六元組<S,A,R,P,Ω,О>定義。其中<S,A,P,R>定義了環(huán)境潛在的馬爾可夫決策模型上，Ω是觀察的集合，即系統(tǒng)可以感知的世界狀態(tài)集合，觀察函數(shù)О：S×A→PD（Ω）。系統(tǒng)在采取動作a轉(zhuǎn)移到狀態(tài)s′時，觀察函數(shù)О確定其在可能觀察上的概率分布。記為О（s′,a,o）。[1]

Ω可以是S的子集，也可以與S無關(guān)2024/12/153強化學(xué)習(xí)史忠植POMDPsWhatifstateinformation(fromsensors)isnoisy?Mostlythecase!MDPtechniquesaresuboptimal!Twohallsarenotthesame.2024/12/154強化學(xué)習(xí)史忠植POMDPs–ASolutionStrategySE:BeliefStateEstimator(CanbebasedonHMM)П:MDPTechniques2024/12/155強化學(xué)習(xí)史忠植POMDP_信度狀態(tài)方法Idea:Givenahistoryofactionsandobservablevalue,wecomputeaposteriordistributionforthestatewearein(beliefstate)Thebelief-stateMDPStates:distributionoverS(statesofthePOMDP)Actions:asinPOMDPTransition:theposteriordistribution(giventheobservation)OpenProblem:Howtodealwiththecontinuousdistribution?2024/12/156強化學(xué)習(xí)史忠植TheLearningProcessofBeliefMDP2024/12/157強化學(xué)習(xí)史忠植MajorMethodstoSolvePOMDP算法名稱基本思想學(xué)習(xí)值函數(shù)Memorylesspolicies直接采用標(biāo)準(zhǔn)的強化學(xué)習(xí)算法Simplememorybasedapproaches使用k個歷史觀察表示當(dāng)前狀態(tài)UDM(UtileDistinctionMemory)分解狀態(tài)，構(gòu)建有限狀態(tài)機模型NSM(NearestSequenceMemory)存儲狀態(tài)歷史，進(jìn)行距離度量USM(UtileSuffixMemory)綜合UDM和NSM兩種方法Recurrent-Q使用循環(huán)神經(jīng)網(wǎng)絡(luò)進(jìn)行狀態(tài)預(yù)測策略搜索Evolutionaryalgorithms使用遺傳算法直接進(jìn)行策略搜索Gradientascentmethod使用梯度下降（上升）法搜索2024/12/158強化學(xué)習(xí)史忠植強化學(xué)習(xí)中的函數(shù)估計RLFASubsetofstatesValueestimateastargetsV(s)GeneralizationofthevaluefunctiontotheentirestatespaceistheTDoperator.isthefunctionapproximationoperator.2024/12/159強化學(xué)習(xí)史忠植并行兩個迭代過程值函數(shù)迭代過程值函數(shù)逼近過程HowtoconstructtheMfunction?Usingstatecluster,interpolation,decisiontreeorneuralnetwork?2024/12/160強化學(xué)習(xí)史忠植FunctionApproximator:

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/12/161強化學(xué)習(xí)史忠植Semi-MDPDiscretetimeHomogeneousdiscountContinuoustimeDiscreteeventsInterval-dependentdiscountDiscretetimeDiscreteeventsInterval-dependentdiscountAdiscrete-timeSMDPoverlaidonanMDPCanbeanalyzedateitherlevel.OneapproachtoTemporalHierarchicalRL2024/12/162強化學(xué)習(xí)史忠植Theequations2024/12/163強化學(xué)習(xí)史忠植Multi-agentMDPDistributedRLMarkovGameBestResponseEnvironmentactionstaterewardRLAgentRLAgent2024/12/164強化學(xué)習(xí)史忠植三種觀點問題空間主要方法算法準(zhǔn)則合作多agent強化學(xué)習(xí)分布、同構(gòu)、合作環(huán)境交換狀態(tài)提高學(xué)習(xí)收斂速度交換經(jīng)驗交換策略交換建議基于平衡解多agent強化學(xué)習(xí)同構(gòu)或異構(gòu)、合作或競爭環(huán)境極小極大-Q理性和收斂性NASH-QCE-QWoLF最佳響應(yīng)多agent強化學(xué)習(xí)異構(gòu)、競爭環(huán)境PHC收斂性和不遺憾性IGAGIGAGIGA-WoLF2024/12/165強化學(xué)習(xí)史忠植馬爾可夫?qū)Σ咴趎個agent的系統(tǒng)中，定義離散的狀態(tài)集S（即對策集合G），agent動作集Ai的集合A,聯(lián)合獎賞函數(shù)Ri：S×A1×…×An→?和狀態(tài)轉(zhuǎn)移函數(shù)P：S×A1×…×An→PD（S）。

2024/12/166強化學(xué)習(xí)史忠植基于平衡解方法的強化學(xué)習(xí)OpenProblem:Nashequilibriumorotherequilibriumisenough?TheoptimalpolicyinsinglegameisNashequilibrium.2024/12/167強化學(xué)習(xí)史忠植ApplicationsofRLChecker’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/12/168強化學(xué)習(xí)史忠植仿真機器人足球應(yīng)用Q學(xué)習(xí)算法進(jìn)行仿真機器人足球2對1訓(xùn)練，訓(xùn)練的目的是試圖使主體學(xué)習(xí)獲得到一種戰(zhàn)略上的意識，能夠在進(jìn)攻中進(jìn)行配合[宋志偉,2003]2024/12/169強化學(xué)習(xí)史忠植仿真機器人足球前鋒A控球，并且在可射門的區(qū)域內(nèi)，但是A已經(jīng)沒有射門角度了；隊友B也處于射門區(qū)域，并且B具有良好的射門角度。A傳球給B，射門由B來完成，那么這次進(jìn)攻配合就會很成功。通過Q學(xué)習(xí)的方法來進(jìn)行2對1的射門訓(xùn)練，讓A掌握在這種狀態(tài)情況下傳球給B的動作是最優(yōu)的策略；主體通過大量的學(xué)習(xí)訓(xùn)練（大數(shù)量級的狀態(tài)量和重復(fù)相同狀