Improvements of Monte Carlo Tree Search for Real Applications

In recent years techniques of sequential decision making have taken a flight. This is, for instance, exemplified by the AlphaGo program that beat an 18 time world champion at the game of Go [1]. Many of the recent advances are based on simulation-based (also ’sample based’) planning and, in particular, so-called Monte Carlo Tree Search (MCTS) methods [2,3].

These are very flexible: as long as one is confident enough to specify a (stochastic) simulator of the system to be controlled, the techniques enable principled decision making: in the limit they will converge to the optimal policy that takes into account execution uncertainty (e.g., stochastic outcome of actions) in a principled fashion. However, despite this flexibility, there are some domain properties that are challenging for MCTS:

1. It is difficult to deal with large number of actions, as for instance found in the control of multiagent teams [4].
2. In practice, performance depends a lot on the quality of the roll out policy, so it is important that a ’reasonable’ policy can be provided for this purpose.
3. Standard MCTS methods re-plan everything at every stage; a problem in cases where the amount of computation that can be performed for every decision epoch is limited.
4. MCTS plans for the given simulator; this means that if this simulator is incorrect (e.g., sampling from the true transition probabilities might be inherently too complex), or if the environment changes over time, performance is affected.
5. MCTS plans at a single time resolution, but in many real-world applications different types of dependent decisions might need to be made at different time scales.

The goal of this project is to explore advances in MCTS that address these difficulties in the context of two application settings: nano-grids [5] and multi-robot teams [6,7,].

For academic enquiries please contact Dr Frans Oliehoek [Email Address Removed]

For enquiries on the application process or to find out more about the Dual programme please contact Miss Hannah Fosh [Email Address Removed]