mlsanityData to 7 Oct 2026

Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies

arXiv 1905.11527 ↗First posted 27 May 2019cs.LG cs.AI stat.MLcited by 38

Not on the map. Why?

Abstract (arXiv)

State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing full-planning on Markov Decision Processes (MDPs) built by the gathered experience. In this paper, we focus on model-based RL in the finite-state finite-horizon MDP setting and establish that exploring with greedy policies -- act by 1-step planning -- can achieve tight minimax performance in terms of regret, tildeO(√HSAT). Thus, full-planning in model-based RL can be avoided altogether without any performance degradation, and, by doing so, the computational complexity decreases by a factor of S. The results are based on a novel analysis of real-time dynamic programming, then extended to model-based RL. Specifically, we generalize existing algorithms that perform full-planning to such that act by 1-step planning. For these generalizations, we prove regret bounds with the same rate as their full-planning counterparts.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 5; 2023: 3; 2024: 4; 2025: 4; 2026: 5.

38 papers.

Sort:

By area:

  1. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  2. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  3. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  4. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  5. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  6. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  7. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  8. 2021Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learningcited by 38
  9. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  10. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  11. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  12. 2021Online Apprenticeship Learningcited by 28
26 more
  1. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  2. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  3. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  4. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  5. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  6. 2022When to Update Your Model: Constrained Model-based Reinforcement Learningcited by 14
  7. 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
  8. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  9. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11
  10. 2024Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learningcited by 11
  11. 2022Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitionscited by 9
  12. 2023Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learningcited by 8
  13. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  14. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  15. 2022Reinforcement Learning with a Terminatorcited by 4
  16. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  17. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  18. 2021UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithmscited by 0
  19. 2025A Domain-Based Taxonomy of Jailbreak Vulnerabilities in Large Language Modelscited by 0
  20. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  21. 2025Tail Distribution of Regret in Optimistic Reinforcement Learningcited by 0
  22. 2026Provably Safe Reinforcement Learning for Stochastic Reach-Avoid Problems with Entropy Regularizationcited by 0
  23. 2026Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batchingcited by 0
  24. 2026Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?cited by 0
  25. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcited by 0
  26. 2026Optimal Multi-Reward Reinforcement Learningcited by 0