mlsanityData to 7 Oct 2026

An Information-Theoretic Analysis for Thompson Sampling with Many Actions

arXiv 1805.11845 ↗First posted 30 May 2018stat.ML cs.IT cs.LGcited by 35

Not on the map. Why?

Abstract (arXiv)

Information-theoretic Bayesian regret bounds of Russo and Van Roy capture the dependence of regret on prior uncertainty. However, this dependence is through entropy, which can become arbitrarily large as the number of actions increases. We establish new bounds that depend instead on a notion of rate-distortion. Among other things, this allows us to recover through information-theoretic arguments a near-optimal bound for the linear bandit. We also offer a bound for the logistic bandit that dramatically improves on the best previously available, though this bound depends on an information-theoretic statistic that we have only been able to quantify via computation.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 May 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

35 papers.

Sort:

By area:

  1. 2021Reinforcement Learning, Bit by Bitcited by 59
  2. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  3. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  4. 2021Deciding What to Learn: A Rate-Distortion Approachcited by 23
  5. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  6. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  7. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  8. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  9. 2021Metalearning Linear Bandits by Prior Updatecited by 15
  10. 2021The Value of Information When Deciding What to Learncited by 15
  11. 2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
  12. 2021UCB-based Algorithms for Multinomial Logistic Regression Banditscited by 12
23 more
  1. 2021A Payload Optimization Method for Federated Recommender Systemscited by 10
  2. 2023A Definition of Non-Stationary Banditscited by 9
  3. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  4. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5
  5. 2022Gaussian Imagination in Bandit Learningcited by 5
  6. 2023Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewardscited by 5
  7. 2023Incentivizing Exploration with Linear Contexts and Combinatorial Actionscited by 5
  8. 2025Contextual Thompson Sampling via Generation of Missing Datacited by 5
  9. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  10. 2023Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Banditscited by 3
  11. 2021Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classificationcited by 2
  12. 2022Adaptive Sampling for Discoverycited by 2
  13. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysiscited by 2
  14. 2021The Elliptical Potential Lemma for General Distributions with an Application to Linear Thompson Samplingcited by 1
  15. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  16. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Dualitycited by 1
  17. 2024An Information-Theoretic Analysis of Thompson Sampling for Logistic Banditscited by 1
  18. 2025Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Samplingcited by 1
  19. 2026Prior Diffusiveness and Regret in the Linear-Gaussian Banditcited by 1
  20. 2024Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problemscited by 0
  21. 2025An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spacescited by 0
  22. 2025Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contextscited by 0
  23. 2026Bayesian learning for the stochastic shortest path problemcited by 0