第10章-強(qiáng)化學(xué)習(xí)

第10章-強(qiáng)化學(xué)習(xí)第10章-強(qiáng)化學(xué)習(xí)第10章-強(qiáng)化學(xué)習(xí)2020/11/20強(qiáng)化學(xué)習(xí)史忠植2內(nèi)容提要引言強(qiáng)化學(xué)習(xí)模型動(dòng)態(tài)規(guī)劃蒙特卡羅方法時(shí)序差分學(xué)習(xí)Q學(xué)習(xí)強(qiáng)化學(xué)習(xí)中的函數(shù)估計(jì)應(yīng)用內(nèi)容提要引言強(qiáng)化學(xué)習(xí)模型動(dòng)態(tài)規(guī)劃蒙特卡羅方法時(shí)序差分學(xué)習(xí)Q學(xué)習(xí)強(qiáng)化學(xué)習(xí)中的函數(shù)估計(jì)應(yīng)用2024/11/132強(qiáng)化學(xué)習(xí)史忠植引言

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

2024/11/133強(qiáng)化學(xué)習(xí)史忠植引言

強(qiáng)化學(xué)習(xí)技術(shù)是從控制理論、統(tǒng)計(jì)學(xué)、心理學(xué)等相關(guān)學(xué)科發(fā)展而來，最早可以追溯到巴甫洛夫的條件反射實(shí)驗(yàn)。

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

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

Or,withouttheexpectationoperator:isthediscountrate2024/11/1313強(qiáng)化學(xué)習(xí)史忠植Bellman最優(yōu)策略公式其中：V*：狀態(tài)值映射S：環(huán)境狀態(tài)R：獎(jiǎng)勵(lì)函數(shù)P：狀態(tài)轉(zhuǎn)移概率函數(shù)：折扣因子2024/11/1314強(qiáng)化學(xué)習(xí)史忠植馬爾可夫決策過程

MARKOVDECISIONPROCESS

由四元組<S，A，R，P>定義。

環(huán)境狀態(tài)集S

系統(tǒng)行為集合A

獎(jiǎng)勵(lì)函數(shù)R：S×A→?

狀態(tài)轉(zhuǎn)移函數(shù)P：S×A→PD（S）

記R（s，a，s′）為系統(tǒng)在狀態(tài)s采用a動(dòng)作使環(huán)境狀態(tài)轉(zhuǎn)移到s′獲得的瞬時(shí)獎(jiǎng)勵(lì)值；記P（s，a，s′）為系統(tǒng)在狀態(tài)s采用a動(dòng)作使環(huán)境狀態(tài)轉(zhuǎn)移到s′的概率。2024/11/1315強(qiáng)化學(xué)習(xí)史忠植馬爾可夫決策過程

MARKOVDECISIONPROCESS馬爾可夫決策過程的本質(zhì)是：當(dāng)前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和獎(jiǎng)勵(lì)值只取決于當(dāng)前狀態(tài)和選擇的動(dòng)作，而與歷史狀態(tài)和歷史動(dòng)作無(wú)關(guān)。因此在已知狀態(tài)轉(zhuǎn)移概率函數(shù)P和獎(jiǎng)勵(lì)函數(shù)R的環(huán)境模型知識(shí)下，可以采用動(dòng)態(tài)規(guī)劃技術(shù)求解最優(yōu)策略。而強(qiáng)化學(xué)習(xí)著重研究在P函數(shù)和R函數(shù)未知的情況下，系統(tǒng)如何學(xué)習(xí)最優(yōu)行為策略。2024/11/1316強(qiáng)化學(xué)習(xí)史忠植MARKOVDECISIONPROCESSCharacteristicsofMDP:asetofstates:Sasetofactions:Aarewardfunction:R:SxA

RAstatetransitionfunction:T:SxA

∏(S)

T(s,a,s’):probabilityoftransitionfromstos’usingactiona2024/11/1317強(qiáng)化學(xué)習(xí)史忠植馬爾可夫決策過程

