Resumo Técnico: Inícios de Jogo Aumentados por Dados para Acelerar a Exploração em Auto-Jogo em Jogos de Informação Imperfeita

Declaração do Problema

Encontrar equilíbrios aproximados em jogos competitivos de grande escala com informação imperfeita (por exemplo, StarCraft, Dota, CounterStrike) permanece computacionalmente inviável para a maioria dos praticantes. O principal gargalo não é necessariamente a resolução de interações estratégicas, mas a dificuldade de exploração inerente a ambientes com recompensas esparsas, horizontes de decisão longos e dinâmicas complexas de estados ocultos. Métodos tradicionais de auto-jogo frequentemente desperdiçam recursos computacionais explorando repetidamente longas sequências de ações coordenadas para alcançar subjogos estrategicamente relevantes, mesmo que o conjunto de escolhas estratégicas de alto nível distintas seja comparativamente pequeno.

Embora a clonagem comportamental (BC) a partir de demonstrações humanas seja uma abordagem comum para iniciar a competência, ela requer trajetórias extensas de estado-ação para aprender habilidades necessárias. Além disso, benchmarks existentes para jogos de informação imperfeita frequentemente carecem dos desafios de exploração (recompensas esparsas, horizontes longos) encontrados em domínios do mundo real, tornando difícil avaliar métodos projetados para acelerar a exploração.

Metodologia: Inícios de Jogo Aumentados por Dados (DAGS)

Os autores propõem Inícios de Jogo Aumentados por Dados (DAGS), uma estratégia que acelera a exploração online inicializando episódios de aprendizado por reforço (RL) em estados intermediários amostrados de dados de jogabilidade offline, em vez de sempre reiniciar a partir do estado raiz.

Mecanismo Central

1. Conjunto de Dados Offline: O método utiliza um conjunto de dados offline $D$ de estados globais coletados de jogabilidade proficientes (mas não necessariamente ótimas). Esses estados fornecem uma cobertura ampla de situações de jogo estrategicamente distintas.
2. Distribuição de Estado Inicial Aumentada: DAGS define uma distribuição de mistura $\tilde{d}^\beta_0 = (1 - \beta)d_0 + \beta d_D$, onde $d_0$ é a distribuição raiz original e $d_D$ é uma distribuição uniforme sobre o conjunto de dados offline. O parâmetro $\beta \in [0, 1]$ controla a fração de episódios que começam a partir de estados offline.
3. Integração com Auto-Jogo: Durante o treinamento, episódios são amostrados a partir de $\tilde{d}^\beta_0$. Quando um episódio começa a partir de um estado offline, o ambiente continua evoluindo de acordo com as dinâmicas de transição originais, preservando a estrutura de informação do jogo.
4. Mitigação de Viés de Equilíbrio: Os autores identificam que modificar a distribuição de estados iniciais em jogos de informação imperfeita pode distorcer as crenças dos agentes sobre informações privadas, levando a equilíbrios enviesados. Para mitigar isso, eles empregam aprendizado multi-tarefa com uma bandeira de observação binária ($f$) indicando a fonte do episódio ($f=0$ para início na raiz, $f=1$ para início no conjunto de dados). Isso permite que a política aprenda uma estratégia não enviesada para o jogo original ($f=0$), enquanto aproveita a exploração aumentada dos episódios iniciados no conjunto de dados ($f=1$) através de parâmetros de rede compartilhados.

Construção do Benchmark

Para avaliar DAGS em um ambiente controlado com explorabilidade analiticamente tratável, os autores introduzem um novo conjunto de ambientes de benchmark baseados em jogos OpenSpiel (Kuhn Poker, Goofspiel). Esses benchmarks aplicam duas transformações:

1. Transformação de Desistência (FF): Adiciona uma ação "desistência" estritamente dominada a cada nó de decisão para modelar a falha em executar tarefas de controle.
2. Transformação de Jogo de Controle: Substitui cada decisão por uma tarefa de navegação em gridworld de múltiplos passos. Os agentes devem navegar por uma grade para alcançar "quadrados de ação" específicos dentro de um limite de tempo. Se falharem em alcançar o quadrado correto, a ação de desistência é acionada.
   Essas transformações aumentam significativamente o horizonte e o espaço de estados, permitindo que as políticas sejam analiticamente reduzidas ao jogo base para cálculo exato da explorabilidade.

