Monte Carlo Tree Search in the Presence of Model Uncertainty

• Author / Creator

  Aghakasiri, Kiarash

• Monte Carlo Tree Search (MCTS) is an extremely successful search-based frame- work for decision making. With an accurate simulator of the environment’s dynamics, it can achieve great performance in many games and non-games applications. However, without a perfect simulator, the performance degradation is so high that it can make the framework almost useless. Therefore, we propose two methods to improve the performance of MCTS in such a scenario: Deep Q-Network MCTS (DQMCTS) and Uncertainty Adapted MCTS (UAMCTS). In the former, we use the model-free algorithm DQN to evaluate the leaf nodes in the search tree. Although this approach shows promising improvement over baseline MCTS, our results show that there is still more room for improvement. In UAMCTS, we take a more fundamental approach and change the behavior of MCTS’s components to directly take the model incorrectness into account. Our results show that with an accurate measure of model incorrectness, UAMCTS can achieve the performance of MCTS with a perfect simulator in some cases. Even with a poor measure of model error, UAMCTS can still outperform plain MCTS with an imperfect simulator.

• Subjects / Keywords

  • Reinforcement Learning
  • Monte Carlo Tree Search

• Graduation date

  Fall 2022

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-c430-5f26

• License

  This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.