mlsanityData to 14 Oct 2026

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

arXiv 2205.13924 ↗First posted 27 May 2022cs.LGcited by 19

Not on the map. Why?

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.

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

25 of 57 references.

References · 25

  1. 2013Learning to Optimize Via Posterior Samplingcited by 256
  2. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  4. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  5. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  6. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  7. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  8. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  9. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  10. 2017Ensemble Samplingcited by 62
  11. 2021Reinforcement Learning, Bit by Bitcited by 59
  12. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 57
13 more
  1. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  2. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  3. 2020Information Directed Sampling for Linear Partial Monitoringcited by 40
  4. 2018An Information-Theoretic Analysis for Thompson Sampling with Many Actionscited by 35
  5. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  6. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  7. 2022An Analysis of Ensemble Samplingcited by 24
  8. 2018PG-TS: Improved Thompson Sampling for Logistic Contextual Banditscited by 19
  9. 2019First-Order Bayesian Regret Analysis of Thompson Samplingcited by 17
  10. 2022Contextual Information-Directed Samplingcited by 16
  11. 2018Analysis of Thompson Sampling for Graphical Bandits Without the Graphscited by 7
  12. 2013Generalized Thompson Sampling for Contextual Banditscited by 5
  13. 2022Gaussian Imagination in Bandit Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 6; 2025: 6; 2026: 2.

19 papers.

Sort:

By area:

  1. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  2. 2023A Definition of Non-Stationary Banditscited by 9
  3. 2024Optimistic Information Directed Samplingcited by 7
  4. 2025Contextual Thompson Sampling via Generation of Missing Datacited by 6
  5. 2023Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewardscited by 5
  6. 2023Incentivizing Exploration with Linear Contexts and Combinatorial Actionscited by 5
  7. 2024Diffusion Models Meet Contextual Banditscited by 5
  8. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  9. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysiscited by 2
  10. 2025Learning to Decide with Just Enough: Information-Theoretic Context Summarization for CMDPscited by 2
  11. 2023Overcoming Prior Misspecification in Online Learning to Rankcited by 1
  12. 2024An Information-Theoretic Analysis of Thompson Sampling for Logistic Banditscited by 1
7 more
  1. 2025Sparse Optimistic Information Directed Samplingcited by 1
  2. 2026BFTS: Thompson Sampling with Bayesian Additive Regression Treescited by 1
  3. 2024Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problemscited by 0
  4. 2025An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spacescited by 0
  5. 2025Sparse Nonparametric Contextual Banditscited by 0
  6. 2025Decentralized Contextual Bandits with Network Adaptivitycited by 0
  7. 2026Learning to Assign Prediction Tasks to Agents with Capacity Constraintscited by 0