Resumo Técnico: EMAgnet

Declaração do Problema

Avanços recentes na resolução de jogos de informação imperfeita de dois jogadores (IIGs) demonstraram que métodos de gradiente de política regularizados, como o Proximal Policy Optimization (PPO), podem igualar ou exceder algoritmos de teoria dos jogos especializados quando usados em autoatendimento (self-play). Uma decisão de design crítica neste framework é a escolha do alvo de regularização. A distribuição uniforme emergiu como um alvo padrão, implementada via um bônus de entropia. No entanto, o alvo uniforme é estrategicamente agnóstico; ele regulariza a política igualmente em direção a todas as ações, independentemente de sua viabilidade.

Em jogos com grandes espaços estratégicos contendo muitas estratégias estritamente dominadas (opções subótimas), o alvo uniforme desperdiça o orçamento de regularização em estratégias irrelevantes. Essa limitação torna-se cada vez mais consequente à medida que a complexidade do jogo cresce e a fração de estratégias estrategicamente relevantes diminui. Além disso, abordagens existentes que utilizam regularização uniforme com recozimento (annealed) enfrentam um dilema: uma regularização forte no início força a política a explorar estratégias dominadas, enquanto uma regularização fraca na fase final falha em fornecer pressão suficiente para incentivar a mistura estratégica, frequentemente levando à convergência em estratégias puras em vez de equilíbrios de Nash.

Metodologia

Os autores introduzem o EMAgnet, um método que estende o conceito de um alvo de regularização de "ímã móvel" (moving magnet) de configurações tabulares para o aprendizado por reforço profundo (deep RL). Em vez de regularizar em direção a uma distribuição uniforme fixa, o EMAgnet regulariza em direção a uma Média Móvel Exponencial (EMA) dos próprios parâmetros da rede da política.

Mecanismo Central

O método baseia-se no PPO em autoatendimento simétrico. O objetivo padrão do PPO é aumentado com um termo de divergência de Kullback-Leibler (KL) que puxa os parâmetros da política atual ($\theta$) em direção a uma política "ímã" ($\theta_{mag}$):

$$L_{PPO-EMAg}(\theta) = L_{PPO}(\theta) + \lambda_{KL} \mathbb{E}_{z \sim \mathcal{T}} \left[ D_{KL}(\pi_{\theta_{mag}}(\cdot | z) \parallel \pi_{\theta}(\cdot | z)) \right]$$

Os parâmetros do ímã são atualizados após cada passo de PPO usando uma média aritmética no espaço de parâmetros:
$$\theta_{mag} \leftarrow (1 - \tau) \theta_{mag} + \tau \theta$$
onde $\tau \in (0, 1]$ é o tamanho do passo. O ímã é inicializado com os mesmos pesos aleatórios da política.

Propriedades Adaptativas

A inovação fundamental é a natureza adaptativa do alvo:

1. Esquecendo Estratégias Ruins: À medida que a política aprende a evitar estratégias estritamente dominadas, o ímã EMA gradualmente deixa de regularizar em direção a elas porque os pesos da política não suportam mais essas ações.
2. Lembrando Estratégias Boas: O EMA acumula naturalmente uma mistura suavizada sobre as estratégias encontradas durante o ciclo de autoatendimento. Isso incentiva a política a manter a cobertura sobre opções estrategicamente relevantes.
3. Força Constante: Ao contrário da regularização uniforme com recozimento, a força da regularização KL ($\lambda_{KL}$) permanece constante, mas o alvo evolui. Isso evita o "dilema" onde a regularização forte força a exploração de estratégias ruins ou a regularização fraca falha em evitar o colapso para estratégias puras.

Principais Contribuições

1. Extensão Algorítmica: O artigo estende o conceito tabular de ímã móvel (previamente explorado por Sokota et al.) para o aprendizado por reforço profundo ao implementar uma EMA no espaço de parâmetros dos pesos da política como o alvo de regularização.
2. Regularização Adaptativa: O método fornece um alvo de regularização adaptativo que evolui com a estratégia melhorada do agente, distinguindo-se de alvos fixos como a distribuição uniforme.
3. Avaliação Empírica: Os autores avaliam o PPO-EMAg contra o PPO self-play com regularização de ímã uniforme (usando esquemas de recozimento linear e de lei de potência) através de três categorias de jogos:
   • Benchmarks padrão (Biased RPS, Goofspiel-4, Kuhn Poker).
   • Benchmarks modificados com uma única ação de desistência (forfeit) estritamente dominada (variantes FF).
   • Benchmarks modificados onde a vasta maioria do espaço estratégico é dominada via tarefas de navegação em gridworld (variantes de Controle).

Resultados

A avaliação demonstra que o PPO-EMAg alcança uma explorabilidade menor do que as linhas de base uniformes em ambientes contendo estratégias estritamente dominadas, permanecendo competitivo em benchmarks padrão.

• Jogos Padrão: Em Biased RPS, Goofspiel-4 e Kuhn Poker, o PPO-EMAg é competitivo com as linhas de base, com a política do ímã EMA frequentemente alcançando a menor explorabilidade final.
• Jogos de Desistência (FF Games): Em jogos aumentados com uma ação de desistência estritamente dominada, o Piano-EMAg supera significativamente as linhas de base uniformes. O ímã uniforme continua a regularizar em direção à ação de desistência durante todo o treinamento, enquanto o ímã EMA se adapta para reduzir a regularização em direção a ela conforme a política aprende a evitá-la.
• Jogos de Controle: Em ambientes onde a maioria das estratégias é estritamente dominada (devido a falhas de navegação), o PPO-EMAg mostra desempenho superior e convergência significativamente mais rápida.
  • No Control Biased RPS, o recozimento linear uniforme falha em aprender por aproximadamente 7 milhões de passos antes de cair tardiamente no treinamento, enquanto o PPO-EMAg converge em 2 milhões de passos.
  • No Control Goofspiel, o recozimento linear uniforme mal melhora após 6 milhões de passos, enquanto o PPO-EMAg atinge baixa explorabilidade muito mais cedo.
• Análise de Trajetória: Visualizações das trajetórias da política no simplex de estratégia revelam que o recozcimento uniforme faz com que as políticas fiquem presas em estratégias dominadas no início ou colapsem para estratégias puras mais tarde. O PPO-EMAg evita isso reduzindo gradualmente a massa em ações dominadas enquanto mantém a pressão de mistura, permitindo que a política realize ciclos próximos ao equilíbrio de Nash.

Significância e Alegações

O artigo afirma que o EMAgnet oferece um mecanismo simples e eficaz para adaptar os alvos de regularização à estratégia evolutiva de um agente em jogos grandes. Ao regularizar em direção a uma EMA no espaço de parâmetros dos próprios pesos da política, o método evita as armadilhas da regularização uniforme em jogos com um grande número de estratégias estritamente dominadas.

Os autores postulam que, à medida que os jogos crescem em complexidade, a fração do espaço estratégico que é estrategicamente relevante tende a diminuir. Em tais cenários, alocar o orçamento de regularização para opções subótimas incorre em um custo crescente. O EMAgnet aborda isso "esquecendo" estratégias ruins enquanto "lembra" das boas, exigindo apenas uma atualização de EMA por passo de treinamento além do loop padrão do PPO. O artigo conclui que, embora o PPO-EMAg seja competitivo em benchmarks padrão, sua principal vantagem reside em jogos com altas densidades de estratégias dominadas, onde permite uma convergência mais rápida e menor explorabilidade final em comparação com o recozimento uniforme.