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 a cornerstone of recent breakthroughs in artificial intelligence, most notably in games like Go. However, these successes typically rely on the availability of a perfect simulator. In real-world applications such as robotics or logistics, we often operate with an imperfect model—one that may be learned from sparse data or represents a degraded version of reality.

When standard MCTS utilizes an inaccurate model, it frequently suffers from "optimism under uncertainty," pursuing paths that appear high-value in simulation but are unachievable or unreliable in the real environment. This research introduces Uncertainty Adapted MCTS (UA-MCTS), a framework designed to be risk-averse regarding model errors by guiding search toward trustworthy regions of the state space.

Methodology: Uncertainty Adapted MCTS

UA-MCTS modifies the four fundamental phases of the MCTS cycle by integrating a learned estimate of transition uncertainty ($\hat{U}$):

  1. UA-Selection: The Upper Confidence Bound (UCB) formula is modified to dampen the exploration of nodes associated with high predicted uncertainty.
  2. UA-Expansion: New nodes are added to the tree probabilistically; children with high uncertainty are "pruned" to prevent the tree from expanding into unreliable territory.
  3. UA-Simulation: Rollout rewards are calculated as a weighted average, where rollouts accumulating high uncertainty are penalized.
  4. UA-Backpropagation: Parent nodes are updated using a weighting scheme that prioritizes the contributions of more reliable child nodes.

To support these modifications, a neural network uncertainty model is trained via regression to predict the squared difference between the imperfect model's predictions and the actual environment transitions.

Experimental Evaluation

The framework was evaluated using the MinAtar test suite, featuring environments with specific "corruptions":

  • Space Invaders: The "shoot" action is disabled in 50% of positions.
  • Freeway: The "None" action causes unintended movement in specific locations.
  • Breakout: The paddle fails in designated "dead zones."
Performance comparison in Space Invaders showing UA-MCTS (Combined) outperforming the Corrupted and even the True Model.

In Space Invaders, UA-MCTS achieved an average reward of 23.8, significantly outperforming standard MCTS on the corrupted model (16.3). Notably, UA-MCTS even surpassed the "True Model" baseline. By identifying and avoiding uncertain states (where shooting was impossible), the agent optimized its search time more effectively than an agent that simply knew the rules but explored all possibilities.

Discussion and Insights

A critical finding of this work is that uncertainty is easier to learn than physics. Learning a scalar value representing "model error" requires fewer parameters and less data than learning a full transition function for a complex environment.

Comparison of learning a full transition model versus learning uncertainty in a GridWorld environment.

As shown in the GridWorld experiments, UA-MCTS (using linear regression for uncertainty) converges to an efficient path much faster than methods attempting to learn the full transition dynamics. Furthermore, the authors provide theoretical grounding by proving that UA-MCTS maintains "completeness," ensuring that the algorithm will eventually explore the entire tree given sufficient time, despite its risk-averse bias.

Conclusion

UA-MCTS provides a robust alternative to standard search algorithms when environment models are unreliable. By explicitly modeling and acting upon transition uncertainty, the framework avoids the pitfalls of hallucinated rewards. Future work may address the balance between risk-aversion and exploration in non-stationary environments or scenarios where high-uncertainty regions are necessary to reach a goal.

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