Research map / Learning theory and algorithms / Combinatorial and search optimization
Improving Monte Carlo Tree Search for Symbolic Regression
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 an improved MCTS for symbolic regression using an extreme-bandit (UCB-extreme) allocation rule with finite-time guarantees and evolution-inspired state-jumping actions (mutation/crossover) plus bidirectional propagation of top-N trajectories.
Problem
Symbolic regression is a combinatorial search over expressions; standard MCTS with average-reward UCB targets expected reward rather than the single best expression, and stepwise construction limits search efficiency.
Approach
Replaces the average-reward UCB with an extreme-bandit allocation that uses the highest observed reward per arm, analyzed under polynomial-like reward tail decay, and adds GP-style mutation and crossover as non-local state-jumping actions inside MCTS with bidirectional propagation of top-N trajectory queues.
Key results
- On the Basic Benchmarks, the method reaches 93.25% average recovery on Nguyen (vs NGGP 92.33%, DSR 83.58%, PySR 74.41%) and 71.41% on Livermore (vs NGGP 71.09%).
- On Nguyen-C and Jin, the method matches top baselines at 100% recovery; PySR is 65.40% on Nguyen-C.
- On SRBench black-box, the method ranks second in test accuracy behind Operon while producing substantially simpler models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ours instead of NGGP | Symbolic regression search · Nguyen | recovery rate (%): 92.33 -> 93.25 | Helped |
| Use Ours instead of NGGP | Symbolic regression search · Nguyen^C | recovery rate (%): 100.00 -> 100.00 | No clear effect |
| Use Ours instead of NGGP | Symbolic regression search · Jin | recovery rate (%): 100.00 -> 100.00 | No clear effect |
| Use Ours instead of NGGP | Symbolic regression search · Livermore | recovery rate (%): 71.09 -> 71.41 | Helped |
| Add evolution-inspired state-jumping actions | MCTS for symbolic regression · Nguyen-4 | reward tail decay parameter a: [4,6] -> below 2 | Helped |
| Add evolution-inspired state-jumping actions | MCTS for symbolic regression · Other Nguyen test cases | reward tail decay parameter a: original range -> [2,4] | Helped |
Surprising findings
- Without state-jumping, the UCB-extreme strategy alone is highly sensitive to c and struggles on complex targets such as Nguyen-4.
Limitations
- Theoretical guarantees rely on polynomial-like reward distribution assumptions that may not hold in practice.
- Some hard benchmarks such as Nguyen-12 remain unsolved.
- Hyperparameter c and gamma need to be matched to the unknown tail decay rate a_1.
Experimental setup
Datasets: Nguyen Nguyen-C Jin Livermore Nguyen-12* Feynman Strogatz SRBench Black-box
Benchmarks: Nguyen Nguyen-C Jin Livermore SRBench Black-box Feynman Strogatz
Metrics: recovery rate median test R^2 model size Pareto frontier
Baselines: DSR GEGL NGGP PySR Operon GP-COMEA
Builds on: UCB AlphaGo-style MCTS Deep symbolic regression PySR
Closest papers by meaning
- Deep Generative Symbolic Regression with Monte-Carlo-Tree-Search (ICML 2023 · similarity 0.91)
- Reinforcement Symbolic Regression Machine (ICLR 2024 · similarity 0.91)
- SMILE: Bridging Continuous Optimization and Discrete Symbolic Recovery (NeurIPS 2026 · similarity 0.88)
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.88)
- FunctionEvolve: Structure-Guided Symbolic Regression with LLMs (NeurIPS 2026 · similarity 0.87)
- Symbolic Regression with a Learned Concept Library (NeurIPS 2024 · 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.