PaperlayerView exact revision on arXiv

Source-linked AI summary

Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications

Sarah Perrin, Julien Perolat, Mathieu Laurière, Matthieu Geist, Romuald Elie, Olivier Pietquin

arXiv:2007.03458v2math.OCcs.AI

TL;DR

Large-population MFG learning is difficult, and much prior work assumes full knowledge of game dynamics and rewards. This paper analyzes continuous-time Fictitious Play across finite-horizon, discounted, and common-noise settings; it reports O(1/t) exploitability decrease and uses exploitability to assess learned controls.

  • Problem

    Much MFG literature assumes the representative player knows the game dynamics and rewards, while deterministic approximation schemes face scalability limits.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes continuous-time Fictitious Play, computing best responses to distributions induced by averaged past responses, across MFG settings including common noise.

    Source: §1 · p. 2, §2 · p. 3, §5 · p. 6

  • Results

    Exploitability decreases at O(1/t) in the studied MFG settings, and model-based and model-free instances learn near-optimal controls in the reported experiments.

    Source: §9 · p. 9

  • Takeaways & Limitations

    Exploitability can monitor learned-control quality and characterize convergence toward Nash equilibrium in MFGs.

    Source: §9 · p. 9, Broader Impact · p. 10

    Exploitability’s absolute value is not meaningful across games because it scales with rewards and is game-dependent.

    Source: §2 · p. 3

Abstract

from arXiv · show

In this paper, we deepen the analysis of continuous time Fictitious Play learning algorithm to the consideration of various finite state Mean Field Game settings (finite horizon, $\gamma$-discounted), allowing in particular for the introduction of an additional common noise. We first present a theoretical convergence analysis of the continuous time Fictitious Play process and prove that the induced exploitability decreases at a rate $O(\frac{1}{t})$. Such analysis emphasizes the use of exploitability as a relevant metric for evaluating the convergence towards a Nash equilibrium in the context of Mean Field Games. These theoretical contributions are supported by numerical experiments provided in either model-based or model-free settings. We provide hereby for the first time converging learning dynamics for Mean Field Games in the presence of common noise.

1 Introduction

Mean Field Games (MFGs) make large-population strategic interactions tractable by modeling players through the distribution of their states. This paper develops scalable simulation-based Fictitious Play, analyzes its convergence, and studies settings that include common noise.

1 Introduction

  • MFGs reduce large-population interactions to a representative player responding to the population state distribution.Players are modeled as identical, anonymous, and symmetrically interested.Source: §1 · p. 1
  • Deterministic approximations based on coupled dynamical equations face scalability limits, motivating stochastic neural-network methods for MFGs.The cited stochastic approaches use optimality conditions, control formulations, or variational methods.Source: §1 · pp. 1–2
  • The paper studies simulation-based Fictitious Play and proves O(1/t) convergence for finite-horizon or γ-discounted monotone MFGs.It also treats common noise and emphasizes exploitability as a convergence metric.Source: §1 · p. 2

2 Background on Finite Horizon Mean Field Games

The background formulates finite-horizon MFGs through a representative player's policy, rewards, and population distribution. It defines exploitability as a measure of the gain from deviating, then presents Fictitious Play as iterative best response to the distribution induced by averaged past responses.

2 Background on Finite Horizon Mean Field Games

  • A finite-horizon MFG models a representative player's state, action, transition, reward, and policy in relation to the population distribution.The player's cumulative reward depends on the sequence of policies and population distributions.Source: §2 · p. 2
  • Exploitability measures the gain from replacing a policy with a best response while the population continues using that policy.A Nash equilibrium has zero exploitability; a small value indicates an approximate equilibrium.Source: §2 · p. 3
  • Exploitability averages over state-process trajectories, unlike related evaluations over all starting states that can overweight rarely visited states.Its absolute value scales with rewards, so the paper recommends comparing it with a reference value rather than interpreting it across games.Source: §2 · p. 3
  • Monotone games impose a Lasry-Lions condition on how rewards vary with population distributions, a condition used to ensure Nash-equilibrium uniqueness.The reward separates into a state-action component and a population-dependent component.Source: §2 · p. 3
  • Fictitious Play iteratively computes a best response to the population distribution induced by the average of past best responses.Best responses and population distributions may be computed with model-based or model-free algorithms.Source: §2 · p. 3

3 Continuous Time Fictitious Play in Mean Field Games

The paper defines a continuous-time Fictitious Play process by extending the discrete-time scheme, with an arbitrary initial policy over the first unit of time. Under monotonicity, exploitability is a strong Lyapunov function, and continuous-time analysis provides tools for deriving the stated convergence rate.

