SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Sep 17, 2026 · UTC

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 wh

Read original source ↗ Open in workspace

recordType

paper

region

Global