Bootstrapping Monte Carlo Tree Search with an Imperfect Heuristic

Truong-Huy Dinh Nguyen, Wee Sun Lee, Tze-Yun Leong

TL;DR

This paper introduces UCT-Aux, a novel method to improve Monte Carlo Tree Search (MCTS) by adding an "auxiliary arm" to each decision node. This arm leverages an imperfect heuristic policy to guide simulations, leading to faster convergence and better performance in large-scale planning problems compared to existing MCTS enhancements.

What Problem Does This Paper Address?

Monte Carlo Tree Search (MCTS), particularly its UCT variant, is a powerful technique for solving complex planning problems in domains like game playing and robotics. However, UCT's reliance on random sampling can lead to slow convergence to optimal solutions, especially in large state spaces. Existing improvements often focus on modifying the action selection strategy or the rollout policy. While these methods can be effective, they can also be misled by inaccurate heuristics, potentially leading the search astray. This paper addresses the challenge of effectively incorporating imperfect heuristic knowledge into MCTS to accelerate learning without sacrificing robustness.

Methods

The core contribution is the UCT-Aux algorithm. It builds upon the standard UCT framework by introducing a simple yet effective modification: at each internal node of the search tree, an additional "auxiliary arm" is added. This arm is specifically designed to utilize a given heuristic policy ($\pi$). When this auxiliary arm is selected by the UCT's exploration strategy (UCB1), it immediately performs a simulation rollout using the heuristic policy $\pi$, rather than exploring the standard action branches.

The key idea is that if the heuristic policy is good in a particular state, this auxiliary arm will quickly provide a reliable estimate of the state's value, accelerating convergence. If the heuristic is poor, the standard UCT exploration will naturally favor the other "ordinary" arms, ensuring that the algorithm doesn't get stuck due to a bad heuristic. This approach aims to achieve fast convergence in states where the heuristic is accurate while maintaining performance similar to standard UCT in other states. For stochastic heuristics, multiple auxiliary arms can be added, one for each possible action of the heuristic.

Datasets

The paper evaluates UCT-Aux on two benchmark domains:

  • Obstructed Sailing: An extension of the original Sailing domain, featuring a boat navigation task with obstacles and changing wind conditions. This domain is modeled as an infinite-horizon discounted Markov Decision Process (MDP).
  • Sheep Savior: A two-player cooperative game where players herd a sheep into a pen while avoiding ghosts. This domain is also modeled as an MDP.

The paper does not introduce new datasets but uses these established benchmarks to compare UCT-Aux against other MCTS variants.

Key Insights and Ideas

  • "Make or Break It" Heuristics: UCT-Aux performs best when coupled with "extreme" heuristics. These heuristics provide near-optimal estimates in some situations but can be significantly misleading in others. This "extreme" behavior allows UCT-Aux to effectively exploit good heuristic guidance while naturally falling back to exploration when the heuristic is unreliable.
  • Orthogonal Enhancement: UCT-Aux is designed to be orthogonal to other bootstrapping techniques (like UCT-I and UCT-S). This means it can be combined with them to potentially achieve even greater performance gains by leveraging multiple sources of heuristic knowledge.
  • Targeted Exploration: By dedicating an auxiliary arm to the heuristic, UCT-Aux intelligently directs computational effort. It prioritizes exploring promising states identified by the heuristic, rather than relying solely on random sampling or a modified exploration strategy across all actions.

Key Results

  • Superior Performance: UCT-Aux consistently outperforms vanilla UCT and other bootstrapping methods (UCT-I, UCT-S, UCT-IS) in both the Obstructed Sailing and Sheep Savior domains when paired with appropriate "extreme" heuristics.
  • Faster Convergence: The auxiliary arm allows UCT-Aux to achieve good performance with significantly fewer rollouts compared to other methods, especially in the early stages of learning. For instance, in Obstructed Sailing with a suboptimal heuristic, UCT-Aux constructed search trees with up to 20 times fewer nodes than other variants for the same number of samplings.
  • Robustness to Imperfect Heuristics: While UCT-S can be severely hampered by inaccurate heuristics, UCT-Aux mitigates this by allowing standard UCT exploration to dominate when the heuristic is misleading.

Limitations and Future Work

  • Heuristic Quality Dependency: The effectiveness of UCT-Aux is highly dependent on the quality and "extremeness" of the heuristic policy. If the heuristic is only mildly suboptimal or consistently inaccurate, UCT-Aux may not offer significant advantages.
  • "Worst-Case" Behavior: The paper identifies scenarios where UCT-Aux can perform poorly, particularly when coupled with heuristics that are "mostly better than random but much worse than optimal." This is attributed to the inherent optimism of the UCB1 exploration strategy, which can lead to excessive sampling of suboptimal auxiliary arms.
  • Future Work: The authors suggest exploring how UCT-Aux can be adapted for adversarial domains and investigating combinations with other heuristic-based enhancements. They also propose that heuristic designers should consider creating "greedier" and "riskier" heuristics specifically for UCT-Aux, rather than focusing solely on safe, broadly applicable ones.

Summary updated

Abstract

We consider the problem of using a heuristic policy to improve the value approximation by the Upper Confidence Bound applied in Trees (UCT) algorithm in non-adversarial settings such as planning with large-state space Markov Decision Processes. Current improvements to UCT focus on either changing the action selection formula at the internal nodes or the rollout policy at the leaf nodes of the search tree. In this work, we propose to add an auxiliary arm to each of the internal nodes, and always use the heuristic policy to roll out simulations at the auxiliary arms. The method aims to get fast convergence to optimal values at states where the heuristic policy is optimal, while retaining similar approximation as the original UCT in other states. We show that bootstrapping with the proposed method in the new algorithm, UCT-Aux, performs better compared to the original UCT algorithm and its variants in two benchmark experiment settings. We also examine conditions under which UCT-Aux works well.
BibTeX
@inproceedings{nguyen2012bootstrapping,
  author = {Truong-Huy Dinh Nguyen and Wee Sun Lee and Tze-Yun Leong},
  title = {{Bootstrapping Monte Carlo Tree Search with an Imperfect Heuristic}},
  booktitle = {ECML/PKDD},
  year = {2012},
  doi = {10.1007/978-3-642-33486-3\_11},
}

Loading related content...

Figure