acceptodds
Under review as a conference paper at ICLR 2027

Exact-Consensus Distributed Q-learning with Finite-Time Guarantees

Abstract

We study distributed Q-learning for networked Markov decision problems, where agents share a common environment, observe only local rewards, and communicate with their neighbors to learn the team-optimal Q-function. Since the local rewards differ across agents, existing methods rely on diminishing step-sizes to reach consensus, which sacrifices responsiveness over time. To overcome this limitation, we propose Exact-Consensus Q-learning (ECQ), which uses three variables: a local Bellman-learning variable, an agreement variable, and an auxiliary dynamic-consensus variable. By accumulating past disagreement, this auxiliary variable removes the steady-state consensus bias caused by reward heterogeneity. Under this scheme, the mean dynamics of ECQ are shown to converge to an equilibrium that exactly coincides with the centralized team-optimal Q-function. Moreover, using an exact switching-system representation, joint-spectral-radius stability, and martingale-difference noise analysis, we derive finite-time bounds that decompose the total error into a geometrically decaying transient and an residual. We also prove that the consensus error of ECQ vanishes geometrically without any residual under deterministic reward heterogeneity. Experiments show that ECQ reaches machine-precision consensus under deterministic local rewards, exhibits steady-state errors consistent with our theoretical results, and adapts robustly to sudden reward shifts.

Primary area:
reinforcement learning
Keywords:
Distributed reinforcement learning, Networked multi-agent system, Consensus, Finite-time analysis, Switching system

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_m1UcOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

In this work, the authors propose a distributed Q-learning algorithm that converges to true equilibria under sufficiently small constant step sizes for networked MDPs using asynchronous updates. Finite-time error bounds are provided, along with toy experiments demonstrating the theoretical results.

Critical strengths

None that I can see.

Critical weaknesses

The paper reads like an itemized list concatenated together, with no coherence.

  • The only motivation provided for studying the present problem is that previous works have considered related problems under subsets of these assumptions, but not all of them simultaneously. No clear motivation or explanation is provided for why the current problem is of independent interest, other than the statement that “diminishing step sizes can fail to adapt to non-stationary environments.”

  • However, an algorithm with a constant step size cannot generally be expected to converge exactly unless additional structural assumptions, such as a minorization condition or comparable restrictions on the dynamics, are imposed. Thus, constant step sizes do not by themselves resolve the issue of adaptation to non-stationary environments if exact convergence is required.

  • In the present paper, Assumption 5.1 together with equation (16) effectively imposes a highly restrictive update schedule that is crucial for obtaining the claimed convergence. I do not believe that these conditions are satisfied in general, and the paper does not provide sufficient justification as to why they should hold in the settings of interest.

  • The only explanation provided in the main body regarding the results consists largely of restating the mathematical content of the lemmas and theorems in words. There is little discussion of the underlying insight, no meaningful comparison with the previous literature, and no explanation of what is technically or conceptually new. Given that the paper is primarily a theoretical contribution, the main body should clearly explain what the results achieve, how they are obtained at a high level, how they differ from or improve upon existing results, and why these contributions are significant. At present, this context and interpretation are largely missing.

  • It is not explained how “distribution sampling” is actually used. The concept is defined once and then effectively forgotten.

  • The appendix is written in a needlessly cumbersome way and does not communicate the proofs efficiently. Writing out every algebraic or intermediate step explicitly does not, by itself, make a proof clearer or easier to follow. In fact, the level of detail often obscures the main ideas and makes it difficult to identify the key arguments.

Minor comments:

  • Line 142 - “Let dd denote a state-action sampling ...”
  • Line 157 – “one-hot”? Is there a typo?
  • Disagreement subspace is not defined in the main body.
  • I presume “heterogeneous local rewards” refers to asynchronous learning.
  • The way Definition 4.1 is written, it does not make much sense. It does not appear that it is verbatim from Liberzon (2003) as claimed.
  • I’m not sure what “Bellman maximization”, “local Bellman-learning variable”, “agreement-variable” are supposed to mean.
Questions for authors

Is there a general class of nontrivial, “useful” models that satisfy Assumption 5.1?

9 comments
AuthorsOpenReview ↗

Response to Reviewer m1Uc (1/5)

We thank the reviewer for the detailed and candid feedback. Several of the main concerns arise from places where our presentation was unclear, including two cases where our wording made the assumptions appear more restrictive than they are. We clarify each point below and describe the concrete revisions.

  1. W1 / W2 (Independent motivation and what "exact" means under a constant step-size)

(short answer: "exact" refers to consensus among agents, not to convergence of QkQ_k to Q∗Q^{\ast}).

The problem is of independent interest for three reasons.

  • Exact consensus is what yields a single, well-defined team policy: when the agents' Q-tables agree exactly, their greedy policies coincide by definition.

  • A constant step-size can follow changes in the environment but leaves an O(α)O(\alpha) consensus bias [1], while a diminishing step-size (QD-learning; [2]) removes the bias but loses the ability to adapt as the step-size vanishes. Obtaining both requires breaking this trade-off; it is not a union of existing assumptions.

  • Removing this bias under a constant step-size has been studied in distributed optimization [3, 4] and in reinforcement learning for policy evaluation [5], in both cases relying on smooth or linear local updates. To our knowledge, whether the consensus bias can be provably removed when the local update contains the Bellman maximization of Q-learning was open; we show that it can under deterministic reward heterogeneity and shared transitions.

