Learning Mean-Field Games

• Repeated Ad auctions pose a large-population bidding problem with unknown click conversion, reward observed only after user activity, and advertiser budget constraints.The motivating question is how an advertiser should bid when the conversion and reward distributions are unknown.Source: §1 · p. 1
• GMF-Q outperforms existing multi-agent reinforcement-learning algorithms in convergence, stability, and learning accuracy on the repeated Ad auction problem.The paper also reports that GMF-Q is efficient and robust in convergence and learning.Source: §1 · p. 2
• Under appropriate technical conditions, the GMFG has a unique Nash equilibrium, while the proposed GMF-Q algorithm has convergence and computational-complexity analysis.Source: §1 · p. 2
• Prior work does not address simultaneous learning and decision-making in a general MFG while establishing global Nash-equilibrium existence and uniqueness and analyzing model-free convergence and complexity.The paper notes that global results are harder to obtain than local results.Source: §1 · p. 2

2.1 Background: classical N-player Markovian game and MFG

• Classical MFGs aggregate the states of a large population of interchangeable players to focus analysis on a representative player and make large stochastic games more tractable.Source: §2.1 · pp. 2–3

2.2 General MFG (GMFG)

• GMFG allows rewards and transitions to depend on the joint population state-action distribution and to be unknown, unlike the classical MFG setting described here.The GMFG solution pairs a player policy with a population flow satisfying individual optimality and population consistency.Source: §2.2 · p. 3

2.3 Example: GMFG for the repeated auction

• In the auction example, an advertiser's state is her budget, her action is her bid, and winning depends on game intensity and the population bidding distribution.The reward includes auction profit and a penalty for exceeding the budget; rewards and budget dynamics are unknown a priori.Source: §2.3 · pp. 3–4

• The proof combines individual optimization with population consistency and repeats the two steps until the population flow matches its update.The resulting mapping Γ is contractive under the W1 distance, allowing the Banach fixed-point theorem to establish existence and uniqueness.Source: §3 · pp. 4–5
• The analysis assumes regularity conditions, including feedback regularity for the individual optimization step and bounds on how policies and distributions affect the dynamics.The paper states that Assumption 2 can be reduced to Lipschitz continuity and boundedness of the transition dynamics.Source: §3 · pp. 4–5
• If Assumptions 1 and 2 hold and d1d2 + d3 < 1, the GMFG has a unique Nash equilibrium.Source: §3 · p. 5

4 RL Algorithms for (stationary) GMFGs

• The stationary setting supports a time-independent Q-learning algorithm for an infinite-horizon game, with the stationary and non-stationary cases requiring slightly different assumptions.The algorithm focuses on finite state and action spaces and stationary Nash equilibria.Source: §4 · p. 5
• For fixed L, the algorithm treats the problem as an infinite-horizon MDP and updates Q-values using rewards and the discounted maximum next-state Q-value.The section assumes access to a population simulator that returns a next state, reward, and next population distribution for a policy and L.Source: §4 · pp. 5–6
• Because argmax-e is discontinuous and can destabilize learning, GMF-Q uses a smooth Boltzmann policy whose gap from the optimal policy can be controlled through c.The section notes that other smoothing operators, such as Mellowmax, may also be considered.Source: §4 · p. 6
• The ϵ-net addresses potentially vanishing action gaps across population distributions, supporting a definite distinction between optimal and suboptimal actions in the convergence argument.The section relies on compactness of the probability simplex and finiteness of the action set for the net and gap bound.Source: §4 · p. 6

Algorithm 1 Q-learning for GMFGs (GMF-Q)

• GMF-Q alternates Q-learning for a fixed population distribution with a Boltzmann policy update, a simulator sample, and projection onto an ϵ-net.Softmax is applied after the approximate Q-function is obtained at each outer iteration; Q-learning runs within that iteration.Source: Algorithm 1 Q-learning for GMFGs (GMF-Q) · p. 6
• Theorem 2 establishes GMF-Q’s convergence to an ϵ-Nash and provides a complexity analysis under stated conditions.The theorem’s constant C is independent of δ, ϵ, and η.Source: Algorithm 1 Q-learning for GMFGs (GMF-Q) · p. 7

Performance evaluation in the GMFG setting

• The experiments use a repeated auction game in which each advertiser learns to bid subject to a budget constraint.The stated default setup uses |S| = |A| = 10 and 2,000 inner iterations.Source: §5 · p. 7

Learning accuracy of GMF-Q

• A relative Q-table distance of 0.098879 corresponds to 90-percent learning accuracy against GMF-V after 10,000 inner iterations.GMF-V is the special form that assumes the conversion-rate distribution and budget-state dynamics are known.Source: Figure 1 · p. 8, §5 · p. 8

Convergence and stability of GMF-Q

• GMF-Q converges after about 10 outer iterations, its error decreases with more inner iterations, and convergence is robust to changes in state count and initial population distribution.The experiments also report that the naive algorithm fails to converge even with 10,000 inner iterations, while the joint distribution continues to fluctuate.Source: §5 · p. 7, Figure 2 · p. 8, Figure 3 · p. 8