MARKOVDECISIONPROCESS2024/11/1318強(qiáng)化學(xué)習(xí)史忠植MDPEXAMPLE:TransitionfunctionStatesandrewardsBellman

Equation:(Greedypolicyselection)2024/11/1319強(qiáng)化學(xué)習(xí)史忠植MDPGraphicalRepresentationβ,α:T(s,action,s’)SimilaritytoHiddenMarkovModels(HMMs)2024/11/1320強(qiáng)化學(xué)習(xí)史忠植ReinforcementLearning

…DeterministictransitionsStochastictransitionsistheprobabilitytoreachingstatejwhentakingactionainstateistart3211234+1-1Asimpleenvironmentthatpresentstheagentwithasequentialdecisionproblem:Movecost=0.04(Temporal)creditassignmentproblemsparsereinforcementproblemOfflinealg:actionsequencesdeterminedexanteOnlinealg:actionsequencesisconditionalonobservationsalongtheway;Importantinstochasticenvironment(e.g.jetflying)2024/11/1321強(qiáng)化學(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/11/1322強(qiáng)化學(xué)習(xí)史忠植動(dòng)態(tài)規(guī)劃DynamicProgramming動(dòng)態(tài)規(guī)劃(dynamicprogramming)的方法通過從后繼狀態(tài)回溯到前驅(qū)狀態(tài)來計(jì)算賦值函數(shù)。動(dòng)態(tài)規(guī)劃的方法基于下一個(gè)狀態(tài)分布的模型來接連的更新狀態(tài)。強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)規(guī)劃的方法是基于這樣一個(gè)事實(shí)：對(duì)任何策略π和任何狀態(tài)s，有(10.9)式迭代的一致的等式成立π(a｜s)是給定在隨機(jī)策略π下狀態(tài)s時(shí)動(dòng)作a的概率。π(s→s'｜a)是在動(dòng)作a下狀態(tài)s轉(zhuǎn)到狀態(tài)s'的概率。這就是對(duì)Vπ的Bellman(1957)等式。2024/11/1323強(qiáng)化學(xué)習(xí)史忠植動(dòng)態(tài)規(guī)劃

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

DynamicProgramming–IterativeSolution

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

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

(Williams&Baird1993b)2024/11/1329強(qiáng)化學(xué)習(xí)史忠植PolicyIterationAlgorithm

Policiesconvergefasterthanvalues.Whyfasterconvergence?

2024/11/1330強(qiáng)化學(xué)習(xí)史忠植動(dòng)態(tài)規(guī)劃DynamicProgramming典型的動(dòng)態(tài)規(guī)劃模型作用有限，很多問題很難給出環(huán)境的完整模型。仿真機(jī)器人足球就是這樣的問題，可以采用實(shí)時(shí)動(dòng)態(tài)規(guī)劃方法解決這個(gè)問題。在實(shí)時(shí)動(dòng)態(tài)規(guī)劃中不需要事先給出環(huán)境模型，而是在真實(shí)的環(huán)境中不斷測(cè)試，得到環(huán)境模型。可以采用反傳神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)對(duì)狀態(tài)泛化，網(wǎng)絡(luò)的輸入單元是環(huán)境的狀態(tài)s,

網(wǎng)絡(luò)的輸出是對(duì)該狀態(tài)的評(píng)價(jià)V(s)。2024/11/1331強(qiáng)化學(xué)習(xí)史忠植沒有模型的方法

ModelFreeMethodsModelsoftheenvironment:T:SxA

∏(S)

andR:SxARDoweknowthem?Dowehavetoknowthem?MonteCarloMethodsAdaptiveHeuristicCriticQLearning2024/11/1332強(qiáng)化學(xué)習(xí)史忠植蒙特卡羅方法

MonteCarloMethods

