mlsanityData to 7 Oct 2026

Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity

arXiv 2006.03864 ↗First posted 6 Jun 2020cs.LG stat.MLcited by 28

Not on the map. Why?

Abstract (arXiv)

In this paper we consider the problem of learning an ε-optimal policy for a discounted Markov Decision Process (MDP). Given an MDP with S states, A actions, the discount factor γ ∈ (0,1), and an approximation threshold ε > 0, we provide a model-free algorithm to learn an ε-optimal policy with sample complexity tildeO(fracSAln(1/p)ε2(1-γ)5.5) (where the notation tildeO(·) hides poly-logarithmic factors of S,A,1/(1-γ), and 1/ε) and success probability (1-p). For small enough ε, we show an improved algorithm with sample complexity tildeO(fracSAln(1/p)ε2(1-γ)3). While the first bound improves upon all known model-free algorithms and model-based ones with tight dependence on S, our second algorithm beats all known sample complexity bounds and matches the information theoretic lower bound up to logarithmic factors.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 6; 2024: 4; 2025: 4; 2026: 1.

28 papers.

Sort:

By area:

  1. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  2. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  3. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  4. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  5. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  6. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  7. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  8. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  9. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  10. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  11. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  12. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
16 more
  1. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  2. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  3. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  4. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  5. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  6. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  7. 2022Multi-armed Bandit Learning on a Graphcited by 3
  8. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  9. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  10. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  11. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  12. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  13. 2025Improving Reinforcement Learning Sample-Efficiency using Local Approximationcited by 1
  14. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  15. 2024Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQcited by 0
  16. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0