Continuous Upper Confidence Trees with Polynomial Exploration - Consistency

David Auger 1 Adrien Couetoux 2 Olivier Teytaud 2, 3
1 AlCAAP - Algorithmique, Combinatoire Analytique et Applications
PRISM - Parallélisme, Réseaux, Systèmes, Modélisation
3 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
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 both 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 and infinite action spaces 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.
Type de document :
Communication dans un congrès
Hendrik Blockeel and Kristian Kersting and Siegfried Nijssen and Filip Železný. ECML/PKKD 2013, Sep 2013, Prague, Czech Republic. Springer Verlag, 8188, pp.194-209, 2013, LNCS
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00835352
Contributeur : Adrien Couetoux <>
Soumis le : mardi 18 juin 2013 - 15:26:31
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 19 septembre 2013 - 04:11:19

Fichier

doublePWConf.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00835352, version 1

Collections

Citation

David Auger, Adrien Couetoux, Olivier Teytaud. Continuous Upper Confidence Trees with Polynomial Exploration - Consistency. Hendrik Blockeel and Kristian Kersting and Siegfried Nijssen and Filip Železný. ECML/PKKD 2013, Sep 2013, Prague, Czech Republic. Springer Verlag, 8188, pp.194-209, 2013, LNCS. 〈hal-00835352〉

Partager

Métriques

Consultations de la notice

512

Téléchargements de fichiers

695