mlsanityData to 7 Oct 2026

Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs

arXiv 2010.00587 ↗First posted 1 Oct 2020cs.LG math.OC stat.MLcited by 42

Not on the map. Why?

Abstract (arXiv)

We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-γ, which is based on the optimism in the face of uncertainty principle and the Bernstein-type bonus. We show that UCBVI-γ achieves an tildeObig(√SAT/(1-γ)1.5big) regret, where S is the number of states, A is the number of actions, γ is the discount factor and T is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least tildeOmegabig(√SAT/(1-γ)1.5big). Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-γ is nearly minimax optimal for discounted MDPs.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 7; 2023: 10; 2024: 7; 2025: 5; 2026: 8.

42 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  2. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  3. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  4. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  5. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  6. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  7. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  8. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  9. 2022No-regret Learning in Repeated First-Price Auctions with Budget Constraintscited by 9
  10. 2023Optimistic Planning by Regularized Dynamic Programmingcited by 8
  11. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  12. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
30 more
  1. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  2. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  3. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  4. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  5. 2025Neural Logistic Banditscited by 5
  6. 2022Provably Efficient Kernelized Q-Learningcited by 4
  7. 2023Online Reinforcement Learning with Uncertain Episode Lengthscited by 4
  8. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  9. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  10. 2022Multi-armed Bandit Learning on a Graphcited by 3
  11. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  12. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  13. 2023Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertaintycited by 2
  14. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  15. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  16. 2025Safe Learning Under Irreversible Dynamics via Asking for Helpcited 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. 2025Online Bayesian Risk-Averse Reinforcement Learningcited by 1
  19. 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safetycited by 1
  20. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  21. 2023Model-Free, Regret-Optimal Best Policy Identification in Online CMDPscited by 0
  22. 2024Thompson Sampling for Infinite-Horizon Discounted Decision Processescited by 0
  23. 2024A Factored MDP Approach To Moving Target Defense With Dynamic Threat Modeling and Cost Efficiencycited by 0
  24. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  25. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  26. 2026Fundamental Limits of Man-in-the-Middle Attack Detection in Model-Free Reinforcement Learningcited by 0
  27. 2026Provably Efficient Offline-to-Online Value Adaptation with General Function Approximationcited by 0
  28. 2026Optimizing Digital Therapeutic Interventions: Online Learning under Endogenous Adherencecited by 0
  29. 2026Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPscited by 0
  30. 2026Near-Optimal Reinforcement Learning with Multi-Step Transition Lookaheadcited by 0