Performance evaluation in the GMFG setting

• GMF-Q converges faster than IL and MF-Q, with the smallest error and lowest variance; at N = 20, its error is 0.065 versus 0.101 for MF-Q and 0.220 for IL.As N increases, GMF-Q's error decreases while both baselines' errors increase; GMF-Q also remains robust as state and action dimensions grow.Source: Figure 5 · p. 9, §5 · p. 9

6 Conclusion

• The paper builds a GMFG framework for simultaneous learning and decision-making in large-population stochastic games.Source: §6 · p. 9
• The framework establishes existence and uniqueness of a Nash equilibrium.Source: §6 · p. 9
• The paper proposes GMF-Q, a Q-learning algorithm with convergence and complexity analysis, and reports superior experimental performance.Source: §6 · p. 9

A Distance metrics and completeness

• The ℓ1-Wasserstein distance has a coupling-based definition and an equivalent dual representation over 1-Lipschitz functions.The dual form follows from Kantorovich duality.Source: A Distance metrics and completeness · p. 12
• For compact X, W1 is bounded above by diam(X) times total variation distance, which is itself bounded by diam(X).For finite X, the minimum distance between distinct points is positive.Source: A Distance metrics and completeness · p. 12
• The paper’s metrics are distance functions and define complete metric spaces, enabling Banach fixed-point arguments for existence and uniqueness.For compact state and action spaces, the distances are finite for input distribution pairs.Source: A Distance metrics and completeness · p. 12

B Existence and uniqueness for stationary NE of GMFGs

• The stationary equilibrium requires both single-player optimality and a population state-action distribution that remains L⋆ under the policy’s dynamics.The population condition holds for all t ≥ 0.Source: B Existence and uniqueness for… · pp. 12–13
• The proof composes a policy best-response mapping with a population-update mapping and requires the combined mapping to be contractive under W1.The stated contraction condition is d1d2 + d3 < 1.Source: B Existence and uniqueness for… · p. 13
• Given Assumptions 3 and 4 and d1d2 + d3 < 1, the GMFG has a unique stationary Nash equilibrium.The result follows from Banach’s fixed-point theorem and completeness of the related metric spaces.Source: B Existence and uniqueness for… · p. 13

C Additional comments on assumptions

• For finite state and action spaces, the population-side assumptions can be characterized from boundedness and W1-Lipschitz continuity of the transition dynamics.The passage notes that c1 becomes smaller as transition dynamics become more diverse and the state space grows.Source: C Additional comments on assumptions · p. 14

D Proof of Theorems 1 and 4

• The proof presents the stationary case and states that Theorem 1 follows with appropriate notational changes.Source: D Proof of Theorems 1 and 4 · p. 15
• A stationary equilibrium is equivalent to a fixed point of Γ, with its policy given by Γ1(L).The proof identifies Γ(L) as Γ2(Γ1(L), L).Source: D Proof of Theorems 1 and 4 · p. 15
• The proof establishes a unique stationary GMFG solution when d1d2 + d3 ∈ [0, 1), by applying Banach’s fixed-point theorem.The contraction bound is derived for the composed mapping Γ.Source: D Proof of Theorems 1 and 4 · p. 15

E Proof of Theorem 2

• The softmax-to-argmax distance is bounded by 2n exp(−cδ), where δ is the gap between the maximum and next-highest entries.The proof also invokes softmax Lipschitz continuity and a Q-learning convergence lemma.Source: E Proof of Theorem 2 · p. 15
• The cited Q-learning result gives an ϵ-accurate optimal Q-function with probability at least 1 − 2δ under its step-size and bounded-covering-time conditions.The bound applies to the MDP Q-learning iterations used in the proof.Source: E Proof of Theorem 2 · p. 16
• The convergence proof selects Kϵ,η using a tolerance-dependent iteration bound and then relaxes η to 1 to obtain the stated result.The supplied passages do not show the resulting bound’s full expression.Source: E Proof of Theorem 2 · p. 17

F Naive algorithm

• The naive algorithm alternates Q-learning, a greedy policy choice, and a population update; its limitation is referred to elsewhere in the paper.The passage notes empirical verification of that limitation in Figure 4 but does not specify it here.Source: F Naive algorithm · p. 17, Algorithm 2 Alternating Q-learning for… · p. 17

G GMF-V

• GMF-V is a value-iteration version of GMF-Q for settings with known transition dynamics and rewards.It uses a softmax policy, updates the population distribution, and projects the update onto Sϵ.Source: G GMF-V · p. 18, Algorithm 3 Value Iteration for GMFGs… · p. 18

H.1 Competition intensity index M.

• M is implemented as the number of selected players in an auction competition, with M −1 randomly selected players competing against the representative advertiser.The auction literature also refers to M as auction thickness.Source: §H.1 · p. 18

H.2 Adjustment for Algorithm MF-Q.

• Unlike the joint-state assumption for all N players in [40], the experiment’s MF-Q adjustment bases each player’s decision on her private state and makes Qi a function of si and ai.The adjustment is made for computational efficiency and model comparability.Source: §H.2 · p. 18