PaperlayerView exact revision on arXiv

Source-linked AI summary

Infinite Horizon Mean-Field Terminal Value Problem

Uğur Aydın, Tamer Başar, Naci Saldi

arXiv:2609.12768v1math.OCcs.SYeess.SY

TL;DR

Discrete-time MFG computation faces forward–backward coupling, and non-stationary infinite-horizon solutions can be computationally intractable. The paper studies MFTVP uniqueness and finite-horizon tail behavior from prescribed terminal Q-functions. It shows that, when a unique TRMFE exists, accumulation points of finite-horizon tails induce stationary MFEs.

  • Problem

    Forward–backward coupling challenges discrete-time MFG computation, and infinite-horizon non-stationary solutions are computationally intractable.

    Source: §1.1 · p. 1, §1.2 · p. 5

  • Method

    The paper studies uniqueness of time-reversed equilibria from prescribed terminal Q-functions and uses occupancy measures to analyze convergence of approximations.

    Source: §3 · pp. 12–13, §6.2 · p. 24

  • Results

    In a sufficiently large discount-factor regime, each prescribed terminal Q-function has a unique TRMFE when the stated conditions hold.

    Source: §3 · p. 13

  • Takeaways & Limitations

    If a unique TRMFE exists, every accumulation point of the finite-horizon MFE tails induces a stationary MFE.

    Source: §3 · p. 14

    A nontrivial terminal Q-function prescribed externally need not correspond to a terminal cost or to the representative agent’s objective.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

We introduce a class of finite- and infinite-horizon discrete-time control problems for studying macroscale systems in discrete time, which we refer to as mean-field terminal value problems (MFTVPs). An MFTVP takes a terminal \(Q\)-function as input and, starting from this terminal \(Q\)-function, seeks an indefinite backward evolution of optimal policies and state measures, as required for an infinite-horizon non-stationary mean-field equilibrium (MFE) of a discrete-time mean-field game (MFG). We study the existence and uniqueness properties of this problem. As an application, using the uniqueness properties of MFTVPs, we show that, in the average-cost setting (and in the discounted setting for sufficiently small discount factors), MFTVPs can be used as an intermediate step to develop approximation schemes between finite-horizon MFEs and average-cost MFEs (respectively, stationary MFEs). In contrast to approaches that use infinite-horizon MFGs as intermediate problems, MFTVPs can be employed when the discount factor is sufficiently small (or, in the average-cost setting, when the drift factor is sufficiently small), together with a regularizer, to approximate a stationary MFE. Assuming uniqueness of the solution of a MFTVP, the restrictions we impose on the Lipschitz parameters of the system are weaker than the contraction conditions available for regularized stationary MFGs, and our approximation scheme remains applicable even in the presence of multiple stationary MFEs.

1 Introduction

Discrete-time MFGs are difficult to compute because of forward–backward coupling and the intractability of non-stationary solutions. The paper introduces MFTVPs, which extend finite-horizon backward Q-function recursions from a prescribed terminal Q-function, and studies their existence, uniqueness, and use in approximating stationary MFEs.

1.1 Motivation and the Formulation of the Problem

  • Forward–backward coupling challenges discrete-time MFG computation, while non-stationary infinite-horizon solutions are computationally intractable and finite-horizon approximations may be inefficient.The cited finite-to-infinite approximation error is O(a^t b^T), where 0 < a < 1 and b > 1.Source: §1.1 · p. 1, §1.2 · p. 5
  • An MFTVP fixes a terminal Q-function and extends the finite-horizon backward Q-function recursion indefinitely into the past, coupled to the forward evolution of population state measures.The terminal Q-function is prescribed externally, so the recursion need not correspond to a single global objective for the representative agent.Source: §1.1 · pp. 2–3
  • An infinite-horizon MFTVP can be obtained as a limit of finite-horizon problems near their terminal times when the relevant sequences converge for every fixed number of steps.Passing to the limit yields an infinite family satisfying the same coupled backward–forward relations.Source: §1.1 · p. 3
  • When finite-horizon MFEs remain contractive for every fixed terminal Q-function and horizon, a unique TRMFE exists for each prescribed terminal Q-function in the sufficiently large discount-factor regime.This regime differs from the sufficiently small discount-factor regime used to construct invariant terminal Q-functions for arbitrarily long horizons.Source: §1.1 · p. 4

