Resumo Técnico: Oráculos de Resposta de Espaço de Políticas com Eficiência de Amostragem via Melhor Resposta de Experiência Conjunta

1. Definição do Problema

O aprendizado por reforço multiagente (MARL) oferece uma alternativa escalável à análise exata da teoria dos jogos, mas enfrenta dois desafios primários: a não-estacionariedade (onde o aprendizado independente causa o deslocamento do ambiente conforme os agentes atualizam) e a necessidade de manter populações de estratégias diversas para capturar interações não-transitivas. O framework Policy Space Response Oracles (PSRO) aborda esses problemas expandindo iterativamente um jogo restrito com melhores respostas (BRs) aproximadas.

No entanto, o PSRO padrão sofre de custos computacionais e de amostragem proibitivos. Em cada iteração, cada agente deve computar independentemente uma melhor resposta contra o perfil de meta-estratégia atual dos outros agentes. Isso exige resolver tantos problemas de aprendizado por reforço (RL) quanto o número de agentes, cada um exigindo a simulação completa dos agentes restantes. Em domínios com muitos jogadores ou simuladores caros, essa estrutura de treinamento por agente torna o PSRO impraticável.

2. Metodologia

Conceito Central: Melhor Resposta de Experiência Conjunta (JBR)

Os autores propõem a Melhor Resposta de Experiência Conjunta (Joint Experience Best Response - JBR), uma modificação do PSRO que reutiliza dados de interação entre todos os agentes. Em vez de treinar a melhor resposta de cada agente independentemente, o JBR:

1. Coleta trajetórias uma única vez sob o perfil de meta-estratégia atual $\sigma = (\sigma_j)_{j \in N}$.
2. Constrói um conjunto de dados conjunto compartilhado $\mathcal{D}_\sigma$ contendo transições $(s_t, a_{1,t}, \dots, a_{n,t}, r_{1,t}, \dots, r_{n,t}, s_{t+1})$.
3. Computa as melhores respostas para todos os agentes simultaneamente a partir deste único conjunto de dados.

Isso converte a computação da melhor resposta de um problema de RL online em um problema de RL offline, onde as políticas são otimizadas a partir de um conjunto de dados fixo. Embora isso melhore drasticamente a eficiência de amostragem, introduz um viés de deslocamento de distribuição porque o conjunto de dados é gerado sob a meta-estratégia atual, que pode não cobrir as regiões de estado-ação relevantes para a verdadeira melhor resposta.

Abordagem do Viés de RL Offline

Para mitigar as limitações do RL offline (especificamente o deslocamento de distribuição), o artigo introduz três remédios complementares:

1. JBR Conservador (Melhoria de Política Segura):

   • Impõe uma restrição onde a política aprendida $\pi_i$ só se desvia da meta-estratégia base $\sigma_i$ em pares estado-ação suficientemente cobertos pelo conjunto de dados (contagem $N_D(s, a_i) \ge N^\wedge$).
   • Em regiões subamostradas, a política retorna à $\sigma_i$, garantindo que o desempenho não degrade abaixo da linha de base.
   • Limitação: Embora seja seguro, é excessivamente cauteloso e limita a capacidade de encontrar melhorias significativas em comparação com as BRs independentes.

2. JBR Aumentado por Exploração:

   • Perturba o processo de coleta de dados para melhorar a cobertura. Em vez de agir estritamente de acordo com $\sigma$, os agentes seguem uma meta-estratégia $\delta$-perturbada:
     $$\tilde{\sigma}_j(a_j|s) = (1-\delta)\sigma_j(a_j|s) + \delta\nu_j(a_j|s)$$
   • Duas estratégias de exploração são propostas:
     • $\delta$-Aleatória ($\delta$-R): $\nu_j$ é uma política aleatória uniforme.
     • $\delta$-Direcionada ($\delta$-T): $\nu_j$ é a atual candidata à melhor resposta ($\pi^{BR,cur}_j$). Isso direciona a exploração para trajetórias promissoras, atuando efetivamente como uma forma de modelagem de oponente.
   • Garantia Teórica: O artigo prova que para jogos de soma zero de dois jogadores finitos, se os agentes computarem uma $\epsilon$-melhor resposta para a estratégia perturbada $\tilde{\sigma}$, a meta-estratégia resultante é um equilíbrio de Nash $(\epsilon + 2R\delta)$ do jogo original (onde $R$ é o intervalo de payoff).