Under a constant step-size, we agree that QkQ_k does not converge exactly to Q∗Q^{\ast}, and we do not claim it does: Theorem 5.1 bounds the total error by a geometrically decaying term plus an O(α)O(\sqrt{\alpha}) residual. The exact statement concerns only the consensus error (Corollary 5.1). Under deterministic reward heterogeneity and shared transitions, the noise driving the disagreement dynamics has no additive component (Lemma A.11), so the disagreement converges to zero geometrically in mean square. No minorization-type condition is required because our guarantee concerns the vanishing of the disagreement among agents, rather than the stochastic estimation error. Finally, adaptation to a changing environment does not rely on exact convergence of QkQ_k; it relies on the step-size not vanishing.

[1] Han-Dong Lim, Donghwan Lee, A Finite-Time Analysis of Distributed Q-Learning, RL Journal, 2025.

[2] Kar, Soummya, José MF Moura, and H. Vincent Poor. "${{\cal Q}{\cal D}} $-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through ${\rm Consensus}+{\rm Innovations} $." IEEE Transactions on Signal Processing 61.7 (2013): 1848-1862.

[3] Shi, Wei, et al. "Extra: An exact first-order algorithm for decentralized consensus optimization." SIAM Journal on Optimization 25.2 (2015): 944-966.

[4] Nedic, Angelia, Alex Olshevsky, and Wei Shi. "Achieving geometric convergence for distributed optimization over time-varying graphs." SIAM Journal on Optimization 27.4 (2017): 2597-2633.

[5] Wang, Gang, et al. "Decentralized TD tracking with linear function approximation and its finite-time analysis." Advances in neural information processing systems 33 (2020): 13762-13772.

AuthorsOpenReview ↗

Response to Reviewer m1Uc (2/5)

  1. W3 / W5 / Q1 (Role of Assumption 5.1 and (16); use of the sampling distribution)

We apologize for the unclear presentation and clarify both points below.

  • Assumption 5.1 and (16) (short answer: neither is a restriction; every networked MDP satisfies Assumption 5.1).

Assumption 5.1 states that the problem data (P,Ri,γ,D,L,κ)(P, R^i, \gamma, D, L, \kappa) are held fixed across different choices of the constant step-size α\alpha. It is a bookkeeping convention that lets us write Aμ,⊥(α)=I+αHμ,⊥A_{\boldsymbol{\mu},\perp}(\alpha) = I + \alpha H_{\boldsymbol{\mu},\perp} with Hμ,⊥H_{\boldsymbol{\mu},\perp} independent of α\alpha, as in (19). This structure allows interpolation across step-sizes: Aμ,⊥(α)=(1−ααˉ)I+ααˉAμ,⊥(αˉ)A_{\boldsymbol{\mu},\perp}(\alpha) = \left(1 - \frac{\alpha}{\bar{\alpha}}\right) I + \frac{\alpha}{\bar{\alpha}} A_{\boldsymbol{\mu},\perp}(\bar{\alpha}). It restricts neither the model nor the algorithm, since every networked MDP satisfies it. In the revision, we have removed Assumption 5.1 and now state this as a standing convention in the text. (16) is likewise not a constraint on the algorithm. Proposition 4.1 shows that the ZZ-equilibrium is not unique. (16) merely selects the equilibrium with the same network sum as Z0Z_0 as the reference point for the error coordinates (14). No condition on the initialization, the update rule, or the update schedule is imposed. We also removed the initial conditions and Z∞Z_\infty from the former Assumption 5.1: The initialization is an arbitrary input, and Z∞Z_\infty is defined by (16), so neither depends on α\alpha.

  • Sampling distribution (short answer: dd is used throughout the analysis, through DD, dmin⁡d_{\min}, and the i.i.d. noise structure).

The sampling distribution dd defined in Section 3 is used throughout: it defines DD in (2), which appears in every mean-dynamics matrix (e.g., (10)–(12)); its minimum dmin⁡d_{\min} sets the contraction rate of the Bellman-estimation subsystem (Lemma A.3) and enters the threshold κ∗\kappa^{\ast} (Lemma A.5); and i.i.d. sampling from dd is what makes the noise a martingale difference in Lemma 5.4.

AuthorsOpenReview ↗

Response to Reviewer m1Uc (3/5)

  1. W4 (Interpretation of the results and comparison with prior work in the main body)

(short answer: we replaced the verbal restatements with a discussion of what the results achieve, how they are obtained, and how they compare with prior work).

We made three changes.

  • What the results achieve and why (added in Section 5.2): Theorem 5.1 bounds the total error by geometrically decaying transients plus an O(α)O(\sqrt{\alpha}) residual, while Corollary 5.1 shows that the consensus error alone vanishes. The difference comes from the sampling noise, whose second moment splits into a constant part and a part proportional to the error (Lemma 5.4). The constant part yields the O(α)O(\sqrt{\alpha}) residual; in the disagreement coordinates, it is absent under deterministic reward heterogeneity and shared transitions, which is why consensus is exact.

  • Comparison with [1] (moved from Appendix A.11 to Section 5.2): Both analyses retain an O(α)O(\sqrt{\alpha}) residual for the total error. The difference lies in the consensus error: their bound retains an O(α)O(\alpha) term, while ours vanishes. Their algorithm has no counterpart to the tracking variable ZZ, which in our algorithm accumulates the disagreement and thereby removes the consensus bias. We state explicitly that this compares guarantees, not true residuals.

  • What is technically new (added in Section 4.2 and 5): From the perspective of convergence analysis, related methods relied on smooth or linear local updates, as stated in Section 2. However, in Q-learning, the Bellman maximization makes the mean dynamics piecewise linear and non-smooth. We handle this with a switching-system representation and a JSR argument, and we added a short explanation of why these tools are needed.

