Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
A Bayesian Approach to Online Planning
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 a Bayesian online tree-search framework (Thompson sampling and Bayes-UCB variants with max-backup) with a finite-time Bayesian regret bound, evaluated on ProcGen Maze and Leaper using neural Q-networks with MLE or ensemble uncertainty.
Problem
Online planning with Monte Carlo tree search and neural value approximations is hurt by imperfect network outputs under limited search budgets; existing MCTS variants ignore epistemic uncertainty of those estimates.
Approach
Treat tree search as a Bayesian sequential discovery of the optimal branch, apply Thompson sampling over leaves with independent Q posteriors updated by max-backup and forward sampling, and propose a Bayes-UCB schedule for trees; learned uncertainty from MLE heads or ensembles feeds the posteriors.
Key results
- With ground-truth uncertainty on ProcGen Maze test domains, Bayesian tree search variants (TSTS, BTS) significantly outperform N-MCTS in success rate.
- BTS still significantly outperforms N-MCTS with up to 20% error added to ground-truth uncertainty.
- Learned uncertainty (MLE heads or ensembles) on Maze was not accurate enough to improve over N-MCTS; on Leaper, BTS with learned uncertainty significantly outperforms N-MCTS and with GT exceeds 85% success.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ground-truth uncertainty estimates during tree search | BTS on ProcGen Maze test domains · ProcGen Maze test domains | success rate | Helped |
| Use learned uncertainty estimates instead of ground-truth uncertainty (ablation) | BTS on ProcGen Maze test domains · ProcGen Maze test domains | success rate | No clear effect |
| Use the BTS quantile schedule instead of Bayes-UCT2 or Bayes-UCB action selection | Bayesian tree search on ProcGen Maze test domains · ProcGen Maze test domains | success rate | Helped |
| Use Bayes-UCT2 or Bayes-UCB action selection instead of Thompson sampling | Bayesian tree search on ProcGen Maze test domains · ProcGen Maze test domains | success rate | Helped |
| Use learned uncertainty estimates for BTS instead of no uncertainty estimates (ablation) | BTS on ProcGen Leaper test instances · ProcGen Leaper test instances | success rate | Helped |
| Use ground-truth uncertainty estimates instead of learned estimates (ablation) | BTS on ProcGen Leaper test instances · ProcGen Leaper test instances | success rate: >85% | Helped |
| Use risk-averse action commitment instead of the other tested commitment choices (ablation) | BTS with ground-truth uncertainty on ProcGen Maze · ProcGen Maze | success rate | Helped |
| Add up to 20% error to ground-truth uncertainty estimates (ablation) | BTS on ProcGen Maze · ProcGen Maze | success rate: 20% error | No clear effect |
| Use stochastic planning instead of deterministic planning (ablation) | Planners on ProcGen Maze · ProcGen Maze | success rate | Helped |
| Use sequential halving at the root instead of P-UCT (ablation) | SH-N-MCTS on ProcGen Maze · ProcGen Maze | success rate | Hurt |
| Average predictions from an ensemble of neural networks (ablation) | N-MCTS on ProcGen Maze test domains · ProcGen Maze test domains | success rate | Helped |
| Approximate posterior sampling and BTS quantiles with Gaussian distributions instead of exact calculations (ablation) | TSTS and BTS · ProcGen Maze | success rate | No clear effect |
Surprising findings
- Thompson sampling underperforms Bayesian exploration bonuses (B-UCB, B-UCT2) in tree search, contrary to the MAB setting.
- Committing to risk-averse actions at the root improves performance even though risk-seeking helps during tree exploration.
Limitations
- Independent leaf posteriors assumption is restrictive; efficient posterior updates for correlated case left open.
- Learned uncertainty estimates on Maze are too inaccurate to yield gains over N-MCTS.
- Ground-truth uncertainty used for main demonstrations is not available at test time.
Experimental setup
Datasets: ProcGen Maze ProcGen Leaper
Benchmarks: ProcGen Maze ProcGen Leaper
Metrics: success rate
Baselines: N-MCTS SH-N-MCTS B-UCT2 B-UCB DNG-MCTS W-MCTS
Builds on: AlphaZero Bayes-UCB Thompson sampling information-theoretic analysis UCT Expert Iteration
Closest papers by meaning
- Online Robust Reinforcement Learning Through Monte-Carlo Planning (ICML 2025 · similarity 0.86)
- Bayesian Exploration Networks (ICML 2024 · similarity 0.86)
- Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning (NeurIPS 2026 · similarity 0.86)
- Compositional Monte Carlo Tree Diffusion for Extendable Planning (NeurIPS 2025 · similarity 0.86)
- PlanU: Large Language Model Reasoning through Planning under Uncertainty (NeurIPS 2025 · similarity 0.86)
- Reflect-then-Plan: Offline Model-Based Planning through a Doubly Bayesian Lens (ICML 2025 · similarity 0.86)
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.