Monte-Carlo graph search improves planning in stochastic problems
Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation
Machine Learning
Summary
Planning in uncertain environments can be inefficient because the same situation may be explored multiple times in different ways. The authors propose a new method called GS-Power-UCT that treats the problem as a graph rather than a tree, allowing it to share information across repeated states. This approach helps the planning algorithm learn faster and make better decisions while handling uncertainty and loops in the environment. Their experiments show that their method uses fewer simulations to find good plans compared to previous approaches.
What this means in practice
- •For robotics engineers: Improve autonomous robot decision making in uncertain environments by efficiently reusing planning simulations across repeated states.
- •For game ai developers: Enhance strategic decision algorithms in games that involve randomness and repeated game states by sharing samples in the search process.
Authors
Tung Tran, Viet Bao Mai, Hoang Ta, Tuan Dam
Abstract
Tree-based Monte-Carlo Tree Search (MCTS) duplicates the same state when it is reached through different trajectories, which can waste simulations in stochastic MDPs. We introduce Graph-Based Stochastic-Power-UCT (GS-Power-UCT), which shares states reached at the same planning depth while keeping separate values for states reached at different depths. This design applies to general stochastic MDPs, including problems with cycles. We prove that for a fixed planning horizon, the root estimate converges to the finite-horizon value at rate $O(n^{-1/2})$, matching tree-based Stochastic-Power-UCT while reusing samples across shared states. We also study two full-state variants: GS-Power-UCT-F, which stores one node per physical state to increase sample sharing but may mix values from different remaining horizons, and GS-Power-UCT-F$^+$, which uses an adaptive horizon to control this bias. The latter converges to $V^{\star}(s_0)$, the optimal infinite-horizon discounted value at the root state $s_0$, when the remaining cross-depth gap vanishes. Experiments on stochastic planning benchmarks show improved sample efficiency over tree-based and graph-based baselines.