Efficient Model-free Reinforcement Learning in Metric Spaces
This work addresses the challenge of scaling model-free reinforcement learning to continuous domains, which is incremental as it builds on prior Q-learning methods for discrete spaces.
The authors tackled the problem of extending efficient model-free Q-learning to continuous state-action spaces by introducing a metric space structure, resulting in an algorithm that achieves sample efficiency without needing a planning oracle.
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.