電子商務技術

內容提要引言強化學習模型動態(tài)規(guī)劃蒙特卡羅方法時序差分學習Q學習強化學習中的函數(shù)估計應用2/7/2024強化學習史忠植1引言

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

2/7/2024強化學習史忠植2引言

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

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

Or,withouttheexpectationoperator:isthediscountrate2/7/2024強化學習史忠植12Bellman最優(yōu)策略公式其中：V*：狀態(tài)值映射S：環(huán)境狀態(tài)R：獎勵函數(shù)P：狀態(tài)轉移概率函數(shù)：折扣因子2/7/2024強化學習史忠植13MARKOVDECISIONPROCESS

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

RAstatetransitionfunction:T:SxA

∏(S)

T(s,a,s’):probabilityoftransitionfromstos’usingactiona2/7/2024強化學習史忠植14MDPEXAMPLE:TransitionfunctionStatesandrewardsBellman

Equation:(Greedypolicyselection)2/7/2024強化學習史忠植15MDPGraphicalRepresentationβ,α:T(s,action,s’)SimilaritytoHiddenMarkovModels(HMMs)2/7/2024強化學習史忠植16動態(tài)規(guī)劃

DynamicProgramming-ProblemAdiscrete-timedynamicsystemStates{1,…,n}+terminationstate0ControlU(i)TransitionProbabilitypij(u)AccumulativecoststructurePolicies2/7/2024強化學習史忠植17FiniteHorizonProblemInfiniteHorizonProblemValueIteration動態(tài)規(guī)劃

DynamicProgramming–IterativeSolution

2/7/2024強化學習史忠植18動態(tài)規(guī)劃中的策略迭代/值迭代policyevaluationpolicyimprovement“greedification”PolicyIterationValueIteration2/7/2024強化學習史忠植19動態(tài)規(guī)劃方法TTTTTTTTTTTTT2/7/2024強化學習史忠植20自適應動態(tài)規(guī)劃(ADP)Idea:usetheconstraints(statetransitionprobabilities)betweenstatestospeedlearning.Solve

=valuedetermination.Nomaximizationoveractionsbecauseagentispassiveunlikeinvalueiteration.usingDPLargestatespacee.g.Backgammon:1050equationsin1050variables2/7/2024強化學習史忠植21ValueIterationAlgorithmANALTERNATIVEITERATION:(Singh,1993)(Importantformodelfreelearning)StopIterationwhenV(s)differslessthan?.Policydifferenceratio=<2?γ/(1-γ)

(Williams&Baird1993b)2/7/2024強化學習史忠植22PolicyIterationAlgorithm

Policiesconvergefasterthanvalues.Whyfasterconvergence?

2/7/2024強化學習史忠植23ReinforcementLearning

…DeterministictransitionsStochastictransitionsistheprobabilitytoreachingstatejwhentakingactionainstateistart3211234+1-1Asimpleenvironmentthatpresentstheagentwithasequentialdecisionproblem:Movecost=0.04(Temporal)creditassignmentproblemsparsereinforcementproblemOfflinealg:actionsequencesdeterminedexanteOnlinealg:actionsequencesisconditionalonobservationsalongtheway;Importantinstochasticenvironment(e.g.jetflying)2/7/2024強化學習史忠植24ReinforcementLearning

…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.2/7/2024強化學習史忠植25ModelFreeMethodsModelsoftheenvironment:T:SxA

∏(S)

andR:SxARDoweknowthem?Dowehavetoknowthem?MonteCarloMethodsAdaptiveHeuristicCriticQLearning2/7/2024強化學習史忠植26MonteCarlo策略評價Goal:learnVp(s)

underPandRareunknowninadvanceGiven:

somenumberofepisodesunderpwhichcontainsIdea:AveragereturnsobservedaftervisitstosEvery-VisitMC:averagereturnsforeverytimesisvisitedinanepisodeFirst-visitMC:averagereturnsonlyforfirsttimesisvisitedinanepisodeBothconvergeasymptotically123452/7/2024強化學習史忠植27蒙特卡羅方法

MonteCarloMethods

Idea:HoldstatisticsaboutrewardsforeachstateTaketheaverageThisistheV(s)Basedonlyonexperience

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

2/7/2024強化學習史忠植29MonteCarlo方法TTTTTTTTTTTTTTTTTTTT2/7/2024強化學習史忠植30蒙特卡羅控制HowtoselectPolicies:(Similartopolicyevaluation)

MCpolicyiteration:PolicyevaluationusingMCmethodsfollowedbypolicyimprovement

Policyimprovementstep:greedifywithrespecttovalue(oraction-value)function2/7/2024強化學習史忠植31時序差分學習

Temporal-Differencetarget:theactualreturnaftertimettarget:anestimateofthereturn2/7/2024強化學習史忠植32時序差分學習

(TD)Idea:DoADPbackupsonapermovebasis,notforthewholestatespace.Theorem:AveragevalueofU(i)convergestothecorrectvalue.Theorem:Ifisappropriatelydecreasedasafunctionoftimesastateisvisited(=[N[i]]),thenU(i)itselfconvergestothecorrectvalue2/7/2024強化學習史忠植33時序差分學習

TDTTTTTTTTTTTTTTTTTTTT2/7/2024強化學習史忠植34TD(l)–AForwardViewTD(l)isamethodforaveragingalln-stepbackupsweightbyln-1(timesincevisitation)l-return:

Backupusingl-return:2/7/2024強化學習史忠植35時序差分學習算法

TD()

Idea:updatefromthewholeepoch,notjustonstatetransition.Specialcases: =1:Least-mean-square(LMS),MontCarlo =0:TDIntermediatechoiceof(between0and1)isbest.Interplaywith…2/7/2024強化學習史忠植36時序差分學習算法

TD()

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

Untilsisterminal2/7/2024強化學習史忠植37時序差分學習算法2/7/2024強化學習史忠植38時序差分學習算法收斂性TD(

)Theorem:Convergesw.p.1undercertainboundariesconditions.Decrease

i(t)s.t.Inpractice,oftenafixedisusedforalliandt.2/7/2024強化學習史忠植39時序差分學習

TD2/7/2024強化學習史忠植40Q-LearningWatkins,1989EstimatetheQ-functionusingsomeapproximator(forexample,linearregressionorneuralnetworksordecisiontreesetc.).DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedQ-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2/7/2024強化學習史忠植41Q-learningQ(a,i)Directapproach(ADP)wouldrequirelearningamodel.Q-learningdoesnot:Dothisupdateaftereachstatetransition:2/7/2024強化學習史忠植42ExplorationTradeoffbetweenexploitation(control)andexploration(identification)Extremes:greedyvs.randomacting (n-armedbanditmodels)Q-learningconvergestooptimalQ-valuesif*Everystateisvisitedinfinitelyoften(duetoexploration),*Theactionselectionbecomesgreedyastimeapproachesinfinity,and*Thelearningrateaisdecreasedfastenoughbutnottoofast (aswediscussedinTDlearning)2/7/2024強化學習史忠植43CommonexplorationmethodsInvalueiterationinanADPagent:OptimisticestimateofutilityU+(i)?-greedymethodNongreedyactionsGreedyactionBoltzmannexplorationExplorationfuncR+ifn<Nuo.w.2/7/2024強化學習史忠植44Q-LearningAlgorithmSetForTheestimatedpolicysatisfies2/7/2024強化學習史忠植45Whatistheintuition?BellmanequationgivesIfandthetrainingsetwereinfinite,thenQ-learningminimizeswhichisequivalenttominimizing2/7/2024強化學習史忠植46A-Learning

Murphy,2003andRobins,2004EstimatetheA-function(advantages)usingsomeapproximator,asinQ-learning.DerivetheestimatedpolicyasanargumentofthemaximumoftheestimatedA-function.Allowdifferentparametervectorsatdifferenttimepoints.Letusillustratethealgorithmwithlinearregressionastheapproximator,andofcourse,squarederrorastheappropriatelossfunction.2/7/2024強化學習史忠植47A-LearningAlgorithm

(InefficientVersion)ForTheestimatedpolicysatisfies2/7/2024強化學習史忠植48DifferencesbetweenQandA-learningQ-learningAttimetwemodelthemaineffectsofthehistory,(St,,At-1)andtheactionAtandtheirinteractionOurYt-1isaffectedbyhowwemodeledthemaineffectofthehistoryintimet,(St,,At-1)

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

2/7/2024強化學習史忠植49Q-LearningVs.A-LearningRelativemeritsanddemeritsarenotcompletelyknowntillnow.Q-learninghaslowvariancebuthighbias.A-learninghashighvariancebutlowbias.ComparisonofQ-learningwithA-learninginvolvesabias-variancetrade-off.2/7/2024強化學習史忠植50POMDP部分感知馬氏決策過程

