Efficient Model-free Reinforcement Learning in Metric Spaces

2019/05/01 by Zhao Song, Wen Sun, Song, Zhao +1 · 5 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1905.00475

openalex publication_date 2019/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Trust Region Policy Optimization
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement\n Learning

Cited by

• Improving Reinforcement Learning Sample-Efficiency using Local Approximation
• Provably Efficient and Agile Randomized Q-Learning
• Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Provably adaptive reinforcement learning in metric spaces
• Bellman operator convergence enhancements in reinforcement learning algorithms

Related

• Reinforcement Learning with Parameterized Actions
• A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes
• Is Q-learning Provably Efficient?
• Q-learning with Nearest Neighbors
• Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes