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

Abstract

A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} 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 \emph{without} accessing a generative model. We show that the \textit{sample complexity of exploration} of our algorithm is bounded by $\tilde{O}(\frac{SA}{{\epsilon }^2(1-\gamma {)}^7})$. This improves the previously best known result of $\tilde{O}(\frac{SA}{{\epsilon }^4(1-\gamma {)}^8})$ in this setting achieved by delayed Q-learning \cite{strehl2006pac}, and matches the lower bound in terms of $\epsilon$ as well as $S$ and $A$ except for logarithmic factors.

References in corpus (3)

• Playing Atari with Deep Reinforcement Learning
• Trust Region Policy Optimization
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

Cited by in corpus (22)

• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• $Q$-learning with Logarithmic Regret
• Optimistic Exploration even with a Pessimistic Initialisation
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learning
• Adaptive Approximate Policy Iteration
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Transfer Reinforcement Learning under Unobserved Contextual Information
• Gap-Dependent Bounds for Two-Player Markov Games
• A Hybrid PAC Reinforcement Learning Algorithm
• Q-greedyUCB: a New Exploration Policy for Adaptive and Resource-efficient Scheduling