Ratherthanobservingthestateweobservesomefunctionofthestate.Ob–Observablefunction arandomvariableforeachstates.Problem:differentstatesmaylooksimilarTheoptimalstrategymightneedtoconsiderthehistory.2/7/2024強化學習史忠植51FrameworkofPOMDP

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

Ω可以是S的子集，也可以與S無關2/7/2024強化學習史忠植52POMDPsWhatifstateinformation(fromsensors)isnoisy?Mostlythecase!MDPtechniquesaresuboptimal!Twohallsarenotthesame.2/7/2024強化學習史忠植53POMDPs–ASolutionStrategySE:BeliefStateEstimator(CanbebasedonHMM)П:MDPTechniques2/7/2024強化學習史忠植54POMDP_信度狀態(tài)方法Idea:Givenahistoryofactionsandobservablevalue,wecomputeaposteriordistributionforthestatewearein(beliefstate)Thebelief-stateMDPStates:distributionoverS(statesofthePOMDP)Actions:asinPOMDPTransition:theposteriordistribution(giventheobservation)OpenProblem:Howtodealwiththecontinuousdistribution?2/7/2024強化學習史忠植55TheLearningProcessofBeliefMDP2/7/2024強化學習史忠植56MajorMethodstoSolvePOMDP

算法名稱基本思想學習值函數(shù)Memorylesspolicies直接采用標準的強化學習算法Simplememorybasedapproaches使用k個歷史觀察表示當前狀態(tài)UDM(UtileDistinctionMemory)分解狀態(tài)，構建有限狀態(tài)機模型NSM(NearestSequenceMemory)存儲狀態(tài)歷史，進行距離度量USM(UtileSuffixMemory)綜合UDM和NSM兩種方法Recurrent-Q使用循環(huán)神經(jīng)網(wǎng)絡進行狀態(tài)預測策略搜索Evolutionaryalgorithms使用遺傳算法直接進行策略搜索Gradientascentmethod使用梯度下降（上升）法搜索2/7/2024強化學習史忠植57強化學習中的函數(shù)估計RLFASubsetofstatesValueestimateastargetsV(s)GeneralizationofthevaluefunctiontotheentirestatespaceistheTDoperator.isthefunctionapproximationoperator.2/7/2024強化學習史忠植58并行兩個迭代過程值函數(shù)迭代過程值函數(shù)逼近過程HowtoconstructtheMfunction?Usingstatecluster,interpolation,decisiontreeorneuralnetwork?2/7/2024強化學習史忠植59FunctionApproximator:

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?并行兩個迭代過程2/7/2024強化學習史忠植60Semi-MDPDiscretetimeHomogeneousdiscountContinuoustimeDiscreteeventsInterval-dependentdiscountDiscretetimeDiscreteeventsInterval-dependentdiscountAdiscrete-timeSMDPoverlaidonanMDPCanbeanalyzedateitherlevel.OneapproachtoTemporalHierarchicalRL2/7/2024強化學習史忠植61Theequations2/7/2024強化學習史忠植62Multi-agentMDPDistributedRLMarkovGameBestResponseEnvironmentactionstaterewardRLAgentRLAgent2/7/2024強化學習史忠植63三種觀點問題空間主要方法算法準則合作多agent強化學習分布、同構、合作環(huán)境交換狀態(tài)提高學習收斂速度交換經(jīng)驗交換策略交換建議基于平衡解多agent強化學習同構或異構、合作或競爭環(huán)境極小極大-Q理性和收斂性NASH-QCE-QWoLF最佳響應多agent強化學習異構、競爭環(huán)境PHC收斂性和不遺憾性IGAGIGAGIGA-WoLF2/7/2024強化學習史忠植64馬爾可夫對策在n個agent的系統(tǒng)中，定義離散的狀態(tài)集S（即對策集合G），agent動作集Ai的集合A,聯(lián)合獎賞函數(shù)Ri：S×A1×…×An→?和狀態(tài)轉移函數(shù)P：S×A1×…×An→PD（S）。

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

狀態(tài)描述，將進攻禁區(qū)劃分為個小區(qū)域，每個小區(qū)域是邊長為2m的正方形，一個二維數(shù)組()便可描述這個區(qū)域。使用三個Agent的位置來描述2對1進攻