🔢 mathematics

High order Tensor-Train-Based Schemes for High-Dimensional Mean Field Games

This paper introduces a fully discrete, high-order Tensor-Train-based semi-Lagrangian scheme that overcomes the curse of dimensionality in solving high-dimensional Mean Field Games by reducing storage and computational costs from exponential to polynomial complexity while achieving superior accuracy and efficiency compared to traditional grid-based methods.

Original authors: Elisabetta Carlini, Luca Saluzzi

Published 2026-04-02

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Elisabetta Carlini, Luca Saluzzi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the movement of a massive crowd, like thousands of people at a concert or cars in a city. Each person (or car) makes decisions based on where they want to go and where everyone else is. In math, this is called a Mean Field Game.

The problem is: when you have just a few people, it's easy to track them. But when you have thousands of variables (like the position of every person in a 3D city, plus their speed, plus their mood), the math becomes impossible. This is known as the "Curse of Dimensionality." It's like trying to fill a library with books, but every time you add one more shelf, the number of books you need explodes exponentially until your computer runs out of memory instantly.

This paper introduces a clever new way to solve these massive, high-dimensional problems without the computer exploding. Here is how they did it, using simple analogies:

1. The Strategy: "The Smart Hiker" (Semi-Lagrangian)

Usually, to solve these movement problems, mathematicians use a grid (like a chessboard) and check every single square. But in high dimensions, the chessboard has more squares than there are atoms in the universe.

Instead, the authors use a Semi-Lagrangian approach. Imagine you are a hiker trying to figure out the best path down a mountain.

Old Way: You stand on a grid and check every single square around you to see where the wind is blowing.
Their Way: You stand at your current spot and ask, "If I walked backward for a second, where would I have come from?" You trace your steps back to the source. This is much smarter because you only calculate the paths that actually matter, rather than checking empty space.

2. The Magic Trick: "The Russian Doll" (Tensor-Train)

Even with the smart hiker method, the data is still too huge to store. This is where the Tensor-Train (TT) comes in.

Imagine you have a giant, complex 3D sculpture made of millions of tiny Lego bricks.

The Problem: Storing the blueprint for every single brick takes up a terabyte of space.
The Solution: The authors realized that this sculpture isn't random; it has a pattern. It's like a set of Russian nesting dolls. Instead of storing the whole giant doll, you just store the smallest doll inside, and a set of instructions on how to build the next layer, and the next.
The Result: You can describe a massive, complex shape using a tiny fraction of the data. This turns an "impossible" storage problem into a manageable one.

3. The Upgrade: "The High-Speed Camera" (Second-Order Schemes)

The paper also introduces a "Second-Order" scheme.

First-Order (Old): Imagine taking a photo of a moving car every second. You can guess where it was, but your guess is a bit blurry.
Second-Order (New): Imagine taking a photo every second, but you also measure the car's speed and acceleration to predict exactly where it was in between the photos.
The Catch: To do this super-accurate prediction, the math requires some "negative weights" (like saying a step backward counts as a step forward). Usually, this is risky and can make the math unstable. The authors proved that even with these weird negative numbers, their method stays stable and accurate, like a tightrope walker who knows exactly how to balance even when the wind blows.

Why This Matters

Before this paper, solving these crowd problems for high dimensions (like 10, 20, or 100 variables) was practically impossible. You'd have to wait years for a computer to finish the calculation.

With this new method:

It's Fast: It turns an exponential explosion of work into a manageable polynomial growth (like going from $2^{100}$ to $100^4$ ).
It's Accurate: It doesn't just guess; it calculates with high precision.
It's Scalable: You can add more variables (more dimensions) without the computer crashing.

In a nutshell: The authors built a "smart hiker" who uses "Russian nesting dolls" to compress the data and a "high-speed camera" to predict the future. This allows us to simulate complex systems—like traffic flow, financial markets, or robot swarms—that were previously too big for our computers to handle.

1. Problem Statement

The paper addresses the numerical solution of Mean Field Games (MFGs) in high-dimensional settings. MFGs model the collective behavior of a large number of rational agents interacting through their empirical distribution. The system couples two partial differential equations (PDEs):

A Hamilton-Jacobi-Bellman (HJB) equation describing the optimal control of a representative agent.
A Fokker-Planck (FP) equation governing the evolution of the population density.

The Challenge: Traditional grid-based numerical methods suffer from the curse of dimensionality, where computational cost and memory requirements grow exponentially with the spatial dimension $d$ . While neural network-based methods have emerged for high dimensions, they often lack rigorous convergence guarantees and high-order accuracy. Furthermore, existing high-order schemes are often inefficient in high dimensions. The authors aim to develop a fully discrete, high-order (second-order) numerical scheme that remains computationally feasible (polynomial cost) in high dimensions while maintaining accuracy and stability.

2. Methodology

The proposed approach combines Semi-Lagrangian (SL) time discretization with Tensor-Train (TT) decompositions.

A. Policy Iteration Framework

The authors utilize the Smoothed Policy Iteration (SPI) algorithm to solve the coupled MFG system. This iterative method alternates between:

