Provably adaptive reinforcement learning in metric spaces
arXiv:2006.10875
Abstract
We study reinforcement learning in continuous state and action spaces endowed with a metric. We provide a refined analysis of a variant of the algorithm of Sinclair, Banerjee, and Yu (2019) and show that its regret scales with the \emph{zooming dimension} of the instance. This parameter, which originates in the bandit literature, captures the size of the subsets of near optimal actions and is always smaller than the covering dimension used in previous analyses. As such, our results are the first provably adaptive guarantees for reinforcement learning in metric spaces.
arXiv commentPublished in NeurIPS 2020. This version fixes a bug in the published version
References in corpus (6)
- Contextual Bandits with Similarity Information
- Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
- Stochastic simultaneous optimistic optimization
- Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
- Efficient Model-free Reinforcement Learning in Metric Spaces
- Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces