- 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 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
Response to Reviewer m1Uc (2/5)
- 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 are held fixed across different choices of the constant step-size . It is a bookkeeping convention that lets us write with independent of , as in (19). This structure allows interpolation across step-sizes: . 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 -equilibrium is not unique. (16) merely selects the equilibrium with the same network sum as 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 from the former Assumption 5.1: The initialization is an arbitrary input, and is defined by (16), so neither depends on .
- Sampling distribution (short answer: is used throughout the analysis, through , , and the i.i.d. noise structure).
The sampling distribution defined in Section 3 is used throughout: it defines in (2), which appears in every mean-dynamics matrix (e.g., (10)–(12)); its minimum sets the contraction rate of the Bellman-estimation subsystem (Lemma A.3) and enters the threshold (Lemma A.5); and i.i.d. sampling from is what makes the noise a martingale difference in Lemma 5.4.
Response to Reviewer m1Uc (3/5)
- 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 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 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 residual for the total error. The difference lies in the consensus error: their bound retains an term, while ours vanishes. Their algorithm has no counterpart to the tracking variable , 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.
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.
(short answer: "exact" refers to consensus among agents, not to convergence of Qk to Q∗).
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(α) 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 Qk does not converge exactly to Q∗, and we do not claim it does: Theorem 5.1 bounds the total error by a geometrically decaying term plus an O(α) 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 Qk; 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.