Research map / Learning theory and algorithms / Combinatorial and search optimization
Epistemic Monte Carlo Tree Search
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 Epistemic MCTS (EMCTS), which propagates epistemic uncertainty from learned value/reward models through MCTS backups and uses an upper-confidence-bound search objective for deep exploration in AlphaZero/MuZero agents.
Problem
Learned models in AlphaZero/MuZero introduce epistemic uncertainty, but MCTS does not propagate it, so A/MZ cannot use search for deep exploration in sparse-reward tasks.
Approach
Treat the learned model as a random variable, derive a UCB on Q* from its variance, and propagate an upper bound on the epistemic variance of node values through backups so that search (EUCT/EPUCT) tracks an optimistic objective for deep exploration.
Key results
- On the SUBLEQ Identity Function task, E-AZ finds correct programs in far fewer samples than the AZ baseline.
- On Deep Sea 40x40, E-AZ with RND reaches the goal in about 10.5k steps on average (94% of seeds) versus 0% of seeds for AZ.
- E-AZ solves the stochastic-reward Deep Sea 50x50 variant, which baseline AZ cannot solve in the training budget.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use EMCTS search for uncertainty estimation rather than UBE exploration without uncertainty search | AZ with RND novelty estimation · Deep Sea 40x40 | average steps to goal transition: 22801 ± 7514 -> 10539 ± 9006 | Helped |
| use EMCTS search for uncertainty estimation rather than UBE exploration without uncertainty search | MZ with Counts novelty estimation · Deep Sea 40x40 | average steps to goal transition: 29945 ± 8113 -> 14339 ± 6845 | Helped |
| use EMCTS search for uncertainty estimation rather than UBE exploration without uncertainty search | MZ reconstruction model with RND novelty estimation · Deep Sea 40x40 | average steps to goal transition: 22497 ± 6645 -> 15241 ± 3236 | Helped |
| use EMCTS search for uncertainty estimation | AZ with RND novelty estimation · Deep Sea 40x40 | seeds that discovered goal: 91% of 35 seeds -> 94% of 35 seeds | Helped |
| use EMCTS search for uncertainty estimation | MZ with Counts novelty estimation · Deep Sea 40x40 | seeds that discovered goal: 57% of 21 seeds -> 100% of 23 seeds | Helped |
| use EMCTS search for uncertainty estimation | MZ reconstruction model with RND novelty estimation · Deep Sea 40x40 | seeds that discovered goal: 85% of 20 seeds -> 95% of 20 seeds | Helped |
| increase exploration parameter β (ablation) | E-A/MZ · Deep Sea 30x30 | evaluation regret | No clear effect |
Surprising findings
- Baseline AZ solved essentially none of the Deep Sea sizes within the training budget, with one exception that was due to an initial replay buffer containing a goal trajectory.
- A MuZero agent with a reconstruction-based model reached the goal much earlier than other baselines despite not searching the environment significantly faster.
Limitations
- Theoretical guarantees hold for reward-model uncertainty; extension to learned transition models is approximate and not analytically justified.
- Uncertainty estimators (counts, RND, hash-based) must be suited to the domain; an unsuited estimator on MinAtar was only comparable to baseline.
Experimental setup
Datasets: SUBLEQ programming tasks (Negate Positives, Identity Function) Deep Sea grid (40x40, 50x50 variants)
Benchmarks: SUBLEQ Negate Positives SUBLEQ Identity Function Deep Sea MinAtar
Metrics: sample efficiency interactions to 90% regret expected return steps to goal exploration rate
Baselines: AZ MZ AZ+UBE MZ+UBE Bootstrapped DQN
Builds on: AlphaZero MuZero PUCT Uncertainty Bellman Equation Reanalyze Gumbel MuZero
Closest papers by meaning
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.88)
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.84)
- Are Uncertainty Quantification Capabilities of Evidential Deep Learning a Mirage? (NeurIPS 2024 · similarity 0.84)
- Evaluating Epistemic Uncertainty: Beyond OOD Detection and Active Learning (NeurIPS 2026 · similarity 0.84)
- SeeA*: Efficient Exploration-Enhanced A* Search by Selective Sampling (NeurIPS 2024 · similarity 0.83)
- Epistemic Uncertainty Quantification For Pre-Trained Neural Networks (CVPR 2024 · similarity 0.83)
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.