- 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 memory bottleneck of replay-free policy evaluation (where is the number of agents and 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 and .
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 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 from to barely improves the value estimation error (e.g., DoubleSWEET decreases only from to , and DoubleSWEET-MC-LS from to ). Because the estimation error plateaus at relatively small sample sizes, the practical necessity of processing all agents is questionable. In fact, simply tracking a small subset of agents (as shown by the Subsampled Private Dutch baseline with agents) achieves nearly identical accuracy () 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 in the introduction is somewhat misleading without immediate qualification. It is only with respect to and , while scaling linearly with the number of states as . 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 is too large?
5 comments
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 , where denotes the maximum number of occupied states in the population flow after it has stabilized for sufficiently large . In the following, we explain why this complexity is much lower than and discuss how to handle large finite and continuous state spaces, respectively.
Space Complexity Reduction: Although our approach has a space complexity linear in , it still provides a much lower complexity than . This is because, for games that can be modeled as MFGs, the number of agents is commonly much larger than . From the perspective of propagation of chaos, as the number of agents 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
where 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
where is a feature vector, is the parameter matrix, and .
Step 2: Trace Recursion. Recall that the original state-wise trace satisfies
where
Substituting the linear approximation of the previous trace gives
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.$$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 and the joint transition measure :
\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.
Weakness1
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):
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 N 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.