⚡ electrical engineering

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

This paper proposes an online learning framework for two-player zero-sum linear quadratic games with unknown dynamics that integrates regularized model estimation, confidence sets, and a shrinkage-based surrogate model selection to ensure stabilizing solutions and achieves provable regret bounds.

Original authors: Shanting Wang, Weihao Sun, Andreas A. Malikopoulos

Published 2026-04-06

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Shanting Wang, Weihao Sun, Andreas A. Malikopoulos

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine two drivers trying to navigate a car together, but with a twist: one driver wants to get to the destination as fast as possible (the "Minimizer"), while the other wants to make the trip as slow and bumpy as possible (the "Maximizer"). They are playing a high-stakes game of tug-of-war inside the vehicle.

The problem? They don't know how the car works. They don't know how heavy the engine is, how slippery the tires are, or how the steering responds. They only know that when they turn the wheel or press the gas, the car moves a little bit differently than they expected.

This paper presents a smart, safe way for these two drivers to learn how to drive the car while they are driving it, without crashing.

Here is the breakdown of their strategy, using simple analogies:

1. The Problem: Driving Blindfolded

In the real world, many systems (like self-driving cars, power grids, or robot swarms) involve multiple parties with opposing goals. If the "rules of the road" (the math behind the physics) are unknown, you can't just calculate the perfect move. You have to learn by doing.

But there's a catch: if you guess wrong, the car might spin out of control. In math terms, the system becomes "unstable." The goal is to learn the rules fast enough to win the game, but slowly enough to never crash.

2. The Solution: The "Safe Guess" Strategy

The authors propose a three-step learning loop that happens over and over again:

Step A: The "Notebook" (Data Collection)

Every time the drivers take an action, they write down what happened in a notebook.

Analogy: Imagine a student taking notes in class. "I pressed the gas, and the car went 5 mph." "I turned left, and we drifted right."
They use a method called Ridge Regression to look at all these notes and make their best guess about how the car works. This gives them a "Raw Estimate" of the engine and steering.

Step B: The "Safety Check" (The Certified Surrogate)

Here is the paper's big innovation. The "Raw Estimate" might be mathematically perfect based on the data, but it could be dangerous. It might suggest a steering angle that would flip the car.

Analogy: Imagine your best guess says, "If I turn the wheel 90 degrees, we go straight!" But your gut says, "That sounds like a crash."
So, the algorithm performs a "Shrinkage Step." It takes that risky, raw guess and pulls it back toward a "Safe Zone." It finds a model that is close to the raw guess but is guaranteed to keep the car stable.
They call this the Certified Surrogate Model. It's like a "safe version" of the truth that the drivers can trust to use for the next few minutes.

Step C: The "Game Plan" (Solving the Puzzle)

Once they have this "Safe Model," they solve a complex math puzzle (called the Generalized Algebraic Riccati Equation, or GARE).

Analogy: This is like the drivers sitting down with their safe map and calculating the perfect strategy: "If I do X, and the other guy does Y, we end up here."
They calculate new steering and gas commands (feedback gains) based on this safe map and apply them until they have enough new data to update their notebook again.

3. The "Regret" Score: How Well Did We Do?

In this field, they measure success using a metric called Regret.

Analogy: Imagine you are playing a video game. "Regret" is the difference between your score and the score of a pro player who has known the game's code since birth.
If your regret stays low, you are learning fast. If it keeps growing, you are making mistakes.
The paper proves mathematically that their method ensures the "Regret" grows very slowly (specifically, proportional to the square root of time). This means that as time goes on, the drivers get almost as good as the pro, even though they started with zero knowledge.

4. The Results: The Simulation

The authors tested this on a computer simulation of a 3D system (like a drone or a complex robot).

The Learning Curve: They showed that as time passed, their "Safe Model" got closer and closer to the real physics of the system.
The Safety Gap: They showed that the "Safe Model" was often different from the "Raw Guess," proving that the safety check was actually doing work to prevent instability.
The Score: The "Regret" curve flattened out, proving that the algorithm learned efficiently and didn't crash.

Summary

Think of this paper as a safety manual for learning while playing a dangerous game.

Instead of blindly guessing how a system works, the algorithm:

Gathers data to make a best guess.
Cautiously adjusts that guess to ensure it won't cause a disaster (the "Shrinkage").
Calculates the best move based on that safe guess.
Repeats, getting smarter and safer every time.

It's a way to teach a computer to play a high-stakes game of chess against an opponent, even when the computer doesn't know the rules of the board, without ever getting checkmated.

1. Problem Formulation

The paper addresses the challenge of controlling two-player zero-sum Linear Quadratic (LQ) games where the system dynamics are unknown.

System Model: A discrete-time linear system $x_{t+1} = A x_t + B_1 u_t + B_2 v_t + w_t$ , where $u_t$ and $v_t$ are control inputs for Player 1 (minimizer) and Player 2 (maximizer), respectively. The matrices $A, B_1, B_2$ are unknown.
Objective: Player 1 aims to minimize, and Player 2 aims to maximize, the infinite-horizon average cost function $J(u, v)$ .
Equilibrium: The goal is to find the Nash Equilibrium (NE) strategies, which are linear feedback policies ( $u_t = -K^* x_t, v_t = -L^* x_t$ ) derived from the solution to the Generalized Algebraic Riccati Equation (GARE).
Challenge: Unlike single-agent Linear Quadratic Regulator (LQR) problems, zero-sum games involve coupled strategies and adversarial interactions. Standard online learning methods (like Certainty Equivalence) often fail because the estimated model may not satisfy the stability conditions required to solve the GARE (i.e., the estimated matrices might not admit a stabilizing saddle-point solution).
Performance Metric: The algorithm's performance is measured by Regret, defined as the cumulative difference between the cost incurred by the learning algorithm and the optimal cost under the true dynamics. The goal is to achieve sublinear regret ( $O(\sqrt{T})$ ).

