Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits
We study the Bayesian regret of the renowned Thompson Sampling algorithm in
contextual bandits with binary losses and adversarially-selected contexts. We
adapt the information-theoretic perspective of Russo and Van Roy [2016] to the
contextual setting by introducing a new concept of information ratio based on
the mutual information between the unknown model parameter and the observed
loss. This allows us to bound the regret in terms of the entropy of the prior
distribution through a remarkably simple proof, and with no structural
assumptions on the likelihood or the prior. The extension to priors with
infinite entropy only requires a Lipschitz assumption on the log-likelihood. An
interesting special case is that of logistic bandits with d-dimensional
parameters, K actions, and Lipschitz logits, for which we provide a
$\widetilde{O}(\sqrt{dKT})$ regret upper-bound that does not depend on the
smallest slope of the sigmoid link function.