Lookahead Pathology in Monte-Carlo Tree Search

Authors

  • Khoi P. N. Nguyen University of Texas at Dallas, Richardson, TX
  • Raghuram Ramanujan Davidson College, Davidson, NC

DOI:

https://doi.org/10.1609/icaps.v34i1.31501

Abstract

Monte-Carlo Tree Search (MCTS) is a search paradigm that first found prominence with its success in the domain of computer Go. Early theoretical work established the soundness and convergence bounds for Upper Confidence bounds applied to Trees (UCT), the most popular instantiation of MCTS; however, there remain notable gaps in our understanding of how UCT behaves in practice. In this work, we address one such gap by considering the question of whether UCT can exhibit lookahead pathology in adversarial settings --- a paradoxical phenomenon first observed in Minimax search where greater search effort leads to worse decision-making. We introduce a novel family of synthetic games that offer rich modeling possibilities while remaining amenable to mathematical analysis. Our theoretical and experimental results suggest that UCT is indeed susceptible to pathological behavior in a range of games drawn from this family.

Downloads

Published

2024-05-30

How to Cite

Nguyen, K. P. N., & Ramanujan, R. (2024). Lookahead Pathology in Monte-Carlo Tree Search. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 414-422. https://doi.org/10.1609/icaps.v34i1.31501