Transformar e Explorar: uma Técnica Simples e Eficaz para Otimização Combinatória Exploratória com Aprendizado por Reforço

Muitos problemas complexos encontrados tanto na produção quanto na vida diária podem ser conceptualizados como problemas de otimização combinatória (COPs) sobre gráficos. Nos últimos anos, modelos baseados em aprendizado por reforço (RL) surgiram como uma direção promissora, tratando a resolução de COPs como um problema de aprendizado heurístico. No entanto, os modelos de RL baseados em MDP de horizonte finito atuais têm limitações inerentes. Eles não podem explorar adequadamente para melhorar soluções durante o teste, o que pode ser necessário dada a complexidade das tarefas de otimização NP-difíceis. Algumas tentativas recentes resolvem esse problema focando no design de recompensas e engenharia de características do estado, que são tediosos e ad-hoc. Neste trabalho, propomos uma técnica muito mais simples, mas mais eficaz, chamada transformação de gauge (GT). A técnica tem origem na física, mas é muito eficaz em permitir que agentes de RL explorem para melhorar continuamente as soluções durante o teste. Além disso, a GT é muito simples, podendo ser implementada com menos de 10 linhas de código Python, e pode ser aplicada à grande maioria dos modelos de RL. Experimentalmente, mostramos que modelos de RL tradicionais com a técnica GT produzem desempenhos de ponta no problema MaxCut. Além disso, como a GT é independente de qualquer modelo de RL, ela pode ser integrada perfeitamente em várias estruturas de RL, abrindo caminho para explorações mais eficazes na resolução de COPs gerais.