[1] Han-Dong Lim, Donghwan Lee, A Finite-Time Analysis of Distributed Q-Learning, RL Journal, 2025.

Reviewer_Ym8MOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the consensus error in networked MDP problem, where decentralized agents learn the team optimal policy together while having their own rewards/goals. They proposed EXACT-CONSENSUS Q-LEARNING(ECQ) to eliminate the consensus bias. Each agent maintains 3 variables, including WiW^i for local learning, QiQ^i for network agreement, and ZiZ^i for accumulated disagreement. They provide finite-time convergence guarantees on the total error and show the consensus error can be eliminated with constant stepsizes under deterministic reward heterogeneity.

Critical strengths

This paper is well-written and the storyline is clear.

Experiments show that ECQ does eliminate the consensus error under deterministic local rewards and aligns with the theory. And as far as I know, the reward function has only (s,a) as inputs and is deterministic in a lot of literature, so the deterministic reward heterogeneity holds automatically. As for the technical depth and correctness, they combine switching-system formulation and joint-spectral-radius analysis. I did not check all the details but the overall structure and the theorem statement make sense to me.

Critical weaknesses
  1. Proposition 5.1 says κ\kappa should be larger than some κ∗\kappa^*, however, κ∗\kappa^* is unknown. Then how do we choose κ\kappa when running the algorithm? In the experiments, κ\kappa is chosen to be 1, and I wonder why this is a reasonable choice. The ablation study on κ\kappa shows for a given α\alpha, when κ\kappa is large, the algorithm may diverge. I wonder if the relationship between κ\kappa and α\alpha can be explicitly given.

  2. The paper does not give an explicit sample complexity bound, therefore it is difficult to compare with the baseline work [1] mentioned repeatedly in the paper. I guess it is because some constants are only provided with existence proofs but no deeper characterization. Could the authors provide a comparison with [1] in the sense of convergence rate/ sample complexity bound?

  3. The analysis is limited to iid samples. What if the samples are from Markovian trajectories, which is more common in reality? For example, [1] provides both Markovian and iid cases.

[1] Han-Dong Lim, Donghwan Lee, A Finite-Time Analysis of Distributed Q-Learning, RL Journal, 2025

Questions for authors

see Weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer Ym8M (1/3)

We thank the reviewer for the positive assessment and for the three precise questions.

  1. W1 (Choosing κ\kappa without knowing κ∗\kappa^{\ast} and the explicit relation between κ\kappa and α\alpha)
  • κ∗\kappa^{\ast} (short answer: explicit but conservative).

In the proof of Lemma A.5, κ∗\kappa^{\ast} is defined as κ∗=b22+b12b21/(dmin⁡(1−γ))λm\kappa^{\ast} = \frac{b_{22} + b_{12}b_{21}/\left(d_{\min}(1-\gamma)\right)}{\lambda_m}, with λm\lambda_m and b12,b21,b22b_{12}, b_{21}, b_{22} defined in (69) and (70). Two of these constants, b21b_{21} and b22b_{22}, cannot be evaluated exactly, so we bound them from above; this gives κ∗≤6.3×104\kappa^{\ast} \le 6.3\times10^4 for Garnet and 9.5×1049.5\times10^4 for Gridworld (Appendix A.13), whereas ECQ already converges at κ=1\kappa=1. The gap is structural rather than computational: already in its definition, κ∗\kappa^{\ast} combines several worst-case constants as if they were attained at the same policy, which does not happen during learning. This quantifies the conservatism noted in Appendix A.13.

  • Relation between κ\kappa and α\alpha and the choice of κ=1\kappa=1 (short answer: an explicit relation holds for each block in isolation and matches the experiments).

With the other block held fixed, the WW-update and the (Q,Z)(Q,Z)-updates each reduce to repeated multiplication by a matrix built from LL alone, so an eigenvalue computation gives, for each block in isolation, α<min⁡{21+λN(L), c(L)κ},\alpha<\min\left\lbrace\frac{2}{1+\lambda_N(L)},\ \frac{c(L)}{\kappa}\right\rbrace, where λN(L)\lambda_N(L) is the largest eigenvalue of LL; for ECQ, c(L)c(L) is the smallest value of −2Re⁡λ/∣λ∣2-2\operatorname{Re}\lambda/|\lambda|^2 over the nonzero eigenvalues of a matrix built from LL, and for R-ECQ, c(L)=2/λN(L)c(L)=2/\lambda_N(L). We add these conditions to Appendix A.14 as Lemma A.24 and Corollary A.5, together with a new Figure 16 sweeping (κ,α)(\kappa,\alpha). The observed transition follows the predicted boundaries, which also explain the κ\kappa-sweep in the current Figure 13(b); we remove it as redundant. Together with the bound κ∗≤6.3×104\kappa^{\ast} \le 6.3\times10^4 from the first bullet, this further quantifies how conservative κ∗\kappa^{\ast} is: the algorithm is already stable at κ=0.25\kappa=0.25, the smallest value tested. We therefore recommend taking a moderate constant κ\kappa (we use 11) and then α\alpha below this bound; (κ,α)=(1,0.05)(\kappa,\alpha)=(1,0.05) satisfies it. Since each condition holds the other block fixed, it does not certify the coupled iteration, and Figure 14 is the empirical check.

