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

Titolo: Un Approccio di Apprendimento Online per Giochi Lineari-Quadratici a Somma Zero a Due Giocatori

1. Definizione del Problema

Il paper affronta il problema del controllo ottimo in un contesto di giochi dinamici a somma zero a due giocatori con dinamiche di sistema sconosciute.

• Modello: Si considera un sistema lineare discreto $x_{t+1} = A x_t + B_1 u_t + B_2 v_t + w_t$, dove $u_t$ e $v_t$ sono gli input di controllo dei due giocatori (uno minimizza il costo, l'altro lo massimizza). Le matrici $A, B_1, B_2$ sono sconosciute.
• Obiettivo: I giocatori devono apprendere online le strategie di feedback ottimali (equilibrio di Nash) basandosi esclusivamente sui dati osservati, senza conoscere il modello esatto.
• Metrica di Performance: L'efficacia dell'algoritmo è misurata attraverso il regret cumulativo (Regret), definito come la differenza tra il costo totale sostenuto dall'algoritmo di apprendimento e il costo ottimo asintotico (valore del gioco) che si otterrebbe con dinamiche note. L'obiettivo è dimostrare una crescita sublineare del regret, ovvero $O(\sqrt{T})$.
• Sfida Principale: A differenza del controllo ottimo a singolo agente (LQR), in questo scenario le strategie dei due giocatori sono accoppiate attraverso la struttura dell'equilibrio. Inoltre, l'apprendimento deve garantire la stabilità del sistema durante tutto il processo, evitando che le stime temporanee portino a soluzioni instabili o non ammissibili per le equazioni di Riccati.

2. Metodologia Proposta

Gli autori sviluppano un algoritmo di apprendimento online certificato (Algorithm 1) che combina identificazione del sistema, costruzione di insiemi di confidenza e selezione di modelli surrogati.

A. Stima dei Parametri e Insiemi di Confidenza

• Viene utilizzata la regressione ridge per stimare i parametri del sistema $\Theta = [A, B_1, B_2]$ dai dati di stato e input.
• Viene costruita una ellissoide di confidenza ad alta probabilità ($C_k(\delta)$) attorno alla stima $\hat{\theta}_k$. Questo insieme garantisce che il vero parametro $\theta^*$ si trovi all'interno della regione con probabilità $1-\delta$.

B. Selezione Certificata del Modello Surrogato (Key Innovation)

Un problema critico è che la stima grezza $\hat{\theta}_k$ potrebbe non soddisfare le condizioni di regolarità necessarie per la risoluzione dell'Equazione di Riccati Algebrica Generalizzata (GARE), portando a instabilità.

• Shrinkage (Ridimensionamento): L'algoritmo introduce un passo di "shrinking" (contrazione). Invece di usare direttamente $\hat{\theta}_k$, cerca un modello surrogato $\tilde{\theta}_k$ lungo il segmento che congiunge la stima precedente certificata $\tilde{\theta}_{k-1}$ e la nuova stima $\hat{\theta}_k$.
• Vincoli di Regolarità: Il modello surrogato $\tilde{\theta}_k$ viene selezionato in modo tale da:
  1. Rimanere all'interno dell'insieme di confidenza $C_k(\delta)$.
  2. Soddisfare margini di regolarità espliciti: garantire che la GARE ammetta una soluzione stabilizzante, che il margine di stabilità sia positivo ($R_v - B_2^T P B_2 \succ 0$) e che la matrice del sistema in anello chiuso sia Schur-stabile.
• Questo approccio garantisce che ogni aggiornamento della politica sia certificato come stabile e ammissibile.

C. Aggiornamento della Politica e Esplorazione

• Una volta ottenuto il modello surrogato $\tilde{\theta}_k$, si risolve la GARE per ottenere i guadagni di feedback ottimali $(K_k, L_k)$.
• Vengono iniettati segnali di esplorazione ($\eta_t, \zeta_t$) per garantire la condizione di eccitazione persistente necessaria per la convergenza della stima.
• Gli aggiornamenti della politica avvengono solo quando la matrice di informazione $V_t$ cresce sufficientemente (regola del "doubling trick"), limitando la frequenza degli aggiornamenti e riducendo il costo computazionale.

3. Contributi Chiave

1. Algoritmo Certificato: Sviluppo del primo algoritmo di apprendimento online certificato per giochi a somma zero LQ con dinamiche sconosciute, che garantisce la stabilità durante tutto il processo di apprendimento.
2. Analisi del Regret: Dimostrazione di un limite superiore sublineare per il regret, specificamente $O(\sqrt{T})$. La dimostrazione scompone il regret in tre termini:
   • Costo transitorio (dovuto agli aggiornamenti).
   • Costo di esplorazione.
   • Gap della politica (dovuto all'errore di stima).
3. Stabilità della GARE: Introduzione di un meccanismo di selezione del modello surrogato che garantisce che l'equazione di Riccati sia risolvibile e che la soluzione sia stabilizzante ad ogni iterazione, superando il problema dell'instabilità delle stime grezze.
4. Analisi di Sensibilità: Dimostrazione che piccoli errori di stima del modello inducono perturbazioni proporzionalmente piccole nella soluzione di Riccati e nei guadagni di equilibrio (Lipschitz continuity).

4. Risultati Sperimentali

Gli autori hanno validato l'approccio attraverso simulazioni numeriche su un sistema 3D:

• Convergenza dei Parametri: Gli errori di stima dei parametri ($\|\tilde{\theta}_k - \theta^*\|$) e dei guadagni di feedback ($\|K_k - K^*\|$, $\|L_k - L^*\|$) diminuiscono nel tempo, avvicinandosi ai valori veri.
• Ruolo dello Shrinkage: Il confronto tra l'errore della stima grezza ($\hat{\theta}_k$) e quello del modello surrogato certificato ($\tilde{\theta}_k$) mostra un divario visibile, confermando che il passo di contrazione seleziona attivamente modelli più conservativi per garantire la stabilità.
• Comportamento del Regret: Il regret cumulativo normalizzato ($\text{Regret}/\sqrt{T}$) rimane limitato e si stabilizza, confermando empiricamente il risultato teorico $O(\sqrt{T})$.

5. Significato e Implicazioni

Questo lavoro è significativo perché colma un vuoto nella letteratura sul controllo adattativo per sistemi multi-agente competitivi.

• Sicurezza e Affidabilità: In applicazioni critiche come la sicurezza informatica, la guida autonoma o il coordinamento robotico, è fondamentale che il sistema non diventi instabile durante la fase di apprendimento. Il metodo proposto offre garanzie matematiche su questo aspetto.
• Teoria dei Giochi e Controllo: Estende i risultati noti sull'apprendimento per il controllo ottimo a singolo agente (LQR) a scenari competitivi più complessi, gestendo l'accoppiamento strategico e l'adversarialità.
• Direzioni Future: Il lavoro apre la strada a ricerche su sistemi parzialmente osservabili, giochi a più giocatori e sistemi a tempo variante, suggerendo anche la necessità di rilassare l'assunzione di eccitazione persistente.

In sintesi, il paper presenta un framework robusto che combina teoria dell'apprendimento statistico e teoria del controllo ottimo per risolvere giochi dinamici complessi in condizioni di incertezza, garantendo stabilità e convergenza.