Resumo Técnico: GAE Fica aquém em Autojogo com Informação Imperfeita

Declaração do Problema

A aprendizagem por reforço multiagente competitiva (MARL) em jogos com informação imperfeita exige que os agentes operem sob observabilidade parcial contra oponentes adversariais, necessitando de políticas estocásticas. Embora a aprendizagem por reforço em autojogo utilizando Otimização de Política Próxima (PPO) tenha alcançado sucesso empírico, enfrenta um gargalo crítico na aprendizagem de equilíbrios: a variância da estimativa de vantagem.

Implementações padrão de PPO dependem da Estimativa Generalizada de Vantagem (GAE) para agregar resíduos de diferença temporal (TD) de múltiplos passos. Em configurações de agente único, a GAE equilibra efetivamente viés e variância. No entanto, no autojogo com informação imperfeita, as políticas de equilíbrio são inerentemente estocásticas. A GAE herda aleatoriedade da amostragem de ações futuras dentro de sua trajetória de múltiplos passos. Como as políticas de equilíbrio atribuem valores diferentes a ações distintas, a amostragem de ações futuras introduz ruído intrínseco. Essa variância é amplificada em cenários de autojogo e persiste mesmo quando o crítico de valor-estado ($V$-critic) é exato. Consequentemente, a GAE padrão produz estimativas de gradiente de alta variância exatamente nos regimes onde a aprendizagem estável é mais crítica, dificultando a convergência para equilíbrios de alta qualidade.

Metodologia

Estimador Q-Boosting

Para abordar a variância introduzida pela amostragem de ações, os autores propõem o Q-boosting, um estimador de vantagem com variância reduzida. A inovação central é substituir a trajetória de TD de múltiplos passos amostrada usada na GAE por uma trajetória de Expected SARSA($\lambda$) de múltiplos passos calculada a partir de um crítico de valor-ação centralizado ($Q$-critic).

• Mecanismo: Em vez de fazer bootstrap através de ações futuras amostradas (o que introduz ruído), o Q-boosting calcula expectativas de política em cada etapa de backup. Ele média o ruído das ações futuras estocásticas ao tomar a expectativa sobre a distribuição de ações definida pela política atual.
• Formulação: Dado um crítico $Q$ centralizado $Q_i(s, a)$ e uma política conjunta $\pi$, o valor do estado é calculado como $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$. A estimativa de vantagem Q-boosting $\hat{A}^{boost}_{i,\tau}$ é definida como:
  $$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$$
  onde o resíduo TD do Expected SARSA é $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$.
• Garantia Teórica: Os autores provam que, para trajetórias on-policy e $\lambda=1$, o estimador Q-boosting fornece uma estimativa não enviesada do termo de gradiente de política da função de pontuação. Além disso, se o crítico $Q$ for suficientemente preciso, o erro quadrático médio do estimador Q-boosting é estritamente menor que o da GAE com um crítico $V$ exato, desde que as ações futuras exibam variância não nula em seus valores de ação.

Otimização de Política com Variância Reduzida (VRPO)

Os autores integram o Q-boosting em um algoritmo no estilo PPO denominado Otimização de Política com Variância Reduzida (VRPO).

• Arquitetura: O VRPO segue o paradigma de Treinamento Centralizado com Execução Descentralizada (CTDE). Utiliza atores descentralizados para execução e um crítico $Q$ centralizado para treinamento.
• Objetivo: O algoritmo mantém o objetivo substituto truncado do PPO e as atualizações de região de confiança, mas modifica os procedimentos de estimativa de vantagem e aprendizagem do crítico.
• Procedimento de Treinamento:
  1. Atualização do Atores: Os atores são atualizados usando as estimativas de vantagem Q-boosting. Para manter propriedades on-policy, os termos de expectativa de política no cálculo da vantagem são recalculados usando as probabilidades atuais do ator, mantendo os valores do crítico fixos.
  2. Atualização do Crítico: Os críticos $Q$ centralizados são treinados minimizando a perda de regressão quadrada contra o alvo Q-boosting (uma trajetória de Expected SARSA de múltiplos passos).
  3. Regularização: Uma penalidade explícita de divergência KL em relação a uma distribuição uniforme é adicionada ao objetivo da política para promover exploração e encorajar a convergência na última iteração.
