mlsanityData to 7 Oct 2026

Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds

arXiv 1901.00210 ↗First posted 1 Jan 2019cs.LG cs.AI stat.MLcited by 194

Not on the map. Why?

Abstract (arXiv)

Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong problem-dependent bounds could help illuminate the key features of what makes a RL problem hard and reduce the barrier to using RL algorithms in practice. As a step towards this we derive an algorithm for finite horizon discrete MDPs and associated analysis that both yields state-of-the art worst-case regret bounds in the dominant terms and yields substantially tighter bounds if the RL environment has small environmental norm, which is a function of the variance of the next-state value functions. An important benefit of our algorithmic is that it does not require apriori knowledge of a bound on the environmental norm. As a result of our analysis, we also help address an open learning theory question~citejiang2018open about episodic MDPs with a constant upper-bound on the sum of rewards, providing a regret bound with no H-dependence in the leading term that scales a polynomial function of the number of episodes.

Key facts. Cited by 194 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 52; 2022: 40; 2023: 34; 2024: 29; 2025: 23; 2026: 15.

194 papers.

Sort:

By area:

  1. 2020MOPO: Model-based Offline Policy Optimizationcited by 630
  2. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  3. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  5. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  6. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  7. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  9. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  10. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  11. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  12. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
38 more
  1. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  2. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  3. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  4. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  5. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  6. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  7. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  8. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  9. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  10. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  11. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  12. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  13. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  14. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  15. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  16. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  17. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  18. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  19. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  20. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  21. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  22. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  23. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  24. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  25. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  26. 2021Online Apprenticeship Learningcited by 28
  27. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  28. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  29. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  30. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  31. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  32. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  33. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  34. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  35. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  36. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  37. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  38. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21

50 most cited of 194 All 194 (JSON)