Data to 7 Oct 2026

Q-learning with Logarithmic Regret

arXiv 2006.09118 ↗First posted 16 Jun 2020cs.LG math.OC stat.MLcited by 59

Not on the map. Why?

Abstract (arXiv)

This paper presents the first non-asymptotic result showing that a model-free algorithm can achieve a logarithmic cumulative regret for episodic tabular reinforcement learning if there exists a strictly positive sub-optimality gap in the optimal Q-function. We prove that the optimistic Q-learning studied in [Jin et al. 2018] enjoys a Oleft(fracSA· polyleft(Hright)Deltaminlogleft(SATright)right) cumulative regret bound, where S is the number of states, A is the number of actions, H is the planning horizon, T is the total number of steps, and Deltamin is the minimum sub-optimality gap. This bound matches the information theoretical lower bound in terms of S,A,T up to a logleft(SAright) factor. We further extend our analysis to the discounted setting and obtain a similar logarithmic cumulative regret bound.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 16; 2023: 8; 2024: 6; 2025: 9; 2026: 4.

59 papers.

Sort:

By area:

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
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
2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34

38 more

2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
2021Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learningcited by 29
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
2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
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
2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
2021Can Q-Learning be Improved with Advice?cited by 13
2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
2022No-regret Learning in Repeated First-Price Auctions with Budget Constraintscited by 9
2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 7
2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
2025Automatic Reward Shaping from Confounded Offline Datacited by 6
2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
2022Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonmentcited by 5
2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
2023Provably Efficient Reinforcement Learning via Surprise Boundcited by 4
2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
2025Gap-Dependent Bounds for Federated Q-learningcited by 4
2022Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regretcited by 3
2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
2026Continuous Latent Contexts Enable Efficient Online Learning in Transformerscited by 3
2022Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learningcited by 2
2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2

50 most cited of 59 All 59 (JSON)