1.2 Literature Review

  • Regularized stationary-MFG contraction conditions require sufficiently small Lipschitz parameters and become more restrictive as the discount factor vanishes, whereas finite-horizon contraction conditions do not deteriorate as the discount factor approaches one.The paper motivates its approach by seeking contraction conditions less restrictive than those needed to compute a stationary MFE directly.Source: §1.2 · p. 4, §1.1 · p. 4
  • The paper adapts a finite-horizon state-measure iteration to Q-functions and shows that one-step terminal-Q invariance holds under the finite-horizon MFE contraction condition, which is less restrictive than the stationary-MFE condition.The results apply when the discount factor or drift factor is sufficiently small.Source: §1.2 · p. 4

1.3 Contributions

  • The paper establishes existence and uniqueness conditions for time-reversed MFEs in average-cost and discounted stationary settings, while imposing relatively restrictive assumptions for simplicity.It also presents finite-horizon MFTVPs as approximations to the infinite-horizon problem and uses a stability result to establish existence for a prescribed terminal Q-function.Source: §1.3 · p. 5
  • With a unique TRMFE, the proposed finite-horizon approximation scheme works with a sufficiently small drift factor in average-cost settings or a sufficiently small discount factor in discounted settings, under weaker contraction conditions than stationary MFG methods and even with multiple MFEs.The method uses finite-horizon TRMFEs with a one-step invariant terminal Q-function.Source: §1.3 · pp. 5–6

2 Discrete-Time Mean-field Games

The paper sets out discrete-time MFGs through a representative agent’s optimization coupled to population state-measure evolution. It then describes discounted and average-cost formulations and introduces terminal Q-functions and regularization for its approximation framework.

2 Discrete-Time Mean-field Games

  • A forward discrete-time MFG is specified by finite state and action spaces, a one-stage cost, a transition probability, and an initial population state distribution.The model represents limiting dynamics for homogeneous players with weak interactions.Source: §2 · p. 6, §2.1 · p. 6
  • A mean-field equilibrium couples a representative player's objective optimization with consistency of the population state-measure evolution.The interaction between optimal policies and state measures means an MFE is neither a traditional game equilibrium nor a standard stochastic-control solution.Source: §2.1 · pp. 6–7

2.1 Discounted Discrete-Time Mean-field Games

  • In discounted finite-horizon MFGs, a prescribed terminal Q-function replaces the usual last-stage cost and acts as an additional invariant for approximating stationary and average-cost MFEs.This terminal condition can break the standard objective-function structure and need not yield a closed-form objective.Source: §2.1 · pp. 7–8
  • A discounted MFE is stationary when both the population measure and policy remain constant over time.For stationary MFEs, the initial state measure is part of the solution rather than part of the problem specification.Source: §2.1 · p. 7

2.2 Average-Cost Discrete-time Mean-field Games

  • Average-cost Q-functions require an asymptotic discount optimality equation rather than the discounted Bellman equation, under additional assumptions on the dynamics.Under the stated minorization condition, each given state measure has a unique Q-function satisfying that equation.Source: §2.2 · p. 9
  • The average-cost setting assumes minorization and a drift condition with factor α, with sufficiently small α corresponding to dynamics pulled toward lower values of the weight function.The associated average-cost MFTVP couples backward Q-function evolution with forward state-measure consistency.Source: §2.2 · pp. 9–10

3 Main Results

The section establishes existence and uniqueness results for regularized terminal-value mean-field equilibria in discounted and average-cost settings, including weighted-drift conditions that extend applicability to larger discount factors. It also describes iterative computation of the terminal Q-function using a contractive mapping and the use of finite-horizon equilibria to support approximation of stationary equilibria.

