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

Probleemstelling
Hoewel Deep Reinforcement Learning (Deep-RL) een state-of-the-art hulpmiddel is geworden voor Dynamic Algorithm Configuration (DAC), specifiek voor parametercontrole in Evolutionaire Algoritmen (EA's), blijft er een aanzienlijke barrière bestaan: het gebrek aan rigoureuze theoretische analyse voor scenario's met meerdere parameters. Bestaande theoretische bewijzen voor parametercontrole zijn grotendeels beperkt tot scenario's met één parameter, omdat het afleiden van effectieve, interpreteerbare policies met meerdere parameters die vatbaar zijn voor formele studie, moeilijk is. Bovendien creëert het vertrouwen op neurale netwerken een "black-box"-bottleneck; praktijkgebruikers en theoretici vereisen expliciete, symbolische wiskundige regels in plaats van opake neurale gewichten om algoritmisch gedrag te verifiëren, te analyseren en te generaliseren. De specifiew uitdaging die wordt aangepakt, is het gelijktijdig controleren van vier parameters in het $(1+(\lambda, \lambda))$-Genetisch Algoritme (GA) dat de OneMax-functie optimaliseert—een probleem waarbij super-constante versnellingen via dynamische controle formeel zijn bewezen, maar multi-parameter controle nog onderbelicht is gebleven.

Methodologie
De auteurs stellen een tweestaps-framework voor om de kloof tussen de empirische Deep-RL prestaties en theoretische interpreteerbaarheid te overbruggen, zoals geïllustreerd in Figuur 1 van het artikel:

1. Deep-RL Oracle Generatie (Fase I):

   • Omgeving: Het $(1+(\lambda, \lambda))$-GA wordt gemodelleerd als een Contextual Markov Decision Process (MDP) waarbij de staat de huidige fitness is, en de acties de vier parameters zijn: mutatie populatiegrootte ($\lambda_m$), crossover populatiegrootte ($\lambda_c$), mutatiesnelheidscoëfficiënt ($\alpha$) en crossover biascoëfficiënt ($\beta$).
   • Algoritme Vergelijking: De studie vergelijkt Double Deep Q-Networks (DDQN) en Proximal Policy Optimization (PPO).
   • Actieruimte Representatie: Twee architecturen worden getest: Combinatorisch (het behandelen van parametercombinaties als atomaire acties) en Gefactoreerd (het decomponeren van de actieruimte in onafhankelijke sub-acties voor elke parameter).
   • Verbeteringen: De auteurs introduceren algoritme-agnostische verbeteringen, waaronder actieruimte-decompositie, reward shifting (adaptieve bias) en long-horizon discounting (met behulp van $\gamma \approx 1.0$).
   • Bevindingen over RL: DDQN met gefactoreerde actieruimtes, adaptieve reward shifting en hoge discount factoren blijkt robuust. In contrast hiermee lijdt PPO aan "policy collapse", waarbij het frequent convergeert naar suboptimale, statische policies (bijv. het fixeren van $\lambda_m=1$), ongeacht de actieruimte of de pogingen tot reward shaping.

2. Symbolische Distillatie (Fase II):

   • Handmatige Ontwerp: Gebaseerd op de trajecten gegenereerd door de beste DDQN-agent, leiden de auteurs handmatig een transparante, symbolische controle-policy af. Ze analyseren de relatie tussen fitness-progressie en parametereigenschappen om expliciete vergelijkingen te formuleren.
   • Fine-tuning: Deze handmatig ontworpen symbolische vergelijkingen worden verder verfijnd met behulp van SMAC3 (een geautomatiseerde tool voor algoritmeconfiguratie). De zoekruimte omvat schakelpunten voor populatiegroottes en amplificatiefactoren, wat een precieze optimalisatie van de symbolische constanten mogelijk maakt.

Belangrijkste Bijdragen

• Vergelijkende Effectiviteit van Deep-RL Methoden: Het artikel demonstreert dat hoewel PPO stabiel is in algemene RL-domeinen, het faalt in deze specifieke DAC-omgeving vanwege policy collapse. Daarentegen navigeert DDQN, wanneer uitgerust met gefactoreerde actierepresentaties en specifieke reward/discounting strategieën, succesvol door het multi-parameter landschap om hoogwaardige trajecten te genereren.
• Ontdekking van Symbolische Policies: De auteurs gaan verder dan de black-box neurale netwerken door geleerde gedragingen te distilleren naar een symbolische policy. Deze policy is niet alleen interpreteerbaar, maar presteert ook beter dan bestaande baselines.
• Tweestaps-distillatie Framework: Het artikel introduceert een methodologie die eerst Deep-RL gebruikt om de oplossingsruimte te verkennen en vervolgens algoritmeconfiguratie (SMAC3) gebruikt om handmatige symbolische representaties te verfijnen, wat een policy oplevert die zowel empirisch superieur als theoretisch traceerbaar is.
• Parameter Belangrijkheidsanalyse: Door middel van ablatie-studies stelt het artikel een hiërarchie van parameterbelang vast: $\lambda_m \gg \alpha \gg \lambda_c \gg \beta$. Het onthult dat het ontkoppelen van $\lambda_m$ en $\lambda_c$ (waarbij $\lambda_c$ aanzienlijk groter kan zijn dan $\lambda_m$) een cruciale factor is voor prestaties.

Resultaten

• RL Prestaties: De beste DDQN-configuratie (Gefactoreerde representatie, Adaptive Reward Shifting, $\gamma=0.9998$) presteert consistent beter dan PPO en single-parameter controle-policies over verschillende probleemgroottes ($n=100$ tot $n=2.000$).
• Symbolische Policy Prestaties: De uiteindelijke gedistilleerde policy (verfijnd door SMAC3) bereikt een genormaliseerde Expected Runtime (ERT) van ongeveer 4.7, vergeleken met 6.9 voor de theoretische baseline ($\pi_{THEORY}$) en 5.8 voor de IRACE-gebaseerde baseline.
• Schaalbaarheid: De afgeleide symbolische policy behoudt zijn prestatievoordeel over een breed scala aan probleemgroottes, inclusief zeer grote instanties tot $n=40.000$.
• Omvang van Verbetering: De uiteindelijke door SMAC3 getunede policy levert een consistente versnelling op, waarbij deze de theoretisch afgeleide baseline met ongeveer 27,5% en de IRACE-gebaseerde benadering met 19,4% tot 32,2% overtreft, afhankelijk van de probleemgrootte.

Betekenis en Claims
Het artikel claimt dat dit werk erin is geslaagd de kloof tussen empirische Deep-RL ontdekking en theoretische verificatie in Evolutionaire Computatie te overbruggen. Door de "black-box" output van een neuraal netwerk om te zetten in een "white-box" symbolische policy, bieden de auteurs:

1. Interpreteerbaarheid: Expliciete wiskundige regels die onderzoekers in staat stellen om formele looptijdanalyses uit te voeren, een taak die voorheen werd gehinderd door de complexiteit van neurale netwerken.
2. Generalisatie: Het symbolische karakter van de policy maakt zero-shot generalisatie mogelijk naar ongeziene probleeminstanties en dimensies, waardoor overfitting die gebruikelijk is bij neurale netwerken wordt vermeden.
3. Efficiëntie: Het evalueren van de symbolische policy brengt slechts $O(1)$ overhead met zich mee, waardoor de computationele kosten van deep netwerk inferentie worden omzeild.
4. Theoretische Traceerbaarheid: De afgeleide policy biedt een concreet doel voor toekomstige theoretische bewijzen met betrekking tot de constante factoren van lineaire verwachte looptijden voor het $(1+(\lambda, \lambda))$-GA, waarmee een gat wordt gedicht waar huidige theoretische grenzen vaak te pessimistisch zijn vergeleken met empirische resultaten.

De auteurs concluderen dat hoewel Deep-RL een krachtig hulpmiddel is voor policy discovery, de werkelijke waarde in algoritmeconfiguratie pas wordt gerealiseerd wanneer de outputs worden gedestilleerd naar interpreteerbare, symbolische vormen die rigoureus geanalyseerd en gegeneraliseerd kunnen worden.