Resumo Técnico: GARIP – Uma Referência de Média Móvel de Referência para Auto-Jogo de Última Iteração

1. Definição do Problema

Em jogos de soma zero de dois jogadores, o auto-jogo padrão usando gradiente ascendente ingênuo (SGA) falha em convergir na última iteração; em vez disso, a trajetória orbita o equilíbrio de Nash em um campo conservativo fechado. Embora as políticas de média temporal converjam, o aprendizado por reforço (RL) profundo multiagente moderno depende dos parâmetros finais da rede, tornando o comportamento da última iteração crítico.

Métodos existentes tentam restaurar a convergência da última iteração regularizando a política em direção a uma referência ("ímã") para quebrar rotações conservativas:

• MMD: Utiliza uma referência fixa (ex: uniforme). Converge para um equilíbrio regularizado (Equilíbrio de Resposta Quantal), exigindo o amortecimento (annealing) da regularização para alcançar o verdadeiro Nash.
• R-NaD: Utiliza um snapshot periódico da política atual (reiniciado a cada $K$ passos). Alcança o Nash sem necessidade de amortecimento e sustenta sistemas como o DeepNash.
• Fictitious Play: Responde ao melhor cenário contra o oponente médio, mas carece de um auto-ancoramento.

O artigo identifica uma lacuna no espaço de design: um método que se ancora à média móvel da própria política (atualizada continuamente) em vez de um ponto fixo ou snapshots discretos, visando alcançar a convergência da última iteração sem amortecimento e melhorar a robustez aos hiperparâmetros.

2. Metodologia: GARIP

GARIP (Generative Adversarial Reciprocal Iterative Play) é uma regra de atualização que combina um passo de gradiente otimista com um âncoramento de Halpern direcionado à média móvel da política.

Mecânica de Atualização

Para um jogador de linha com política $x$ e oponente $y$ em um jogo com matriz de ganhos $A$:

1. Passo Otimista: A política realiza um passo de ascensão entrópica otimista (semelhante ao Optimistic Mirror Descent) usando o gradiente atual e o gradiente anterior para antecipar o movimento do oponente.
2. Âncora de Halpern: A política atualizada é uma combinação convexa do passo otimista e da média móvel $\bar{x}$:
   $$x_{t+1} = (1 - \beta) x_{t+1/2} + \beta \bar{x}_t$$
   onde $\beta \in (0, 1)$ é uma força de ancoragem constante (sem amortecimento).
3. Atualização da Média Móvel: A âncora $\bar{x}$ é atualizada continuamente (média cumulativa em jogos de matriz ou média móvel exponencial de Polyak em RL profundo).

Motivação Teórica

O método é motivado por uma visão de "consistência de ciclo" de jogos de soma zero como um CycleGAN, onde o equilíbrio é o ponto fixo do percurso de ida e volta $F \circ G$. Ancorar na média móvel impõe consistência com este ponto fixo autorreferencial. Mecanicamente, porém, o GARIP é um optimistic mirror ascent composto com uma âncora de Halpern móvel; ele não otimiza uma perda de consistência de ciclo.

3. Contribuições Principais e Resultados Teóricos

A. O Mecanismo de "Pico de Atraso" (Peak Lag) do Colapso

O artigo identifica que o modo de falha (colapso) dos métodos de referência móvel é impulsionado pelo pico de atraso (peak lag) da referência em relação à política atual.

• Obsolescência (Staleness): Uma referência atrasa a política atual em $\ell$ passos. Sob um peso de regularização $\lambda$, isso exerce uma força de restauração proporcional a $\lambda \cdot \ell$. Se essa força sobrecarregar o gradiente do jogo, a política colapsa para um estado obsoleto e explorável.
• Dente de Serra vs. Plano:
  • R-NaD (Snapshot): Mantém a referência fixa por $K$ passos, criando um perfil de atraso em dente de serra. O pico de atraso é $K$, enquanto o atraso médio é $K/2$. Assim, Pico = 2 × Média.
  • GARIP (Média Móvel): O perfil de atraso é plano (estacionário). O pico de atraso é igual ao atraso médio.
• Proposição 1: Entre todas as médias convexas causais com um atraso médio fixo, a média móvel minimiza unicamente o pico de atraso. O pico de um snapshot é estritamente dominado por um fator de 2.

B. Propriedades de Convergência

• Convergência Local da Última Iteração (Proposição 3): O artigo prova que, para uma pequena força de ancoragem $\beta$, a âncora escala os autovalores de rotação do mapa base por $(1-\beta)$. Isso cruza a fronteira de estabilidade, transformando um mapa base recorrente (orbitante) em uma contração, garantindo estabilidade assintótica local no equilíbrio de Nash sem amortecimento.
• Pontos Fixos Não Viesados (Proposição 2): Ao contrário do MMD, que converge para um equilíbrio regularizado por ímã, a âncora autorreferencial do GARIP desaparece em qualquer ponto fixo. Assim, todo ponto fixo interior é um verdadeiro equilíbrio de Nash.
• Convergência Global: A convergência global é conjecturada para pequenos valores de $\beta$. O artigo nota um modo de falha de "consenso prematuro" para $\beta$ grande, onde a âncora força a política e a média a concordarem rápido demais em um ponto suboptimal, travando o progresso.