3 Continuous Time Fictitious Play in Mean Field Games

  • For t < 1, the continuous-time process starts from a fixed, arbitrarily chosen policy before its dynamics are defined for t ≥ 1.The process is introduced as a continuous-time version of discrete-time Fictitious Play.Source: §3 · p. 4
  • The population distribution in the process is induced by the averaged policy, which is defined from the best-response policies over time.The paper presents the policy and distribution definitions in integral form as well as their time-dependent forms.Source: §3 · p. 4
  • Under the monotony assumption, exploitability φ(π̄_t) is a strong Lyapunov function of the system, with dφ(π̄_t)/dt ≤ −1 for every t ≥ 1.Source: §3 · p. 4
  • The paper uses continuous-time analysis to derive a convergence rate; for discrete time, it conjectures O(t^-1) convergence for monotone MFGs.The discrete-time rate is presented as a conjecture, not as the theorem established by the continuous-time analysis.Source: §3 · p. 4

4 Experiments on Fictitious Play in the Finite Horizon Case

The finite-horizon experiments compare model-based and model-free Fictitious Play in linear-quadratic and beach-bar games. Both approaches approximate the expected population behavior, while model-based exploitability decreases at about O(1/t) and faster than model-free exploitability in the reported settings.

4.1 Linear Quadratic Mean Field Game

  • The linear-quadratic experiment uses 100 states and a 30-step horizon, with model-based backward induction and exact population dynamics compared against model-free Q-learning and sampled dynamics.The game has a closed-form solution in its continuous-state-and-action version.Source: §4 · p. 4, §4.1 · p. 5
  • In the linear-quadratic game, model-based exploitability decreases at a rate close to O(1/t), while model-free exploitability decreases more slowly.Both methods approximate the movement of two separated bell-shaped populations toward a unique bell-shaped distribution.Source: §4.1 · p. 5, Figure 1 · p. 5

4.2 The Beach Bar Process

  • The beach-bar process is a discrete-state, discrete-action game on a one-dimensional beach, where players seek the bar but avoid crowded areas.The experiment uses 100 states and a 15-step horizon; its behavior can be analyzed intuitively despite lacking a closed-form solution.Source: §4.2 · pp. 5–6
  • In the beach-bar game, backward induction converges at O(1/t) and faster than Q-learning, as exploitability measures closeness to Nash equilibrium.Both algorithms converge toward a peaky distribution near the bar, with players moving away when it is crowded.Source: §4.2 · p. 6, Figure 3 · p. 6

5 Finite Horizon Mean Field Games with Common Noise

The common-noise formulation makes rewards, transitions, policies, and population distributions depend on a shared sequence of random events. Its continuous-time Fictitious Play process updates against best responses, and under monotonicity exploitability is a strong Lyapunov function.

5 Finite Horizon Mean Field Games with Common Noise

  • Common noise affects both rewards and transition probabilities, and policies and population distributions are conditioned on the shared noise sequence.The representative player’s expected return and exploitability are defined in this noise-conditioned setting.Source: §5 · pp. 6–7
  • For each noise history, continuous-time Fictitious Play forms its policy from best responses against the evolving average population distribution.The process defines the best-response distribution and the distribution induced by the current policy.Source: §5 · p. 7
  • Under the monotonicity assumption, exploitability is a strong Lyapunov function of the system for t ≥ 1.Source: §5 · p. 7

6 Experiments with Common Noise

The common-noise experiments test linear-quadratic and beach-bar games. In the linear-quadratic setting the population mean follows the noise sequence, while in the beach-bar setting players anticipate possible closure; model-based exploitability decreases at O(1/t) in the linear-quadratic experiment and faster than model-free exploitability in both reported settings.

6.1 Linear Quadratic Mean Field Game

  • The linear-quadratic experiment adds stationary i.i.d. common noise to the idiosyncratic noise, and its population first moment is conditioned on the common-noise sequence.The common-noise parameter is set to ρ = 0.5.Source: §6.1 · p. 7
  • In the linear-quadratic common-noise experiment, both methods approximate the exact solution, and model-based exploitability decreases at O(1/t) while model-free exploitability decreases more slowly.The separated bell-shaped distributions reassemble and their mean follows successive common noises.Source: §6.1 · p. 7, Figure 4 · p. 7

6.2 The Beach Bar Process

  • In the beach-bar environment, closure can occur at only one time step, producing either an open-bar or closed-bar realization and a reward that depends on the common noise.Source: §6.2 · p. 8
  • In the beach-bar game with closure probability 0.5, players anticipate closure as density near the bar declines before common noise; both approaches converge to Nash equilibrium by exploitability, with model-based learning faster.After common noise, the distribution becomes uniform if the bar has closed, or people return next to the bar if it stays open.Source: §6.2 · p. 8

7 Experiment at Scale

The scale experiment models a crowd moving through a 100 × 100 maze toward its center, with a reward that also penalizes crowded areas. The figure presents the population distribution’s evolution and exploitability.

7 Experiment at Scale

  • The crowd-modeling experiment encourages players on a 100 × 100 grid to move through a maze toward its center.The initial distribution is concentrated around a point near a maze corner and is zero on obstacles.Source: §7 · p. 8
  • The reward combines distance to the grid center with an aversion term for crowded areas.Source: §7 · p. 8
  • Figure 6 presents both the population distribution’s evolution and exploitability for the 2D crowd-modeling example.Source: §7 · p. 8, Figure 6 · p. 8

