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

Problematica
Sebbene il Deep Reinforcement Learning (Deep-RL) sia diventato uno strumento all'avanguardia per la Configurazione Dinamica degli Algoritmi (DAC), specificamente per il controllo dei parametri negli Algoritmi Evolutivi (EA), rimane una barriera significativa: la mancanza di un'analisi teorica rigorosa per le impostazioni multi-parametro. Le prove teoriche esistenti per il controllo dei parametri sono ampiamente limitate agli scenari a singolo parametro, poiché derivare politiche multi-parametro efficaci e interpretabili che siano suscettibili di uno studio formale è difficile. Inoltre, fare affidamento sulle reti neurali crea un collo di bottiglia "black-box"; i praticanti e i teorici richiedono regole matematiche simboliche esplicite piuttosto che pesi neurali opachi per verificare, analizzare e generalizzare i comportamenti algoritmici. La sfida specifica affrontata è il controllo simultaneo di quattro parametri nell'Algoritmo Genetico (GA) $(1+(\lambda, \lambda))$ che ottimizza la funzione OneMax — un problema in cui i miglioramenti di velocità super-costanti tramite controllo dinamico sono stati formalmente dimostrati, ma il controllo multi-parametro rimane poco esplorato.

Metodologia
Gli autori propongono un framework in due fasi per colmare il divario tra le prestazioni empiriche del Deep-RL e l'interpretabilità teorica, come illustrato nella Figura 1 del documento:

1. Generazione dell'Oracolo Deep-RL (Fase I):

   • Ambiente: Il $(1+(\lambda, \lambda))$-GA è modellato come un Processo Decisionale di Markov Contestuale (MDP) dove lo stato è il fitness corrente, e le azioni sono i quattro parametri: dimensione della popolazione di mutazione ($\lambda_m$), dimensione della popolazione di crossover ($\lambda_c$), coefficiente del tasso di mutazione ($\alpha$) e coefficiente del bias di crossover ($\beta$).
   • Confronto tra Algoritmi: Lo studio confronta Double Deep Q-Networks (DDQN) e Proximal Policy Optimization (PPO).
   • Rappresentazione dello Spazio delle Azioni: Sono testate due architetture: Combinatoria (trattando le combinazioni di parametri come azioni atomiche) e Fattorizzata (decomponendo lo spazio delle azioni in sotto-azioni indipendenti per ogni parametro).
   • Miglioramenti: Gli autori introducono miglioramenti agnostici rispetto all'algoritmo, inclusi la decomposizione dello spazio delle azioni, lo spostamento del reward (bias adattivo) e il discounting a lungo orizzonte (usando $\gamma \approx 1.0$).
   • Risultati su RL: DDQN con spazi di azione fattorizzati, spostamento adattivo del reward e fattori di discount elevati si dimostra robusto. Al contrario, PPO soffre di "collasso della policy", convergendo frequentemente a policy statiche subottimali (ad esempio, fissando $\lambda_m=1$) indipendentemente dallo spazio delle azioni o dai tentativi di reward shaping.

2. Distillazione Simbolica (Fase II):

   • Design Hand-Crafted: Basandosi sulle traiettorie generate dal miglior agente DDQN, gli autori derivano manualmente una policy di controllo trasparente e simbolica. Analizzano la relazione tra il progresso del fitness e i valori dei parametri per formulare equazioni esplicite.
   • Fine-Tuning: Queste equazioni simboliche hand-crafted sono ulteriormente perfezionate utilizzando SMAC3 (uno strumento di configurazione automatica degli algoritmi). Lo spazio di ricerca include i punti di commutazione per le dimensioni della popolazione e i fattori di amplificazione, permettendo l'ottimizzazione precisa delle costanti simboliche.

Contributi Chiave

• Efficacia Comparativa dei Metodi Deep-RL: Il documento dimostra che mentre PPO è stabile in domini RL generali, fallisce in questo specifico ambiente DAC a causa del collasso della policy. Al contrario, DDQN, quando dotato di rappresentazioni di azione fattorizzate e strategie specifiche di reward/discounting, naviga con successo nel panorama multi-parametro per generare traiettorie di alta qualità.
• Scoperta di Policy Simboliche: Gli autori vanno oltre le reti neurali black-box distillando i comportamenti appresi in una policy simbolica. Questa policy non è solo interpretabile, ma supera anche le baseline esistenti.
• Framework di Distillazione a Due Fasi: Il documento introduce una metodologia che utilizza prima il Deep-RL per esplorare lo spazio delle soluzioni e poi utilizza la configurazione degli algoritmi (SMAC3) per raffinare le rappresentazioni simboliche hand-crafted, ottenendo una policy che è sia empiricamente superiore che teoricamente trattabile.
• Analisi dell'Importanza dei Parametri: Attraverso studi di ablazione, il documento stabilisce una gerarchia di importanza dei parametri: $\lambda_m \gg \alpha \gg \lambda_c \gg \beta$. Rivela che il disaccoppiamento di $\lambda_m$ e $\lambda_c$ (permettendo a $\lambda_c$ di essere significativamente più grande di $\lambda_m$) è un fattore critico per le prestazioni.

Risultati

• Prestazioni RL: La migliore configurazione DDQN (Rappresentazione Fattorizzata, Adaptive Reward Shifting, $\gamma=0.9998$) supera costantemente PPO e le policy di controllo a singolo parametro attraverso diverse dimensioni del problema ($n=100$ a $n=2.000$).
• Prestazioni della Policy Simbolica: La policy distillata finale (perfezionata da SMAC3) raggiunge un tempo di esecuzione atteso (ERT) normalizzato di circa 4.7, rispetto a 6.9 per la baseline teorica ($\pi_{THEORY}$) e 5.8 per la baseline basata su IRACE.
• Scalabilità: La policy simbolica derivata mantiene il suo vantaggio di prestazione attraverso una vasta gamma di dimensioni del problema, incluse istanze molto grandi fino a $n=40.000$.
• Entità del Miglioramento: La policy ottimizzata tramite SMAC3 produce un miglioramento costante, superando la baseline derivata dalla teoria di circa il 27.5% e l'approccio basato su IRACE dal 19.4% al 32.2% a seconda della dimensione del problema.

Significatività e Rivendicazioni
Il documento sostiene che questo lavoro riesce a colmare il divario tra la scoperta empirica del Deep-RL e la verifica teorica nella Computazione Evolutiva. Convertendo l'output "black-box" di una rete neurale in una policy simbolica "white-box", gli autori forniscono:

1. Interpretabilità: Regole matematiche esplicite che permettono ai ricercatori di condurre un'analisi formale del tempo di esecuzione, un compito precedentemente ostacolato dalla complessità delle reti neurali.
2. Generalizzazione: La natura simbolica della policy consente la generalizzazione zero-shot a istanze di problemi e dimensioni non viste, evitando l'overfitting comune nelle reti neurali.
3. Efficienza: L'valutazione della policy simbolica comporta solo un overhead di $O(1)$, bypassando il costo computazionale dell'inferenza di reti profonde.
4. Trattabilità Teorica: La policy derivata offre un obiettivo concreto per future prove teoriche riguardanti i fattori costanti dei tempi di esecuzione lineari per il $(1+(\lambda, \lambda))$-GA, affrontando un vuoto in cui i limiti teorici attuali sono spesso troppo pessimistici rispetto ai risultati empirici.

Gli autori concludono che, sebbene il Deep-RL sia uno strumento potente per la scoperta di policy, il suo vero valore nella configurazione degli algoritmi si realizza solo quando i suoi output vengono distillati in forme simboliche interpretabili che possono essere rigorosamente analizzate e generalizzate.