Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

Resumo Técnico: Rumo ao Aprendizado de Representações de Políticas em Jogos de Informação Imperfeita de Dois Jogadores com Soma Zero

Definição do Problema
Em jogos de informação imperfeita (IIG) de dois jogadores com soma zero, os agentes frequentemente se beneficiam ao raciocinar sobre suas próprias políticas e as de seus oponentes. Embora a busca de antecipação (lookahead) com limite de profundidade seja viável em jogos pequenos usando representações tabulares (ex: Minimização de Arrependimento Contrafactual), essa abordagem torna-se intratável em jogos com grandes estados de crença pública, onde enumerar todas as políticas possíveis é impossível. Consequentemente, há uma necessidade de representações compactas e úteis (embeddings) de políticas que permitam aos agentes raciocinar sobre a intenção estratégica sem acessar tabelas de políticas completas. No entanto, a pesquisa existente sobre o aprendizado dessas embeddings de política em IIGs é escassa, carecendo tanto de métodos sistemáticos para gerar conjuntos de dados de políticas quanto de tarefas de avaliação padronizadas para jusante (downstream).

Metodologia
Os autores propõem um framework sistemático composto por três componentes principais: geração de dataset, aprendizado de embedding e avaliação de jusante.

1. Geração de Dataset: O artigo introduz três métodos para criar datasets diversos de políticas para um determinado jogo:

   • Inicialização Aleatória: Inicializar redes neurais de política aleatoriamente com um esquema customizado para garantir diversidade comportamental, evitando a homogeneidade das inicializações padrão do PyTorch.
   • Oráculo de Resposta de Espaço de Política (PSRO): Treinar iterativamente melhores respostas (best-responses) para misturas de políticas existentes para gerar um conjunto em expansão de estratégias diversas.
   • Aprendizado de População Neural (NeuPL): Treinar uma única rede condicional compartilhada por todos os agentes; novas políticas são geradas amostrando do espaço de embedding latente da rede.

2. Aprendizado de Embedding: Diversos métodos são propostos para mapear políticas em representações vetoriais:

   • Autoencoder de Pesos: Um baseline ingênuo que tenta reconstruir o vetor de pesos achatado de uma rede de política a partir de uma camada de gargalo (bottleneck).
   • Encoder Funcional: Semelhante ao autoencoder de pesos, mas minimiza a divergência KL entre as distribuições de ação das redes originais e reconstruídas em estados de informação amostrados, focando na reconstrução comportamental em vez da reconstrução de pesos.
   • Encoder de Trajetória: Uma abordagem de aprendizado contrastivo (inspirada em SimCLR) que mapeia trajetórias de comprimento variável (coletadas através de execuções de políticas contra oponentes aleatórios) para um espaço latente de dimensão fixa. Este método não requer acesso aos internos da rede.
   • Embeddings Condicionais Estilo NeuPL: Uma abordagem generativa onde uma rede condicional aprende a decodificar qualquer vetor do espaço latente em uma política, gerando conjuntamente a população e os embeddings.
   • Baseline de Grover et al.: Um modelo híbrido generativo-discriminativo usando um encoder MLP e uma rede de política condicional treinada com perdas de imitação e identificação de tripletos.
   • Baselines: Inclui um Baseline Tabular (concatenação de distribuições de ação em todos os estados de informação) e um Baseline de Identidade (usando os pesos brutos da rede diretamente).

3. Tarefas de Avaliação de Jusante: A eficácia das representações é avaliada usando cinco tarefas:

   • Tarefa A & B (Predição de Payoff): Predizer payoffs esperados contra um oponente aleatório uniforme (Tarefa A) ou entre duas políticas específicas (Tarefa B) usando um preditor linear.
   • Tarefa C (Predição de Exploitabilidade): Predizer o payoff da melhor resposta de um oponente a uma determinada política.
   • Tarefa D (Melhor Resposta Zero-Shot): Treinar uma rede de política condicional para aproximar uma melhor resposta a uma política dado apenas seu embedding.
   • Tarefa E (Identificação de Agente): Classificar qual política gerou uma determinada trajetória usando k-NN ou sondas lineares.

Resultados Experimentais
Experimentos foram conduzidos no Kuhn Poker (12 estados de informação) e Leduc Poker (936 estados de informação), com resultados preliminares em jogos maiores (Liar's Dice, Phantom Tic-Tac-Toe).

• Predição de Payoff (Tarefas A & B): No Kuhn Poker, o baseline tabular dominou devido ao tamanho pequeno do jogo. No entanto, no Leduc Poker, os encoders aprendidos (Trajetória, Grover, NeuPL) superaram o baseline tabular, que sofreu com alta dimensionalidade (2808 dimensões). Os encoders Grover e de Trajetória alcançaram as maiores melhorias (até 32,3% de redução em MSE) na Tarefa A no Leduc. Os autoencoders simples de Peso e Funcional geralmente falharam em melhorar em relação à predição da média.
• Exploitabilidade e Resposta Zero-Shot (Tarefas C & D): O método NeuPL superou significativamente os baselines na predição de payoffs de melhor resposta (Tarefa C) e no treinamento de respondedores zero-shot (Tarefa D), particularmente em populações de políticas geradas pelo próprio NeuPL. Os baselines de Identidade e de Peso tiveram desempenho ruim, muitas vezes pior que o baseline da média.
• Identificação de Agente (Tarefa E): O Encoder de Trajetória (usando um classificador linear) superou substancialmente o baseline de Grover, alcançando 47,9% de acurácia top-1 no Kuhn e 57,8% no Leduc, comparado a 25,7% e 38,9% do Grover, respectivamente.
• Visualização: Visualizações t-SNE dos embeddings do Kuhn Poker revelaram que o Encoder de Trajetória separou com sucesso estratégias agressivas e passivas, enquanto os embeddings do Autoencoder de Pesos não mostraram tal estrutura.

Principais Contribuições

1. Criação de Dataset: Introdução de três métodos distintos (Random, PSRO, NeuPL) para gerar datasets de políticas diversas em IIGs.
2. Aprendizado de Representação: Proposta e comparação de múltiplas técnicas de embedding, variando de reconstrução de peso ingênua a aprendizado de trajetória contrastivo e modelos condicionais generativos.

• Suíte de Avaliação: Definição de um conjunto abrangente de tarefas de jusante (predição de payoff, resposta zero-shot, identificação de agente) para avaliar rigorosamente as representações de política.

4. Comparação Sistemática: Tanto quanto o conhecimento dos autores, este é um dos primeiros trabalhos a comparar sistematicamente técnicas de aprendizado autossupervisionado para representações de política.

Significância e Alegações
O artigo alega ser um passo fundamental em direção ao aprendizado de representações comportamentais compactas e úteis em jogos de informação imperfeita. Embora os métodos sejam descritos como "muito básicos", os resultados demonstram que semânticas comportamentais úteis estão presentes nas embeddings aprendidas, particularmente quando se usa aprendizado de trajetória contrastivo ou condicionamento estilo NeuPL. O trabalho destaca que, embora representações tabulares sejam suficientes para jogos pequenos, as embeddings aprendidas tornam-se superiores conforme a complexidade do jogo aumenta. Os autores posicionam este trabalho como um framework aberto (código disponível) para facilitar pesquisas futuras sobre o aprendizado de representação de política, observando que trabalhos futuros poderiam envolver o refinamento de termos de perda ou a integração dessas representações com planejamento em tempo de decisão.