Stochastic linjära banditer är en naturlig och enkel generalisering av finita beväpnade banditer med många praktiska tillämpningar. De nuvarande strategierna är inriktade på att generalisera befintlig teknik för finita beväpnade banditer, särskilt optimismsprincipen och Thompson-provtagning. Medan tidigare arbete mest har varit i värsta fall, analyserar vi den asymptotiska instansberoende ånger och visar matchande övre och nedre gränser på vad som är möjligt. Förvånansvärt nog visar våra resultat att ingen algoritm baserad på optimism eller Thompson-provtagning någonsin kommer att uppnå den optimala hastigheten, och faktiskt kan vara godtyckligt långt ifrån optimal, även i mycket enkla fall. Detta är ett oroande resultat eftersom dessa tekniker är standardverktyg som används i stor utsträckning för sekventiell optimering. Till exempel för generella linjära banditer och förstärkande inlärning.
När det gäller finita, linjära banditer tillhandahåller REF en asymptotisk exempeloptimal algoritm och visade att både UCB och Thompson provtagning kan vara godtyckligt långt från den nedre gränsen.
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}