Research map / Probabilistic and scientific modeling / Molecules and proteins
Monte Carlo Tree Search in the Presence of Transition Uncertainty
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 UA-MCTS, which modifies all four MCTS phases using a learned transition-uncertainty estimate so search avoids uncertain transitions in an imperfect model, evaluated on corrupted MinAtar games and a toy GridWorld.
Problem
MCTS assumes a perfect simulation model; when the given model is imperfect, standard MCTS degrades significantly.
Approach
Estimate transition uncertainty as squared difference between imperfect model and real environment via a neural network, and adapt UCT selection, expansion, simulation, and backpropagation to be risk-averse toward high-uncertainty transitions; also gives a regret bound for an uncertainty-adapted UCB in corrupted bandits.
Key results
- On corrupted Space Invaders, combined UA-MCTS achieved an average reward of 23.8 offline, close to the perfect-play reward of 24, versus 16.3 for Corrupted Model MCTS and 18.4 for True Model MCTS.
- On Freeway, offline combined UA-MCTS reached an average reward of 0.9 and outperformed Corrupted Model MCTS; online it beat Corrupted Model MCTS but did not reach True Model MCTS.
- On the 2-Way GridWorld, learning transition uncertainty online with UA-MCTS converged much better than corrupted MCTS and near true-model MCTS, while learning the transition function with small networks failed to find the goal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an imperfect transition model instead of the true model | MCTS · Space Invaders, offline | average reward: 18.4 -> 16.3 | Hurt |
| Add uncertainty adaptations to all four MCTS components | MCTS with an imperfect model · Space Invaders, offline | average reward: 16.3 -> 23.8 | Helped |
| Add uncertainty adaptations to all four MCTS components | MCTS with an imperfect model · Freeway, offline | average reward | Helped |
| Add uncertainty adaptations to all four MCTS components | MCTS with an imperfect model · Breakout | average reward | Helped |
| Learn uncertainty online instead of using true uncertainty | Combined UA-MCTS · Space Invaders | average reward | Helped |
| Learn uncertainty online instead of using true uncertainty | Combined UA-MCTS · Freeway | average reward | Mixed |
| Learn uncertainty online instead of using true uncertainty | Combined UA-MCTS · Breakout | average reward | Hurt |
| Use selection-only uncertainty adaptation (ablation) | UA-MCTS · Space Invaders, offline | average reward | Helped |
| Use expansion-only uncertainty adaptation (ablation) | UA-MCTS · Space Invaders, offline | average reward | Helped |
| Use backpropagation-only uncertainty adaptation (ablation) | UA-MCTS · Space Invaders, offline | average reward | Hurt |
| Use each individual uncertainty-adapted component instead of unmodified MCTS (ablation) | UA-MCTS · Freeway, offline | average reward | Helped |
| Use selection-only or expansion-only uncertainty adaptation (ablation) | UA-MCTS · Breakout | average reward | Helped |
Surprising findings
- In Space Invaders, UA-MCTS offline exceeded the True Model MCTS baseline in most configurations, because discouraging uncertain (low-value) states made search more efficient despite the imperfect model.
- Learning the transition function with the same network capacity failed to find a path to the goal at all, while learning only the uncertainty worked.
Limitations
- Performance in the online setting is strongly limited by the accuracy of the learned uncertainty network, especially on Freeway and Breakout.
- Evaluated only on three modified deterministic MinAtar games and a toy gridworld, with uncertainty defined as the squared model discrepancy in a fixed setup.
- Hyperparameters such as the tau schedule and the 1/10 scaling constant were chosen empirically.
Experimental setup
Datasets: MinAtar Space Invaders MinAtar Freeway MinAtar Breakout 2-Way GridWorld (toy environment)
Benchmarks: MinAtar Space Invaders MinAtar Freeway MinAtar Breakout 2-Way GridWorld
Metrics: average episode reward average steps to goal
Baselines: Corrupted Model MCTS True Model MCTS Cmax
Builds on: UCT UCB Cmax
Closest papers by meaning
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.90)
- Online Robust Reinforcement Learning Through Monte-Carlo Planning (ICML 2025 · similarity 0.90)
- Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves (AAAI 2025 · similarity 0.89)
- 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.88)
- Improving Monte Carlo Tree Search for Symbolic Regression (NeurIPS 2025 · similarity 0.88)
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.