Linear-Quadratic Gaussian Games with Distributed Sparse Estimation

1. Problem Statement

The paper addresses the challenge of resource-constrained multi-agent systems operating under uncertainty. Specifically, it focuses on Linear-Quadratic Gaussian (LQG) games, where $N$ agents interact strategically to minimize a quadratic cost function while subject to linear dynamics and Gaussian noise.

Key Challenges:

• Standard LQG Limitations: Traditional LQG formulations assume agents utilize the full set of available noisy observations to form state estimates. In large-scale systems (e.g., robot swarms), processing and exchanging all measurements is often impractical due to limited bandwidth, energy, and computational resources.
• Strategic Coupling: Unlike single-agent estimation, agents in a game interact strategically. The control input of one agent affects the state evolution of others, and the estimation error of one agent impacts the control performance of all.
• Separation Principle Failure: In LQG games with individual (partial) observations, the classical separation principle (where estimation and control can be designed independently) does not generally hold. The equilibrium strategies depend on the information pattern, making the design of sparse estimators non-trivial.

The core problem is to design a distributed sparse estimator that allows agents to selectively use a subset of available observations (sensor sparsity) while maintaining acceptable control performance and ensuring the stability of the estimation error.

2. Methodology

The authors propose a framework that integrates Group Lasso optimization into the estimation stage of LQG games, coupled with Feedback Nash strategies for control.

A. System Formulation

• Dynamics: Agents follow discrete-time linear dynamics with Gaussian process noise.
• Observations: Each agent $i$ receives partial, noisy observations $y^i_t$ of the joint state $x_t$. These observations are partitioned into groups (e.g., measurements from specific sensors or other agents).
• Control: Agents implement a feedback control law $u^i_t = -\Gamma^i_t \hat{x}^i_t - \alpha^i_t$, where $\hat{x}^i_t$ is the estimated joint state. The gains $\Gamma_t$ and $\alpha_t$ are pre-computed Nash equilibrium gains assuming full information (a common low-complexity approximation).

B. Distributed Sparse Estimation Design

The core innovation is the design of the estimation gain $K^i_t$ to enforce sparsity.

1. Error Propagation: The authors derive the propagation of the joint estimation error covariance $\Sigma_t$, explicitly showing how it depends on the mismatch between an agent's estimated control and the actual joint control.
2. Group Lasso Optimization: To enforce sparsity, the optimal dense gain $K^{i*}_t$ (derived via standard Kalman filtering logic) is approximated by solving a Group Lasso problem:
   $$\min_{K^i_t} \| K^i_t(C^i_t \Sigma^{i-}_t C^{i\top}_t + V^i_t) - \Sigma^{i-}_t C^i_t \|_F^2 + \sum_{\rho} \lambda^i_{\rho,t} \| K^i_t[\rho] \|_F$$
   • The first term minimizes the estimation error (Least Squares).
   • The second term penalizes the Frobenius norm of specific block columns ($K^i_t[\rho]$) corresponding to sensor groups.
   • If the norm of a block is small enough, it is zeroed out, effectively disabling that sensor.
3. Convexity: The problem is proven to be a convex conic program (specifically a Second-Order Cone Program), solvable by standard optimizers.

C. Control-Adaptive Regularization

To make the sparsity decision "game-theoretic," the regularization parameter $\lambda^i_{\rho,t}$ is not static. It is dynamically adjusted based on the control dependency:

• If Agent $i$'s control gain heavily depends on Agent $j$'s state (large $\|\Gamma^i_t[j]\|_F$), the regularization is lowered, encouraging the retention of that sensor.
• If the dependency is weak, regularization increases, promoting sparsity.
• This creates a feedback loop where estimation sparsity adapts to the strategic needs of the game.

D. Stability and Reset Mechanism

The paper provides a sufficient condition (Theorem 1) ensuring that if the estimation error covariance grows too large (due to excessive sparsity), the system is guaranteed to "reset" the sparse gain back to the optimal dense gain. This prevents unbounded degradation of estimation quality.

3. Key Contributions

1. Distributed Sparse Estimator: A novel framework for LQG games that enforces structured sparsity in inter-agent observations using Group Lasso, balancing estimation accuracy with communication/computation costs.
2. Game-Theoretic Adaptivity: A control-adaptive regularization scheme that dynamically tunes sparsity levels based on the strategic coupling between agents (i.e., how much one agent's control relies on another's state).
3. Theoretical Guarantees: Proof that the sparse estimator is a convex optimization problem and derivation of conditions under which the estimator self-corrects (resets) to prevent estimation failure.
4. Handling Information Patterns: Explicitly addresses the complexity of LQG games where the separation principle fails, deriving error propagation equations that account for the mismatch between estimated and actual joint controls.

4. Results

The framework was validated via simulations on a three-robot formation game (one leader, two followers).

• Sparsity vs. Performance Trade-off:
  • Static Regularization: High regularization ($\lambda=1000$) significantly reduced sensor usage but degraded trajectory tracking performance due to accumulated estimation errors. Low regularization ($\lambda=50$) improved performance but used more resources.
  • Control-Adaptive Regularization: Achieved the best balance. The leader (R1) prioritized self-measurement (saving resources) while followers (R2, R3) maintained frequent measurements of the leader.
• Trajectory Performance: The adaptive strategy allowed agents to track reference paths with minimal sensing overhead compared to static methods, with only a marginal increase in trajectory error compared to the full-information baseline.
• Covariance Behavior: The simulation confirmed that estimation error covariance remains bounded and triggers the "reset" mechanism when sparsity causes errors to spike, validating the theoretical safety guarantees.

5. Significance

This work bridges the gap between strategic game theory and resource-constrained estimation.

• Scalability: It offers a practical solution for large-scale multi-agent systems (e.g., drone swarms) where full communication is impossible.
• Efficiency: By intelligently pruning uninformative or low-impact sensor interactions, it reduces bandwidth and energy consumption without sacrificing the stability of the game equilibrium.
• Robustness: The built-in reset mechanism ensures that the system does not collapse due to over-sparsification, providing a safety net for real-world deployment.
• Future Direction: The paper lays the groundwork for extending these concepts to nonlinear dynamics and non-quadratic objectives via iterative LQ approaches.