PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Model Free Learning in Mean Field Games

Romuald Elie, Julien Pérolat, Mathieu Laurière, Matthieu Geist, Olivier Pietquin

arXiv:1907.02633v3math.OCcs.LGstat.ML

TL;DR

Learning in large multi-agent populations is challenging because the environment changes as agents learn, while much model-free mean field game research addresses stationary settings and specific algorithms. This paper analyzes approximate fictitious play with general single-agent learning steps, bounding error propagation and establishing convergence results, with a deep-RL numerical illustration.

  • Problem

    Experience-based learning in large multi-agent systems faces a changing environment, while existing model-free mean field game studies focus on stationary settings and particular reinforcement-learning algorithms.

    Source: §1 · p. 1

  • Method

    The paper studies model-free fictitious play with any single-agent learning algorithm at each step and analyzes how approximate best-response errors propagate.

    Source: §1 · p. 2

  • Results

    The analysis relates convergence to the iteration-level learning errors, and a deep-RL illustration shows empirical convergence in a larger setting, including a mean field game that is not first order.

    Source: §4.2 · p. 5, §5 · p. 6

  • Takeaways & Limitations

    The framework provides a general convergence analysis for model-free fictitious play in mean field games, including non-stationary settings and varied single-agent learning procedures.

    Source: §1 · p. 2, §7 · p. 7

    Exact equilibrium convergence requires sufficiently rapid best-response approximation, a guarantee the paper identifies only for tabular settings with finite state and action spaces.

    Source: §4.3 · p. 5

Abstract

from arXiv · show

Learning by experience in Multi-Agent Systems (MAS) is a difficult and exciting task, due to the lack of stationarity of the environment, whose dynamics evolves as the population learns. In order to design scalable algorithms for systems with a large population of interacting agents (e.g. swarms), this paper focuses on Mean Field MAS, where the number of agents is asymptotically infinite. Recently, a very active burgeoning field studies the effects of diverse reinforcement learning algorithms for agents with no prior information on a stationary Mean Field Game (MFG) and learn their policy through repeated experience. We adopt a high perspective on this problem and analyze in full generality the convergence of a fictitious iterative scheme using any single agent learning algorithm at each step. We quantify the quality of the computed approximate Nash equilibrium, in terms of the accumulated errors arising at each learning iteration step. Notably, we show for the first time convergence of model free learning algorithms towards non-stationary MFG equilibria, relying only on classical assumptions on the MFG dynamics. We illustrate our theoretical results with a numerical experiment in a continuous action-space environment, where the approximate best response of the iterative fictitious play scheme is computed with a deep RL algorithm.

1 Introduction

Large interacting populations make experience-based learning difficult both because agents change the environment as they learn and because many-agent algorithms may not scale. The paper studies model-free fictitious play for mean field games, including non-stationary settings and approximate best responses.

1 Introduction

  • Learning in multi-agent systems is difficult because the environment’s dynamics evolve as the population learns, while large populations such as swarms challenge the scalability of learning algorithms.The paper uses the infinite-population mean field limit as a modeling simplification for anonymous identical agents.Source: §1 · p. 1
  • Mean field games model anonymous identical agents through the asymptotic infinite-population limit, where an equilibrium matches a representative agent’s best response to the population flow with the flow that policy induces.For many finite-player games, a mean field Nash equilibrium provides an approximate Nash equilibrium.Source: §1 · p. 1
  • Recent model-free MFG learning work focuses on stationary games and specific algorithms, including Q-learning, fictitious play, and policy gradients.Some contributions rely on assumptions described as hardly verifiable.Source: §1 · pp. 1–2
  • The paper analyzes approximate fictitious play with any single-agent learning algorithm, tracking how iteration-level approximation errors affect convergence in possibly non-stationary MFGs.Its numerical illustration computes approximate best responses with deep RL in a continuous state-action environment.Source: §1 · p. 2

2 Background

The background formulates a discrete-time mean field game through a representative agent interacting with a population distribution flow. An equilibrium requires both an optimal response to that flow and consistency between the flow and the policy-induced population.

2 Background

  • A mean field game represents the infinite-population limit of a differential game with identical, indistinguishable agents, and this paper uses discrete time to connect its presentation with learning.Only the distribution of states matters in the limit, rather than individual interactions.Source: §2 · p. 2
  • A population flow is a time-indexed sequence of state distributions, and each agent’s transition dynamics depend on its state, action, and the population distribution at that time.The population term represents the whole distribution, not merely the average state.Source: §2 · p. 2
  • A representative agent chooses a feedback policy to maximize expected reward while interacting with the population flow, which affects its rewards.Because agents are anonymous, the relevant interaction is through the aggregate state distribution.Source: §2 · pp. 2–3
  • A mean field Nash equilibrium requires the policy to be a best response to the population flow and the policy-induced state distribution to coincide with that flow.Computing an exact best response can be difficult, motivating iterative learning with approximate responses.Source: §2 · p. 3