AuthorsOpenReview ↗

Response to Reviewer Ym8M (2/3)

  1. W2 (Explicit sample complexity and comparison with [1])
  • Sample complexity (short answer: O~(ϵ−2)\tilde{O}(\epsilon^{-2}) for the total error and O(log⁡(1/ϵ))O(\log(1/\epsilon)) for the consensus error).

The right-hand side of (24) in Theorem 5.1 has three terms. Bounding each by ϵ/3\epsilon/3, as in [1], the third term forces α∝ϵ2\alpha \propto \epsilon^2, and the first two then give k=O~(ϵ−2)k = \tilde{O}(\epsilon^{-2}). The same argument applies to R-ECQ with the corresponding constants (Corollary A.3). For the consensus error (Corollary 5.1 and Corollary A.4), there is no residual term, so α\alpha need not shrink with ϵ\epsilon, and the same procedure gives k=O(log⁡(1/ϵ))k = O(\log(1/\epsilon)) for any admissible step-size.

  • Comparison with [1] (short answer: the same ϵ\epsilon-order for the total error; the difference is in the consensus guarantee).

For the total error, [1] gives O~(ϵ−2)\tilde{O}(\epsilon^{-2}), matching ours. For the consensus error, they do not state a complexity, but it follows from their bound that O(log⁡(1/ϵ))O(\log(1/\epsilon)) iterations suffice once the step-size is taken proportional to ϵ\epsilon. Ours is the same, and without tying the step-size to ϵ\epsilon: their bound retains a residual proportional to α\alpha, so a smaller target accuracy forces a smaller step-size, whereas ours decays geometrically to zero at any admissible α\alpha. We note that some constants in our bound are not explicit, so the comparison is at the level of the order in ϵ\epsilon, not at the constant level; a fully explicit version is left to future work.

[1] Han-Dong Lim, Donghwan Lee, A Finite-Time Analysis of Distributed Q-Learning, RL Journal, 2025.

AuthorsOpenReview ↗

Response to Reviewer Ym8M (3/3)

  1. W3 (Extension from i.i.d. sampling to Markovian trajectories)

(short answer: exact consensus carries over unchanged, and the remaining steps have a standard Markovian treatment; we add an experiment confirming this).

i.i.d. sampling is used in two places: (a) the equality of the conditional mean of the update and the D\mathbf D-weighted mean dynamics in Appendix A.1, and (b) the martingale-difference property E[ηk+1∣Fk]=0E[\eta_{k+1}|\mathcal F_k]=0 in Lemma 5.4. Under Markovian sampling with a fixed behavior policy, neither holds exactly at each step, because the next sample depends on the current state. Both hold only in the long run, with dd the stationary state-action distribution, and the remaining gap can be handled by the standard mixing-time decomposition [2]. We add a Markovian-sampling experiment (Figure 15) to Appendix A.13. It shows that the exact-consensus mechanism does not rely on i.i.d. sampling, in line with Lemma A.11: the noise acting on the disagreement is proportional to the disagreement itself, so no consensus floor arises under any sampling scheme, and the scheme changes only how fast the disagreement decays. Unlike the consensus error, whose noise vanishes with the disagreement, the total error carries an additive noise term, so its floor can grow with the mixing time under Markovian sampling [2]; the fixed behavior chains in this experiment mix within few steps, so this effect is small and the observed floors match. A full analysis under Markovian sampling is left to future work.

[2] Srikant, Rayadurgam, and Lei Ying. "Finite-time error bounds for linear stochastic approximation andtd learning." Conference on learning theory. PMLR, 2019.

I thank the authors for the detailed rebuttal, and I will maintain my positive score.

Reviewer_gAb3OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Exact-Consensus Q-learning (ECQ) for networked Markov decision problems to eliminate the steady-state consensus bias caused by heterogeneous local rewards while maintaining a constant step-size.

Algorithm Design: Decouples local learning from network agreement using three variables (a local Bellman-learning variable, an agreement variable, and an auxiliary dynamic-consensus variable), proving that the equilibrium of its mean dynamics coincides with the centralized team-optimal Q-function.

Theoretical Analysis: Establishes finite-time error bounds via an exact switching system representation, Joint Spectral Radius (JSR) stability, and martingale-difference noise analysis. The total error bound consists of a geometrically decaying transient term and an O(α)O(\sqrt{\alpha}) steady-state residual, while the consensus error vanishes geometrically without any residual under deterministic reward heterogeneity.

Empirical Validation: Experiments on gridworld and Garnet MDP environments demonstrate that ECQ achieves machine-precision consensus and adapts robustly to sudden reward shifts.

Critical strengths
  1. Clever Coupling of Non-smooth Bellman Operators with Switching Linear Systems: The authors demonstrate strong mathematical proficiency by successfully transforming the error dynamics of distributed Q-learning, which involves a non-smooth max operator, into piecewise-defined switching linear systems. They precisely leverage the Joint Spectral Radius (JSR) and Dini directional derivatives to characterize the convergence trajectories. This theoretical framework—bridging consensus mechanisms from distributed optimization with reinforcement learning operators—provides robust technical backing.

  2. Breaking the Steady-State Bias Bottleneck under Constant Step-Sizes: By introducing auxiliary dynamic consensus states (ZZ -variables), the framework explicitly decouples local Bellman learning from network averaging. It rigorously proves that "residual-free" geometric convergence can be achieved under deterministic heterogeneous rewards, successfully pushing past the long-standing theoretical ceiling where traditional distributed Q-learning fails to eliminate consensus bias under constant step-sizes.