3 Main Results

  • For every terminal Q-function in Cβ, a discounted TRMFE exists, and finite-horizon MFE approximations converge to it along a subsequence.The proof uses occupancy-measure limits because policies themselves need not converge; the target TRMFE may be nonunique.Source: §3 · pp. 12–13
  • For sufficiently large discount factors, the TRMFE is unique for each terminal Q-function in Cβ.The theorem’s condition is stated in the supplied passage without its formula.Source: §3 · p. 13
  • Under Theorem 3’s condition, each finite horizon has a unique equilibrium computable by contractive iteration, and uniqueness of the TRMFE makes its tails approximate a stationary MFE.A sufficiently small drift factor can replace the discount factor in relevant expressions, extending applicability to larger discount factors.Source: §3 · pp. 13–15
  • If each terminal Q-function has a unique TRMFE, accumulation points of finite-horizon occupancy measures induce a stationary MFE after disintegration.The result applies along horizon subsequences whose initial Q-functions converge; the finite-horizon Q-function restrictions can hold even when the stationary-MFG contraction condition does not.Source: §3 · p. 14
  • In the average-cost setting, every terminal Q-function in Cα admits a TRMFE, and finite-horizon equilibria converge to an average-cost TRMFE when the MFTVP solution is unique.The approximation result assumes terminal Q-functions converge in Cα.Source: §3 · pp. 14–15
  • Theorem 6 extends the finite-horizon contraction criterion to weighted dynamics, mitigating the effect of the discount factor.Under its stated condition, the theorem guarantees a unique finite-horizon equilibrium pair; the condition’s formula is absent from the supplied passage.Source: §3 · p. 15
  • Q_T^0 ∈ C_{αβ} can be computed iteratively through a contractive mapping.Source: §3 · p. 15

4 A Numerical Example

The two-state example shows terminal-value invariance can converge where stationary best response and ordinary value iteration do not converge to a stationary MFE. Its finite-horizon values also approach the corresponding stationary-MFE values as the horizon grows.

4 A Numerical Example

  • The example uses two states and two actions, with a nonnegative 1-strongly convex regularizer and cost bounded between 0.00586 and 0.63414.The stated configuration also has λ = 0.98, ω ≡ 1, and α = 0.02.Source: §4 · p. 16
  • All 2,000 random initializations reached the same fixed point, with largest uniform error below 1.6 × 10−14 after 65 updates.The runs used T = 20 and initial population µinitial(1) = .508.Source: §4 · p. 17, Figure 1 · p. 17
  • Stationary best response approaches a two-cycle, ordinary value iteration remains nonconvergent, while terminal-value invariance converges.The example reports a unique infinite-horizon TRMFE for every prescribed terminal Q-function.Source: §4 · p. 15, Figure 2 · p. 17
  • The Q-functions obtained from one-step invariance converge to the corresponding stationary-MFE values as the horizon increases.The numerical setup uses β = 4/5 and regularization parameter ρ = 1/1000.Source: §4 · pp. 16–17

5 Properties of H1 and H2 under Regularization

The appendix establishes compactness and invariance properties for the discounted setting, then gives weighted counterparts of key estimates for minorized discounted costs. These properties support later existence and convergence arguments.

5.1 Discounted Case

  • The discounted-case lemmas establish a one-to-one correspondence between Cβ and a compact set, yielding compactness of Cβ.The appendix also states Lipschitz bounds for the cost and transition operators under Assumption 2.Source: §5.1 · p. 20
  • The discounted space Cβ is compact under the uniform norm, and H1(·, µ) maps Cβ to itself for fixed µ.The appendix also defines Qmin and its Lipschitz pseudo-norm.Source: §5 · p. 19, §5.1 · p. 20

5.2 The minorized discounted-cost case

  • Under the minorized discounted-cost setting, weighted versions of the estimates for Q-functions and state measures are provided.These estimates are identified as inputs to the proof of Theorem 6.Source: §5.2 · p. 22

6 Existence and Uniqueness of Infinite-Horizon Time-Reversed Mean-field Equilibria under Fixed Terminal Cost

This section establishes existence and uniqueness criteria for infinite-horizon time-reversed mean-field equilibria under a fixed terminal cost, presenting discounted-case results with proofs that extend to average cost with minimal modifications. Under the condition that F(t_o) < 1 for some t_o > 1, finite-horizon equilibria converge toward a unique infinite-horizon equilibrium for each terminal Q-function in Cβ.