3 Fictitious Play Algorithms for MFG

The section sets out fictitious play for mean field games and how approximate best responses generate an iteration-level error. It defines exploitability as a measure of equilibrium quality and gives conditions under which approximate or exact equilibrium follows.

3 Fictitious Play Algorithms for MFG

  • Fictitious play has agents update beliefs from empirical frequencies of previously observed strategies and play best responses to those beliefs.Its convergence is not guaranteed in general games, though it has been proved for some classes of mean field games.Source: §3 · p. 3
  • At each iteration, agents may use an approximate best response instead of the exact response, producing an average learning loss whose propagation through fictitious play is analyzed.The framework permits any learning procedure for the intermediate step, with a separate discussion of single-agent RL approximations.Source: §3 · p. 3
  • The aggregate policy randomizes uniformly over previous approximate best responses, and its associated population flow is used to assess the resulting approximate equilibrium.The algorithm updates the population-flow estimate iteratively.Source: §3 · pp. 3–4
  • Exploitability measures an agent’s expected gain from switching from the current belief policy to the exact best response against the current population flow.It quantifies the quality of the current policy-flow pair as a mean field Nash equilibrium.Source: §3 · p. 4
  • If exploitability is at most ϵ^2, the policy-flow pair is an (ϵ, ϵ)-mean-field Nash equilibrium; if exploitability vanishes, any accumulation point of the population flow is a mean field Nash equilibrium.The approximate equilibrium notion allows an ϵ-optimal policy for at least a fraction 1−δ of the population.Source: §3 · p. 4

4 Error propagation & Nash equilibrium approximation for first order MFG

For first-order MFGs, the section relates approximate fictitious-play equilibrium quality to per-iteration learning errors, then gives finite and asymptotic convergence conditions. Its RL discussion considers whether existing methods can meet those conditions.

4.1 First order mean field game

  • The analysis focuses on first-order games without dynamics noise, where agents control their state increments and monotone rewards support uniqueness of the MF Nash equilibrium.The discussion also notes that similar results should hold for second-order games with a potential structure.Source: §4 · p. 4, §4.1 · p. 4

4.2 Error propagation in the Fictitious Play algorithm

  • Theorem 6 bounds exploitability after n fictitious-play iterations using accumulated learning errors and distances between mean-field flows generated by approximate and exact best responses.Averaging the learning errors gives one bound but requires stronger control of the Wasserstein distance; an alternative is slower and requires weaker regularity of the approximate best response.Source: §4.2 · p. 5
  • Under Assumption 1, controlled errors yield a finite-iteration (ε, ε)-MF Nash equilibrium and convergence to the unique MF Nash equilibrium under either stated condition.The two asymptotic conditions are continuity of the update in d1 with nℓn → 0, or convergence to zero of the learning and policy-approximation errors.Source: §4.2 · p. 5

4.3 Discussion on the convergence for Best Response RL approximation

  • Speedy Q-learning can meet the required error decay with O(ln(K)n^(2α)/(1−γ)^4) steps when α > 1, but existing results do not ensure d1-continuity or policy proximity.The paper notes arbitrary-precision, high-probability guarantees only in the tabular setting; regularized MDPs may provide unique policies but bias Nash equilibria.Source: §4.3 · pp. 5–6

5 Numerical illustration

The numerical illustration applies model-free fictitious play with deep RL to a continuous state-action MFG. Its learned distributions and controls approach the benchmark as iterations increase.

Numerical illustration

  • A stylized congestion MFG with continuous states and actions provides a proof of concept, with empirical convergence even outside the first-order setting of the theory.The approximation combines Algorithm 1 with DDPG.Source: §5 · p. 6

Environment

  • Agents move on a periodic unit torus with control-driven drift and noise, and a continuous-time ergodic closed-form solution supplies an error benchmark.The benchmark is available for γ = 1; the discrete-time learned case uses γ = 0.95 and Δt = 0.05.Source: §5 · p. 6, Figure 1 · p. 7

Implementation

  • The implementation uses DDPG and adds 3,000 trajectories of length 1,000 to the replay buffer at each fictitious-play iteration.The reported training also runs 30,000 DDPG trajectories of length 300.Source: §5 · pp. 6–7

