mlsanityData to 7 Oct 2026

Regret Bounds for Information-Directed Reinforcement Learning

arXiv 2206.04640 ↗First posted 9 Jun 2022cs.LG cs.IT math.ITcited by 24

Not on the map. Why?

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.

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

Builds on

35 of 51 references.

References · 35

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  12. 2014Learning to Optimize via Information-Directed Samplingcited by 168
23 more
  1. 2017Deep Exploration via Randomized Value Functionscited by 155
  2. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2021Epistemic Neural Networkscited by 120
  5. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  8. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  9. 2021Reinforcement Learning, Bit by Bitcited by 59
  10. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  11. 2018Information-Directed Exploration for Deep Reinforcement Learningcited by 52
  12. 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
  13. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  14. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
  15. 2020Information Directed Sampling for Linear Partial Monitoringcited by 39
  16. 2020Mirror Descent and the Information Ratiocited by 39
  17. 2018Satisficing in Time-Sensitive Bandit Learningcited by 38
  18. 2018An Information-Theoretic Analysis for Thompson Sampling with Many Actionscited by 35
  19. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  20. 2017Information Directed Sampling for Stochastic Bandits with Graph Feedbackcited by 24
  21. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  22. 2019First-Order Bayesian Regret Analysis of Thompson Samplingcited by 17
  23. 2022Contextual Information-Directed Samplingcited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 5; 2025: 5; 2026: 5.

24 papers.

Sort:

By area:

  1. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  2. 2023Leveraging Demonstrations to Improve Online Learning: Quality Matterscited by 13
  3. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  4. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  5. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  6. 2024Optimistic Information Directed Samplingcited by 7
  7. 2023Bridging Imitation and Online Reinforcement Learning: An Optimistic Talecited by 5
  8. 2023STEERING: Stein Information Directed Exploration for Model-Based Reinforcement Learningcited by 4
  9. 2023Bayesian Reinforcement Learning with Limited Cognitive Loadcited by 4
  10. 2024Value of Information and Reward Specification in Active Inference and POMDPscited by 4
  11. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  12. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
12 more
  1. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  2. 2024Learning with Posterior Sampling for Revenue Management under Time-varying Demandcited by 1
  3. 2024Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender Systemcited by 1
  4. 2025Sparse Optimistic Information Directed Samplingcited by 1
  5. 2023REBEL: Reward Regularization-Based Approach for Robotic Reinforcement Learning from Human Feedbackcited by 0
  6. 2025Empirical Bound Information-Directed Sampling for Norm-Agnostic Banditscited by 0
  7. 2025Learning What Matters Now: A Dual-Critic Context-Aware RL Framework for Priority-Driven Information Gaincited by 0
  8. 2026C-IDS: Solving Contextual POMDP via Information-Directed Objectivecited by 0
  9. 2026Adaptive Exploration for Latent-State Banditscited by 0
  10. 2026Information-Directed Offline-to-Online Reinforcement Learningcited by 0
  11. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0
  12. 2026Future Information-Directed Sampling for Bayesian Nonstationary Banditscited by 0