# Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

arXiv: https://arxiv.org/abs/2609.19956 · HTML: https://mlsanity.com/paper/2609.19956/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 28 references that are in the map.
- First posted on arXiv 17 Sep 2026.

## Builds on (most cited first, 9 of 9)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Generalized Mean Estimation in Monte-Carlo Tree Search](https://mlsanity.com/paper/1911.00384/) (2019)
- [A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search](https://mlsanity.com/paper/2202.07071/) (2022)
- [Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning](https://mlsanity.com/paper/2604.14974/) (2026)
- [Power Mean Estimation in Stochastic Monte-Carlo Tree_Search](https://mlsanity.com/paper/2406.02235/) (2024)
- [Planning in entropy-regularized Markov decision processes and games](https://mlsanity.com/paper/2604.19695/) (2026)
- [Online Robust Reinforcement Learning Through Monte-Carlo Planning](https://mlsanity.com/paper/2609.18599/) (2026)
- [Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing](https://mlsanity.com/paper/2609.06484/) (2026)
- [Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search](https://mlsanity.com/paper/2609.06489/) (2026)

## Abstract (arXiv)

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 Vstar(s0), the optimal infinite-horizon discounted value at the root state s0, when the remaining cross-depth gap vanishes. Experiments on stochastic planning benchmarks show improved sample efficiency over tree-based and graph-based baselines.