# Information-Theoretic Confidence Bounds for Reinforcement Learning

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

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

- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiency](https://mlsanity.com/paper/2309.17382/) (2023)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Thompson Sampling with a Mixture Prior](https://mlsanity.com/paper/2106.05608/) (2021)
- [Metalearning Linear Bandits by Prior Update](https://mlsanity.com/paper/2107.05320/) (2021)
- [PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration](https://mlsanity.com/paper/2107.07410/) (2021)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Bayesian Design Principles for Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2405.20984/) (2024)
- [Unsupervised Behavior Extraction via Random Intent Priors](https://mlsanity.com/paper/2310.18687/) (2023)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [Graph Neural Network Bandits](https://mlsanity.com/paper/2207.06456/) (2022)
- [On Rollouts in Model-Based Reinforcement Learning](https://mlsanity.com/paper/2501.16918/) (2025)
- [Multi-Task Off-Policy Learning from Bandit Feedback](https://mlsanity.com/paper/2212.04720/) (2022)
- [Social Contract AI: Aligning AI Assistants with Implicit Group Norms](https://mlsanity.com/paper/2310.17769/) (2023)
- [Shattering the Agent-Environment Interface for Fine-Tuning Inclusive Language Models](https://mlsanity.com/paper/2305.11455/) (2023)
- [Thompson Sampling with Diffusion Generative Prior](https://mlsanity.com/paper/2301.05182/) (2023)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [On Rate-Distortion Theory in Capacity-Limited Cognition & Reinforcement Learning](https://mlsanity.com/paper/2210.16877/) (2022)
- [Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent](https://mlsanity.com/paper/2402.10228/) (2024)
- [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)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)

## Abstract (arXiv)

We integrate information-theoretic concepts into the design and analysis of optimistic algorithms and Thompson sampling. By making a connection between information-theoretic quantities and confidence bounds, we obtain results that relate the per-period performance of the agent with its information gain about the environment, thus explicitly characterizing the exploration-exploitation tradeoff. The resulting cumulative regret bound depends on the agent's uncertainty over the environment and quantifies the value of prior information. We show applicability of this approach to several environments, including linear bandits, tabular MDPs, and factored MDPs. These examples demonstrate the potential of a general information-theoretic approach for the design and analysis of reinforcement learning algorithms.