Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning

Este trabalho apresenta um regime de treinamento multiagente escalável e genérico que combina busca em árvore, modelos generativos profundos e conceitos de barganha de Nash para criar agentes de aprendizado por reforço capazes de modelar oponentes, negociar eficazmente e alcançar bem-estar social comparável ao de humanos em jogos de barganha bilaterais.

O essencial

Imagine que você está jogando um jogo de negociação complexo, como um leilão ou uma troca de presentes, mas não sabe o que a outra pessoa realmente quer. Ela pode estar escondendo seus verdadeiros desejos. O grande desafio para os cientistas da computação é: como criar um robô inteligente que consiga negociar bem com humanos, sem ter sido programado com regras específicas para cada situação?

Este artigo da Google DeepMind apresenta uma solução genial que mistura três ideias poderosas: Aprendizado de Máquina (IA), Planejamento Estratégico (como um xadrezista) e Imaginação (Modelos Generativos).

Vamos descomplicar isso com analogias do dia a dia:

1. O Problema: O "Adivinha" e o "Estrategista"

Antes, para criar robôs que negociam, os cientistas precisavam escrever regras manuais (como "se o humano oferecer X, responda Y"). Isso é como tentar ensinar alguém a dirigir apenas com um manual de instruções; funciona em estradas retas, mas falha no trânsito caótico.

Além disso, em jogos onde você não vê tudo (como poker ou negociações onde os preços são privados), calcular a melhor jogada é um pesadelo matemático. É como tentar adivinhar todas as cartas do oponente em um baralho gigante sem olhar para elas.

2. A Solução: O "Detetive Imaginativo" (GenBR)

Os autores criaram um novo método chamado GenBR (Resposta Gerativa). Pense nele como um detetive que usa a imaginação para resolver crimes.

• O Detetive (Busca MCTS): O robô usa um algoritmo de busca (chamado MCTS) que funciona como um xadrezista olhando para o futuro. Ele simula milhares de "e se?" para ver qual jogada é melhor.
• A Imaginação (Modelo Generativo): Aqui está a mágica. Em jogos onde você não vê tudo, o robô precisa adivinhar o que está acontecendo. Em vez de tentar calcular todas as possibilidades (o que é impossível), ele usa uma Rede Neural Generativa.
  • Analogia: Imagine que você está jogando "Advinhe o Objeto" com um amigo. Você não vê o objeto dele. O modelo generativo é como o seu cérebro criando uma "ilusão" ou um "sonho" do que o objeto pode ser, baseado no que você vê (o histórico do jogo). O robô "sonha" com o estado do mundo (o que o oponente tem) e planeja sua jogada baseada nesse sonho. Se o sonho estiver errado, ele aprende e ajusta o "sonho" na próxima vez.

3. O Treinamento: A "Escola de Negociação" (PSRO)

Como ensinar esse robô a ser bom? Eles usaram um sistema chamado PSRO.

• Analogia: Imagine uma escola onde os alunos (robôs) lutam uns contra os outros em uma arena.
  1. Um aluno tenta vencer o atual campeão.
  2. Se ele vencer, ele entra na lista de "campeões".
  3. O próximo aluno tenta vencer a média de todos os campeões atuais.
  4. Isso cria uma "hierarquia cognitiva": os robôs aprendem a lidar com estratégias simples, depois médias, e finalmente com estratégias muito complexas.

Dentro dessa escola, eles usaram uma ideia da Teoria do Bargaining (Negociação) chamada Solução de Nash. Em vez de apenas tentar ganhar o máximo possível (o que pode destruir a relação), o robô aprende a buscar um "acordo justo" onde ambos ganham, similar a como humanos negociam para não brigar.

4. O Resultado: Robôs que Parecem Humanos

Eles testaram isso em um jogo chamado "Deal or No Deal" (Negocie ou Não Negocie), onde dois jogadores dividem itens com valores diferentes para cada um.

