acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

When the population size is large, a finite -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 memory, which can be substantial when both the population size and the horizon 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 . We further compress the collection of agent-wise traces and develop DoubleSWEET, which maintains state-wise traces instead, making the storage independent of and . 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 ; 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 or the episode horizon . At , the private-trace method requires as much memory as DoubleSWEET and the model-based projected evaluator requires approximately as much learner memory as DoubleSWEET-MC-LS while achieving the same relative RMSE.

Primary area:
reinforcement learning
Keywords:
Policy evaluation, evolutive mean-field games, expected eligibility traces, LSTD(λ), Dutch traces, temporal credit assignment, replay-free learning, finite-horizon learning.

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_VY32OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

In the field of finite-horizon evolutive mean-field games, this paper try to solve the O(NT)\mathcal{O}(NT) memory bottleneck of replay-free policy evaluation (where NN is the number of agents and TT is the time horizon). To takle this, the authors propose two novel trace-based algorithms, the Private Population Dutch Trace Algorithm and DoubleSWEET, which compress temporal and agent-wise histories into state-wise expected traces, achieving comparable evaluation accuracy while reducing memory complexity to be independent of both NN and TT.

Critical strengths

The paper is technically solid, and I found the overall storytelling very clear and easy to follow. The construction of the DoubleSWEET algorithm is very interesting, particularly how it compresses the NN agent-wise private traces into state-wise expected traces by propagating historical credit forward through empirical state-to-state transitions. I appreciated the rigorous analysis of the trace compression consistency in Theorem 2, which solidly justifies the algorithmic design choices.

Critical weaknesses

While I find the paper overall a solid and technically valid work, its practical impact is not fully exploited by the experimental section:

  • Looking at Figure 2(c) (and Table 10), increasing the number of agents NN from 5,0005,000 to 100,000100,000 barely improves the value estimation error (e.g., DoubleSWEET decreases only from 6.87%6.87\% to 6.78%6.78\% , and DoubleSWEET-MC-LS from 0.49%0.49\% to 0.47%0.47\%). Because the estimation error plateaus at relatively small sample sizes, the practical necessity of processing all NN agents is questionable. In fact, simply tracking a small subset of agents (as shown by the Subsampled Private Dutch baseline with K=2,000K=2,000 agents) achieves nearly identical accuracy (6.81%6.81\%) with low, constant memory and lower computation time per step. One could reasonably stay with a smaller number of tracked agents and accept a negligible bias. This would invalidate the main claim about the necessity of switching to a state-aware trace.
  • Framing the space complexity as O(1)\mathcal{O}(1) in the introduction is somewhat misleading without immediate qualification. It is O(1)\mathcal{O}(1) only with respect to NN and TT, while scaling linearly with the number of states SS as O(Sd+d2)\mathcal{O}(Sd + d^2). This state-enumeration requirement limits applicability in very large or continuous state spaces where linear function approximation is normally most useful.
  • Moving the pseudocode of DoubleSWEET into Section 3 would substantially improve the readability and self-containment of the paper.
  • The main text lacks a dedicated Related Work section and cites a relatively narrow set of references. It does not fully position the contribution at the intersection of multi-agent reinforcement learning, value-based eligibility trace methods, and concurrent/parallel learning from multiple agents.
Questions for authors
  • In the experimental section no result is presented about the routing environment, can you present also that results?
  • How could DoubleSWEET be adapted when SS is too large?
5 comments

Response to Reviewer 3 — Part 1 of 4

We sincerely thank you for your careful reading of our paper. Our responses to the weaknesses and questions are provided below:

Weakness 1: Necessity of Having A Large Number of Agents

We agree with the reviewer that, under the experiments shown in the recent manuscript, having a large number of agents may not lead to a significant reduction in estimation error. This is because the recent experimental setting evaluates a relatively simple scenario, where events happen at similar and moderate probabilities. However, when events happen with quite diverse probabilities (especially when some events occur with a low probability while they incur substantial costs), having a large number of agents is necessary. For example, in traffic routing, accidents may occur with a very low probability but incur substantial costs. Similarly, in satellite games, satellites at certain locations may have a higher probability of being hit by space debris. Although such collisions are rare, their consequences can be severe. In these cases, sampling a subset of agents may fail to capture rare but critical events, leading to the risk of missing important information.

To verify the above explanation and the necessity of having a large number of agents, we modified the transition probabilities and reward scale in the Garnet environment, while kept all other experimental settings unchanged. Specifically, we reduced the baseline probability of transitioning from the entrance to the rewarding room from 25% to 0.5%, set the baseline probability of transitioning to the ordinary room to 84.5%, and set reward_scale=45. The resulting experimental results are as follows, where each tuple shows (estimation error, processing time, memory):

