  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.
