Timezone: »

 
Poster
Monte Carlo Tree Search With Iteratively Refining State Abstractions
Samuel Sokota · Caleb Y Ho · Zaheen Ahmad · J. Zico Kolter

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »

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.

Keywords: Reinforcement Learning and Planning

Author Information

Samuel Sokota (Carnegie Mellon University)
Caleb Y Ho (Independent Researcher)
Zaheen Ahmad (University of Alberta)
J. Zico Kolter (Carnegie Mellon University / Bosch Center for A)

More from the Same Authors