Analysis of Thompson Sampling for the Multi-armed Bandit Problem
作者： Shipra Agrawal , Navin Goyal
DOI:
关键词:
摘要: The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by WR Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In …
arxiv.org
harvard.edu参考文章(13)
Rémi Munos, Odalric-Ambrym Maillard, Gilles Stoltz, A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences conference on learning theory. pp. 18- ,(2011)
Nathan Korda, David S. Leslie, Anthony Lee, Benedict C. May, Optimistic Bayesian sampling in contextual-bandit problems Journal of Machine Learning Research. ,vol. 13, pp. 2069- 2106 ,(2012) , 10.5555/2188385.2343711
T.L Lai, Herbert Robbins, Asymptotically efficient adaptive allocation rules Advances in Applied Mathematics. ,vol. 6, pp. 4- 22 ,(1985) , 10.1016/0196-8858(85)90002-8
Ole‐Christoffer Granmo, Solving two‐armed Bernoulli bandit problems using a Bayesian learning automaton International Journal of Intelligent Computing and Cybernetics. ,vol. 3, pp. 207- 234 ,(2010) , 10.1108/17563781011049179
W. R THOMPSON, ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLES Biometrika. ,vol. 25, pp. 285- 294 ,(1933) , 10.1093/BIOMET/25.3-4.285
Kumar Jogdeo, S. M. Samuels, Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation Annals of Mathematical Statistics. ,vol. 39, pp. 1191- 1195 ,(1968) , 10.1214/AOMS/1177698243
Olivier Chapelle, Lihong Li, An Empirical Evaluation of Thompson Sampling neural information processing systems. ,vol. 24, pp. 2249- 2257 ,(2011)
Steven L. Scott, A modern Bayesian look at the multi-armed bandit Applied Stochastic Models in Business and Industry. ,vol. 26, pp. 639- 658 ,(2010) , 10.1002/ASMB.874
Thore Graepel, Joaquin Quiñonero-Candela, Thomas Borchert, Ralf Herbrich, Web-Scale Bayesian Click-Through rate Prediction for Sponsored Search Advertising in Microsoft's Bing Search Engine international conference on machine learning. pp. 13- 20 ,(2010)
Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem Machine Learning. ,vol. 47, pp. 235- 256 ,(2002) , 10.1023/A:1013689704352