Monte Carlo Tree Search With Iteratively Refining State Abstractions
Samuel Sokota, Caleb Ho, Zaheen Farraz Ahmad, J Zico Kolter
Abstract
Decision-time planning is the process of constructing a transient, local policy with the intent of using it to make the immediate decision. Monte Carlo tree search (MCTS), which has been leveraged to great success in Go, chess, shogi, Hex, Atari, and other settings, is perhaps the most celebrated decision-time planning algorithm. Unfortunately, in its original form, MCTS can degenerate to one-step search in domains with stochasticity. Progressive widening is one way to ameliorate this issue, but we argue that it possesses undesirable properties for some settings. In this work, we present a method, called abstraction refining, for extending MCTS to stochastic environments which, unlike progressive widening, leverages the geometry of the state space. We argue that leveraging the geometry of the space can offer advantages. To support this claim, we present a series of experimental examples in which abstraction refining outperforms progressive widening, given equal simulation budgets.
BibTeX
@inproceedings{
sokota2021monte,
title={Monte Carlo Tree Search With Iteratively Refining State Abstractions},
author={Samuel Sokota and Caleb Ho and Zaheen Farraz Ahmad and J Zico Kolter},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=0qnPBmvJSaf}
}