PaperlayerView exact revision on arXiv

Source-linked AI summary

Value Iteration Algorithm for Mean-field Games

Berkay Anahtarci, Can Deha Kariksiz, Naci Saldi

arXiv:1909.01758v3eess.SYcs.SYmath.OC

TL;DR

Discrete-time mean-field equilibrium computation with convergence guarantees has been missing for abstract state spaces, despite prior existence results and the relevance of both discounted and average costs. The paper proposes Q-function value iteration through a mean-field equilibrium operator; under stated regularity conditions, it proves convergence to a fixed point and constructs an equilibrium from it.

  • Problem

    For discrete-time mean-field games with abstract state spaces, prior work established equilibrium existence but had not supplied a convergence-guaranteed computation method for discounted and average-cost criteria.

    Source: §1 · p. 3

  • Method

    The paper iterates Q-functions and the state distribution with a mean-field equilibrium operator, rather than using value functions alone.

    Source: §1 · p. 1

  • Results

    Under regularity assumptions, the mean-field equilibrium operator is a contraction, and its fixed point is used to construct a mean-field equilibrium for discounted and average costs.

    Source: §1 · p. 1, §3.1 · pp. 12, 15, §3.2 · p. 19

  • Takeaways & Limitations

    The fixed-point construction provides a value-iteration route to computing mean-field equilibria in the paper's discrete-time setting.

    Source: §4 · p. 21

    The results rely on regularity assumptions on system components, with the average-cost analysis imposing additional conditions in place of one discounted-case assumption.

    Source: §2 · p. 7, §3.2 · p. 16

Abstract

from arXiv · show

In the literature, existence of mean-field equilibria has been established for discrete-time mean field games under both the discounted cost and the average cost optimality criteria. In this paper, we provide a value iteration algorithm to compute mean-field equilibrium for both the discounted cost and the average cost criteria, whose existence proved previously. We establish that the value iteration algorithm converges to the fixed point of a mean-field equilibrium operator. Then, using this fixed point, we construct a mean-field equilibrium. In our value iteration algorithm, we use $Q$-functions instead of value functions.

1. Introduction

Mean-field games replace an intractable finite-agent equilibrium problem with an infinite-population model whose equilibrium can approximate a Nash equilibrium when the population is sufficiently large. The paper addresses the lack of convergence-guaranteed computation for discrete-time games with abstract state spaces by proposing a Q-function value-iteration algorithm for discounted and average costs.

1. Introduction

  • The paper proposes Q-function value iteration for discrete-time Polish-state mean-field games under both discounted-cost and average-cost criteria.The mean-field equilibrium operator updates both the Q-function and the state distribution; under regularity assumptions it is a contraction, and its fixed point is used to construct an equilibrium.Source: §1 · p. 1
  • Finite-agent equilibrium is generally infeasible to establish because information is decentralized and many agents are coupled, while the infinite-population equilibrium is approximately Nash for sufficiently large populations.In the limit, a generic agent faces a single-agent control problem constrained by the state distribution; Nash certainty equivalence requires an optimal policy to reproduce that distribution.Source: §1 · pp. 1–2
  • Continuous-time mean-field games have an extensive numerical literature, but the paper notes that its methods generally assume special state spaces and are unlikely to transfer directly to discrete time.Continuous-time approaches include numerical methods for coupled Fokker-Planck and Hamilton-Jacobi-Bellman equations [2], [3],,,,.Source: §1 · pp. 2–3
  • Prior discrete-time work mostly covers finite or countable states, linear games, or mean-field effects confined to costs; computation with convergence guarantees remained absent for abstract state spaces.The cited computational exception uses fictitious play for finite-state, finite-horizon games under a restrictive monotonicity condition.Source: §1 · pp. 2–3

2. Mean-field games and mean-field equilibria

This section formulates a mean-field game as a single-agent control problem coupled to a state-measure consistency condition, then relates that limit model to a finite-agent game. Its equilibrium pairs an optimal policy with the state distribution induced by that policy.

2. Mean-field games and mean-field equilibria

  • A mean-field game has Polish state space, compact finite-dimensional action space, transition probabilities depending on state, action, and state measure, and a one-stage cost with the same inputs.The model also specifies an initial state distribution.Source: §2 · p. 4
  • An equilibrium pair requires a policy optimal for the state measure and a state measure consistent with the distribution generated under that policy.The mappings Ψ and Λ represent the optimal-policy and induced-state-measure conditions, respectively.Source: §2 · pp. 4–5
  • The model assumes regularity conditions on costs, transitions, and optimization so the state measure's effects on value functions and optimal policies can be controlled.The paper identifies continuity and Lipschitz conditions, along with strong convexity, among the assumptions used for those controls.Source: §2 · p. 7

2.1. Finite Player Game

  • When the finite-agent population is sufficiently large, adopting the mean-field equilibrium policy yields an approximate Nash equilibrium, although proving exact finite-agent equilibrium existence is generally prohibitive.The paper cites this approximation result for [30, Theorem 4.1] and [35, Section 5].Source: §2.1 · pp. 8–9

3. Value Iteration Algorithm

This section develops Q-function-based value iteration algorithms for computing mean-field equilibria under discounted and average-cost criteria, building on the MDP reduction for a given state-measure. For the average-cost criterion, it describes convergence to a fixed point of the mean-field equilibrium operator, a contraction with constant κ, from which a mean-field equilibrium is obtained.

3.1. Discounted Cost

  • In the discounted-cost case, H is a contraction with constant k, so value iteration converges to its fixed point, from which the constructed policy and measure form a mean-field equilibrium.Source: §3.1 · pp. 12, 15

3.2. Average Cost

  • For average cost, under Assumption 1 (except (1)) and additional conditions, the Q-based MFE operator L is defined and shown to map M × P(X) into itself.Source: §3.2 · pp. 16–18
  • The operator L is a contraction on M × P(X) with constant κ from Assumption 3.Source: §3.2 · p. 19
  • Value iteration converges to a fixed point of the average-cost mean-field equilibrium operator L.The algorithm iterates (Q_{n+1}, μ_{n+1}) = L(Q_n, μ_n) and returns the fixed point (Q*, μ*).Source: §3.2 · p. 20
  • The fixed point yields a mean-field equilibrium (π*, μ*) when the policy is constructed as π*(a|x) = δ_{f*(x)}(a).The proof identifies π* as optimal for μ* and μ* as consistent with π*.Source: §3.2 · pp. 20–21

4. Conclusion

The paper establishes a value iteration algorithm for discrete-time mean-field games under discounted and average cost criteria. Under regularity conditions, the mean-field equilibrium operator is a contraction, and its fixed point is used to construct an equilibrium.

  • The value iteration algorithm addresses discrete-time mean-field games under both discounted and average cost criteria.Source: §4 · p. 21
  • Under certain regularity conditions, the mean-field equilibrium operator is a contraction.Source: §4 · p. 21
  • The fixed point of the mean-field equilibrium operator is used to construct a mean-field equilibrium.Source: §4 · p. 21
Loading 1909.01758v3…