NN (RelRMSE, PT, MEM; %, ms/step, MiB)Full MC-LSSubsampled MC-LS (K=2,000K=2{,}000)DoubleSWEET-MC-LS
5,000(5.82±0.17, 6.56±0.87, 21.66)(5.82 \pm 0.17,\, 6.56 \pm 0.87,\, 21.66)(9.13±0.27, 5.06±0.48, 9.96)(9.13 \pm 0.27,\, 5.06 \pm 0.48,\, 9.96)(1.88±0.10, 7.13±0.88, 3.13)(1.88 \pm 0.10,\, 7.13 \pm 0.88,\, 3.13)
10,000(4.35±0.36, 9.40±1.18, 41.20)(4.35 \pm 0.36,\, 9.40 \pm 1.18,\, 41.20)(9.69±0.74, 5.14±0.42, 9.96)(9.69 \pm 0.74,\, 5.14 \pm 0.42,\, 9.96)(1.93±0.33, 7.84±0.90, 3.13)(1.93 \pm 0.33,\, 7.84 \pm 0.90,\, 3.13)
20,000(3.21±0.09, 15.15±1.73, 80.26)(3.21 \pm 0.09,\, 15.15 \pm 1.73,\, 80.26)(9.35±0.33, 5.45±0.23, 9.96)(9.35 \pm 0.33,\, 5.45 \pm 0.23,\, 9.96)(1.64±0.21, 9.99±0.99, 3.13)(1.64 \pm 0.21,\, 9.99 \pm 0.99,\, 3.13)
50,000(2.34±0.20, 32.70±2.27, 197.45)(2.34 \pm 0.20,\, 32.70 \pm 2.27,\, 197.45)(9.27±0.50, 5.62±0.13, 9.96)(9.27 \pm 0.50,\, 5.62 \pm 0.13,\, 9.96)(1.52±0.33, 15.74±1.21, 3.13)(1.52 \pm 0.33,\, 15.74 \pm 1.21,\, 3.13)
100,000(1.68±0.12, 62.39±4.55, 392.76)(1.68 \pm 0.12,\, 62.39 \pm 4.55,\, 392.76)(9.96±1.47, 6.32±0.91, 9.96)(9.96 \pm 1.47,\, 6.32 \pm 0.91,\, 9.96)(1.15±0.19, 26.78±2.60, 3.13)(1.15 \pm 0.19,\, 26.78 \pm 2.60,\, 3.13)

As can be seen from the table, under this new experimental setting where rare events happen, (i) Our DoubleSWEET achieves much lower estimation error than full MC-LS and subsampled MC-LS. (ii) As the number of agents NN increases, the estimation error of full MC-LS decreases obversely, indicating the necessity of having a large number of agents. (iii) Our DoubleSWEET consumes much lower processing time and memory than the other methods, especially when the number of agents is large, validating the significance and necessity of our approach.

Reflections on Revisions to the Main Text

We have tried to include this result in the main text. But the page limit does not allow this, we have moved it to the appendix and provided a clear explanation in the experimental section of the main text.

AuthorsOpenReview ↗

Weakness 2

Part 2/4

Weakness 2: Space Complexity and Large State Space

To begin with, we would like to clarify that a more accurate expression for the space complexity of our approach is O(SNd+d2)O(S_N d+d^2), where SNS_N denotes the maximum number of occupied states in the population flow after it has stabilized for sufficiently large NN. In the following, we explain why this complexity is much lower than O(NT)O(NT) and discuss how to handle large finite and continuous state spaces, respectively.

Space Complexity Reduction: Although our approach has a space complexity linear in SNS_N, it still provides a much lower complexity than O(NT)O(NT). This is because, for games that can be modeled as MFGs, the number of agents NN is commonly much larger than SNS_N. From the perspective of propagation of chaos, as the number of agents NN increases, the empirical population distribution at each time step converges to a deterministic mean-field population distribution. Consequently, for states with positive population mass, multiple agents tend to occupy the same state as the population grows.

Dealing with Large State Space: We provide a detailed discussion of how to handle scenarios with a large number of occupied states in finite state spaces.

For a large occupied finite state space, we can further compress the state-wise traces using linear function approximation. Based on this compression, the resulting space complexity becomes

O(M2+Md+d2),M≪SN,O(M^2+Md+d^2), \qquad M\ll S_N,

where MM is the dimension of the feature vector used to represent the compressed traces.

