A Simulation-Based Algorithm for Ergodic Control o

ASimulation-BasedAlgorithmforErgodicControlofMarkovChainsConditionedonRareEventsS.Bhatnagary,V.S.BorkarzandA.MadhukarxFebruary2006AbstractWestudytheproblemoflong-runaveragecostcontrolofMarkovchainsconditionedonarareevent.Inarelatedrecentwork,asimulationbasedalgorithmforestimatingperformancemeasuresassociatedwithaMarkovchainconditionedonarareeventhasbeendeveloped.Weextendideasfromthisworkanddevelopanadaptivealgorithmforobtaining,online,optimalcontrolpoliciesconditionedonarareevent.Ouralgorithmusesthreetimescalesorstep-sizeschedules.Ontheslowesttimescale,agradientsearchalgorithmforpolicyupdatesthatisbasedonone-simulationsimultaneousperturbationstochasticapproximation(SPSA)typeestimatesisused.DeterministicperturbationsequencesobtainedfromappropriatenormalizedHadamardmatricesareusedhere.Thefasttimescalerecursionscomputetheconditionaltransitionproba-bilitiesofanassociatedchainbyobtainingsolutionstothemultiplicativePoissonequation(foragivenpolicyestimate).Further,theriskparameterassociatedwiththevaluefunctionforagivenpolicyestimateisupdatedonatimescalethatliesinbetweenthetwoscalesabove.Webrieysketchtheconvergenceanalysisofouralgorithmandpresentanumericalapplicationinthesettingofroutingmultipleowsincommunicationnetworks.KeyWords:Markovdecisionprocesses,optimalcontrolconditionedonarareevent,simulationbasedalgorithms,SPSAwithdeterministicperturbations,reinforcementlearning.1IntroductionMarkovdecisionprocesses(MDPs)[5],[35]formageneralframeworkforstudyingproblemsofcontrolofstochasticdynamicsystems(SDS).Manytimes,oneencounterssituationsinvolvingcontrolofSDSconditionedonarareeventofasymptoticallyzeroprobability.Thiscouldbe,e.g.,aproblemofdamagecontrolwhenfacedwithacatastrophicevent.Forinstance,inthesettingofalargecommunicationnetworksuchastheinternet,onemaybeinterestedinobtainingoptimalowCorrespondingauthoryDepartmentofComputerScienceandAutomation,IndianInstituteofScience,Bangalore560012,India.E-Mail:[e-mail]ComputerScience,TataInstituteofFundamentalResearch,HomiBhabhaRoad,Mumbai400005,India.E-Mail:[e-mail]lEngineering,IndianInstituteofScience,Bangalore560012,India.E-Mail:[e-mail]1andcongestioncontrolorroutingstrategiesinasubnetworkgiventhatanextremaleventsuchasalinkfailurehasoccurredinanotherremotesubnetwork.OurobjectiveinthispaperistoconsideraproblemofthisnaturewhereinarareeventisspecicallydenedtobethetimeaverageofafunctionoftheMDPanditsassociatedcontrol-valuedprocessexceedingathresholdthatislargerthanitsmean.Weconsidertheinnitehorizonlong-runaveragecostcriterionforourproblemanddeviseanalgorithmbasedonpolicyiterationforthesame.ResearchondevelopingsimulationbasedmethodsforcontrolofSDShasgatheredmomentuminrecenttimes.Theselargelygounderthenamesofneuro-dynamicprogramming(NDP)[7]orreinforcementlearning(RL)[39]andareapplicableinthecaseofsystemsforwhichmodelinformationisnotknownorcomputationallyforbiddinglyexpensive,butoutputdataobtainedeitherthrougharealsystemorasimulatedoneisavailable.Ourproblemdoesnotsharethislastfeature,butwedoborrowcertainalgorithmicparadigmsfromthisliterature.Beforeweproceedfurther,werstreviewsomerepresentativerecentworkalongtheselines.In[3],analgorithmforlong-runaveragecostMDPsispresented.TheaveragecostgradientisapproximatedusingthatassociatedwithacorrespondinginnitehorizondiscountedcostMDPproblem.Thevarianceoftheestimateshoweverincreasesrapidlyasthediscountfactorisbroughtclosertoone.In[4],certainvariantsbasedonthealgorithmin[3]arepresentedandapplicationsonsomeexperimentalsettingsshown.In[25],aperturbationanalysis(PA)typeapproachisusedtoobtaintheperformancegradientbasedonsamplepathanalysis.In[24],aPA-basedmethodisproposedforsolvinglong-runaveragecostMDPs.Thisrequireskeepingtrackoftheregenerationepochsoftheunderlyingprocessforanypolicyandaggregatingdataoverthese.Theaboveepochscanhoweverbeveryinfrequentinmostreallifesystems.In[32],theaveragecostgradientiscomputedbyassumingthatsamplepathgradientsofperformanceandtransitionprobabilitiesareknowninfunctionalform.AmongstotherRL-basedapproaches,thetemporaldierence(TD)[39]andQ-learning[42]havebeenpopularinrecenttimes.Thesearebasedonvaluefunctionapproximations.Aparalleldevelopmentisthatofactor-criticalgorithmsbasedontheclassicalpolicyiterationalgorithmindynamicprogramming.Notethattheclassicalpolicyiterationalgorithmproceedsviatwonestedloops{anouterloopinwhichthepolicyimprovementstepisperformedandaninnerloopinwhichthepolicyevaluationstepforthepolicyprescribedbytheouterloopisconducted.Therespectiveoperationsinthetwoloopsareperformedone-after-the-otherinacyclicmanner.Theinnerloopcaninprincipletakealongtimetoconverge,makingtheoverallprocedureslowinpractice.In[29],certainsimulation-basedalgorithmsthatusemulti-timescalestochasticapproximationareproposed.Theideaistousecoupledstochasticrecursionsdrivenbydierentstep-sizeschedulesortimescales.Therecursioncorrespondingtopolicyevaluationisrunonthefastertimescalewhile2thatcorrespondingtopolicyimprovementisrunontheslowerone.Thus