Random features for high-dimensional nonlocal mean-field games. (English) Zbl 07525128
Summary: We propose an efficient solution approach for high-dimensional nonlocal mean-field game (MFG) systems based on the Monte Carlo approximation of interaction kernels via random features. We avoid costly space-discretizations of interaction terms in the state-space by passing to the feature-space. This approach allows for a seamless mean-field extension of virtually any single-agent trajectory optimization algorithm. Here, we extend the direct transcription approach in optimal control to the mean-field setting. We demonstrate the efficiency of our method by solving MFG problems in high-dimensional spaces which were previously out of reach for conventional non-deep-learning techniques.
MSC:
| 91Axx | Game theory |
| 35Qxx | Partial differential equations of mathematical physics and other areas of application |
| 65Mxx | Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems |
Keywords:
mean-field games; nonlocal interactions; random features; optimal control; Hamilton-Jacobi-BellmanReferences:
| [1] | Huang, M.; Malhamé, R. P.; Caines, P. E., Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6, 3, 221-251 (2006) · Zbl 1136.91349 |
| [2] | Huang, M.; Caines, P. E.; Malhamé, R. P., Large-population cost-coupled LQG problems with nonuniform agents: individual-mass behavior and decentralized ϵ-Nash equilibria, IEEE Trans. Autom. Control, 52, 9, 1560-1571 (2007) · Zbl 1366.91016 |
| [3] | Lasry, J.-M.; Lions, P.-L., Jeux à champ moyen. I. Le cas stationnaire, C. R. Math. Acad. Sci. Paris, 343, 9, 619-625 (2006) · Zbl 1153.91009 |
| [4] | Lasry, J.-M.; Lions, P.-L., Jeux à champ moyen. II. Horizon fini et contrôle optimal, C. R. Math. Acad. Sci. Paris, 343, 10, 679-684 (2006) · Zbl 1153.91010 |
| [5] | Lasry, J.-M.; Lions, P.-L., Mean field games, Jpn. J. Math., 2, 1, 229-260 (2007) · Zbl 1156.91321 |
| [6] | Achdou, Y.; Buera, F. J.; Lasry, J.-M.; Lions, P.-L.; Moll, B., Partial differential equation models in macroeconomics, Philos. Trans. R. Soc. Lond. Ser. A, Math. Phys. Eng. Sci., 372, 2028, Article 20130397 pp. (2014) · Zbl 1353.91027 |
| [7] | Achdou, Y.; Han, J.; Lasry, J.-M.; Lions, P.-L.; Moll, B., Income and wealth distribution in macroeconomics: a continuous-time approach (August 2017), National Bureau of Economic Research, Working Paper 23732 |
| [8] | Guéant, O.; Lasry, J.-M.; Lions, P.-L., Mean field games and applications, (Paris-Princeton Lectures on Mathematical Finance 2010 (2011), Springer), 205-266 · Zbl 1205.91027 |
| [9] | Gomes, D. A.; Nurbekyan, L.; Pimentel, E. A., Economic Models and Mean-Field Games Theory, IMPA Mathematical Publications (2015), Instituto Nacional de Matemática Pura e Aplicada (IMPA): Instituto Nacional de Matemática Pura e Aplicada (IMPA) Rio de Janeiro · Zbl 1335.91003 |
| [10] | Firoozi, D.; Caines, P. E., An optimal execution problem in finance targeting the market trading speed: an mfg formulation, (2017 IEEE 56th Annual Conference on Decision and Control (CDC) (2017)), 7-14 |
| [11] | Cardaliaguet, P.; Lehalle, C.-A., Mean field game of controls and an application to trade crowding, Math. Financ. Econ., 12, 3, 335-363 (2018) · Zbl 1397.91084 |
| [12] | Casgrain, P.; Jaimungal, S., Algorithmic trading in competitive markets with mean field games, SIAM News, 52, 2 (2019) |
| [13] | De Paola, A.; Trovato, V.; Angeli, D.; Strbac, G., A mean field game approach for distributed control of thermostatic loads acting in simultaneous energy-frequency response markets, IEEE Trans. Smart Grid, 10, 6, 5987-5999 (2019) |
| [14] | Kizilkale, A. C.; Salhab, R.; Malhamé, R. P., An integral control formulation of mean field game based large scale coordination of loads in smart grids, Automatica, 100, 312-322 (2019) · Zbl 1415.93039 |
| [15] | Gomes, D. A.; Saúde, J., A mean-field game approach to price formation in electricity markets · Zbl 1475.91102 |
| [16] | Liu, Z.; Wu, B.; Lin, H., A mean field game approach to swarming robots control, (2018 Annual American Control Conference (ACC) (2018), IEEE), 4293-4298 |
| [17] | Elamvazhuthi, K.; Berman, S., Mean-field models in swarm robotics: a survey, Bioinspir. Biomim., 15, 1, Article 015001 pp. (2019) |
| [18] | Kang, Y.; Liu, S.; Zhang, H.; Li, W.; Han, Z.; Osher, S.; Poor, H. V., Joint sensing task assignment and collision-free trajectory optimization for mobile vehicle networks using mean-field games, IEEE Int. Things J., 8, 10, 8488-8503 (2021) |
| [19] | Kang, Y.; Liu, S.; Zhang, H.; Han, Z.; Osher, S.; Poor, H. V., Task selection and route planning for mobile crowd sensing using multi-population mean-field games, (ICC 2021 - IEEE International Conference on Communications (2021)), 1-6 |
| [20] | W. Lee, S. Liu, H. Tembine, S. Osher, Controlling propagation of epidemics via mean-field games, UCLA CAM preprint: 20-19. · Zbl 1458.92075 |
| [21] | Chang, S. L.; Piraveenan, M.; Pattison, P.; Prokopenko, M., Game theoretic modelling of infectious disease dynamics and intervention methods: a review, J. Biol. Dyn., 14, 1, 57-89 (2020) · Zbl 1447.92405 |
| [22] | Weinan, E.; Han, J.; Li, Q., A mean-field optimal control formulation of deep learning, Res. Math. Sci., 6, 1, 10 (2019) · Zbl 1421.49021 |
| [23] | Guo, X.; Hu, A.; Xu, R.; Zhang, J., Learning mean-field games, (Advances in Neural Information Processing Systems (2019)), 4967-4977 |
| [24] | Carmona, R.; Laurière, M.; Tan, Z., Linear-quadratic mean-field reinforcement learning: convergence of policy gradient methods |
| [25] | Cardaliaguet, P., Notes on mean field games (2013) · Zbl 1314.91043 |
| [26] | Achdou, Y.; Cardaliaguet, P.; Delarue, F.; Porretta, A.; Santambrogio, F.; Cardaliaguet, Pierre; Porretta, Alessio, Mean Field Games, Lecture Notes in Mathematics, vol. 2281 (2020), Springer/Centro Internazionale Matematico Estivo (C.I.M.E.): Springer/Centro Internazionale Matematico Estivo (C.I.M.E.) Cham/Florence, Fondazione CIME/CIME Foundation Subseries · Zbl 1456.49002 |
| [27] | Gomes, D. A.; Pimentel, E. A.; Voskanyan, V., Regularity Theory for Mean-Field Game Systems, SpringerBriefs in Mathematics (2016), Springer: Springer Cham · Zbl 1391.91003 |
| [28] | Cesaroni, A.; Cirant, M., Introduction to variational methods for viscous ergodic mean-field games with local coupling, (Contemporary Research in Elliptic PDEs and Related Topics. Contemporary Research in Elliptic PDEs and Related Topics, Springer INdAM Ser., vol. 33 (2019), Springer: Springer Cham), 221-246 · Zbl 1427.35287 |
| [29] | Carmona, R.; Delarue, F., Probabilistic Theory of Mean Field Games with Applications. IMean Field FBSDEs, Control, and Games, Probability Theory and Stochastic Modelling, vol. 83 (2018), Springer: Springer Cham · Zbl 1422.91014 |
| [30] | Carmona, R.; Delarue, F., Probabilistic Theory of Mean Field Games with Applications. IIMean Field Games with Common Noise and Master Equations, Probability Theory and Stochastic Modelling, vol. 84 (2018), Springer: Springer Cham · Zbl 1422.91015 |
| [31] | Bensoussan, A.; Frehse, J.; Yam, P., Mean Field Games and Mean Field Type Control Theory, SpringerBriefs in Mathematics (2013), Springer: Springer New York · Zbl 1287.93002 |
| [32] | Cardaliaguet, P.; Delarue, F.; Lasry, J.-M.; Lions, P.-L., The Master Equation and the Convergence Problem in Mean Field Games, Annals of Mathematics Studies, vol. 201 (2019), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1430.91002 |
| [33] | Gangbo, W.; Mészáros, A. R.; Mou, C.; Zhang, J., Mean field games master equations with non-separable Hamiltonians and displacement monotonicity (2021) |
| [34] | Achdou, Y.; Mannucci, P.; Marchi, C.; Tchou, N., Deterministic mean field games with control on the acceleration and state constraints: extended version (Nov. 2021), Working paper or preprint |
| [35] | Nurbekyan, L., One-dimensional, non-local, first-order stationary mean-field games with congestion: a Fourier approach, Discrete Contin. Dyn. Syst. Ser., 11, 5, 963-990 (2018) · Zbl 1406.35420 |
| [36] | Nurbekyan, L.; Saúde, J., Fourier approximation methods for first-order nonlocal mean-field games, Port. Math., 75, 3-4, 367-396 (2018) · Zbl 1496.35393 |
| [37] | Liu, S.; Jacobs, M.; Li, W.; Nurbekyan, L.; Osher, S. J., Computational methods for first-order nonlocal mean field games with applications, SIAM J. Numer. Anal., 59, 5, 2639-2668 (2021) · Zbl 1477.35276 |
| [38] | Liu, S.; Nurbekyan, L., Splitting methods for a class of non-potential mean field games, J. Dyn. Games, 8, 4, 467-486 (2021) · Zbl 1481.91024 |
| [39] | Rahimi, A.; Recht, B., Random features for large-scale kernel machines, (NIPS 2007 (2007)), 1177-1184 |
| [40] | Cardaliaguet, P.; Hadikhanloo, S., Learning in mean field games: the fictitious play, ESAIM Control Optim. Calc. Var., 23, 2, 569-591 (2017) · Zbl 1365.35183 |
| [41] | Hadikhanloo, S., Learning in anonymous nonatomic games with applications to first-order mean field games |
| [42] | Hadikhanloo, S.; Silva, F. J., Finite mean field games: fictitious play and convergence to a first order continuous mean field game, J. Math. Pures Appl. (9), 132, 369-397 (2019) · Zbl 1427.35288 |
| [43] | Bonnans, J. F.; Lavigne, P.; Pfeiffer, L., Generalized conditional gradient and learning in potential mean field games (2021) |
| [44] | Camilli, F.; Silva, F., A semi-discrete approximation for a first order mean field game problem, Netw. Heterog. Media, 7, 2, 263-277 (2012) · Zbl 1260.91019 |
| [45] | Carlini, E.; Silva, F. J., A fully discrete semi-Lagrangian scheme for a first order mean field game problem, SIAM J. Numer. Anal., 52, 1, 45-67 (2014) · Zbl 1300.65064 |
| [46] | Carlini, E.; Silva, F. J., A semi-Lagrangian scheme for a degenerate second order mean field game system, Discrete Contin. Dyn. Syst., 35, 9, 4269-4292 (2015) · Zbl 1332.65138 |
| [47] | Carlini, E.; Silva, F. J., On the discretization of some nonlinear Fokker-Planck-Kolmogorov equations and applications, SIAM J. Numer. Anal., 56, 4, 2148-2177 (2018) · Zbl 1394.35511 |
| [48] | Lin, A. T.; Fung, S. W.; Li, W.; Nurbekyan, L.; Osher, S. J., Alternating the population and control neural networks to solve high-dimensional stochastic mean-field games, Proc. Natl. Acad. Sci., 118, 31 (2021) |
| [49] | Li, H.; Fan, Y.; Ying, L., A simple multiscale method for mean field games, J. Comput. Phys., 439, Article 110385 pp. (2021) · Zbl 07512327 |
| [50] | Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, V. B., Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98 (2017) · Zbl 1356.68030 |
| [51] | Rudin, W., Fourier Analysis on Groups, Wiley Online Library, vol. 121967 (1962) · Zbl 0107.09603 |
| [52] | Onken, D.; Nurbekyan, L.; Li, X.; Fung, S. W.; Osher, S.; Ruthotto, L., A neural network approach applied to multi-agent optimal control, (2021 European Control Conference (ECC) (2021)), 1036-1041 |
| [53] | Onken, D.; Nurbekyan, L.; Li, X.; Fung, S. W.; Osher, S.; Ruthotto, L., A neural network approach for high-dimensional optimal control, arXiv preprint |
| [54] | Nakamura-Zimmerer, T.; Gong, Q.; Kang, W., Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations, arXiv preprint · Zbl 1467.49028 |
| [55] | Parkinson, C.; Arnold, D.; Bertozzi, A. L.; Osher, S., A model for optimal human navigation with stochastic effects · Zbl 1446.49023 |
| [56] | Ruthotto, L.; Osher, S. J.; Li, W.; Nurbekyan, L.; Fung, S. W., A machine learning framework for solving high-dimensional mean field game and mean field control problems, Proc. Natl. Acad. Sci., 117, 17, 9183-9193 (2020) |
| [57] | Onken, D.; Wu Fung, S.; Li, X.; Ruthotto, L., Ot-flow: fast and accurate continuous normalizing flows via optimal transport, (Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35 (2021)) |
| [58] | Enright, P. J.; Conway, B. A., Discrete approximations to optimal trajectories using direct transcription and nonlinear programming, J. Guid. Control Dyn., 15, 4, 994-1002 (1992) · Zbl 0776.49015 |
| [59] | Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 1, 120-145 (2011) · Zbl 1255.68217 |
| [60] | Evans, L. C., Partial Differential Equations, Graduate Studies in Mathematics, vol. 19 (1998), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0902.35002 |
| [61] | Carrillo, L. R.G.; López, A. E.D.; Lozano, R.; Pégard, C., Modeling the quad-rotor mini-rotorcraft, (Quad Rotorcraft Control (2013), Springer), 23-34 |
| [62] | Y.T. Chow, S. Liu, S.W. Fung, L. Nurbekyan, S. Osher, Inverse mean field game problem from partial boundary measurement, in preparation. |
| [63] | Bonnans, J. F.; Shapiro, A., Perturbation Analysis of Optimization Problems, Springer Series in Operations Research (2000), Springer-Verlag: Springer-Verlag New York · Zbl 0966.49001 |
| [64] | Mou, C.; Yang, X.; Zhou, C., Numerical methods for mean field games based on Gaussian processes and Fourier features · Zbl 07525161 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
