Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

Resumo Técnico: Além do Equilíbrio de Nash Bayesiano: Aprendendo Equilíbrios de Minimax-Regret para Jogos de Equipes Adversárias sob Informação Assimétrica

1. Definição do Problema

O artigo aborda o cálculo de estratégias robustas em Jogos de Equipes Adversárias (ATGs) caracterizados por informação assimétrica. Nestes cenários, uma equipe (a equipe "informada", ex: Vermelho) possui conhecimento perfeito de um estado oculto (o tipo da Natureza, como a localização de uma bandeira), enquanto a equipe oposta (a equipe "não informada", ex: Azul) deve agir com base em uma distribuição de crença a priori sobre os possíveis tipos.

O desafio central são os deslocamentos estratégicos de distribuição. Conceitos de solução existentes, como o Equilíbrio de Nash Bayesiano (BNE), dependem de uma suposição de prior comum. No entanto, em ambientes de formações de decomposição (deceptivos), um oponente informado pode coludir com a "Natureza" para deslocar a distribuição de tipos para longe da prior nominal, explorando estratégias otimizadas para essa prior.

• Limitações das Abordagens Atuais:
  • Risco-Neutro (BNE): Altamente sensível a deslocamentos de distribuição; estratégias otimizadas para uma prior nominal tornam-se exploráveis se a distribuição real mudar.
  • Otimização Robusta de Distribuição (DRO): Fornece garantias apenas dentro de um conjunto de ambiguidade prescrito (ex: bolas de divergência KL). Estas falham sob mudanças de regime de grande escala ou deslocamentos que não se ajustam a modelos de divergência local.
  • Robustez de Pior Caso (Equilíbrio de Minimax-Regret - MRE): Minimiza o arrependimento (regret) em todo o espaço de tipos. Embora livre de distribuição, é excessivamente conservador porque trata tipos raros com o mesmo peso que tipos comuns, ignorando informações probabilísticas úteis da prior nominal.

O artigo busca um conceito de equilíbrio que equilibre a robustez contra deslocamentos estratégicos com a eficiência em distribuições típicas, evitando o conservadorismo do raciocínio de pior caso total, ao mesmo tempo em que protege contra a redistribuição adversarial de massa de probabilidade.

2. Metodologia

A. Estrutura Teórica: Equilíbrio de Minimax-Regret Probabilisticamente Robusto (PR-MRE)
Os autores introduzem o PR-MRE, um novo conceito de equilíbrio que interpola entre o BNE de risco-neutro e o MRE livre de distribuição.

• Modelo de Ameaça (Deslocamentos que Preservam a Tipicidade): Em vez de assumir deslocamentos arbitrários ou perturbações locais, os autores definem um modelo de ameaça onde as distribuições admissíveis preservam a tipicidade dos tipos. Tipos raros sob a distribuição nominal permanecem raros (limitados por um parâmetro de confiança $\delta$), enquanto a massa de probabilidade pode ser redistribuída arbitrariamente entre tipos de alta probabilidade (típicos).
• Objetivo: A equipe não informada minimiza o pior caso de arrependimento (worst-case regret) sobre este conjunto de distribuições permissíveis. O arrependimento é definido como a perda de desempenho em relação a uma estratégia ótima condicionada ao tipo.
• Formulação Matemática:
  • Para jogos de forma normal, a melhor resposta do PR-MRE é formulada como um programa bilinear robusto.
  • Diferente do BNE (programa linear) ou do MRE padrão (programa bilinear sobre o simplex completo), o PR-MRE acopla os arrependimentos entre os tipos ponderados pelas restrições do modelo de ameaça que preserva a tipicidade.
  • Os autores derivam uma relaxação de programação semidefinida (SDP) tratável para resolver este programa bilinear robusto.

B. Estrutura Algorítmica: PRMRE-PSRO
Para escalar o PR-MRE para ATGs de grande escala estruturados em grafos (como o Capture-the-Flag em grafos), os autores propõem o PRMRE-PSRO, uma extensão robusta do framework de Policy-Space Response Oracles (PSRO).

• Double Oracle Robusto (RDO): O algoritmo mantém uma população de estratégias para ambas as equipes.
  • Meta-Solver: Calcula o meta-equilíbrio PR-MRE sobre as populações de políticas atuais usando a relaxação SDP.
  • Oráculos de Melhor Resposta (Best-Response Oracles):
    • Vermelho (Informado): Utiliza Aprendizado por Reforço Multiagente (MARL) cooperativo para encontrar uma melhor resposta à meta-equilíbrio do Azul.
    • Azul (Não Informado): Utiliza MARL para encontrar uma melhor resposta que minimize o arrependimento de pior caso contra o meta-equilíbrio do Vermelho, empregando um critério de parada de minimax-regret.
• Tensor de Payoff 3D: Ao contrário do PSRO padrão que utiliza uma matriz de payoff 2D, o PRMRE-PSRO mantém um tensor de payoff 3D (Políticas do Vermelho $\times$ Políticas do Azul $\times$ Tipos) para rastrear explicitamente o desempenho e o arrependimento através de diferentes hipóteses de tipos durante o processo de aprendizado.

3. Principais Contribuições

1. Novo Conceito de Equilíbrio (PR-MRE): O artigo introduz o PR-MRE, que utiliza informações probabilísticas grosseiras (tipicidade) de uma prior nominal para minimizar a explorabilidade de pior caso. Ele fornece um limite inferior de desempenho mais justo sob deslocamentos estratégicos de distribuição em comparação ao MRE, B================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================