Source-linked AI summary
Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning
Gunes Akbas, Naci Saldi, Berkay Anahtarci, Can Deha Kariksiz
TL;DR
The paper addresses the limited treatment of finite-state, finite-action mean-field games with population-dependent dynamics under the average-reward criterion. It develops span-seminorm contraction results for entropy-regularized control and uses them to compute and learn equilibria. Under stated contraction conditions, the equilibrium population is unique and fixed-point iteration converges geometrically, while simulator-based learning has finite-sample guarantees.
Problem
For finite-state, finite-action mean-field games with population-dependent dynamics, existing average-reward results do not provide the combined contraction, equilibrium-computation, and simulator-learning treatment considered here.
Source: §1.2 · p. 4Method
The paper replaces hard action maximization with entropy-regularized softmax optimization, uses full-kernel span-seminorm contractions, and combines soft Q-learning with empirical transition estimates.
Source: §2.3 · p. 7, §7 · p. 30Results
When K1 < ε and temperature exceeds an explicit threshold, the equilibrium population is unique and fixed-point iteration converges geometrically; soft Q-learning has temperature-independent finite-sample constants, and learned population and policy errors decrease with growing inner samples.
Source: §1.3 · p. 5Takeaways & Limitations
Relative value iteration and the learning algorithms require the minorization mass but not the minorizing measure, supporting model-free equilibrium computation from simulator samples.
Source: §1 · p. 2, §2.3 · p. 7The contraction result requires K1 < ε and temperature above an explicit threshold; when population dependence is too strong, the mean-field operator may be non-contractive and equilibrium need not be unique.
Source: §4.5 · p. 19
Abstract
from arXiv · showhide
We study stationary discrete-time mean-field games with finite state and action spaces under the average-reward criterion, with an entropy-regularized objective and population-dependent dynamics and rewards. Under a minorization condition, the soft Q-operator is a span-seminorm contraction for the full transition kernel, so relative value iteration does not require the minorizing measure. When the Lipschitz constant of the kernel is below the minorization mass and the temperature exceeds an explicit threshold, the equilibrium fixed-point operator is a contraction: an equilibrium exists, its population distribution is unique, and a fixed-point iteration converges to it geometrically. We then learn the equilibrium model-free from a simulator, combining soft Q-learning at a fixed population distribution with an empirical transition kernel. We prove a finite-sample bound for soft Q-learning in the span seminorm, with temperature-independent constants, and derive convergence rates for the learned population distribution and policy. A congestion-aware routing game illustrates the results.
1 Introduction
The paper studies entropy-regularized, average-reward mean-field games with population-dependent dynamics and rewards, where a representative agent responds to the population distribution. It develops contraction-based equilibrium computation and simulator-based learning under explicit conditions.
1 Introduction
- The introduction frames mean-field games through a representative agent whose optimal policy reproduces the population distribution as an equilibrium.For the cited models and criteria, limiting equilibria approximate Nash equilibria of large finite-player games; this paper does not study the finite-player game.Source: §1 · pp. 1–2
1.1 Background and related work
- Earlier work establishes average-reward equilibrium existence, while contraction and learning results for regularized games largely concern discounted or finite-horizon settings.Existing average-reward learning results cover unregularized games or discounted approximations, with some exceptions in specific models.Source: §1.1 · pp. 2–3
1.2 The gap addressed by this paper
- The paper addresses a gap for finite-state, finite-action average-reward games with population-dependent dynamics, combining soft-operator and population-update contractions with simulator-based learning guarantees.The algorithms use the minorization mass but do not require the minorizing measure.Source: §1.2 · p. 4
1.3 Main results and contributions
- Replacing the hard maximum with log-sum-exp preserves the soft Q-operator’s span-seminorm contraction rate and full kernel, so iteration needs no minorizing measure.The softmax map also has a population-dependence Lipschitz bound proportional to inverse temperature.Source: §1.3 · p. 4
- When K1 < ε and temperature exceeds an explicit threshold, the mean-field operator contracts, yielding an equilibrium with a unique population distribution and geometrically convergent fixed-point iteration.The equilibrium policy is the softmax policy at that distribution and is unique on its support.Source: §1.3 · p. 5
- At a fixed population, synchronous soft relative value Q-learning has span-seminorm mean-square error decaying inversely with iterations, with temperature-independent constants.The constants depend logarithmically on the number of state-action pairs and polynomially on the inverse minorization mass; the learned policy bound has an additional squared inverse-temperature factor.Source: §1.3 · p. 5
- Using learned soft Q-functions and an empirical transition kernel gives an inexact fixed-point iteration whose population and policy errors depend on geometric decay plus accumulated inner errors.Growing inner sample sizes yield convergence in expectation; geometrically growing sample sizes give geometric outer-iteration error decay, while constant sizes leave an error floor.Source: §1.3 · p. 5
1.4 Organization
- The paper proceeds from model and span-seminorm solution theory through entropy regularization, equilibrium contraction, learning analysis, and numerical experiments.Proofs for the first two sections are in appendices; later proofs are in the main text.Source: §1.4 · p. 5
2 Average-Reward MDPs and the Span-Seminorm Approach
The section sets up finite-state, finite-action average-reward control and uses minorization to obtain a span-seminorm contraction for the Q-operator built from the full transition kernel. Relative value iteration then solves the Q-AROE without requiring the minorizing measure in the algorithm.
2.1 Model, policies and notation
- Finite-state, finite-action MDPs use controlled transitions and one-stage rewards, and stationary Markov policies suffice for the criteria considered.The state process evolves according to the policy and controlled transition kernel.Source: §2.1 · p. 6
2.2 The average-reward criterion and its optimality equation
- Minorization makes the controlled chain ergodic under every policy, so average reward is independent of the initial state.The Q-AROE characterizes the optimal average reward; its Q-function is unique only up to an additive constant.Source: §2.2 · pp. 6–7
2.3 Minorization and the span-seminorm contraction
- The full-kernel Q-operator contracts in the span seminorm, while the minorizing measure is used in the proof but not the algorithm.The alternative residual-kernel contraction requires the minorizing measure explicitly, which is unavailable when the model is unknown.Source: §2.3 · p. 7
- Relative value iteration has a unique normalized fixed point, and its iterate differences converge to the optimal average reward.The normalized Q-function fixes one state-action value to zero; the average reward is obtained from iterate differences.Source: §2.3 · pp. 7–8
3 Entropy-Regularized MDPs and the Soft Q-AROE
Entropy regularization replaces hard action maximization with a smooth randomized best response while retaining a span-contractive Q-iteration. A softmax sensitivity bound supplies the population-dependence control used in the mean-field analysis.
3.1 The entropy-regularized problem and the softmax
- Entropy regularization replaces hard maximization with a strictly concave randomized-action problem whose softmax solution and log-sum-exp value are smooth.As temperature decreases to zero, the hard maximum is recovered.Source: §3 · p. 8, §3.1 · p. 9
3.2 The soft Q-AROE and its span-seminorm solution
- The soft Q-operator is span-seminorm contractive under the same condition and at the same rate as the classical operator, and its relative value iteration has a unique fixed point.Each iteration evaluates a log-sum-exp, and the optimal policy is obtained in closed form.Source: §3.2 · pp. 9–10
3.3 Lipschitz properties of the softmax
- The softmax is Lipschitz from the sup norm to the 1-norm with constant 1/δ, so higher temperature reduces best-response sensitivity to population changes.Composing this bound with the population-dependent Q-function bound makes the mean-field operator a contraction for sufficiently high temperature.Source: §3.3 · pp. 10–11
4 Entropy-Regularized Mean-Field Games
This section formulates a finite-state, stationary entropy-regularized mean-field game with population-dependent rewards and dynamics, and studies its equilibrium under uniform Lipschitz and minorization assumptions. When population sensitivity is sufficiently small and temperature high enough, the equilibrium operator is contractive, yielding a unique fixed point, geometrically convergent iterates, and a polynomial-time equilibrium algorithm.
4.1 Finite-state mean-field model
- The model has finite state and action spaces, population-dependent transitions and rewards, and an entropy bonus δH(π(· | x)) corresponding to a δ-strongly convex regularizer.The explicit softmax/log-sum-exp analysis gives a dimension-free Lipschitz constant 1/δ, rather than requiring general strongly convex regularizer machinery.Source: §4.1 · p. 12
4.2 Mean-field equilibrium
- A stationary mean-field equilibrium is a policy optimal at its population distribution together with a distribution invariant under the induced Markov chain, equivalently a fixed point of F.For each fixed population, the optimal policy is obtained from the entropy-regularized average-reward MDP.Source: §4.2 · pp. 12–13
4.3 Lipschitz assumptions
- Uniform population, state, and action regularity bounds the reward span by 2L1, while uniform minorization supplies mass ε across transitions for every population.These assumptions let the transition-kernel results apply uniformly over population distributions.Source: §4.3 · p. 13
4.4 Lipschitz continuity of 𝑄∗ 𝑚and 𝜋∗
- The optimal soft Q-function is Lipschitz in the population with a temperature-independent constant, while the softmax policy’s sensitivity scales with 1/δ.The policy bound uses softmax shift-invariance, which contributes a factor of 1/2 to the temperature threshold.Source: §4.4 · pp. 16–17
4.5 Banach contraction of the mean-field operator
- If K1 < ε and δ > K1C_Q/(2(ε−K1)), the mean-field operator is a strict contraction, yielding a unique equilibrium and geometrically convergent fixed-point iteration.The smallness condition on K1 is structural; the temperature threshold controls the remaining policy-sensitivity term.Source: §4 · p. 11, §4.5 · pp. 17–19
- The mean-field operator has a unique fixed point defining an equilibrium, and every equilibrium has the same population distribution and agrees with its canonical policy on that distribution’s support.The result holds when K1 < ε and δ satisfies (19), so that CF < 1.Source: §4.5 · p. 19
- From any initial population distribution, fixed-point iteration converges geometrically to the equilibrium distribution.The contraction rate is CF.Source: §4.5 · p. 19
4.6 Algorithmic interpretation
- The equilibrium algorithm runs in polynomial time in |S| and |A|, with soft Q-solving and population propagation as its model-dependent steps.Section 5 replaces those steps with soft Q-learning and an empirical kernel estimate.Source: §4.6 · p. 20
5 Model-Free Learning of the Mean-Field Equilibrium
This section develops a simulator-driven, model-free scheme for learning the mean-field equilibrium using soft Q-learning and empirical transition estimates. It characterizes finite-sample learning at a fixed population and shows how increasing the learning and sampling budgets drives the population distribution and policy toward equilibrium, with population error governed by a contraction recursion plus estimation error.
5 Model-Free Learning of the Mean-Field Equilibrium
- The model-free iteration replaces fixed-population soft Q-solving with simulator samples and population propagation with an empirical transition kernel.Each outer iteration uses |S||A|(n_k + N_k) simulator calls.Source: §5 · p. 20, §5.2 · p. 25
5.1 Synchronous soft Q-learning at a fixed population
- Minorization lets the analysis remove constant shifts and convert the span-seminorm contraction into a supremum-norm contraction, enabling finite-sample stochastic-approximation bounds without using ν in the learner’s algorithm.The learned quantities are relevant modulo constants because the softmax policy is unchanged by additive shifts of Q.Source: §5 · p. 20, §5.1 · p. 21
- Theorem 5.5 bounds synchronous soft Q-learning error in the span seminorm, with O(1/n) mean-square decay and constants independent of temperature; the policy bound depends on temperature at rate 1/δ^2.The constants depend on problem size through log(|S||A|) and on minorization mass through ε^-3.Source: §5.1 · p. 24
5.2 Learning the mean-field equilibrium
- Under K1 < ε and the temperature condition ensuring C_F < 1, Theorem 5.9 gives a convergence rate for the learned mean-field iteration toward the equilibrium population and policy.The fixed-point operator’s contraction yields a unique equilibrium population under these conditions.Source: §5 · p. 20, §5.2 · pp. 25–26
- The expected population error satisfies e_{k+1} ≤ C_F e_k + η̄_k, combining contraction with an additive estimation error.The proof propagates one-step learning errors, then uses the geometric sum to bound population error; the policy bound follows from the population bound.Source: §5.2 · pp. 27–28
- As n_k and N_k tend to infinity, the expected population error and policy error at every state tend to zero.This is the asymptotic sample-complexity guarantee under Theorem 5.9's assumptions.Source: §5.2 · p. 27
- For θ ∈ (C_F, 1), sufficient geometric sampling growth is n_k + n_0 ≥ c_1θ^-2k and N_k ≥ c_2θ^-2k, yielding geometrically decaying estimation error.The stated sample growth makes the aggregate error term decay geometrically, which gives a corresponding population-error bound; the policy statement follows from the population bound.Source: §5.2 · pp. 27–28
6 Numerical Experiments
The experiments apply the deterministic and model-free methods to a congestion-aware routing game, checking their behavior against the paper’s predicted convergence rates.
6.1 The model as a network-congestion game
- The routing game has good/bad connection states and stable/cheap routes, with congestion m_B affecting both transition probabilities and rewards.The transition and reward specifications depend on the fraction of users experiencing a bad connection.Source: §6.1 · p. 28
- For the instance, K1 = 0.20 < ε = 0.68 and δ = 2.0 > δ★ ≈ 0.793, yielding a strict mean-field contraction with modulus C_F ≈ 0.71.These parameter conditions satisfy the stated hypotheses for the contraction result.Source: §6.1 · p. 28
6.2 Mean-field equilibrium
- The deterministic Banach iteration reaches the exact equilibrium to numerical tolerance in 20 outer iterations.The reported equilibrium average reward is 1.7076, with stable/cheap route probabilities reported separately for good and bad states.Source: §6.2 · p. 28, Table 2 · p. 29
6.3 Model-free learning
- The soft Q-learning span error eventually decays at 1/n, with least-squares slopes of −0.88 and −0.93 for the two step-size offsets.Panel (a) evaluates learning at the equilibrium population; the figure marks a proportional-to-1/n reference line.Source: §6.3 · p. 29, Figure 1 · p. 30
- With constant inner budgets N_k ∈ {10^2, 10^3, 10^4} and n_0 = 100, the model-free iteration first tracks the exact iteration’s geometric decay, then settles at floors approximately 4 × 10−2, 1.2 × 10−2, and 3.7 × 10−3.Source: §6.3 · p. 29
- Geometrically growing inner budgets remove the error floor, with population error decreasing geometrically in outer iteration k at a rate consistent with θ^k for θ = 0.8.Panel (c) uses n_k = N_k = ⌈bθ^−2k⌉ and compares two values of b.Source: §6.3 · p. 30, Figure 1 · p. 30
7 Conclusion
The paper establishes span-seminorm contraction for the entropy-regularized average-reward control problem and uses it to obtain equilibrium and learning results for mean-field games. Its conditions yield a unique equilibrium population and geometric fixed-point convergence, while the model-free method has finite-sample and population/policy convergence guarantees.
7 Conclusion
- Replacing hard action maximization with entropy-penalized stochastic policies yields a soft Q-operator that contracts in span seminorm under the classical minorization condition, without using the minorizing measure.The log-sum-exp value inherits the one-Lipschitz property of the hard maximum; the soft optimality equation has solutions unique up to an additive constant and is iteratively computable.Source: §7 · p. 30
- When K1 < ε and temperature is sufficiently high, the mean-field operator contracts; synchronous soft Q-learning and an empirical kernel then provide model-free equilibrium learning with finite-sample and population/policy convergence guarantees.The inner mean-square bound is O(1/n), with logarithmic dependence on state-action space size, and the routing experiments confirm the results.Source: §7 · p. 30
A.1 Proof of Theorem 2.4
The proof sets up a comparison of two action-value functions and bounds the difference between their action maxima using pointwise extrema.
A.1 Proof of Theorem 2.4
- The proof defines Φ as the difference between Q and Q′ and Φ_max as the difference between their actionwise maxima.These quantities organize the comparison for each state-action pair.Source: §A.1 · p. 31
- The difference of two maxima is bounded above by the maximum pointwise difference and below by its minimum.The proof applies these inequalities to the action-value functions.Source: §A.1 · p. 31
- The proof then concludes after applying those bounds to the span comparison.The supplied proof passage ends with the theorem proof’s completion.Source: §A.1 · p. 31
A.2 Proof of Corollary 2.5
The appendix derives the normalized soft optimality equation’s fixed point and convergence from contraction, then bounds exponential weight changes through a uniform value difference.
A.2 Proof of Corollary 2.5
- Contraction of L in span seminorm makes the normalized operator eL contractive on R^(S×A), giving a unique fixed point Q*.The proof then defines ρ* from LQ* at a reference state-action pair to recover the Q-AROE.Source: §A.2 · p. 31
- The proof uses contraction to show successive increments have vanishing span, then applies normalization to establish uniform convergence of the iterates.The limiting normalized iterate is the fixed point Q*.Source: §A.2 · p. 31
B.1 Proof of Lemma 3.3
- For the exponential-weight bound, a uniform value difference M bounds each exponentiated weight between factors exp(−M/δ) and exp(M/δ).Summing the weights preserves these multiplicative bounds.Source: §B.1 · p. 32
B.2 Proof of Theorem 3.5
The appendix proofs use log-sum-exp order and shift properties to bound span variation, establish normalized-iteration behavior, and derive softmax calculus bounds.
B.2 Proof of Theorem 3.5
- The log-sum-exp preserves the pointwise bounds on Q, while the shared term independent of state and action cancels in the span argument.These steps support the span bound in the proof of Theorem 3.5.Source: §B.2 · p. 32
B.3 Proof of Corollary 3.6
- The normalized operator remains a span contraction, and the iterates’ successive differences become asymptotically independent of state and action.The proof also identifies the normalized fixed point as solving the soft Q-AROE.Source: §B.3 · p. 33
B.4 Proof of Lemma 3.8
- The softmax is the gradient of log-sum-exp, whose Hessian entries are derived and identified with equation (8).The proof defines log-sum-exp through the partition sum and the softmax through normalized exponentials.Source: §B.4 · p. 33
B.5 Proof of Lemma 3.10
- The proof bounds the relevant matrix norm by reducing the maximization to cube extreme points and using 4α(1 − α) ≤ 1.The quadratic term reaches its maximum at α = 1/2.Source: §B.5 · p. 34
B.6 Proof of Corollary 3.11
The proof applies the simplex bound to the softmax probability vector when controlling the Hessian of log-sum-exp.
B.6 Proof of Corollary 3.11
- Because the softmax vector lies in the simplex, Lemma 3.10 supplies the norm bound used in the Hessian argument.The passage applies the bound to M(σδ(z)).Source: §B.6 · p. 34
B.7 Proof of Lemma 3.12
The proof uses the softmax gradient representation and shift invariance to establish the stated bounds for changes in softmax probabilities.
B.7 Proof of Lemma 3.12
- The softmax is the gradient of a C2 function, allowing the proof to integrate its Hessian along the segment between z′ and z.The resulting bound uses the 1-norm and Corollary 3.11.Source: §B.7 · p. 34
- Shift invariance of softmax lets the proof express its bound using the sup norm after subtracting an arbitrary constant shift.The passage states that the minimizing shift is c* = 1…; the expression is truncated in the supplied text.Source: §B.7 · p. 34