NeurIPS 2019poster20 citations
Planning in entropy-regularized Markov decision processes and games
Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Menard, Remi Munos, Michal Valko
Abstract
We propose SmoothCruiser, a new planning algorithm for estimating the value function in entropy-regularized Markov decision processes and two-player games, given a generative model of the SmoothCruiser. SmoothCruiser makes use of the smoothness of the Bellman operator promoted by the regularization to achieve problem-independent sample complexity of order $\tilde{\mathcal{O}}(1/\epsilon^4)$ for a desired accuracy $\epsilon$, whereas for non-regularized settings there are no known algorithms with guaranteed polynomial sample complexity in the worst case.
BibTeX
@inproceedings{NEURIPS2019_50982fb2,
author = {Grill, Jean-Bastien and Darwiche Domingues, Omar and Menard, Pierre and Munos, Remi and Valko, Michal},
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 = {Planning in entropy-regularized Markov decision processes and games},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/50982fb2f2cfa186d335310461dfa2be-Paper.pdf},
volume = {32},
year = {2019}
}