On finite-horizon approximation of a feedback Nash equilibrium in LQ games

This paper proposes and analyzes a finite-horizon approximation method for computing feedback Nash equilibria in infinite-horizon discrete-time linear-quadratic games, establishing conditions for equilibrium uniqueness, providing an efficient solution algorithm, and proving the convergence of costs with explicit error bounds.

The Gist

Imagine a group of friends playing a very long, complex game of chess, but instead of moving one piece at a time, they are all trying to control a giant, moving robot together. Each friend has a different goal: one wants the robot to go fast, another wants it to be smooth, and a third wants it to save energy. They all have to make decisions every second, forever.

This is the problem the paper tackles: How do you find the perfect strategy for a game that never ends?

The Problem: The "Forever" Game is Too Hard

In the world of math and engineering, this is called an Infinite-Horizon Linear-Quadratic (LQ) Game.

• Infinite-Horizon: The game goes on forever.
• Feedback Nash Equilibrium: This is the "perfect" state where everyone is playing their best possible move, knowing everyone else is doing the same. No one wants to change their strategy because it would only make things worse for them.

The problem? Calculating this "perfect" strategy for a game that lasts forever is a mathematical nightmare. It involves solving massive, tangled equations (called Riccati equations) that are incredibly difficult to compute, especially when the players have different priorities (like different discount factors).

The Solution: The "Look-Ahead" Trick

The authors propose a clever shortcut inspired by how self-driving cars and robots actually work. They call it the Finite-Horizon Strategy.

Instead of trying to solve the "forever" game all at once, imagine each player says:

"I can't see the end of time, but I can see the next 10 steps clearly. So, I will plan my moves for the next 10 steps, pick the very first move from that plan, take it, and then immediately re-plan for the next 10 steps."

This is exactly like Model Predictive Control (MPC), a technique used in real-world engineering.

• The Analogy: Think of driving a car down a long, winding road. You don't plan your entire route from New York to London in one go. Instead, you look 100 meters ahead, steer the car to stay in the lane, and then look another 100 meters ahead. You repeat this constantly.

How the Paper Breaks It Down

