Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
Preprint
Abstract
We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We further show the "mismatched sampling paradox": A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-ParadoxKeywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-BanditsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2021
- Kullback–Leibler upper confidence bounds for optimal sequential allocationThe Annals of Statistics, 2013
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985