Efficient Model-free Reinforcement Learning in Metric Spaces

Abstract

Model-free Reinforcement Learning (RL) algorithms such as Q-learning [Watkins, Dayan 92] have been widely used in practice and can achieve human level performance in applications such as video games [Mnih et al. 15]. Recently, equipped with the idea of optimism in the face of uncertainty, Q-learning algorithms [Jin, Allen-Zhu, Bubeck, Jordan 18] can be proven to be sample efficient for discrete tabular Markov Decision Processes (MDPs) which have finite number of states and actions. In this work, we present an efficient model-free Q-learning based algorithm in MDPs with a natural metric on the state-action space--hence extending efficient model-free Q-learning algorithms to continuous state-action space. Compared to previous model-based RL algorithms for metric spaces [Kakade, Kearns, Langford 03], our algorithm does not require access to a black-box planning oracle.

References in corpus (4)

• Trust Region Policy Optimization
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning

Cited by in corpus (13)

• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Adaptive Discretization in Online Reinforcement Learning
• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Adaptive Discretization for Model-Based Reinforcement Learning
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• Provably adaptive reinforcement learning in metric spaces
• Single-partition adaptive Q-learning
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Control with adaptive Q-learning
• Coarse-Grained Smoothness for RL in Metric Spaces
• Off-Policy Interval Estimation with Lipschitz Value Iteration