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

arXiv: https://arxiv.org/abs/2006.03864 · HTML: https://mlsanity.com/paper/2006.03864/

## Key facts

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

## Built on by (most cited first, 28 of 28)

- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2212.13540/) (2022)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [Uncertainty-Aware Reward-Free Exploration with General Function Approximation](https://mlsanity.com/paper/2406.16255/) (2024)
- [Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice](https://mlsanity.com/paper/2305.13185/) (2023)
- [Multi-armed Bandit Learning on a Graph](https://mlsanity.com/paper/2209.09419/) (2022)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Control](https://mlsanity.com/paper/2211.15205/) (2022)
- [Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path](https://mlsanity.com/paper/2402.08998/) (2024)
- [Improving Reinforcement Learning Sample-Efficiency using Local Approximation](https://mlsanity.com/paper/2507.12383/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQ](https://mlsanity.com/paper/2402.11877/) (2024)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)

## 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.