• Tratamento de Espaços de Ação Grandes: Para jogos com conjuntos de ações massivos (por exemplo, Dou Dizhu), os autores decompõem decisões complexas em múltiplos passos de tempo. Isso reduz o número de ações disponíveis por passo para um tamanho gerenciável, permitindo a enumeração necessária para a expectativa de política na trajetória Q-boosting.

Contribuições Principais

1. Identificação da Fonte de Variância: O artigo identifica que a amostragem de ações futuras na GAE introduz variância adicional no autojogo estocástico, que persiste mesmo com funções de valor exatas.
2. Estimador Q-Boosting: Os autores derivam o Q-boosting, um estimador compatível com PPO que aplica uma trajetória de Expected SARSA($\lambda$) a um crítico $Q$ centralizado para média o ruído da amostragem de ações futuras.
3. Algoritmo VRPO: A proposta do VRPO, um algoritmo no estilo PPO que aproveita o Q-boosting para alcançar estabilidade e desempenho aprimorados.
4. Validação Empírica: Demonstração de que a redução da variância na estimativa de vantagem produz ganhos substanciais na qualidade do equilíbrio em jogos de várias escalas.

Resultados Experimentais

Jogos de Tamanho Médio (Explorabilidade Exata)

Os autores avaliaram o VRPO em jogos de tamanho médio onde a explorabilidade exata pode ser computada: Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3) e Liar's Dice com 2 Dados e 5 Faces (LiDi 2D5F).

• Desempenho: O VRPO alcançou consistentemente mais de 15% de menor explorabilidade em comparação com várias bases baseadas em PPO (IPPO, MAPPO, MMD, PPG) sob um cronograma de treinamento compartilhado.
• Ablação: Experimentos confirmaram que os ganhos de desempenho são robustos em diferentes parâmetros de trajetória ($\lambda$), coeficientes de regularização ($\alpha$) e coeficientes de truncamento PPO ($\epsilon$).

Jogos de Grande Escala

Os autores avaliaram o VRPO em domínios de grande escala onde a explorabilidade exata é intratável.

• Dou Dizhu: O VRPO foi treinado contra o agente anterior de última geração, PerfectDou. Sob um orçamento de treinamento correspondente ($\approx 2,65 \times 10^9$ passos de tempo), o VRPO superou o PerfectDou após apenas 40% dos passos de treinamento. Em avaliações face a face sobre 100.000 mãos, o VRPO alcançou ganhos positivos contra o PerfectDou, DouZero e contra si mesmo (em confrontos com papéis trocados), estabelecendo um novo estado da arte.
• Heads-Up No-Limit Texas Hold'em (HUNL): O VRPO foi treinado no HUNL com uma pilha de 200 big blinds. Em comparação com IPPO e MAPPO, o VRPO reduziu significativamente o desvio padrão das estimativas de vantagem durante o treinamento. Contra a forte base Slumbot, o agente VRPO alcançou um ganho médio de $33 \pm 19$ mBB/mão sobre 1.000.000 de mãos. Notavelmente, esse desempenho foi alcançado sem busca online, resolução de subjogos ou dimensionamento de aumentos baseado em blueprint.

Significado e Escopo

O artigo afirma que a contribuição principal é a identificação da variância da estimativa de vantagem como um gargalo no autojogo de equilíbrio e a demonstração de que o Q-boosting mitiga efetivamente esse problema. Os resultados sugerem que a redução da variância na estimativa de vantagem pode produzir ganhos substanciais na qualidade dos equilíbrios aprendidos.

Os autores mantêm um escopo modesto em relação às suas alegações:

• A abordagem é validada para jogos com grandes conjuntos de ações discretas (via decomposição), mas não aborda espaços de ação contínuos de alta dimensão.
• O foco empírico está no autojogo estocástico com críticos centralizados; os autores não alegam melhorias amplas sobre a GAE em benchmarks padrão de RL de agente único.
• O método depende da capacidade de calcular expectativas de política sobre ações, o que é viável nos domínios testados, mas pode exigir considerações arquitetônicas específicas para espaços de ação extremamente grandes.

Em conclusão, o VRPO representa um passo significativo para a frente na aplicação de métodos de gradiente de política a jogos com informação imperfeita, abordando uma fonte específica e anteriormente subidentificada de variância inerente à aprendizagem de equilíbrios estocásticos.