8 Related Work

Prior MFG work established theoretical results and numerical solution methods, while learning methods face scaling and convergence challenges. The paper positions continuous-time Fictitious Play as extending prior results to common-noise and time-dependent settings with an explicit convergence rate.

Theoretical results in MFGs

  • MFG theory includes existence, uniqueness, and stability results, while common-noise games have been addressed with PDE and probabilistic numerical methods.Finite-state and discounted-cost MFGs are also represented in prior work.Source: §8 · p. 9

Learning in games and MFGs

  • Independent learning can scale at least linearly with player count, and some methods scale exponentially; recent model-free MFG convergence results require strong hypotheses.The paper’s method can use model-free or model-based algorithms and relies on Lasry-Lions monotonicity rather than potential or variational structure.Source: §8 · p. 9
  • Prior model-free Fictitious Play work studied a restricted stationary setting and relied on hardly verifiable assumptions.That work also contained inaccuracies noted by.Source: §8 · p. 9
  • Earlier approximate-Fictitious-Play convergence analysis [54] covered discrete-time, first-order MFGs without common noise and gave no convergence rate.This paper analyzes continuous-time dynamics with idiosyncratic and common randomness and time-dependent games, with rate O(1/t).Source: §8 · p. 9

9 Conclusion

The paper presents Fictitious Play as a practical basis for solving finite-horizon, γ-discounted, and common-noise MFGs. It proves an O(1/t) decrease in exploitability and reports near-optimal controls and intended population behavior across its tested settings.

9 Conclusion

  • Across finite-horizon, γ-discounted, and common-noise MFGs, Fictitious Play yields exploitability decreasing at O(1/t).The paper presents this as a basis for practical algorithms and uses exploitability to monitor control quality during learning.Source: §9 · p. 9
  • Backward Induction and Q-Learning instances learned near-optimal controls and produced the desired population behavior across the tested MFGs.The authors suggest that advanced reinforcement learning with neural networks could help scale the scheme further.Source: §9 · p. 9

Broader Impact

The paper highlights exploitability as a proposed metric for assessing MFG numerical methods. Its finite-horizon analyses use monotonicity to establish convergence, including when common noise affects the game.

Broader Impact

  • Exploitability is proposed as a useful MFG metric, analogous in role to established success metrics in reinforcement and supervised learning.The paper notes that exploitability is game-dependent and difficult to rescale, so its relative value to a reference point matters.Source: Broader Impact · p. 10

A Continuous Time Fictitious Play in Finite Horizon

  • In the finite-horizon proof, monotonicity makes a key term non-positive, supporting the convergence conclusion.The proof develops properties of the averaged distribution and policy before applying this monotonicity argument.Source: A Continuous Time Fictitious Play in… · p. 17

B Continuous Time Fictitious Play in Finite Horizon with Common Noise

C Continuous Time Fictitious Play: the γ-discounted case

The analysis extends continuous-time Fictitious Play to γ-discounted MFGs, using γ-weighted occupancy measures and proving exploitability is a strong Lyapunov function under monotonicity. Experiments report convergence of model-based and model-free approaches, while the appendices describe algorithms, a benchmark model, and evaluation metrics.

C Continuous Time Fictitious Play: the γ-discounted case

  • The discounted analysis uses γ-weighted occupancy measures in place of state distributions and proves exploitability is a strong Lyapunov function under monotonicity.The paper presents the convergence reasoning as similar to the finite-horizon case.Source: C Continuous Time Fictitious Play: the… · pp. 20–21
  • In the γ-discounted beach-bar experiment, model-based and model-free approaches converge to the same distribution; model-based exploitability decreases at O(1/t), while model-free convergence is slower.The experiment uses γ = 0.9, Policy Iteration for model-based best responses, and Q-learning for model-free best responses.Source: Experiment: the Beach Bar Process with… · p. 21, Figure 8 · p. 21

D Algorithms

  • The algorithms appendix lists Q-Learning, Backward Induction, and density-estimation procedures for MFG computations.It includes both empirical and non-empirical density estimation algorithms.Source: D Algorithms · p. 22

E.1 Description

  • The LQ benchmark has linear dynamics with idiosyncratic and common Brownian noise, and its explicit Riccati solution serves as a benchmark.The noise correlation is parameterized by ρ; the stated condition q ≤ κ^2 makes the running cost jointly convex in state and control.Source: §E.1 · p. 23

F Common Success Metrics in Mean Field Games

  • The fixed-point discussion relates a small sup-norm change in successive value functions to an exploitability upper bound, while noting exploitability is game-dependent and hard to rescale.The appendix also describes using the residual in the fixed-point equation to assess a learned value function.Source: F Common Success Metrics in Mean Field… · p. 24
Loading 2007.03458v2…