Progressive Subexpression Reuse in Symbolic Regression: Insights from RL-based Search and a Genetic Programming Realization
TL;DR
Reinforcement Genetic Programming is proposed, a purely GP-based and non-RL framework that explicitly realizes a stage-wise retention– reintroduction loop through a dynamically maintained subexpression pool and pool-guided population initialization, suggesting that progressive subexpression reuse is an effective mechanism for SR search.
Abstract
Symbolic regression (SR) aims to recover compact and interpretable mathematical expressions from data. Genetic programming (GP) directly searches over symbolic structures, but its population dynamics can make it difficult to reliably preserve and accumulate useful subexpressions. In contrast, reinforcement learning (RL)-based SR has shown strong empirical performance, suggesting that learned sampling dynamics may capture useful regularities in symbolic search. Motivated by this contrast, we analyze expressions sampled during RL training and identify a recurring pattern, termed progressive subexpression reuse, where useful simple subexpressions emerge early, become increasingly frequent, and support the formation of more complex structures. Based on this observation, we propose Reinforcement Genetic Programming (RGP), a purely GP-based and non-RL framework that explicitly realizes a stage-wise retention--reintroduction loop through a dynamically maintained subexpression pool and pool-guided population initialization. Experiments on standard SR benchmarks show that RGP matches or outperforms strong baselines without RL policy training, suggesting that progressive subexpression reuse is an effective mechanism for SR search. We release our code at https://github.com/wuxiangdong586-max/RGP.