• O Teste: Humanos reais jogaram contra esses robôs.
• A Descoberta: Os robôs treinados com esse método (especialmente o que buscava "justiça" e "bem-estar social") negociaram tão bem quanto humanos negociando entre si.
  • Eles não eram apenas gananciosos.
  • Eles conseguiam prever o que o humano queria (usando a "imaginação" do modelo generativo).
  • Eles chegavam a acordos que deixavam ambos felizes, alcançando o mesmo nível de eficiência e satisfação que duas pessoas reais teriam.

Resumo em uma frase

Os cientistas criaram um robô que aprende a negociar jogando contra versões de si mesmo, usa sua imaginação (IA generativa) para adivinhar o que o oponente está pensando quando não tem todas as informações, e usa lógica matemática de justiça para fechar acordos que agradam a todos, funcionando tão bem quanto um humano na vida real.

É como ter um parceiro de negociação que é ao mesmo tempo um gênio do xadrez, um psicólogo que entende o que você quer e um diplomata que busca o melhor para todos.

Resumo técnico

Resumo Técnico: Modelagem de Oponentes Teórico-Jogos com Aprendizado por Reforço Profundo, Busca e Modelos Generativos

1. O Problema

A modelagem de oponentes em ambientes multiagente de informação imperfeita enfrenta dois desafios principais:

1. Dependência de Heurísticas: Métodos existentes frequentemente exigem heurísticas específicas do domínio para construir modelos de oponentes, o que dificulta a transferência para novos domínios onde dados ou regras humanas não estão disponíveis.
2. Escalabilidade em Informação Imperfeita: Mesmo quando um modelo de oponente existe, calcular uma "melhor resposta" (best response) em jogos de grande escala com informação imperfeita é computacionalmente intratável. Isso ocorre porque calcular a distribuição posterior sobre os estados do mundo (o que o oponente sabe ou possui) é extremamente caro, especialmente em espaços de crença vastos.

O objetivo deste trabalho é criar um regime de treinamento escalável e genérico que permita a agentes de IA aprenderem a modelar oponentes e reagir a eles sem depender de conhecimento prévio específico do domínio, utilizando apenas raciocínio teórico-jogos e aprendizado por reforço.

2. Metodologia

Os autores propõem uma arquitetura unificada que combina três pilares principais:

A. Generative Best Response (GenBR)
O núcleo da contribuição é o GenBR, um algoritmo de melhor resposta que estende o estilo AlphaZero (MCTS + RL) para jogos de soma geral com informação imperfeita.

• Rede PVGN (Policy-Value-and-Generative): Ao contrário do AlphaZero tradicional, o GenBR utiliza três redes neurais:
  1. Política ($p$): Seleciona ações.
  2. Valor ($v$): Estima o retorno esperado.
  3. Generativa ($g$): Um modelo profundo que amostra estados do mundo (histórias ocultas) a partir do estado de informação atual.
• Busca com Amostragem Generativa: Durante a busca MCTS (Monte-Carlo Tree Search), em vez de calcular explicitamente a distribuição posterior sobre todos os estados possíveis (o que é impossível em grandes espaços), o modelo generativo $g$ amostra diretamente estados do mundo plausíveis na raiz da árvore de busca. Isso permite que o agente planeje e infera o estado ambiental e as estratégias dos oponentes durante a tomada de decisão online.
• Aprendizado Online: O agente atualiza continuamente seu modelo de oponente online usando inferência bayesiana enquanto joga, refinando a distribuição sobre as estratégias dos oponentes com base nas ações observadas.

B. PSRO (Policy Space Response Oracles)
O GenBR é integrado como o "oráculo" dentro do framework PSRO.

• O PSRO constrói iterativamente um conjunto de estratégias (políticas) para cada jogador.
• Em cada iteração, o PSRO calcula uma melhor resposta contra uma mistura de oponentes (modelo offline) e adiciona essa nova estratégia ao conjunto.
• Isso cria uma hierarquia cognitiva de estratégias racionalizáveis, permitindo que o agente aprenda a explorar fraquezas em diferentes tipos de oponentes.

