Value Iteration Algorithm for Mean-field Games

Berkay Anahtarci; Can Deha Kariksiz; Naci Saldi

REVIEW 2 major objections 4 minor 35 references

Value Iteration Algorithm for Mean-field Games

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves a mean-field equilibrium operator is a contraction, so value iteration converges to a fixed point from which a mean-field equilibrium is constructed.

desk verdict A genuine first: convergent value iteration for discrete-time mean-field games on Polish spaces, but the contraction proof needs a formally defined complete metric before the Banach step is valid. read the letter →

arxiv 1909.01758 v3 pith:HTKUOADS submitted 2019-09-04 eess.SY cs.SYmath.OC

Berkay Anahtarci , Can Deha Kariksiz , Naci Saldi This is my paper · ORCID

classification eess.SYcs.SYmath.OC MSC 91A1649N8090C40

keywords mean-fieldgamesvalueiterationQ-functionsdiscountedcostaveragecontractionmappingWassersteindistanceMarkovdecisionprocesses

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Mean-field games describe a single agent optimizing against a distribution of many identical agents, and an equilibrium is a policy paired with a state distribution that each makes the other correct. This paper claims that, under regularity conditions, a single operator that updates both the Q-function and the state distribution is a contraction. Therefore iterating it from any starting point converges to a unique fixed point, and the greedy policy built from that fixed point's Q-function, together with the fixed point's distribution, is a mean-field equilibrium. This gives the first convergence-guaranteed algorithm for computing mean-field equilibria in discrete-time games with abstract Polish state spaces, for both discounted and average cost.

What carries the argument

The central object is the mean-field equilibrium operator: $H(Q,\mu)$ updates the Q-function like a Bellman operator and simultaneously updates the state measure by one application of the transition kernel under the unique minimizer $f(x,Q,\mu)$ of a strongly convex function $F(x,Q_{\min},\mu,a)$. The proof's engine is the strong convexity of $F$, which yields a Lipschitz bound on the minimizer in $(Q,\mu)$, together with Kantorovich-Rubinstein duality to bound the Wasserstein distance between the two distribution components. These bounds combine into the explicit contraction constants $k$ and $\kappa$, and Banach's fixed point theorem supplies convergence.

What would settle it

Run the proposed iteration on a scalar mean-field game with a heavy-tailed transition kernel, such as t-distributed noise, so that some iterates have infinite first moment; if the iterates do not converge in Wasserstein distance, or if two different initial pairs converge to different limits, then the claimed contraction and completeness fail.

Watch

Extended reading notes

Core claim

For a discrete-time mean-field game with Polish state space, compact convex action space, and costs and transitions satisfying Lipschitz and strong-convexity assumptions, define the mean-field equilibrium operator $H(Q,\mu)=(H_1(Q,\mu),H_2(Q,\mu))$, where $H_1$ is a Bellman-style update on Q-functions and $H_2$ pushes $\mu$ forward one step under the greedy policy minimizing $H_1$. The paper proves that $H$ is a contraction with explicit modulus $k$, and that the analogous operator $L$ for average cost is a contraction with modulus $\kappa$. By Banach's fixed point theorem the iteration $(Q_{n+1},\mu_{n+1})=H(Q_n,\mu_n)$ converges to a unique fixed point $(Q^*,\mu^*)$; Theorem 2 and Theorem 4 then construct a mean-field equilibrium by setting $\pi^*(a|x)=\delta_{f^*(x)}(a)$ with $f^*(x)$ minimizing $Q^*(x,\cdot)$, and verify that $\pi^*$ is optimal for $\mu^*$ while $\mu^*$ is invariant under $\pi^*$.

Load-bearing premise

The load-bearing premise is that the state-distribution space is complete under the Wasserstein distance used in the contraction proof, which holds only for distributions with finite first moment (or a compact state space) and is never stated in the paper.

Editorial extensions

If this is right