蒙特卡羅方法不需要一個(gè)完整的模型。而是它們對(duì)狀態(tài)的整個(gè)軌道進(jìn)行抽樣，基于抽樣點(diǎn)的最終結(jié)果來更新賦值函數(shù)。蒙特卡羅方法不需要經(jīng)驗(yàn)，即從與環(huán)境聯(lián)機(jī)的或者模擬的交互中抽樣狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)的序列。聯(lián)機(jī)的經(jīng)驗(yàn)是令人感興趣的，因?yàn)樗恍枰h(huán)境的先驗(yàn)知識(shí)，卻仍然可以是最優(yōu)的。從模擬的經(jīng)驗(yàn)中學(xué)習(xí)功能也很強(qiáng)大。它需要一個(gè)模型，但它可以是生成的而不是分析的，即一個(gè)模型可以生成軌道卻不能計(jì)算明確的概率。于是，它不需要產(chǎn)生在動(dòng)態(tài)規(guī)劃中要求的所有可能轉(zhuǎn)變的完整的概率分布。2024/11/1333強(qiáng)化學(xué)習(xí)史忠植MonteCarlo方法TTTTTTTTTTTTTTTTTTTT2024/11/1334強(qiáng)化學(xué)習(xí)史忠植蒙特卡羅方法

MonteCarloMethods

Idea:HoldstatisticsaboutrewardsforeachstateTaketheaverageThisistheV(s)Basedonlyonexperience

Assumesepisodictasks(Experienceisdividedintoepisodesandallepisodeswillterminateregardlessoftheactionsselected.)Incrementalinepisode-by-episodesensenotstep-by-stepsense.2024/11/1335強(qiáng)化學(xué)習(xí)史忠植MonteCarlo策略評(píng)價(jià)Goal:learnVp(s)

underPandRareunknowninadvanceGiven:

somenumberofepisodesunderpwhichcontainsIdea:AveragereturnsobservedaftervisitstosEvery-VisitMC:averagereturnsforeverytimesisvisitedinanepisodeFirst-visitMC:averagereturnsonlyforfirsttimesisvisitedinanepisodeBothconvergeasymptotically123452024/11/1336強(qiáng)化學(xué)習(xí)史忠植Problem:Unvisited<s,a>pairs(problemofmaintainingexploration)Forevery<s,a>makesurethat:P(<s,a>selectedasastartstateandaction)>0(Assumptionofexploringstarts)蒙特卡羅方法

2024/11/1337強(qiáng)化學(xué)習(xí)史忠植蒙特卡羅控制HowtoselectPolicies:(Similartopolicyevaluation)

MCpolicyiteration:PolicyevaluationusingMCmethodsfollowedbypolicyimprovement

Policyimprovementstep:greedifywithrespecttovalue(oraction-value)function2024/11/1338強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)

Temporal-Difference時(shí)序差分學(xué)習(xí)中沒有環(huán)境模型，根據(jù)經(jīng)驗(yàn)學(xué)習(xí)。每步進(jìn)行迭代，不需要等任務(wù)完成。預(yù)測(cè)模型的控制算法，根據(jù)歷史信息判斷將來的輸入和輸出，強(qiáng)調(diào)模型的函數(shù)而非模型的結(jié)構(gòu)。時(shí)序差分方法和蒙特卡羅方法類似，仍然采樣一次學(xué)習(xí)循環(huán)中獲得的瞬時(shí)獎(jiǎng)懲反饋，但同時(shí)類似與動(dòng)態(tài)規(guī)劃方法采用自舉方法估計(jì)狀態(tài)的值函數(shù)。然后通過多次迭代學(xué)習(xí)，去逼近真實(shí)的狀態(tài)值函數(shù)。2024/11/1339強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)

TDTTTTTTTTTTTTTTTTTTTT2024/11/1340強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)

Temporal-Differencetarget:theactualreturnaftertimettarget:anestimateofthereturn2024/11/1341強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)

