Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits
This provides a theoretical improvement for researchers in bandit algorithms by offering a simpler proof and more general regret bounds, though it is incremental as it builds on existing information-theoretic frameworks.
The paper tackles the problem of analyzing the Bayesian regret of Thompson Sampling in contextual bandits with binary losses and adversarial contexts, resulting in a regret bound of $\widetilde{O}(\sqrt{dKT})$ for logistic bandits without dependence on the sigmoid's smallest slope.
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 \cite{RvR16} to the contextual setting by considering a lifted version of the information ratio defined in terms of the unknown model parameter instead of the optimal action or optimal policy as done in previous works on the same setting. 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.