Improving Monte Carlo Tree Search for Symbolic Regression
Authors: Zhengyao Huang
Daniel Zhengyu Huang
Tiannan Xiao
Dina Ma
Zhenyu Ming
Hao Shi
Yuanhui Wen
Venue: NeurIPS 2025 poster ()
Keywords: Symbolic Regression
Monte Carlo Tree Search
Equation Discovery
Combinatorial Optimization
Primary area: reinforcement_learning
TL;DR: This work improves Monte Carlo Tree Search for symbolic regression through an extreme bandit strategy and evolution-inspired state-jumping actions.

Abstract: Symbolic regression aims to discover concise, interpretable mathematical expressions that satisfy desired objectives, such as fitting data, posing a highly combinatorial optimization problem. While genetic programming has been the dominant approach, recent efforts have explored reinforcement learning methods for improving search efficiency. Monte Carlo Tree Search (MCTS), with its ability to balance exploration and exploitation through guided search, has emerged as a promising technique for symbolic expression discovery. However, its traditional bandit strategies and sequential symbol construction often limit performance. In this work, we propose an improved MCTS framework for symbolic regression that addresses these limitations through two key innovations: (1) an extreme bandit allocation strategy tailored for identifying globally optimal expressions, with finite-time performance guarantees under polynomial reward decay assumptions; and (2) evolution-inspired state-jumping actions such as mutation and crossover, which enable non-local transitions to promising regions of the search space. These state-jumping actions also reshape the reward landscape during the search process, improving both robustness and efficiency. We conduct a thorough numerical study to the impact of these improvements and benchmark our approach against existing symbolic regression methods on a variety of datasets, including both ground-truth and black-box datasets. Our approach achieves competitive performance with state-of-the-art libraries in terms of recovery rate, attains favorable positions on the Pareto frontier of accuracy versus model complexity.

Improving Monte Carlo Tree Search for Symbolic Regression
Zhengyao Huang"
Daniel Zhengyu Huang
23012130830stu, pkus edu cn
huangdz@bicmm pku. .du. cn
Tiannan Xiao
Dina Ma
Zhenyu Ming'
alxeuxiao@pku. edu. en madina@huawei.com
mingzhenyul Chuawei. com Yuanhui Wen
Bangzhenyyl@uuawwi.ccomm
Hao Shi
shih22@mails tsinghua. edu.
benyuanhui@huaret
Abstract
Symbolic regression aims discover concise, interpretable mathematical expres- sions that satisfy desired objectives, such as fitting data, posing a highly combina- torial optimization problem. While genetic programming has been the dominant approach, recent efforts have explored reinforcement learning methods for im- proving search efficiency. Monte Carlo Tree Search (MCTS), with its ability balance exploration and exploitation through guided search, has emerged as a promising technique for symbolic expression discovery. However, its traditional bandit strategies and sequential symbol construction often limit performance. In this work, propose improved MCTS framework for symbolic regression that addresses these limitations through two key innovations: (1) an extreme ban- dit allocation strategy tailored for identifying globally optimal expressions, with finite-time performance guarantees under polynomial reward decay assumptions; and (2) evolution-inspiree state-jumping actions such as mutation and crossover, which enable non-loca transitions to promising regions of the search space. These state-jumping actions also reshape the reward landscape during the search process, improving both robustness and efficiency. We conduct thorough numerical study the impact of these improvements and benchmark our approach against existing symbolic regression methods on a variety of datasets, including both ground-truth and black-box datasets. Our approach achieves competitive performance with state-of-the libraries in terms of recovery rate, attains favorable positions on the Pareto frontier of accuracy versus model complexity. Code is available httpps///il htttps://githu..cooPPUU.. Ctt.aa.ccoo//U--UCCCCCC Mtt.aa/.....///..EEEE/oo////S/--
Introduction
Symbolic regression (SR) is machine learning methodology that aims to discover interpretable and concise analytical expressions to represent data-driven relationships or desired functional objectives, without assuming any predefined mathematical form. Unlike traditional regression tech- niques, which optimize parameters within fixed model structures, symbolic regression simultaneously searches for both the functional form and its parameters by exploring combinatorial space. The resulting expressions are often simple and human-readable, which has supported their utility in
"Center for Machine Learning Research, Peking University, Beijing, China.
'Corresponding author; Beijing International Center for Mathematical Research, Center for Machine Learning Research, Peking University, Beijing, China.
Huawei Technologies Ltd., Beijing, China.
Department of Mathematical Sciences, Tsinghua University, Beijing, China.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

