Monte Carlo Tree Search in the Presence of Transition Uncertainty

Farnaz Kohankhaki, Kiarash Aghakasiri, Hongming Zhang, Ting-Han Wei, Chao Gao, Martin Müller

Abstract

Monte Carlo Tree Search (MCTS) is an immensely popular search-based framework used for decision making. It is traditionally applied to domains where a perfect simulation model of the environment is available. We study and improve MCTS in the context where the environment model is given but imperfect. We show that the discrepancy between the model and the actual environment can lead to significant performance degradation with standard MCTS. We therefore develop Uncertainty Adapted MCTS (UA-MCTS), a more robust algorithm within the MCTS framework. We estimate the transition uncertainty in the given model, and direct the search towards more certain transitions in the state space. We modify all four MCTS phases to improve the search behavior by considering these estimates. We prove, in the corrupted bandit case, that adding uncertainty information to adapt UCB leads to tighter regret bound than standard UCB. Empirically, we evaluate UA-MCTS and its individual components on the deterministic domains from the MinAtar test suite. Our results demonstrate that UA-MCTS strongly improves MCTS in the presence of model transition errors.

Introduction

Monte Carlo Tree Search (MCTS) has been the cornerstone of major AI breakthroughs, such as AlphaZero. However, its success typically hinges on the availability of a "perfect" simulator. In real-world scenarios or model-based reinforcement learning (MBRL), agents often rely on approximations that may be inaccurate due to limited data or unmodeled dynamics.

Standard MCTS blindly trusts its internal model. If the model incorrectly predicts that an action leads to a high-reward state—a phenomenon known as a "hallucination"—the search will waste computational resources exploring these non-existent opportunities. This paper introduces Uncertainty Adapted MCTS (UA-MCTS), which formalizes transition uncertainty and integrates it into the search logic to make agents risk-averse toward model errors.

Methodology: UA-MCTS

UA-MCTS adapts the four standard phases of the MCTS cycle using an estimated uncertainty value $\hat{U}(s, a)$, derived from a neural network that learns the squared difference between predicted and actual state transitions.

  1. UA-Selection: The UCT (Upper Confidence Bound applied to Trees) formula is modified so that the exploration term is dampened by the uncertainty of the node. High uncertainty effectively "mutes" exploration in that branch.
  2. UA-Expansion: A pruning mechanism is introduced. Children that the model is most unsure about are eliminated with a probability tied to their uncertainty factor.
  3. UA-Simulation: Rollout returns are weighted based on cumulative trajectory uncertainty. Returns from highly uncertain paths contribute less to the final evaluation.
  4. UA-Backpropagation: When updating parent nodes, values from "certain" children are prioritized over those from "uncertain" ones.

Experimental Evaluation

The researchers evaluated UA-MCTS on two fronts: the MinAtar Suite (using "slightly broken" versions of Space Invaders, Freeway, and Breakout) and a custom 2-Way GridWorld designed to test the efficiency of learning uncertainty versus learning full transition functions.

Performance of UA-MCTS and its components on Space Invaders. The combined approach (Online UA-MCTS) significantly outperforms the corrupted baseline and even the true model.

In Space Invaders, UA-MCTS achieved an average reward of 23.8 (near the perfect score of 24), while the standard MCTS with a corrupted model reached only 16.3. Interestingly, UA-MCTS even outperformed an agent using the perfect model. This occurred because the uncertainty-aware agent learned to avoid "buggy" states entirely, making its search more efficient than an agent that accurately evaluated low-value states.

Key Insights

Scalar vs. High-Dimensional Learning

A critical finding is that learning a single scalar value (uncertainty) is significantly more sample-efficient than learning a complex, high-dimensional transition function. In GridWorld tests, agents attempting to learn the full transition function often failed to find the goal, whereas UA-MCTS succeeded using the same amount of data.

Comparison of learning efficiency: UA-MCTS (purple) converges to the optimal number of steps much faster than models attempting to learn the full transition function (blue/cyan).

Theoretical and Empirical Robustness

The paper proves that UA-MCTS maintains "completeness," ensuring that it will eventually explore all nodes given infinite iterations. This prevents the agent from permanently ignoring potentially good areas that are currently poorly modeled. Furthermore, the authors proved that incorporating uncertainty leads to tighter regret bounds in the "corrupted bandit" case compared to standard UCB.

Conclusion

UA-MCTS demonstrates that agents can remain robust even when their internal simulators are flawed. By favoring "certain" paths, the algorithm avoids the pitfalls of misleading models. While currently focused on deterministic environments and risk-aversion, future work may explore risk-seeking variants and methods to distinguish between model uncertainty and inherent environmental stochasticity.

Summary updated

Abstract

Monte Carlo Tree Search (MCTS) is an immensely popular search-based framework used for decision making. It is traditionally applied to domains where a perfect simulation model of the environment is available. We study and improve MCTS in the context where the environment model is given but imperfect. We show that the discrepancy between the model and the actual environment can lead to significant performance degradation with standard MCTS. We therefore develop Uncertainty Adapted MCTS (UA-MCTS), a more robust algorithm within the MCTS framework. We estimate the transition uncertainty in the given model, and direct the search towards more certain transitions in the state space. We modify all four MCTS phases to improve the search behavior by considering these estimates. We prove, in the corrupted bandit case, that adding uncertainty information to adapt UCB leads to tighter regret bound than standard UCB. Empirically, we evaluate UA-MCTS and its individual components on the deterministic domains from the MinAtar test suite. Our results demonstrate that UA-MCTS strongly improves MCTS in the presence of model transition errors.
BibTeX
@inproceedings{kohankhaki2024monte,
  author = {Farnaz Kohankhaki and Kiarash Aghakasiri and Hongming Zhang and Ting-Han Wei and Chao Gao and Martin Müller},
  title = {{Monte Carlo Tree Search in the Presence of Transition Uncertainty}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=FzcKoeWwMR},
}
Figure