3. Melhor Resposta Híbrida (HBR):

   • Alterna entre JBR e a Melhor Resposta Independente (IBR) padrão.
   • Na maioria das iterações, o JBR é usado para eficiência. A cada $k$-ésima iteração, os agentes realizam uma atualização de IBR padrão para corrigir erros de aproximação.
   • O objetivo é combinar a eficiência de amostragem do JBR com a precisão do IBR.

3. Principais Contribuições

1. Framework JBR: Introdução do Joint Experience Best Response, uma modificação direta ao PSRO que reutiliza trajetórias compartilhadas para computar as melhores respostas para todos os agentes simultaneamente, melhorando significativamente a eficiência de amostragem.
2. Remédios para o Viés Offline: Identificação das limitações de RL offline inerentes ao JBR e a proposta/avaliação de três remédios específicos: JBR Conservador, JBR Aumentado por Exploração (com garantias de convergência teórica) e BR Híbrida.
3. Estudo Empírico Abrangente: Uma comparação rigorosa das variantes de JBR contra o PSRO padrão (Melhor Resposta Independente) e baselines de MARL mainstream (Aprendizado Independente e CTDE) em ambientes discretos (pôquer) e contínuos (partículas).

4. Resultados Experimentais

Ambientes

• Discretos: Kuhn Poker (espaço de estados pequeno e totalmente coberto) e Leduc Poker (espaço de estados maior, informação imperfeita).
• Contínuos: Simple Tag, Simple Adversary e Simple Push (ambientes de partículas multiagentes).

Descobertas

• Viabilidade em Domínios Simples: No Kuhn Poker, onde o espaço de estados é pequeno e totalmente coberto, o JBR iguala o comportamento de convergência do PSRO padrão, confirmando a viabilidade sob condições de boa amostragem.
• Falha do JBR Ingênuo: No Leduc Poker, o JBR ingênuo (sem exploração ou conservadorismo) falha em manter a precisão do equilíbrio devido ao viés de aprendizado offline, estagnando em uma explorabilidade maior comparado ao PS de PSRO.
• Efetividade das Variantes:
  • JBR Conservador é estável, mas performa mal comparado ao PSRO devido ao excesso de cautela.
  • JBR Aumentado por Exploração ($\delta$-R) mostra ganhos moderados, mas carece de direção.
  • JBR Aumentado por Exploração ($\delta$-T) alcança o melhor equilíbrio, atingindo precisão de equilíbrio próxima ao PSRO com significativamente menos amostras. A exploração direcionada antecipa as atualizações dos oponentes, levando a uma convergência inicial mais rápida.
  • Melhor Resposta Híbrida (HBR-PSRO) fecha a lacuna de precisão restante para o PSRO com apenas um aumento modesto no custo de amostragem.
• Eficiência de Amostragem: O JBR-PSRO-$\delta$T atinge um NashConv próximo ao do PSRO com aproximadamente metade dos episódios de melhor resposta totais exigidos pelo PSRO padrão.
• Comparação com MARL: Em todos os ambientes, os métodos baseados em PSRO (incluindo variantes de JBR) superam consistentemente os paradigmas de MARL padrão (Aprendizado Independente e CTDE) em termos de robustez estratégica e precisão de equilíbrio.

5. Significância e Alegações

O artigo afirma que o JBR torna o PSRO substancialmente mais prático para aprendizado estratégico em larga escala, preservando a robustez do equilíbrio.

• Escalabilidade: Ao amortizar as interações com o ambiente entre os agentes, o JBR reduz o custo de amostragem da computação da melhor resposta, abordando o principal gargalo do PSRO em cenários de muitos agentes ou simuladores caros.
• Robustez: Os resultados confirmam que o treinamento estrategicamente fundamentado (estilo PSRO) permanece mais robusto do que as abordagens de MARL padrão quando tornado eficiente em amostragem.
• Implantação Prática: As variantes propostas, particularmente JBR-PSRO-$\delta$T e HBR-PSRO, oferecem caminhos viáveis para implantar o PSRO em domínios onde os custos de interação com o ambiente dominam o tempo de execução, sem sacrificar a qualidade dos equilíbrios aprendidos.

Os autores observam que, embora o JBR melhore a eficiência, o PSRO e suas variantes ainda requerem mais iterações e amostras do que os métodos típicos de MARL, e a escalabilidade para domínios contínuos de alta dimensão permanece um desafio para trabalhos futuros.