2. Methodology

The authors propose a Certified Online Learning Algorithm (Algorithm 1) that integrates system identification with rigorous stability guarantees. The methodology consists of four key stages:

A. Parameter Estimation with Confidence Sets

Ridge Regression: System parameters $\Theta = [A, B_1, B_2]$ are estimated using regularized least squares (ridge regression) on observed state-input data.
Confidence Ellipsoid: A high-probability confidence set $\mathcal{C}_k(\delta)$ is constructed around the estimate $\hat{\theta}_k$ . This set contains the true parameter $\theta^*$ with probability $1-\delta$ .

B. Certified Surrogate Model Selection (The Core Innovation)

The Problem: The raw estimate $\hat{\theta}_k$ might lie outside the region where the GARE admits a stabilizing solution, leading to unstable controllers.
The Solution: Instead of using $\hat{\theta}_k$ directly, the algorithm performs a shrinkage step. It searches along the line segment connecting the previous certified model $\tilde{\theta}_{k-1}$ and the new estimate $\hat{\theta}_k$ .
Selection Criteria: It selects the largest step size $\alpha$ $α$ such that the new surrogate model $\tilde{\theta}_k = (1-\alpha)\tilde{\theta}_{k-1} + \alpha\hat{\theta}_k$ $\tilde{θ}_{k} = (1 - α) \tilde{θ}_{k - 1} + α \hat{θ}_{k}$ satisfies:
1. It remains within the confidence set $\mathcal{C}_k(\delta)$ .
2. It lies in a "regularity region" $\theta_{reg}(\mu, \gamma)$ where the GARE is solvable, the solution is positive definite, and the closed-loop system is Schur stable with specific margins.
Result: This ensures that every policy update is feasible and stabilizing.

C. Control Update and Exploration

Certainty Equivalence: Once a certified surrogate $\tilde{\theta}_k$ is selected, the GARE is solved to obtain new feedback gains $(K_k, L_k)$ .
Exploration: To ensure persistent excitation (necessary for parameter convergence), small Gaussian noise is injected into the control inputs.
Update Frequency: The model is only re-estimated when the information matrix grows sufficiently (using a "doubling trick"), limiting the number of updates to $O(\log T)$ .

D. Local Perturbation Analysis

The authors prove that small errors in the model parameters induce proportionally small errors in the Riccati solution and the feedback gains. This Lipschitz continuity is crucial for bounding the regret.

3. Key Contributions

Certified Algorithm: Development of the first online learning algorithm for two-player zero-sum LQ games with unknown dynamics that guarantees stability at every step through a certified surrogate selection mechanism.
Regret Bound: Establishment of a sublinear regret bound of $O(\sqrt{T})$ . This is achieved by decomposing regret into transient costs, exploration costs, and policy gap costs, and bounding each term using the estimation error and the Lipschitz properties of the GARE solution.
Convergence Analysis: Rigorous proof that the estimated parameters and feedback gains converge to the true Nash equilibrium values, provided the system satisfies a persistent excitation condition.
Surrogate Selection Framework: Introduction of a constructive shrinkage procedure that bridges the gap between statistical estimation (confidence sets) and control-theoretic feasibility (GARE solvability).

4. Results

Numerical Simulation: The paper presents a simulation with a 3-state system over a horizon of $T=50,000$ .
Parameter Convergence: The estimation error ( $\|\tilde{\theta}_k - \theta^*\|_2$ ) and the feedback gain errors ( $\|K_k - K^*\|_F$ ) decrease over time, confirming that the algorithm learns the true dynamics.
Surrogate vs. Raw Estimate: The simulation demonstrates a distinct gap between the raw ridge estimate error and the certified surrogate error. The surrogate remains more conservative to ensure stability, validating the necessity of the shrinkage step.
Regret Performance: The normalized regret ( $\text{Reg}(T)/\sqrt{T}$ ) remains bounded and stabilizes, empirically verifying the theoretical $O(\sqrt{T})$ bound.

5. Significance

Bridging Theory and Practice: This work solves a critical gap in multi-agent control: how to learn optimal strategies in adversarial settings without knowing the system model while guaranteeing the system never becomes unstable.
Robustness: By enforcing regularity margins (via the shrinkage step), the algorithm prevents the "optimism" of standard learning methods from leading to catastrophic instability, a common failure mode in zero-sum games.
Foundation for Future Work: The framework provides a blueprint for extending online learning to more complex scenarios, such as partially observed games, multi-player settings, or time-varying systems, by adapting the certified selection mechanism.

In summary, the paper presents a mathematically rigorous and practically viable approach to learning optimal control strategies in unknown adversarial environments, ensuring that learning efficiency does not come at the cost of system stability.