# Q-learning with Logarithmic Regret

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

## Key facts

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

## Built on by (most cited first, 30 of 60)

- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Provably Efficient Multi-Task Reinforcement Learning with Model Transfer](https://mlsanity.com/paper/2107.08622/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization](https://mlsanity.com/paper/2302.06834/) (2023)
- [Can Q-Learning be Improved with Advice?](https://mlsanity.com/paper/2110.13052/) (2021)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Gap-Dependent Unsupervised Exploration for Reinforcement Learning](https://mlsanity.com/paper/2108.05439/) (2021)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)

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