Mean-field equilibria for this class of games can be computed by repeated application of a Bellman-type operator, with a guaranteed geometric convergence rate dictated by the contraction constant.
Because the iteration uses Q-functions rather than value functions, the same algorithmic structure can be adapted to model-free settings such as Q-learning for mean-field games.
The fixed point yields a deterministic stationary equilibrium policy and an invariant state measure, so the equilibrium is given in closed-loop form.
For average cost, the same construction works under minorization and drift assumptions, giving a value iteration algorithm for ergodic mean-field games.
Combined with known approximate-Nash results for finite-agent games, the algorithm makes equilibrium policies for large finite populations computable in principle.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An extension the paper leaves implicit: the contraction argument might be relaxed by replacing the Wasserstein-1 metric with a metric tailored to the weight function, potentially covering dynamics with heavier tails.
A cautious reading suggests that any practical implementation on a non-compact state space should explicitly restrict to measures with finite first moment, since the completeness of the fixed-point domain is not stated.
The joint contraction on Q and the distribution suggests that asynchronous or approximate updates might still converge if errors decay sufficiently fast, though the paper does not prove this.
The same fixed-point construction could be tested numerically for finite-state or finite-grid approximations to see how the contraction constant degrades as the approximation becomes finer.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: I'd send this out, with a request to patch one technical gap. The paper gives the first convergence guarantee I know for a value-iteration scheme computing mean-field equilibria in discrete-time mean-field games on Polish state spaces, for both discounted and average cost. The contraction theorem is probably correct, and the gap is fixable.

What is actually new: prior work [30,35] proved existence but gave no algorithm; [17] studied fictitious play only for finite-state, finite-horizon games under monotonicity. Here the authors define an MFE operator built from Q-functions, prove it is a contraction under Assumptions 1-3, and then construct an equilibrium from its fixed point. The perturbation analysis around the greedy minimizer f (inequality (8)) is the real work, and it is carefully done. The contraction constants are explicit. The citation pattern is fine: self-citations to [30,35] are background existence results, not load-bearing, and the MDP facts from [19,20] are standard.

Soft spots, in proportion. The main one is real: Theorems 1 and 3 state that H and L are contractions on C×P(X), but no product metric is ever defined. The proof bounds the two coordinates separately, in the w-norm and in W1, and then declares the contraction. That is not a contraction argument on C×P(X) as written. Worse, W1 is only an extended metric on all of P(X) and, for a general non-compact Polish X, P(X) is not complete under W1. Banach's fixed point theorem is therefore not formally applicable. The natural repair is to work on measures with finite first moment, P1(X), prove H2 and L2 map P1(X) into itself, and put a metric like d((Q,µ),(Q̂,μ̂)) = ‖Q−Q̂‖w + W1(µ,μ̂) on the product. This is plausibly derivable from Assumption 1(d), but the derivation is absent. So the central convergence claim is not established as written, though it is probably repairable.

A second, smaller issue: in Remark 1 of the average-cost section, the "without loss of generality" normalization taking b = ∫w dλ is too quick. Changing α and adding a constant to w changes the weighted norm and the sets C and M; that needs a real justification, not a sentence. Finally, there are no numerical examples and the "algorithm" is a conceptual infinite-dimensional fixed-point iteration, so the practical reach is asymptotic. That is acceptable for a theory paper, but worth stating explicitly.

Who this is for: anyone working on computation of mean-field equilibria in discrete time, and people looking for a Q-function route to Q-learning for MFGs. It deserves a serious referee. I recommend sending it out, with the metric/completeness gap and the Remark 1 normalization flagged for revision.

Referee Report

2 major / 4 minor

Summary. This paper studies infinite-horizon discrete-time mean-field games with Polish state space and compact convex action space, under discounted and average cost criteria. It defines a mean-field equilibrium (MFE) operator H (discounted cost) and L (average cost) acting on pairs of Q-functions and state-measures, proves under Lipschitz, strong-convexity, and drift assumptions that these operators are contractions, invokes Banach's fixed point theorem, and then constructs a mean-field equilibrium from the fixed point as a deterministic policy minimizing the fixed-point Q-function. The paper also sketches the N-agent interpretation and positions the result as the first convergent computational scheme for mean-field games with abstract state spaces.

