Resumo Técnico: Aprendizado Heterogêneo em Jogos Estocásticos de Soma Zero com Informação Incompleta

Definição do Problema

O artigo aborda o desafio do aprendizado em ambientes dinâmicos e descentralizados onde os agentes (jogadores) operam com informação incompleta. Especificamente, os autores consideram um jogo estocástico de soma zero entre duas pessoas onde:

• Os jogadores não conhecem suas próprias funções de utilidade (as entradas da matriz de utilidade).
• Os jogadores não têm conhecimento das ações passadas de seus oponentes.
• O espaço de estados e as leis de transição são desconhecidos para os jogadores.
• A comunicação entre os agentes é impraticável.

Em tais configurações, algoritmos de aprendizado padrão, como o jogo fictício (fictitious play) ou a dinâmica de melhor resposta (best response dynamics), que dependem da observação do histórico de ações do oponente, são inaplicáveis. Além disso, os algoritmos de aprendizado por reforço (RL) existentes frequentemente focam exclusivamente no reforço de estratégia ou no reforço de recompensa (payoff), em vez de acoplá-los. A questão central é como projetar esquemas de aprendizado totalmente distribuídos que exijam o mínimo de informação e recursos, permitindo simultaneamente que os agentes aprendam estratégias ótimas e estimem recompensas ótimas.

Metodologia

Os autores propõem uma classe de esquemas de aprendizado heterogêneos onde os agentes podem adotar padrões (algoritmos) de aprendizado distintos e operar em diferentes taxas de aprendizado (escalas de tempo).

Modelo de Jogo

O estudo utiliza um modelo de jogo estocástico de duas pessoas $\Xi = \langle S, A_1, A_2, \{U(s, .)\}_{s \in S} \rangle$.

• $S$: Conjunto de estados (desconhecidos para os jogadores, variáveis aleatórias i.i.d.).
• $A_1, A_2$: Conjuntos de ações finitas.
• $U$: Função de utilidade onde o Jogador 1 (P1) maximiza e o Jogador 2 (P2) minimiza.
• Os jogadores utilizam estratégias mistas $f_t$ e $g_t$ no tempo $t$.

Algoritmos de Aprendizado (CODIPAS-RL)

A metodologia central é a estrutura de Aprendizado de Reforço de Recompensa e Estratégia Totalmente Distribuído e Acoplado (CODIPAS-RL). Esta abordagem acopla o aprendizado de recompensas esperadas com o aprendizado de estratégias. Os autores definem cinco algoritmos específicos dentro desta estrutura:

1. CRL0: Um algoritmo combinado básico que atualiza estratégias e recompensas via médias ponderadas de recompensas observadas (semelhante ao Q-learning acoplado com atualizações de estratégia).
2. CRL1: Um algoritmo baseado em Boltzmann-Gibbs onde as atualizações de estratégia seguem uma função soft-max das recompensas médias estimadas.
3. CRL2: Semelhante ao CRL1, mas utiliza uma estratégia imitativa de Boltzmann-Gibbs, ponderando o soft-max pela atual vetor de estratégia.
4. RL2: Um algoritmo padrão de reforço de estratégia (semelhante à dinâmica do replicador) sem o acoplamento explícito de estimativa de recompensa.
5. RL3: Uma versão normalizada do RL2.

Abordagem Analítica

Os autores empregam técnicas de aproximação estocástica para analisar a convergência destes algoritmos de aprendizado de tempo discreto. Eles mapeiam os processos de aprendizado estocástico para seus contrapartes determinísticos de Equações Diferenciais Ordinárias (EDO).

• A análise considera taxas de aprendizado heterogêneas, onde um jogador pode aprender significativamente mais rápido que o outro (ex: $\lambda_{1,t} / \lambda_{2,t} \to 0$).
• As EDOs resultantes mostram-se diferentes das dinâmicas de replicador, melhor resposta, dinâmica de logit e jogo fictício, dependendo da combinação específica de algoritmos e taxas de aprendizado utilizados pelos jogadores.

