Research map / Learning theory and algorithms / Combinatorial and search optimization
Monte Carlo tree search
Improves MCTS through state abstraction, speculation and best-arm identification.
55 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Combinatorial and search optimization, keyword cluster “planning · search algorithm · tree search”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
6 papers in 2023–24 and 23 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 1.7% to 6.3%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Nested Monte Carlo Search for Two-Player Games (AAAI 2016 · 24 citations)
- 2017 · Count-Based Exploration with Neural Density Models (ICML 2017 · 343 citations)
- 2018 · Learning to Branch (ICML 2018 · 68 citations)
- 2019 · Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning (NeurIPS 2019 · 28 citations)
- 2020 · Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds (AAAI 2020 · 30 citations)
- 2021 · Anytime Heuristic and Monte Carlo Methods for Large-Scale Simultaneous Coalition Structure Generation and Assignment (AAAI 2021 · 11 citations)
- 2022 · Efficient Active Search for Combinatorial Optimization Problems (ICLR 2022 · 27 citations)
- 2023 · Monte Carlo Tree Search with Boltzmann Exploration (NeurIPS 2023 · 2 citations)
- 2024 · Sample-and-Bound for Non-convex Optimization (AAAI 2024 · 2 citations)
- 2025 · Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · 3 citations)
- 2026 · Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers (ICLR 2026 · 0 citations)
Earliest papers here
- Nested Monte Carlo Search for Two-Player Games (AAAI 2016 · 24 citations)
- Learning Bayesian Networks with Bounded Tree-width via Guided Search (AAAI 2016 · 13 citations)
- Count-Based Exploration with Neural Density Models (ICML 2017 · 343 citations)
What has been tried
39 papers here report 354 measured changes (a component added, removed or swapped, compared with a baseline): helped 62%, no clear effect 9%, hurt 23%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Vary the number of child nodes created at expansion | Michalewicz-50d · best objective value | Mixed | Sample-and-Bound for Non-convex Optimization (AAAI 2024 · 2 citations) | |
| Add NN caching to speculative MCTS | 9x9 Go latency evaluation · speedup | 2.1 times improvement, on average | Helped | Speculative Monte-Carlo Tree Search (NeurIPS 2024 · 1 citation) |
| Vary the candidate-set size K; K=1 leaves selection to sampling, while K=∞ is equivalent to A* | USPTO · Solved rate | Mixed | SeeA*: Efficient Exploration-Enhanced A* Search by Selective Sampling (NeurIPS 2024 · 1 citation) | |
| Use SPLIT-THEN-MERGE rather than MERGE-THEN-SPLIT bridging paths | Uniform, A-b Normal, A-b Uniform, Beta, Exponential, Gamma, and Zipf · optimal-solution success rate | 1580 (79%) vs 1402 (70.1%); 582 (29.1%) vs 503 (25.2%); 551 (27.5%) vs 532 (26.6%); 1485 (74.3%) vs 1392 (69.6%); 1826 ( | Helped | A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation (AAAI 2025 · 0 citations) |
| Add the weakest-rank r∞ training examples | Go strength adjustment · strength adjustment | Helped | Strength Estimation and Human-Like Strength Adjustment in Games (ICLR 2025 · 0 citations) | |
| Replace the zero-input heatmap with SoftDist | TSP-500 · Score | 5.20% -> 5.32% | Helped | Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · 0 citations) |
| increase exploration parameter β | Deep Sea 30x30 · evaluation regret | No clear effect | Epistemic Monte Carlo Tree Search (ICLR 2025) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 29 papers; from OpenAlex and the papers' affiliations).
- Shanghai Jiao Tong University · 3 papers
- Pennsylvania State University · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Heuristic and local search algorithms (147 papers)
- Classical and HTN planning (145 papers)
- Search for program synthesis (38 papers)
Elsewhere in the topic
- Logic and answer set programming theory (150 papers)
- Unsupervised neural combinatorial optimization (113 papers)
- Constrained neural network optimization (111 papers)
- Decision-focused optimization (97 papers)
- Multi-objective optimization (93 papers)
- Structure and complexity of constraint reasoning (92 papers)
- Predict-then-optimize learning (89 papers)
- SAT and model counting solvers (89 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).