scientific discovery [ 2 In many cases, SR-derived models align with cemain-speccfic laws, enabling their application across domains such as finance B3, materials science [4). climatology [5]. and healthcare [6]. Additionally, the combination of computational efficiency and model simplicity makes SR well-suited for time-sensitive scenarios like real-time control systems where rapid execution and operational transparency are essential.
Symbolic regression is combinatorial optimization problem, as expressions can be represented as binary trees or symbolic sequences (see Section 2.1 Finding an optimal expression entails searching both the tree structure and its parameters prov-n be an NP-hard task [8. To address this, numerous heuristic and approximate methods have been proposed and benchmarked [9] [0]. Among these, genetic programming (GP) remains the most widely adopted approach: GP evolves a population of candidate expressions via mutation, crossover, and selection to optimize data fit [TT] However, GP frequently produces overly complex formulas and exhibits high sensitivity to hyperparameter settings [16]. More recently, learning-hasee basng methods have been proposed to exploit structural regularities- such as symmetry, separability, and compositionality symbolic expressions [7]. Deep neural networks can be trained to generate candidate formulas directly [18-20), but they often excel only at data-fitting tasks and struggle to generalize beyond the training distribution. An alternative is to cast SR as sequential decision-making task and apply reinforcement learning (RL). Inspired by breakthroughs in games like Go [21 (2), RL-based SR leverages or recurrent-netwer
agents construct expressions token by token [16 23 24 Likewise, Monte
Carlo Tree Search (MCTS) has been adapted to navigate the space of symbolic programs more effectively (25
While symbolic regression can be reformulated as an RL problem involving the determination of an optimal sequence construction policy, it differs from conventional RI. in two critical ways: (1) the objective is to identify the globally optimal state (i.e., the highest reward) rather than to maximize the expected cumulative rewards, and (2) the action space is not fixed but can be designed to enable flexible state-jumping mechanisms, bypassing traditional stepwise transitions. The goal this work is to analyze and enhance the application of MCTS within the framework of symbolic regression. Our key contributions include:
Formulating an baremm--bandtt allocation strategy, analogous the Upper Confidence Bound (UCB) algorithm, and derive optimality guarantees under certain reward assumptions.
Introducing svolution-inspired state-jumping actions (e.g., mutation and crossover, as used in genetic programming) to shift the reward distribution MCTS towards higher values, improving both exploration and exploitation.
Developing refined MCTS framework for SR that (1) attains competitive performance against state-of-the-e libraries and (2) yields new insights into applying RL methods to combinatorial optimization.
1.1 Related Work
Monte Carlo Tree Search for Symbolic Regression. Inspired by the success of AlphaGo 21 22).
MCTS has been explored in symbolic regression. An early effort (26 employs a pretrained actor- critic model for the value function within the UCB scheme. Later, 27 improves MCTS with module transplantation, which manually adds symbolic sub-expressions (e.g.. x from high-reward states in the leaf action space. Another work (28) refines the UCB scheme by incorporating transformer- guided action probability assessment following AlphaGo-inspired UCB scheme (21 22 More recent work (29] introduces hybrid approach that alternates between genetic algorithms and MCTS, where MCTS results are used to initialize GP, and GP's results are leveraged to train a double Q-learning block within MCTS. A common trait across these methods [27229 is the emphasis
exploiting
high-reward actions: [27] and [29] adopt an e-greedy selection strategy, whereas ( modifies the
AlphaGo-inspired UCB formula by replacing the average with the maximum observed reward.
Bandit-Based Allocation Strategies. The Upper Confidence Bound (UCB), originally proposed for multi-armed bandits with uniform logarithmic regret [30], balances exploration and exploitation in MCTS (3I) Integrating UCB into MCTS improves planning performance [32]. However, whereas UCB minimizes average regret, tasks like symbolic regression seek the single best outcome. To ad- dress this, researchers have studied the extreme- setting (3 and applied it to combinatorial challenges such as Weighted Tardiness Scheduling. Here, propose an extreme- bandit allocation

---

rule with optimal guarantees under certain reward distribution assumptions, and embed it within MCTS for symbolic regression.
Hybrid Methods for Symbolic Regression. Symbolic regression is an NP-hard problem g often tackled using heuristic methods like GP and RL, which aim to efficiently explore the expression space under limited computational budgets. GP evolves population of candidate solutions through biologically inspired operations such mutation and crossover (II) This process can be modeled as a finite-state Markov process, where convergence relies on ergodicity [38] 39]. However, the effectiveness of GP depends on a careful balance between exploration and exploitation, which in turn is sensitive to hyperparameter tuning. RL-based approaches, such as MCTS and policy gradients [40], offer an alternative by learning policies to construct expressions symbol by symbol. policy gradient methods 42 43
to guide expression generation. These methods tend to strike a better using recurrent neural networks balance, though they may suffer from inefficiency due to their stepwise construction of expressions. To overcome these limitations, recent works [3 24 29 have proposed hybrid methods that combine RL and GP in modular fashion, alternating between them to enhance overall performance. Building on this idea, the present work incorporates biologically inspired state-jumping operations-namelee mutation and irossover-into MCTS. This hybrid strategy not only improves exploration efficiency but also aims to enhance the interpretability and effectiveness of the search process.
Notably, [16, 41 apply
Background
2.1 Symbolic Regression
Symbolic regression is a combinatorial optimization problem that aims find an expression minimizing a nonnegative objective functional:
min L(f)
(1)
In data-fitting scenarios, L(f) measures the discrepancy between predictions and observations. A common choice is the normalized root mean square error (NRMSE):
Σ (f(z,) - y.)²
NRMSE(J: (Z.,
- (yi 9)
where -= = Σ is the mean of the observed values. Beyond data fitting, symbolic regression can also generate expressions with desired analytical properties, such as control functions. The expression f is constructed from predefined symbol set, including arithmetic operators, elementary functions (e.g., sin, cos), constants, and variables warianges-making the search space inherently combinatorial.
Expressions are commonly represented as binary trees, with internal nodes as operators or functions and leaves as constants variables. These trees are often traversed in pre-order to yield sequential forms suitable for learning algorithms (see Figure Ih.
2.2 Markoy Decision Process
Due to the sequential nature of expression representation, the task of finding the optimal expression can be formulated as a Markov decision process (MDP). The state space S contains valid sequences of symbols, which may represent incomplete expressions. The action space A consists of set of predefined symbols. Taking an action a E A at a state E S deterministically transitions to a new state s' = {). where the action is appended to the sequence.
The reward function r(s, a, s') is defined as zero if the resulting state s' is still an incomplete expression. However, if s' forms a complete and valid expression, the reward is given by 1+2(7)* where L denotes the objective functional defined in I and ② This reward lies within the interval (0, 1]. Complete expressions are treated as terminal states in this process.
In practice, the length of the expression sequence or the maximum depth of the expression tree is typically bounded in order to limit the size of the state space. The goal is to find a sequence actions that, starting from the empty state 80 = Ø leads to complete expression that maximizes the reward. When interpreted as a pre-order traversal, this sequence yields the optimal expression. The detailed modeling procedure can be found in Appendix D
3

---

State-jumping
Selection
B Expression tree
MCTS tree
Cueue
0.96 th
0.99 log, dy
propagate
sin
UCB-extrame
0.02: 1.
Crossover
0.000
0.95 log.
New trajectory
Queue
or mutate
log
0.90
0.85 t. ty
0.88 :...
0.90 (y
3
Forward- propagate
0.9G
0.99:
Queue
0.81 .....
0.95
Pre-arder traversal: 8, th 2, B,ain,,
0.84
Figure I: A. Schematic of State-jumping Actions. Each MCTS node maintains queue of top-N trajectories passing through it. Before the standard selection step, probabilistic State-jumping operation may be applied: randomly mutating or crossing trajectories from the queue to generate new states at the same node. This bypasses conventional RI sampling by directly introducing promising candidates. In this example, the UCB-extreme criterion 77 selects a second-layer node (log). which then generates new child states (+, ....) with higher reward (0.99). Bidirectional propagation ensures that both parent and child queues are updated. B. Illustration of converting a binary expression tree into pre-order sequence. The example expression is (a y) sin(2).
2.3 Monte Carlo Tree Search
sample-based planning algorithm that incrementally builds asymmetric search tree, where each node represents a state (e.g.. a valid symbol sequence), and edges correspond to actions. Each node maintains visit counts and estimated action values to guide the search. MCTS proceeds through four phases:
MCTS
3
In the selection phase, the tree is traversed from the root using the UCB criterion until leaf with unvisited children is reached. At node v for state s, the selected action
In T, Q(ss,a) a) + t
a = argmax,
Tea
where Q(s, a) the estimated value of action a at s. T, is the visit count of s, T.,a is the visit count of (s, a), and controls exploration. Unvisited actions (Ts,a = 0) yield infinite scores, ensuring exploration.
In the expansion phase, child node is added for an unvisited action. The simulation phase then performs a rollout from this node to a terminal state. the backpropagation phase, the obtained reward is propagated along the visited path, updating statistics.
This process repeats until the computational budget exhausted, progressively improving the search estimates.
3 Methodology
In this section, we outline two improvements to the Monte Carlo Tree Search for symbolic regression: the allocation strategy based on the extreme bandit and the incorporation of the state-jumping actions.
3.1 Extreme Bandit Allocation Strategy
The objective of symbolic regression to identify the optimal expression, which corresponds the highest reward, rather than policy that maximizes the expected cumulative rewards. Consequently, the UCB allocation strategy (3). which optimal for maximizing the expected cumulative rewards, may not be well-suited for this task. This limitation has been empirically demonstrated in [16] 27-29)
In this subsection, we introduce an extreme bandit allocation strategy, similar to UCB, with optimal guarantees under certain reward distribution assumptions.

---

The selection step at state is modeled as K arm extreme bandit problem [33 351, where each action corresponds to an arm. We assume that choosing arm k time yields a reward Xg,t- determined through the subsequent selection until reaching leaf node, followed by the simulation step. We assume the reward is drawn from an unknown distribution P& over [0, 1] and Px is supported on [0, bu] with by I 1. Discovering the best expression is equivalent to discovering the maximum reward max {ba}- Given a designed allocation strategy, suppose arm 4e is selected at time The objective is to design an allocation strategy that minimizes
(TT) = max{bu [bx} EE max Xt,1 1ST
(4)
k=1
where the second term represents the expected highest reward achieved under our strategy. The objective function 4 can be decomposed into two components: The performance gap, which quantifies the difference between the maximum possible reward and the expected highest reward when the optimal action is known, accounting for the randomness of the reward:
(T)) = mb
K
max k=
K
E
max Xk.t EST
}.
(5)
A=
And the regret, as defined 35
R(T) max
E max Xx.1
E max X1.1
(6)
Therefore, determining the optimal allocation strategy is equivalent to minimizing the regret. The term G(T) is independent of our strategy and serves as a fundamental performance limit.
In this work, we consider the following allocation strategy for the T + 1-th round:
IT+1 == arg max; (Q.. + 20
IT TE.
with
max X #l,=k
where 7k,r denotes the number of times the k-th arm has been selected, and Qu.7, denotes the highest observed reward obtained from the k-th arm so far. The parameters c > and y > are two hyperparameters satisfying condition in (TO). We now establish upper bounds the performance gap and the regret, assuming that the reward distribution of each arm exhibits polynomial decay near its maximum:
Theorem (Polynomial-iie Arms Upper Bounds). Assume there are K arms, where the rewards for each arm follow special beta distribution Xx, ~ P(x; ax, by) supported on [0, by]:
a();a,b)=1 =1 -1- with 2 1 and b 1.
(8)
We further assume that the first arm is the optimal, meaning As = b1 - bb > 0, 2 Then the performance gap satisfies
b
G(T) S
(9)
T 1) 01
Furthermore, we consider the allocation strategy defined in with
and
2 c
2
2 +
(10)
Then for T 2 Cln + K with constan!
2c 1/7
C=
(11)
the regret bound is given by
201 c
C'InT' +2
R(T) < 12
(12)
201
2 2T -
- -
5

---

The proof of Theorem 1 is provided in Appendix A.1 In the reward density assumption (8) the parameter a controls the decay rate of the reward density near the maximum b. Larger values of indicate that fewer expressions can achieve high rewards. The theorem establishes that
In
G(T) = 0 TI/01 and R(T) = 0 T1+1/a1
which depends only on the tail decay rate aj of the optimal arm. When di is large, the performance gap increases; however, the regret remains at least (((4)) Together with the following theorem, this result demonstrates that the UCB-extreme allocation strategy 7 is also optimal for such extreme bandit problems. However, the required hyperparameters must satisfy (T)). A key condition that y must be greater than the polynomial decay rate, which is generally unknown and varies case by case. While choosing small 7 satisfies this condition, it also causes the constant C defined in (11) in the regret bound to grow exponentially with 4. In practice, 01 can be estimated, and one may,
for example, set 7 1 and c = + 1, which satisfy the condition (TO). The estimation of a1 41
for the symbolic regression task is discussed in Section f and Appendix [F] Meanwhile, have also conducted corresponding numerical experiments to verify this theorem and demonstrate the effectiveness of the UCB-extreme strategy, as detailed in Appendix
Theorem (Polynomial-lin like Arms Lower Bounds). Assume there are K arms, where the rewards for each arm follow a special beta distribution Xx,t ~ P(x; ax, by) supported on [0, by]:
P( b) -1
with a az1 2 and b < 1.
We further assume that the first arm is the optimal, meaning As = bi by > 0, 4k 2 2, and by < 1. Consider a stralegy that satisfies [[[T,T]] o(T5) T Do for any arm l with Dg 0, and any
8 > O. Then, the following holds
IT KL[P(r; bx)ll bx) (1,0; bi)]
lim inf E[T..
(13)
where KL denotes the Kullback- divergence (relative entropy) between the two distributions.
The proof of Theorem 2 follows from 46 and is presented in Appendix A.2 Finally, we point out that for more challenging reward distributions, which decay faster than polynomials, becomes difficult (or even impossible) to identify the best expressions. We focus on reward distributions that exhibit exponential decay near their maximum. The following negative result indicates that the performance gap is O lnT) meaning that an exponentially increasing number of samples is required to find max {by} to identify the best expression with high probability.
x=
Theorem 3 (Exponential-like Arms). Assume there are K arms, where the rewards for each arm follow a distribution Nx.t- P(x; aks by.) supported on [0, by]:
P(x;a,b) = - - with 0 and b S 1.
(14)
We further assume that the first arm is the optimal, meaning Ag bb by > 0. 2 Then the performance gap satisfies
aib min A k22
G(T) 2 min
(15)
(eln(T+))
The proof of Theorem is presented Appendix B
3.2 Evolution-inspired State-jumping Actions
To improve search efficiency. we integrate mutation and crossover from GP as state-jumping actions within MCTS. Unlike prior hybrid methods [3] 24 29] which alternate between GP and RL, our framework tightly embeds these actions into MCTS. As illustrated in Figure [ each MCTS node maintains priority queue of high-reward expressions. During selection, we probabilistically trigger state-jumping, applying mutation or crossover using expressions from this queue. These jumps guide the search toward high-reward regions by leveraging past successful expressions, effectively bypassing less promising paths. To ensure consistency and maximize the utility of information within

---

Algorithm 1: Improved MCTS
Input:
Initial state $0. Ps: state-jumping rate, Poz mutation rate, random explore rate Updated MCTS tree
Output:
Initialize < Vo. 8 < so. Tu t T. +1
Init
2 while NOTLEAF(Y) do Let Ç ~ UNIFORM(O, 1)
b Until reaching a leaf node
> Random variable
4
if & < Ps:
> Evolutionary state-jumping
5
if E2 Pm:
6
Tm + MUT(ss u), BACK/FORWARRDIOpyY, Tm)
> Mutation
7
else:
for in CRS(s.v): BACK/FORWARDDDOo(( Tr)
D Crossover
if Es <E <- U(((e))
>Randomly explore >- DUCCBextreme exploit
10
else: <- arg m ((0))
11 + aw), To + T, +1
State transition
end while
13 NONTERMINAL(S): v + EXPAND(U), update 8
BACKPROP(r, SIMULATE(S))
>Simulation and update ancestral nodes b PPropagate parent node's 's results to child nodes
15 for Tp E Qee: FORWARDPROP(D",
the MCTS tree, we introduce bidirectional propagation, which updates the priority queues both ancestors and descendants whenever a high-reward expression is found. This enables efficient sharing of valuable expressions across the tree and enhances overall search performance.
Priority Queue. For each MCTS node v, we maintain a priority queue ((v) that stores the Top-N (an, ap+1,-..)) along with their associated rewards r(r). Let denote the state at v, so that the sequence (s, (h, (M.))....) defines a complete symbolic expression, with the reward given by r(r). The queue is dynamically updated, recording the top-N highest reward trajectories from both standard MCTS iterations and state-jumping actions passing through the node, even before this MCTS node is expanded. This is achieved through the following bidirectional propagation mechanism.
reward-rrajectories, each denoted
Bidirectional Propagation. Conventional MCTS (Section 2.3 updates node information through backpropagation (upward propagation to the root), which includes the node visit count and the Q-value. However, backpropagation alone is insufficient for maintaining the priority queue and propagating information for state-jumping actions. For instance, if a node is visited during the simulation step but has not yet been expanded, the information for the top-N reward trajectories and their associated rewards is not recorded in that node. To address this, we perform downward propagation after MCTS node expansion. Specifically. when new MCTS node is expanded, its parent node downward propagates information, including the trajectories that bypass the newly expanded node and the associated rewards. Additionally, after a state-jumping action, information is propagated both upward and downward. With this bidirectional propagation, for any node v with state the highest reward stored in the priority queue Q(v), denoted as (uv) equals the maximum reward across all complete trajectories passing through Furthermore, this highest reward is also the maximum among its child nodes' highest rewards
(ss) max (V(v)= o' is child node of n).
More generally, the top-N N reward queue of the parent node Q(v) collects the top-N trajectories from the reward queues of its child nodes. Additionally, if the edge connecting v and its child v'
corresponds to action then the highest reward satisfies ((²) Q(s, a). Implementation details are provided in Appendix G
state- Mate-jumping actions, including crossover and various mutation types-followee following the implementations in 23 29 47), into the MCTS process. During each iteration, a state-jumping action is applied at a node with depth-deeendentt probability Ps: which decreases exponentially with depth. This design prioritizes high-reward nodes near the root, whose top-N queues typically contain better candidates. With probability e, node selection deviates from the extreme bandit allocation strategy 7 choosing nodes uniformly at random before applying state- jutting action. These actions exclusive to the MCTS phase and do not appear in rollouts.
State-jumping Actions.
We integrate
7

---

Simulation Rewards Distribution
State-jumping Rewards Distribution
Betal2.1)
Betai2.1) 1)
Beta(4,1) 1) Beta(6,1)
Beta(4, 11
Beta/6.1)
Simulation
State-jumple
Density
3
2
1
0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Reward
Figure 2: Empirical reward distribution for Nguyen-4 under in Algorithm 1 (fully random node selection), with a computational budget of 200,000 expression evaluations. All other settings follow Table Left: standard MCTS simulation. Right: state-jumping actions. A Gaussian kernel density estimate (bandwidth 0.25) is computed over 100 runs. Overlaid gray curves represent beta distributions on [0, with varying tail decay parameters 2, 6.
The newly generated states and their rewards are incorporated via the bidirectional propagation mechanism.
State-jumping actions extend the search beyond sequential symbol updates by enabling direct transi- tions to distant states, thus enhancing global exploration. Meanwhile, the bidirectional propagation mechanism retains and shares useful substructures across the tree. Combined with the extreme bandit allocation strategy, this hybrid approach improves the reward distribution MCTS, which improves robustness to hyperparameters and facilitates the generation of more complex expressions, as discussed in Section Detailed pseudocode of the algorithm provided in Algorithm
Experiment and Result
In this section, assess method on variety of benchmarks. The Basic Benchmarks include several ground-truth datasets where the true closed-form expressions are known: Nguyen [16), Nguyen [16, Jin [88, and Livermore 23 These datasets consist of data points sampled from equations with at most two variables over restricted intervals. Notably, here we replace Nguyen-12
with Nguyen- 12* 23). The SRBench Black-box Benchmarks (SRBench) [TO 49 feature more challenging datasets: Feynman [17). Strogatz [50]. and the Black-box collection. The Black-box subset contains 122 tasks with two more input variables: 46 are drawn from real-world observa- tional datasets, and 76 are synthetic problems derived from analytical functions or simulation models. Detailed experimental parameters and procedures are provided Appendix H For benchmarks involving constants, each evaluation of symbolic expression based on (2) requires optimizing the
constants within the expression using the BFGS algorithm [5]] as implemented in SciPy [52].
Algorithm Analysis. The effects of the extreme bandit allocation strategy and the state-jumping actions introduced in Section 3 are analyzed using the Nguyen benchmarks. We first visualize the reward distribution-aal important indicator of high-probability recovery, as discussed in Section 3.1 Most Nguyen test cases exhibit polynomial tail decay rates approximately in [4, 6). a representative example for Nguyen-4 is presented in Figure 2 Next, we test MCTS only equipped with the UCB- extreme strategy, under different parameter contigurations (T).. The results show that, for an estimated tail decay rate above a1 6, the algorithm can achieve optimal recovery performance; however, the algorithm is highly sensitive across tasks. Moreover, it often struggles on problems with more complex target expressions (e.g., Nguyen-4). Finally, we examine the effect of incorporating state-jumping actions, which dramatically reshape the reward landscape. Before adding state-jumps, the estimated reward tail decay-measure by the a (first) parameter of the Beta distribution- fell the interval [4, 6) for Nguyen-4 (see Figure 2 After introducing state-jumping, that same value drops below 2. Across all other Nguyen
and requires careful tuning to maintain robust performance

---

Table 1: Average recovery rate (%) of original expressions on five ground-truth benchmarks. The "Datasets" column indicates the number of individual datasets per benchmark. Results are averaged over 100 runs under a 2 mallion-evaluation budget.
Benchmark
Datasets
Ours
DSR
GEGL
NGGP
PySR
Nguyen
12
93.25
83.58
86.00
92.33
74.41
Nguyen
5
100.00
100.00
100.00
100.00
65.40
Jin Livermore
100.00
70.33
95.67
100.00
72.17
22
71.41
30.41
56.36
71.09
46.14
R Teat
Model Size
'Operon
'Oura
'FEAT
"EPLEX
LUWN
XG8
HLFI
LGBM
Model Size Rank
15
GG BOME
PAX
AdwBoool
SBP-GG
AlT
Fordom
FEAT
KomnsReee
TIEA
AAPP FE
Spanant
1DBR
APF PE"
'spream
GP-GOMER
MLP
Liner
185R
WFFeyman
0.0
0.5
10"
5
R² Test Rank
10
15
20
Figure 3: Comparison of our algorithm and SRBench baselines on the Black-box benchmark, showing median test Rº2 and model size across 122 problems (95% confidence intervals; asterisks denote symbolic regression methods); and the Pareto frontier of model size vs. median test R² (median rankings, 95% confidence intervals; lines/colors indicate Pareto dominance).
test cases, the fitted shifts from its original range into the interval [2, 4]. In practical terms, lowering a in this way leads to faster and more stable convergence. Additional decay rate estimates for the full Nguyen suite can be found in Appendix F Accordingly, in the subsequent comparative experiments we fix = 2, c = 1. Additionally, we also performed ablation experiments on Nguyen benchmark,
which can be found in Appendix E
Comparison Study. We benchmark our algorithm (Algorithm T against several representative baselines. Table reports the average recovery rate on the Basic Benchmarks over 1 100 independent runs, using budget of 2 million expression evaluations. The baselines include the RNN-based RL algorithm DSR [16), GEGL [53], NGGP [23], and the genetic programming library PySR [5]. GEGL combines genetic programming with imitation learning, while NGGP integrates it with reinforcement learning following DSR. These methods were selected as they are seneral-purpose algorithms suitable for combinatorial optimization, similar to ours. Our approach achieves comparable performance to these basclines.
We further evaluate algorithm SRBench, comparing it with 21 baseline methods reported in [0]. As shown in Figure our method strikes a favorable balance between accuracy and model complexity: it ranks second in test accuracy, just behind Operon [13], while producing substantially simpler models. On the Pareto frontier, our method stands among the top-performing approaches, alongside Operon [3) GP-COMEA [1), and DSR [16].
Discussion and Limitation
We propose an improved MCTS framework for symbolic regression with two key innovations: (1) an extreme bandit allocation strategy, and (2) evolution-inspired state-jumping actions. The extreme

---

bandit strategy is based on best-arm identification with polynomial-lik reward and offers theoretical guarantees for optimal finite-time regret. Meanwhile, the state-jumping actions reshape the reward landscape towards high-reward regions. The proposed method achieves competitive performance on various symbolic regression benchmarks, including ground-truth and complex SRBench black-box tasks. Despite these advances, some limitations remain. First, the bandit strategy's theoretical guarantees depend on reward distribution assumptions, which future work could explore relaxing. Second, certain challenging problems, such Nguyen-12, 12, remain unsolved. Finally, extending these innovations to broader reinforcement learning and combinatorial optimization domains a promising future direction.
Acknowledgement
The authors acknowledge the support of the National Natural Science Foundation of China through grant 12471403, the Fundamental Research Funds for the Central Universities, and the high- performance computing platform of Peking University.
References
[1] Schmelzer, M., R. Dwight, P. Cinnella. Discovery of algebraic reynolds-stress models using sparse symbolic regression. Flow, Turbulence and Combustion, 104:579-603, 2020.
[2] Lemos, P., N. Jeffrey, M. Cranmer, et al. Rediscovering orbital mechanics with machine learning. Machine Learning: Science and Technology, 4(4):045002, 2023.
[3] Chen, S.-H. Genetic algorithms and genetic programming in computational finance. Springer Science Business Media, 2012.
[4] Wang, Y., N. Wagner, M. Rondinelli. Symbolic regression in materials science. MRS communications, 9(3):793-805, 2019.
[5] Grundner, A., T. Beueler, P. Gentine, et al. Data-driven equation discovery of cloud cover parameterization. Journal of Advances in Modeling Earth Systems, 16(3):22023MS0007663 2024.
[6] Wilstrup. C., C. Cave. Combining symbolic regression with the cox proportional hazards model improves prediction of heart failure deaths. BMC Medical Informatics and Decision Making, 22(1):196, 2022.
[7] Kaiser, E., J. N. Kutz, S. Brunton. Sparse identification of nonlinear dynamics for model pre- dictive control in the low-data limit. Proceedings the Royal Society A, 474(2219):2018033) 2018.
[8] Virgolin, M., S. P. Pissis. Symbolic regression is np-hard. arXiv preprint arXiv:2207.0101 2022.
[9] White, D. J. McDermott, M. Castelli, et al. Better gp benchmarks: community survey results and proposals. Genetic progrumming and evolvable machines, 14:3-29, 2013.
[10] La Cava, W., P. Orzechowski, Burlacu, et al. Contemporary symbolic regression methods and their relative performance. arXiv preprint arXiv:2107.14351, 2021.
[11] Koza, J. R. Genetic programming as a means for programming computers by natural selection. Statistics and computing. 4:87-112, 1994.
[12] Schmidt, M., H. Lipson. Distilling free-form natural laws from experimental data. science, 324(5923):81 8-88 2009.
[13] Kommenda, M., B. Burlacu, G. Kronberger, et al. Parameter identification for symbolic regression using nonlinear least squares. Genetic Programming and Evolvable Machines, 21(3):471-501 2020.
[14] Virgolin, M., T. Alderliesten, C. Witteveen, et Improving model-based genetic programming for symbolic regression of small expressions. Evolutionary computation, 29(2):211-25 2021.
10

---

[15] Cranmer, M. Interpretable machine learning for science with pysr and symbolicregression, jl. arXiv preprint arXiv:2305.0/582, 2023.
[16] Petersen, B. K., M. Landajuela, T. N. Mundhenk, et al. Deep symbolic regression: Recov- ering mathematical expressions from data via risk-seeking policy gradients. arXiv preprint 1rX1v:191..04871, 2019.
[17] Udrescu, S.-M., M. Tegmark. Ai feynman: A physics-inspired method for symbolic regression. Science Advances, 6( 6(16))aayy263, 2020.
[18] Biggio, L., T. Bendinelli, A. Neitz, et al. Neural symbolic regression that scales. In International Conference on Machine Learning, pages 936-945. Pmir, 2021.
[19] Kamienny, P.-A., S. d' Ascoli, G. Lample, et al. End-to-end symbolic regression with transform- ers. Advances in Neural Information Processing Systems, 35: 35: 10269- 2022.
[20] Valipour, M., B. You, M. Panju, al. Symbolicgpt: A generative transformer model for symbolic regression. arXiv preprint arXiv:2106. 14131, 2021.
[21] Silver, D., A. Huang, C. Maddison, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-489, 2016.
[22] Silver, D., J. Schritwieser,, K. Simonyan, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
[23] Mundhenk, T. N., M. Landajuela, R. Glatt, et al. Symbolic regression via neural-guided genetic programming population seeding, arXiv preprint arXiv:2111.00053, 2021.
[24] Landajuela, M., C. S. Lee, J. Yang, et al. A unified framework for deep symbolic regression. Advances in Neural Information Processing Systems, 35:33985-33998, 2022.
[25] Kamienny, P.-.., G. Lample, S. Lamprier, et al. Deep generative symbolic regression with monte-carlo-tree-seacch In International Conference Machine Learning, pages 15655- 15668. PMLR, 2023.
[26] Lu, Q., F. Tao, S. Zhou, al. Incorporating actor-critic in monte carlo tree search for symbolic regression. Neural Computing and Applications, 33:8495-8511, 2021.
[27] Sun, F., Y. Liu, J.-X. Wang, et al. Symbolic physics learner: Discovering governing equations via monte carlo tree search. arXiv preprint arXiv:2205.13134 2022.
[28] Shojaee, P., K. Meidani, A. Barati Farimani, et al. Transformer- planning for symbolic regression. Advances in Neural Information Processing Systems, 36:45907-45919, 2023.
[29] Xu, Y., Liu, H. Sun. Reinforcement symbolic regression machine. In The Twelfth International Conference on Learning Representations. 2024.
[30] Auer, P., N. Cesa-Bianchi, P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[31] Coulom, R. Efficient selectivity and backup operators in monte-carlo tree search, In Interna- lional conference on computers and games, pages 72-83. Springer, 2006.
[32] Kocsis, L., C. Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282-293. Springer, 2006.
[33] Cicirello, V. A., F. Smith. The max k-armed bandit: A new model of exploration applied to search heuristic selection. In The Proceedings of the Twentieth National Conference Artificial Intelligence, vol. 3, pages 1355-1361. 2005.
[34] Streeter, M. J., S. F. Smith. A simple distribution-fres approach to the max k-armed bandit problem. International Conference on Principles and Practice of Constraint Programming, pages 560-574, Springer, 2006.

---

[35] Carpentier, A., M. Valko. Extreme bandits. Advances in Neural Information Processing Systems, 27, 2014.
[36] Kaufmann, E., W. M. Koolen. Monte-carlo tree search by best arm identification. Advances in Neural Information Processing Systems, 30, 2017.
[37] Hu, Y.-Q., X.-H. Liu, S, S.-Q. Li, et al. Cascaded algorithm selection with extreme-region ucb bandit. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10))6782-6774, 2021.
[38] Rudolph, G. Convergence analysis of canonical genetic algorithms. IEEE transactions on neural networks, 101, 1994.
[39] Langdon, W. B., R. Poli. Foundations of genetic programming. Springer Science & Business Media, 2013.
[40] Williams, R. J. Simple statistical sruddeet-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
[41] Li, W., W. Li. L. Yu, al. A neural- gourdl-guided dynamic symbolic network for exploring mathemat- ical expressions from data. In Proceedings of the 41st International Conference on Machine Learning, pages 19222-28242. 2024.
[42] Tamar, A., Y. Glassner, S. Mannor. Policy gradients beyond expectations: Conditional value-at- risk. Citeseer, 2015.
[43] Rajeswaran, A., S. Ghotra, B. Ravindran, et al. Epopt: Learning robust neural network policies using model ensembles. arXiv preprint arXiv: 01283, 2016.
[44] Lai, T. H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[45] Kaufmann, E., O. Cappé, A. Garivier. On the complexity of best-arm identification in multi- armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[46] Bubeck, S., N. Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[47] Fortin, F-A., F-M. De Rainville, M.-A. G. Gardner, et al. Deap: Evolutionary algorithms made easy. The Journal of Machine Learning Research, 13(1):2111-2175, 2012.
[48] Jin, Y., W. Fu, J. Kang, et al. Bayesian symbolic regression. arXiv preprint arXiv:1910.08892. 2019.
[49] Olson, R. S., W. La Cava, P. Orzechowski, et al. Pmlb: a large benchmark suite for machine learning evaluation and comparison. BioData mining, 10:1-13, 2017.
[50] La Cava, W., K. Danai. L. Spector. Inference of compact nonlinear dynamic models by epigenetic local search. Engineering Applications of Artificial Intelligence, 55:292-306, 2016.
[51] Fletcher, R. Practical methods of optimization, 1987.
[52] Virtanen, P., R. Gommers, T. E. Oliphant, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):611277,, 2020.
[53] Ahn, S., J. Kim, H. Lee, et al. Guiding deep molecular optimization with genetic exploration. Advances neural information processing systems, 33:12008- 12021, 2020.
[54] Gautschi, W. Some elementary inequalities relating to the gamma and incomplete gamma function. J. Math. Phys, 38(1):77-81, 1959.
[55] Bubeck, S. Bandits games and clustering foundations. Ph.D. thesis, Université des Sciences et Technologie de Lille-Lille I, 2010.
[56] Meurer, A., C. P. Smith, M. Paprocki, et Sympy: symbolic computing in python. Peerl Computer Science, 3:e103, 2017.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Refer to Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Refer to Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Refer to Appendices A and B for detailed proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Refer Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: We have provided the code at httpp:://ittuu..coomm OMEGroup
MCTS- 20rTS-4-RR, S-SR, which includes complete experimental scripts and detailed instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips. //nips.cc/ppl cccppblic/guu httgg//ddde//oeeubnnnnn
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Refer to Section and appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We show error bars in experiments where they are essential. Refer to Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Refer to Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research adheres to all guidelines outlined in the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This study has societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This study has no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: This study complies with the licenses of all existing assets used in the paper and provides necessary references.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes)
Justification: Our code at htttts://github.... com httpp//.....//PUCMMCCooo////CCT 4- includes a README with setup steps, commands, dependencies, and license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This study does not involve crowdsoureing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This study does not involve crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
18

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This study does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non sta-standard components.
Please refer to LLM policy for what should or should not be described.
19

---

A Polynomial-like Arms
In this section, we study the extreme bandit problem with Polynomial-iie arms, assuming that the reward distribution of each arm exhibits polynomial decay near its maximum b:
(1-5) I ) with 2 1 and b s 1.
P(X+ x; 6)
Specifically, we consider beta distribution. We have the following preliminary about beta distribution Lemma 1. For beta distribution with cumulative density function
P(z; a, b) 1- (1 The probability density function (PDF) of its maximum over n. samples is Pas its expectation satisfies
with 2 and b 1.
E [xc] = 6(1 F(a, where F(a,n) -r-= +++11 +1) r +
[(n 1)
And F(a, n. satisfies
1 + 1)(n +
1 + +1) - F(a,n) S sT(= 1) + -
(16)
1 + -
n n-
F(a,m)) - F(a,n) s
(m1 S s))
(17)
(n1 + (n 2
The density is highly concentrated near its maximum, b, with
Pa Pa( (1 (1))))))* - Se
(18)
Proof. For the beta distribution P(x; a, b), the probability density function (PDF) is given by:
p(2; a, b) = 5 (1 - (0 bb.
a
The PDF of its maximum over samples is
p(x) na 6
(1 - (1 -1)))) (5<z5
with expectation
b a (1
) j--1 1 (1 b. 3000 n-1
Epm [x] n Jo b
dr
= nb f-- (1 - (1 3) ") 1
(y= 1- (1- ()
(19)
b(1 n 1 + 1)I(n)
r( + +
Let denote
F(a,n) = r 1 + 1)
r(n + 1)
a r + +n - 1)'
we have
Ep [x] 6( - n).
By using the following inequality [54 about function
I'n + 1)
< (n 4
(n +
(20)
r 1)
We have (6). For n1 S n, we have
F(a,ni))P(ln n) s r - 1)
(1I+
( a
sT(=+1)
71 +
(21)
(ml + )n + 2
a
20

---

A.1 Upper Bounds
For the extreme bandit problem, we have the following theorem about the performance gap.
Theorem 4. Assume there are K arms, where the rewards for each arm follow a distribution Xx. P(x; ans by) supported on [0, bu]:
with a2 1 and b 1. We further assume that the first arm is the optimal, meaning Ds = b1 - bk > 0, 2 performance gap satisfies
P(æ; a, b) = - 1
Then the
bi
G(T) $
(T + 1
Proof. By using (16), have
1 +1)
G(T) bj max ppr (mras mn)lo) S b1
(pr( =1,
b,
(T + -
Using the fact that r - 1) <
leads to bound for the performance gap.
Finally, we will prove Theorem about the regret bound related to our allocation strategy 7 Theorem Assume there are K arms, where the rewards for each arm follow a distribution Xa. P(r; ax, bu) supported on [0, bu]:
P(x; a, b) = 1- (1
with a 2 1 and S 1.
We further assume that the first arm is the optimal, meaning A = by bk > 0, Ak 2 2, and denote
K
2c
1/7
C
(22)
We consider the allocation strategy
It+1 == arg max Qu.T2 + 2c
In T
2
with
Q..Te.
max X
(23)
Tk.
t:f,=k
1 with & 2 and 2 ct 2 2 + 1. Then for T 2 C'I + K, the regret bound is given by
R(T) < bbb 2 C 1
C' + 2K
(24)
c (T Chn K)1+0i
Proof.
We will first prove that under the conditions
E
max X1.0
max X 1ST
(25)
which is equivalent
F(a,, T) - bb + beF T) As - b
-T(TT+
[T+
-
using T6) and T(
1
1) S
an
01
2c A
using T Cln + K> 2c
1/7
Ax
741
A
701
An Anbl
(2c) 794
2 0
(26)
21

---

In the last inequality, we used 1 ai and 2c 2 which is derived from (2c) Then the regret for the first T round is upper bounded by
c
2
2
27
01
R(T)= S b1 ((((F(o,,T.r)
F(an,T)) T))
(27)
Here T denotes the number of rounds in which arm is chosen, and we used the fact that the extreme reward over all rounds is larger than the extreme reward within each individual arm:
E max Xt..t] 1ST
max IE
K
Xr..t
UST.E=
Our goal is to establish an upper bound on the regret in (27).
Assume that at the + 1-th round, when arm ls + 1 is pulled, the allocation strategy given by 7
implies the following inequality
Int 7
Int ?
Int
Int
1
20
QU.T.. 2c
2 QI.... 20
2c
(28)
TE,t
Tk,
T
We define the event Ar QI,TT.. + +20
+2,e
T2,e
Int
< bj. The probability of this event satisfies
P(A) = (1 (1-(2))
22c In bi
Se (In
(29)
Th.t
Here, we used the fact that Q1, is the extreme value, as described in 18). not occur, the allocation strategy implies
When the event A does
Int
Int
Int
Oy + 2c
2 QU.r.. + 20
2 QI... + 2c
2 b1.
Th,
Thet
The
which leads to
2c
1/7
TBe < b1 by
ln
(30)
When (30) violated, that indicates that A₁ occurs, and the probability at most as given which is
(29
P(T+1 = k) S ( (In 17,
(31)
Then, begin estimating the regret from 27 We denote the event By
2c
1/7
Br TE.T s C'n
with
(32)
b1 b/
k=
And we decompose its complement Bg- = k=
BR. where
Bg : {I= arg max k== o TT.rr (1, by
2c )
1/7
InT}
and
Σ
TK. CInT+K--K -1] (33)
k=2
Using the definition of C, under event BR, we have
2c
1/7
1 < TKT (6 bx
l
(34)
and for all j > 1:
(1,
2e
1/7
2c
1/7
Tyr -
In < STT, -
(b) - by
In < Tg.T - 1.
(35)
b1 1 bi/
1/7
Here we used 2c
IT (2c)2/7 In2 1. We can now estimate the regret in 27 using the
b
following decomposition:
F(ar, Ti.)) -
<
F(a Ti.)) F(a,,T)(Br
P P(Br)
(36)
K
+
E F(a,, Ti.) F Br P(Bx)
(37)
2
22

---

The intuition for the decomposition is as follows: in the first term. Σi.r is large enough, and hence F( Ti Ti,r)
F(a,, I can be bounded using (66). For the second term, P(Br) is small due (34)
violates 30 Next, we will estimate each term in the decomposition.
For the first term in 36.. under Br, we have Ti, = Σ Tk. T K B. using (7). the first term satisfies
ChnT+h K (.F(a),T,p)) ((o s <T( 1 +1) CT-ChT + +(++ x
(38)
For the second term in 36).. we further decompose each Bg (2 S k) based on the round number that arm & is chosen. Under event B2. let I. + denote the last round that arm & is chosen, we have
2c
1/7
2c
1/7
Th. = TA.T 1>
IT
In
(39)
bi
bj
bn
b3
here we used (34) and + 1 $ T, which violates
30
Hence
holds and the probability is at most
( (lut))011),7 7
P(Bx,) Se Se S
< t 69 (1-b, 62) S -2
(40)
Here the second inequality is derived from y I a:
1 and
2c
1/7
Ti. 2 1 + bi bj
lnt,
which is obtained by replacing Tr in (28) as its lower bound in (39) The third inequality uses the fact that bj < 1. Then each term in the second term in (36) can be decomposed
T-1
F(F( F(a,, TT = Σ B(F(a,,Ti,T) - (lP.B (41)
By combining Ti,; 0 from (39) with the condition 2 Tk, we start from 1.
Then divide the range of t in 41 into two parts. When t T-CImT
using 40) leads to
K
([F(aiTTig - F(ai, Tla,, <
2
CinT
(42)
2
K
2 -1
20.07
T
Cl
Here we used
10 +
Pdl
10
p+1
<p> 1.
(43)
tmnto
1=b
p-1
Combining the upper bound of T in
35 and t. > Tx, = TR. 1, we have
Tir= - Σ
Chm - (K -Chh
1)t
(44)
23

---

When t <
T-Chn K
using 17 and (40)
leads to
2 T-cla
[[ Tir)
In
C'I + (K - 1)t
<T(
+1)
22
a1
(T- TT-ChI1 - (K - 1)t )T + S7
(45)
T-C
ChT + (K 1)t
<I( 11)
22
a1
C-CIT (T
41
s <T( sT(+1)
+1 d1
KCh T + K
2 1
C'InT
K of
+T 1
2 -
Here in the second inequality, replaced in the denominator we used (43
T-C In T K
In the last inequality,
Combining
38
42
and 45
we have the regret bound
R(T) $ b
E
F(a1, Tı,r) - F(ai,T)))
Cln++h
< b
(T- Cln KInT-K) -K) 1t
+ bbi(K - ()( 20
2-16-
2 1
- KC'nT++ + K2
2010 -1 T -ChT
2 - (T' C'n' K) 1+ -K)
28: c -1 K2CInT- 2K3
bj
20: 20.07 2 (T ClnT - K) 1+
-K)+#
(46)
Here in the second inequality, we replaced the denominators with the lower bound (T C' In
K) + and used the fact that r a1 + 1) < for all a 1. In the third inequality, used
T CIn K, c 1 2 1 + ai
and the following inequality
K
21 -1
K
1+
CITT
T C'IC
A.2 Lower Bounds
In this section we will first prove the following theorem, and discuss the optimality of the regret bound.
Theorem (Polynomial-lice like Arms Lower Bounds). Assume there are K arms, where the rewards for each arm follow distribution Xt, P(z; ax, bk) supported on [0, by]:
P(x; 1 )a with a21 and b 1.
We further assume that the first arm the optimal, meaning A bj by 0, vk and by Consider strategy that satisfies B[Tx.r] o(T") as T + 3o for any arm l with A > 0, and any > Then, the following holds
In T lim inf E KL[P( a b() (1))1
(47)
where KL denotes the Kullback-Leite divergence (relative entropy) between the two distributions.
24

---

Proof. Without loss of generality, assume that arm is optimal, meaning by < < 1 for all t: 2 2.
Let denote the density function of the beta distribution
a
p(a; ax. bb)
Then the KL divergence between the two reward distributions is given by
[L[P(x; ag, (z): 01 b1)] - p(z; ak, bk) In p(a; uR, bk) dx
p(a; a1, 61.
This quantity is finite since by 0 and is continuous with respect b1 Now, given any e consider an alternative bandit model where by is replaced by big such that 8/ > b1 > by and
[2[P(x; ax P
= (1 + c))LL ax, by) P(:: 01, b1)]
(48)
Under this alternative model, arm & becomes the unique optimal arm. In the following, we show that with big enough probability, the allocation strategy cannot distinguish between the two models, leading to the desired lower bound.
We use the notation E', and p' to denote expectation and probability under the alternative model where the parameter of arm k is replaced by b/g For any event A involving the rewards XA,1, XR,,, ... 22T from arm k, the probability under the alternative model satisfies
In p Xi,ti 02 bz) ((Xi,ti 022 b/2)
P'(A) B[AAe xLn
KL,
(49)
Here, the expectation with respect the original model. Define Px(x) P(x; Plaaaa,b0 bk) and (x(x) P(r; Kj). Then, we have
KL. o.e.
KL[PA||PA| p(z; ax bx) In pla;
plzjan, ak bR) dx < oc p(z; a1, bl.)
lim 8-000
(50)
This follows from the fact that the random variables In (le.)) with Xx,t ~ Ps are i.i.d. and have bounded finite moments.
p ((X..1911))
In order to link the behavior of the allocation strategy on the original and the modified bandits we introduce the event
Ar [TuT <T and KLT,r s (1 -1- [nT]
with fr 1-c INT
(51)
KL(P2
We will first prove that P(AT) o(1). Using 44 leads to
P'(AT) = E[LA,e KTr..T (T-(-)))(AA))
(52)
Using Markov's inequality, the above implies
E' T TR. T fr
P(Ar) TT- S T2-ipp((Trr fT)
T
(53)
Now note that in the modified model, arm l is the unique optimal arm. By assumption, for any suboptimal arm j and any >> O, the strategy satisfies E'T,, = oiT # This implies that E'T Tk,1 = o(TT).. Choosing e/2 then leads to
P(Ar) < T 2/2 E Tk.1l
o(1)
(54)
T fr
Next we will prove P(TR, < ST) = =()). We have
P(Ar) 2 P (T < fr and
max KI, 5 In #S
2
(55)
= =P(Thr < fT and
max KL,
<
1 KL(Pa|IP()
JT S
25

---

Here in the first inequality, we introduce maximum operator to eliminate the dependence of KL on - 1 and KL[P > O, along with 50), the maximal version of
T. The Using the fact that T-e
the strong law of large numbers [55] Lemma 10.5] implies that
lim P max KL, S KL(PAIPPK) = fT SSf
(56)
T T-000
Combining (56) and (55) leads to that
P(TE. (T) o(1)
(57)
Finally, estimate the expectation of Tk,7 follows
B[Ta,T] ((TKTT/TTTT < [T)P(TT,TT < ST) BITTTTTT 2 [T)P(TT,T ST)
1-c
2 P2|
In P(TE.T 2 fr)
(58)
lN
(1 + o())
Using 48 and
++ ++ KL
Taking to 0 in
58
leads to the desired lower bound 47
U
B Exponential-like Arms
In this section, study extreme bandit problem with exponential-Hit like arms, assuming that the reward distribution each arm exhibits exponential decay near its maximum b:
P(X 2; u;
== with
and b S 1.
(59)
Specifically, we consider modified exponential distribution, We have the following preliminary Theorem 7. Assume the reward of the arm follow the distribution:
P(x; = - - with > 0 andddd b < 1.
(60)
For random variables X, P, we have
ab/e t=1
b - Elmax X.)
(61)
In(T + 1)
Proof. For the distribution P(x; a, b), the probability density function (PDF) is given by:
ab
pla; b) The PDF of its maximum over n samples is
(0 x S b).
x))²
a,( np(x:a,,)PP(;;..))))
(0<
with expectation
h I'
E
p.
[
a ());;, dr
Jo
mb 0
(1
1n n- dy
(y = P(
(62)
a 1n(1 y)
1
= 6 - nb
a
y dy
In(1 4)
26

---

By using the following inequality
1
a 1n(1 - 4)
a
1
dy
In(1 y)
y
dy
m+1
1
dy
replacing by 1
In
n
+
0 In
+ T2
a/e
1
1 e
using (1
)"
2
In(n + 1)
(63)
We have the following upper bound about the expectation
nb ! a In(1 y) 1¹ 1 dy S <6(1
a/c In(n+ +
(64)
By using Theorem 7 we have the performance gap satisfies
G(T)
2 b max E mmax XR.1] k=1
K
ST
arbs min D + eln(T +1)
(65)
a,b,
min
min A R22
en 1)
C Numerical Experiments with Beta Distributions
In this section, we construct simple simulated numerical environment to compare the performance of the UCB-extreme policy proposed in this paper (see 77) with classic e-greedy and UCB1 policies. Concurrently, we experimentally validate the theoretical upper bounds for the performance gap GTT) and regret R(T) derived Theorem (specifically, and (2
We consider a multi-armed bandits problem with a total of K arms. The reward for each arm
follows Beta distribution with parameters (aR, bk) (defined in The specifie parameter settings are as follows:
Arm 1: 01
3, bj
Arm 2: 02 4, b2 0.9
Arm 3: 2, by 0.85
Arm 4: 04 = 1, by = 0.9
We employ the three aforementioned policies conduct total of 50, 000 independent sampling rounds on these four arms. The entire experiment is repeated 400 times to obtain statistical averages, thereby mitigating the effects of randomness. It should be noted that since the constant C obtained from (1I is relatively large, the theorem imposes very high requirement on the number of steps in the numerical experiments. Here, we fix C' 10.
The parameter configurations for the policies are as follows:
For the e-greedy policy, set the exploration rate 0.25.
For the UCB-extreme policy, in accordance with the conditions in (10 we set the parameters
2c = and 3.
ensure a fair comparison, the exploration parameters for the UCBI policy are set to the same values those for UCB-extremes
27

---

Average performance over T
Average regret over T
0.10
0.10
g-eedd
c-greedy
UCB extreme
UCB extreme
0.08
UCB1
0.08
UCB1
Bound
Bound
Average G
0.06
Average R
0.06
0.04
0.02
10000 20000
30000
40000
50000
20000 30000
40000
50000
Figure 4: Numerical experimental results of three different strategies for G(T) and R(T), along with their corresponding upper bounds, are shown in the figures. The regret results on the right demonstrate that our UCB-extreme performs the best.
The experimental results are presented in Appendix C It is clearly observable from the figure that, in this specific environment, only the R(T") generated by our proposed UCB- (CB-extreme policy satisfies the upper bound (12). In contrast, the R(T') for both the e-greedy and UCBI policies exceeds this bound. Notably, the traditional UCBI policy, which uses the sample mean as its expectation estimate, performs the worst, remaining far from the upper bound. Meanwhile, the c-greedy policy gradually approaches this bound in the later stages of the algorithm's 's execution.
On the other hand, regarding the performance gap G(T), its definition is inherently independent of the specific policy employed. Consequently, the experimental results also confirm that G(T) under all three policies adheres the theoretical upper bound given by (9)
D Modeling Symbolic Regression as a Markov Decision Process
In this section we describe in detail how to cast the symbolic regression problem as Markov Decision Process (MDP). First, an expression can be represented by binary expression tree, and any such tree can be mapped to a symbol sequence via traversal order. Here we use preorder traversal, as illustrated in Figure Conversely, symbol sequence that obeys the preorder rules can be reconstructed into expression tree follows:
1. Locate the deepest non-full operator node in the current partial tree.
2. Expand that node by adding a child symbol, first to the left and then to the right.
3. Repeat until there
non-full operator nodes remaining.
This procedure yields complete binary tree, which corresponds uniquely to an expression. In code, this can be implemented very efficiently using stack. Note that, because we impose a depth limit on expressions, in some cases only terminal symbols (variables or constants) may be added.
So in practice, we can formulate the symbolic regression task as an MDP defined by the tuple
M (S, A, P, R, B),
where:
S the state space, consisting of all partial symbol sequences (or incomplete binary expression trees) whose depth does not exceed maximum H. Formally,
= { = (a), (ai...., ax) depth(E(s)) < H, obeys valid preorder structure),
where E(s) reconstructs the expression tree from and depth(-) measures tree depth.
28

---

A is the (state-dependent) action space. Let O be the set of operators, X' the set of variables, and C the set of constants. At state sy:
A(ss) SOUXUC, depth(E(ss)) < H, depth(E(ss)) H,
UUC,
i.e. when the partial tree is at maximum depth, actions are restricted to terminal symbols (variables constants) to ensure the depth constraint.
The transition function P : S x A(s) + S is deterministic: given = (a....., .,) and
action a+41 E A(t),,
8++1 Expand(${, a(+1),
where 'Eppand' locates the deepest non-full operator node the tree corresponding to 81 and attaches d+++1 as its next child (left first, then right).
The reward function R: A(s) + R is zero at all nonterminal steps and gives a terminal payoff upon completion (no non-full operators remain):
0,
is non-terminal,
R(Se, ac++)
St41 terminal,
++ NRMSE E($41))
where E(s) denotes the expression tree reconstructed from s and NRMSE its normalized етror on the training data.
The discount factor / E [0, 1] is set to 1, since all reward is issued at termination, yielding return
T-1
G
Σ R(s,, (8TT-1,0)).
An optimal policy x² maximizes the expected return
arg max [ m].
which corresponds to finding the expression with minimal NRMSE. In practice, we explore this MDP via MCTS rollouts and apply genetic operators the queue of promising sequences, detailed in Algorithm
T
E
Ablation Study
To isolate the contributions of two key modifications MCTS-the extreme-bandit node selection strategy and the evolution-inspired state-jumping actions-we perform an ablation study on the Nguyen benchmark. We evaluate these models:
1. Model A: Replaces the UCB-extreme selection rule with uniform random selection (i.c., set in T4)
2. Model B: Model B: Omits the evolution evolution-inspired inspired state-jumping actions and only depends on the standard MCTS rollout to generate expressions(i.e. set g. in Table
3. Model C: MCTS using the standard UCB1 formula. not employing any methods proposed in this paper.
The experimental results in Table 2 show that both Model A and Model B perform worse than the complete algorithm, with Model B suffering particularly large drop. This clearly highlights that the evolution-inspine state-jumping actions are the primary driver our performance gains. At the same time, the (CB-extremee strategy continues to contribute positively, as its absence in Model A also leads to noticeable degradation. In line with our previous analysis, the state-jumping moves dramatically reshape the reward landscape during the search process, allowing the algorithm explore more promising regions of the expression space and to generate more complex yet high-quality expressions.
Simultaneously, can also observe that Model C performs very poorly and shows significant gap compared Model B. This further demonstrates the effectiveness of UCB-extreme for symbolic regression problems.
29

---

Table 2: Recovery rate comparison (%) for ablations on Nguyen benchmark.
Ours
Model
Model B
Model C
Nguyen-1
100
100
100
4
Nguyen-2
100
100
38
0
3
100
98
0
Nguyen-4
97
90
0
0
5
100
89
41
0
Nguyen-6
100
100
100
3
Nguyen-7
100
53
0
Nguyen-8
100
100
98
47
9
100
100
100
1
Nguyen-10
100
100
100
0
Nguyen-11
100
100
71
Nguyen-12
22
14
0
0
Nguyen average
93.25
90.83
53.08
10.50
Finally, we also conducted further hyperparameter tuning experiments based on Model B. This serves both to validate the theoretical insights behind our design and to provide preliminary analysis of the characteristics of different symbolic regression problems. The details can be found in Appendix
Reward Tail Decay Rate Analysis on Nguyen benchmark
We performed empirical investigation of reward distributions across the Nguyen benchmark suite (see Figure (5). The majority of expressions demonstrate tail decay rates ranging approximately between 4 and 6, with notable exceptions observed in expressions 5 and 12. Special attention required regarding our use of Nguyen-12 rather than (tu latter was specifically employed for recovery-rate testing). Furthermore, the integration of state-jumping operations, drawing inspiration from genetic programming methodologies, yields significant enhancements to the global reward profile: expressions 5, 8, 11, and 12 display tail decay rates approximately within [2, 4J, whereas the remaining expressions predominantly exhibit values below 2.
Based these observations, we carried out recovery experiments under six distinct UCB-extreme parameter settings. All evaluations were conducted using the MCTS algorithm that adopts only the UCB-extreme strategy without the evolution wrosutioninnspired state-jumping actions (i.c., with pa 0 and e = 0, as defined Algorithm [T]. This was done to better understand the difficulty of symbolic regression tasks and validate our theoretical analysis. All experiments followed the evaluation protocol outlined Appendix[B
Within our framework, decreasing the discount factor y or increasing the exploration constant both promote exploration. The six tested configurations, denoted as Models A-F, are defined as follows:
1. Model A: y = 3 2c V2. Standard UCBI parameters, used baseline.
2. Model B: y 2: 2c V 2'
Same discount factor as Model A, with an increased e corresponding to a₁ = 2.
3. Model C: 7 - 2c - (2) 1/4
Parameters calibrated to d1 increasing exploration via reduced 7.
4. Model y 1 2c (13) 1/6
Configured for 01 = 6, with further reduction in y and an adjusted c.
5. Model E:
2c 3/5
The most exploratory setting among Models A-E, corresponding to o₁ 8.
30

---

Table 3: Recovery rate comparison (%) on the Nguyen benchmark of MCTS using only the UCB-extreme strategy under six different UCB-extrent parameter configurations.
Model
Model B
Model C
Model
Model E
Model F
Nguyen-1
90
93
100
100
100
100
Nguyen-2
29
77
96
100
92
N Nguyen-3
10
13
17
25
52
25
Nguyen-4
0
1
0
N Nguyen-5
1
22
18
41
Nguyen-6
49
73
100
100
99
100
Nguyen-7
27
30
89
98
72
98
Nguyen-8
16
69
96
95
100
Nguyen-9
56
66
100
100
100
100
Nguyen-10
35
39
100
100
100
100
Nguyen-11
57
59
99
100
100
100
Nguyen-12*
0
0
0
1
Nguyen average
30.83
35.33
64.42
69.50
69.42
71.42
6. Model F: = y 2c = (25) 1/8
1/8
Constructed by fixing 01 = and 7 = g while enforcing equality only in the second inequality of (10).
Models B-E are constructed by fixing = 2, 4, 6, 8, respectively, and then selecting y and e such that both inequalities in (IO) are satisfied with equality. This calibration strategy ensures that each configuration corresponds to a specific theoretical tail decay rate. In contrast, Model F enforces equality only
second inequality of (TO), thereby relaxing the first constraint.
From a theoretical standpoint, any reward distribution conforming to the polynomial decay form discussed Appendix A with 6 < a1 should satisfy (10) under the parameterization Model Empirically. Model F yields the highest recovery rates, with detailed results reported in Table 3
These findings suggest improved performance when aj 6, as confirmed by the quantitative metries in the referenced table.
Moreover, Table 3 indicates that different equations benefit from different parameter configurations for optimal performance. We also explored alternative settings where y was held fixed while c was incrementally increased. However, these variants did not yield statistically significant improvements in performance. On the contrary, excessively large values of e were found to degrade solution quality, underscoring the importance of balanced parameter calibration.
G Algorithm Details
This section provides detailed account of the core algorithmic components. As previously discussed, each node in the Monte Carlo Tree Search (MCTS) framework maintains independent trajectory queue. This functionality is supported by two complementary mechanisms: Backward Propagation (Algorithm2), which propagates complete trajectories upward through ancestor nodes, and Forward Propagation (Algorithm which disseminates partial trajectories downward along promising branches.
is important to highlight that the selection strategy Algorithm is parametrically flexible- can be configured to reduce to either e-greedy policy pure #CB-extreme strategy (7), depending on the parameter settings. Our hybrid approach demonstrates superior performance in symbolic regression tasks, evidenced by the results in Section 4
In contrast to conventional genetic programming, which relies on dedicated selection mechanisms (c.g., tournament selection or roulette-wheel selection) maintain population diversity, frame-
31

---

Nguyen1
Nguyen2
Nguyyen3
Nguyenr
5422
0.0
2.0
Nigayenn
Nguyené
5.0
0.5
24
5.
32
Rahard
Rewadd
3.
04
14
3.8
Dawardd
Ngaayen
0.0
4.2
32
64
0.0
1.
Noward
Roward
Ngutyen-31
Nguyyen-12
24
3.5
07
Figure 5: Empirical reward distributions the Nguyen benchmarks with = in Algorithm 1 (fully random node selection) and budget of 200,000 expression evaluations. Other settings follow Table 4 Results from 100 runs are shown using Gaussian KDE (bandwidth 0.25). The blue and orange curves represent standard MCTS simulation and the state-jumping actions, respectively. Overlaid gray curves depict beta distributions defined the interval [0,1], parameterized by tail decay rates with a = 2, 8,8.
32

---

Algorithm 2: Backward Propagation
Input: Current node no, trajectory (a1,.... am)
Output: Updated trajectory queues (Ωr)
r COMPUTEREWARD(T)
Start from current node D Traverse ancestors Abort if enqueue fails Prepend action to trajectory > Move to parent node
3 while o null do
if ENQUEUE(Q,, T, r) = False: break
5 T + [ ||
v.parent
7 end while
Algorithm 3: Forward Propagation
Input: Current node to. trajectory (a1...., am)
Output: Updated trajectory queues {2.}
COMPUTEREWARD(1
2 V f- 0g
D Start from current node Follow trajectory
for i + to do
4 Unext f fu E C(v) | au = as}
b Find child with matching action Stop if path deviates t Move to next node Store remaining suffix
if Unext 0: break
6 f- Unext
ENQUEUE(Qe, Titlam: r)
8
end for
work adopts streamlined Top-N selection operator fulfill similar role with competitive effec- tiveness. Moreover, the integration of MCTS with bidirectional propagation enables the systematic retention of high-quality expressions across different exploration paths. This design not only pre- serves high-reward solutions but also enhances the ability to escape local optima through informed traversal of the state space.
H Experimental Details
All experiments were conducted on machines delivering 10.6 TFLOPS of FP32 compute performance and 256GB RAM.
H.1 Algorithm Parameters
The hyperparameter configurations used in the comparative study are summarized in Table Note that while the values of p.. e, and the maximum expression evaluation budget vary in Appendix FF all other settings and experimental conditions remain consistent.
Crossover is implemented using single-point crossover, where two expression trees exchange subtrees at randomly selected nodes, with each node chosen with equal probability. Mutation operations include uniform mutation, node replacement, subtree insertion, and subtree shrinkage, each applied with equal probability.
H.2 Metrics and Procedures
Basic Benchmarks. For the ground-trui truth benchmarks, we adopt the recovery rate metric as defined in [16]. The recovery rate the proportion of trials which the original expression is successfully rediscovered, evaluated over 100 trials with fixed random seeds. Each trial is subject to maximum of million expression evaluations.
To ensure fair comparison, we adopt the same action space constraints as in 16
23 and 27
A trigonometric function may not have another trigonometric function descendant.
An exp node must not be followed by log node, and vice versa.
33

---

Table 4: Hyperparameters of Algorithm used in the comparative study. Unless otherwise specified, all experimental settings follow the confguration listed in this table.
Hyperparameter Name
Symbol
Value
Comment
Expression Parameters
Maximum expression depth Maximum expression constants
10
No limit for SRBench
{+, * / sin, co8,
Omit constant for Nguyen Livermore
Available Symbol Set
exp, log, constant, variable}
Algorithm Parameters
UCB-extreme parameter
1
UCB-extreme parameter
Y
0.5
Size of queue
N
500
State-jumping rate
9s
0.2
Mutation rate
Jmn
0.1
Random explore rate
6
0.2
Additional structural constraints are listed in Table Any expression generated through crossover or mutation that violates these constraints is discarded and does not contribute to the evaluation budget.
SRBench Black-box Benchmarks. For black-box benchmarks, we follow the evaluation protocol of 10]. Each dataset is split into training and testing subsets (75% using fixed random seed. We perform 10 independent runs per dataset, each constrained to a maximum of 500,000 evaluations or 48 hours, whichever occurs first. Performance is reported the median test R score across the 10 runs:
E (y: 0.)² E Ø)2
R = 1
Complexity = [f(O))
where ÿ denotes the mean of the true output values. The Complexity term represents the number of nodes in the simplified expression tree, computed using Sympy [56].
H.3
Short Descriptions of Baselines for Basic Benchmarks
Below concise overview of the baseline algorithms used in our Basic Benchmarks:
Deep Symbolic Regression (DSR) employs a recurrent neural network (RNN) to sample candidate expressions and risk-seeking policy gradient algorithm iteratively update network parameters, thereby steering the sampling distribution toward high-reward symbolic forms.
DSR 16:
Genetic Expert- Guieed Learning (GEGL) generates M candidate expressions via RNN, ranks them by reward, and selects the Top-N candidates. Genetic programming operators are applied to these elites to produce offspring, which are subsequently re-ranked to retain the Top-N evolved variants. The RNN is then updated through imitation learning on the combined set of original and evolved Top-N expressions.
GEGL [53]:
NGGP (23): Neural-Guided Genetic Programming (NGGP) enhances DSR by seeding the genetic programming population with RNN-sampled expressions. It subsequently fine-tunes the RNN via risk risk-secking policy gradient updates based on the best solutions discovered during the GP run, establishing bidirectional feedback loop between neural sampling and evolutionary optimization.
PySR [5]: PySR is an open-source nigh-performance genetic programming library featur- ing multi-popplation evolutionary strategies. Implemented in Python and Julia, it efficiently discovers compact symbolic models through parallelized evolutionary search.
In our experimental configuration, PySR's core parameters were set as follows: maxdepth = populations 20, niterations 100, and population_ size 1000. Notably, we deliber-
34

---

ately abstained from constraining PySR's action space, as []6] substantiates that such limitations adversely affect genetic programming efficacy. All other baseline algorithms strictly adhered to the parameterizations detailed in 23
The symbol set configuration matches the specifications
documented in Table 4
H.4 Detailed Experimental Results
T the recovery rates obtained on each equation of the Nguyen and Livermore benchmarks. Table presents comparison of single-core runtimes on the Nguyen benchmark between our algorithm and NGGP. The reported runtimes represent the average over 100 independent runs for each equation, ensuring statistical reliability. These results indicate that our algorithm achieves recovery rates comparable to those of NGGP while demonstrating substantially faster runtimes and requiring fewer equation evaluations to recover each target expression.
H.5 Specifications of Basic Benchmarks
All ground-truth benchmark configurations are listed in Table 7 The notation U(a, b, c) denotes drawing independent uniform samples from the interval (a, b] for each input variable.
35

---

Table 5: Recovery rate comparison (%) across Nguyen and Livermore benchmarks.
(a) Nguyen benchmark
Ours
DSR
GEGL
NGGP
PySR
N
100
100
100
100
100
Nguyen-2
100
100
100
100
98
Nguyen-3
100
100
100
100
70
Nguyen-4
97
100
100
100
2
Nguyen-5
100
72
92
100
89
Nguyen-6
100
100
100
100
100
Nguyen-7
100
35
48
96
35
Nguyen-8
100
96
100
100
99
Nguyen-9
100
100
100
100
100
Nguyen-10 10
100
100
100
100
Nguyen-11
100
100
100
100
100
Nguyen-12*
22
12
0
Average
93.25
83.58
86.00
92.33
74.41
(b) Livermore benchmark
Ours
DSR
GEGL
NGGP
PySR
Livermore-1
100
100
100
100
Livermore-2
95
87
44
100
32
Livermore-3
100
66
100
100
97
Livermore
100
76
100
100
90
Livermore-5
78
4
30
Livermore-6
19
97
64
88
0
Livermore-7
15
0
0
Livermore-8
22
0
0
0
Livermore-9
24
0
Livermore- 10
35
0
24
26
Livermore-11
100
17
92
100
92
Livermore-11 12
91
61
100
100
18
Livermore-13
100
100
100
Livermore-14 14
100
0
100
100
15
Livermore-15 100
100
74
Livermore-16
72
12
92
93
Livermore-17
68
72
Livermore-1e 18
29
0
56
3
Livermore- 19
100
100
100
100
88
Livermore-20
100
98
100
100
76
Livermore-21
41
24
Livermore-2 22
100
68
84
9
Average
71.41
30.41
56.36
71.09
46.14
36

---

Table 6: Comparison of average single-core runtimes (in seconds) over 100 independent runs between our algorithm and NGGP on the Nguyen benchmark.
Ours
NGGP
Nguyen-1 1
6.63
27.05
Nguyen-2
29.10
59.79
N
105.84
151.06
Nguyen-4
254.03
268.88
Nguyen-5
93.00
501.65
6
16.46
43.96
Nguyen-7
49.68
752.32
Nguyen-8
99.41
123.21
Nguyen-9
9.82
31.17
Nguyen-10
71.06
103.72
Nguyen-11
2.99
66.50
Nguyen-122
1156.70
1057.11
Average
157.90
265.54
37

---

Table Specifications of Basic Benchmarks. It should be noted that configurations marked with an asterisk (*) indicate the use of the input domain sampled from the interval [0, 10), consistent with the experimental framework in 23
Name
Expression
Dataset
N
x² + x² +
U(-1,1,20)
Nguyen-2
x² + + x² t
U(-1,1,20)
3
2d + x 1 x. + +
U(-1,1,20)
Nguyen-4
2 + 2 + +xx
+x
U(-1,1,20)
Nguyen-5
sin(x") cos(2)
U(-1,1,20)
6
sin(x) + sin(x x²))
U(-1,1,20)
Nguyen-7
log( + + log(x? +1
U(0,2,20)
Nguyen-8
V
U(0,4,20)
N
sin(x) + sin(y²2 2s)n(x) cos(y)
U(0,1,20)
Nguyen-10
U(0,1,20)
Nguyen-11
x²
U(0,1,20)
Nguyen-12
x4 -xxx x² + 11²²
U(0,1,20)
Nguyen-12
2 - x3 + v²²²²
10,
Livermore-1
1 + cin(2
U(-10, 10, 1000)
Livermore-2
sin(x²) cos(( xx) -
U(-1,1,20)
Livermore-3
sin(x*) cos( (x²) -
U(-1,1,20)
Livermore-4
log(s + 1) log(1"
1) log(z)
U(0,2,20)
Livermore-5
x4 x + x²
U(0,1,20)
Livermore-6
4x + 3x + 2x +
U(-1,1,20)
Livermore-7
sinh(x)
U(-1,1,20)
Livermore-8
cosh(rr
U(-1,1,20)
Livermore-9
x² + x + + x
1 4
U(-1,1,20)
Livermore-10
(sin(x) cos(y)
((0,1,20)
2²
Livermore-11
U(-1,1,20)
x+y
Livermore-12
U(-1,1,20)
Livermore-13
U(0,4,20)
Livermore-14
x + + sin(() + sin(2?)
U(-1,1,20)
1ivermore-15
U(0,4,20)
1ivermore-16
a:
U(0,4,20)
Livermore-17
sin( cos(y)
U(0,1,20)
Livermore-18
sin(x" cos(s) -
U(-1,1,20)
Livermore-19 19
x3 + + + 1² +
U(-1,1,20)
Livermore-20
exp( 22)
U(-1,1,20)
Livermore-21
2 + x7 + x +x5
x3 x² +
U(-1,1,20)
Livermore-22
exp( -05xz)
U(-1,1,20)
N
3. + 2.12r 1.78r
U(-1,1,20)
55
sin(x²) cos(x) - -0.75
U(-1,1,20)
Nguyen-7
log(x + 1.4) + log(2² + 1.3)
U(0,2,20)
Nguyen-8
V1.23r
U(0,4,20)
Nguyen-10
sin(1.5x cos(0.5))
1,0,1,20)
Jin-1
2.5x 3.32 0.5y² 1.7y
U(-3,3,100
Jin-2
8.0z. + 8.0y² 3 15.0
U(-3,3,
Jin-3
0.2, + 0.5y² 1.2g 0.5x
U(-3,3,100)
Jin-4
1.5 ex5())()) 5.0 c.0cos(y)
U U(-3,3,100)
Jin-5
(.0 cos(y)
U 31,3,3,100
Jin-6
1.35xy + 5.5 5.5
(x 1.0) 1.0))
3,
38


Reviews:
[{"review_id": "QgHaoHWp4l", "reviewer": "Reviewer_hpnf", "summary": "This paper introduces new variants of Monte Carlo Tree Search (MCTS) for the symbolic regression (SR) problem. Compared to the standard approach, the authors propose (1) an extreme-bandit allocation strategy and provide theoretical optimality guarantees under certain assumptions, and (2) evolution-inspired state-jumping actions. The proposed methods are evaluated against state-of-the-art baselines on common benchmarks.", "questions": "Please see the weaknesses section above.", "limitations": "Some core components of the proposed SR methods are not clearly explained. The paper is good, but the issues raised above need to be addressed for the paper to be acceptable.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n-----------\n* The proposed approaches are well-motivated and address relevant challenges in SR.\n* The experimental results are strong and demonstrate the effectiveness of the methods.\n* The heuristic designs for mutation and crossover operations appear reasonable and practically sound.\n\nWeaknesses\n----------------\nSome core components of the proposed SR methods are not clearly explained. In more detail,\n\n* For the extreme-bandit strategy, the authors state that the objective is to maximize J(T), as the gap between the maximum possible reward and the expected highest reward, and hence the regret. It is unclear why the goal is to maximize rather than minimize J(T), and the paper does not provide sufficient justification for this design choice.\n\n* There is little information about the exact actions (i.e., which symbols) used when modeling the MDP. How are numerical expressions in SR generated? Are they also produced via MCTS? The paper provides limited details about these aspects of the SR formulation, even in the appendix.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your careful review of our paper and your valuable feedback. We have read all of your comments carefully and respond to your concerns point by point below.\n\n---\n\n**Question 1** Clarification of the Optimization Objective (Minimizing $J(T)$)  \n\n**Response**: Thank you for pointing this out. We apologize for the confusion caused by a typographical error in the manuscript. The objective should indeed be to **minimize** $J(T)$, which measures the regret as the gap between the maximum possible reward and the expected highest reward obtained. As described in the paper, $J(T)$ can be decomposed into two parts: $G(T)$ and $R(T)$, and since $G(T)$ is independent of the policy, the optimization reduces to minimizing $R(T)$. Specifically, the word **\"maximizes\"** in line 159 should be corrected to **\"minimizes,\"** and **\"maximizing\"** in line 165 should be corrected to **\"minimizing.\"** We appreciate your careful attention to this detail.\n\n---\n\n**Question 2** Clarification of MDP Modeling and Action Space in Symbolic Regression\n\n**Response**: We acknowledge that the original version of the paper did not explain the MDP modeling details clearly enough. Here is a more comprehensive explanation, which we plan to add to the Appendix in the revised version.\n\nAn expression can be naturally represented as a binary tree (see Figure 1 in the paper). By conducting a preorder traversal of the binary tree, we obtain a symbol sequence. Conversely, a valid symbol sequence can be converted into a binary expression tree using the following rule:  \n   1. Locate the deepest operator node that does not yet have the required number of children.  \n   2. Expand this node by appending children in a left-then-right order.  \n   3. Continue until all nodes are complete and the full tree is constructed.  \n   \nThis procedure can be efficiently implemented using a stack.\n\nAccordingly, the symbolic regression task can be formulated as an MDP defined by the tuple $\\mathcal{M} = (\\mathcal{S}, \\mathcal{A}, P, R, \\beta)$, where:\n\n- **State** $\\mathcal{S}$: The state space consists of all partial symbol sequences that represent incomplete binary expression trees, constrained by a maximum depth $H$. Formally, a state is $s = (a_1, \\dots, a_k)$ such that the reconstructed tree $E(s)$ satisfies $\\mathrm{depth}(E(s)) \\le H$ and the sequence maintains a valid preorder structure.\n\n- **Action** $\\mathcal{A}$: The action space is state-dependent. Let $\\mathcal{O}$ be the set of operators, $\\mathcal{X}$ the set of variables, and $\\mathcal{C}$ the set of constants. At a given state $s_t$, the available actions are:\n  $$\n  \\mathcal{A}(s_t) = \\mathcal{O} \\cup \\mathcal{X} \\cup \\mathcal{C}, \\quad \\text{if } \\mathrm{depth}(E(s_t)) < H\n  $$\n  $$\n  \\mathcal{A}(s_t) = \\mathcal{X} \\cup \\mathcal{C}, \\quad \\text{if } \\mathrm{depth}(E(s_t)) = H\n  $$\n  This means that when the tree reaches its maximum depth, subsequent actions are restricted to terminal symbols (variables or constants) to ensure the depth constraint is not violated.\n\n- **Transition** $P$: The transition function $P(s_{t+1}|s_t, a_{t+1})$ is deterministic. Given a state $s_t$ and an action $a_{t+1}$, the next state is generated by appending the new symbol: $s_{t+1} = (s_t, a_{t+1})$. This corresponds to expanding the deepest, not-yet-full operator node in the expression tree $E(s_t)$ by adding $a_{t+1}$ as its next child (left-to-right), as mentioned above.\n\n- **Reward** $R$: The reward function provides a signal only upon the completion of a valid expression. For all intermediate steps, the reward is 0. A terminal reward is given when the sequence $s_{t+1}$ corresponds to a complete expression tree:\n  $$\n  R(s_t, a_{t+1}) = 0, \\quad \\text{if } s_{t+1} \\text{ is non-terminal}\n  $$\n  $$\n  R(s_t, a_{t+1}) = \\frac{1}{1 + \\mathrm{NRMSE}(E(s_{t+1}))}, \\quad \\text{if } s_{t+1} \\text{ is terminal}\n  $$\n  Here, NRMSE denotes the Normalized Root Mean Square Error of the final expression on the training data.\n\n- **Discount Factor** $\\beta$: We set $\\beta=1$ because rewards are only dispensed at the final step. The total return $G$ for an episode is simply the terminal reward.\n\nThe goal is to find an optimal policy $\\pi^* = \\arg\\max_{\\pi} \\mathbb{E}[G \\mid \\pi]$, which corresponds to discovering an expression with the minimum NRMSE.\n\nIn our algorithm, expressions can be generated via random rollouts in MCTS or through mutation and crossover operations applied to sequences stored in the population queue, as described in Algorithm 1.\n\n---\n\nOnce again, we sincerely appreciate your thoughtful and constructive comments. They have helped us significantly improve the clarity of our paper. We will revise the manuscript accordingly and respectfully ask for your continued consideration of our work.\n\nSincerely,  \nThe Authors"}, {"review_id": "xFvthlqCHF", "reviewer": "Reviewer_3PJv", "summary": "This study proposes a new Monte Carlo Tree Search (MCTS)-based method for symbolic regression.\nParticularly, two technical contributions are made: i) an extreme bandit allocation strategy for identifying globally optimal expressions with a theoretical guarantee, and ii) state-jumping actions embedded in MCTS. While standard MCTS pursues maximizing expected cumulative rewards, this work adapts MCTS to the case of highest reward maximization. Numerical experiments support the validity of the proposed approach and also demonstrate that the proposed method achieves competitive scores compared with state-of-the-art methods.", "questions": "The questions come from the weaknesses except for the last one.\n1. Is the polynomial-tail assumption intuitively reasonable or just made artificially?\n2. Is it possible to create an artificial dataset or task for which we have better control over reward distribution to further analyze the derived bounds?\n3. Does each of the new MCTS and mutation contribute sufficiently to the symbolic regression performance?\n4. In Theorem 1, it is assumed that the first arm is optimal. Can this assumption be made without loss of generality? If not, how does this assumption become reasonable?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- A new MCTS method that adapts to the extreme bandit case is proposed. The theoretical analysis provides an upper bound on the regret with an assumption on reward density.\n- Inspired by genetic programming, state-jumping actions are introduced to the MCTS framework. Unlike prior methods that, for example, alternate between genetic programming and reinforcement learning, the proposed method rigorously embeds mutations into MCTS.\n- The experiments analyze the validity of the assumption on reward density. The impact of hyperparameters is also extensively examined. Finally, in symbolic regression performance, the proposed method outperforms all baselines on Basic Benchmarks, while it also performs competitively with state-of-the-art methods on the SRBench benchmark.\n\n---\n\n**Weaknesses**\n\nI feel that this work makes solid contributions from both theoretical and practical points of view, although I'm not an expert in this field. I suggest the following points to improve this work further.\n\n**1. Discussion on the assumption.**\nTheorems 1/3 present upper/lower bounds on the regret assuming the distribution of rewards has polynomial/exponential tail. While I appreciate these positive and negative claims, it would be better if the authors could elaborate more on these assumptions. Is the polynomial-tail assumption intuitively reasonable or just made artificially? Figure 2 provides empirical justification, but further analysis may give insights. Is it possible to create an artificial dataset or task for which we have better control over reward distribution to further analyze the derived bounds?\n\n**2. Ablation.**\nThere are two proposed components, one about MCTS and another about mutations. However, it is unclear from the experiments how much performance gain was obtained from each in the final performance.\n\n**3. Minor comments**\n- [l.255] It was initially unclear what range [4, 6] refers to. It would be better to clarify that this is the range of the first argument of the Beta distribution.", "was_revised": true, "final_justification": "A new MCTS method that adapts to the extreme bandit case is proposed. The theoretical analysis provides an upper bound on the regret with an assumption on reward density. \n\nThrough the rebuttal and discussion, the polynomial tail assumption is more justified by the pointers to and clarification of experiments (both in the main text and the appendix). The ablation also demonstrates that each of the two proposed techniques makes a sufficient contribution.\n\nThe paper has solid theoretical analysis, which is also supported by experiments. Thus, I recommend this work for acceptance.", "rebuttal": "Dear Reviewer,\n\nThank you for your thorough review and valuable comments. We have provided a point-by-point response below, which we hope will address all of your concerns. The manuscript has been revised accordingly.\n\n---\n\n\n**Question 1** Is the polynomial-tail assumption intuitively reasonable or just made artificially?  \n\n**Response**: The polynomial-tail assumption is introduced to provide a theoretical foundation for our guarantees. We think this assumption is reasonable for the following reasons:\n\n- The tail parameter $a_1$ controls how rapidly the reward distribution decays near its maximum. A larger $a_1$ reflects greater sparsity of high-reward expressions, matching practical observations. This perfectly captures the \"rare optimal-solution\" phenomenon inherent in the symbolic regression problem.\n\n- Empirically, Figures 2 and 4 (blue curve on the right) provide strong support for this reward-distribution pattern. Furthermore, our state-jump actions (Figures 2 and 4) flatten the tail decay and significantly improve benchmark performance (orange curve on the right). Moreover, our assumptions are empirically verifiable. For the Nguyen dataset, the tail (with state-jump actions) is well-approximated by a polynomial decay with $a_1 = 2$. We use this empirical estimation to set $\\gamma = \\frac{1}{2}$ and $c = 1$, based on Equation (10) in our theory. This single set of parameters was used for all the over 100 tests in this work and yielded excellent results.\n\nWe also acknowledge that for certain cases, such as the Nguyen-12 expression $x^4 - x^3 + \\frac{1}{2}y^2 - y$, the reward distribution does not follow a polynomial decay tail but instead approximates an exponential decay tail. As a result, nearly all of our attempts for this case, as reported in Table 2, achieved a 0% recovery rate. This exception supports our theoretical finding that an exponential decay tail makes the problem nearly unsolvable with our current approach.\n\nWhile we believe this assumption is robust for many practical scenarios, we agree that future work should explore relaxing it to accommodate a broader class of distributions, and we have noted this in our manuscript.\n\n---\n\n**Question 2** Is it possible to create an artificial dataset or task for which we have better control over reward distribution to further analyze the derived bounds?\n\n**Response**: Thank you for this excellent and insightful suggestion. To further validate our theoretical bounds, we have conducted a series of experiments using multiple Beta distributions to simulate controlled reward environments. In these tests, we compared the performance of our UCB-extreme strategy against standard baselines, including UCB1 and epsilon-greedy, by analyzing their performance gap $G(T)$ and regret $R(T)$.\n\nThe performance gap, $G(T)$, is by definition independent of the allocation strategy. As expected, our experiments confirmed that $G(T)$ satisfies the bound in Equation (9) of Theorem 1. However, the regret, $R(T)$, is policy-dependent and serves as the key differentiator. The empirical results demonstrate that only the regret of UCB-extreme consistently satisfies the theoretical upper bound in Equation (12) of Theorem 1. In contrast, strategies like UCB1 and epsilon-greedy, which are not designed for extreme value optimization, failed to meet these guarantees. This outcome highlights the superiority of our allocation strategy in efficiently identifying the maximal reward.\n\nAs we cannot include images in this response, we will add the detailed results and visualizations for these experiments to the appendix.\n\nWe also agree that creating an artificial dataset with controllable reward distributions would be a significant contribution to the field of symbolic regression. Such a dataset would provide a controlled environment to systematically test theoretical bounds and analyze algorithm behavior under diverse conditions. It could also serve as a foundation for developing standardized metrics to quantify task difficulty—a much-needed tool for the community. We believe this is a promising direction for future research and will add this point to the future work section of our manuscript.\n\n---\n\n**Question 3** Does each of the new MCTS and mutation contribute sufficiently to the symbolic regression performance?  \n**Response**: We agree that a formal ablation study is essential. While our initial submission demonstrated strong performance, it did not formally quantify each component’s independent effect. To address this, we have now conducted an ablation study with three distinct models:\n\n- Model A: Replaces the UCB-extreme selection rule with uniform random selection.\n- Model B: Omits the evolution-inspired state-jumping actions and only relies on the standard MCTS rollout to generate expressions.\n- Model C: MCTS using the standard UCB1 formula, without any of the innovations proposed in this paper.\n\nThe results for these models are summarized below:\n\n**Recovery rate comparison (%) for 3 ablations on Nguyen benchmark.**\n| | **Ours** | **Model A** | **Model B** | **Model C** |\n| :--- | :---: | :---: | :---: | :---: |\n| Nguyen-1 | **100** | **100** | **100** | 4|\n| Nguyen-2 | **100** | **100** | 38 | 0|\n| Nguyen-3 | **100** | 98 | 7 | 0|\n| Nguyen-4 | **97** | 90 | 0 | 0|\n| Nguyen-5 | **100** | 89 | 41 | 0|\n| Nguyen-6 | **100** | **100** | **100** | 3|\n| Nguyen-7 | **100** | 99 | 53 | 0|\n| Nguyen-8 | **100** | **100** | 98 | 47|\n| Nguyen-9 | **100** | **100** | **100** | 1|\n| Nguyen-10 | **100** | **100** | **100** |0 |\n| Nguyen-11 | **100** | **100** | **100** | 71|\n| Nguyen-12* | **22** | 14 | 0 | 0|\n| **Nguyen average** | **93.25** | 90.83 | 53.08 | 10.50|\n\n\nThe results clearly demonstrate the contribution of each component. \n- **Model C**, which uses the standard UCB1, performs poorly, confirming that vanilla MCTS is insufficient for this complex search problem. \n- **Model B** shows a dramatic performance drop compared to our full model, highlighting that the **evolution-inspired state-jumping actions are the most critical innovation**. These actions enable the algorithm to effectively explore and escape local optima, and we attribute their effectiveness to a tree-like multi-queue design that provides strong selection pressure while preserving a large pool of high-quality expressions.\n- **Model A** performs better than Model B but is still outperformed by our full model, which indicates that the **UCB-extreme selection strategy provides a significant and complementary benefit** by focusing the search on high-reward regions.\n\nIn our revision, we will add the detailed results and experimental setup for this study to the appendix.\n\n---\n\n\n**Question 4** In Theorem 1, it is assumed that the first arm is optimal. Can this assumption be made without loss of generality? If not, how does this assumption become reasonable?  \n**Response**: In Theorem 1, we assume that a particular arm (e.g., the first arm) is optimal for notational simplicity; this does not restrict the generality of the result.  If multiple arms are optimal, or if the optimal arm is not indexed first, one can simply relabel or reindex the arms and apply the same analysis. Thus, the assumption is benign and does not limit the theorem’s applicability.\n\n---\n\n\n**Clarification of “Range [4, 6]”**  \n\n**Response**: Thank you for pointing this out. We will clarify the meaning of “range [4, 6]” in the revised manuscript and provide a more detailed explanation in the main text.\n\n---\n\nOnce again, thank you for your insightful feedback, which has not only helped us improve the manuscript but also inspired several promising directions for our future research. We believe our revisions have addressed your concerns and look forward to your evaluation.\n\nSincerely,  \nThe Authors"}, {"review_id": "8dujzBFarC", "reviewer": "Reviewer_SL53", "summary": "This paper proposes an improved Monte Carlo Tree Search (MCTS) framework for symbolic regression. To address the challenge of efficiently finding the global optimal symbolic expression, the framework introduces two key innovations: the first is the extreme bandit allocation strategy, which models the node selection process as a K-arm extreme bandit problem, uses a specific formula to balance exploration and exploitation, and theoretically guarantees convergence to the optimal solution in a finite time by analyzing the upper and lower bounds of the performance gap and regret value. The second is the state jump action inspired by evolution, which introduces genetic operations such as mutation and crossover, and combines bidirectional propagation to achieve non-local jumps in the search process, reshape the reward distribution, and improve the efficiency of exploring high-reward areas. The framework is based on Markov decision process (MDP) modeling and is verified by experiments on benchmark datasets such as Nguyen and Livermore.", "questions": "- Is the extreme bandit allocation strategy similar to the following paper? In this paper, the regret upper bounds under stationary distribution and non-stationary distribution are considered respectively. What is the difference between you two?\n\n    Such as, [1] Hu Y Q, Liu X H, Li S Q, et al. Cascaded algorithm selection with extreme-region UCB bandit[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 44(10): 6782-6794.\n\n- The derivation premise of the article requires that the reward distribution has a known polynomial tail decay characteristic. This assumption is very strong. Will it lead to situations where it is not applicable in some scenarios?\n\n- In Appendix Table 2, it can be seen that the experimental results are extremely sensitive to hyperparameters and have poor robustness. The performance is highly dependent on the choice of two parameters. The recovery rate under different combinations varies significantly, and some combinations are almost ineffective. This shows that vanilla MCTS lacks generalization ability. In practical applications, it is difficult to find a set of universal parameters that adapt to all tasks. So is the purpose of this experiment to find the best parameter experience? Or is there another purpose? Are the parameter settings in model F used in subsequent experiments?\n\n- The state jumping mechanism introduced by this method significantly changes the tail shape of the reward distribution, thereby improving the search efficiency. However, the change of the reward landscape is static during the execution of the algorithm. Is it possible to design a dynamic and adaptive state jumping strategy that automatically adjusts the jump probability or operation type according to the current search stage, thereby further improving the convergence and generalization ability of the search?", "limitations": "- The extreme bandit strategy relies on empirical parameters. Is it possible to introduce adaptive tuning or reward-tail-aware automatic calibration mechanism to reduce parameter dependence?\n\n- All performance bounds and regret derivations are based on the assumption that rewards follow a specific form of beta-like distribution with a polynomial decay in the tail. I would like to know if this makes sense and why.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- An extreme bandit allocation strategy suitable for extreme value optimization is proposed, and the state jump mechanism in the evolutionary algorithm is organically integrated into the MCTS framework, which significantly improves the search efficiency and the ability to jump out of the local optimum.\n\n- The upper and lower bounds of the performance of the strategy under the polynomial tail distribution are systematically derived, providing solid theoretical support for the method and filling the theoretical gap of the existing MCTS in symbolic regression.\n\n**Weaknesses:**\n\n- See Questions and Limitations.", "was_revised": true, "final_justification": "N/A", "rebuttal": "Dear Reviewer,\n\nThank you very much for your careful review of our paper and for your valuable comments. We have read all of your questions carefully and respond to each point below.\n\n---\n\n**Question 1** Relation to Hu et al. [1] “Extreme‑Region UCB Bandits”\n\n**Response**: We appreciate you highlighting Hu et al. (IEEE TPAMI 2021) and have added this reference to Section 1.1. While both works use bandits to find the highest-reward configuration (differing from traditional cumulative-reward bandits), key distinctions exist:\n\n1. **Theoretical Objective and Assumptions**\n\n   - **Objective**: The primary objective of Hu et al. is to maximize the extreme-region, with a regret based on the probability of that region. In contrast, our work seeks to maximize the maximum reward of the bandit directly, with regret defined by this maximum reward. We believe our objective is better suited for symbolic regression, as the goal of the task is to find the best possible expression (yielding the maximum reward).\n\n   - **Assumption**: Extreme multi-armed bandit systems often require strong assumptions about the reward distribution. For example, in a bandit with a small probability of a very large reward, the maximum reward can be difficult to find in a finite number of trials. Hu et al. assume the reward distribution satisfies a specific moment condition:\n\n     $$ \\ln \\mathbb{E}[e^{\\lambda|X - EX|}] \\geq \\psi(\\lambda) \\textrm{,where } \\psi \\textrm{ is convex}$$\n\n     Our work, however, studies reward distributions with polynomial or exponential-like tails. We found that for polynomial-like tails, our designed allocation strategy is effective, achieving an optimal regret of $\\mathcal{O}(\\frac{\\ln T}{T^{1+1/a_1}})$, where $a_1$ is the polynomial tail decay rate. Conversely, for exponential-like tails, the problem becomes unsolvable and requires an exponential number of trials. This is consistent with the fact that symbolic regression is an NP-hard problem.\n\n2. **Practical Usage**\n\n   - Both Hu et al's extreme-bandit and our approach have hyperparameters. In our method, one only needs to approximate the polynomial-tail decay rate, $a_1$. The hyperparameters can then be selected based on our theoretical result in Equation (10):\n\n     $$ \\frac{1}{\\gamma} \\geq a_1 \\qquad \\textrm{and} \\qquad 2^{a_1}\\cdot a_1^{\\frac{1}{\\gamma}} \\geq 2 + \\frac{1}{a_1}. $$\n\n   - A sensitivity study of these hyperparameters is presented in Appendix C Table 2, where symbolic regression problems with polynomial-tail reward distribution with $a_1 \\in (4,6)$. Table 2 shows any set of hyperparameters satisfying Equation (10), specifically $\\gamma \\leq \\frac{1}{4}$, yields similarly good results. However, as we mentioned, if the tail is not polynomial-like, the problem may not be solvable.\n\n   - We also conducted experiments comparing our approach with Hu et al's `ER-UCB-S` strategy for symbolic regression, with the results listed below:\n\n   **Recovery rate comparison (%) on Nguyen benchmark.**\n   | | **Ours** | **ER-UCB-S*** | **UCB-extreme*** |\n   | :--- | :---: | :---: | :---: |\n   | **Nguyen average** | **93.25** | 44.00 | 71.42 |\n\n   The other two methods in the table serve as baselines, generating expressions using only the MCTS rollout process without our evolutionary state-jumping actions. The `UCB-extreme` methods utilize the allocation strategy from our paper for direct comparison. The asterisk (*) indicates tuned parameters. Our method consistently performed better, likely due to the reward distributions' tails aligning with a polynomial-tail distribution ($a_1 = 2$), as shown in Figures 2 and 4. It is also possible that the parameters for `ER-UCB-S` were not optimally tuned. Symbolic regression algorithms typically use maximum reward in their allocation strategies [2].\n\n---\n\n**Question 2** The derivation premise of the article requires that the reward distribution has a known polynomial tail decay characteristic. This assumption is very strong. Will it lead to situations where it is not applicable in some scenarios?\n\n**Response**: We understand your concern about the strong assumption of a known polynomial-tail decay. Our algorithm uses this as a heuristic, fitting the decay rate $a_1$ and applying improved MCTS. This assumption is reasonable because:\n\n- A larger $a_1$ reflects greater sparsity of high-reward expressions, matching practical observations and capturing the \"rare optimal-solution\" phenomenon in symbolic regression.\n- Empirical evidence (Figures 2 and 4) supports this pattern, showing that state-jump actions flatten the tail decay and improve benchmark performance. For the Nguyen dataset, the tail is well-approximated by a polynomial decay ($a_1 = 2$), enabling effective parameter settings ($\\gamma = \\frac{1}{2}$, $c = 1$).\n\nHowever, exceptions exist, such as Nguyen-12, where the reward distribution approximates an exponential decay tail, making the problem nearly unsolvable, as shown by the 0% recovery rate in Table 2. This result aligns with our theoretical findings that exponential decay tails pose significant challenges for symbolic regression.\n\n---\n\n**Question 3** Appendix C Table 2, Sensitive to Hyperparameters and have poor robustness\n\n**Response**: Thank you for your careful review. We believe there may have been a misunderstanding regarding the parameter study in Appendix C, and we appreciate the opportunity to clarify our findings.\n\nAppendix C, Table 2, validates our theoretical results about the extreme-bandit allocation strategy rather than finding the \"best\" parameters. For optimal regret, hyperparameters must satisfy Equation (10), specifically $\n\\gamma \\leq \\frac{1}{a_1}$. Tests on the Nguyen benchmark show that Models A and B with $\n\\gamma = \\frac{1}{2}$ violate Equation (10), leading to poor performance. Models C, D, E, and F approximately satisfy Equation (10), demonstrating robustness and acceptable results.\n\nIt is important to note that Appendix C experiments do not incorporate state-jump actions, which significantly improve the reward distribution (shifting from blue to orange curves in Figure 4). This improvement typically brings the polynomial decay rate closer to $a_1 = 2$ for the Nguyen benchmark. Appendix C’s experiments were not meant to find the \"best\" parameters, and Model F’s parameters were **not** used for final comparisons. Instead, we used parameters corresponding to a reward distribution with $a_1 = 2$ for the main text comparisons.\n\nFinally, Appendix C, Table 2, uses MCTS only with our extreme-bandit allocation strategy. Our improved MCTS framework, described in the main paper, is significantly more robust as it combines this allocation strategy with state-jump actions and random exploration probability.\n\n---\n\n**Question 4** Dynamic, Adaptive State-Jumping Strategy\n\n**Response**: Thank you for this insightful suggestion! Designing a dynamic exploring procedure for MCTS is a promising future direction. While we did not adopt this approach in our current work, we conducted preliminary tests on two strategies: `linear-decrease` and `linear-increase`. The `linear-decrease` strategy reduces state-jumping probability over time, whereas the `linear-increase` strategy does the opposite. The results are listed below:\n\n   **Recovery rate comparison of dynamic strategies (%) on the Nguyen benchmark.**\n   | | **Ours(Static)** | **Linear-decrease** | **Linear-increase** |\n   | :--- | :---: | :---: | :---: |\n   | **Nguyen average** | 93.25 | 92.58 | **93.50** |\n\n\n---\n\n**Limitations 1** Adaptive tuning or reward-tail-aware automatic calibration mechanism\n\n**Response**: We thank the reviewer for the suggestion. Our extreme-bandit allocation strategy relies on a key parameter $a_1$, the polynomial-tail decay rate of the reward distribution. Then, we can compute the hyperparameters based on our theoretical results in Equation (10). We can set $\\gamma = \\frac{1}{a_1}$ and $c = \\frac{a_1}{2}$, and this is also how we determine these hyperparameters used in the present work.\n\nWe designed a simple adaptive strategy for the UCB-extreme parameters. During the search, we dynamically adjusted the estimation of $a_1$ based on the gap between the maximum sampled reward and the optimal reward: increasing it when the gap was large and decreasing it when the gap was small. The parameters $\\gamma$ and $c$ were updated according to the changing estimate of $a_1$. The results are as follows:\n\n   **Recovery rate comparison of an adaptive parameter strategy (%) on the Nguyen benchmark.**\n    \n   | | **Ours (Static)** | **Adaptive-UCB** |\n   | :--- | :---: | :---: |\n   | **Nguyen average** | **93.25** | 92.75 |\n\nThe results indicate that this adaptive heuristic performs slightly worse than the static setting. While automatic calibration is promising, this implementation may be too simplistic for complex search dynamics. Future work could explore first estimating $a_1$ from the rewards and then automatically calculating the UCB-extreme parameters $\\gamma$ and $c$.\n\n---\n\n**Limitations 2** Meaning and Necessity of the Tail Assumption\n\n**Response**: This limitation is addressed in our response to Question 2.\n\n---\n\nOnce again, we appreciate your detailed feedback. We believe our paper offers significant theoretical and practical innovations by uniting extreme-bandit theory with evolutionary heuristics in MCTS for Symbolic Regression. We will revise the manuscript to incorporate your suggestions and sincerely hope you will reconsider your evaluation.\n\nSincerely,  \nThe Authors\n\n---\n\n**Reference**  \n[1] Hu Y. Q., Liu X. H., Li S. Q., et al. \"Cascaded Algorithm Selection with Extreme‑Region UCB Bandit\" *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 2021, 44(10): 6782–6794.\n\n[2] Shojaee P, Meidani K, Barati Farimani A, et al. \"Transformer-based planning for symbolic regression\"[J]. *Advances in Neural Information Processing Systems*, 2023, 36: 45907-45919."}]

Author rebuttal:

Meta-review: This paper introduces new variants of Monte Carlo Tree Search (MCTS) for the symbolic regression (SR) problem. Compared to the standard approach, the authors propose (1) an extreme-bandit allocation strategy and provide theoretical optimality guarantees under certain assumptions, and (2) evolution-inspired state-jumping actions. The proposed methods are evaluated against state-of-the-art baselines on common benchmarks.

The paper has made significant contributions in (1) The proposed approaches are well-motivated and address relevant challenges in SR. In particular, an extreme bandit allocation strategy suitable for extreme value optimization is integrated into SR. (2) The experimental results are strong and demonstrate the effectiveness of the methods. (3) The heuristic designs for mutation and crossover operations appear reasonable and practically sound.

At the same time, the reviewers raise questions regarding the experimental comparisons and the ablation study. The most important aspect is whether the conditions used in theoretical analysis are widely applicable in a real-world context. The authors are encouraged to take into account the reviewers' feedback.
Decision: Accept (poster)