(TD)Idea:DoADPbackupsonapermovebasis,notforthewholestatespace.Theorem:AveragevalueofU(i)convergestothecorrectvalue.Theorem:Ifisappropriatelydecreasedasafunctionoftimesastateisvisited(=[N[i]]),thenU(i)itselfconvergestothecorrectvalue2024/11/1342強(qiáng)化學(xué)習(xí)史忠植TD(l)–AForwardViewTD(l)isamethodforaveragingalln-stepbackupsweightbyln-1(timesincevisitation)l-return:

Backupusingl-return:2024/11/1343強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)算法

TD()

Idea:updatefromthewholeepoch,notjustonstatetransition.Specialcases: =1:Least-mean-square(LMS),MontCarlo =0:TDIntermediatechoiceof(between0and1)isbest.Interplaywith…2024/11/1344強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)算法

TD()

算法10.1TD(0)學(xué)習(xí)算法InitializeV(s)arbitrarily,πtothepolicytobeevaluatedRepeat(foreachepisode)InitializesRepeat(foreachstepofepisode)ChooseafromsusingpolicyπderivedfromV(e.g.,ε-greedy)Takeactiona,observerr,s′

Untilsisterminal2024/11/1345強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)算法2024/11/1346強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)算法收斂性TD(

)Theorem:Convergesw.p.1undercertainboundariesconditions.Decrease

i(t)s.t.Inpractice,oftenafixedisusedforalliandt.2024/11/1347強(qiáng)化學(xué)習(xí)史忠植時(shí)序差分學(xué)習(xí)

TD2024/11/1348強(qiáng)化學(xué)習(xí)史忠植Q-learningWatkins,1989在Q學(xué)習(xí)中，回溯從動(dòng)作結(jié)點(diǎn)開始，最大化下一個(gè)狀態(tài)的所有可能動(dòng)作和它們的獎(jiǎng)勵(lì)。在完全遞歸定義的Q學(xué)習(xí)中，回溯樹的底部結(jié)點(diǎn)一個(gè)從根結(jié)點(diǎn)開始的動(dòng)作和它們的后繼動(dòng)作的獎(jiǎng)勵(lì)的序列可以到達(dá)的所有終端結(jié)點(diǎn)。聯(lián)機(jī)的Q學(xué)習(xí)，從可能的動(dòng)作向前擴(kuò)展，不需要建立一個(gè)完全的世界模型。Q學(xué)習(xí)還可以脫機(jī)執(zhí)行。我們可以看到，Q學(xué)習(xí)是一種時(shí)序差分的方法。2024/11/1349強(qiáng)化學(xué)習(xí)史忠植Q-learning在Q學(xué)習(xí)中，Q是狀態(tài)-動(dòng)作對(duì)到學(xué)習(xí)到的值的一個(gè)函數(shù)。對(duì)所有的狀態(tài)和動(dòng)作：Q:(statexaction)→value對(duì)Q學(xué)習(xí)中的一步：(10.15)其中c和γ都≤1，rt+1是狀態(tài)st+1的獎(jiǎng)勵(lì)。

2024/11/1350強(qiáng)化學(xué)習(xí)史忠植Q-LearningEstimatetheQ-functionusingsomeapproximator(forexample,linearregressionorneuralnetworksordecisiontreesetc.).DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedQ-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2024/11/1351強(qiáng)化學(xué)習(xí)史忠植Q-learningQ(a,i)Directapproach(ADP)wouldrequirelearningamodel.Q-learningdoesnot:Dothisupdateaftereachstatetransition:2024/11/1352強(qiáng)化學(xué)習(xí)史忠植ExplorationTradeoffbetweenexploitation(control)andexploration(identification)Extremes:greedyvs.randomacting (n-armedbanditmodels)Q-learningconvergestooptimalQ-valuesif*Everystateisvisitedinfinitelyoften(duetoexploration),*Theactionselectionbecomesgreedyastimeapproachesinfinity,and*Thelearningrateaisdecreasedfastenoughbutnottoofast (aswediscussedinTDlearning)2024/11/1353強(qiáng)化學(xué)習(xí)史忠植CommonexplorationmethodsInvalueiterationinanADPagent:OptimisticestimateofutilityU+(i)?-greedymethodNongreedyactionsGreedyactionBoltzmannexplorationExplorationfuncR+ifn<Nuo.w.2024/11/1354強(qiáng)化學(xué)習(xí)史忠植Q-LearningAlgorithmQ學(xué)習(xí)算法InitializeQ(s,a)arbitrarilyRepeat(foreachepisode)InitializesRepeat(foreachstepofepisode)ChooseafromsusingpolicyderivedfromQ(e.g.,ε-greedy)Takeactiona,observerr,s′

