I detta dokument presenteras en ändlig tidsanalys av KL-UCB-algoritmen, en online, horisontfri indexpolicy för stokastiska banditproblem. Vi bevisar två distinkta resultat: för det första, för godtyckliga begränsade belöningar, uppfyller KL-UCB algoritmen en enhetligt bättre ånger bunden än UCB och dess varianter; för det andra, i det speciella fallet Bernoulli belöningar, når den nedre gränsen av Lai och Robbins. Dessutom visar vi att enkla anpassningar av KL-UCB-algoritmen också är optimala för specifika klasser av (eventuellt obundna) belöningar, inklusive de som genereras från exponentiella distributionsfamiljer. En storskalig numerisk studie som jämför KL-UCB med dess huvudkonkurrenter (UCB, MOSS, UCB-Tuned, UCB-V, DMED) visar att KL-UCB är anmärkningsvärt effektivt och stabilt, även för korta tidshorisonter. KL-UCB är också den enda metod som alltid fungerar bättre än den grundläggande UCB-policyn. Våra beklagande gränser bygger på avvikelser resultat av oberoende intresse som anges och bevisas i bilagan. Som en biprodukt får vi också en förbättrad ånger bundet till standard UCB algoritm.
Nyligen föreslogs KL-UCB-policyn i REF.
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
{'venue': 'Conference On Learning Theory n{\\deg}24 Jul. 2011 pp.359-376', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}