Source-linked AI summary
Approximate Equilibrium Computation for Discrete-Time Linear-Quadratic Mean-Field Games
Muhammad Aneeq uz Zaman, Kaiqing Zhang, Erik Miehling, Tamer Başar
TL;DR
Equilibrium-computation algorithms for mean-field games have received limited attention, and backward-in-time control calculations complicate forward updates. This paper develops forward-in-time policy iteration for discounted-cost linear-quadratic mean-field games using structure in the mean-field update. Numerically, it reports a good approximation in 40 iterations at εs = 0.005, with average cost per agent decreasing as the population grows and approximations improve.
Problem
Equilibrium-computation algorithms for mean-field games have received limited attention, while the backward-in-time optimal control calculation makes forward updates challenging.
Source: §I · p. 2Method
The authors use structural properties of the mean-field update to construct forward-in-time policy iteration for discrete-time discounted-cost LQ-MFGs.
Source: §I · p. 2, B. A Computable Policy Iteration… · p. 4Results
At εs = 0.005, the algorithm reaches a good approximation in k = 40 iterations; average cost per agent decreases as N increases and approximations improve.
Source: §V · p. 5Takeaways & Limitations
The numerical results provide evidence that infinite-population policies can be effective when applied to finite populations.
Source: §II · p. 3, §V · p. 5
Abstract
from arXiv · showhide
While the topic of mean-field games (MFGs) has a relatively long history, heretofore there has been limited work concerning algorithms for the computation of equilibrium control policies. In this paper, we develop a computable policy iteration algorithm for approximating the mean-field equilibrium in linear-quadratic MFGs with discounted cost. Given the mean-field, each agent faces a linear-quadratic tracking problem, the solution of which involves a dynamical system evolving in retrograde time. This makes the development of forward-in-time algorithm updates challenging. By identifying a structural property of the mean-field update operator, namely that it preserves sequences of a particular form, we develop a forward-in-time equilibrium computation algorithm. Bounds that quantify the accuracy of the computed mean-field equilibrium as a function of the algorithm's stopping condition are provided. The optimality of the computed equilibrium is validated numerically. In contrast to the most recent/concurrent results, our algorithm appears to be the first to study infinite-horizon MFGs with non-stationary mean-field equilibria, though with focus on the linear quadratic setting.
I. INTRODUCTION
The paper addresses equilibrium computation for discrete-time linear-quadratic mean-field games, where backward-in-time control calculations challenge forward computation. It introduces a forward-in-time policy iteration approach and motivates mean-field games as a response to multi-agent scalability concerns.
I. INTRODUCTION
- Scalability remains a central motivation: existing multi-agent algorithms can grow exponentially in complexity with the number of agents.The paper notes that this has precluded applying many such algorithms even to moderately sized systems.Source: §I · p. 1
- Mean-field games approximate interactions through the population-state distribution, with each agent’s influence assumed infinitesimal in a large population.The NCE principle decomposes equilibrium computation into an individual best response and a population mean-field update.Source: §I · p. 1
- Discrete-time LQ-MFGs have received less attention than continuous-time models; the cited discrete-time study uses an average-cost setting, unlike this paper’s discounted-cost formulation.LQ-MFGs use linear dynamics and quadratic state-deviation and control-effort costs, yielding a tracking subproblem for each agent.Source: §I · p. 1
- The cost-minimizing control requires a backward-in-time calculation, making straightforward mean-field updates uncomputable and challenging model-free computation.The proposed algorithm uses structural properties of the policy-iteration update to compute forward in time.Source: §I · p. 2
- The authors introduce discounted-cost discrete-time LQ-MFGs, establish MFE existence and uniqueness, and develop forward-in-time policy iteration with convergence error analysis.They also illustrate computed-equilibrium quality in relation to the stopping condition and number of agents.Source: §I · p. 2
II. LINEAR QUADRATIC MEAN-FIELD GAME MODEL
The model replaces finite-agent interactions with a generic agent responding to the population’s mean state. It focuses on linear dynamics and quadratic costs, and defines equilibrium through mutually consistent control and mean-field trajectories.
II. LINEAR QUADRATIC MEAN-FIELD GAME MODEL
- In the infinite-population game, a generic agent interacts with the mass behavior of the population, and the mean-field is the empirical average of agents’ states.The paper’s focus is on linear agent dynamics and quadratic costs.Source: §II · p. 2
- The mean-field trajectory is assumed bounded, and the agent’s policy at each time depends only on its current state.The trajectory belongs to the space of bounded sequences.Source: §II · pp. 2–3
- An MFE is a control law that is optimal for its mean-field together with a mean-field generated by that control law.The equilibrium conditions are µ∗ = Φ(¯z∗) and ¯z∗ = Λ(µ∗).Source: §II · pp. 2–3
- The paper does not derive explicit finite-agent bounds; it uses numerical results to illustrate the mean-field approximation’s effectiveness for finite populations.The cited motivation is that infinite-population equilibrium policies can approximate finite-population policies.Source: §II · p. 3
III. BACKGROUND: MFE CHARACTERIZATION
The paper characterizes equilibrium as a fixed point of a mean-field update operator. Under a stated condition, the operator is contractive, giving a unique equilibrium, but direct iteration is not computable because optimal control runs backward in time.
III. BACKGROUND: MFE CHARACTERIZATION
- For a given mean-field trajectory, the cost-minimizing control has a closed-form characterization involving a Riccati solution and a co-state sequence generated backward in time.The control gain gp is defined using the positive solution p of the discrete-time algebraic Riccati equation.Source: §III · p. 3
- Assumption 1 requires Tp < 1; under this condition, the co-state process and optimal cost are bounded.The section distinguishes its discounted-cost criterion from the average-cost criterion in.Source: §III · p. 3
- Under Assumption 1, the mean-field update operator is a contraction on the bounded-trajectory space, and its fixed point corresponds to an MFE.The paper states that the resulting MFE is unique by the Banach fixed-point theorem.Source: §III · pp. 3–4
- Directly iterating the operator would converge to the MFE, but is not computable because its cost-minimizing control requires backward-in-time calculation.The paper identifies forward-in-time computation as necessary for developing model-free learning algorithms.Source: §III · p. 4
- The section develops operator properties intended to support a computable policy iteration algorithm that proceeds forward in time.The update operator maps a candidate mean-field to the trajectory induced by its cost-minimizing control.Source: §III · pp. 3–4
A. Properties of the Mean-Field Update Operator
The mean-field update preserves a structured sequence form: it maps stable τ-latent LTI sequences to stable sequences with one additional latent step. This structure makes finite-iteration representations possible.
A. Properties of the Mean-Field Update Operator
- A τ-latent LTI sequence follows linear dynamics after time τ and can be represented by τ + 2 parameters, (x0:τ, r).The initial τ + 1 values and the constant r specify the sequence.Source: A. Properties of the Mean-Field Update… · p. 4
- The update maps a stable τ-latent LTI sequence with |r| ≤ 1 to a stable (τ + 1)-latent LTI sequence with the same r.This preservation property is the basis for parameterizing successive mean-field iterates.Source: A. Properties of the Mean-Field Update… · p. 4
- Each application of the update operator increases the trajectory parameterization’s dimension, while every finite iteration remains computable.The finite representation addresses the challenge that the equilibrium trajectory and cost-minimizing control are infinite dimensional.Source: A. Properties of the Mean-Field Update… · p. 4
B. A Computable Policy Iteration Algorithm
The algorithm iterates the mean-field update using parameterized trajectories, allowing finite iterations and control calculations to proceed forward in time. Its iterates approach the equilibrium trajectory.
B. A Computable Policy Iteration Algorithm
- The policy-iteration procedure operates over iterations k = 1, 2, …, with variables at iteration k denoted by superscript (k).Algorithm 1 summarizes the procedure and returns a parameter tuple for the mean-field trajectory.Source: B. A Computable Policy Iteration… · pp. 4–5
- Starting from a 0-latent trajectory, the algorithm’s kth mean-field trajectory is k-latent and has a finite parameter representation.The update structure ensures the finite representation at every finite iteration.Source: B. A Computable Policy Iteration… · p. 4
- The cost-minimizing control is calculated forward in time, then the mean-field is updated by executing that control and aggregating agent states.The control has a closed form without infinite sums.Source: B. A Computable Policy Iteration… · p. 4
- The algorithm produces iterates that approach the equilibrium mean-field trajectory.The minimum iterations needed for a desired accuracy can be expressed using the desired accuracy, initial approximation error, contraction coefficient, and linear-dynamics constant.Source: B. A Computable Policy Iteration… · p. 4
V. NUMERICAL RESULTS
Numerical results show that decreasing εs brings the approximated mean-field toward equilibrium, with a good approximation reached in 40 iterations at εs = 0.005. Average cost per agent decreases as the population grows and as the approximation improves.
V. NUMERICAL RESULTS
- The generic agent dynamics use a = 1.1315 and b = 0.7752, with cost coefficients cz = 0.0392 and cu = 1.6864; the initial mean field has z̄0 = ν0 and r = 0.6.Source: §V · p. 5
- As the number of agents N increases, the average cost per agent decreases.Figure 2 presents average cost per agent across population sizes and εs values.Source: §V · p. 5, Figure 2 · p. 5
- εs = 0.005 yields a good equilibrium-mean-field approximation after 40 iterations.Figure 1 compares mean-field approximations for different εs and shows convergence as εs decreases.Source: Figure 1 · p. 5, §V · p. 5
- Better mean-field approximations are accompanied by a decrease in average cost per agent.The reported cost values are normalized to the lowest cost obtained at N = 10000 and εs = 0.005.Source: §V · p. 5, Figure 2 · p. 5
VI. CONCLUDING REMARKS AND FUTURE DIRECTIONS
The policy-iteration algorithm uses the mean-field update’s τ-latent structure to construct updates forward in time. It converges, and the computed equilibrium’s optimality improves with more iterations and a tighter stopping threshold.
VI. CONCLUDING REMARKS AND FUTURE DIRECTIONS
- The τ-latent property lets each iteration represent the mean-field trajectory with finitely many parameters, enabling forward-in-time construction of the optimal control.The algorithm approximates equilibria in infinite-horizon LQ-MFGs with discounted cost.Source: §VI · p. 5
- The policy-iteration algorithm is provably convergent, with numerical results demonstrating its convergence behavior.The paper describes its analysis as providing an algorithmic viewpoint on the nature of mean-field equilibria for LQ-MFGs.Source: §VI · pp. 5–6
- The computed equilibrium’s optimality improves as the iteration index increases and the stopping threshold decreases.Source: §VI · pp. 5–6
- Future work includes extending the approach to multivariate cases and to nonlinear or non-quadratic models.Source: §VI · p. 6
APPENDIX
The appendix establishes conditions for the LQ solution and mean-field update, and proves fixed-point and stopping-condition results for the algorithm.
APPENDIX
- The appendix bounds λ for bounded mean-fields and gives the closed-loop state dynamics under the cost-minimizing control.Source: APPENDIX · p. 6
- Under Assumption 1, T is a contraction, and the DARE has a unique positive solution with γ|hp| < 1.The appendix also uses the steady-state solution of the Riccati equation for the infinite-horizon problem.Source: APPENDIX · p. 6
- A mean-field equilibrium corresponds to a fixed point of T, with the equilibrium control given by the cost-minimizing response to that mean-field.Source: APPENDIX · p. 6
- The stopping condition terminates the algorithm when the successive-iterate discrepancy is below εs, and the appendix derives a bound on the required iteration count.Source: APPENDIX · p. 7