Data to 14 Oct 2026

Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP

arXiv 1901.09311 ↗First posted 27 Jan 2019cs.LG stat.MLcited by 55

Not on the map. Why?

Abstract (arXiv)

A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. citejin2018q proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with UCB-exploration bonus to infinite-horizon MDP with discounted rewards without accessing a generative model. We show that the textitsample complexity of exploration of our algorithm is bounded by tildeO(fracSAε2(1-γ)7). This improves the previously best known result of tildeO(fracSAε4(1-γ)8) in this setting achieved by delayed Q-learning citestrehl2006pac, and matches the lower bound in terms of ε as well as S and A except for logarithmic factors.

Key facts. Cited by 55 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 13; 2022: 7; 2023: 13; 2024: 8; 2025: 9; 2026: 4.

55 papers.

Sort:

By area:

2021Recent Advances in Reinforcement Learning in Financecited by 110
2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
2021A Survey of Exploration Methods in Reinforcement Learningcited by 73
2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40

38 more

2021Interesting Object, Curious Agent: Learning Task-Agnostic Explorationcited by 38
2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 22
2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 16
2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 15
2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
2022Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learningcited by 9
2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
2024Beyond Optimism: Exploration With Partially Observable Rewardscited by 6
2025Automatic Reward Shaping from Confounded Offline Datacited by 6
2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
2023Keep Various Trajectories: Promoting Exploration of Ensemble Policies in Continuous Controlcited by 5
2024Model-Free Active Exploration in Reinforcement Learningcited by 5
2024The Bandit Whisperer: Communication Learning for Restless Banditscited by 5
2022Posterior Sampling for Continuing Environmentscited by 4
2023Provable Reset-free Reinforcement Learning by No-Regret Reductioncited by 3
2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
2024Learning to Steer Markovian Agents under Model Uncertaintycited by 2
2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
2025Improving Reinforcement Learning Sample-Efficiency using Local Approximationcited by 1
2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
2025Online Bayesian Risk-Averse Reinforcement Learningcited by 1
2025Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learningcited by 1
2023Decentralized model-free reinforcement learning in stochastic games with average-reward objectivecited by 0
2024Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQcited by 0
2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
2025Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problemcited by 0

50 most cited of 55 All 55 (JSON)