Contribuições Principais

1. Nova Suíte de Benchmarks: Os autores fornecem um conjunto de jogos de soma zero com dois jogadores (2p0s) com horizontes longos e desafios de exploração (navegação em gridworld) onde a explorabilidade pode ser computada analiticamente. Isso aborda a falta de benchmarks que combinam complexidade estratégica com avaliação tratável.
2. Convergência Acelerada via DAGS: O artigo demonstra que DAGS permite que algoritmos de gradiente de política regularizados (especificamente PPO-Uniform e PPO-EMAg) alcancem menor explorabilidade em jogos com desafios de exploração significativamente maiores sob orçamentos computacionais fixos.
3. Identificação e Mitigação de Viés de Equilíbrio: O trabalho demonstra que aumentar distribuições de estados iniciais pode enviesar equilíbrios aprendidos em jogos de informação imperfeita. Fornece uma estratégia de mitigação direta usando bandeiras de observação multi-tarefa para recuperar jogadas não enviesadas.

Resultados Experimentais

Os autores avaliaram DAGS em Kuhn Poker, Goofspiel de 4 cartas e um jogo de contraexemplo personalizado projetado para expor viés de equilíbrio.

• Escalonamento de Exploração: Nas variantes "Control Travel" (onde os agentes devem navegar por grades para executar ações), o auto-jogo padrão ($\beta=0$) falhou em descobrir como navegar para quadrados de ação específicos dentro dos limites de tempo, resultando em alta explorabilidade (efetivamente desistindo). DAGS ($\beta > 0$) inicializou com sucesso episódios em estados intermediários, permitindo que os agentes se concentrassem em resolver interações estratégicas de alto nível. Em Goofspiel com alta dificuldade (Travel 20), o auto-jogo padrão estagnou em alta explorabilidade, enquanto DAGS continuou a convergir para baixa explorabilidade.
• Viés de Equilíbrio: No jogo de contraexemplo, definir $\beta=1$ (sempre iniciar a partir de dados offline) fez com que os agentes convergissem para um equilíbrio enviesado com alta explorabilidade devido a crenças distorcidas sobre informações ocultas.
• Eficácia da Mitigação: O uso de um $\beta$ intermediário (por exemplo, 0,5) combinado com a bandeira de observação de identificação de tarefa mitigou com sucesso o viés. O ramo $f=0$ aprendeu uma política não enviesada para o jogo original, enquanto o ramo $f=1$ facilitou a exploração. Essa abordagem alcançou exploração eficaz sem sacrificar a correção do equilíbrio.

Significado e Alegações

O artigo alega que DAGS oferece um caminho prático para resolver jogos de grande escala com informação imperfeita, desacoplando o custo de explorar longas sequências de controle do custo de aprender interações estratégicas. Ao aproveitar dados offline para cobertura de estados em vez de inicialização de política, DAGS requer menos dados que a clonagem comportamental e é viável mesmo quando as demonstrações são incompletas ou subótimas.

Os autores enfatizam que sua contribuição é modesta em escopo quanto aos algoritmos específicos utilizados (PPO regularizado), mas significativa no insight metodológico sobre redefinições de estado em configurações multiagente. Eles destacam que, embora modificar distribuições de início seja uma técnica conhecida em RL de agente único, sua aplicação a jogos de informação imperfeita introduz riscos únicos de viés de equilíbrio que devem ser abordados. A mitigação proposta via aprendizado multi-tarefa fornece uma solução robusta para esse desafio específico.

O trabalho conclui que, embora seus benchmarks atuais usem mecânicas simples para preservar a tratabilidade analítica, os princípios de DAGS devem escalar para domínios complexos (por exemplo, jogos de luta, FPS) onde demonstrações são escassas e a clonagem comportamental é ineficiente em termos de dados. Os autores posicionam DAGS como uma direção promissora para trabalhos futuros na aplicação dessas técnicas em jogos onde a explorabilidade exata não é tratável.