An official website of the United States government
This project investigates numerical methods for solving fully coupled forward-backward stochastic differential equations (FBSDEs) of McKean-Vlasov type. Having numerical solvers for such mean field FBSDEs is of interest because of the potential application of these equations to optimization problems over a large population, say for instance mean field games (MFG) and optimal mean field control problems . Theory for this kind of problems has met with great success since the early works on mean field games by Lasry and Lions, see [29], and by Huang, Caines, and Malhame, see [26]. Generally speaking, the purpose is to understand the continuum limit of optimizers or of equilibria (say in Nash sense) as the number of underlying players tends to infinity. When approached from the probabilistic viewpoint, solutions to these control problems (or games) can be described by coupled mean field FBSDEs, meaning that the coefficients depend upon the own marginal laws of the solution. In this note, we detail two methods for solving such FBSDEs which we implement and apply to five benchmark problems . The first method uses a tree structure to represent the pathwise laws of the solution, whereas the second method uses a grid discretization to represent the time marginal laws of the solutions. Both are based on a Picard scheme; importantly, we combine each of them with a generic continuation method that permits to extend the time horizon (or equivalently the coupling strength between the two equations) for which the Picard iteration converges.
more »
« less
A blob method for mean field control with terminal constraints
In the present work, we develop a novel particle method for a general class of mean field control problems, with source and terminal constraints. Specific examples of the problems we consider include the dynamic formulation of thep-Wasserstein metric, optimal transport around an obstacle, and measure transport subject to acceleration controls. Unlike existing numerical approaches, our particle method is meshfree and does not require global knowledge of an underlying cost function or of the terminal constraint. A key feature of our approach is a novel way of enforcing the terminal constraint via a soft, nonlocal approximation, inspired by recent work on blob methods for diffusion equations.We prove convergence of our particle approximation to solutions of the continuum mean-field control problem in the sense of Γ-convergence. A byproduct of our result is an extension of existing discrete-to-continuum convergence results for mean field control problems to more general state and measure costs, as arise when modeling transport around obstacles, and more general constraint sets, including controllable linear time invariant systems. Finally, we conclude by implementing our method numerically and using it to compute solutions the example problems discussed above. We conduct a detailed numerical investigation of the convergence properties of our method, as well as its behavior in sampling applications and for approximation of optimal transport maps.
more »
« less
- Award ID(s):
- 2145900
- PAR ID:
- 10610295
- Publisher / Repository:
- ESAIM
- Date Published:
- Journal Name:
- ESAIM: Control, Optimisation and Calculus of Variations
- Volume:
- 31
- ISSN:
- 1292-8119
- Page Range / eLocation ID:
- 20
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This project investigates numerical methods for solving fully coupled forward-backward stochastic differential equations (FBSDEs) of McKean-Vlasov type. Having numerical solvers for such mean field FBSDEs is of interest because of the potential application of these equations to optimization problems over a large population, say for instance mean field games (MFG) and optimal mean field control problems. Theory for this kind of problems has met with great success since the early works on mean field games by Lasry and Lions, and by Huang, Caines, and Malhame. Generally speaking, the purpose is to understand the continuum limit of optimizers or of equilibria (say in Nash sense) as the number of underlying players tends to infinity. When approached from the probabilistic viewpoint, solutions to these control problems (or games) can be described by coupled mean field FBSDEs, meaning that the coefficients depend upon the own marginal laws of the solution. In this note, we detail two methods for solving such FBSDEs which we implement and apply to five benchmark problems. The first method uses a tree structure to represent the pathwise laws of the solution, whereas the second method uses a grid discretization to represent the time marginal laws of the solutions. Both are based on a Picard scheme; importantly, we combine each of them with a generic continuation method that permits to extend the time horizon (or equivalently the coupling strength between the two equations) for which the Picard iteration converges.more » « less
-
We develop a general reinforcement learning framework for mean field control (MFC) problems. Such problems arise for instance as the limit of collaborative multi-agent control problems when the number of agents is very large. The asymptotic problem can be phrased as the optimal control of a non-linear dynamics. This can also be viewed as a Markov decision process (MDP) but the key difference with the usual RL setup is that the dynamics and the reward now depend on the state's probability distribution itself. Alternatively, it can be recast as a MDP on the Wasserstein space of measures. In this work, we introduce generic model-free algorithms based on the state-action value function at the mean field level and we prove convergence for a prototypical Q-learning method. We then implement an actor-critic method and report numerical results on two archetypal problems: a finite space model motivated by a cyber security application and a continuous space model motivated by an application to swarm motion.more » « less
-
In an earlier paper (https://doi.org/10.1137/21M1393315), the switch point algorithm was developed for solving optimal control problems whose solutions are either singular or bang-bang or both singular and bang-bang, and which possess a finite number of jump discontinuities in an optimal control at the points in time where the solution structure changes. The class of control problems that were considered had a given initial condition, but no terminal constraint. The theory is now extended to include problems with both initial and terminal constraints, a structure that often arises in boundary-value problems. Substantial changes to the theory are needed to handle this more general setting. Nonetheless, the derivative of the cost with respect to a switch point is again the jump in the Hamiltonian at the switch point.more » « less
-
Abstract We develop a convergence analysis for the simplest finite element method for a model linear-quadratic elliptic distributed optimal control problem with pointwise control and state constraints under minimal assumptions on the constraint functions.We then derive the generalized Karush–Kuhn–Tucker conditions for the solution of the optimal control problem from the convergence results of the finite element method and the Karush–Kuhn–Tucker conditions for the solutions of the discrete problems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1051/cocv/2025010