Critical weaknesses
  1. The theoretical convergence guarantees require a sufficiently large mixing gain and a sufficiently small step size. However, the experiments employ fixed parameters, such as κ=1\kappa =1 and α=0.05\alpha =0.05, without establishing whether these choices satisfy the sufficient stability conditions. Although the authors acknowledge the conservatism of the theoretical thresholds, the lack of computable parameter-selection guidelines limits their practical applicability. Furthermore, the sensitivity to κ\kappa observed in Figure 13(b) at a fixed step size indicates that the admissible (κ,α)(\kappa, \alpha) region is not sufficiently characterized.

  2. Corollary 5.1 establishes residual-free consensus convergence under deterministic inter-agent reward differences. Bounded common reward noise is compatible with this structural condition, whereas the unbounded Gaussian common noise considered in the experiments lies outside the stated bounded-reward assumptions. Independent reward noise violates the deterministic-difference condition, and Figure 13(a) shows a non-zero consensus error floor in this setting. Although the paper provides finite-time error bounds under general sampling noise, the consensus behavior under stochastic inter-agent reward differences remains insufficiently characterized, particularly regarding its dependence on noise variance and correlation structure.

  3. The finite-time error bounds involve several constants, including cc, KK, σ0\sigma _0, and σ1\sigma _1, whose dependence on the underlying problem characteristics is not made sufficiently explicit. In particular, the analysis does not clearly quantify how these constants scale with the state-action space size, the number of agents, or the spectral properties of the graph Laplacian (L). Although the stability analysis uses properties of the positive-definite matrix ULU⊤ULU^{\top}, their quantitative implications for the finite-time convergence bounds remain unclear. This implicit dependence makes it difficult to assess how the theoretical guarantees change with problem size and network connectivity.

  4. The convergence analysis is restricted to tabular Q-learning over fixed connected communication graphs. While this is a reasonable theoretical setting, the applicability of the switching-system and JSR framework to more general scenarios remains unclear. In particular, the paper provides limited discussion of which analytical steps fundamentally rely on tabular representations and fixed network structures. A complete theoretical extension is not necessary, but a clearer discussion of the main mathematical obstacles associated with function approximation and time-varying communication graphs would strengthen the presentation.

  5. The theoretical analysis assumes that state-action pairs are independently sampled from a fixed distribution with full support and that all agents share the same sampled transition while observing their respective local rewards. Although this assumption facilitates the finite-time analysis, it differs from practical online distributed reinforcement learning settings, where samples may be temporally correlated and generated by evolving behavior policies. The paper does not sufficiently discuss which components of the convergence analysis rely on independent sampling and shared transitions, or how relaxing these assumptions might affect the consensus mechanism and theoretical guarantees.

Questions for authors
  1. Could the authors report estimates or lower bounds of κ∗\kappa^* and α0\alpha_0 for the tested environments, even if conservative? What practical procedure would they recommend for choosing without trial-and-error, and how does the empirical degradation in Figure 13(b) relate to the theoretically admissible region?

  2. Figure 13(a) shows a non-zero consensus floor under independent reward noise. Could the authors provide a quantitative or empirical characterization of how this floor scales with noise variance, inter-agent noise correlation, and step size? Even a partial bound or scaling law would clarify the scope of the exact-consensus mechanism.

  3. Could the authors provide order-wise or partial characterizations of how c, K, σ0\sigma _0, and σ0\sigma _0 depend on ∥S∥∥A∥\|\mathcal{S}\|\|\mathcal{A}\|, N, and the graph spectrum? It would also help to isolate network-dependent factors, e.g., those involving L or ULU⊤ULU^{\top}, so that the bounds are easier to interpret across graph topologies and problem sizes.

  4. The current analysis focuses on tabular Q-learning over fixed connected communication graphs. Which steps of the switching-system representation and JSR-based stability analysis rely critically on these assumptions? Could the authors briefly discuss the main mathematical challenges associated with extending ECQ to linear function approximation or time-varying communication graphs? A complete theoretical extension is not required, but clarification of the principal technical obstacles would help establish the scope of the proposed framework.

  5. The theoretical analysis assumes independently sampled state-action pairs from a fixed distribution and a shared transition across all agents. Which steps of the finite-time convergence proof rely critically on these sampling assumptions? Could the authors discuss how temporally correlated samples generated by Markov trajectories or evolving behavior policies might affect the convergence analysis? Additionally, would relaxing the shared-transition assumption introduce new difficulties for the consensus mechanism? A discussion of these limitations would help clarify the applicability of ECQ to more general online distributed reinforcement learning settings.

7 comments
AuthorsOpenReview ↗

Response to Reviewer gAb3 (1/5)

We sincerely thank the reviewer for an exceptionally careful and constructive review. The weaknesses and questions are paired (W1/Q1, …\dots, W5/Q5), so we answer them jointly.

  1. W1 / Q1 (Values of κ∗\kappa^{\ast} and α0\alpha_0, and the practical choice of (κ,α)(\kappa,\alpha))
  • κ∗\kappa^{\ast} (short answer: explicit but conservative).

