Source-linked AI summary
A Machine Learning Framework for Solving High-Dimensional Mean Field Game and Mean Field Control Problems
Lars Ruthotto, Stanley Osher, Wuchen Li, Levon Nurbekyan, Samy Wu Fung
TL;DR
High-dimensional MFG and MFC solvers face grid-induced curse-of-dimensionality limitations. This paper combines a Lagrangian formulation, HJB enforcement, and a structure-aware neural network to avoid spatial discretization, approximately solving optimal transport and crowd-motion problems in 100 dimensions and validating against a two-dimensional Eulerian solver. The authors identify unresolved questions about neural-network convergence, architecture design, regularization, and time discretization.
Problem
Grid-based MFG and HJB solvers suffer computational complexity that grows exponentially with spatial dimension, limiting high-dimensional numerical solution.
Method
The framework uses Lagrangian coordinates for the continuity equation, penalizes HJB violations, and parameterizes the potential with a specialized neural network.
Results
The method approximately solves optimal transport and crowd-motion instances in up to 100 dimensions and is competitive with an Eulerian solver on two-dimensional examples.
Takeaways & Limitations
The mesh-free, parallelizable framework provides a route toward numerical MFG and MFC applications at dimensions beyond existing methods’ reach.
Takeaways & Limitations
Theoretical convergence guidance for neural networks and practical guidance for architecture, regularization, and discretization remain underdeveloped.
Abstract
from arXiv · showhide
Mean field games (MFG) and mean field control (MFC) are critical classes of multi-agent models for efficient analysis of massive populations of interacting agents. Their areas of application span topics in economics, finance, game theory, industrial engineering, crowd motion, and more. In this paper, we provide a flexible machine learning framework for the numerical solution of potential MFG and MFC models. State-of-the-art numerical methods for solving such problems utilize spatial discretization that leads to a curse-of-dimensionality. We approximately solve high-dimensional problems by combining Lagrangian and Eulerian viewpoints and leveraging recent advances from machine learning. More precisely, we work with a Lagrangian formulation of the problem and enforce the underlying Hamilton-Jacobi-Bellman (HJB) equation that is derived from the Eulerian formulation. Finally, a tailored neural network parameterization of the MFG/MFC solution helps us avoid any spatial discretization. Our numerical results include the approximate solution of 100-dimensional instances of optimal transport and crowd motion problems on a standard work station and a validation using an Eulerian solver in two dimensions. These results open the door to much-anticipated applications of MFG and MFC models that were beyond reach with existing numerical methods.
Introduction
The paper develops a machine-learning framework for potential MFGs and MFCs that avoids grid-based spatial discretization. It combines Lagrangian computation, HJB enforcement, and a tailored neural network to address high-dimensional problems.
- MFGs and MFCs model interactions within large agent populations across economics, finance, crowd motion, industrial engineering, data science, and material dynamics.
- Both problem classes couple a Hamilton-Jacobi-Bellman equation with a continuity equation, whose solution determines agents’ optimal actions without individual optimization.
- The framework targets potential MFGs and MFCs formulated as infinite-dimensional optimal control problems in density space.
- Grid-based numerical methods face a curse of dimensionality because computational complexity grows exponentially with spatial dimension.
- The method uses Lagrangian coordinates to solve the continuity equation and compute characteristics and Jacobian information from the potential.
- A specialized space-time neural network parameterizes the potential and enables direct penalization of HJB violations, transforming a broad class of MFGs into machine-learning problems.
- Experiments solve optimal transport and crowd-motion instances in up to 100 dimensions, validate against a two-dimensional Eulerian solver, and report improved accuracy and reduced cost from HJB penalization.
- The prototype implementation is released as open-source Julia software under a permissible license.
Related work
The related work situates the framework at the intersection of machine learning, PDEs, optimal control, and high-dimensional transport. Its distinguishing scope is handling density-dependent MFGs while scaling to 100 dimensions.
- Neural networks have been used to solve high-dimensional PDEs and control problems, while prior ML approaches addressed MFGs in spatial dimensions up to four.
- High-dimensional optimal transport remains numerically challenging because Euclidean-coordinate methods require spatial discretization and are vulnerable to the curse of dimensionality.
- Normalizing flows provide a related ML approach that transforms samples from an unknown distribution toward an approximately normal distribution and can generate samples by reversing the flow.
- Earlier MFG methods were limited when formulations involved population density, whereas this framework estimates density along agents’ trajectories and supports nonlinear congestion terms.
- The neural architecture respects optimality-induced control structure and is used to approximately solve MFGs in 100 dimensions on a standard workstation.
- Prior Lagrangian approaches avoided some density-estimation difficulties through Fourier coordinates, while particle-in-cell density computation did not scale to high dimensions.
Mathematical Modeling
MFGs describe decentralized Nash-equilibrium behavior, while MFCs use a central planner; both can be represented through coupled HJB and continuity equations. Potential formulations reduce the problem to optimization over a potential.
- Mean field games model large populations of rational agents whose optimal behavior leads to a Nash equilibrium.
- The population density evolves under agents’ strategies according to a continuity equation, with initial density ρ0.
- An MFG equilibrium occurs when the forecast population distribution equals the actual distribution generated by optimal behavior.
- Solving the coupled HJB and continuity PDEs yields optimal strategies for all agents simultaneously rather than optimizing each strategy separately.
- Potential MFGs arise when the MFG system coincides with first-order optimality conditions of an infinite-dimensional constrained optimization problem.
- The paper re-parameterizes control through the potential and adds penalties for HJB violations without changing the minimizer.
- In MFC, a central planner selects one distributed strategy followed by all agents to minimize overall costs.
Lagrangian Method
The Lagrangian method eliminates the continuity constraint by following characteristics generated by the potential, yielding a mesh-free, parallelizable optimization problem. Jacobian, cost, and HJB terms are accumulated along trajectories and approximated with neural networks and sampling.
- The method discretizes the optimal control problem by using Lagrangian coordinates to eliminate the continuity equation and other density-dependent terms.
- Characteristics are the trajectories of individual agents, making Lagrangian coordinates closely connected to the microscopic model and enabling stable mesh-free parallel computation.
- The framework focuses concretely on L2 transport costs while remaining adaptable to other transport-cost choices.
- Given a potential, characteristics are computed by solving an ODE with initial condition z(x,0)=x, and the continuity equation is evaluated along those curves.
- The method uses Jacobi’s identity to evolve the logarithm of the Jacobian determinant instead of directly computing the determinant, whose direct evaluation costs O(d^3) FLOPS.
- Running, terminal, and HJB-penalty contributions are accumulated along characteristics, with the HJB penalty enforcing equation violations during optimization.
- Quadrature converts the formulation into unconstrained optimization over the potential, and Monte Carlo integration is used for high-dimensional cases.
- Independent sample trajectories make the computation trivially parallel, while stochastic approximation and sample average approximation provide optimization options.
Machine Learning Framework for MFGs
The framework parameterizes the MFG/MFC potential with a tailored neural network and computes the derivatives needed for a mesh-free Lagrangian scheme. Its characteristic computations scale linearly with input dimension and depth but quadratically with network width.
- Neural-network parameterization: A neural network parameterizes the potential, allowing HJB violations to be penalized during training and yielding a mesh-free Lagrangian scheme.The network is designed to approximate characteristics accurately and efficiently.
- Neural-network parameterization: The model maps s = (x, t) ∈ R^(d+1) to a scalar potential Φ(s), with trainable network parameters θ.Its architecture is modular, although architecture choices affect expressibility and training difficulty.
- Derivative computation: The residual network computes the potential gradient by back-propagation, with the first d components representing spatial derivatives and the final component representing the time derivative.These derivatives provide the inputs needed for characteristic computation.
- Derivative computation: The Laplacian can be computed exactly through layerwise operations, with first-layer cost O(m · d) FLOPS.The computation squares and sums selected weight columns before one inner product.
- Computational complexity: O(m^2 · d · M) FLOPS characterize each time-step computation, so cost is linear in input dimension and layers but quadratic in network width.This scaling motivates deep rather than wide architectures.
Numerical Experiments
The experiments apply the proposed framework to optimal transport and crowd motion across dimensions up to 100, examine training choices, and compare the method with an Eulerian solver in two dimensions.
- Experimental design: The experiments cover optimal transport and crowd motion, including dimensions d = 2, 10, 50, and 100, with a similar network architecture across cases.The study also evaluates scalability, the HJB penalty CHJB, optimization strategies, and validation against an Eulerian method.
- Optimal transport: The two-dimensional optimal transport solution matches the initial and target densities, produces approximately straight characteristics, and partitions the target into eight approximately equal slices.The visualization uses push-forward and pull-back densities to assess the learned transformation.
- Optimal transport: Higher-dimensional optimal transport instances achieve quantitatively similar objective values for d = 10, 50, and 100, while runtime per iteration grows slower than predicted.The d = 50 case has a slight increase in terminal costs, while projected image quality remains similar across cases.
- Training choices: Removing the HJB penalty can prevent density matching and produce curved characteristics, whereas the penalty yields more accurate solutions at lower computational cost.Increasing characteristic time steps improves the penalty-free result but remains inferior and makes training four times more expensive.
- Training choices: BFGS with the SAA approach is more effective than ADAM with SA at reducing the HJB penalty at comparable computational cost, although both reach similar final results.The comparison is reported for the two-dimensional optimal transport instance.
- Validation: Against a provably convergent Eulerian solver, the proposed method is competitive in d = 2 and scales to dimensions beyond the reach of Eulerian schemes.The comparison evaluates controls using an explicit Finite-Volume continuity-equation solver that was not used during optimization.
- Crowd motion: The crowd motion experiment produces trajectories that avoid crowded regions and spread horizontally, with visually similar characteristics across dimensions and results comparable to a convergent Eulerian solver.For d = 2, the trajectories are approximately symmetric and bend around the central obstacle or congested region.
Discussion and Outlook
The framework combines Lagrangian PDE solvers with neural networks to address high-dimensional potential MFG and MFC problems without spatial meshes. The authors identify theoretical, computational, and machine-learning questions that remain open before broader applications.
- The framework combines Lagrangian PDE solvers with neural networks for mesh-free numerical solution of potential MFG and MFC problems.
- The authors view the framework as a promising direction for large-scale MFG applications because it is mesh-free and suited to parallel computation.
- The transformed MFG learning problems have unique traits that require further machine-learning attention.
- Practical convergence results for neural networks in optimal control and firm theoretical results for regularization effects remain open mathematical issues.
- More thorough parallel implementation may provide speed-up for more realistic MFG problems, while improved deep-learning optimization could increase efficiency.
- Network architecture design lacks theoretical guidance and must support accurate evaluation of the gradients and Laplacians required by the Lagrangian scheme.
- Applying the framework to more realistic problems is identified as an open application question, supported by the release of open-source code.
A. Supplemental Information for Numerical Experiments
The supplemental information describes the prototype implementation, its validation infrastructure, and the workstation-based experimental environment used for runtime measurements.
- The prototype extends Flux and is written in Julia rather than being fully described in the paper.
- Unit tests are provided to verify the validity of the code.
- Experiments ran on a shared Ubuntu workstation with 40 CPU cores and 1 TB of memory, so reported runtimes are rough averages.
Dynamical Optimal Transport
The dynamical optimal transport experiments evaluate scalability, discretization choices, HJB-penalty effects, and optimization methods across dimensions from 2 to 100. The results show qualitatively similar transport behavior across dimensions, while finer characteristic discretization improves solutions at higher training cost.
- Dynamical Optimal Transport: The default training setup uses SAA with resampling every 25 iterations and BFGS with a backtracked Armijo line search.
- Dynamical Optimal Transport: The experiments use a Gaussian-mixture initial density and centered Gaussian target with covariance 0.3 · I across dimensions.
- Dynamical Optimal Transport: Across dimensions, projected densities and characteristics are qualitatively similar, with trajectories moving toward the target along almost straight paths.
- Dynamical Optimal Transport: Without the HJB penalty, the mean-field objective decreases substantially, but the learned densities and characteristics do not match the desired solution well.
- Dynamical Optimal Transport: Using nt = 8 characteristic steps quadruples training cost but produces more meaningful results, likely because approximate transport costs become more accurate.
- Dynamical Optimal Transport: BFGS converges in fewer iterations and reduces the HJB penalty more sharply early on, whereas ADAM has lower cost per iteration; overall costs are approximately comparable.
Crowd Motion
The crowd-motion experiments model obstacle and congestion avoidance through running costs and compare behavior across dimensions. The learned characteristics bend around costly regions rather than following the straight, parallel paths expected for optimal transport.
- Crowd Motion: The crowd-motion setup uses nt = 4 Runge-Kutta steps because characteristics are expected to bend around the obstacle.
- Crowd Motion: The model uses a Kullback-Leibler terminal cost with λKL = 5 and HJB-penalty parameters α1 = 10 and α2 = 1.
- Crowd Motion: Crowd-motion characteristics bend to avoid congestion and the domain center, effects represented by the running costs F.
- Crowd Motion: Unlike optimal transport, where characteristics would be straight and parallel, the crowd-motion trajectories respond to obstacle and congestion costs.
- Crowd Motion: Across tested dimensions, the model learns similar dynamics, with agents avoiding the centrally placed high-travel-cost obstacle region.
Comparison to Eulerian Methods
The framework is compared with Eulerian finite-volume methods using matched continuity-equation discretizations and visual diagnostics. In two dimensions it is competitive, while its Lagrangian formulation supports experiments at dimensions beyond Eulerian reach.
- Eulerian reference: The Eulerian reference solves a discretized convex optimization problem with staggered momentum and density variables on a regular space-time grid.Its implementation uses a conservative scheme and a primal-dual Newton method with multilevel initialization.
- Method: The comparison uses identical explicit finite-volume schemes to evaluate controls from the machine learning and Eulerian methods fairly.The trained neural network is evaluated on the Eulerian method’s space-time grid before solving the continuity equation.
- Eulerian comparison: For the two-dimensional optimal-transport comparison, both methods are visually comparable, while the machine-learning objective is about 0.59% higher.The machine-learning result has higher image similarity, whereas the Eulerian method has lower transport costs.
- Eulerian comparison: The Lagrangian method is less than 1% sub-optimal with the HJB penalty and two time steps, while scaling to dimensions beyond Eulerian schemes.This performance is obtained despite non-convex training and a vastly reduced parameter count.
- HJB penalty: The HJB penalty improves density matching and characteristic geometry; without it, optimization can fail, while eight time steps remain inferior and cost four times more.With the penalty and two time steps, the pull-back and push-forward match their targets more closely and characteristics are nearly straight.
- Optimization: BFGS converges in fewer iterations than ADAM and produces a more substantial reduction of the HJB penalty.Figure 7 tracks the overall objective, mean field term, and HJB penalty using validation data.