mlsanityData to 7 Oct 2026

On Lower Bounds for Regret in Reinforcement Learning

arXiv 1608.02732 ↗First posted 9 Aug 2016stat.ML cs.LGcited by 39

Not on the map. Why?

Abstract (arXiv)

This is a brief technical note to clarify the state of lower bounds on regret for reinforcement learning. In particular, this paper: - Reproduces a lower bound on regret for reinforcement learning, similar to the result of Theorem 5 in the journal UCRL2 paper (Jaksch et al 2010). - Clarifies that the proposed proof of Theorem 6 in the REGAL paper (Bartlett and Tewari 2009) does not hold using the standard techniques without further work. We suggest that this result should instead be considered a conjecture as it has no rigorous proof. - Suggests that the conjectured lower bound given by (Bartlett and Tewari 2009) is incorrect and, in fact, it is possible to improve the scaling of the upper bound to match the weaker lower bounds presented in this paper. We hope that this note serves to clarify existing results in the field of reinforcement learning and provides interesting motivation for future work.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Aug 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 6; 2023: 6; 2024: 8; 2025: 3; 2026: 1.

39 papers.

Sort:

By area:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  3. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  4. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  5. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  6. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  7. 2021Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environmentscited by 26
  8. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  9. 2023Replicable Reinforcement Learningcited by 21
  10. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  11. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  12. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
27 more
  1. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
  2. 2021Continual Learning In Environments With Polynomial Mixing Timescited by 13
  3. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  4. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  5. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
  6. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  7. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  8. 2023Semi-Bandit Learning for Monotone Stochastic Optimizationcited by 8
  9. 2024Can we hop in general? A discussion of benchmark selection and design using the Hopper environmentcited by 7
  10. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
  11. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  12. 2022Provably Efficient Kernelized Q-Learningcited by 4
  13. 2024Cascading Reinforcement Learningcited by 4
  14. 2022Multi-armed Bandit Learning on a Graphcited by 3
  15. 2024Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Samplingcited by 3
  16. 2026Cold-Start Personalization via Training-Free Priors from Structured World Modelscited by 2
  17. 2021Online Sub-Sampling for Reinforcement Learning with General Function Approximationcited by 1
  18. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  19. 2022Branching Reinforcement Learningcited by 1
  20. 2024Causal Contextual Bandits with Adaptive Contextcited by 1
  21. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
  22. 2022Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamicscited by 0
  23. 2023An Option-Dependent Analysis of Regret Minimization Algorithms in Finite-Horizon Semi-Markov Decision Processescited by 0
  24. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  25. 2024Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximationcited by 0
  26. 2025Reinforcement Learning from Multi-level and Episodic Human Feedbackcited by 0
  27. 2025Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problemscited by 0