In the proof of Lemma A.5, κ∗\kappa^{\ast} is defined as κ∗=b22+b12b21/(dmin⁡(1−γ))λm\kappa^{\ast} = \frac{b_{22} + b_{12}b_{21}/\left(d_{\min}(1-\gamma)\right)}{\lambda_m}, with λm\lambda_m and b12,b21,b22b_{12}, b_{21}, b_{22} defined in (69) and (70). b12b_{12} and λm\lambda_m can be computed exactly. For b21b_{21} and b22b_{22}, however, WmW_m sums over all coordinates rather than selecting the largest, so the maximization over π\boldsymbol\pi requires enumerating all ∣A∣∣S∣N|\mathcal A|^{|\mathcal S|N} joint policies; b21b_{21} also maximizes a quadratic over the cube {∥u∥∞≤1}\lbrace\Vert u\Vert_\infty \le 1\rbrace, which has no closed form. For these two, we instead compute upper bounds. Both relax the maximization over π\boldsymbol\pi; b21b_{21} additionally relaxes the input constraint. This gives κ∗≤6.3×104\kappa^{\ast} \le 6.3\times10^4 for Garnet and 9.5×1049.5\times10^4 for Gridworld (Appendix A.13), whereas ECQ already converges at κ=1\kappa=1. The gap is structural rather than computational: already in its definition, κ∗\kappa^{\ast} combines several worst-case constants as if they were attained at the same policy, which does not happen during learning. This quantifies the conservatism noted in Appendix A.13. We add Figure 16 in Appendix A.14 for the empirical analysis; see the third bullet of our response to W1 / Q1.

  • α0\alpha_0 (short answer: no numerical value is available).

In Proposition 5.2, α0\alpha_0 is defined in (22) as α0:=min⁡{αˉ, 1/(2C1σ12)}\alpha_0 := \min\lbrace\bar\alpha,\ 1/(2C_1\sigma_1^2)\rbrace. Unlike κ∗\kappa^{\ast}, it admits neither a numerical estimate nor a lower bound. σ1\sigma_1 is explicit in the proof of Lemma 5.4, but C1C_1 depends on KK and cc, and αˉ\bar\alpha is only asserted to exist (Proposition 5.1); both trace back to the JSR ρ(Aαˉ,⊥)\rho(\mathcal{A}_{\bar{\alpha},\perp}), which the analysis certifies to be below 11 without computing it. Computing it is out of reach: the family has one matrix per deterministic joint policy, hence ∣A∣∣S∣N|\mathcal A|^{|\mathcal S|N} of them, and approximating the JSR is NP-hard even for two matrices [1]. What α0\alpha_0 does provide is a sufficient threshold: (23) holds for every α≤α0\alpha \le \alpha_0, and nothing is claimed for larger α\alpha.

  • Admissible (κ,α)(\kappa,\alpha) (short answer: isolating the two updates gives computable boundaries that match the experiments).

Our sufficient conditions, κ>κ∗\kappa>\kappa^{\ast} and α≤α0\alpha\le\alpha_0, cannot certify any pair used in practice. With the other block held fixed, however, the WW-update and the (Q,Z)(Q,Z)-updates each reduce to repeated multiplication by a matrix built from LL alone, so an eigenvalue computation gives, for each block in isolation, α<min⁡{21+λN(L), c(L)κ},\alpha<\min\left\lbrace\frac{2}{1+\lambda_N(L)},\ \frac{c(L)}{\kappa}\right\rbrace, where λN(L)\lambda_N(L) is the largest eigenvalue of LL; for ECQ, c(L)c(L) is the smallest value of −2Re⁡λ/∣λ∣2-2\operatorname{Re}\lambda/|\lambda|^2 over the nonzero eigenvalues of a matrix built from LL, and for R-ECQ, c(L)=2/λN(L)c(L)=2/\lambda_N(L). We add these conditions to Appendix A.14 as Lemma A.24 and Corollary A.5, together with a new Figure 16 sweeping (κ,α)(\kappa,\alpha). The observed transition follows the predicted boundaries, which also explain the κ\kappa-sweep in the current Figure 13(b); we remove it as redundant. Together with the bound κ∗≤6.3×104\kappa^{\ast} \le 6.3\times10^4 from the first bullet, this further quantifies how conservative κ∗\kappa^{\ast} is: the algorithm is already stable at κ=0.25\kappa=0.25, the smallest value tested. We therefore recommend taking a moderate constant κ\kappa (we use 11) and then α\alpha below this bound; (κ,α)=(1,0.05)(\kappa,\alpha)=(1,0.05) satisfies it. Since each condition holds the other block fixed, it does not certify the coupled iteration, and Figure 16 is the empirical check.

[1] Tsitsiklis, John N., and Vincent D. Blondel. "The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate." Mathematics of Control, Signals and Systems 10.1 (1997): 31-40.

AuthorsOpenReview ↗

Response to Reviewer gAb3 (2/5)

  1. W2 / Q2 (Scope of the bounded-reward assumption and the scaling of the consensus floor)
  • Unbounded Gaussian common noise and the bounded-reward assumption (short answer: the proofs can be revised with a bounded second moment of the reward, so we relax the assumption accordingly, and the Gaussian experiments then lie inside it).

