Provably adaptive reinforcement learning in metric spaces

2020/06/18 by Tongyi Cao, Akshay Krishnamurthy, Cao, Tongyi +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2006.10875

openalex publication_date 2020/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 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.

Citations

• Efficient Model-free Reinforcement Learning in Metric Spaces

Related

• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
• Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces
• Learning to Control in Metric Space with Optimal Regret
• Metrics and continuity in reinforcement learning
• Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting