PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Analysis of Machine Learning Algorithms for the Numerical Solution of Mean Field Control and Games: II -- The Finite Horizon Case

René Carmona, Mathieu Laurière

arXiv:1908.01613v2math.OCcs.LGcs.NAmath.NA

TL;DR

Numerical analysis of mean field control and games remains challenging, particularly for high-dimensional problems and common noise. The paper proposes two neural-network optimization methods, including a control reformulation of McKean–Vlasov FBSDEs, and proves an approximation error bound for a tractable proxy problem. Numerical examples compare the schemes with analytical or PDE benchmarks, including examples with common noise.

  • Problem

    Numerical analysis of mean field control and games remains challenging, especially in high dimensions and when dynamics are affected by common noise.

    Source: §1 · p. 1

  • Method

    The paper uses neural-network loss optimization for direct mean field control and reformulates McKean–Vlasov FBSDEs as mean field control problems.

    Source: §1 · p. 2, §4.2 · p. 15

  • Results

    The authors prove convergence for approximation schemes and demonstrate their efficiency against analytical or PDE benchmarks, including two examples with common noise.

    Source: §1 · p. 1, §2.5 · p. 6

  • Takeaways & Limitations

    The methods cover both McKean–Vlasov control and mean field games without requiring space discretization, and the FBSDE reformulation avoids recursive or fixed-point methods that typically work only for small times or coefficients.

    Source: §6 · pp. 23–24

    The stated error analysis leaves finite-population generalization error and stochastic-gradient-descent implementation error unbounded.

    Source: §2.5 · p. 7

Abstract

from arXiv · show

We propose two numerical methods for the optimal control of McKean-Vlasov dynamics in finite time horizon. Both methods are based on the introduction of a suitable loss function defined over the parameters of a neural network. This allows the use of machine learning tools, and efficient implementations of stochastic gradient descent in order to perform the optimization. In the first method, the loss function stems directly from the optimal control problem. The second method tackles a generic forward-backward stochastic differential equation system (FBSDE) of McKean-Vlasov type, and relies on suitable reformulation as a mean field control problem. To provide a guarantee on how our numerical schemes approximate the solution of the original mean field control problem, we introduce a new optimization problem, directly amenable to numerical computation, and for which we rigorously provide an error rate. Several numerical examples are provided. Both methods can easily be applied to certain problems with common noise, which is not the case with the existing technology. Furthermore, although the first approach is designed for mean field control problems, the second is more general and can also be applied to the FBSDE arising in the theory of mean field games.

1. Introduction

The paper develops numerical methods for finite-horizon mean field control and games, where numerical analysis remains challenging, especially in high dimensions and with common noise. It uses neural-network optimization to approximate McKean–Vlasov control and FBSDE solutions, and establishes convergence guarantees for its schemes.

1. Introduction

  • Numerical analysis of mean field control and games remains challenging, particularly for high-dimensional problems and dynamics affected by common noise.Source: §1 · p. 1
  • The methods address finite-horizon problems by numerically solving McKean–Vlasov FBSDEs, which encode the search for MFG equilibria and MFC optimal controls.Source: §1 · p. 1
  • The paper introduces a numerically tractable optimization problem whose approximation schemes have a proved convergence guarantee and are tested against analytical or PDE benchmarks.The examples include two problems with common noise.Source: §1 · p. 1
  • The first method extends neural-network control optimization to mean field interactions and bounds approximation error; the second extends neural BSDE approximation to coupled mean field FBSDEs.The cited work [27] treats a specific linear-quadratic model with delay and provides no theoretical convergence result.Source: §1 · p. 2

2. Formulation of the problem, standing assumptions and main results

The paper formulates a McKean–Vlasov control problem, states regularity and solvability assumptions, and constructs a neural-network approximation with a quantified error. The approximation uses a finite population, feedback controls, and time discretization; its stated bounds include a time-mesh rate of order 1/2.

2. Formulation of the problem, standing assumptions and main results

  • The original control problem uses a law-dependent state SDE and progressively measurable square-integrable controls, with assumptions ensuring well-posed dynamics.The initial distribution is in P4(Rd), and the volatility is assumed not to depend on the control.Source: §2 · p. 2, §2.2 · p. 3

2.1. Definitions, notations and background

  • The formulation defines probability measures by finite moments and uses Wasserstein distance to describe regularity with respect to the law argument.Source: §2.1 · p. 3

2.2. Standing assumptions

  • The standing assumptions include differentiability in state and measure variables, a unique Lipschitz Hamiltonian minimizer, and a uniquely solvable FBSDE with a Lipschitz decoupling field.The optimal control is represented in feedback form; the volatility is uncontrolled and additional regularity is assumed for approximation.Source: §2.2 · pp. 3–4

2.3. Approximation results

  • The approximation replaces the state law by an empirical distribution of N agents, restricts controls to neural-network feedback functions, and discretizes time.The feedback-network approximation is motivated by the expected feedback form of optimal controls.Source: §2.3 · pp. 4–5, §2.4 · p. 5

2.4. Neural networks

  • The neural-network construction fixes an architecture and activation function; bounded output activations can accommodate controls constrained to a closed convex set.The chosen periodic activation class supports approximation of feedback controls while relating the network's Lipschitz constant to that of the optimal control.Source: §2.4 · pp. 5–6

2.5. New optimization problem and main result

  • The proposed proxy optimization problem is tractable and its solution approximates the original mean field control problem with a quantified error.The problem is framed as minimizing the social cost of N agents under a decentralized neural-network feedback rule.Source: §2.5 · p. 6
  • The stated approximation error combines population, network-width, and time-discretization terms, and the time-mesh contribution is only claimed at order 1/2.An order-1 time rate is expected to require extra smoothness of the decoupling field, which the authors do not assume.Source: §2.5 · p. 6
  • The error analysis does not bound finite-population generalization or stochastic-gradient-descent implementation error; the authors leave these analyses for future work.Source: §2.5 · p. 7

3. Proof of the main result

The proof controls approximation errors from the finite-agent replacement, neural-network restriction, and time discretization. It also establishes strong-error control for the Euler scheme with Lipschitz feedback and derives a bound for the associated discrete-time problem.

3. Proof of the main result

  • The proof is organized around the errors from the N-agent, neural-network, and time-discretization steps.The three steps are treated in separate subsections.Source: §3 · p. 7

3.1. Problem with N agents and closed-loop controls.

  • The N-agent formulation minimizes average social cost when all agents use the same feedback rule, and Proposition 7 relates it to the original mean-field problem.The stated feedback is constructed from the optimal Hamiltonian control and the associated McKean–Vlasov FBSDE; the supplied passages do not include the bound’s expression.Source: §3.1 · pp. 7–8

3.2. Problem with neural networks as controls.

  • On a compact domain, a one-hidden-layer neural network approximates the optimal feedback with error bounded by c3(1+R)n^-1/(2(d+1)).The rate’s dimension dependence is identified as a curse of dimensionality, arising from the guarantee on the approximating control’s Lipschitz constant.Source: §3.2 · pp. 9, 10, 12

3.3. Problem in discrete time.

  • The discrete-time subsection compares objective values with the continuous-time problem while seeking error constants independent of the number of agents.The supplied passage introduces this comparison but does not provide its bound.Source: §3.3 · p. 13
  • Lemma 14 gives a strong-error estimate for the Euler scheme under a Lipschitz feedback control.The estimate’s constant depends only on problem data and the feedback’s Lipschitz constant and value at (0, 0).Source: §3.3 · p. 14
  • The discrete-time problem admits a bound for all agent counts N and times t, with its constant depending on problem data and specified control quantities.For the feedback control constructed in Proposition 8, the constant depends on problem data and the activation function through specified derivatives.Source: §3.3 · p. 14

4. Two numerical methods

The section presents two neural-network optimization methods: one minimizes the mean field control cost directly, while the other reformulates McKean–Vlasov FBSDEs as mean field control problems. The FBSDE method also applies to mean field games.

4. Two numerical methods

  • The two methods target different problems: direct optimization of McKean–Vlasov control, and a reformulated FBSDE approach applicable to both mean field control and mean field games.Source: §4 · p. 14

4.1. Method 1: minimization of the MFC cost function.

  • The first method parameterizes feedback controls with a neural network and minimizes the control cost using a loss function and stochastic gradient descent on empirical population samples.Source: §4 · p. 14, §4.1 · pp. 14–15

4.2. Method 2: MKV FBSDE.

  • The general FBSDE formulation assumes non-controlled volatility; the authors describe combining Euler discretization, finite-population interaction estimates, and SGD, with error bounds expected to carry over.Source: §4.2 · pp. 15–16
  • For the second method, the backward equation is replaced by a forward equation, with the initial value and volatility of the Y process chosen as controls and terminal mismatch penalized.Source: §4.2 · pp. 15–16

5. Numerical results

The numerical tests compare the two algorithms with analytical or PDE-based benchmarks, including settings with common noise. Results show close benchmark agreement in several cases, while errors improve with larger time discretizations and populations in the systemic-risk example.

Numerical setup

  • The numerical tests use either analytical solutions or finite-difference PDE solutions as benchmarks, and some examples lie outside the theory’s scope.The authors report that the algorithms remain robust in those out-of-scope cases.Source: §5 · pp. 16–17

Test case 1

  • Increasing the time steps and population size improves Algorithm 1’s learned control, whose L2 distance from the optimal control also decreases with SGD iterations.The comparison uses an ODE solution as the reference; results are averaged over three SGD runs.Source: §5 · p. 17, Figure 1 · p. 18

Test case 2

  • Algorithm 2 approximates Y0 better than YT in the two-target problem and learns the value-function gradient’s jump at the midpoint between targets.The learned solution is compared with a finite-difference PDE benchmark.Source: §5 · p. 18, Figure 2 · p. 19

Test case 3

  • For the FBSDE benchmark, Algorithm 2’s Y0 values are compared with PDE values across ρ at T = 1 and T = 2, using the same network parameter count.The time-step count increases for the longer horizon while the architecture remains unchanged.Source: Figure 3 · p. 19, §5 · p. 19

Test case 4

  • In the MFG test, Algorithm 2’s Y0 solution is very close to the PDE benchmark and does not exhibit the bifurcation seen in [23, Figure 3].The authors suggest this may relate to reformulating the FBSDE as a control problem driven by two forward SDEs.Source: §5 · p. 20, Figure 4 · p. 20

Test case 5

  • With common noise revealing one of two targets at T/2, the distribution moves toward the revealed target but does not reach it because the running cost penalizes displacement.Algorithm 1’s density histograms are compared with the PDE solution; before revelation, the distribution concentrates around zero.Source: §5 · p. 21, Figure 5 · p. 22

Test case 6

  • For the numerical tests, the L2 error decreases as the number of time steps NT and particle-population elements N increase, while variance also decreases as N grows.Algorithm 2 is compared with the ODE method; Figure 6 displays sample trajectories for two agents for one realization of common noise.Source: §5 · p. 23, Figure 6 · p. 23

6. Conclusion

The conclusion presents the methods as covering a broader class of mean field control and game problems without space discretization. It also highlights the FBSDE reformulation, the direct-control method’s implementation simplicity, and directions for extending the analysis and computations.

6. Conclusion

  • The methods cover a broader class of models than prior stochastic mean field control methods, including both MKV control problems and mean field games, without space discretization.The authors expect both algorithms to work well in higher dimensions, based on the LQ example in Test case 1.Source: §6 · p. 23
  • Figure 7 reports the L2 error for Algorithm 2 against a benchmark solution in Test case 6, with NT denoting time steps and N the sampled population size per SGD iteration.Source: Figure 7 · p. 24
  • Recasting MKV FBSDEs as mean field control problems avoids recursive or fixed-point methods that typically work only for small times or sufficiently small coefficients.The authors report that their results do not suffer from bifurcation in Test case 4.Source: §6 · p. 24
  • The first method starts directly from the MKV control problem and does not require deriving an optimality condition, making it more straightforward to implement numerically.Source: §6 · p. 24
  • The authors identify improved neural-network approximation bounds, including for functions and their derivatives, as a theoretical direction for improving the overall convergence result.They also suggest trying more involved network architectures or approximating the value function as a function of the population distribution.Source: §6 · p. 24
  • The second method can also apply to generic MKV FBSDEs, including systems in which the backward variable represents the value function directly.Source: §6 · pp. 24–25

Appendix A. Standing assumptions