Significance. If the result holds, this is a useful advance: it gives a concrete value-iteration scheme with a convergence guarantee for discrete-time mean-field games beyond finite-state or linear models, and the use of Q-functions opens the door to model-free extensions. The proofs are largely self-contained, the coordinatewise contraction estimates are explicit, and the construction of the equilibrium policy from the fixed point is standard and plausible. However, the central fixed-point step is missing a formal metric and completeness argument, so the main theorems are not fully justified as written.

major comments (2)

[§3.1, Theorem 1; §3.2, Theorem 3] The Banach fixed-point step is not formally justified because no metric is defined on C×P(X). The proofs bound the two coordinates separately, using ‖·‖_w for the Q-coordinate and W1 for the measure coordinate, but coordinatewise bounds do not by themselves specify a complete metric on the product. On all of P(X), W1 is an extended metric (it can equal +∞), and for a general non-compact Polish X, P(X) is not complete under W1. To apply Banach's theorem the authors must (i) define a product metric such as d((Q,µ),(Q̂,μ̂)) = ‖Q−Q̂‖_w + γ W1(µ,μ̂) for a suitable γ>0, (ii) restrict the measure component to a W1-complete set, typically P1(X), and (iii) prove that H2 (resp. L2) maps P1(X) into itself and that the iterates starting from the algorithm's initial (Q0,µ0) stay in that set. The self-map and completeness steps are absent; without them Theorems 1 and 3 do not deliver the fixed point, and the convergence claims of Algorithms 1 and 2 are not established.
[§3.2, Lemma 2 and Remark 1] The proof that L1(Q,µ)∈M uses the bound ∫ wmax(y) q(dy|x,a,µ) ≤ α w(x,a). This requires an assumption relating the constant b in Assumption 3(b) to ∫ wmax dλ. The "without loss of generality" argument in Remark 1 is not written carefully: the function wmax is never defined, and the stated reduction sets b=∫ w dλ even though the expression that enters the proof is built from wmax. Moreover, the proposed operation of increasing α and adding a constant to w changes the data entering Assumption 3(c), so it cannot be swept into a WLOG statement without rechecking κ. As written, Lemma 2's norm bound is incomplete.

minor comments (4)

[§3.1, Algorithm 1; §3.2, Algorithm 2] The loop condition "(Qn,µn) ≠ (Qn−1,µn−1)" is not implementable and appears to claim finite termination. The algorithms should state convergence in the limit as n→∞, or use an ε-stopping criterion.
[§3.1, proof of Theorem 1, Eq. (9)] The displayed inequality labeled (1) in the proof of (9) contains a garbled line: the second integrand has an extra outer integral and is missing the intended variables of integration. The subsequent paragraph explains the coupling argument, but the displayed line should be corrected.
[§3.2, Lemma 2] In the first displayed estimate, "Q(dy|x,a,µ)" should be "q(dy|x,a,µ)".
[Notation, §2] The notation wmax is used for the wmax-norm, but the function wmax itself is never defined. Please define it explicitly at first use.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the MFE contraction and fixed-point construction are derived from Assumptions 1–3, not assumed from the cited existence results.

full rationale

The paper's central derivation is self-contained. Theorem 1 and Theorem 3 prove that the MFE operators H and L are contractions by explicit coordinate-wise bounds (inequalities (4), (9), (14), (16)), with the contraction constants k and κ stipulated in Assumptions 2 and 3 rather than fitted to the output. Banach's fixed point theorem is then invoked to obtain a fixed point, and Theorems 2 and 4 construct an MFE from that fixed point: at the fixed point, H1(Q*, μ*) = Q* makes the minimizer f* optimal for μ*, and H2(Q*, μ*) = μ* gives the invariant-measure consistency. No step in this chain assumes the mean-field equilibrium whose existence is the target; the cited existence results [30] and [35] are used only as background context, and the external MDP optimality results [19,20,31] are standard results with stated assumptions that do not include the present theorem. The paper does have a genuine correctness gap—the product space C × P(X) is never given an explicit complete metric, and W1 is only an extended metric on all of P(X)—but this is a completeness/rigor issue, not a circularity: the contraction estimates themselves are derived independently. Accordingly no circular step is identified.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper contains no data-driven or fitted numerical parameters. The constants M, alpha, L1, L2, K1, K2, KF, rho and the smallness conditions k<1, kappa<1 are model assumptions, not estimated quantities.