The detailed steps are as follows:

Step 1: Linear Function Approximation. We represent the trace associated with each state as

zt(s)≈z^t(s)=Wt⊤ψ(s),z_t(s) \approx \widehat z_t(s) = W_t^\top \psi(s),

where ψ(s)∈RM\psi(s)\in\mathbb{R}^M is a feature vector, Wt∈RM×dW_t\in\mathbb{R}^{M\times d} is the parameter matrix, and M≪SNM\ll S_N.

Step 2: Trace Recursion. Recall that the original state-wise trace satisfies

zt(s)=φt(s)+βAt∑s′Bt(s′∣s)zt−1(s′),z_t(s) = \varphi_t(s) + \beta A_t \sum_{s'} B_t(s'|s)z_{t-1}(s'),

where

Bt(s′∣s)=Γt(s′,s)ut(s),β=γλ.B_t(s'|s) = \frac{\Gamma_t(s',s)}{u_t(s)}, \qquad \beta=\gamma\lambda.

Substituting the linear approximation of the previous trace gives

qt(s;Wt−1)=φt(s)+βAt∑s′Bt(s′∣s)Wt−1⊤ψ(s′).q_t(s;W_{t-1}) = \varphi_t(s) + \beta A_t \sum_{s'}B_t(s'|s) W_{t-1}^\top\psi(s').

Step 3: Parameter Update. We obtain the updated parameters by solving a regularized weighted least-squares problem:

\left\lbrace \sum_{s\in\mathcal{S}_t} u_t(s) \left\\|W^\top\psi(s)-q_t(s;W_{t-1})\right\\|_2^2 +\eta\\|W\\|_F^2 \right\rbrace.$$ Here, $\eta>0$ is a small regularization coefficient that controls the strength of the Frobenius-norm penalty. This regularization discourages excessively large parameter values and improves the numerical stability of the least-squares estimation. **Step 4: Closed-form Update.** Define $$G_t = \sum_s u_t(s)\psi(s)\psi(s)^\top,$$ $$F_t = \sum_s u_t(s)\psi(s)\varphi_t(s)^\top,$$ and $$H_t = \sum_{s,s'}\Gamma_t(s',s)\psi(s)\psi(s')^\top.$$ The resulting parameter update is $$\boxed{ W_t = (G_t+\eta I_M)^{-1} \left[F_t+\beta H_tW_{t-1}A_t^\top\right]. }$$ Here, $I_M$ denotes the $M\times M$ identity matrix, and $\eta>0$ is the same small regularization coefficient introduced in Step 3. In particular, since $G_t$ is a positive semidefinite matrix (assuming nonnegative population weights $u_t(s)$), adding $\eta I_M$ makes $G_t+\eta I_M$ positive definite and therefore invertible. This ensures that the closed-form update remains well-defined even when the feature vectors are linearly dependent or $G_t$ is singular. The regularization also helps improve numerical conditioning and avoid excessively large estimates. The initialization is given by $$W_0=(G_0+\eta I_M)^{-1}F_0.$$
AuthorsOpenReview ↗

Weakness2: experiment

Response to Reviewer 3 — Part 3 of 4

Weakness 2: Space Complexity and Large State Space

Dealing with Continuous State Space: For continuous state spaces, there are two approaches.

Option 1: (RBF). The same construction as above can be extended to continuous state scenario by replacing the summations with integrals with respect to the population measure utu_t and the joint transition measure Γt\Gamma_t:

\int_{\mathcal X}(\cdot)\,u_t(ds),$$ and $$\sum_{s,s'}\Gamma_t(s',s)(\cdot) \quad\longrightarrow\quad \int_{\mathcal X}\int_{\mathcal X}(\cdot)\,\Gamma_t(ds',ds).$$ Here, $\Gamma_t(ds',ds)=u_t(ds)B_t(ds'|s)$ denotes the joint measure of the current and next states. Accordingly, the sufficient statistics become $$G_t = \int_{\mathcal X}\psi(s)\psi(s)^\top u_t(ds),$$ $$F_t = \int_{\mathcal X}\psi(s)\varphi_t(s)^\top u_t(ds),$$ and $$H_t = \int_{\mathcal X}\int_{\mathcal X} \psi(s)\psi(s')^\top\Gamma_t(ds',ds).$$ The resulting parameter update retains the same closed form: $$W_t = (G_t+\eta I_M)^{-1} \left[F_t+\beta H_tW_{t-1}A_t^\top\right].$$ the resulting space complexity remains the same. **Option 2: Cut Continuous State Space into Bins.** Another method is to cut continuous state space into bins, which turns continuous situation into finite state situation. **Experiments under Continuous State Space:** To further evaluate our method in continuous-state environments, we conduct an additional experiment using a one-dimensional linear-Gaussian system with quadratic rewards, which is a standard instance of the classical linear-quadratic-Gaussian (LQG) framework. |$N$|Algorithm|Trace Representation|Relative RMSE (%)|Memory (KiB)|Time (ms)| |:--|:--|:--|:--|:--|:--| |500|MC-LS|Original|$3.931 \pm 1.669$|191.95|0.67| |500|MC-LS|RBF ($M=8$)|$4.691 \pm 2.143$|26.77|4.75| |500|MC-LS|Uniform Bin ($K=128$)|$7.134 \pm 4.719$|122.05|6.30| |500|MC-LS|Quantile Bin ($K=128$)|$6.443 \pm 3.347$|122.05|6.81| |500|LSTD(0.8)|Original|$3.815 \pm 1.606$|191.95|0.99| |500|LSTD(0.8)|RBF ($M=8$)|$3.652 \pm 1.486$|26.77|5.42| |500|LSTD(0.8)|Uniform Bin ($K=128$)|$3.785 \pm 1.406$|122.05|7.18| |500|LSTD(0.8)|Quantile Bin ($K=128$)|$3.727 \pm 1.425$|122.05|7.96| |2,000|MC-LS|Original|$1.699 \pm 0.295$|719.30|1.79| |2,000|MC-LS|RBF ($M=8$)|$2.179 \pm 0.221$|26.77|17.89| |2,000|MC-LS|Uniform Bin ($K=128$)|$2.845 \pm 1.034$|122.05|8.91| |2,000|MC-LS|Quantile Bin ($K=128$)|$5.358 \pm 1.109$|122.05|9.73| |2,000|LSTD(0.8)|Original|$1.704 \pm 0.288$|719.30|3.39| |2,000|LSTD(0.8)|RBF ($M=8$)|$1.574 \pm 0.364$|26.77|20.89| |2,000|LSTD(0.8)|Uniform Bin ($K=128$)|$1.549 \pm 0.417$|122.05|11.45| |2,000|LSTD(0.8)|Quantile Bin ($K=128$)|$1.549 \pm 0.553$|122.05|11.74| |8,000|MC-LS|Original|$1.014 \pm 0.218$|2828.67|6.15| |8,000|MC-LS|RBF ($M=8$)|$1.306 \pm 0.291$|26.77|74.28| |8,000|MC-LS|Uniform Bin ($K=128$)|$1.202 \pm 0.279$|122.05|19.91| |8,000|MC-LS|Quantile Bin ($K=128$)|$4.789 \pm 0.332$|122.05|20.98| |8,000|LSTD(0.8)|Original|$1.011 \pm 0.245$|2828.67|28.78| |8,000|LSTD(0.8)|RBF ($M=8$)|$0.987 \pm 0.289$|26.77|82.57| |8,000|LSTD(0.8)|Uniform Bin ($K=128$)|$1.010 \pm 0.302$|122.05|28.23| |8,000|LSTD(0.8)|Quantile Bin ($K=128$)|$0.939 \pm 0.295$|122.05|31.81| 1. **Memory:** When $N=8000$, the Original method requires 2828.67 KiB, whereas RBF requires only 26.77 KiB and Binning requires 122.05 KiB. Both compression methods substantially reduce the working memory. 2. **Accuracy:** Under LSTD, RBF and both Binning methods achieve estimation accuracy comparable to the Original method when $N=8000$. In particular, Quantile Binning achieves a relative RMSE of 0.939%. 3. **Runtime:** Binning is considerably faster than the current RBF implementation. In particular, when $N=8000$, Uniform Binning requires only 19.91 ms for MC-LS, compared with 74.28 ms for RBF.
Reviewer_nhdoOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies replay-free policy evaluation for finite-horizon MFGs and develops two algorithms, Private Population Dutch Trace and DoubleSWEET, which remove the memory dependence on the horizon and the number of agents, providing a memory-efficient solution to large finite-N player games. The authors provide a set of theoretical analyses, laying out the foundation for these two algorithms. Finally, the authors verify the effectiveness and efficiency of the proposed algorithms in a synthetic Garnet-inspired finite-state MFG environment.

Critical strengths

This paper is theory-intensive. I have to admit that I am not an expert in the theory of MFGs, so I did not check all the details of the proofs.

The problem of addressing the memory bottleneck in finite-horizon MFG policy evaluation is important and relevant to the MFG and multi-agent system community. The authors propose to compress the agents' histories by storing traces (agent-wise or state-wise), which is well-motivated and reasonable.

As I said, I am not a theory expert, so I cannot accurately evaluate the theoretical contribution of this paper. I would like to see more discussion from other reviewers. My rating of this paper is largely based on the idea of the proposed algorithms and the experiments; thus, I have reservations about my rating and must lower my confidence.

Critical weaknesses

One question in my mind is the linear form of the value function used in the paper. It seems this is the foundational assumption for this paper; it would be good to discuss the reason for this choice, as a linear function typically has limited expressiveness.

Questions for authors

See weaknesses.

1 comment

Thank you for your comment. Justification of Linear Form:

  1. Our choice of linear value-function approximation follows the classical treatment of function approximation in reinforcement learning (Sutton and Barto, 2018, Section 9.3).

  2. This form has also been adopted in several control-oriented reinforcement learning applications, including traffic signal control and industrial energy management. For example, Alegre et al. (2022) employed Fourier-basis linear function approximation for traffic signal control in a MATSim simulation of 22 intersections in Cottbus, Germany. van den Bovenkamp et al. (2023) adopted tile-coded linear function approximation for industrial energy scheduling, using measured electricity consumption, photovoltaic generation, and wholesale electricity price data from a manufacturing company in the Netherlands.

  3. From the analytical perspective, linear function approximation can ensure stable training and provide theoretical error bounds at convergence. Note that trace-based methods employ the bootstrapping idea, in which the output of a function is also used as part of its own learning target. This coupling makes it difficult to guarantee that the learning process converges to a fixed point across general neural network architectures.

Tackling Non-Linear Expression:

  1. Despite the linear form of value function, our approach can deal with non-linear expressions through feature design. Specifically, when nonlinear expressiveness is required, nonlinear features can be used to capture nonlinear relationships. For example, if the original state is xx, the features can include xx, x2x^2, x3x^3, and so on. Similar to a Taylor expansion, a linear combination of these basis functions can still represent a broad class of functions. On the other hand, when the feature representation is fixed and cannot be formulated as above, convergence guarantees can be established.

  2. Intuitively, even if the feature representation changes, convergence may still be guaranteed as long as it evolves sufficiently slowly, such that its changes are negligible compared with those of the parameter vector. {The feature representation can also be parameterized by a neural network; however, this would require sufficiently slow updates of the representation and further theoretical analysis to establish convergence guarantees.} This falls under representation learning in reinforcement learning, and could be an interesting direction for future work.

Reflections on Revisions to the Main Text

We have included a footnote in the main text to discuss this issue.

References

Alegre, L. N., Ziemke, T., & Bazzan, A. L. C. (2022). Using reinforcement learning to control traffic signals in a real-world scenario: An approach based on linear function approximation. IEEE Transactions on Intelligent Transportation Systems, 23(7), 9126–9135. https://doi.org/10.1109/TITS.2021.3091014

Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press.

van den Bovenkamp, N., Giraldo, J. S., Salazar Duque, E. M., Vergara, P. P., Konstantinou, C., & Palensky, P. (2023). Optimal energy scheduling of flexible industrial prosumers via reinforcement learning. In Proceedings of the 2023 IEEE Belgrade PowerTech (pp. 1–6). IEEE. https://doi.org/10.1109/PowerTech55446.2023.10202699

Reviewer_okVLOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper is related to mean field game (MFG) theory, which is a framework to study situations with a large number of interacting players by passing to the limit and considering a continuum of agents. This work focuses on the question of policy evaluation for discrete time, finite state/action space MFGs. It proposes a replay-free method, analyzes it and present some numerical experiments.

Critical strengths

(1) The framework is clearly defined.

(2) The paper provides a theoretical analysis.

(3) Numerical results are also provided.

Critical weaknesses

(1) The interest of the question studied in this work is not clear: policy evaluation is typically much easier than policy training, which is the real bottleneck to scale up RL for MFGs.

(2) The setting is very restrictive and is probably not a situation in which the proposed method is relevant: when the state space is finite, we don’t need to simulate all the agents, we can simply evolve the mean field using the transition matrix.

(3) The numerical experiments are very limited: only a Garnet-style setting is considered; while interesting it is not sufficient to illustrate how interesting the method is for more structured examples that are actually encountered in more realistic models.

(4) The paper is very long (around 90% of the paper is after the 9-page main text), which means it is hard to detect potential issues (correctness or others) hidden in the details.

Questions for authors
  1. Please provide a few different examples satisfying all the assumptions you require.

  2. Please explain, for each assumption whether you expect it to be necessary or not for the analysis.

  3. For each of the bounds, please provide the dependence on the other parameters of the model (in particular the number of states, actions and time steps).

  4. Can you comment on whether (and if yes, how) your methods can be combined to also accelerate some RL algorithms for MFGs? Does accelerating policy evaluation really accelerate the overall algorithms?

6 comments
AuthorsOpenReview ↗

Weakness 1 to 4

We sincerely thank you for your valuable suggestions and comments. We provide the following point-by-point response.

Weakness 1: Policy Training and Policy Evaluation

Existing methods for solving mean field games (MFGs) can be roughly classified into two categories: best-response (BR)-based methods and policy-evaluation (PE)-based methods. According to the concern on policy training being the bottleneck, we guess that the reviewer may interpret our work as a study of BR-based methods. However, we focus on PE-based methods, under which policy training is not the main part, and policy evaluation is the main bottleneck.

Best-Response (BR)-Based Methods: BR-based methods iteratively train the population policy by computing the best response to the population distribution resulting from the current policy and updating the policy accordingly. Therefore, policy training is the actual bottleneck.

Policy-Evaluation (PE)-Based Methods: Two steps are repeated iteratively: (i) the current Q-table that records the action value determines a policy, which is then fixed to generate the corresponding population flow; (ii) policy evaluation is conducted to generate a new Q-table under this population flow, and the previous and newly estimated Q-tables are then combined through a weighted average. Thus, after policy evaluation, policy can be determined using the updated Q-table without policy training to best response, so policy evaluation is the main bottleneck.

In this process, policy evaluation accounts for almost the entire workload. Once policy evaluation is completed, policy training is almost considered complete.

In the Introduction section of the manuscript, we have refined the way we introduce PE-based method process to make this point clearer.

Weakness 2: Evolve MFGs using Transition Matrix

We would like to clarify that we consider the case where the transition kernel is unknown, so the transition matrix is unknown and cannot be used to evolve MFGs directly. This is one of the major challenges we addressed. Although there may exist a two-step alternative by first estimating the transition matrix and then using it to estimate the value function, our method provides a single-step approach by estimating the value function directly from the observed interactions, which saves the memory required to store the estimated transition matrices.

This point was explained in the last paragraph of Section Problem Settings, and we have refined the reason why we don't use transition matrix in problem settings to further clarify this point.

Weakness 3: Other Experimental Settings

We conducted an experiment on a day-to-day commuting traffic game during peak commuting hours, where each day represents one game. The results are presented in Appendix F, and demonstrate that our method can converge to an approximate Nash equilibrium.

To address your concern, we further increased the complexity of the road network and conducted policy evaluation again. DoubleSWEET continued to perform well, maintaining its advantages in terms of memory usage and computational time. The experimental results are shown below:

Table: Fixed-policy value estimation on the 2,000-state routing network.

MethodProcessing (s)Final solve (s)Total (s)Peak arrays (MiB)Weighted RMSE
MC-LS0.54810.00250.550738.40.008916
DoubleSWEET-MCLS0.44120.00220.443526.80.008876
Private Dutch0.7254---0.725430.80.542639
DoubleSWEET0.5328---0.532819.10.542639
LSTD(λ\lambda)0.74131.01651.757869.90.017653
DoubleSWEET-LSTD(λ\lambda)0.48080.06070.541548.60.017648
We achieve similar outcome in this experiment with respect to memory, time and accuracy.

Weakness 4: Presentation and Soundness Issues

Thank you for this comment. We have revised the appendix to improve readability. We have 1) outlined a Proof Overview at the beginning of appendix, and 2) structured the proof along the outlined proof strategy.

AuthorsOpenReview ↗

Question1 and 2

We provide the rationale, examples, and necessity of each assumption below.

Assumption 1: Markov Property

Given the current agent state and empirical population distribution, the conditional distribution of the next state does not depend on the agent's past history.

L(Xt+1i,N∣FtN)=Pt(⋅∣Xti,N,UtN).\mathcal{L}(X_{t+1}^{i,N}\mid\mathcal{F}_t^N)=P_t(\cdot\mid X_t^{i,N},U_t^N).

Here, FtN\mathcal{F}_t^N denotes the information available from the entire finite population up to time tt.

Rationale: This assumption is common in existing MFG works (Gomes et al., 2010; Saldi et al., 2018).

For example, in a traffic network, each agent represents a vehicle. Its state represents its current road segment (and destination), while the empirical population distribution describes traffic density across road segments. The probability of transitioning to the next road segment depends on the vehicle's current state and the current traffic distribution, rather than its previous route history.

Necessity:

This condition plays a fundamental role in the proof, as it yields:

eti,N,D⊥!!!⊥δt,i′∣(Xti,N,UtN).e_t^{i,N,D}\perp\\!\\!\\!\perp\delta'_{t,i}\mid(X_t^{i,N},U_t^N).

This is the key assumption underlying both the expected-trace recursion and Theorem 1 based on expected traces. It is formalized as transition-model setting C-A1 in Appendix C, Sec. C.2. The corresponding Markov property of the representative mean-field process, used to derive the expected-trace recursion, is stated in setting C-M1 in Appendix C, Sec. C.3.

Assumption 2: Bounded Feature Map

Bϕ:=max⁡0≤t≤T,x∈X∣ϕt(x)∣2<∞,B_\phi:=\max_{0\leq t\leq T,\\ x\in\mathcal X}\\|\phi_t(x)\\|_2 < \infty,

where BϕB_\phi is the maximum Euclidean norm of the feature vectors over all states and time steps.

Rationale:

In practice, we would never map a state to an infinite value.

Necessity:

This assumption is established as a derived property in Appendix C, Sec. C.3 (C-M3), and Appendix D, Sec. D.2 (D-P5). It is subsequently used in the proofs of Theorems 2 and 3 in Appendix D, Secs. D.3 and D.4.

Assumption 3: Idiosyncratic Transition Noise without Common Noise

Conditioned on the current information of the entire finite population, different agents' next-state transitions are independent, with no additional shared transition noise. Formally,

\bigotimes P_t\left(\cdot\mid X_t^{i,N},U_t^N\right), \quad 0\leq t<T.$$ Here, ⊗ denotes the product distribution. **Rationale:** In congested traffic, conditioned on the current configuration, each vehicle independently transitions to its next road segment according to a probability determined by traffic density. **Necessity:** This assumption is used in Theorems 2 and 3, where conditional independence across agents allows us to upper-bound the expected squared error. It is stated as Assumption D-C2 in Appendix D, Sec. D.1, and restated as Assumption D-T3-A2 in Sec. D.4. It is used in the finite-population consistency analysis in Sec. D.2 and in the proofs of Theorems 2 and 3 in Secs. D.3 and D.4. ### Assumption 4: Lipschitz Continuity with Respect to the Population Distribution Both the transition kernel and reward function are assumed to be Lipschitz continuous with respect to the population distribution. Specifically, $$\begin{aligned} &\\|P_t(\cdot\mid x,u)-P_t(\cdot\mid x,v)\\|_{\mathrm{TV}} \leq L_P\\|u-v\\|_1,\\\\ &|r_t(x,u)-r_t(x,v)| \leq L_r\\|u-v\\|_1, \end{aligned}$$ for all $0\leq t < T$, $x\in\mathcal X$, and $u,v\in\mathcal P(\mathcal X)$, where $\mathcal P(\mathcal X)$ denotes the set of probability distributions over the state space $\mathcal X$. **Rationale:** Consider a car traveling on the same road. If the traffic distribution across the city changes only slightly, neither the probabilities of this car transitioning to different roads nor its received reward should change dramatically. The above Lipschitz conditions capture this limited variation. **Necessity:** Our goal is to investigate whether a sufficiently large finite population can approximate the mean-field system in Theorem 3, thereby providing a basis for modeling MFGs. Thus, our results are not intended for environments in which an arbitrarily small change in the population distribution causes a disproportionately large change in transition dynamics or rewards, since such environments are not well captured by this approximation. The transition-kernel Lipschitz condition is stated as Assumption D-C3 in Appendix D, Sec. D.1 (and restated as Assumption D-T3-A3 in Sec. D.4). The reward Lipschitz condition is separately stated as Assumption D-T3-A5 in Sec. D.4. Both conditions are used in the proof of Theorem 3.
AuthorsOpenReview ↗

assumption5、Question3 and 4

Assumption 5: Consistent i.i.d. Initialization.

The initial states are independently and identically distributed (i.i.d.), as specified in the problem setting. Formally,

X01,N,…,X0N,N∼iidu0.X_0^{1,N},\ldots,X_0^{N,N}\overset{\mathrm{iid}}{\sim}u_0.

Rationale:

In practice, for example, the initial distribution of cars starting their commutes to or from work can be approximated by independent samples from the same initial distribution.

Necessity:

This assumption is used at the beginning of the error analysis for propagation of chaos (PoC).

These assumptions are standard in classical mean-field game analysis and are satisfied by a broad class of population-interaction environments.

This condition is formally stated as Assumption D-C1 in Appendix D, Sec. D.1, and is restated as Assumption D-T3-A1 in Sec. D.4; it is used in the finite-population consistency analysis in Sec. D.2, which underpins the proofs of Theorem 3 in Secs. D.3 and D.4.

Reflections on Revisions to the Main Text

Due to the strict page limit in the original submission, we could only briefly introduce the relevant settings and assumptions together in the main text. With the additional page now available, we have explicitly stated the settings and assumptions required by each theorem before presenting the theorem in the revised main text.

Question 3: Dependence on Parameters in Bounds

We discuss the two bounds in Theorems 2 and 3, respectively, as follows.

For Theorem 2, the bound can be explicitly written as

\mathbb{E}\left[ \left||\hat m_t^{N,D}-m_t^{\mathrm{priv},N,D}\right||_{1,2} \right] \leq \frac{2|\mathcal S|B_\phi}{\sqrt N} \left(\sum_{k=0}^{T}q^k\right) \left(\sum_{j=1}^{T}q^j\right).$$ where $$q=\gamma\lambda(1+\alpha B_\phi^2).$$ The error bound grows linearly with the state-space size $|\mathcal S|$. The factor $q$ determines how the compression error propagates over time. When $q<1$, which can be achieved by using a relatively small discount factor $\gamma$, a small trace parameter $\lambda$ (corresponding to a higher degree of bootstrapping), and a sufficiently small learning rate $\alpha$, the two geometric sums remain bounded independently of the horizon $T$. Consequently, the trace-compression error can be controlled even over an arbitrarily long horizon. When $q>1$ but remains close to $1$, the error can still be controlled over sufficiently long but finite horizons, although the bound grows with $T$. For Theorem 3, $$\max_{0\leq t\leq T} \mathbb{E}\left[ \max\lbrace \left||w_t^{N,D}-w_t^{MF}\right||_2, \left||w_t^{N,C}-w_t^{MF}\right||_2, \left||w_t^{N,D}-w_t^{N,C}\right||_2 \rbrace \right] \leq \frac{C_{\mathrm{learner},T}}{\sqrt N}.$$ The bound can be written as follows: $$\kappa=\gamma\lambda\max\{1,|1-\alpha B_\phi^2|\}.$$ Depending on the value of $\kappa$, the prefactor satisfies the following bounds. If $\kappa<1$, $$C_{\mathrm{learner},T}=O(|\mathcal S|\xi_0^T).$$ If $\kappa=1$, $$C_{\mathrm{learner},T}=O(|\mathcal S|T^{2T}\xi_1^T).$$ If $\kappa>1$, $$C_{\mathrm{learner},T}=O(|\mathcal S|\kappa^{2T^2}\xi_2^T).$$ Here, $\xi_0,\xi_1,\xi_2>1$ are constants independent of $T$ and $N$. In particular, for any constant $\xi>\max\{1,\kappa^2\}$, independent of $T$ and $N$, we have $$C_{\mathrm{learner},T}=O(|\mathcal S|\xi^{T^2}).$$ The error bound grows linearly with the state-space size $|\mathcal S|$, and $\kappa$ cannot be too large to avoid rapid growth of the learner error bound with the horizon $T$. Moreover, $\kappa$ can be controlled by choosing an appropriate learning rate. In particular, since $\alpha>0$, a sufficient condition $\alpha B_\phi^2\leq 2$ ensures that $$|1-\alpha B_\phi^2|\leq 1,$$ and consequently, $$\kappa=\gamma\lambda\leq 1.$$ Thus, this condition leads to the more favorable error bound. **Why is $|\mathcal A|$ not included?** The effects of actions are implicitly incorporated into the policy-induced reward and transition dynamics in our settings, and the theoretical bounds depend on $|\mathcal S|$ rather than $|\mathcal S||\mathcal A|$. If extended to action-value estimation, the state-action pairs $(x,a)$ can be treated as an augmented state space, leading to a dependence on $|\mathcal S||\mathcal A|$. We have explained this in the footnote of the problem-setting section. ## Question 4: Accelerating RL Algorithms & Policy Evaluation We clarify that DoubleSWEET can serve as a policy-evaluation module in PE-based MFG methods, but does not directly accelerate BR optimization or the RL algorithms used to compute BRs. Meanwhile, as mentioned in our response to Weakness 1, we can replace our method with procedures (i) and (ii). The averaging of the previous and current Q-tables is equivalent to averaging the old and new learner parameters in our setting. Therefore, memory usage can be reduced throughout the entire process.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.