Results

  • The L2 errors between learned and benchmark distributions and controls decrease across fictitious-play iterations, illustrating numerical convergence.The comparison is approximate: the learned case uses γ = 0.95 in discrete time, while the explicit solution uses γ = 1 in continuous time.Source: §5 · p. 7, Figure 1 · p. 7

6 Related work

Prior model-free MFG studies analyze particular RL algorithms, mostly in stationary settings and finite state-action examples. The paper distinguishes its general analysis and continuous state-action illustration from that work.

Model-free MFG learning

  • Earlier model-free MFG analyses study Q-learning, fictitious play, or policy gradients, but focus on stationary settings and particular algorithms.Their convergence assumptions are described as often hard to verify, and their numerical examples use finite state-action sets.Source: §6 · p. 7

Other related work

  • Other related work includes mean-field approximation through empirical mean actions, inverse RL, and model-based learning, including decentralized deep fictitious play for selected linear-quadratic examples.The paper contrasts its own numerical example in a continuous state-action setting with prior finite state-action illustrations.Source: §6 · p. 7

7 Conclusion and future research

The paper presents a general convergence analysis for model-free fictitious play, including non-stationary settings, and illustrates it with continuous state-action deep RL. It identifies Wasserstein control of best-response approximation and decentralized convergence as future research directions.

Conclusion

  • The analysis covers model-free fictitious play with any single-agent learning algorithm and non-stationary settings, reducing convergence to per-iteration error analysis.For RL, that error analysis aggregates repeated supervised-learning approximation errors.Source: §7 · p. 7
  • The authors state that their theoretical setting uses reasonable, verifiable assumptions and motivates asymptotic mean-field approximation for learning in large multi-agent systems.Source: §7 · p. 7
  • A continuous state-action deep-RL experiment illustrates convergence of the model-free fictitious-play scheme.Source: §7 · p. 7

Future research

  • The analysis suggests faster convergence when best-response quality is controlled in Wasserstein distance, while deriving such RL estimates and analyzing decentralized convergence remain future work.Source: §7 · p. 7

Appendix

The appendix collects technical proofs for error propagation in approximate fictitious play and recalls the distance and compactness assumptions used in the analysis.

Proofs

  • The appendix gathers proofs of the error-propagation bounds for the approximate fictitious-play algorithm in Theorem 6.Some arguments draw on results for exact fictitious play.Source: Appendix · p. 9

Notation and assumptions

  • With b(x, a, µ) = a and compact action set A, the product state space X^T is compact and bounded.X denotes the set of accessible states before time T.Source: Appendix · p. 9

Distance

  • The appendix measures proximity between mean-field population flows using the 1-Wasserstein distance d1, defined through Kantorovich-Rubinstein duality.The dual functions are 1-Lipschitz on X^T.Source: Appendix · p. 9

A. Stability of the FP mean field flow (¯µ(n))n

The stability result shows that consecutive elements of the learned mean-field flow sequence become close in the d1 distance.

B. Propagation error estimates

The propagation-error analysis derives the theorem’s bounds by relating reward-function regularity and changes in mean-field flows to learning errors. The appendices also specify the fictitious-play and DDPG algorithms and a classification-based density approximation.

B. Propagation error estimates

  • Assumption 1 and compactness yield a Lipschitz bound on reward differences as mean-field flows change, which is used to derive estimates (8) and (7).The proof controls the approximate learning error and relates it to the total error through en = ℓn + ˆen.Source: B. Propagation error estimates · pp. 10–11
  • Best-response continuity and stability of the learned flow make the distance between consecutive best-response flows tend to zero, supporting the remaining propagation-error estimate.The proof combines this convergence with Lemma 9.Source: B. Propagation error estimates · p. 11

C. Algorithms

  • Exact fictitious play iteratively computes a best-response policy against the current mean-field flow; DDPG uses actor and critic networks with replay-buffer updates.The DDPG pseudocode includes action selection with exploration noise, transition storage, minibatch sampling, policy updates, and target-network updates.Source: C. Algorithms · p. 12

D. Approximation of the density

  • Density estimation classifies states into partition intervals and trains a function to estimate interval membership by minimizing cross-entropy loss.The state dataset is divided into Nclasses intervals.Source: D. Approximation of the density · p. 12

E. Additional numerical results

Figure 2 juxtaposes an explicit continuous-time policy with a numerically estimated discrete-time policy distribution. The comparison uses γ = 1 for the continuous-time solution and γ = 0.95 with ∆t = 0.05 for the learned discrete-time policy.

Loading 1907.02633v3…