assumptions (4)

standard math Discounted and average-cost optimality results for MDPs (Bellman equation, ACOE) are taken as given from [19,20].
Invoked in Section 3.1 to identify optimal policies via Q-functions and in Section 3.2 for the average-cost optimality equation (ACOE).
domain assumption Assumption 1: c and p are Lipschitz in the mean-field argument and state, p is weakly continuous, A is convex, growth/drift condition (1) holds, and F is rho-strongly convex with KF-Lipschitz gradient.
These define the class of MFGs and are used in Lemmas 1-2 and Theorems 1-4 to keep H and L inside their domains and to derive Lipschitz bounds on the minimizing policy.
ad hoc to paper Assumption 2: the composite constant k in Section 3.1 is less than 1.
Imposed specifically so the MFE operator H is a Banach contraction; it couples the discount factor, drift, Lipschitz constants, and strong-convexity ratio, and is not derived from the model.
domain assumption Assumption 3: minorization p(.|x,a,mu) >= lambda(.), drift inequality with alpha<1, and composite constant kappa<1 for the average-cost case.
Standard ergodicity conditions (see [20, Theorem 7.3.11]) used to make the average-cost operator L a contraction and to justify the ACOE.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Value Iteration Algorithm for Mean-field Games." pith.science (2026). https://pith.science/paper/HTKUOADS

@misc{pith2026190901758,
  author       = {Pith},
  title        = {Pith review of: Value Iteration Algorithm for Mean-field Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HTKUOADS}},
  note         = {Machine review of arXiv:1909.01758}
}

abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 33 canonical work pages

[17]

Hadikhanloo and F.J.Silva

S. Hadikhanloo and F.J.Silva. Finite mean ﬁeld games: ﬁctitous play a nd convergence to a ﬁrst order continuous mean ﬁeld game. Journel de Math- ematiques Pures et Appliquees , 132:369–397, 2019

work page 2019
[1]

Achdou and A.Porretta

Y. Achdou and A.Porretta. Convergence of a ﬁnite diﬀerence sc heme to weak solutions of the system of partial diﬀerential equations arisin g in mean ﬁeld games. SIAM J. Numer. Anal. , 54(1):161–186, 2016

work page 2016
[2]

Achdou and I

Y. Achdou and I. Capuzzo-Dolcetta. Mean ﬁeld games: numerica l methods. SIAM J. Numer. Anal. , 48(3):1136–1162, 2010

work page 2010
[3]

Achdou, F.Camilli, and I

Y. Achdou, F.Camilli, and I. Capuzzo-Dolcetta. Mean ﬁeld games: c on- vergence of a ﬁnite diﬀerence method. SIAM J. Numer. Anal. , 51(5):2585– 2612, 2013

work page 2013
[4]

Achdou and M.Lauriere

Y. Achdou and M.Lauriere. Mean ﬁeld games and applications: nume rical aspects. arXiv:2003.04444, 2020

arXiv 2003
[5]

Adlakha, R

S. Adlakha, R. Johari, and G.Y. Weintraub. Equilibria of dynamic gam es with many players: Existence, approximation, and market structu re. Jour- nal of Economic Theory , 156:269–316, 2015

work page 2015
[6]

Almulla, R.Ferreira, and D.Gomes

N. Almulla, R.Ferreira, and D.Gomes. Two numerical approaches to staionary mean-ﬁeld games. Dyn Games Appl , 7:657–682, 2016

