🤖 machine learning

Bayesian Symbolic Regression with Entropic Reinforcement Learning

This paper introduces ERRLESS, a scalable Bayesian symbolic regression method that employs entropy-regularized reinforcement learning to sample from the posterior distribution of algebraic expressions, thereby enabling effective uncertainty quantification and producing competitive, interpretable results on benchmarks like Feynman.

Original authors: Oussama Boussif, Mohammed Mahfoud, Younesse Kaddar, Moksh Jain, Sida Li, Damiano Fornasiere, Xiaoyin Chen, Yoshua Bengio, Esmeralda S. Whitammer

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oussama Boussif, Mohammed Mahfoud, Younesse Kaddar, Moksh Jain, Sida Li, Damiano Fornasiere, Xiaoyin Chen, Yoshua Bengio, Esmeralda S. Whitammer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of finding a missing person, you are trying to find the hidden mathematical rule that explains how the world works. This is the job of Symbolic Regression. While standard math tools are like a tailor who can only adjust the buttons on a suit that already exists (tweaking numbers in a fixed formula), symbolic regression is like a master tailor who can invent entirely new suits from scratch, stitching together different fabrics (math operations like addition, sine, or square roots) to fit the data perfectly.

However, real-world data is messy. It's noisy, like a radio signal full of static, and often scarce, like trying to guess a song's melody from just three notes. If you only find one "best" formula, you might be fooled by the static. This is where Bayesian thinking comes in. Instead of betting on a single answer, a Bayesian detective keeps a whole library of possible theories, assigning each a probability based on how well it fits the clues. This allows them to say, "I'm pretty sure it's this formula, but there's a small chance it's this other one," which is crucial when data is scarce. The big challenge has always been: how do you efficiently search through the infinite library of possible math formulas to find the right mix of probabilities without getting lost?

Enter ERRLESS, a new approach introduced by Oussama Boussif and colleagues that treats this search like a video game. Imagine a robot learning to build a complex Lego structure, but instead of just trying to build one perfect tower, it learns to build many different towers, understanding which ones are most likely to be the "true" structure given the clues. The researchers call their method ERRLESS (Entropy-Regularized Reinforcement Learning for Expression Structure Sampling).

Here is how it works in the real world of data: The team taught a neural network (a type of AI) to act as a builder. This builder doesn't just guess; it constructs mathematical expressions step-by-step, like assembling a sentence word by word. But there's a catch: the builder has to follow strict rules of physics. Just as you can't add "meters" to "seconds" to get a meaningful result, the AI is programmed to reject any math combination that breaks the laws of physical units. This is done using a "bottom-up" approach, where the AI builds small, valid pieces first and snaps them together, ensuring every step makes sense before moving on.

The AI learns through a process called Reinforcement Learning, which is like training a dog with treats. Every time the AI builds a formula that fits the data well, it gets a "treat" (a reward). But here is the clever twist: the researchers didn't just want the AI to find the single best formula. They wanted it to explore the whole "library" of possibilities. To do this, they used a technique called Maximum-Entropy Reinforcement Learning. Think of this as telling the AI, "Don't just find the one best path; explore as many different paths as possible, but make sure you visit the most promising ones more often." This ensures the AI doesn't get stuck on one idea but instead learns the full "map" of likely formulas.

The results are quite promising. When tested on the Feynman Symbolic Regression Database—a famous collection of 100 physics formulas from the legendary physicist Richard Feynman—ERRLESS performed competitively against the best existing methods. It managed to find short, easy-to-read formulas that were just as accurate as the complex ones found by other algorithms. More importantly, because it captures the uncertainty (the Bayesian perspective), it handled noisy data better. In tests where data was scarce and full of noise, ERRLESS produced a "posterior predictive mean" (a kind of average of all its best guesses) that was more accurate than a leading competitor called PySIPS. While PySIPS sometimes got confused by wild, unlikely guesses that skewed its average, ERRLESS kept its guesses grounded, providing a more reliable prediction.

The paper also highlights that ERRLESS is incredibly fast. Unlike other methods that have to stop and fine-tune the numbers in a formula over and over again (a slow, computationally expensive process), ERRLESS learns to guess both the structure of the formula and the numbers inside it all at once. This makes it an order of magnitude faster than many of its rivals.

However, the authors are careful not to claim this is a magic bullet for every problem. They note that while ERRLESS is excellent at modeling the distribution of possible answers, it can still struggle with extremely complex target expressions. They also point out that their method relies on a specific set of mathematical operators and that future work could involve teaching the AI to invent its own operators or apply these ideas to differential equations.

In short, this paper suggests that by combining the rules of physics with a smart, exploratory AI training method, we can build a system that doesn't just find a formula, but understands the landscape of possible formulas. It's a step toward machines that don't just crunch numbers, but truly understand the uncertainty and beauty of the laws that govern our universe.

Technical Summary: Bayesian Symbolic Regression with Entropic Reinforcement Learning (ERRLESS)

Problem Statement

Symbolic Regression (SR) aims to discover an algebraic expression that maps inputs to outputs, typically represented as an abstract syntax tree (AST) constructed from a library of operators. While standard SR algorithms focus on finding a single "best-fitting" expression (often trading off complexity against fit), this point estimate fails to capture epistemic uncertainty. In scientific settings characterized by limited and noisy data, a single expression may be unreliable, and the uncertainty arising from data scarcity is obscured.

