Planning in Markov Decision Processes with Gap-Dependent Sample Complexity
Abstract
We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process in which transitions have a finite support. We prove an upper bound on the number of sampled trajectories needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent result is expressed in terms of the sub-optimality gaps of the state-action pairs that are visited during exploration. Our experiments reveal that MDP-GapE is also effective in practice, in contrast with other algorithms with sample complexity guarantees in the fixed-confidence setting, that are mostly theoretical.
Cite
Text
Jonsson et al. "Planning in Markov Decision Processes with Gap-Dependent Sample Complexity." Neural Information Processing Systems, 2020.Markdown
[Jonsson et al. "Planning in Markov Decision Processes with Gap-Dependent Sample Complexity." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/jonsson2020neurips-planning/)BibTeX
@inproceedings{jonsson2020neurips-planning,
title = {{Planning in Markov Decision Processes with Gap-Dependent Sample Complexity}},
author = {Jonsson, Anders and Kaufmann, Emilie and Menard, Pierre and Domingues, Omar Darwiche and Leurent, Edouard and Valko, Michal},
booktitle = {Neural Information Processing Systems},
year = {2020},
url = {https://mlanthology.org/neurips/2020/jonsson2020neurips-planning/}
}