# Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2020.

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

- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Finding Counterfactually Optimal Action Sequences in Continuous State Spaces](https://mlsanity.com/paper/2306.03929/) (2023)
- [Adaptive Discretization using Voronoi Trees for Continuous POMDPs](https://mlsanity.com/paper/2302.10439/) (2023)
- [BF++: a language for general-purpose program synthesis](https://mlsanity.com/paper/2101.09571/) (2021)
- [Adaptive Discretization using Voronoi Trees for Continuous-Action POMDPs](https://mlsanity.com/paper/2209.05733/) (2022)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [Review of Metrics to Measure the Stability, Robustness and Resilience of Reinforcement Learning](https://mlsanity.com/paper/2203.12048/) (2022)

## Abstract (arXiv)

Despite the wealth of research into provably efficient reinforcement learning algorithms, most works focus on tabular representation and thus struggle to handle exponentially or infinitely large state-action spaces. In this paper, we consider episodic reinforcement learning with a continuous state-action space which is assumed to be equipped with a natural metric that characterizes the proximity between different states and actions. We propose ZoomRL, an online algorithm that leverages ideas from continuous bandits to learn an adaptive discretization of the joint space by zooming in more promising and frequently visited regions while carefully balancing the exploitation-exploration trade-off. We show that ZoomRL achieves a worst-case regret tildeO(H^frac52 K^fracd+1d+2) where H is the planning horizon, K is the number of episodes and d is the covering dimension of the space with respect to the metric. Moreover, our algorithm enjoys improved metric-dependent guarantees that reflect the geometry of the underlying space. Finally, we show that our algorithm is robust to small misspecification errors.