Principais Contribuições

1. Estrutura de Aprendizado Heterogêneo: O artigo introduz uma estrutura onde os agentes podem adotar diferentes esquemas de aprendizado (ex: um usa CRL1 enquanto o outro usa RL2) e operar em diferentes escalas de tempo.
2. Aprendizado Acoplado de Recompensa-Estratégia: Ao contrário do RL padrão, que frequentemente separa o aprendizado de estratégia e de valor, os algoritmos propostos CODIPAS-RL atualizam simultaneamente os vetores de estratégia e as recompensas médias estimadas sem exigir o conhecimento das ações do oponente.
3. Caracterização por EDO: Os autores derivam as EDOs específicas que regem o comportamento assintótico destes esquemas heterogêneos. Eles demonstram que, quando os jogadores aprendem em velocidades diferentes, a dinâmica do sistema pode ser descrita por um jogador "lento" reagindo à melhor resposta suave do jogador "rápido", ou vice-versa.
4. Convergência para Pontos de Sela $\epsilon$: O artigo estabelece que estas dinâmicas heterogêneas convergem quase certamente para um ponto de sela $\epsilon$ do jogo esperado. À medida que o parâmetro soft-max $\epsilon \to 0$, estes pontos convergem para os verdadeiros pontos de sela.
5. Eliminação de Estratégias Dominadas: Sob o algoritmo CRL1, os autores provam que as estratégias estritamente dominadas são eliminadas a longo prazo.

Resultados

• Convergência: O artigo prova que combinações de CRL1, RL2 e RL3 (ex: CRL1 vs. RL2, CRL1 vs. CRL2) levam à convergência para soluções de ponto de sela em jogos estocásticos de soma zero.
• Separação de Escala de Tempo: Quando um jogador aprende mais rápido que o outro, a trajetória do jogador mais lento converge para uma melhor resposta suave (ou dinâmica do replicador ajustada) em relação à estratégia do jogador rápido.
• Simulação (Aplicação em Jogo de Segurança): Os autores aplicam os algoritmos a um cenário de detecção de intrusão em rede (Atacante vs. Defensor).
  • Cenário: Um jogo $2 \times 2$ com recompensas estocásticas.
  • Caso Homogêneo: Quando ambos os jogadores usam CRL1, as recompensas e estratégias convergem para o valor do jogo (aprox. 2.6) e as estratégias de ponto de sela ($f^*=[0.4, 0.6]$, $g^*=[0.2, 0.8]$), embora a convergência seja lenta.
  • Caso Heterogêneo: Quando o atacante usa CRL1 e o defensor usa RL2, o sistema também converge, demonstrando a robustez da abordagem heterogênea.

Significância e Alegações

O artigo afirma que sua principal contribuição é abordar o grande desafio do aprendizado em ambientes descentralizados com requisitos mínimos de informação. Ao relaxar a suposição de que os jogadores devem observar o histórico de ações de seus oponentes, os algoritmos propostos são mais aplicáveis a cenários reais de redes e segurança, onde tal observação é "implausível e impraticável".

Os autores enfatizam que seu trabalho:

• Fornece uma base teórica para o aprendizado heterogêneo, reconhecendo que agentes em sistemas reais (como atacantes e defensores) possuem diferentes níveis de racionalidade e informação.
• Oferece uma classe de algoritmos que são totalmente distribuídos e exigem apenas observações locais de recompensa.
• Estende a compreensão das dinâmicas de jogo além dos modelos padrão de replicador ou de melhor resposta, mostrando como diferentes taxas de aprendizado e esquemas criam novos comportamentos dinâmicos que ainda convergem para o equilíbrio.

O artigo conclui modestamente, observando que trabalhos futuros envolvem a extensão destes resultados para jogos estocásticos com estados controlados e jogos de soma não nula.