We agree that the Gaussian-noise experiments lie outside the reward model as currently stated, in which rir^i is a bounded function of (s,a,s′)(s,a,s'). Since the proofs used Rmax⁡R_{\max} only to bound the reward term inside the conditional second moment of the update, we relax the model so that the observed reward rk+1ir^i_{k+1} has bounded mean and a uniformly bounded second moment (Definition 3.1). In the proofs of Lemma 5.4 and Lemma A.19, we split the reward term from the rest with (a+b)2≤2a2+2b2(a+b)^2 \le 2a^2+2b^2 and take the conditional expectation, which replaces Rmax⁡R_{\max} by that bounded second moment in σ0\sigma_0. The Gaussian common noise in the current Figure 13(a) then lies inside the assumptions.

  • The scaling of the consensus floor (short answer: the floor is linear in σr\sigma_{\rm r}, of order α\sqrt{\alpha}, and of order 1−ρcorr\sqrt{1-\rho_{\rm corr}}; we add both the bound and an experiment confirming it).

To characterize the scaling, we add the notion of stochastic reward heterogeneity, Lemma A.12 and Corollary A.1 in Appendix A.11, and Remark A.1 in Appendix A.12. Corollary A.1 gives a consensus floor that is linear in the per-agent noise standard deviation σr\sigma_{\rm r}, of order α\sqrt{\alpha} in the step-size, and of order 1−ρcorr\sqrt{1-\rho_{\rm corr}} in the inter-agent noise correlation ρcorr\rho_{\rm corr}. We also add an experiment (Figure 14) to Appendix A.13 that sweeps each of the three quantities in turn. The fitted slopes match the prediction in 1−ρcorr1-\rho_{\rm corr} (0.500.50) and in σr\sigma_{\rm r} (1.001.00); in α\alpha the fitted slope over the full range is slightly larger (0.530.53 and 0.550.55), as the bound is derived under a step-size restriction, and restricting the fit to α≤0.0125\alpha\le0.0125 recovers 0.500.50 and 0.510.51. ECQ and R-ECQ follow the same scaling law. This also explains the current Figure 13(a), where we had only observed that the consensus floor grows with the noise level under independent reward noise while common noise stays at machine precision. Independent noise is the case ρcorr=0\rho_{\rm corr}=0, so the floor is linear in σr\sigma_{\rm r}; common noise is ρcorr=1\rho_{\rm corr}=1, where the floor vanishes and exact consensus is recovered, which Figure 14 confirms at machine precision.

AuthorsOpenReview ↗

Response to Reviewer gAb3 (3/5)

  1. W3 / Q3 (Dependence of theoretical constants on problem size and graph topology)
  • cc (short answer: c=O(1/(∣S∣∣A∣))c = O(1/(|\mathcal{S}||\mathcal{A}|)); no sharper NN nor graph dependence is available).

The proof of Lemma 5.2 sets c=(1−βˉ)/αˉc = (1-\bar\beta)/\bar\alpha with βˉ\bar\beta chosen in (ρ(Aαˉ,⊥),1)(\rho(\mathcal A_{\bar\alpha,\perp}), 1), so cc carries no information beyond the JSR itself and is not available in closed form. Still, each member of Aαˉ,⊥\mathcal A_{\bar\alpha,\perp} has the affine form Aμ,⊥(αˉ)=I+αˉHμ,⊥A_{\boldsymbol\mu,\perp}(\bar\alpha) = I + \bar\alpha H_{\boldsymbol\mu,\perp} in (19), which localizes the dependence: the identity alone would give ρ=1\rho = 1, so the entire gap 1−ρ1-\rho is produced by αˉHμ,⊥\bar\alpha H_{\boldsymbol\mu,\perp}. Every nonzero block of Hμ,⊥H_{\boldsymbol\mu,\perp} carries a factor DD, so the gap scales with the visitation probabilities, and the slowest coordinate is the one visited least. Since dd is a distribution over ∣S∣∣A∣|\mathcal S||\mathcal A| pairs, dmin⁡≤1/(∣S∣∣A∣)d_{\min} \le 1/(|\mathcal S||\mathcal A|), so that c=O(dmin⁡)=O(1/(∣S∣∣A∣)).c = O(d_{\min}) = O(1/(|\mathcal S||\mathcal A|)). Although the graph enters Hμ,⊥H_{\boldsymbol\mu,\perp} only through S=L⊗D\mathbf S = L \otimes D, a sharper dependence on NN or on the Laplacian spectrum is not available here: the mode switches at every iteration, and the per-agent policy blocks in Πμ\Pi^{\boldsymbol\mu} do not commute with L⊗IL \otimes I, so the eigenvalues λi(L)\lambda_i(L) do not separate out.

  • KK (short answer: no order-wise characterization is available).

KK is the constant in the product bound ∥Mℓ−1⋯M0∥2≤K(1−cα)ℓ\Vert M_{\ell-1}\cdots M_0\Vert_2 \le K(1-c\alpha)^{\ell} of Lemma 5.2, so it bounds how much the products can grow before they begin to decay. Such growth depends on the entries of these matrices rather than on their size, so we cannot express KK in terms of ∣S∣∣A∣|\mathcal S||\mathcal A|, NN or the graph spectrum.

  • σ0,σ1\sigma_0, \sigma_1 (short answer: both are independent of ∣S∣∣A∣|\mathcal S||\mathcal A| and of order NλN(L)2(1+κ2)N\lambda_N(L)^2(1+\kappa^2) up to problem constants).

From Lemma 5.4, σ02=2N(R22+2bW2+κ2bQ2+κ2bZ2)\sigma_0^2 = 2N(R_2^2 + 2b_W^2 + \kappa^2 b_Q^2 + \kappa^2 b_Z^2) and σ12=2N(2aW2+κ2aQ2+κ2aZ2)\sigma_1^2 = 2N(2a_W^2 + \kappa^2 a_Q^2 + \kappa^2 a_Z^2), with b∙=a∙K0b_\bullet = a_\bullet K_0, so that σ02=2NR22+K02σ12\sigma_0^2 = 2NR_2^2 + K_0^2\sigma_1^2. Both are independent of ∣S∣∣A∣|\mathcal S||\mathcal A|, since a single (s,a)(s,a) is sampled per iteration. The graph enters aW,aQ,aZa_W, a_Q, a_Z only through max⁡i∣Ni∣\max_i|\mathcal N_i|, in which they are linear; since max⁡i∣Ni∣≤λN(L)≤2max⁡i∣Ni∣\max_i|\mathcal N_i| \le \lambda_N(L) \le 2\max_i|\mathcal N_i| (by the Rayleigh quotient and Gershgorin's theorem, respectively), σ12=O(NλN(L)2(1+κ2)),σ02=O(N(R22+K02λN(L)2(1+κ2))).\sigma_1^2 = O\left(N\lambda_N(L)^2(1+\kappa^2)\right), \qquad \sigma_0^2 = O\left(N(R_2^2 + K_0^2\lambda_N(L)^2(1+\kappa^2))\right).

  • Network-dependent factors (short answer: only σ0,σ1\sigma_0,\sigma_1 admit an explicit topology dependence).

Among the constants of Theorem 5.1, the network enters as follows:

  • cc: network-dependent, through S=L⊗D\mathbf S = L \otimes D, but this does not yield a closed form, as in the first bullet of our response to W3 / Q3.

  • KK: network-dependent, but no characterization is available, as in the second bullet of our response to W3 / Q3.

  • σ0,σ1\sigma_0, \sigma_1: network-dependent through max⁡i∣Ni∣\max_i|\mathcal N_i| only, contributing a factor O(λN(L)2)O(\lambda_N(L)^2), as in the third bullet of our response to W3 / Q3.

  • LΠL_\Pi: independent of the network. By (19), the policy appears only in the block γDPΠμ\gamma \mathbf{D}\mathbf{P}\mathbf{\Pi^{\boldsymbol{\mu}}}, which contains no LL. Therefore, the mode-difference bound of Lemma 5.3 is unaffected by the topology.

  • C0,C1C_0, C_1: network-dependent. They are explicit functions of KK, cc, and LΠL_\Pi, so they inherit the characterizations above.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their time and constructive feedback. Below we summarize the revisions made to the manuscript. All revised text is marked in blue.

  • Section 1: introduced the term "heterogeneous local rewards".

  • Definition 3.1, Appendix A.1, and the proofs of Lemma 5.4 and Lemma A.19: relaxed the bounded-reward requirement.

  • Definition 4.1: clarified the definition of the switching system.

  • Section 4.3: defined the disagreement subspace as {1N}⊥⊗R∣S∣∣A∣\lbrace\mathbf{1}_N\rbrace^{\perp} \otimes \mathbb{R}^{|{\cal S}||{\cal A}|}.

  • Assumption 5.1: removed and restated as a standing convention in the text.

  • Sections 4.2, 5, and 5.2: made the contributions explicit. We added a discussion of what our main results achieve and why, moved the comparison with [1] from Appendix A.11 to Section 5.2, and explained what is technically new in our convergence analysis.

  • Appendices A.11, A.12, and A.13: characterized how the consensus floor scales. We introduced the notion of stochastic reward heterogeneity, together with Lemma A.12 and Corollary A.1 (Appendix A.11) and Remark A.1 (Appendix A.12), and added a supporting experiment (Figure 14, Appendix A.13).

  • Appendix A.13: added a Markovian-sampling experiment (Figure 15).

  • Appendix A.14: added Lemma A.24 and Corollary A.5, which give the predicted boundary conditions on (κ,α)(\kappa, \alpha), together with a supporting experiment (Figure 16). Figure 13(b) was removed as redundant.

  • Proofs of Proposition 4.1, Lemmas A.2-A.6, Lemma 5.2, Lemma 5.4, and Proposition 5.2: added a short proof sketch at the beginning of each proof so that the key argument is visible before the details.

[1] Han-Dong Lim, Donghwan Lee, A Finite-Time Analysis of Distributed Q-Learning, RL Journal, 2025.

  • Section 2 (Table 1): added a comparison table of convergence guarantees for consensus-based distributed Q-learning.

  • Sections 4.2 (Assumption 4.1): moved the sampling model from Section 3 to Section 4.2 and stated it as Assumption 4.1, together with a note that it is needed only for the analysis.

  • Section 4.3: defined "Bellman maximization" explicitly as maxa′Qki(sk′,a′)max_{a'} Q^i_k(s'_k, a').

  • Algorithms 1 and 2: made the observed transition (sk,ak,sk′)(s_k, a_k, s'_k) explicit, with a pointer to Assumption 4.1 noting that the algorithms use only the observed transitions and can be run on any sequence of them.

  • Section 5.1: moved the standing convention on the problem parameters (former Assumption 5.1) to the text preceding Proposition 5.1.

  • Appendix A.11: added a paragraph after Corollary A.1 clarifying when the bound is free of residual under agent-specific reward noise.

  • Appendix A.15: added a new subsection "Scope and limitations of the analysis".

  • Replaced the term "heterogeneous local rewards" by the explicit statement that agents receive different local rewards.

  • Removed the term "deterministic reward heterogeneity" and restated the condition as "when the randomness in the rewards is common to all agents".

  • Replaced the term "stochastic reward heterogeneity" by the explicit statement that the reward differences between agents are random.

  • Replaced several other descriptive phrases by explicit mathematical statements.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.