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

Definição do Problema
Embora o Aprendizado por Reforço Profundo (Deep-RL) tenha se tornado uma ferramenta de estado da arte para a Configuração Dinâmica de Algoritmos (DAC), especificamente para o controle de parâmetros em Algoritmos Evolutivos (EAs), uma barreira significativa permanece: a falta de análise teórica rigorosa para cenários de múltiplos parâmetros. As provas teóricas existentes para controle de parâmetros são amplamente restritas a cenários de parâmetro único, pois derivar políticas de múltiplos parâmetros que sejam eficazes, interpretáveis e passíveis de estudo formal é difícil. Além disso, confiar em redes neurais cria um gargalo de "caixa-preta"; profissionais e teóricos exigem regras matemáticas simbólicas explícitas, em vez de pesos neurais opacos, para verificar, analisar e generalizar comportamentos algorítmicos. O desafio específico abordado é o controle de quatro parâmetros simultaneamente no Algoritmo Genético (GA) $(1+(\lambda, \lambda))$ otimizando a função OneMax — um problema onde acelerações (speedups) super-constantes via controle dinâmico foram formalmente provadas, mas o controle de múltiplos parâmetros permanece subexplorado.

Metodologia
Os autores propõem uma estrutura de dois estágios para preencher a lacuna entre o desempenho empírico do Deep-RL e a interpretabilidade teórica, conforme ilustrado na Figura 1 do artigo:

1. Geração de Oráculo via Deep-RL (Estágio I):

   • Ambiente: O $(1+(\lambda, \lambda))$-GA é modelado como um Processo de Decisão de Markov Contextual (MDP) onde o estado é o fitness atual, e as ações são os quatro parâmetros: tamanho da população de mutação ($\lambda_m$), tamanho da população de crossover ($\lambda_c$), coeficiente da taxa de mutação ($\alpha$) e coeficiente do viés de crossover ($\beta$).
   • Comparação de Algoritmos: O estudo compara Double Deep Q-Networks (DDQN) e Proximal Policy Optimization (PPO).
   • Representação do Espaço de Ações: Duas arquiteturas são testadas: Combinatória (tratando combinações de parâmetros como ações atômicas) e Fatorada (decompondo o espaço de ações em subações independentes para cada parâmetro).
   • Melhorias: Os autores introduzem melhorias agnósticas ao algoritmo, incluindo decomposição do espaço de ações, deslocamento de recompensa (reward shifting - viés adaptativo) e desconto de longo horizonte (usando $\gamma \approx 1.0$).
   • Descobertas sobre RL: O DDQN com espaços de ação fatorados, deslocamento de recompensa adaptativo e fatores de desconto elevados mostra-se robusto. Em contraste, o PPO sofre de "colapso de política", convergindo frequentemente para políticas estáticas e subótimas (por exemplo, fixando $\lambda_m=1$) independentemente do espaço de ação ou das tentativas de modelagem de recompensa.

2. Destilação Simbólica (Estágio II):

   • Design Manual: Com base nas trajetórias geradas pelo melhor agente DDQN, os autores derivam manualmente uma política de controle transparente e simbólica. Eles analisam a relação entre o progresso do fitness e os valores dos parâmetros para formular equações explícitas.
   • Ajuste Fino (Fine-Tuning): Essas equações simbólicas manuais são refinadas usando SMAC3 (uma ferramenta de configuração de algoritmos automatizada). O espaço de busca inclui pontos de mudança para tamanhos de população e fatores de amplificação, permitindo a otimização precisa das constantes simbólicas.

Principais Contribuições

• Eficácia Comparativa de Métodos de Deep-RL: O artigo demonstra que, embora o PPO seja estável em domínios gerais de RL, ele falha neste ambiente específico de DAC devido ao colapso de política. Por outro lado, o DDQN, quando equipado com representações de ação fatoradas e estratégias específicas de recompensa/desconto, navega com sucesso pelo cenário de múltiplos parâmetros para gerar trajetórias de alta qualidade.
• Descoberta de Políticas Simbólicas: Os autores vão além das redes neurais de caixa-preta ao destilar comportamentos aprendidos em uma política simbólica. Esta política não é apenas interpretável, mas também supera as linhas de base existentes.
• Estrutura de Destilação de Dois Estágios: O artigo introduz uma metodologia que primeiro utiliza o Deep-RL para explorar o espaço de soluções e, em seguida, utiliza a configuração de algoritmos (SMA3) para refinar representações simbólicas manuais, resultando em uma política que é tanto empiricamente superior quanto teoricamente tratável.
• Análise de Importância de Parâmetros: Através de estudos de ablação, o artigo estabelece uma hierarquia de importância de parâmetros: $\lambda_m \gg \alpha \gg \lambda_c \gg \beta$. Revela que o desacoplamento de $\lambda_m$ e $\lambda_c$ (permitindo que $\lambda_c$ seja significativamente maior que $\lambda_m$) é um fator crítico para o desempenho.

Resultos

• Desempenho de RL: A melhor configuração de DDQN (Representação Fatorada, Deslocamento de Recompensa Adaptativo, $\gamma=0.9998$) supera consistentemente o PPO e as políticas de controle de parâmetro único através de diversos tamanhos de problema ($n=100$ a $n=2.000$).
• Desempenho da Política Simbólica: A política simbólica final (refinada por SMAC3) atinge um Tempo de Execução Esperado (ERT) normalizado de aproximadamente 4,7, comparado a 6,9 para a linha de base teórica ($\pi_{THEORY}$) e 5,8 para a linha de base baseada em IRACE.
• Escalabilidade: A política simbólica derivada mantém sua vantagem de desempenho através de uma ampla gama de tamanhos de problema, incluindo instâncias muito grandes de até $n=40.000$.
• Magnitude de Melhoria: A política ajustada por SMAC3 produz um aumento de velocidade consistente, superando a linha de base derivada da teoria em cerca de 27,5% e a abordagem baseada em IRACE entre 19,4% e 32,2%, dependendo do tamanho do problema.

Significância e Alegações
O artigo afirma que este trabalho consegue preencher a lacavra entre a descoberta empírica de Deep-RL e a verificação teórica em Computação Evolutiva. Ao converter a saída de "caixa-preta" de uma rede neural em uma política simbólica de "caixa-branca", os autores fornecem:

1. Interpretabilidade: Regras matemáticas explícitas que permitem aos pesquisadores realizar análises formais de tempo de execução, uma tarefa anteriormente dificultada pela complexidade das redes neurais.
2. Generalização: A natureza simbólica da política permite a generalização zero-shot para instâncias de problemas e dimensões não vistas, evitando o overfitting comum em redes neurais.
3. Eficiência: A avaliação da política simbólica incorre apenas em um custo de processamento $O(1)$, contornando o custo computacional da inferência de redes profundas.
4. Tratabilidade Teórica: A política derivada oferece um alvo concreto para futuras provas teóricas relativas aos fatores constantes de tempos de execução lineares para o $(1+(\lambda, \lambda))$-GA, abordando uma lacuna onde os limites teóricos atuais são frequentemente excessivamente pessimistas em comparação com os resultados empíricos.

Os autores concluem que, embora o Deep-RL seja uma ferramenta poderosa para a descoberta de políticas, seu verdadeiro valor na configuração de algoritmos é realizado apenas quando seus resultados são destilados em formas simbólicas interpretáveis que podem ser rigorosamente analisadas e generalizadas.