Vi studerar det tvåarmade banditproblemet med subgaussiska belöningar. Strategin Explore-then-commit (ETC), som består av en prospekteringsfas följt av en exploateringsfas, är en av de mest använda algoritmerna i en mängd olika online-beslutstillämpningar. Ändå har det visat sig att ETC är suboptimal i asymptotisk betydelse när horisonten växer, och därmed är värre än helt sekventiella strategier såsom Övre förtroende Bound (UCB). I detta dokument hävdar vi att en variant av ETC-algoritm faktiskt kan uppnå asymptotiskt optimala ångergränser för multi-armade bandit problem som UCB-typ algoritmer gör. I synnerhet föreslår vi en algoritm med dubbla utforska-då-åtaganden (DETC) som har två prospekterings- och exploateringsfaser. Vi bevisar att DETC uppnår den asymptotiska optimal ånger bunden när tidshorisonten går till oändlighet. Såvitt vi vet är DETC den första icke-fullständiga algoritmen som uppnår sådan asymptotisk optimalitet. Dessutom utvidgar vi DETC till batchade banditproblem, där (i) prospekteringsprocessen delas upp i ett litet antal partier och (ii) den runda komplexiteten är av centralt intresse. Vi bevisar att en batchad version av DETC kan uppnå den asymptotiska optimalitet med endast konstant rund komplexitet. Detta är den första batched bandit algoritm som kan uppnå asymptotic optimalitet i termer av både ånger och rund komplexitet.
Ett undantag är den nyligen föreslagna dubbel utforska-då-bekräfta algoritm REF, som har visat sig uppnå den asymptotiska optimalitet.
Double Explore-then-Commit: Asymptotic Optimality and Beyond
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}