Planification dans les processus de décision de Markov avec une complexité d'échantillon dépendant de l'écart.

Résumé Nous proposons MDP-GapE, un nouvel algorithme de Monte-Carlo Tree Search basé sur la trajectoire pour la planification dans un processus de décision de Markov dans lequel les transitions ont un support fini. Nous prouvons une limite supérieure sur le nombre d'appels aux modèles génératifs nécessaires pour que MDP-GapE identifie une action quasi-optimale avec une probabilité élevée. Ce résultat de complexité d'échantillon dépendant du problème est exprimé en termes d'écarts de sous-optimalité des paires état-action qui sont visitées pendant l'exploration. Nos expériences révèlent que MDP-GapE est également efficace en pratique, contrairement à d'autres algorithmes avec des garanties de complexité d'échantillon dans le cadre de la confiance fixe, qui sont principalement théoriques.