# Regret Bounds for Information-Directed Reinforcement Learning

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 51 references that are in the map.
- First posted on arXiv 9 Jun 2022.

## Builds on (most cited first, 30 of 35)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Epistemic Neural Networks](https://mlsanity.com/paper/2107.08924/) (2021)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Information-Directed Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.07544/) (2018)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)

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

- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [Leveraging Demonstrations to Improve Online Learning: Quality Matters](https://mlsanity.com/paper/2302.03319/) (2023)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Bridging Imitation and Online Reinforcement Learning: An Optimistic Tale](https://mlsanity.com/paper/2303.11369/) (2023)
- [STEERING: Stein Information Directed Exploration for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2301.12038/) (2023)
- [Bayesian Reinforcement Learning with Limited Cognitive Load](https://mlsanity.com/paper/2305.03263/) (2023)
- [Value of Information and Reward Specification in Active Inference and POMDPs](https://mlsanity.com/paper/2408.06542/) (2024)
- [Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling](https://mlsanity.com/paper/2502.05434/) (2025)
- [Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.19292/) (2024)
- [Provably Efficient and Agile Randomized Q-Learning](https://mlsanity.com/paper/2506.24005/) (2025)
- [Learning with Posterior Sampling for Revenue Management under Time-varying Demand](https://mlsanity.com/paper/2405.04910/) (2024)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [Sparse Optimistic Information Directed Sampling](https://mlsanity.com/paper/2510.24234/) (2025)
- [REBEL: Reward Regularization-Based Approach for Robotic Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14436/) (2023)
- [Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits](https://mlsanity.com/paper/2503.05098/) (2025)
- [Learning What Matters Now: A Dual-Critic Context-Aware RL Framework for Priority-Driven Information Gain](https://mlsanity.com/paper/2506.06786/) (2025)
- [C-IDS: Solving Contextual POMDP via Information-Directed Objective](https://mlsanity.com/paper/2602.03939/) (2026)
- [Adaptive Exploration for Latent-State Bandits](https://mlsanity.com/paper/2602.05139/) (2026)
- [Information-Directed Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2605.29405/) (2026)
- [Minimax-Optimality of Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2609.33246/) (2026)
- [Future Information-Directed Sampling for Bayesian Nonstationary Bandits](https://mlsanity.com/paper/2609.33981/) (2026)

## Abstract (arXiv)

Information-directed sampling (IDS) has revealed its potential as a data-efficient algorithm for reinforcement learning (RL). However, theoretical understanding of IDS for Markov Decision Processes (MDPs) is still limited. We develop novel information-theoretic tools to bound the information ratio and cumulative information gain about the learning target. Our theoretical results shed light on the importance of choosing the learning target such that the practitioners can balance the computation and regret bounds. As a consequence, we derive prior-free Bayesian regret bounds for vanilla-IDS which learns the whole environment under tabular finite-horizon MDPs. In addition, we propose a computationally-efficient regularized-IDS that maximizes an additive form rather than the ratio form and show that it enjoys the same regret bound as vanilla-IDS. With the aid of rate-distortion theory, we improve the regret bound by learning a surrogate, less informative environment. Furthermore, we extend our analysis to linear MDPs and prove similar regret bounds for Thompson sampling as a by-product.