Research map / Learning theory and algorithms / Combinatorial and search optimization

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

NeurIPS 2026 · Learning theory and algorithms › Combinatorial and search optimization · approach: Monte Carlo tree search · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GS-Power-UCT, a graph-based MCTS for stochastic MDPs that merges states by (state, depth) keys with power-mean backups and polynomial bonuses, plus a full-state variant with adaptive horizon, and gives O(n^{-1/2}) root convergence theory and simulation-budget experiments.

Problem

Tree-based MCTS duplicates states reached via different trajectories, wasting simulations in stochastic MDPs; existing graph-based MCTS lacks convergence theory for stochastic MDPs.

Approach

Key search-graph nodes by (state, depth) so the graph is a DAG for any MDP and same-depth transpositions share statistics; combine with power-mean backup and polynomial exploration bonus, and offer a full-state variant with adaptive horizon H(n) whose cross-depth bias vanishes under a gap condition.

Key results

• Depth-augmented GS-Power-UCT is particularly effective at small and moderate simulation budgets in the stochastic domains tested.
• GS-Power-UCT-F+ is competitive in four of five domains but underperforms in Passenger Grid.
• Theory: root expected error O(n^{-1/2}) for fixed horizon, matching tree-based Stochastic-Power-UCT.

Surprising findings

• Full-state merging can introduce cross-depth bias and underperform in Passenger Grid.

Limitations

• Assumes non-negative rewards for the power-mean backup.
• Sharing helps only with same-depth transpositions; otherwise overhead without benefit.
• Memory and hash-table overhead can grow up to |S|*H nodes.

Experimental setup

Datasets: five stochastic MDP planning benchmarks (including Passenger Grid)

Benchmarks: five stochastic MDP environments including Passenger Grid

Metrics: planning performance vs simulation budget

Baselines: UCT MENTS Stochastic-Power-UCT GBOP

Builds on: Stochastic-Power-UCT UCT Monte-Carlo Graph Search MENTS Fixed-Depth-MCTS

Closest papers by meaning

• Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.93)
• Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.89)
• Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.88)
• Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning (NeurIPS 2026 · similarity 0.88)
• Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves (AAAI 2025 · similarity 0.88)
• Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization (ICML 2024 · similarity 0.87)