Resumo Técnico: Oráculos de Resposta ao Espaço de Políticas Global para Jogos de Soma Zero com Dois Jogadores

1. Declaração do Problema

O cálculo de equilíbrios de Nash em jogos de soma zero com dois jogadores e em grande escala é computacionalmente intratável devido aos enormes espaços de estratégias. O framework Policy-Space Response Oracles (PSRO) aborda isso expandindo iterativamente um conjunto restrito de estratégias (população) e resolvendo o "meta-jogo" induzido para encontrar uma meta-estratégia, tipicamente usando Aprendizado por Reforço Profundo (DRL) para gerar Respostas Ótimas (BRs).

Um desafio central no PSRO é a construção da população de estratégias: como montar um pequeno conjunto de estratégias sob orçamentos computacionais limitados de modo que o jogo restrito induzido aproxime fielmente o jogo completo. Variantes existentes do PSRO dependem de Solvers de Meta-Estratégia Baseados em Jogos Restritos (RGB-MSSs), que calculam meta-estratégias usando apenas a matriz de pagamentos do jogo restrito atual. Os autores argumentam que essa abordagem leva a expansões ineficientes. Como os RGB-MSSs ignoram estratégias fora da população atual, as BRs resultantes podem ser localmente fortes, mas contribuem pouco para reduzir a explorabilidade global (a distância para um equilíbrio do jogo completo). Em cenários de pior caso, os RGB-MSSs podem exigir a incorporação de todo o espaço de estratégias para convergir, mesmo quando um suporte de equilíbrio muito menor existe.

2. Metodologia: PSRO Global

Os autores propõem o PSRO Global, um framework que guia a expansão da população otimizando explicitamente a qualidade da população após a adição de uma estratégia candidata. A métrica central para essa qualidade é a Explorabilidade da População (PE), definida como a mínima explorabilidade alcançável por qualquer estratégia mista suportada na população restrita contra oponentes do jogo completo.

A metodologia consiste em um framework de duas fases Exploração–Seleção:

Fase I: Exploração

Em vez de treinar uma única BR contra uma única meta-estratégia, o PSRO Global gera um pool diversificado de respostas candidatas.

• Pool de Misturas: Um conjunto de meta-estratégias $S_t = \{\sigma_k\}_{k=1}^K$ é construído. Isso inclui uma meta-estratégia base (por exemplo, de um RGB-MSS padrão como NE de Jogo Restrito) e $K-1$ misturas adicionais amostradas uniformemente do simplex de probabilidade (por exemplo, via distribuição Dirichlet).
• Treinamento Condicional: Para tornar viável o treinamento de múltiplos candidatos, uma única rede de política condicional $\pi_\theta(a|s, \sigma)$ é treinada via DRL (PPO) para gerar respostas adaptadas a cada $\sigma_k \in S_t$. Isso produz um conjunto de estratégias candidatas $\{\pi_k\}$.

Fase II: Seleção

O framework avalia qual candidato, se adicionado à população, resultaria na menor PE.

• Estimativa de PE: Para cada expansão candidata $\Pi_r \cup \{\pi_k\}$, o algoritmo estima a PE. Isso é feito usando um procedimento de Minimização de Arrependimento (RM) – Resposta Ótima. Uma rede avaliadora condicional $\beta_\psi(a|s, \sigma)$ é usada para rastrear a resposta ótima contra a mistura minimizadora de arrependimento $\rho_k$ para cada candidato.
• Pontuação Regularizada: Para garantir robustez contra erros de estimativa (onde um candidato pode parecer bom simplesmente porque é raramente jogado na mistura de estimativa), uma pontuação regularizada é usada:
  $$\widehat{PE}^{reg}_k = (1 - \hat{p}_k)(\widehat{PE}(\Pi_r; G) - U(\beta_k, \rho_r)) + \widehat{PE}_k$$
  onde $\hat{p}_k$ é a massa atribuída à nova estratégia na mistura.
• Expansão: O candidato $k^*$ que minimiza a PE regularizada é selecionado. A população é expandida adicionando tanto o candidato selecionado $\pi_{k^*}$ quanto a BR de avaliação correspondente $\beta_{k^*}$ (uma expansão no estilo Anytime-PSRO).

