- Rating
- 2
- Confidence
- 1
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
Overall, I think this is an interesting paper with a nice theoretical insight. The idea of extending spatial locality to higher-order Taylor derivatives is novel, and the proposed methods are well motivated and supported by solid experiments. My main concerns are about the probability guarantee in Theorem 2, the mismatch between the theory and experiments, and some limitations in the scalability and decentralization claims. I would be open to raising my score if the authors can address these concerns in the rebuttal.
Critical strengths
- The paper shows that not only the Q-functions but also their higher-order Taylor derivatives exhibit exponential spatial decay. This provides a nice way to reduce the representation complexity from global to local neighborhoods.
- The paper builds on the locality result to propose the Taylor Centroid critic, LTC, and NTC, with clear approximation–estimation tradeoffs.
- The authors test different environments, include several useful ablations, and scale up to 1,000 agents. The derivative-decay experiments are also helpful in supporting the theoretical motivation.
Critical weaknesses
-
Theorem 2 has a nontrivial conditioning issue in its high-probability guarantee. The theorem claims that the critic error bound holds with probability at least , conditioned on the empirical LSTD matrices being well-conditioned. However, the proof first establishes an unconditional concentration bound and then intersects it with the random event , which depends on the same rollout data. This seems to establish only , rather than the claimed . Without a lower bound on or a concentration argument valid after conditioning on , the stated confidence level does not follow. The theorem may therefore need to be reformulated or supported by an additional argument.
-
The analysis assumes compact state/action spaces, bounded rewards, and bounded policy scores, while the LQR and switched-LQR experiments use Gaussian noise, quadratic rewards, and Gaussian policies. These violate the boundedness assumptions, so it is unclear whether Theorem 3 applies to these main benchmarks.
-
The representation complexity can still grow quickly with the Taylor order, locality radius, state dimension, and graph degree. Also, centroid selection relies on the global state, so the critic is not fully decentralized. The stronger-performing NTC also lacks the finite-sample guarantee provided for LTC.
Questions for authors
- Could the authors clarify the probability statement in Theorem 2? The current proof seems to support a joint bound rather than a conditional one. Can the theorem be revised, or can the authors bound the probability of the LSTD matrices being well-conditioned?
- How should we understand the theoretical guarantees in the LQR and switched-LQR experiments, given the unbounded noise, rewards, and policy scores? Could the authors provide an extension of the theory or experiments under bounded settings?
- How important is access to the global state for centroid selection? It would be interesting to see whether the method still works well when each agent selects its centroid using only local observations.
7 comments
Clarifications on Theoretical Assumptions, Global Centroid Selection, and Scalability [2/2]
Q/C3. On the importance of the global state for centroid selection
As explained in Section 3.1, our method does not claim fully decentralized critic evaluation: selecting centroids in the global state space is a deliberate choice that allows the cluster index to inject global information into otherwise local critics.
Global selection is particularly useful under latent system-wide conditions. Figure 8 shows that centroids align with switched LQR operating regimes. In switched LQR, multinomial logistic regression on local neighborhoods predicts the mode with only 51-57% accuracy (similarly with an MLP), versus 82-84% using the global cluster index alone (assigning each cluster its majority mode), close to the 83--85% obtained by logistic regression on the full global state. These results show that global clusters capture substantial information about the latent mode. We also directly compare global versus local centroid selection (K-medians is applied for each agent's neighborhoods) on switched LQR (relative optimality gap in %, mean ± std. over five seeds):
| LTC global | LTC local | NTC global | NTC local | |
|---|---|---|---|---|
| 4.73 ± .06 | 5.24 ± .06 | 4.90 ± .08 | 5.28 ± .11 | |
| 4.68 ± .02 | 5.20 ± .04 | 4.67 ± .04 | 5.19 ± .07 | |
| 3.44 ± .02 | 4.54 ± .06 | 3.40 ± .06 | 3.92 ± .13 | |
| 3.45 ± .01 | 5.57 ± .06 | 3.44 ± .07 | 3.94 ± .14 | |
| 1.63 ± .02 | 2.36 ± .05 | 1.69 ± .13 | 2.23 ± .21 |
Global selection yields lower gaps in all ten comparisons: by 0.51-2.12 percentage points for LTC and 0.38-0.54 for NTC (five configurations each). On LQR and Kuramoto, which lack latent global modes, local and global clustering perform similarly. This supports using global centroids to capture hidden system-wide regimes.
Revision. We will clarify global versus local centroid selection in Section 3.1, report the mode-prediction and local-clustering ablations in Appendix D.5, and discuss limitations in Section 7.
C4. Scalability of the representation complexity.
We agree that representation complexity can increase with the Taylor order, locality radius, local state dimension, and graph degree. While the dependencies highlighted by the reviewer remain, they involve local quantities that are often manageable in practice, unlike the global system dimension, which grows with and whose dependence our approach eliminates. In particular:
-
Graph degree and state dimension. With other quantities fixed, scales polynomially with degree and local state dimension , which are typically small and independent of . Examples include building control (, ) and Kuramoto (, ) in Ren et al. (2025), wireless grids (, ) in Qu et al. (2022), epidemic spreading (, ) in Zhang et al. (2023), and building grids (, ) in Shin et al. (2023). Thus, replacing dependence on with dependence on the typically small and yields a substantial scalability gain.
-
Locality radius . Our theory establishes that the error from discarding distant agents decays exponentially with at a rate governed by , enabling accurate local approximations with small radii. Appendix D.1 further shows particularly small empirical decay rates in our environments, where achieves competitive performance, although the required radius remains environment-dependent.
-
Taylor order . We primarily use low orders (), which suffice in our experiments. For LQR and switched LQR, increasing from to substantially improves critic estimation and policy performance, while brings little additional benefit (Figures 1 and 6). Similarly, low orders achieve strong performance on Kuramoto.
Hence, our claim is that, despite these dependencies, many control problems can be modeled by low-degree graphs, with small local state dimensions, and can be accurately approximated using relatively small and low . Consequently, representation complexity typically remains manageable in practice. We acknowledge that settings requiring substantially larger values of these quantities remain an interesting direction for future work.
Revision. We will clarify the dependence on , , , and and their typical values in Section 3.1 and Appendix F.6, and discuss limitations in Section 7.
C5. Guarantees and NTC.
We agree that the lack of finite-sample guarantees for NTC is a limitation, as acknowledged in Section 7. Extending such guarantees to nonlinear TD remains challenging future work. Nevertheless, NTC offers greater expressivity than LTC, and Theorem 3 still applies provided its critic approximation error is controlled.
Revision. We will clarify these distinctions in Sections 3.2 and 4.
References
Ren et al. (2025). Scalable Spectral Representations for Multiagent Reinforcement Learning in Network MDPs. AISTATS 2025.
Wang et al. (2026). Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces. arXiv preprint.
Qu et al. (2022). Scalable Reinforcement Learning for Multiagent Networked Systems. Operations Research.
Zhang et al. (2023). Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems.
Shin et al. (2023). Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems. SIAM Journal on Control and Optimization.
Clarifications on Theoretical Assumptions, Global Centroid Selection, and Scalability [1/2]
We thank the reviewer for the detailed and constructive feedback. We address each point below.
Q/C1. Conditional high-probability statement in Theorem 2.
The phrase "Conditionally on the centroids and on ⋂i=1Nσmin(Ai)≥cLSTD>0" incorrectly suggests a conditional probability guarantee, which is not established by our proof. Our intended statement is that, with probability at least 1−δ, the error bound holds whenever the LSTD matrices satisfy the conditioning requirement.
More precisely, let C=⋂i=1Nσmin(Ai)≥cLSTD>0 and let E denote the event that the error bounds of Theorem 2 hold for all agents.
Our proof indeed establishes P(C∩Ec)≤δ, that is P(Cc∪E)=1−P(C∩Ec)≥1−δ.
Thus, the correct statement is: with probability at least 1−δ, if the empirical LSTD matrices satisfy the conditioning requirement, then the error bounds of Theorem 2 hold for all agents.
Revision. We will correct the statement of Theorem 2 in Section 3.2 and clarify its interpretation in Appendix F.
Q/C 2. Theory assumes bounded quantities, whereas LQR experiments use Gaussian noise and quadratic costs.
We agree that the theoretical Gaussian LQR does not strictly satisfy our boundedness assumptions. This discrepancy between bounded theoretical assumptions and Gaussian linear-quadratic benchmarks is common in networked RL. For instance, Ren et al. (2025) establish guarantees under compactness assumptions while evaluating a similar Gaussian LQR benchmark. Similarly, Wang et al. (2026) evaluate a Gaussian LQR benchmark with empirical state and action clipping. As acknowledged in the introductory remark of Appendix B, our experiments should be interpreted through a sufficiently large compactification of the dynamics. We elaborate on this argument below.
Interpretation of our LQR experiments. For both of our LQR settings, over any fixed finite horizon and under fixed affine Gaussian policies, the Gaussian tails of the state distributions ensure that the probability of exiting a compact state-space region of radius R decays exponentially with R2. Thus, sufficiently large clipping radii can be chosen a priori so that clipping remains inactive with arbitrarily high probability over any fixed finite collection of rollouts.
More precisely, our recorded experimental trajectories should be understood exactly as trajectories of the compactified LQR dynamics
St+1=clip(ASt+BAt+εt,−R⋆,R⋆).
where clipping remained inactive. Indeed, there exists a sufficiently large fixed radius R⋆ encompassing every state visited throughout our experiments and generally making clipping statistically negligible. Introducing state clipping at this radius leaves every recorded trajectory unchanged. Although state clipping was not explicitly implemented, our experimental results should be interpreted as trajectories of this compactified MDP. The same reasoning applies to switched LQR.
Actions were clipped at a very large radius in our implementation, although clipping never activated in our experimental rollouts. Consequently, the Gaussian policy scores used in our implementation coincide with the exact scores of the clipped policies on the recorded samples. Assuming bounded policy parameters during training, the clipped policies have uniformly bounded scores over the compact state-action space.
Applicability of our assumptions. Importantly, the compactified MDP has compact state and action spaces, and bounded rewards since the reward functions are smooth on these compacts.
It also satisfies Assumption 1. More specifically, although clipping introduces boundary atoms in the transition distribution, the smoothing argument of Appendix E.4.1 can be adapted by expressing expected future rewards as integrals against the Gaussian density before clipping. Differentiating this density yields derivative bounds uniform in time, policy, and network size under the bounded-degree and uniform local-regularity conditions. Hence, Assumption 1 holds for the compactified MDP. This establishes the applicability of our theoretical framework to the compactified MDP.
Furthermore, the compactified system accurately approximates the original Gaussian LQR over any fixed finite horizon, in terms of trajectory agreement and expected values on bounded evaluation regions. In particular, Gaussian tail and moment bounds imply that the corresponding finite-horizon value functions are uniformly close on any fixed bounded evaluation region. Since the LQR value function is quadratic, this supports its use as a reference in our comparisons.
Revision. We will expand the existing remark in Appendix B to clarify the compactified interpretation and Gaussian-tail argument, document action clipping in Appendix C.2.