Abstract
Symbolic regression aims to discover concise, interpretable mathematicalexpressions that satisfy desired objectives, such as fitting data, posing ahighly combinatorial optimization problem. While genetic programming has beenthe dominant approach, recent efforts have explored reinforcement learningmethods for improving search efficiency. Monte Carlo Tree Search (MCTS), withits ability to balance exploration and exploitation through guided search, hasemerged as a promising technique for symbolic expression discovery. However,its traditional bandit strategies and sequential symbol construction oftenlimit performance. In this work, we propose an improved MCTS framework forsymbolic regression that addresses these limitations through two keyinnovations: (1) an extreme bandit allocation strategy tailored for identifyingglobally optimal expressions, with finite-time performance guarantees underpolynomial reward decay assumptions; and (2) evolution-inspired state-jumpingactions such as mutation and crossover, which enable non-local transitions topromising regions of the search space. These state-jumping actions also reshapethe reward landscape during the search process, improving both robustness andefficiency. We conduct a thorough numerical study to the impact of theseimprovements and benchmark our approach against existing symbolic regressionmethods on a variety of datasets, including both ground-truth and black-boxdatasets. Our approach achieves competitive performance with state-of-the-artlibraries in terms of recovery rate, attains favorable positions on the Paretofrontier of accuracy versus model complexity. Code is available athttps://github.com/PKU-CMEGroup/MCTS-4-SR.