6.1 Existence of Infinite-Horizon Time-Reversed Mean-field Equilibria

  • Under Assumption 2, every terminal Q-function in Cβ yields a solution to the infinite-horizon MFTVP.The existence proof also shows that accumulation points of finite-horizon MFEs belong to the TRMFE set for the limiting terminal Q-function. It uses compactness to extract convergent Q-function subsequences and shows limiting joint measures remain concentrated on optimal state-action pairs.Source: §6 · p. 22, §6.1 · p. 23

6.2 Uniqueness of Infinite-Horizon Time-Reversed Mean-field Equilibrium under Contraction

  • A contraction condition provides uniqueness of the time-reversed MFE for a given terminal Q-function.The argument uses finite-horizon error bounds, a Q-function iteration contraction characterized through a nonnegative matrix’s spectral radius, and asymptotic properties of its Perron right eigenvectors. The iteration reverses the orientation of the state-measure method in [3], using Collatz–Wielandt bounds; the required contraction regime differs from that for finite-horizon one-step invariance iterations.Source: §6.2 · pp. 24–25
  • If F(t_o) < 1 for some t_o > 1, there is a unique infinite-horizon TRMFE under any given terminal Q-function in Cβ.The theorem also gives an explicit convergence bound for finite-horizon equilibria, though its formula is not available in the supplied passage.Source: §6.2 · p. 30
  • Finite-horizon TRMFEs approximate the infinite-horizon equilibrium, and their state-measure flows converge to its unique flow.Uniqueness follows because the finite-horizon equilibria are unique and their state measures converge to any infinite-horizon TRMFE; dynamic programming and the regularizer then induce unique Q-functions and policies.Source: §6.2 · pp. 30–31
  • The paper characterizes when the minimizer t* of F lies above 1, a condition used to establish the contraction-based uniqueness criterion.The supplied passages state that this characterization describes the system's worst-case behavior, but the displayed parameter threshold is incomplete.Source: §6.2 · p. 31

7 One-Shot Terminal Value Invariance for the Mean-Field Terminal Value Problem under Fixed Initial State-Measure

This section identifies the phase shift governing the asymptotic spectral radius of the matrices B_T, whose Perron roots increase strictly with the horizon. It derives the limit through a recurrence for their characteristic determinants.

7 One-Shot Terminal Value Invariance for the Mean-Field Terminal Value Problem under Fixed Initial State-Measure

  • The Perron roots ρ(B_T) increase strictly with T, and their asymptotic behavior has two branches separated by a phase-shift condition.The section identifies the phase shift and the limiting spectral radius in each case.Source: §7 · p. 33
  • The characteristic determinants are reduced to a tridiagonal determinant, whose standard continuant recurrence supports the asymptotic analysis.The passage states that the transformed matrix T_n(λ) is tridiagonal and that its determinant equals the original characteristic determinant.Source: §7 · p. 34
  • The analyzed sequence ρ(B_T) increases to λac in one case and to λbd in another; at ρ = β(1 − K_D)^2, λac = λbd.Source: §7 · p. 37
  • When K_D ≥ 1, the upper-bound argument gives lim sup ρ(B_T) ≤ λ_ac, and the matching lower bound yields convergence to λ_ac.The lower bound is obtained by considering values below λ_ac for which the characteristic roots are complex conjugates.Source: §7 · pp. 36–37

8 Discounted Terminal Value Invariance under Minorization

Under the stated discounted terminal-value invariance conditions, the iteration is a contraction in a weighted norm. Its unique fixed point yields the finite-horizon MFE, and the iterates converge to it.

8 Discounted Terminal Value Invariance under Minorization

  • The mapping is contractive in a weighted norm defined using a strictly positive Perron eigenvector, and the invariant set then gives a unique fixed point.The fixed point's forward state-measure flow and induced policies form the unique finite-horizon MFE satisfying Q_0 = H_avg,1(Q_0, μ_0).Source: §8 · p. 39
  • The iteration converges to that fixed point, whose forward state-measure flow and induced policies give the unique finite-horizon MFE.The passage states this result for the MFE satisfying Q_0 = H_avg,1(Q_0, μ_0).Source: §8 · p. 39
Loading 2609.12768v1…