Untilsisterminal2024/11/1355強(qiáng)化學(xué)習(xí)史忠植Q-LearningAlgorithmSetForTheestimatedpolicysatisfies2024/11/1356強(qiáng)化學(xué)習(xí)史忠植Whatistheintuition?BellmanequationgivesIfandthetrainingsetwereinfinite,thenQ-learningminimizeswhichisequivalenttominimizing2024/11/1357強(qiáng)化學(xué)習(xí)史忠植A-Learning

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

(InefficientVersion)ForTheestimatedpolicysatisfies2024/11/1359強(qiáng)化學(xué)習(xí)史忠植DifferencesbetweenQandA-learningQ-learningAttimetwemodelthemaineffectsofthehistory,(St,,At-1)andtheactionAtandtheirinteractionOurYt-1isaffectedbyhowwemodeledthemaineffectofthehistoryintimet,(St,,At-1)

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

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

Ratherthanobservingthestateweobservesomefunctionofthestate.Ob–Observablefunction arandomvariableforeachstates.Problem:differentstatesmaylooksimilarTheoptimalstrategymightneedtoconsiderthehistory.2024/11/1362強(qiáng)化學(xué)習(xí)史忠植FrameworkofPOMDP

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

Ω可以是S的子集，也可以與S無(wú)關(guān)2024/11/1363強(qiáng)化學(xué)習(xí)史忠植POMDPsWhatifstateinformation(fromsensors)isnoisy?Mostlythecase!MDPtechniquesaresuboptimal!Twohallsarenotthesame.2024/11/1364強(qiáng)化學(xué)習(xí)史忠植POMDPs–ASolutionStrategySE:BeliefStateEstimator(CanbebasedonHMM)П:MDPTechniques2024/11/1365強(qiáng)化學(xué)習(xí)史忠植POMDP_信度狀態(tài)方法Idea:Givenahistoryofactionsandobservablevalue,wecomputeaposteriordistributionforthestatewearein(beliefstate)Thebelief-stateMDPStates:distributionoverS(statesofthePOMDP)Actions:asinPOMDPTransition:theposteriordistribution(giventheobservation)OpenProblem:Howtodealwiththecontinuousdistribution?2024/11/1366強(qiáng)化學(xué)習(xí)史忠植TheLearningProcessofBeliefMDP2024/11/1367強(qiáng)化學(xué)習(xí)史忠植MajorMethodstoSolvePOMDP