The standing assumptions impose regularity, convexity, and growth conditions on the model and its value and control functions. Additional conditions support well-posedness and the analysis of time discretization.

Appendix A. Standing assumptions

  • Assumption (A1) makes the drift linear in the state, measure, and control, and the volatility linear in the state and measure; the volatility is not controlled.Source: Appendix A · p. 25
  • Assumptions (A2)–(A3) require measure differentiability with continuous measure derivatives, bounded reference values and derivative bounds growing as L(1 + R), plus L-Lipschitz derivatives in the specified variables.Source: Appendix A · p. 25
  • Assumption (B1) requires the control-cost derivative to be Lipschitz in time and state uniformly in the measure and control; under the stated conditions, the minimizing control is unique and regular, and the FBSDE is well posed.Source: Appendix A · p. 26
  • Assumption (B2) requires the value function V to be Lipschitz in time and state, while (B3) requires the initial distribution to have a finite fourth moment.The fourth-moment condition is used for well-posedness and stability estimates.Source: Appendix A · p. 27
  • The time-discretization analysis requires extra regularity, including boundedness and second-derivative conditions on V and the optimal control.The stated derivative conditions ensure Lipschitz continuity of the control’s second derivative in the state, used to analyze an Euler-scheme error term.Source: Appendix A · pp. 27–28

Appendix B. Proof of Proposition 4

The proof of Proposition 4 applies a result for the open-loop control problem under the paper’s standing assumptions, then relates its optimum to the finite-agent feedback formulation.

Appendix B. Proof of Proposition 4

  • The proof modifies [19, Theorem 6.17] under the standing assumptions, including an uncontrolled volatility and a fourth-moment initial distribution.Source: Appendix B · p. 28
  • It identifies J as the infimum over admissible open-loop controls and the distributed control α̂N as a feedback control.Source: Appendix B · p. 28
  • By symmetry across agents, JN( v̂ ) can be interpreted as the cost of a typical player, and the proof derives a bound relating the best feedback cost to the open-loop optimum.Source: Appendix B · pp. 28–29

Appendix C. Proofs of the Results of Section 3.2

The proofs compare Lipschitz feedback controls by first controlling their induced particle trajectories and then bounding the corresponding costs. Localization and regularity estimates support the comparison.

Appendix C. Proofs of the Results of Section 3.2

  • The proof localizes to a bounded domain and controls the probability that particles exit it using a fourth-moment stability estimate and Markov’s inequality.Source: Appendix C · pp. 29–30
  • For Lipschitz feedback controls close in the stated bounded-domain sup norm, the proof bounds the difference between the resulting particle states using the dynamics and Grönwall’s inequality.Source: Appendix C · pp. 29–31
  • The proof then bounds differences in terminal and running costs using their local Lipschitz properties, combining these estimates to obtain the desired cost bound.Source: Appendix C · pp. 32–33

Appendix D. Proofs of the Results of Section 3.3

Appendix D closes approximation estimates with Gronwall arguments. The proofs use Lipschitz assumptions, with a stronger differentiability requirement for one running-cost estimate.

Appendix D. Proofs of the Results of Section 3.3

  • Lemma 19’s Lipschitz-coefficient estimate has a constant independent of N, t0, and t.The proof also concludes an estimate by Gronwall’s inequality.Source: Appendix D · pp. 33–34
  • A minor modification extends the Lemma 14 and Lemma 19 proofs beyond globally Lipschitz drift and volatility when the coefficients have the stated linearity structure.The remark notes that global Lipschitz continuity does not strictly follow from Assumption (A1).Source: Appendix D · p. 34
  • The proofs also use discrete Gronwall to conclude an estimate whose constants depend on problem data and the control.The stated constant is independent of N.Source: Appendix D · p. 37
  • The running-cost estimate uses Itô’s formula and therefore assumes stronger differentiability of the running cost and feedback function.The proof introduces an empirical projection to apply the classical Itô formula.Source: Appendix D · p. 39
  • The proof bounds δ2_f by the same upper bound as δg, completing the estimate for the running-cost term.The argument uses the feedback function’s Lipschitz property to give F_n the same properties as G.Source: Appendix D · p. 42

Related papers

Loading 1908.01613v2…