Provably adaptive reinforcement learning in metric spaces

Tongyi Cao; Akshay Krishnamurthy

NeurIPS 2020poster11 citations

Provably adaptive reinforcement learning in metric spaces

Abstract

We study reinforcement learning in continuous state and action spaces endowed with a metric. We provide a refined analysis 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.

BibTeX

@inproceedings{NEURIPS2020_6ef1173b,
 author = {Cao, Tongyi and Krishnamurthy, Akshay},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
 pages = {9736--9744},
 publisher = {Curran Associates, Inc.},
 title = {Provably adaptive reinforcement learning in metric spaces},
 url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/6ef1173b096aa200158bfbc8af3ae8e3-Paper.pdf},
 volume = {33},
 year = {2020}
}