算法名稱基本思想學(xué)習(xí)值函數(shù)Memorylesspolicies直接采用標(biāo)準(zhǔn)的強(qiáng)化學(xué)習(xí)算法Simplememorybasedapproaches使用k個(gè)歷史觀察表示當(dāng)前狀態(tài)UDM(UtileDistinctionMemory)分解狀態(tài)，構(gòu)建有限狀態(tài)機(jī)模型NSM(NearestSequenceMemory)存儲(chǔ)狀態(tài)歷史，進(jìn)行距離度量USM(UtileSuffixMemory)綜合UDM和NSM兩種方法Recurrent-Q使用循環(huán)神經(jīng)網(wǎng)絡(luò)進(jìn)行狀態(tài)預(yù)測(cè)策略搜索Evolutionaryalgorithms使用遺傳算法直接進(jìn)行策略搜索Gradientascentmethod使用梯度下降（上升）法搜索2024/11/1368強(qiáng)化學(xué)習(xí)史忠植強(qiáng)化學(xué)習(xí)中的函數(shù)估計(jì)RLFASubsetofstatesValueestimateastargetsV(s)GeneralizationofthevaluefunctiontotheentirestatespaceistheTDoperator.isthefunctionapproximationoperator.2024/11/1369強(qiáng)化學(xué)習(xí)史忠植并行兩個(gè)迭代過程值函數(shù)迭代過程值函數(shù)逼近過程HowtoconstructtheMfunction?Usingstatecluster,interpolation,decisiontreeorneuralnetwork?2024/11/1370強(qiáng)化學(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?并行兩個(gè)迭代過程2024/11/1371強(qiáng)化學(xué)習(xí)史忠植Semi-MDPDiscretetimeHomogeneousdiscountContinuoustimeDiscreteeventsInterval-dependentdiscountDiscretetimeDiscreteeventsInterval-dependentdiscountAdiscrete-timeSMDPoverlaidonanMDPCanbeanalyzedateitherlevel.OneapproachtoTemporalHierarchicalRL2024/11/1372強(qiáng)化學(xué)習(xí)史忠植Theequations2024/11/1373強(qiáng)化學(xué)習(xí)史忠植Multi-agentMDPDistributedRLMarkovGameBestResponseEnvironmentactionstaterewardRLAgentRLAgent2024/11/1374強(qiáng)化學(xué)習(xí)史忠植三種觀點(diǎn)問題空間主要方法算法準(zhǔn)則合作多agent強(qiáng)化學(xué)習(xí)分布、同構(gòu)、合作環(huán)境交換狀態(tài)提高學(xué)習(xí)收斂速度交換經(jīng)驗(yàn)交換策略交換建議基于平衡解多agent強(qiáng)化學(xué)習(xí)同構(gòu)或異構(gòu)、合作或競(jìng)爭(zhēng)環(huán)境極小極大-Q理性和收斂性NASH-QCE-QWoLF最佳響應(yīng)多agent強(qiáng)化學(xué)習(xí)異構(gòu)、競(jìng)爭(zhēng)環(huán)境PHC收斂性和不遺憾性IGAGIGAGIGA-WoLF2024/11/1375強(qiáng)化學(xué)習(xí)史忠植馬爾可夫?qū)Σ咴趎個(gè)agent的系統(tǒng)中，定義離散的狀態(tài)集S（即對(duì)策集合G），agent動(dòng)作集Ai的集合A,聯(lián)合獎(jiǎng)賞函數(shù)Ri：S×A1×…×An→?和狀態(tài)轉(zhuǎn)移函數(shù)P：S×A1×…×An→PD（S）。

2024/11/1376強(qiáng)化學(xué)習(xí)史忠植基于平衡解方法的強(qiáng)化學(xué)習(xí)OpenProblem:Nashequilibriumorotherequilibriumisenough?TheoptimalpolicyinsinglegameisNashequilibrium.2024/11/1377強(qiáng)化學(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/11/1378強(qiáng)化學(xué)習(xí)史忠植仿真機(jī)器人足球應(yīng)用Q學(xué)習(xí)算法進(jìn)行仿真機(jī)器人足球2對(duì)1訓(xùn)練，訓(xùn)練的目的是試圖使主體學(xué)習(xí)獲得到一種戰(zhàn)略上的意識(shí)，能夠在進(jìn)攻中進(jìn)行配合

2024/11/1379強(qiáng)化學(xué)習(xí)史忠植仿真機(jī)器人足球前鋒A控球，并且在可射門的區(qū)域內(nèi)，但是A已經(jīng)沒有射門角度了；隊(duì)友B也處于射門區(qū)域，并且B具有良好的射門角度。A傳球給B，射門由B來完成，那么這次進(jìn)攻配合就會(huì)很成功。通過