Monte Carlo Tree Search for Continuous and Stochastic Sequential Decision Making Problems

2013 
Dans cette these, nous avons etudie les problemes de decisions sequentielles, avec comme application la gestion de stocks d'energie. Traditionnellement, ces problemes sont resolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexite du probleme, amenent a faire des simplifications sur le modele pour pouvoir faire fonctionner ces methodes.Nous avons donc etudie une methode alternative, qui ne requiert pas de simplifications du modele: Monte Carlo Tree Search (MCTS). Nous avons commence par etendre le MCTS classique (qui s’applique aux domaines finis et deterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilise la methode de Double Progressive Widening (DPW), qui permet de gerer le ratio entre largeur et profondeur de l’arbre, a l’aide de deux meta parametres. Nous avons aussi propose une heuristique nommee Blind Value (BV) pour ameliorer la recherche de nouvelles actions, en utilisant l’information donnee par les simulations passees. D’autre part, nous avons etendu l’heuristique RAVE aux domaines continus. Enfin, nous avons propose deux nouvelles methodes pour faire remonter l’information dans l’arbre, qui ont beaucoup ameliore la vitesse de convergence sur deux cas tests.Une part importante de notre travail a ete de proposer une facon de meler MCTS avec des heuristiques rapides pre-existantes. C’est une idee particulierement interessante dans le cas de la gestion d’energie, car ces problemes sont pour le moment resolus de maniere approchee. Nous avons montre comment utiliser Direct Policy Search (DPS) pour rechercher une politique par defaut efficace, qui est ensuite utilisee a l’interieur de MCTS. Les resultats experimentaux sont tres encourageants.Nous avons aussi applique MCTS a des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de demineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l’est, en transformant le POMDP en MDP, par un changement de vecteur d’etat.Enfin, nous avons utilise MCTS dans un cadre de meta-bandit, pour resoudre des problemes d’investissement. Le choix d’investissement est fait par des algorithmes de bandits a bras multiples, tandis que l’evaluation de chaque bras est faite par MCTS.Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de tres peu d’hypotheses (uniquement un modele generatif du probleme), converge vers l’optimum, et peut facilement ameliorer des methodes suboptimales existantes.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    120
    References
    13
    Citations
    NaN
    KQI
    []