Data to 7 Oct 2026

Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition

arXiv 2004.10019 ↗First posted 21 Apr 2020cs.LG cs.DS stat.MLcited by 127

Not on the map. Why?

Abstract (arXiv)

We study the reinforcement learning problem in the setting of finite-horizon episodic Markov Decision Processes (MDPs) with S states, A actions, and episode length H. We propose a model-free algorithm UCB-Advantage and prove that it achieves tildeO(√H2SAT) regret where T = KH and K is the number of episodes to play. Our regret bound improves upon the results of [Jin et al., 2018] and matches the best known model-based algorithms as well as the information theoretic lower bound up to logarithmic factors. We also show that UCB-Advantage achieves low local switching cost and applies to concurrent reinforcement learning, improving upon the recent results of [Bai et al., 2019].

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 36; 2022: 26; 2023: 25; 2024: 17; 2025: 15; 2026: 8.

127 papers.

Sort:

By area:

2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
2022Jump-Start Reinforcement Learningcited by 102
2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48

38 more

2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
2023Fast Rates for Maximum Entropy Explorationcited by 32
2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
2021Parallelizing Thompson Samplingcited by 20
2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 18
2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 16
2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
2023Lower Bounds for Learning in Revealing POMDPscited by 14
2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14

50 most cited of 127 All 127 (JSON)