# An Information-Theoretic Analysis for Thompson Sampling with Many Actions

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

## Key facts

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

## Built on by (most cited first, 30 of 35)

- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Deciding What to Learn: A Rate-Distortion Approach](https://mlsanity.com/paper/2101.06197/) (2021)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Metalearning Linear Bandits by Prior Update](https://mlsanity.com/paper/2107.05320/) (2021)
- [The Value of Information When Deciding What to Learn](https://mlsanity.com/paper/2110.13973/) (2021)
- [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021)
- [UCB-based Algorithms for Multinomial Logistic Regression Bandits](https://mlsanity.com/paper/2103.11489/) (2021)
- [A Payload Optimization Method for Federated Recommender Systems](https://mlsanity.com/paper/2107.13078/) (2021)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Contextual Thompson Sampling via Generation of Missing Data](https://mlsanity.com/paper/2502.07064/) (2025)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)
- [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)
- [Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling](https://mlsanity.com/paper/2502.05434/) (2025)
- [Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification](https://mlsanity.com/paper/2109.14412/) (2021)
- [Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits](https://mlsanity.com/paper/2306.14872/) (2023)
- [Adaptive Sampling for Discovery](https://mlsanity.com/paper/2205.14829/) (2022)
- [Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis](https://mlsanity.com/paper/2401.11565/) (2024)
- [The Elliptical Potential Lemma for General Distributions with an Application to Linear Thompson Sampling](https://mlsanity.com/paper/2102.07987/) (2021)
- [The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2405.11226/) (2024)
- [Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality](https://mlsanity.com/paper/2410.16013/) (2024)
- [An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits](https://mlsanity.com/paper/2412.02861/) (2024)
- [Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Sampling](https://mlsanity.com/paper/2508.13749/) (2025)

## 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.