C. Alegação de Robustez

A principal vantagem do GARIP é a robustez aos hiperparâmetros, não o desempenho de pico.

• Como o pico de atraso do R-NaD é o dobro de seu atraso médio, um período de reset convencional $K$ (escolhido com base na intuição do atraso médio) inadvertidamente define o pico de atraso em um nível perigoso.
• O perfil plano do GARIP garante que, nas parametrizações convencionais, o pico de atraso permaneça baixo.
• O artigo afirma que o GARIP iguala o desempenho de pico do R-NaD quando ambos são ajustados para o seu melhor, mas o GARIP é o padrão superior porque sua "bacia de segurança" é mais larga.

4. Resultados Experimentais

Jogos de Matriz e Poker

• Jogos de Matriz: O GARIP alcança explorabilidade próxima ao Nash em jogos aleatórios de $10\times10$ e $12\times6$ com configurações padrão, enquanto o R-NaD com configurações padrão fica significativamente atrás (exigindo ajuste para igualar). O MMD estagna no equilíbrio regularizado.
• Poker (Kuhn/Leduc): O GARIP supera o R-NaD e o MMD com ajuste padrão, alcançando explorabilidade próxima ao best-response fictitious play exato.

RL Profundo (Jogo da Moeda & Jogos de Tabuleiro)

• Jogo da Moeda (Coin Game): GARIP e R-NaD empatam em desempenho de pico (ambos muito superiores às linhas de base sem ímã ou com ímã fixo).
• Jogos de Tabuleiro (Connect Four, Othello, Animal Shogi, Hex):
  • Jogos de Ciclo (Connect Four, Othello): Referências móveis (GARIP/R-NaD) são significativamente mais robustas que as linhas de base. O GARIP supera levemente o R-NaD em Othello.
  • Jogo Não-Cíclico (Animal Shogi): O auto-jogo ingênuo converge naturalmente. Aqui, a regularização é desnecessária e ligeiramente prejudica o desempenho, embora o GARIP permaneça o melhor regularizador entre os métodos testados.
  • Jogo Inaprendizável (Hex): Todos os métodos falham em aprender estratégias robustas devido à complexidade do tabuleiro $11\times11$, confirmando os limites do aprendiz sem busca (search-free).

Robustez de Hiperparâmetros (A Descoberta Central)

O artigo realiza um varredura sobre hiperparâmetros para medir as taxas de colapso (falha em convergir para uma política robusta).

• Grade Completa: Sobre todo o espaço de parâmetros, o GARIP e o R-NaD possuem taxas de colapso agregadas estatisticamente indistinguíveis (aprox. 25% vs 32%). Ambos podem falhar se levados a extremos de obsolência.
• Parametrização Convencional: A diferença crítica reside na localização da fronteira de colapso relativa ao uso padrão.
  • GARIP: Colapsa apenas em taxas de média muito lentas ($\rho \le 0.005$). No $\rho$ padrão de $0.01$, a taxa de colapso é de 0/40 sementes.
  • R-NaD: Colapsa em períodos de reset padrão. Para $K=200$, a taxa de colapso é de 10/40 sementes.
• Conclusão: O $K$ convencional do R-NaD subestima seu pico de atraso por um fator de 2, colocando-o na zona de perigo. O GARIP fornece uma parametrização "segura por padrão".

5. Significância e Alegações

O artigo posiciona o GARIP não como um método que alcança maior desempenho de pico que o R-NaD, mas como um padrão estruturalmente superior para auto-jogo sem amortecimento.

• Vantagem Estrutural: A média móvel é a forma de referência ideal para minimizar o pico de atraso entre médias causais. Isso o torna inerentemente mais robusto ao modo de falha de "obsolescência" que assola os snapshots periódicos.
• Impacto Prático: Usuários não precisam saber reduzir o período de reset $K$ para o R-NaD evitar o colapso; o GARIP alcança essa segurança automaticamente com parâmetros padrão.
• Limitações:
  • O artigo afirma explicitamente que não reivindica superioridade de desempenho de pico sobre o R-NaD devidamente ajustado.
  • A convergência global é uma conjectura; $\beta$ grande pode causar consenso prematuro.
  • A vantagem só se manifesta em jogos onde o auto-jogo ingênuo cicla; não oferece benefício (e impõe um leve custo) em jogos que convergem naturalmente.
  • O método não é imune ao colapso; ele simplesmente desloca a fronteira de colapso para regimes de parâmetros menos comuns.

O artigo conclui que, para auto-jogo profundo em jogos de soma zero cíclicos, a média móvel é a referência preferida, ofereis uma margem de segurança "gratuita" sobre a abordagem de snapshot.