# Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits

arXiv: https://arxiv.org/abs/2205.13924 · HTML: https://mlsanity.com/paper/2205.13924/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 25 of 25)

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits](https://mlsanity.com/paper/1805.07458/) (2018)
- [First-Order Bayesian Regret Analysis of Thompson Sampling](https://mlsanity.com/paper/1902.00681/) (2019)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [Analysis of Thompson Sampling for Graphical Bandits Without the Graphs](https://mlsanity.com/paper/1805.08930/) (2018)
- [Generalized Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/1310.7163/) (2013)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)

## Built on by (most cited first, 19 of 19)

- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Contextual Thompson Sampling via Generation of Missing Data](https://mlsanity.com/paper/2502.07064/) (2025)
- [Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards](https://mlsanity.com/paper/2304.13593/) (2023)
- [Incentivizing Exploration with Linear Contexts and Combinatorial Actions](https://mlsanity.com/paper/2306.01990/) (2023)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis](https://mlsanity.com/paper/2401.11565/) (2024)
- [Learning to Decide with Just Enough: Information-Theoretic Context Summarization for CMDPs](https://mlsanity.com/paper/2510.01620/) (2025)
- [Overcoming Prior Misspecification in Online Learning to Rank](https://mlsanity.com/paper/2301.10651/) (2023)
- [An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits](https://mlsanity.com/paper/2412.02861/) (2024)
- [Sparse Optimistic Information Directed Sampling](https://mlsanity.com/paper/2510.24234/) (2025)
- [BFTS: Thompson Sampling with Bayesian Additive Regression Trees](https://mlsanity.com/paper/2602.07767/) (2026)
- [Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems](https://mlsanity.com/paper/2403.03361/) (2024)
- [An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces](https://mlsanity.com/paper/2502.02140/) (2025)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Decentralized Contextual Bandits with Network Adaptivity](https://mlsanity.com/paper/2508.13411/) (2025)
- [Learning to Assign Prediction Tasks to Agents with Capacity Constraints](https://mlsanity.com/paper/2605.27999/) (2026)

## Abstract (arXiv)

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 citeRvR16 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 widetildeO(√dKT) regret upper-bound that does not depend on the smallest slope of the sigmoid link function.