Monte Carlo Tree Search (MCTS) is particularly adapted to domains where the potential actions can be represented as a tree of sequential decisions. For an effective action selection, MCTS performs many simulations to build a reliable tree representation of the decision space. As such, a bottleneck to MCTS appears when enough simulations cannot be performed between action selections. This is particularly highlighted in continuously running tasks, for which the time available to perform simulations between actions tends to be limited due to the environment's state constantly changing. In this paper, we present an approach that takes advantage of the anytime characteristic of MCTS to increase the simulation time when allowed. Our approach is to effectively balance the prospect of selecting an action with the time that can be spared to perform MCTS simulations before the next action selection. For that, we considered the simulation time as a decision variable to be selected alongside an action. We extended the Hierarchical Optimistic Optimization applied to Tree (HOOT) method to adapt our approach to environments with a continuous decision space. We evaluated our approach for environments with a continuous decision space through OpenAI gym's Pendulum and Continuous Mountain Car environments and for environments with discrete action space through the arcade learning environment (ALE) platform. The evaluation results show that, with variable simulation times, the proposed approach outperforms the conventional MCTS in the evaluated continuous decision space tasks and improves the performance of MCTS in most of the ALE tasks.
The combination of modern Reinforcement Learning and Deep Learning approaches holds the promise of making significant progress on challenging applications requiring both rich perception and policy-selection. The Arcade Learning Environment (ALE) provides a set of Atari games that represent a useful benchmark set of such applications. A recent breakthrough in combining model-free reinforcement learning with deep learning, called DQN, achieves the best real-time agents thus far. Planning-based approaches achieve far higher scores than the best model-free approaches, but they exploit information that is not available to human players, and they are orders of magnitude slower than needed for real-time play. Our main goal in this work is to build a better real-time Atari game playing agent than DQN. The central idea is to use the slow planning-based agents to provide training data for a deep-learning architecture capable of real-time play. We proposed new agents based on this idea and show that they outperform DQN. In this paper, Monte Carlo tree search (MCTS) is introduced for controlling the Pac-Man character in the real-time game Ms Pac-Man. MCTS is used to find an optimal path for an agent at each turn, determining the move to make based on the results of numerous randomized simulations. Several enhancements are introduced in order to adapt MCTS to the real-time domain. Ms Pac-Man is an arcade game, in which the protagonist has several goals but no conclusive terminal state. Unlike games such as Chess or Go there is no state in which the player wins the game. Instead, the game has two subgoals, 1) surviving and 2) scoring as many points as possible. Decisions must be made in a strict time constraint of 40 ms. The Pac-Man agent has to compete with a range of different ghost teams, hence limited assumptions can be made about their behavior. In order to expand the capabilities of existing MCTS agents, four enhancements are discussed: 1) a variable-depth tree; 2) simulation strategies for the ghost team and Pac-Man; 3) including long-term goals in scoring; and 4) reusing the search tree for several moves with a decay factor γ. The agent described in this paper was entered in both the 2012 World Congress on Computational Intelligence (WCCI'12, Brisbane, Qld., Australia) and the 2012 IEEE Conference on Computational Intelligence and Games (CIG'12, Granada, Spain) Pac-Man Versus Ghost Team competitions, where it achieved second and first places, respectively. In the experiments, we show that using MCTS is a viable technique for the Pac-Man agent. Moreover, the enhancements improve overall performance against four different ghost teams. Real world applications of artificial intelligence often require agents to sequentially choose actions from continuous action spaces with execution uncertainty. When good actions are sparse, domain knowledge is often used to identify a discrete set of promising actions. These actions and their uncertain effects are typically evaluated using a recursive search procedure. The reduction of the problem to a discrete search problem causes severe limitations, notably, not exploiting all of the sampled outcomes when evaluating actions, and not using outcomes to help find new actions outside the original set. We propose a new Monte Carlo tree search (MCTS) algorithm specifically designed for exploiting an execution model in this setting. Using kernel regression, it generalizes the information about action quality between actions and to unexplored parts of the action space. In a high fidelity simulator of the Olympic sport of curling, we show that this approach significantly outperforms existing MCTS methods. 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.