Minimax-Optimal Policy Regret in Partially Observable Markov Games

Resumo Técnico: Regret de Política Minimax-Ótima em Jogos de Markov Parcialmente Observáveis

Formulação do Problema
Este artigo aborda a tomada de decisão sequencial em ambientes parcialmente observáveis contra oponentes estratégicos e adaptativos, modelados como Jogos de Markov Parcialmente Observáveis (POMGs). O desafio central reside em aprender a dinâmica latente do mundo a partir de observações parciais enquanto se enfrenta um adversário cujo comportamento se adapta à estratégia do aprendiz. As noções padrão de regret externo são inadequadas neste cenário porque a resposta do ambiente depende das ações passadas do aprendiz, criando dependências contrafatuais. Consequentemente, o artigo adota o regret de política (policy regret) como métrica de desempenho, que compara a recompensa cumulativa do aprendiz contra a melhor política fixa $\pi^*$, assumindo que o adversário teria eventualmente convergido para uma resposta estacionária $R_\infty(\pi^*)$ caso o aprendiz tivesse se comprometido com $\pi^*$ desde o início.

O cenário envolve dois jogadores: um aprendiz e um adversário, ambos operando sob observabilidade parcial. O aprendiz observa sinais $o^A$ e o adversário observa $o^B$, enquanto as transições de estado latente baseiam-se nas ações de ambos os jogadores. Assume-se que o adversário é limitado em memória $m$ (m-memory bounded), o que significa que sua resposta em qualquer episódio depende apenas das políticas do aprendiz nos últimos $m$ episódios.

Metodologia e Estrutura Algorítmica
Os autores propõem um algoritmo de Estimativa de Máxima Verossimilhança (MLE) otimista baseado em épocas (Algoritmo 1) para minimizar o regret de política. A metodologia baseia-se em vários componentes estruturais fundamentais:

1. Decomposição Causal: Uma contribuição teórica central é a decomposição do operador observável $J_{\xi,\pi}^h$ em dois componentes distintos:

   • Um canal do mundo $W_h^\theta$, que depende exclusivamente das dinâmicas do mundo (kernels de transição e emissão) e é independente da resposta do adversário.
   • Um operador de agregação do adversário $G_{\Phi,\pi}^h$, que depende da função de resposta do adversário e da política do aprendiz, mas é independente do parâmetro do mundo $\theta$.
     Esta fatoração permite que o algoritmo separe a estimativa das dinâmicas do mundo do controle das respostas do adversário.

2. Suposições Estruturais:

   • Adversário Posterior-Lipschitz: A resposta do adversário varia suavemente com a política do aprendiz. Crucialmente, esta suavidade é definida em relação a uma medida de referência fixa $\mu_{ref}$ (independente da estratégia real do adversário) para evitar dependências circulares na definição.
   • Revelação Fraca Multi-etapa (Multi-step Weak Revealing): As observações são suficientemente informativas sobre os estados latentes ao longo de uma janela de $\kappa$ passos, garantindo que discrepâncias nas dinâmicas do mundo sejam detectáveis.
   • Dimensão Eluder: A complexidade da classe conjunta de modelos mundo-adversário é medida pela dimensão Eluder agregada uniforme ($d_E$).

3. Execução Baseada em Épocas: O algoritmo divide o tempo em épocas de crescimento geométrico ($T_e = 2^e$). Dentro de cada época:

   • Uma única política $\pi_e$ é selecionada otimisticamente de um conjunto de confiança construído cumulativamente a partir de todos os dados passados.
   • Uma fase de aquecimento (warm-up phase) de $m-1$ episódios permite que o adversário de memória $m$ se estabilize em sua resposta estacionária para a política atual.
   • A política é executada por $T_e$ episódios de coleta de dados.
     Esta estrutura garante que o aprendiz implemente apenas $O(\log T)$ políticas distintas ao longo de $T$ episódios, o que é crítico para controlar o custo de comparar as respostas do adversário entre diferentes políticas.

Resultados Principais
O artigo estabelece um limite superior minimax-ótimo para o regret de política e um limite inferior correspondente.

• Limite Superior: Sob as suposições declaradas, o algoritmo alcança um regret de política de:
  $$PR(T) \leq C \left( H \sqrt{\bar{\beta}_T \cdot d_E \cdot T} + mH \log T \right)$$
  onde $\bar{\beta}_T = H\beta_T + H^2 \log T$. O termo $H^2 \log T$ representa o "custo de transporte" de comparar as respostas do adversário através das $O(\log T)$ políticas distintas implementadas. A dependência de $\sqrt{T}$ é alcançada pela estrutura de época geométrica; implementar $O(\sqrt{T})$ políticas (como no loteamento plano/flat batching) resultaria em um regret de $T^{3/4}$ devido ao acúmulo de custos de transporte.

• Limite Inferior: Os autores provam um limite inferior de $\Omega(\sqrt{d_E T})$ para qualquer algoritmo, mesmo em POMGs totalmente reveladores com adversários sem memória. Isso confirma que a dependência de $\sqrt{T}$ e $d_E$ no limite superior é ótima, exceto por fatores dependentes do problema ou logarítmicos.

• Extensões: O framework é estendido para lidar com:

  • Horizontes Desconhecidos: O algoritmo se adapta a $T$ desconhecido sem modificações.
  • Adversários de Memória Decrescente (Fading Memory): Os resultados sustentam-se para adversários com memória que decai geometricamente, com o custo de aquecimento escalando como $O(\frac{H \log^2 T}{1-\gamma})$.
  • Configurações Tabulares: Limites explícitos são derivados em termos dos tamanhos dos espaços de estado, ação e observação.

Significância e Alegações
O artigo afirma fornecer um tratamento teórico completo da minimização do regret de política em POMGs contra adversários adaptativos. Sua principal significância reside em demonstrar que o aprendizado eficiente (com regret de $\sqrt{T}$) é possível neste cenário complexo, desde que a resposta do adversário seja suave (Posterior-Lipschitz) e as observações sejam fracamente reveladoras.

Os autores destacam duas inovações técnicas específicas que permitem este resultado:

1. Formulação Não Circular: Ao definir a condição Posterior-Lipschitz em relação a uma medida de referência fixa, eles evitam os problemas de circularidade presentes em formulações anteriores onde a métrica de suavidade dependia do adversário estar sendo restringido.
2. Custo de Transporte Logarítmico: Ao restringir o aprendiz a $O(\log T)$ políticas distintas via estrutura baseada em épocas, eles garantem que o custo de transportar erros de resposta do adversário permaneça logarítmico, preservando a taxa ótima de $\sqrt{T}$. Isso contrasta com abordagens de loteamento plano (flat-batching), que, segundo os autores, levam a taxas subótimas de $T^{3/4}$ devido ao crescimento polinomial nos custos de transporte.

O trabalho é apresentado como um passo fundamental para o design de algoritmos de aprendizado com garantias de desempenho confiáveis em ambientes multiagentes onde os agentes são simultaneamente parcialmente observáveis e estrategicamente adaptativos. Os autores observam que, embora as garantias estatísticas tenham sido estabelecidas, a tratabilidade computacional do passo de planejamento otimista permanece uma direção aberta para trabalhos futuros, particularmente para classes de modelos gerais.