work page 2016
[7]

Bensoussan, J

A. Bensoussan, J. Frehse, and P. Yam. Mean Field Games and Mean Field Type Control Theory . Springer, New York, 2013

work page 2013

Show all 35 references

[8]

A. Biswas. Mean ﬁeld games with ergodic cost for discrete time Mar kov processes. arXiv:1510.08968, 2015

2015 arXiv
[9]

Bonnans and A

J.F. Bonnans and A. Shapiro. Perturbation Analysis of Optimization Prob- lems. Springer, New York, 2000

2000
[10]

Cardaliaguet

P. Cardaliaguet. Notes on Mean-ﬁeld Games . 2011. 21

2011
[11]

Carmona and F

R. Carmona and F. Delarue. Probabilistic analysis of mean-ﬁeld ga mes. SIAM J. Control Optim. , 51(4):2705–2734, 2013

2013
[12]

Elliot, X

R. Elliot, X. Li, and Y. Ni. Discrete time mean-ﬁeld stochastic linear - quadratic optimal control problems. Automatica, 49:3222–3233, 2013

2013
[13]

Gomes and J.Saude

D.A. Gomes and J.Saude. Numerical methods for ﬁnite-state me an-ﬁeld games satisfying monotonicity condition. Applied mathematics and opti- mization, 2018

2018
[14]

Gomes, J

D.A. Gomes, J. Mohr, and R.R. Souza. Discrete time, ﬁnite state space mean ﬁeld games. J. Math. Pures Appl. , 93:308–328, 2010

2010
[15]

Gomes and J

D.A. Gomes and J. Sa´ ude. Mean ﬁeld games models - a brief surve y. Dyn. Games Appl. , 4(2):110–154, 2014

2014
[16]

O. Guetant. New numerical methods for mean ﬁeld games with qu adratic costs. Networks and Heterogeneous Media , 7(2):315–336, 2012

2012
[18]

Hajek and M

B. Hajek and M. Raginsky. Statistical learning theory. Lecture Notes, 2019

2019
[19]

Hern´ andez-Lerma and J.B

O. Hern´ andez-Lerma and J.B. Lasserre. Discrete-Time Markov Control Processes: Basic Optimality Criteria . Springer, 1996

1996
[20]

Hern´ andez-Lerma and J.B

O. Hern´ andez-Lerma and J.B. Lasserre. Further Topics on Discrete-Time Markov Control Processes . Springer, 1999

1999
[21]

Hern´ andez-Lerma, R

O. Hern´ andez-Lerma, R. Montes-De-Oca, and R. Cavazos- Cadena. Recur- rence conditions for Markov decision processes with Borel state s pace: a survey. Ann. Oper. Res. , 28(1):29–46, 1991

1991
[22]

M. Huang. Large-population LQG games involving major player: T he Nash certainty equivalence principle. SIAM J. Control Optim. , 48(5):3318–3353, 2010

2010
[23]

Huang, P.E

M. Huang, P.E. Caines, and R.P. Malham´ e. Large-population cos t coupled LQG problems with nonuniform agents: Individual-mass behavior and de- centralized ǫ-Nash equilibria. IEEE. Trans. Autom. Control , 52(9):1560– 1571, 2007

2007
[24]

Huang, R.P

M. Huang, R.P. Malham´ e, and P.E. Caines. Large population stoc has- tic dynamic games: Closed loop McKean-Vlasov systems and the Nash certainty equivalence principle. Communications in Information Systems , 6:221–252, 2006

2006
[25]

Lasry and P.Lions

J. Lasry and P.Lions. Mean ﬁeld games. Japan. J. Math. , 2:229–260, 2007. 22

2007
[26]

Moon and T

J. Moon and T. Ba¸ sar. Discrete-time decentralized control u sing the risk- sensitive performance criterion in the large population regime: a mea n ﬁeld approach. In ACC 2015 , Chicago, Jul. 2015

2015
[27]