Existing Bayesian approaches to SR attempt to model this uncertainty by defining a prior over expression structures and parameters, inducing a posterior distribution given the data. However, traditional methods relying on Reversible-Jump Markov Chain Monte Carlo (MCMC) or Sequential Monte Carlo (SMC) often depend on handcrafted proposal distributions and are computationally expensive to scale.

Methodology: ERRLESS

The authors propose ERRLESS (Entropy-Regularized Reinforcement Learning for Expression Structure Sampling), a scalable framework that amortizes the sampling process using a neural policy trained via maximum-entropy reinforcement learning (RL).

1. Bottom-Up Generation Environment

Unlike most deep SR methods that use top-down generation (sampling operators before operands), ERRLESS employs a bottom-up (postorder) generation process.

Sequential Decision Making: An expression tree is generated as a sequence of tokens (Reverse Polish Notation). The policy samples tokens one by one.
Constraint Enforcement: This bottom-up approach allows for the immediate enforcement of constraints. As operands (leaves) are specified first, newly added operators can be checked for dimensional validity (physical unit compatibility) and structural validity (e.g., preventing redundant compositions like $\sqrt{x^2}$ or nesting trigonometric functions) before the operator is added.
State Space: The environment tracks the current partial sequence, ensuring that only valid continuations are sampled, effectively pruning the search space.

2. Maximum-Entropy Reinforcement Learning

The core innovation is formulating the Bayesian SR task as an RL problem where the goal is to sample from the posterior distribution $p(T, \theta, \sigma | D)$ .

Reward Function: The reward $R(T, \theta, \sigma)$ is defined as the unnormalized log-posterior:
$R(T, \theta, \sigma) = \log P(T) + \log p(\theta, \sigma | T) + \sum_{i=1}^N \log \mathcal{N}(y_i; f_{T,\theta}(x_i), \sigma^2)$
Objective: The policy $\pi_\phi$ is trained to maximize the entropy-regularized objective:
$\max_\phi \left( \mathbb{E}_{(T,\theta,\sigma) \sim \pi_\phi}[R(T, \theta, \sigma)] + H[\pi_\phi] \right)$
Maximizing this objective minimizes the Kullback-Leibler (KL) divergence between the learned policy and the true posterior.
Training Algorithm: The authors utilize the Trajectory Balance (TB) objective, a core loss function for Generative Flow Networks (GFlowNets). This allows for off-policy training, where the policy learns from a replay buffer of trajectories generated by a behavior policy, optimizing the path consistency between the initial state and the terminal reward.

3. Policy Architecture

The policy is parameterized by a Transformer-based architecture:

Input: The sequence of tokens generated so far.
Heads: The network outputs three distinct distributions:
1. Action Head: Logits for the next token (operator, variable, constant, or termination).
2. Constant Head: Parameters for a Gaussian Mixture Model (GMM) to sample real-valued constants $\theta$ .
3. Noise Head: Parameters for a Log-Normal mixture to sample the noise variance $\sigma$ .

Key Contributions

Novel Generation Process: A bottom-up environment for SR that integrates dimensional analysis and structural constraints directly into the generation process, significantly reducing the search space.
End-to-End Bayesian Formulation: The first formulation of Bayesian SR (including inference of scalar parameters) as a single policy-learning problem using maximum-entropy RL, avoiding explicit per-candidate constant fitting.
Scalable Posterior Sampling: A method capable of efficiently sampling from the posterior distribution over expressions and parameters, enabling uncertainty quantification.

Experimental Results

The authors evaluated ERRLESS on three benchmarks: a synthetic dataset, the Feynman Symbolic Regression Database, and a Blackbox benchmark.

Posterior Modeling Accuracy (Synthetic Data): Compared to PySIPS (an SMC baseline), ERRLESS produced a posterior predictive mean with a significantly higher coefficient of determination ( $R^2$ ). PySIPS often failed on the posterior mean because a tail of divergent samples dominated the average, whereas ERRLESS produced finite, well-behaved posterior samples.
Feynman Benchmark: ERRLESS achieved a competitive Area Under the Curve (AUC) score of 0.924, outperforming other RL-based methods like DSR (0.873) and PhySO (0.893), as well as the Bayesian baseline BSR (0.702). It demonstrated superior robustness across varying noise levels ( $\gamma \in \{0.001, 0.01, 0.1\}$ ).
Complexity vs. Accuracy: While leading evolutionary methods sometimes achieved high fit scores, they often produced overly complex expressions. ERRLESS maintained a favorable trade-off, producing short, interpretable expressions.
Efficiency: ERRLESS was an order of magnitude faster than most learning-based competitors. This speedup is attributed to the amortization of parameter optimization; the neural policy learns to sample parameters directly, eliminating the need for an inner optimization loop (e.g., least squares fitting) required by other methods.

Significance and Claims

The paper claims that ERRLESS successfully bridges the gap between the interpretability of symbolic regression and the uncertainty quantification of Bayesian inference. By leveraging maximum-entropy RL, the method avoids the computational bottlenecks of traditional MCMC/SMC approaches while providing a full posterior distribution rather than a single point estimate.

The authors emphasize that the Bayesian perspective is particularly valuable in settings with scarce and noisy data, where the posterior predictive mean of ERRLESS outperforms single-point estimates. The work demonstrates that it is possible to learn a policy that samples expression structures and their parameters simultaneously, offering a scalable path toward automated scientific discovery where uncertainty is explicitly modeled.

Limitations noted by the authors: Performance may degrade on highly complex target expressions. Future work is suggested to condition the sampler on temperature parameters to better balance complexity and accuracy, and to extend the approach to amortize over datasets or discover operator libraries.