Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

Max Simchowitz; Kevin G. Jamieson

NeurIPS 2019poster181 citations

Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

Abstract

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\widetilde{\mathcal{O}}(\sqrt{HSAT})$-minimax rate. The key technique in our analysis is a novel ``clipped'' regret decomposition which applies to a broad family of recent optimistic algorithms for episodic MDPs.

BibTeX

@inproceedings{NEURIPS2019_10a5ab2d,
 author = {Simchowitz, Max and Jamieson, Kevin G},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs},
 url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/10a5ab2db37feedfdeaab192ead4ac0e-Paper.pdf},
 volume = {32},
 year = {2019}
}