Moon and T

J. Moon and T. Ba¸ sar. Discrete-time mean ﬁeld Stackelberg ga mes with a large number of followers. In CDC 2016 , Las Vegas, Dec. 2016

2016
[28]

Moon and T

J. Moon and T. Ba¸ sar. Robust mean ﬁeld games for coupled Mar kov jump linear systems. International Journal of Control , 89(7):1367–1381, 2016

2016
[29]

Nourian and G.N

M. Nourian and G.N. Nair. Linear-quadratic-Gaussian mean ﬁeld g ames under high rate quantization. In CDC 2013 , Florence, Dec. 2013

2013
[30]

Saldi, T

N. Saldi, T. Ba¸ sar, and M. Raginsky. Markov–Nash equilibria in me an-ﬁeld games with discounted cost. SIAM Journal on Control and Optimization , 56(6):4256–4287, 2018

2018
[31]

Saldi, T

N. Saldi, T. Linder, and S. Y¨ uksel. Finite approximations in discrete-time stochastic control: Quantized models and asymptotic optim ality. Springer, Cham, 2018

2018
[32]

Tembine, Q

H. Tembine, Q. Zhu, and T. Ba¸ sar. Risk-sensitive mean ﬁeld gam es. IEEE. Trans. Autom. Control , 59(4):835–850, 2014

2014
[33]

C. Villani. Optimal transport: Old and New . Springer, 2009

2009
[34]

Wiecek and E

P. Wiecek and E. Altman. Stationary anonymous sequential gam es with undiscounted rewards. Journal of Optimization Theory and Applications , 166(2):686–710, 2015

2015
[35]

Discrete-time ergodic mean-ﬁeld games with avera ge reward on compact spaces

Piotr Wiecek. Discrete-time ergodic mean-ﬁeld games with avera ge reward on compact spaces. Dynamic Games and Applications , pages 1–35, 2019. 23

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [17]

Hadikhanloo and F.J.Silva

S. Hadikhanloo and F.J.Silva. Finite mean ﬁeld games: ﬁctitous play a nd convergence to a ﬁrst order continuous mean ﬁeld game. Journel de Math- ematiques Pures et Appliquees , 132:369–397, 2019

work page 2019

[2] [1]

Achdou and A.Porretta

Y. Achdou and A.Porretta. Convergence of a ﬁnite diﬀerence sc heme to weak solutions of the system of partial diﬀerential equations arisin g in mean ﬁeld games. SIAM J. Numer. Anal. , 54(1):161–186, 2016

work page 2016

[3] [2]

Achdou and I

Y. Achdou and I. Capuzzo-Dolcetta. Mean ﬁeld games: numerica l methods. SIAM J. Numer. Anal. , 48(3):1136–1162, 2010

work page 2010

[4] [3]

Achdou, F.Camilli, and I

Y. Achdou, F.Camilli, and I. Capuzzo-Dolcetta. Mean ﬁeld games: c on- vergence of a ﬁnite diﬀerence method. SIAM J. Numer. Anal. , 51(5):2585– 2612, 2013

work page 2013

[5] [4]

Achdou and M.Lauriere

Y. Achdou and M.Lauriere. Mean ﬁeld games and applications: nume rical aspects. arXiv:2003.04444, 2020

arXiv 2003

[6] [5]

Adlakha, R

S. Adlakha, R. Johari, and G.Y. Weintraub. Equilibria of dynamic gam es with many players: Existence, approximation, and market structu re. Jour- nal of Economic Theory , 156:269–316, 2015

work page 2015

[7] [6]

Almulla, R.Ferreira, and D.Gomes

N. Almulla, R.Ferreira, and D.Gomes. Two numerical approaches to staionary mean-ﬁeld games. Dyn Games Appl , 7:657–682, 2016

work page 2016

[8] [7]

Bensoussan, J

A. Bensoussan, J. Frehse, and P. Yam. Mean Field Games and Mean Field Type Control Theory . Springer, New York, 2013

work page 2013