NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

1. Formulação do Problema

O artigo aborda o desafio de encontrar Equilíbrios de Nash (EN) em jogos de informação imperfeita de soma zero com dois jogadores (2p0s IIGs) utilizando Aprendizado por Reforço Multiagente (MARL).

• A Dificuldade Central: Embora o Aprendizado por Reforço Profundo (DRL) tenha obtido sucesso em jogos de informação perfeita, os 2p0s IIGs (como Poker) envolvem observabilidade parcial e informações ocultas.
• Limitações dos Métodos Existentes:
  • Métodos baseados em população (e.g., PSRO, NFSP): Frequentemente exigem cálculos caros de melhor resposta e garantem convergência apenas para uma política média, não para a última iteração. Extrair uma política final em configurações de DRL não é trivial.
  • Minimização de Arrependimento Contrafactual (CFR): Requer enumeração completa da árvore do jogo (baseado em modelo), tornando-o intratável para domínios grandes.
  • Métodos baseados em regularização (e.g., R-NaD): Abordagens recentes utilizam regularização para garantir convergência da última iteração para um equilíbrio regularizado. No entanto, estes não são necessariamente verdadeiros Equilíbrios de Nash (permanecem exploráveis). Além disso, implementações práticas existentes (como R-NaD) dependem de Dinâmicas Replicadoras Neurais (NeuRD), que demonstraram desempenho inferior comparado a métodos padrão de gradiente de política em benchmarks.
• A Lacuna: Há uma falta de um algoritmo escalável, livre de modelo e baseado em gradiente de política que convirja provadamente para um Equilíbrio de Nash exato em IIGs de grande escala.

2. Metodologia

Os autores propõem uma abordagem em duas etapas: um framework teórico (IMMD) e um algoritmo prático (NASHPG).

A. Framework Teórico: MMD Iterativo (IMMD)

Os autores estendem o Descenso Espelho Magnético (MMD), um método que resolve Variacionais Inequações (VI) regularizadas.

• VI Regularizada: Problemas VI padrão para Equilíbrios de Nash são monótonos, mas não fortemente monótonos, tornando-os difíceis de resolver diretamente. O MMD adiciona um regularizador fortemente convexo (baseado em divergência de Bregman) para criar um operador fortemente monótono, garantindo uma solução única.
• Refinamento Iterativo: Em vez de resolver um único problema regularizado, o IMMD resolve uma sequência deles.
  1. Comece com um perfil de estratégia inicial $\rho$.
  2. Resolva o problema VI regularizado $VI(Z, G_\rho)$ para encontrar uma nova estratégia $z = M(\rho)$.
  3. Utilize esta nova estratégia $z$ como referência $\rho$ para a próxima rodada.
• Garantia Teórica: O artigo prova que este processo iterativo produz uma redução estritamente monótona na divergência de Bregman para qualquer Equilíbrio de Nash. Consequentemente, a sequência de estratégias converge para um verdadeiro Equilíbrio de Nash.

B. Algoritmo Prático: Gradiente de Política de Nash (NASHPG)

Para tornar o IMMD aplicável a jogos de grande escala onde a enumeração completa é impossível, os autores derivam o NASHPG:

• De Estratégias Mistas para Comportamentais: Eles aproximam a divergência de Bregman de estratégia mista (usada no IMMD) com uma divergência de Kullback-Leibler (KL) entre políticas comportamentais (políticas estocásticas em RL).
• Função Objetivo: O algoritmo otimiza um objetivo de política regularizado:
  $$\text{Objetivo} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$$
  Onde $\pi$ é a política atual, $\rho$ é a política de referência (do loop externo anterior) e $\alpha$ é a força da regularização.
• Estrutura do Algoritmo:
  1. Loop Interno: Realize $K$ passos de atualizações padrão de gradiente de política (e.g., usando PPO) para otimizar o objetivo regularizado contra a referência atual $\rho$.
  2. Loop Externo: Após $K$ passos, atualize a política de referência $\rho$ para a política atual $\pi$ e repita.