1. The Finite Game (The "10-Step" Plan)
First, the authors analyze what happens if the game actually stops after a set number of steps (say, 10). They show that if you have a certain mathematical condition (the equations don't get "stuck"), you can easily calculate the perfect strategy for this short game. It's like solving a puzzle with a clear end point.

2. The Infinite Game (The "Forever" Plan)
Next, they apply this short-term thinking to the long-term game. They prove that if everyone plays this "look 10 steps ahead, move one step" strategy:

• Convergence: As you increase the number of steps you look ahead (from 10 to 20, to 50, to 100), your strategy gets closer and closer to the "perfect" infinite strategy.
• The Cost Gap: They even calculated a "price tag" for not looking far enough. They derived a formula that tells you exactly how much "worse" your score will be compared to the perfect strategy, based on how far you are looking ahead.
  • Metaphor: If looking 10 steps ahead costs you 5 points of efficiency, looking 20 steps might only cost you 1 point. The paper gives you the math to predict exactly how much you lose by being "short-sighted."

Why This Matters

This paper is a big deal because it turns an impossible math problem into a practical, solvable one.

• Before: Engineers might have said, "We can't solve this game because it's too complex and never ends."
• Now: They can say, "Let's just solve a short version of the game, take the first step, and repeat. We know exactly how close this gets us to the perfect solution, and we can prove it."

The Real-World Example

The paper includes a simulation with two "players" (like two autonomous drones) trying to coordinate their movements.

• When they only looked 2 steps ahead, their performance was okay but not great.
• As they increased their "vision" to 50 steps, their performance smoothly improved and eventually matched the theoretical "perfect" infinite strategy.

The Bottom Line

The authors found a way to approximate the "perfect" strategy for a never-ending game by breaking it down into manageable, short-term chunks. They proved that this method works, showed how to calculate it efficiently, and gave a guarantee on how good the result will be. It's a bridge between the theoretical ideal of "perfect forever planning" and the practical reality of "good enough, step-by-step planning."

Technical Summary

Here is a detailed technical summary of the paper "On finite-horizon approximation of an infinite-horizon feedback Nash equilibrium in discrete-time LQ games."

1. Problem Statement

The paper addresses the computational challenge of finding Feedback Nash Equilibria (FNE) in infinite-horizon discrete-time Linear-Quadratic (LQ) dynamic games involving multiple agents.

• Context: In infinite-horizon settings, the FNE is typically characterized by a set of coupled algebraic Riccati equations. Solving these equations is computationally difficult due to high dimensionality, non-linear algebraic structures, and cross-product terms.
• Specific Challenge: Existing methods (iterative algorithms, approximate $\epsilon$-Nash equilibria) often struggle with convergence guarantees, computational complexity, or fail to explicitly handle heterogeneous discount factors across players.
• Goal: The authors propose a finite-horizon approximation strategy where each player solves a $T$-stage game at every time step, implements only the first-stage control, and repeats. The paper aims to:
  1. Establish conditions for the existence and uniqueness of the FNE in the finite-horizon setting.
  2. Prove that as the prediction horizon $T \to \infty$, the cost incurred by this finite-horizon strategy converges to the cost of the true infinite-horizon FNE.
  3. Derive an explicit upper bound on the performance gap (cost difference) between the approximation and the true equilibrium.

2. Methodology

A. System and Game Formulation

• Dynamics: The system follows linear time-invariant dynamics with Input/Output/State (i/o/s) structure:
  $$x_{t+1} = A x_t + \sum_{i=1}^N B_i u_{i,t}$$
  $$y_t = C x_t + \sum_{i=1}^N D_i u_{i,t}$$
• Cost Function: Players minimize a discounted quadratic cost over an infinite horizon:
  $$J_i = \frac{1}{2} \sum_{t=1}^{\infty} \left( y_t^\top Q_i y_t + \sum_{j=1}^N u_{j,t}^\top R_{ij} u_{j,t} \right) (\delta_i)^{t-1}$$
  where $\delta_i \in (0, 1]$ is the heterogeneous discount factor for player $i$.

B. Finite-Horizon Analysis

The authors first analyze a $T$-stage finite-horizon game.

• Riccati Structure: They characterize the FNE via coupled generalized discrete Riccati difference equations involving matrices $P_i, S_i, w_i$ (cost matrices) and feedback gains $K_i, L_i$.
• Uniqueness Condition: They derive a sufficient condition for the uniqueness of the FNE: the invertibility of a specific matrix function $H(P_{t+1})$ at every stage.
• Algorithm: Based on this condition, they propose a Backward Algorithm (Algorithm 1). Instead of solving the complex coupled non-linear system directly, the algorithm iteratively solves a sequence of linear equations (specifically, linear systems for $K_t$ and $L_t$) moving backward from $t=T$ to $t=1$.

C. Infinite-Horizon Approximation Strategy

• Strategy Definition: In the infinite-horizon game, each player $i$ adopts a "look-ahead" strategy with a fixed horizon $T_i$. At any time $t$, player $i$ solves the $T_i$-stage game starting from the current state, extracts the first-stage feedback gain $K_{i,1}^*(T_i)$, and applies $u_{i,t} = K_{i,1}^*(T_i) x_t$.
• Key Insight: Due to the time-invariance of the system parameters, the first-stage gain of a $T$-stage game depends only on $T$, not on the absolute time $t$. Thus, the strategy is time-invariant (stationary).

D. Convergence and Error Analysis

• Convergence: Assuming the coupled Riccati iterations converge to limiting matrices $P_i^*$ and $K_i^*$ (which constitute the true infinite-horizon FNE), the authors prove that the strategy matrices $K_{i,1}^*(T_i)$ converge to $K_i^*$ as $T_i \to \infty$.
• Cost Gap Bound: The paper derives an explicit upper bound on the difference between the total cost under the finite-horizon strategy ($\tilde{J}_i$) and the true FNE cost ($J_i$).
  $$|\tilde{J}_i(x_1) - J_i(x_1)| \leq \frac{1}{2} \|x_1\|^2 \frac{\theta_i(\epsilon)}{1 - \delta_i}$$
  where $\epsilon = \max_i \|K_{i,1}^*(T_i) - K_i^*\|_2$ represents the distance between the approximate and true strategy matrices. The term $\theta_i(\epsilon)$ is a cubic polynomial in $\epsilon$, ensuring the error vanishes as the horizon increases.

3. Key Contributions

1. Computational Tractability: The paper provides a computationally efficient algorithm for finite-horizon LQ games that reduces the problem to solving a sequence of linear equations, avoiding the direct solution of non-linear coupled Riccati equations.
2. Theoretical Justification for MPC-like Strategies: It rigorously justifies the use of finite-horizon strategies (similar to Model Predictive Control) in infinite-horizon dynamic games, proving convergence to the true FNE.
3. Explicit Performance Guarantees: Unlike previous works that offer qualitative convergence, this paper provides a quantitative upper bound on the sub-optimality (cost gap) in terms of the strategy matrix error and system parameters.
4. Handling Heterogeneity: The framework explicitly accommodates heterogeneous discount factors ($\delta_i$) and i/o/s dynamics (where output $y_t$ differs from state $x_t$), which are often simplified in standard literature.

4. Results

• Numerical Simulation: A two-player numerical example with a 3-dimensional state space and non-zero reference trajectories was conducted.
  • Convergence of Gains: The simulation showed that the first-stage strategy matrices $K_{i,1}^*(T)$ converge rapidly to the limiting infinite-horizon matrices as $T$ increases (from 1 to 20).
  • Convergence of Cost: The total costs incurred by players using the finite-horizon strategy converged to the theoretical infinite-horizon FNE costs as the prediction horizon $T$ increased (tested up to $T=50$).
• Validation: The results confirmed that the finite-horizon strategy serves as a high-quality approximation, with the error diminishing as the prediction horizon extends.

5. Significance

This work bridges the gap between theoretical dynamic game solutions and practical implementation.

• Practicality: Solving infinite-horizon coupled Riccati equations is often intractable for real-world multi-agent systems (e.g., robotics, smart grids, economics). This paper offers a viable alternative: solving a manageable finite-horizon problem repeatedly.
• Robustness: By providing explicit error bounds, the paper allows system designers to determine the necessary prediction horizon $T$ to achieve a desired level of performance accuracy.
• Foundation for Future Work: The analysis of heterogeneous discount factors and i/o/s dynamics sets a more general foundation for future research in multi-agent control, moving beyond standard state-feedback assumptions.

In summary, the paper successfully demonstrates that finite-horizon look-ahead strategies are not only computationally feasible but also theoretically sound approximations for infinite-horizon LQ dynamic games, with provable convergence and quantifiable performance guarantees.