Monte Carlo Tree Search in the Presence of Transition Uncertainty
Farnaz Kohankhaki Kiarash Aghakasiri Hongming Zhang Ting-Han Wei Chao Gao Martin Müller
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.