Discovering Interpretable Multi-Parameter Control Policies for Evolutionary Algorithms Using Deep Reinforcement Learning

Problem Statement
While Deep Reinforcement Learning (Deep-RL) has become a state-of-the-art tool for Dynamic Algorithm Configuration (DAC), specifically for parameter control in Evolutionary Algorithms (EAs), a significant barrier remains: the lack of rigorous theoretical analysis for multi-parameter settings. Existing theoretical proofs for parameter control are largely restricted to single-parameter scenarios because deriving effective, interpretable, multi-parameter policies that are amenable to formal study is difficult. Furthermore, relying on neural networks creates a "black-box" bottleneck; practitioners and theoreticians require explicit, symbolic mathematical rules rather than opaque neural weights to verify, analyze, and generalize algorithmic behaviors. The specific challenge addressed is controlling four parameters simultaneously in the $(1+(\lambda, \lambda))$-Genetic Algorithm (GA) optimizing the OneMax function—a problem where super-constant speedups via dynamic control have been formally proven, yet multi-parameter control remains under-explored.

Methodology
The authors propose a two-stage framework to bridge the gap between empirical Deep-RL performance and theoretical interpretability, as illustrated in Figure 1 of the paper:

1. Deep-RL Oracle Generation (Stage I):

   • Environment: The $(1+(\lambda, \lambda))$-GA is modeled as a Contextual Markov Decision Process (MDP) where the state is the current fitness, and actions are the four parameters: mutation population size ($\lambda_m$), crossover population size ($\lambda_c$), mutation rate coefficient ($\alpha$), and crossover bias coefficient ($\beta$).
   • Algorithm Comparison: The study compares Double Deep Q-Networks (DDQN) and Proximal Policy Optimization (PPO).
   • Action Space Representation: Two architectures are tested: Combinatorial (treating parameter combinations as atomic actions) and Factored (decomposing the action space into independent sub-actions for each parameter).
   • Enhancements: The authors introduce algorithm-agnostic enhancements, including action-space decomposition, reward shifting (adaptive bias), and long-horizon discounting (using $\gamma \approx 1.0$).
   • Findings on RL: DDQN with factored action spaces, adaptive reward shifting, and high discount factors proves robust. In contrast, PPO suffers from "policy collapse," frequently converging to suboptimal, static policies (e.g., fixing $\lambda_m=1$) regardless of the action space or reward shaping attempts.

2. Symbolic Distillation (Stage II):

   • Hand-Crafted Design: Based on the trajectories generated by the best DDQN agent, the authors manually derive a transparent, symbolic control policy. They analyze the relationship between fitness progress and parameter values to formulate explicit equations.
   • Fine-Tuning: These hand-crafted symbolic equations are further refined using SMAC3 (an automated algorithm configuration tool). The search space includes switching points for population sizes and amplification factors, allowing for precise optimization of the symbolic constants.

Key Contributions

• Comparative Efficacy of Deep-RL Methods: The paper demonstrates that while PPO is stable in general RL domains, it fails in this specific DAC environment due to policy collapse. Conversely, DDQN, when equipped with factored action representations and specific reward/discounting strategies, successfully navigates the multi-parameter landscape to generate high-quality trajectories.
• Discovery of Symbolic Policies: The authors move beyond black-box neural networks by distilling learned behaviors into a symbolic policy. This policy is not only interpretable but also outperforms existing baselines.
• Two-Stage Distillation Framework: The paper introduces a methodology that first uses Deep-RL to explore the solution space and then uses algorithm configuration (SMAC3) to refine hand-crafted symbolic representations, yielding a policy that is both theoretically tractable and empirically superior.
• Parameter Importance Analysis: Through ablation studies, the paper establishes a hierarchy of parameter importance: $\lambda_m \gg \alpha \gg \lambda_c \gg \beta$. It reveals that decoupling $\lambda_m$ and $\lambda_c$ (allowing $\lambda_c$ to be significantly larger than $\lambda_m$) is a critical factor for performance.

Results

• RL Performance: The best DDQN configuration (Factored representation, Adaptive Reward Shifting, $\gamma=0.9998$) consistently outperforms PPO and single-parameter control policies across problem sizes ($n=100$ to $n=2,000$).
• Symbolic Policy Performance: The final distilled policy (refined by SMAC3) achieves a normalized Expected Runtime (ERT) of approximately 4.7, compared to 6.9 for the theoretical baseline ($\pi_{THEORY}$) and 5.8 for the IRACE-based baseline.
• Scalability: The derived symbolic policy maintains its performance advantage across a wide range of problem sizes, including very large instances up to $n=40,000$.
• Improvement Magnitude: The final SMAC3-tuned policy yields a consistent speedup, outperforming the theory-derived baseline by approximately 27.5% and the IRACE-based approach by 19.4% to 32.2% depending on the problem size.

Significance and Claims
The paper claims that this work successfully bridges the gap between empirical Deep-RL discovery and theoretical verification in Evolutionary Computation. By converting the "black-box" output of a neural network into a "white-box" symbolic policy, the authors provide:

1. Interpretability: Explicit mathematical rules that allow researchers to conduct formal running time analysis, a task previously hindered by the complexity of neural networks.
2. Generalization: The symbolic nature of the policy enables zero-shot generalization to unseen problem instances and dimensions, avoiding the overfitting common in neural networks.
3. Efficiency: Evaluating the symbolic policy incurs only $O(1)$ overhead, bypassing the computational cost of deep network inference.
4. Theoretical Tractability: The derived policy offers a concrete target for future theoretical proofs regarding the constant factors of linear expected running times for the $(1+(\lambda, \lambda))$-GA, addressing a gap where current theoretical bounds are often too pessimistic compared to empirical results.

The authors conclude that while Deep-RL is a powerful tool for policy discovery, its true value in algorithm configuration is realized only when its outputs are distilled into interpretable, symbolic forms that can be rigorously analyzed and generalized.