# Efficient Model-free Reinforcement Learning in Metric Spaces

arXiv: https://arxiv.org/abs/1905.00475 · HTML: https://mlsanity.com/paper/1905.00475/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2019.

## Built on by (most cited first, 18 of 18)

- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs](https://mlsanity.com/paper/2405.06363/) (2024)
- [Low-Rank MDPs with Continuous Action Spaces](https://mlsanity.com/paper/2311.03564/) (2023)
- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [Provably Efficient and Agile Randomized Q-Learning](https://mlsanity.com/paper/2506.24005/) (2025)
- [Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2405.18793/) (2024)
- [Topological Foundations of Reinforcement Learning](https://mlsanity.com/paper/2410.03706/) (2024)
- [Bellman operator convergence enhancements in reinforcement learning algorithms](https://mlsanity.com/paper/2505.14564/) (2025)
- [Improving Reinforcement Learning Sample-Efficiency using Local Approximation](https://mlsanity.com/paper/2507.12383/) (2025)
- [Scrutinize What We Ignore: Reining In Task Representation Shift Of Context-Based Offline Meta Reinforcement Learning](https://mlsanity.com/paper/2405.12001/) (2024)
- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)

## Abstract (arXiv)

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.