C. Soluções Meta-Estratégicas Baseadas em Teoria de Barganha
Para resolver o jogo empírico gerado pelo PSRO (escolher qual mistura de estratégias usar como alvo), os autores introduzem novos solucionadores baseados na Teoria de Barganha de Nash:

• Nash Bargaining Solution (NBS): Em vez de apenas buscar equilíbrio de Nash (que pode ser ineficiente em jogos cooperativos), o método maximiza o produto de Nash (Nash product), buscando resultados Pareto-ótimos que equilibrem os ganhos de todos os jogadores.
• Eles propõem um algoritmo de ascensão de gradiente projetado para otimizar o logaritmo do produto de Nash, garantindo convergência mesmo em jogos de soma geral complexos.

3. Principais Contribuições

1. GenBR: Um novo método de busca que integra MCTS de Informação Set (IS-MCTS) com um modelo generativo profundo. Isso permite escalabilidade em domínios de informação imperfeita onde métodos anteriores (como filtragem de partículas) falham.
2. MSS Baseados em Barganha: Introdução de solucionadores de meta-estratégia (MSS) no PSRO baseados na solução de Nash Bargaining, permitindo a descoberta de perfis de oponentes próximos à fronteira de Pareto, em vez de apenas equilíbrios competitivos.
3. Validação com Humanos: Demonstração empírica de que agentes treinados com essa abordagem podem negociar com humanos de forma tão eficiente quanto humanos negociando entre si, alcançando alto bem-estar social e pontuações de barganha de Nash.

4. Resultados Experimentais

Os experimentos foram conduzidos em dois jogos principais: Colored Trails (negociação em grade) e Deal or No Deal (DoND) (negociação bilateral com informação imperfeita).

• Desempenho do GenBR:
  • Em DoND, o uso de busca com modelagem generativa superou significativamente o aprendizado por reforço puro (DQN) e métodos sem busca.
  • O agente aprendeu a aproximar a posteriori do estado do mundo e das preferências do oponente, alcançando retornos esperados muito mais altos contra oponentes fortes (como DQN treinado em auto-jogo) do que métodos baselines.
• Comparação com Humanos (Estudo Comportamental):
  • Foram realizados testes com 346 participantes humanos em DoND.
  • Bem-estar Social: O agente "Fair" (mais justo), treinado com NBS e valores de retropropagação baseados no produto de utilidade, alcançou um bem-estar social combinado (humano + agente) comparável ao de humanos jogando contra humanos.
  • Pontuação de Nash: O agente "Fair" obteve a maior pontuação de Nash Bargaining, indicando que conseguiu negociar acordos eficientes e justos.
  • Adaptabilidade: Diferente de agentes puramente competitivos que exploram humanos (reduzindo o ganho humano para maximizar o próprio), os agentes baseados em PSRO/NBS foram adaptáveis, mantendo a cooperação e a justiça.

5. Significância e Impacto

Este trabalho representa um avanço significativo na inteligência artificial para sistemas multiagente:

• Generalização: Demonstra que é possível criar agentes que modelam oponentes e planejam em ambientes complexos de informação imperfeita sem depender de regras manuais ou dados humanos prévios.
• Aplicações Práticas: A metodologia é aplicável a cenários do mundo real como negociação automatizada, leilões, cibersegurança e robótica de armazém, onde a interação é de soma geral e a informação é parcial.
• Ética e Alinhamento de Valores: Ao incorporar conceitos de teoria de barganha (NBS), o trabalho mostra como alinhar agentes de IA para comportamentos cooperativos e justos, mitigando riscos de comportamentos exploratórios que poderiam prejudicar a eficiência do mercado ou a experiência do usuário.

Em resumo, o artigo propõe uma arquitetura robusta que une a capacidade de generalização do Deep RL, o poder de raciocínio da busca MCTS e a modelagem probabilística de estados ocultos, resultando em agentes capazes de negociar e competir de forma eficaz e socialmente desejável contra humanos e outros agentes.