Algoritmer baserade på övre förtroendegränser för att balansera prospektering och exploatering blir allt populärare eftersom de är lätta att genomföra, effektiva och effektiva. I detta dokument behandlas en variant av den grundläggande algoritmen för det stokastiska, flerarmade banditproblemet som tar hänsyn till de olika armarnas empiriska varians. I tidigare experimentella arbeten visade sig sådana algoritmer överträffa de konkurrerande algoritmerna. Vi tillhandahåller den första analysen av den förväntade ångern för sådana algoritmer. Som förväntat visar våra resultat att algoritmen som använder variansskattningarna har en stor fördel jämfört med dess alternativ som inte använder sådana uppskattningar, förutsatt att varianserna av de suboptimala armarna är låga. Vi bevisar också att ångern koncentrerar sig endast i polynom takt. Detta gäller för alla övre förtroende bundna algoritmer och för alla bandit problem utom de speciella där med sannolikhet en payoff som erhålls genom att dra den optimala armen är större än den förväntade payoff för den näst bästa armen. Därför, även om övre förtroende bundna bandit algoritmer uppnå logaritmiska förväntade ångerfrekvenser, * Motsvarande författare. E-postadresser: audibert@certis.enpc.fr (Jean Yves Audibert), remi.munos@inria.fr (Rémi Munos), szepesva@cs.ualberta.ca (Csaba Szepesvári) 1 Csaba Szepesvári är ledig från MTA SZTAKI, Budapest, Ungern. Preprint inlämnad till Teoretisk datavetenskap 11 januari 2009 de kanske inte lämpar sig för en risk-averse beslutsfattare. Vi illustrerar några av resultaten av datorsimuleringar.
REF visar att den algoritm som använder variansskattningarna har en stor fördel jämfört med de alternativ som inte använder sådana uppskattningar, förutsatt att varianserna för de suboptimala armarna är låga.
Exploration-exploitation trade-off using variance estimates in multi-armed bandits
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}