Memory-Efficient Replay-Free Policy Evaluation for Mean-Field Games

When the population size $N$ is large, a finite $N$-agent game can be approximated by its mean-field limit, where the interaction among agents is represented through the population distribution. In finite-horizon evolutive mean-field games (MFGs), a common approach to computing a Nash equilibrium is to first generate the entire sequence of population distributions under a fixed policy and then fix this sequence as the external environment for policy evaluation. However, in many real-world systems, a simulator that can freely reproduce a prescribed distribution flow for subsequent policy evaluation is unavailable, which motivates a replay-free policy evaluation method. A straightforward alternative is to store the entire population history while a large finite population, approximated by the MFG, evolves forward to generate the distribution flow, and then perform policy evaluation after the forward evolution is completed. But this requires $\mathcal{O}(NT)$ memory, which can be substantial when both the population size $N$ and the horizon $T$ are large. In this work, we first propose a Private Population Dutch Trace Algorithm, which recursively compresses the relevant history of each agent into a trace, eliminating the memory's dependence on $T$. We further compress the collection of agent-wise traces and develop DoubleSWEET, which maintains state-wise traces instead, making the storage independent of $N$ and $T$. Finally, we theoretically prove that the compressed state-wise traces in DoubleSWEET lead to similar policy evaluation as the private traces, for any fixed horizon, with an error upper bound of $\mathcal{O}(N^{-1/2})$; at the deterministic mean-field level, we further show that the same exact-expectation Dutch evaluator produces the same critic trajectory and learned value-function readout whether it is run live during population-flow generation or after that same flow has been frozen. In our experimental settings, DoubleSWEET achieves nearly the same policy-evaluation accuracy as the private-trace method while substantially reducing memory consumption; its memory usage does not grow with the population size $N$ or the episode horizon $T$. At $N=100,000$, the private-trace method requires $344.9\times$ as much memory as DoubleSWEET and the model-based projected evaluator requires approximately $40.6\times$ as much learner memory as DoubleSWEET-MC-LS while achieving the same $0.472\%$ relative RMSE.