3. Contribuições Principais

1. Análise Teórica das Limitações dos RGB-MSSs: Os autores provam que confiar exclusivamente em pagamentos de jogos restritos (RGB-MSSs) pode levar a uma expansão de população altamente ineficiente. Eles demonstram, via Teorema 3.2, que para qualquer RGB-MSS, existem jogos onde a convergência exige a adição de todas as $N$ estratégias puras, enquanto um solver específico da instância poderia atingir o equilíbrio em $O(S)$ iterações (onde $S$ é o tamanho do suporte do equilíbrio).
2. Formulação de Otimização: Eles formulam a construção da população de estratégias como um problema de otimização explícito: minimizar a PE pós-expansão. Isso alinha o processo de expansão diretamente com o objetivo principal de aproximar o equilíbrio do jogo completo.
3. Algoritmo PSRO Global: Eles instanciam esse framework como um algoritmo escalável baseado em DRL. Inovações técnicas-chave incluem:
   • Compartilhamento de Parâmetros: Uso de redes neurais condicionais para gerar múltiplos candidatos e estimar a PE simultaneamente, amortizando o custo computacional.
   • Seleção Regularizada: Um mecanismo de pontuação que previne a seleção de candidatos que parecem benéficos apenas devido ao ruído de estimativa.
4. Garantias de Convergência: Sob a suposição de um oráculo exato, o framework preserva as garantias de convergência em iterações finitas do PSRO padrão, oferecendo complexidade de iteração melhorada em famílias de jogos adversariais (Teorema 4.3).

4. Resultados Experimentais

Experimentos foram conduzidos em jogos de forma extensiva padrão de dois jogadores e soma zero: Kuhn Poker, Liar's Dice, Leduc Poker e Goofspiel (5 e 13 cartas).

• Comparação com Variantes do PSRO: Sob orçamentos de interação com o ambiente correspondentes, o PSRO Global alcançou consistentemente uma Explorabilidade da População (PE) menor do que variantes padrão do PSRO usando solvers Nash, AlphaRank, PRD, Uniforme e Anytime PSRO. A melhoria foi mais significativa em jogos maiores (Leduc Poker, Goofspiel).
• Comparação com Métodos Impulsionados por Diversidade: O PSRO Global superou o PSD-PSRO (uma variante impulsionada por diversidade), indicando que simplesmente incentivar adições diversas é menos eficaz do que selecionar explicitamente para reduzir a PE. Adicionar um objetivo de diversidade à fase de exploração do PSRO Global proporcionou ganhos adicionais marginais em alguns jogos.
• Comparação com Métodos de População Condicional: O PSRO Global superou o NeuPL (Neural Population Learning), que também usa compartilhamento condicional de parâmetros. Isso isola o ganho de desempenho ao mecanismo de seleção (minimizar a PE pós-expansão) e não apenas à arquitetura de compartilhamento de parâmetros.
• Estudos de Ablação: Remover qualquer componente (por exemplo, usar apenas exploração, seleção aleatória ou remover a regularização de PE) degradou o desempenho, confirmando que a combinação de exploração de informações globais e seleção baseada em PE é crítica.

5. Significado e Alegações

O artigo afirma que a fonte dominante de melhoria no PSRO Global é o uso explícito de informações globais para selecionar expansões de população. Ao avaliar candidatos com base em sua capacidade de reduzir a explorabilidade de toda a população contra o jogo completo (em vez de apenas responder a uma única meta-estratégia de jogo restrito), o método evita as ineficiências inerentes às abordagens baseadas apenas em jogos restritos.

Os autores posicionam o PSRO Global como uma solução prática e escalável para jogos de soma zero em grande escala que alcança uma aproximação de equilíbrio superior com menos iterações de política. Eles observam que sua discussão se limita a jogos de soma zero com dois jogadores, pois estender a métrica PE para configurações de soma geral com múltiplos jogadores é não trivial devido à perda da estrutura de ponto de sela. Sugere-se trabalho futuro para estender o framework a classes de jogos mais amplas e desenvolver aproximações de PE escaláveis para essas configurações.