• Modularidade: O NASHPG é agnóstico ao estimador específico de gradiente de política. Pode integrar-se perfeitamente com algoritmos avançados de RL de agente único como PPO (Proximal Policy Optimization).

3. Principais Contribuições

1. Convergência Teórica: Introduziu o IMMD, um framework de regularização multi-rota que garante redução estritamente monótona na divergência de Bregman e convergência para um Equilíbrio de Nash exato em jogos de forma extensiva 2p0s.
2. Algoritmo Prático (NASHPG): Desenvolveu um algoritmo escalável e livre de modelo que implementa o framework IMMD usando métodos padrão de gradiente de política (como PPO) e regularização KL.
3. Validação de Hipótese: Forneceu evidência empírica de que o desempenho pobre de métodos anteriores de regularização (como R-NaD) deveu-se ao uso de NeuRD como solucionador interno, e não ao próprio framework de regularização. Substituir o NeuRD pelo PPO em um framework similar melhorou significativamente o desempenho.
4. Escalabilidade: Demonstrou a capacidade de resolver domínios de grande escala (e.g., Battleship, Heads-Up No-Limit Texas Hold'em) onde a enumeração exata é impossível.

4. Resultados Experimentais

Os autores avaliaram o NASHPG em sete jogos que variam de pequenos (Kuhn Poker) a massivos (Heads-Up No-Limit Texas Hold'em).

• Convergência e Estabilidade: O NASHPG mostrou convergência estável sem divergência, mesmo com altas forças de regularização, ao contrário de algumas linhas de base.
• Desempenho vs. Linhas de Base:
  • Jogos Pequenos: O NASHPG alcançou explorabilidade comparável ou menor que NFSP, PSRO, MMD e R-NaD em Kuhn Poker, Leduc Poker, Dark Hex e Phantom Tic-Tac-Toe.
  • Jogos Grandes: Em Battleship e Heads-Up No-Limit Texas Hold'em (onde a explorabilidade exata é intratável), o NASHPG alcançou payoffs médios mais altos em partidas frente a frente contra todas as linhas de base (NFSP, PSRO, R-NaD, MMD).
• Estudo de Ablação (R-NaD vs. PPO): Um experimento controlado substituiu o NeuRD pelo PPO no framework R-NaD (criando RNaD-PPO).
  • Em jogos pequenos, a regra de atualização importava menos.
  • Em jogos grandes, o RNaD-PPO superou dramaticamente o R-NaD padrão, estreitando a lacuna com o NASHPG. Isso confirmou que a regra de otimização interna (PPO vs. NeuRD) é o principal gargalo na regularização multi-rota baseada em amostras.
• Eficiência: A implementação exigiu apenas ~20 linhas de modificação de código sobre o PPO Independente padrão, destacando sua acessibilidade.

5. Significado

• Ponte entre Teoria e Prática: O artigo conecta com sucesso a lacuna entre garantias de convergência teóricas (frequentemente limitadas a jogos pequenos e enumerados) e algoritmos práticos e escaláveis de MARL.
• Novo Paradigma para MARL: Estabelece que refinar iterativamente uma referência de regularização combinado com gradientes de política padrão é uma abordagem superior para encontrar Equilíbrios de Nash comparado a métodos baseados em população ou técnicas de regularização mais antigas.
• Acessibilidade: Ao depender do PPO padrão e de uma simples regularização KL, o NASHPG reduz a barreira de entrada para praticantes, permitindo-lhes aplicar garantias avançadas de convergência teórica de jogos sem a necessidade de solucionadores personalizados complexos ou enumeração completa da árvore do jogo.
• Desempenho de Ponta: Estabelece um novo benchmark para métodos livres de modelo em jogos de informação imperfeita, superando linhas de base estabelecidas tanto em domínios pequenos quanto grandes.