Research map / Probabilistic and scientific modeling / Variational and generative sampling
Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport
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 Wasserstein MCTS, which models value and action-value nodes as Gaussians and backs up values as L1-Wasserstein barycenters under alpha-divergence (yielding a power-mean backup), with optimistic and Thompson-sampling selection, evaluated on stochastic MDPs and POMDPs.
Problem
Value estimation in MCTS is unreliable in highly stochastic and partially observable MDPs, where uncertainty propagates up the tree and causes suboptimal root action selection.
Approach
Treat value nodes as the L1-Wasserstein barycenter of Gaussian action-value children under an alpha-divergence cost, so both mean and standard deviation are backed up as power means; this recovers the generalized (power-mean) backup and propagates uncertainty to the root, paired with optimistic or Thompson-sampling selection.
Key results
- On PocMan with 65536 samples, W-MCTS-TS (p=100) reaches 77.70 ± 1.22 discounted reward versus 28.5 ± 3.8 for UCT, and is comparable to D2NG (72.2) in that setting.
- On Taxi, only W-MCTS with Thompson sampling picked up all three passengers among the compared methods.
- On RiverSwim, W-MCTS with optimistic selection converged fastest and obtained the best results.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Thompson sampling instead of optimistic selection (ablation) | W-MCTS · Pocman | discounted total reward: 50.9 ± 0.6 -> 67.38 ± 0.53; 51.0 ± 0.62 -> 75.64 ± 0.51; 52.2 ± 0.79 -> 77.68 ± 0.77; 54.6 ± 1.08 -> 77.70 ± 1.22 | Helped |
| Use Thompson sampling with p=100 instead of D2NG | W-MCTS · Pocman | discounted total reward: 67.38 ± 0.53 vs 71.55 ± 0.57; 75.64 ± 0.51 vs 75.39 ± 1.47; 77.68 ± 0.77 vs 76.90 ± 6.40; 77.70 ± 1.22 vs 72.2 ± 0.0 | Mixed |
| Use Thompson sampling with p=100 instead of UCT | W-MCTS · Pocman | discounted total reward: 67.38 ± 0.53 vs 23.4 ± 0.99; 75.64 ± 0.51 vs 23.6 ± 1.09; 77.68 ± 0.77 vs 24.90 ± 3.40; 77.70 ± 1.22 vs 28.5 ± 3.8 | Helped |
| Use W-MCTS with p=1 instead of W-MCTS-TS (ablation) | W-MCTS · FrozenLake | total discounted reward | No clear effect |
| Use Thompson sampling instead of optimistic selection (ablation) | W-MCTS · NChain | total discounted reward | Mixed |
| Use optimistic selection instead of Thompson sampling (ablation) | W-MCTS · RiverSwim | total discounted reward | Helped |
| Use Thompson sampling instead of optimistic selection (ablation) | W-MCTS · Taxi | total discounted reward | Helped |
| Use Thompson sampling instead of optimistic selection (ablation) | W-MCTS · Rocksample (11,11), (15,15), and (15,35) | total discounted reward | Helped |
| Use Thompson sampling instead of optimistic selection (ablation) | W-MCTS · Pocman | discounted total reward | Helped |
Surprising findings
- Power-UCT struggled on NChain despite using the same power-mean backup family.
Limitations
- Theoretical guarantees are for Thompson sampling at the root via a non-stationary bandit analysis, and the Gaussian assumption is needed for closed-form backups.
- Hyperparameters such as the power p are tuned by grid search per environment.
Experimental setup
Datasets: FrozenLake NChain RiverSwim SixArms Taxi RockSample PocMan
Benchmarks: FrozenLake NChain RiverSwim SixArms Taxi RockSample PocMan
Metrics: discounted total reward
Baselines: UCT Power-UCT DNG D2NG W-MCTS-OS
Builds on: Power-UCT UCT Wasserstein Q-learning D2NG
Closest papers by meaning
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.90)
- Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.89)
- Graph-Based Stochastic-Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation (NeurIPS 2026 · similarity 0.89)
- Online Robust Reinforcement Learning Through Monte-Carlo Planning (ICML 2025 · similarity 0.87)
- An Efficient Algorithm for Thresholding Monte Carlo Tree Search (NeurIPS 2026 · similarity 0.87)
- Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.