An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games

Resumo Técnico: Abordagem de Aprendizado Online para Jogos Lineares Quadráticos de Soma Zero com Dois Jogadores

1. Problema e Contexto

O artigo aborda o desafio de controlar sistemas dinâmicos lineares em um cenário de jogo de soma zero com dois jogadores, onde a dinâmica do sistema é desconhecida.

• Cenário: Dois agentes (jogadores) interagem estrategicamente através de um processo dinâmico compartilhado. O Jogador 1 busca minimizar um custo, enquanto o Jogador 2 busca maximizá-lo (ou minimizar o custo do oponente).
• Desafio Principal: Diferente do controle ótimo clássico (LQR) de agente único, onde a estabilidade é garantida pela estrutura do problema, em jogos de soma zero com dinâmica desconhecida, os estratégias dos jogadores são acopladas e adversárias. O grande desafio é aprender as políticas de equilíbrio (Nash) online a partir de dados observados, garantindo simultaneamente a estabilidade do sistema durante todo o processo de aprendizado e evitando que o algoritmo tente resolver equações de Riccati para modelos que não possuem soluções estáveis.
• Métrica de Desempenho: O desempenho é medido pelo arrependimento (regret), que quantifica a diferença entre o custo acumulado pelo algoritmo de aprendizado e o custo ótimo teórico (equilíbrio de Nash) ao longo do tempo. O objetivo é alcançar um crescimento sublinear do arrependimento.

2. Metodologia Proposta

Os autores desenvolvem um algoritmo de aprendizado online certificado que combina estimativa de parâmetros, seleção de modelos e controle adaptativo. O método segue os seguintes passos principais:

• Estimativa de Parâmetros (Ridge Regression):

  • Os parâmetros do sistema ($A, B_1, B_2$) são estimados a cada episódio usando mínimos quadrados regularizados (Ridge Regression) sobre os dados de estado e entrada observados.
  • É construído um conjunto de confiança de alta probabilidade (elipsoide) ao redor da estimativa, garantindo que o parâmetro verdadeiro esteja contido nele com alta probabilidade.

• Seleção de Modelo Surrogado Certificado (Certified Surrogate Selection):

  • Um problema crítico é que a estimativa bruta ($\hat{\theta}_k$) pode não garantir que a Equação Algébrica de Riccati Generalizada (GARE) tenha uma solução estabilizante (ponto de sela).
  • Para resolver isso, o algoritmo introduz um passo de contração (shrinkage). Ele busca um modelo "surrogado" ($\tilde{\theta}_k$) que seja uma combinação convexa entre o modelo anterior certificado e a nova estimativa bruta.
  • Este modelo surrogado é selecionado para permanecer dentro do conjunto de confiança e satisfazer margens de regularidade explícitas (garantindo que a GARE seja solúvel e que o sistema em malha fechada seja estável).

• Atualização de Controle e Exploração:

  • Com o modelo surrogado certificado, resolve-se a GARE para obter os ganhos de feedback ótimos ($K, L$).
  • O controle é aplicado com sinais de exploração (ruído injetado) para garantir a excitação persistente, necessária para a convergência da estimativa.
  • As atualizações do modelo ocorrem apenas quando a matriz de informação cresce significativamente (regra de "doubling trick"), evitando re-estimativas desnecessárias.

3. Contribuições Principais

1. Algoritmo Certificado: Desenvolvimento de um algoritmo de aprendizado online com garantias teóricas de estabilidade para jogos de soma zero com dinâmica desconhecida.
2. Análise de Regret Sublinear: Estabelecimento de um limite superior de arrependimento (regret bound) da ordem de $O(\sqrt{T})$. Isso prova que o algoritmo aprende eficientemente e converge para o desempenho ótimo a longo prazo.
3. Mecanismo de Regularidade: Proposição de um método de seleção de modelo surrogado que garante que a GARE permaneça solúvel e estável em cada passo de atualização, superando a instabilidade comum em métodos de equivalência de certeza direta.
4. Análise de Perturbação: Demonstração de que pequenos erros de estimação de parâmetros induzem perturbações proporcionais e limitadas nas soluções da equação de Riccati e nos ganhos de feedback.

4. Resultados e Simulações

Os autores validaram a abordagem através de simulações numéricas em um sistema de dimensão 3:

• Convergência de Parâmetros: Os erros de estimação dos parâmetros do sistema e dos ganhos de feedback ($K$ e $L$) diminuem consistentemente ao longo do tempo, convergindo para os valores verdadeiros.
• Eficácia do Modelo Surrogado: As simulações mostram uma clara distinção entre o estimador bruto e o modelo surrogado certificado, demonstrando que o passo de contração é necessário para manter a estabilidade e a solvabilidade da GARE.
• Comportamento do Regret: O arrependimento acumulado, quando normalizado por $\sqrt{T}$, permanece limitado e estabiliza, confirmando empiricamente o limite teórico $O(\sqrt{T})$ estabelecido no Teorema 2.

5. Significado e Impacto

Este trabalho é significativo porque preenche uma lacuna na literatura de aprendizado por reforço e controle adaptativo para sistemas multiagente competitivos.

• Segurança Crítica: Ao garantir a estabilidade em cada passo de aprendizado, o método é aplicável a domínios onde falhas temporárias são inaceitáveis, como coordenação de robôs, direção autônoma e aplicações de controle crítico em segurança.
• Fundamentação Teórica: O artigo fornece uma estrutura rigorosa para lidar com a complexidade de jogos de soma zero (onde a estabilidade não é automática como no LQR) em cenários de dados desconhecidos.
• Futuro: O trabalho abre caminho para extensões em jogos parcialmente observados, cenários com múltiplos jogadores e sistemas com dinâmica variante no tempo.

Em resumo, o artigo propõe uma solução robusta e teoricamente fundamentada para aprender estratégias de equilíbrio em jogos dinâmicos adversários sem conhecimento prévio do modelo, garantindo estabilidade e eficiência de aprendizado.