Forward Step: Solving a linearized FP equation for the density $m$ given a current policy.
Backward Step: Solving a linearized HJB equation for the value function $u$ given the density.
Policy Update: Updating the control policy based on the gradient of the value function.
Smoothing: Applying a relaxation step to ensure convergence.

B. High-Order Semi-Lagrangian Discretization

The time discretization relies on the Feynman-Kac formula, representing the solution as an expectation over stochastic processes.

First-Order Scheme (SL1): Uses $2d$ axial quadrature nodes to match moments up to order 2.
Second-Order Exponential Scheme (SL2e): Uses a full tensor product of 1D Gauss-Hermite nodes ( $3^d$ nodes). While accurate, this suffers from exponential complexity.
Second-Order Polynomial Scheme (SL2p): This is a key innovation. The authors construct a new quadrature rule with $2d^2 + 1$ nodes (a central node, axial nodes, and face-diagonal nodes). This rule matches Gaussian moments up to order 5, ensuring second-order accuracy in time while keeping the number of characteristics polynomial in dimension $d$ $d$ .
- Note: For $d > 4$ , some quadrature weights become negative, which theoretically risks positivity. However, numerical experiments show the scheme is asymptotically positivity-preserving (positivity violations vanish as $\Delta t \to 0$ ).

C. Tensor-Train (TT) Approximation

To handle the spatial discretization in high dimensions without a full grid:

Functions ( $u$ and $m$ ) are represented in a Legendre polynomial basis.
The coefficient tensors are compressed using the Tensor-Train (TT) format, which factorizes high-dimensional tensors into a sequence of low-rank cores.
TT-Cross Approximation: Instead of requiring full tensor access, the authors use the TT-Cross method to reconstruct the solution from a sparse set of sampling points via least-squares minimization.
Log-Transform: For the density $m$ , a logarithmic transform ( $\log m$ ) is often applied before TT reconstruction. Since $\log m$ for Gaussian-like densities is quadratic, it admits a very low TT rank, improving compressibility and ensuring positivity.

3. Key Contributions

Polynomial Complexity Second-Order Scheme: The development of the SL2p scheme, which achieves second-order temporal accuracy with a computational cost scaling as $O(d^2)$ (number of characteristics) rather than $O(3^d)$ .
Integration with TT Decomposition: A fully discrete algorithm that couples SL time-stepping with TT spatial representation, effectively mitigating the curse of dimensionality for both the HJB and FP equations.
Theoretical and Numerical Validation:
- Proof of second-order convergence rates for the new quadrature rule.
- Demonstration that the method is asymptotically positivity-preserving despite negative quadrature weights.
- Validation of mass and first-moment conservation properties.
Scalability: The method successfully solves MFG problems in dimensions up to $d=100$ (for HJB) and $d=8$ (for coupled systems) with reasonable CPU times, outperforming grid-based methods by orders of magnitude.

4. Numerical Results

The authors tested the method on various benchmarks, including linear advection-diffusion, local MFGs, and non-local MFGs.

Accuracy: The SL2p scheme consistently achieved second-order convergence in time ( $O(\Delta t^2)$ ) for both HJB and FP components, matching the theoretical predictions.
Efficiency vs. Dimension:
- SL2e (Exponential): Computation time grew exponentially with $d$ , becoming infeasible for $d > 6$ .
- SL2p (Polynomial): Computation time grew polynomially (approx. $O(d^4)$ in viscous cases, $O(d^{2.6})$ in deterministic cases). It became the most efficient method for $d \geq 4$ .
- Grid-based SL: For $d=3$ , the TT-based method was orders of magnitude faster than grid-based SL for comparable accuracy.
High-Dimensional Performance:
- In a test with $d=100$ , the SL1 scheme solved the HJB equation in ~3 hours with stable error ( $\sim 10^{-2}$ ), demonstrating that error does not degrade significantly with dimension.
- The TT ranks remained low (typically 3–9) even for high dimensions, confirming the compressibility of the solutions.
Physical Properties: The scheme preserved total mass and first moments with high accuracy ( $10^{-7}$ to $10^{-6}$ errors), outperforming first-order schemes in conservation properties.

5. Significance

This work represents a significant advancement in the numerical analysis of high-dimensional PDEs arising in game theory and control.

Bridging the Gap: It bridges the gap between the high accuracy of traditional grid-based methods and the scalability of neural network methods, providing a rigorous, grid-free alternative with proven convergence rates.
Practical Applicability: By reducing the complexity from exponential to polynomial, the method makes high-dimensional MFG simulations feasible for applications previously considered intractable, such as multi-agent robotics, traffic flow, and financial modeling with many interacting agents.
Robustness: The ability to handle non-local couplings and maintain structural properties (positivity, mass conservation) makes the method robust for complex, real-world scenarios.

In conclusion, the authors successfully demonstrate that combining high-order semi-Lagrangian schemes with Tensor-Train decompositions offers a scalable, accurate, and memory-efficient framework for solving high-dimensional Mean Field Games.