Planning in Markov Decision Processes with ...
Type de document :
Communication dans un congrès avec actes
Titre :
Planning in Markov Decision Processes with Gap-Dependent Sample Complexity
Auteur(s) :
Jonsson, Anders [Auteur]
Kaufmann, Emilie [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Scool [Scool]
Ménard, Pierre [Auteur]
Scool [Scool]
Domingues, Omar [Auteur]
Scool [Scool]
Leurent, Edouard [Auteur]
RENAULT
Scool [Scool]
Valko, Michal [Auteur]
DeepMind [Paris]
Kaufmann, Emilie [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Scool [Scool]
Ménard, Pierre [Auteur]
Scool [Scool]
Domingues, Omar [Auteur]
Scool [Scool]
Leurent, Edouard [Auteur]
RENAULT
Scool [Scool]
Valko, Michal [Auteur]
DeepMind [Paris]
Titre de la manifestation scientifique :
Neural Information Processing Systems
Ville :
Vancouver
Pays :
France
Date de début de la manifestation scientifique :
2020
Date de publication :
2020-12-07
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Résumé en anglais : [en]
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 calls to the ...
Lire la suite >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 calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent sample complexity 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.Lire moins >
Lire la suite >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 calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent sample complexity 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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-02863486v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02863486v2/file/budget.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02863486v2/file/simple_regret.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02863486v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02863486v2/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- MDPGapE_hal.pdf
- Accès libre
- Accéder au document
- budget.pdf
- Accès libre
- Accéder au document
- simple_regret.pdf
- Accès libre
- Accéder au document