Hidden-mode markov decision processes for nonstati

Hidden-ModeMarkovDecisionProcessesforNonstationarySequentialDecisionMakingSamuelP.M.Choi,Dit-YanYeung,andNevinL.ZhangDepartmentofComputerScience,HongKongUniversityofScienceandTechnologyClearWaterBay,Kowloon,HongKongfpmchoi,dyyeung,[e-mail]1IntroductionProblemformulationisoftenanimportantrststepforsolvingaproblemeec-tively.Insequentialdecisionproblems,Markovdecisionprocess(MDP)(Bellman1957b;Puterman1994)isamodelformulationthathasbeencommonlyused,duetoitsgenerality,exibility,andapplicabilitytoawiderangeofproblems.Despitetheseadvantages,therearethreenecessaryconditionsthatmustbesatisedbeforetheMDPmodelcanbeapplied;thatis,1.Theenvironmentmodelisgiveninadvance(acompletely-knownenviron-ment).2.Theenvironmentstatesarecompletelyobservable(fully-observablestates,implyingaMarkovianenvironment).3.Theenvironmentparametersdonotchangeovertime(astationaryenviron-ment).Theseprerequisites,however,limittheusefulnessofMDPs.Inthepast,re-searcheortshavebeenmadetowardsrelaxingthersttwoconditions,leadingtodierentclassesofproblemsasillustratedinFigure1.EnvironmentObservablePartiallyObservableCompletelyStatesofObservableMDPMDPKnownPartiallyUnknownModelofEnvironmentTraditionalRLHidden-stateRLFig.1.Categorizationintofourrelatedproblemswithdierentconditions.Notethatthedegreeofdicultyincreasesfromlefttorightandfromuppertolower.Thispapermainlyaddressestherstandthirdconditions,whereasthesec-ondconditionisonlybrieydiscussed.Inparticular,weareinterestedinaspe-cialtypeofnonstationaryenvironmentsthatrepeattheirdynamicsinacertainmanner.Weproposeaformalmodelforsuchenvironments.Wealsodevelopal-gorithmsforlearningthemodelparametersandforcomputingoptimalpolicies.Beforeweproceed,letusbrieyreviewthefourcategoriesofproblemsshowninFigure1anddenetheterminologythatwillbeusedinthispaper.1.1FourProblemTypesMarkovDecisionProcessMDPisthecentralframeworkforalltheproblemswediscussinthissection.AnMDPformulatestheinteractionbetweenanagentanditsenvironment.Theenvironmentconsistsofastatespace,anactionspace,aprobabilisticstatetran-sitionfunction,andaprobabilisticrewardfunction.Thegoaloftheagentistond,accordingtoitsoptimalitycriterion,amappingfromstatestoactions(i.e.policy)thatmaximizesthelong-termaccumulatedrewards.Thispolicyiscalledanoptimalpolicy.Inthepast,severalmethodsforsolvingMarkovdecisionprob-lemshavebeendeveloped,suchasvalueiterationandpolicyiteration(Bellman1957a).ReinforcementLearningReinforcementlearning(RL)(Kaelblingetal.1996;SuttonandBarto1998)isoriginallyconcernedwithlearningtoperformasequentialdecisiontaskbasedonlyonscalarfeedbacks,withoutanyknowledgeaboutwhatthecorrectac-tionsshouldbe.AroundadecadeagoresearchersrealizedthatRLproblemscouldnaturallybeformulatedintoincompletelyknownMDPs.ThisrealizationisimportantbecauseitenablesonetoapplyexistingMDPalgorithmstoRLproblems.Thishasledtoresearchonmodel-basedRL.Themodel-basedRLap-proachrstreconstructstheenvironmentmodelbycollectingexperiencefromitsinteractionwiththeworld,andthenappliesconventionalMDPmethodstondasolution.Onthecontrary,model-freeRLlearnsanoptimalpolicydirectlyfromtheexperience.Itisthissecondapproachthataccountsforthemajordif-ferencebetweenRLandMDPalgorithms.Sincelessinformationisavailable,RLproblemsareingeneralmoredicultthantheMDPones.PartiallyObservableMarkovDecisionProcessTheassumptionofhavingfully-observablestatesissometimesimpracticalintherealworld.Inaccuratesensorydevices,forexample,couldmakethiscon-ditiondiculttoholdtrue.ThisconcernleadstostudiesonextendingMDPtopartially-observableMDP(POMDP)(Monahan1982;Lovejoy1991;WhiteIII1991).APOMDPbasicallyintroducestwoadditionalcomponentstotheoriginalMDP,i.e.anobservationspaceandanobservationprobabilityfunction.Observationsaregeneratedbasedonthecurrentstateandthepreviousaction,andaregovernedbytheobservationfunction.Theagentisonlyabletoperceiveobservations,butnotstatesthemselves.Asaresult,pastobservationsbecomerelevanttotheagent’schoiceofactions.Hence,POMDPsaresometimesreferredtoasnon-MarkovianMDPs.TraditionalapproachestoPOMDPs(Sondik1971;Cheng1998;Littmanetal.1995b;Cassandraetal.1997;Zhangetal.1997)main-tainaprobabilitydistributionoverthestates,calledbeliefstate.ItessentiallytransformstheproblemintoanMDPonewithanaugmented(andcontinuous)statespace.Unfortunately,solvingPOMDPproblemsexactlyisknowntobeintractableingeneral(PapadimitriouandTsitsiklis1987;Littmanetal.1995a).Hidden-StateReinforcementLearningRecently,researchhasbeenconductedonthecasewheretheenvironmentisbothincompletelyknownandpartiallyobservable.Thistypeofproblemsissometimesreferredtoashidden-statereinforcementlearning,incompleteper-ception,perceptionaliasing,ornon-Markovianreinforcementlearning.Hidden-stateRLalgorithmscanalsobeclassiedintomodel-basedandmodel-freeap-proaches.Fortheformer,avariantoftheBaum-Welchalgorithm(Chrisman1992)istypicallyusedformodelreconstruction,andhenceturnstheproblemintoaconventionalPOMDP.OptimalpoliciescanthenbecomputedbyusingexistingPOMDPalgorithms.Forthelatter,researcheortsarediverse,rangingfromstate-freestochasticpolicy(Jaakkol