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

2019/01/27 by Dong, Kefan, Wang, Yuanhao, Chen, Xiaoyu +1 · 4 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1901.09311

Abstract

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 sample complexity of exploration of our algorithm is bounded by O((SA)/(ε²(1-γ)⁷)). This improves the previously best known result of O((SA)/(ε⁴(1-γ)⁸)) 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.

Cited by

• Tensor-Efficient High-Dimensional Q-learning
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning
• Online Bayesian Risk-Averse Reinforcement Learning
• Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem

Related

• Is Q-learning Provably Efficient?
• Is Q-Learning Provably Efficient? An Extended Analysis
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition