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.
Introduction
Monte Carlo Tree Search (MCTS), specifically the UCT variant, is a cornerstone for solving large-scale planning problems like Markov Decision Processes (MDPs). However, UCT's reliance on random sampling for exploration can lead to slow convergence in massive state spaces. To accelerate this, researchers often "bootstrap" UCT with heuristic knowledge. Common approaches include initializing new nodes with heuristic values (UCT-I) or replacing random rollouts with a heuristic policy (UCT-S).
The primary challenge with these methods is their sensitivity to "imperfect" heuristics. If a heuristic provides misleading advice in certain states, UCT-I and UCT-S can be drawn into suboptimal regions, potentially performing worse than vanilla UCT. This paper introduces UCT-Aux, a method designed to exploit high-quality guidance when available while remaining robust to poor heuristic advice.
The UCT-Aux Method
The core innovation of UCT-Aux is the introduction of an auxiliary arm at every internal node of the search tree. Instead of using the heuristic to modify existing node values or rollout policies, UCT-Aux treats the heuristic policy ($\pi$) as an additional choice that competes with standard actions.
Key features of UCT-Aux include:
- Selection: The auxiliary arm is selected using the standard UCB1 formula. If the heuristic yields high rewards, the algorithm naturally favors it.
- Rollout Logic: When the auxiliary arm is chosen, the algorithm does not expand the tree. Instead, it immediately performs a rollout using the heuristic policy to obtain a value estimate.
- Convergence: The authors prove that UCT-Aux eventually converges to the optimal policy regardless of heuristic quality, given sufficient sampling time.
Experimental Evaluation
The algorithm was tested in two complex planning domains designed to challenge heuristic-based search:
- Obstructed Sailing: A navigation task where a boat must reach a goal under stochastic wind conditions. The environment is populated with random obstacles that make a simple "sail toward goal" heuristic misleading in many states.
- Sheep Savior: A massive collaborative game with approximately $10^{11}$ states. The heuristic used, "GoalAveraging," solves individual sub-tasks perfectly but fails to account for complex multi-agent interactions.
Key Results and Insights
UCT-Aux consistently outperformed vanilla UCT, UCT-I, and UCT-S in both domains. Notably, in the Sheep Savior domain, UCT-Aux showed significant advantages at low rollout counts (200–500), which is critical for real-time AI applications.
- Robustness to Misleading Advice: While UCT-I and UCT-S often performed worse than vanilla UCT when faced with misleading heuristics, UCT-Aux remained competitive or superior. It effectively "ignores" the auxiliary arm if it consistently returns poor values.
- Efficiency: In scenarios where the heuristic is mediocre, UCT-Aux can build trees up to 20x smaller than vanilla UCT because it spends its sampling budget on the non-expansive auxiliary arm rather than unnecessary node expansions.
- The "Mild Heuristic" Limitation: The authors identified a specific failure case: if a heuristic is "better than random" but still significantly worse than optimal (a "mild" heuristic), UCB1's optimism may cause the algorithm to over-sample the auxiliary arm. This can prevent the tree from growing deep enough to discover the true optimal path.
Conclusion
UCT-Aux provides a simple yet powerful framework for integrating imperfect heuristics into MCTS. By treating the heuristic as a competing arm rather than a replacement for exploration, the algorithm achieves a better balance between exploitation of prior knowledge and robust discovery of optimal strategies. Future work includes extending this approach to adversarial domains like Go or Chess.
Summary updated