# Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 26 Apr 2023.

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

- [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)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/1801.10242/) (2018)
- [An Information-Theoretic Analysis of Bayesian Reinforcement Learning](https://mlsanity.com/paper/2207.08735/) (2022)

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

- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis](https://mlsanity.com/paper/2401.11565/) (2024)
- [Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality](https://mlsanity.com/paper/2410.16013/) (2024)
- [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)

## Abstract (arXiv)

In this work, we study the performance of the Thompson Sampling algorithm for Contextual Bandit problems based on the framework introduced by Neu et al. and their concept of lifted information ratio. First, we prove a comprehensive bound on the Thompson Sampling expected cumulative regret that depends on the mutual information of the environment parameters and the history. Then, we introduce new bounds on the lifted information ratio that hold for sub-Gaussian rewards, thus generalizing the results from Neu et al. which analysis requires binary rewards. Finally, we provide explicit regret bounds for the special cases of unstructured bounded contextual bandits, structured bounded contextual bandits with Laplace likelihood, structured Bernoulli bandits, and bounded linear contextual bandits.