资源描述：
《a note on bandits with a twist》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ANOTEONBANDITSWITHATWISTAKSHAY-KUMARKATTA∗ANDJAYSETHURAMAN†Abstract.Avariantofthemulti-armedbanditproblemwasrecentlyintroducedbyDimitriu,TetaliandWinkler.Forthismodel(andamildgeneralization)weproposefasteralgorithmstocomputetheGittinsindex.Theindexabilityofsuchmodelsfollowsfromearlier
2、workofNashongeneralizedbandits.Keywords.Multiarmedbanditproblem,generalizedbanditproblem,stochasticscheduling,priorityrule,Gittinsindex,gameAMSsubjectclassifications.60J10,66C99,60G40,90B35,90C401.Introduction.Themulti-armedbanditproblemisawellstudiedoptimiza-tionproblemconcernedwithdy
3、namicallyallocatingasingleresourceamongstseveralcompetingprojects.Inthebasicversionofthisproblem,thereareNindependentprojects,eachofwhichcanbeinoneofmanypossiblestates.Ateacht=1,2,...,wemustoperateexactlyoneoftheprojects;asaresult,weearna(possiblyrandom)rewardthatmaydependonthestateof
4、theoperatedproject,whichundergoesaMarkovianstatetransition.Thestatesofalltheotherprojectsremainfrozen.Futureearningsarediscountedbyafactorβ,andourobjectiveistodecidetheorderinwhichwemustoperatethevariousprojectstomaximizetheexpectedtotaldiscountedre-wardearned.GittinsandJones[7]showed
5、thattoeachprojecti,wecanattachanindexwhichdependsonlyonthestateofprojecti,andisindependentofthestatesofalltheotherprojects,andthatoperatingaprojectwiththelargestindexatanypointintimeisoptimal.(Suchproblemsaresaidtobeindexable.)Sincetheiroriginalproof,manyalternativeandinsightfulproofs
6、haveappeared,see[14,10,12,5,9,11,1,3].Inaddition,severalnaturalextensionsandvariationsofthebasicmulti-armedbanditmodelhavebeenconsidered,see[8,14,15,13,2].EspeciallyrelevanttothisworkisthegeneralizedbanditmodelofNash[8],whichconsidersaclassofbanditproblemswithamoregeneralrewardstructu
7、re.Insuchamodel,therewardobtainedfromatransitioninoneprojectdependsinamultiplicativelyseparablewayonthestatesofalltheotherprojects.Nash[8]provedthatthismoregeneralclassofbanditproblemsisindexable.Inthispaperweconsideravariantofthemulti-armedbanditproblemthathasbeenrecentlyintroducedin
8、[4].H
