Continuous Upper Confidence Trees with Polynomial Exploration - Consistency
Abstract
Upper Confidence Trees (UCT) are now a well known algorithm for sequential decision making; it is a provably consistent variant of Monte-Carlo Tree Search. However, the consistency is only proved in a the case where the action space is finite. We here propose a proof in the case of fully observable Markov Decision Processes with bounded horizon, possibly including infinitely many states, infinite action space and arbitrary stochastic transition kernels. We illustrate the consistency on two benchmark problems, one being a legacy toy problem, the other a more challenging one, the famous energy unit commitment problem.
Cite
Text
Auger et al. "Continuous Upper Confidence Trees with Polynomial Exploration - Consistency." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013. doi:10.1007/978-3-642-40988-2_13Markdown
[Auger et al. "Continuous Upper Confidence Trees with Polynomial Exploration - Consistency." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013.](https://mlanthology.org/ecmlpkdd/2013/auger2013ecmlpkdd-continuous/) doi:10.1007/978-3-642-40988-2_13BibTeX
@inproceedings{auger2013ecmlpkdd-continuous,
title = {{Continuous Upper Confidence Trees with Polynomial Exploration - Consistency}},
author = {Auger, David and Couëtoux, Adrien and Teytaud, Olivier},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2013},
pages = {194-209},
doi = {10.1007/978-3-642-40988-2_13},
url = {https://mlanthology.org/ecmlpkdd/2013/auger2013ecmlpkdd-continuous/}
}