Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling
This work addresses a foundational issue in bandit algorithms for decision-making under uncertainty, offering a Bayesian solution that improves regret bounds and practical performance, though it is incremental by building on prior variance-adaptive methods.
The paper tackles the problem of suboptimal performance in bandit algorithms due to assumed known or homogeneous reward variances by developing a variance-adaptive Thompson sampling algorithm for Gaussian bandits with unknown heterogeneous variances, achieving lower regret with more informative priors and demonstrating superiority over frequentist approaches in experiments.
Most bandit algorithms assume that the reward variances or their upper bounds are known, and that they are the same for all arms. This naturally leads to suboptimal performance and higher regret due to variance overestimation. On the other hand, underestimated reward variances may lead to linear regret due to committing early to a suboptimal arm. This motivated prior works on variance-adaptive frequentist algorithms, which have strong instance-dependent regret bounds but cannot incorporate prior knowledge on reward variances. We lay foundations for the Bayesian setting, which incorporates prior knowledge. This results in lower regret in practice, due to using the prior in the algorithm design, and also improved regret guarantees. Specifically, we study Gaussian bandits with {unknown heterogeneous reward variances}, and develop a Thompson sampling algorithm with prior-dependent Bayes regret bounds. We achieve lower regret with lower reward variances and more informative priors on them, which is precisely why we pay only for what is uncertain. This is the first result of its kind. Finally, we corroborate our theory with extensive experiments, which show the superiority of our variance-adaptive Bayesian algorithm over prior frequentist approaches. We also show that our approach is robust to model misspecification and can be applied with estimated priors.