Provably adaptive reinforcement learning in metric spaces
This work offers improved theoretical bounds for reinforcement learning in continuous spaces, which is incremental but addresses a specific bottleneck in adaptive learning.
The paper tackles reinforcement learning in continuous metric spaces by refining an existing algorithm to achieve regret scaling with the zooming dimension, which is smaller than the covering dimension used previously, providing the first provably adaptive guarantees.
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.