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

Titel: Een Online Leerbenadering voor Twee-Speler Nul-Som Lineair-Kwadratische Spellen

Auteurs: Shanting Wang, Weihao Sun, en Andreas A. Malikopoulos (Cornell University)

1. Probleemstelling

Het artikel adresseert het probleem van het leren van evenwichtsstrategieën in twee-speler nul-som lineair-kwadratische (LQ) spellen waarbij de systeemdynamica onbekend is.

• Context: In cyber-fysische systemen (zoals robotcoördinatie, autonoom rijden en beveiligingskritieke controles) moeten meerdere beslissingsmakers strategisch interageren. Bij nul-som spellen zijn de doelen van de spelers exact tegenovergesteld (de ene minimaliseert de kosten, de andere maximaliseert ze).
• Uitdaging: Wanneer de matrices die de dynamica beschrijven ($A, B_1, B_2$) onbekend zijn, moeten spelers hun feedbackstrategieën leren op basis van waargenomen data. Dit is complexer dan het klassieke single-agent LQR-probleem omdat:
  1. De strategieën van de twee spelers gekoppeld zijn via de evenwichtsstructuur.
  2. De interactie antagonistisch is.
  3. Stabiliteit van het systeem gedurende het hele leerproces moet worden gegarandeerd, wat essentieel is voor de oplossing van de Generalized Algebraic Riccati-vergelijking (GARE).
• Doel: Ontwikkelen van een online leeralgoritme dat sublineaire regret bereikt, wat betekent dat de cumulatieve prestatieverlies ten opzichte van het optimale evenwicht groeit langzamer dan lineair met de tijd ($O(\sqrt{T})$).

2. Methodologie

De auteurs presenteren een gecertificeerd online leerframework (Algorithm 1) dat bestaat uit drie kerncomponenten:

A. Parameterschatting en Confidentiegebieden

• Ridge-regressie: De onbekende systeemmatrices worden geschat uit waargenomen toestands- en invoerdata ($x_t, u_t, v_t$) met behulp van gestructureerde least-squares schatting (ridge regression).
• Confidentie-ellipsoïde: Er wordt een hoog-probabiliteit confidentiegebied ($C_k(\delta)$) om de geschatte parameters $\hat{\theta}_k$ geconstrueerd. Dit gebied garandeert dat de ware parameter $\theta^*$ met hoge waarschijnlijkheid binnen zit.

B. Gecertificeerde Surrogaatmodel Selectie (Kerninnovatie)

Een direct gebruik van de ruwe schatting $\hat{\theta}_k$ is riskant omdat deze mogelijk buiten het gebied valt waar de GARE een stabiele oplossing heeft (de "regulariteit" is niet gegarandeerd).

• Shrinkage-stap: In plaats van de ruwe schatting te gebruiken, wordt een surrogaatmodel $\tilde{\theta}_k$ geselecteerd.
• Methode: Er wordt een lijnsegment getrokken tussen het vorige gecertificeerde model en de nieuwe schatting. Het algoritme zoekt het punt op dit segment dat nog binnen het confidentiegebied ligt én voldoet aan strikte regulariteitsvoorwaarden (GARE heeft een stabiele oplossing, de matrix is Schur-stabiel, en er is een voldoende stabiliteitsmarge).
• Doel: Dit zorgt ervoor dat elke update van de feedbackwinsten ($K, L$) leidt tot een stabiel systeem, zelfs tijdens het leerproces.

C. Gecertificeerde Certainty-Equivalent Controle

• Op basis van het geselecteerde surrogaatmodel $\tilde{\theta}_k$ wordt de GARE opgelost om de optimale feedbackwinsten $K_k$ en $L_k$ te verkrijgen.
• Verkenning (Exploration): Er worden kleine ruisignalen ($\eta_t, \zeta_t$) toegevoegd aan de besturing om voldoende excitatie te garanderen voor de parameterschatting (persistent excitation).
• Update-frequentie: De parameters worden niet bij elke tijdstap bijgewerkt, maar alleen wanneer de informatie-inhoud (gemeten via de determinant van de ontwerpmatrix) verdubbelt. Dit beperkt het aantal updates tot $O(\log T)$.

3. Belangrijkste Bijdragen

1. Gecertificeerd Algoritme: De ontwikkeling van een online leeralgoritme voor twee-speler nul-som LQ-spellen met onbekende dynamica dat stabiliteit expliciet garandeert via een "surrogaatmodel"-selectie.
2. Regret-Bound: Het bewijzen van een sublineaire regret-bounds van $O(\sqrt{T})$. Dit wordt bereikt door de regret te ontleden in:
   • Transiënte kosten (door updates).
   • Verkenningskosten (door ruisinjectie).
   • Beleidskloof (door schattingsfouten).
3. Lokale Stooringsanalyse: Het tonen aan dat kleine fouten in de parameterschatting leiden tot proportioneel kleine afwijkingen in de Riccati-oplossing en de feedbackwinsten (via de impliciete functiestelling).
4. Numerieke Validatie: Een simulatie die de convergentie van parameterschatting, de stabiliteit van de feedbackwinsten en de sublineaire groei van de regret aantoont.

4. Resultaten

De numerieke simulaties (met een horizon van $T=50.000$) tonen het volgende:

• Parameterschatting: De fout in de geschatte parameters ($\|\tilde{\theta}_k - \theta^*\|$) neemt af naarmate meer data wordt verzameld.
• Feedbackwinsten: De berekende Nash-evenwichtswinsten ($K_k, L_k$) convergeren naar de ware optimale waarden.
• Rol van Shrinkage: Er is een duidelijk verschil tussen de ruwe schatting en het gecertificeerde surrogaatmodel. De "shrinkage"-stap zorgt ervoor dat het gebruikte model conservatiever is, maar wel binnen de stabiliteitsgrenzen blijft.
• Regret: De genormaliseerde regret ($Reg(T)/\sqrt{T}$) blijft begrensd en stabiliseert, wat de theoretische $O(\sqrt{T})$-bound bevestigt.

5. Betekenis en Toekomstperspectief

• Significantie: Dit werk vult een belangrijke lacune op in de literatuur over data-gedreven besturing. Waar eerdere studies zich vaak richtten op single-agent LQR of bekende dynamica, biedt deze paper een oplossing voor adversariele, multi-agent systemen met onbekende dynamica, waarbij stabiliteit niet wordt opgeofferd voor leersnelheid.
• Toekomstige Richtingen: De auteurs suggereren als volgende stappen:
  • Het versoepelen van de aannames over "persistent excitation".
  • Uitbreiding naar gedeeltelijk waargenomen spellen (partially observed games).
  • Toepassing op multi-speler settings (meer dan twee spelers) en tijdvariërende systemen.

Kortom, de paper biedt een robuust theoretisch raamwerk en een praktisch algoritme om complexe, antagonistische besturingsproblemen veilig en efficiënt te leren zonder voorafgaande kennis van het systeemmodel.