NeurIPS 2020poster46 citations
Planning in Markov Decision Processes with Gap-Dependent Sample Complexity
Anders Jonsson, Emilie Kaufmann, Pierre Menard, Omar Darwiche Domingues, Edouard Leurent, Michal Valko
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.
BibTeX
@inproceedings{NEURIPS2020_0d85eb24,
author = {Jonsson, Anders and Kaufmann, Emilie and Menard, Pierre and Darwiche Domingues, Omar and Leurent, Edouard and Valko, Michal},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {1253--1263},
publisher = {Curran Associates, Inc.},
title = {Planning in Markov Decision Processes with Gap-Dependent Sample Complexity},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/0d85eb24e2add96ff1a7021f83c1abc9-Paper.pdf},
volume = {33},
year = {2020}
}