- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes a new theoretical framework for analyzing the convergence rate of Q-learning by using a Switching Linear System (SLS) representation of the Q-learning error under a constant learning rate. While the paper does not introduce the concept of viewing Q-learning as an SLS, previous approaches model the error as an SLS with an affine term and then construct a "pure" SLS as an upper bound as well as a non-switching lower bound on the dynamics. In contrast, this paper models the Q-learning error is directly as an SLS, without the upper- and lower-bounding auxiliary systems. This is achieved by constructing the switching family (the set of transition matrices of the Markov chains induced by the corresponding policies) from stochastic rather than deterministic policies, which enables the SLS to represent the Bellman error of Q-learning exactly. This allows the authors to characterize the convergence rate of Q-learning directly in terms of the Joint Spectral Radius (JSR) of the switching family. The authors highlight the fact that their work presents a new perspective and framework to analyze Q-learning and that they do not claim to improve upon all existing methods across all possible use-cases.
In their first sections the authors introduce the connection between Q-learning and SLSs. In highly condensed form: In a given MDP each action is associated with a transition matrix and hence a deterministic policy can be seen as the switching dynamics that select different dynamics from the switching families depending on the state and the Q-values of the current iteration. From this the Q-learning error can be expanded, by plugging in the Q-update rule as well as the Bellman identity of , to the form of an SLS with an affine part. The authors then show that by changing the representation using stochastic policies instead of the deterministic policies directly, the error can also be expressed as a "pure" SLS (without affine term). Since the transition matrices induced by the stochastic policies are all contained in the convex hull of the switching family induced by the deterministic policies and Lemma 7 shows that the JSR of the deterministic switching family, , is equal to , it suffices to use the JSR of the deterministic switching family when analyzing the new SLS representation. This is the foundation that allows the convergence rate characterization in terms of the JSR. They then establish that this JSR is smaller than one as they upper bound it with the row-sum rate. This last point is what is required for convergence under arbitrary switching sequences.
The paper then shows that the switching families arising from the structure of Q-learning make the JSR more tractable compared to the generally hard-to-compute JSR of arbitrary matrix families. That is, under their assumptions, the JSR of the switching family equals the maximum, over all deterministic policies, of the spectral radius of the transition matrix induced by that policy. However, this is still expensive as the entire set of deterministic policies has to be considered. Instead, the authors provide a linear programming approach that avoids the search through all the policies. The resulting constrained optimization problem depends on the vector of Q-values, the vector of state-values, the steady state-action distribution induced by the data-generating behavioral policy, and the matrix of state-action-state transition probabilities of the MDP. This linear program significantly reduces the cost of computing the JSR.
Based on all the foundations mentioned above the authors then provide finite-time error bounds for the setting where the update samples are obtained as i.i.d. samples based on the stationary state-action distribution induced by the data-generating policy and for the setting where the samples are generated from a single trajectory that follows the dynamics of the Markov chain induced by the data-generating policy. In both error bounds, the transient terms depend on the JSR, whereas the noise terms depend on the row-sum rate in the i.i.d. setting and on the row-sum rate and the mixing time in the Markov setting. The paper provides a numerical example of an i.i.d. asynchronous Q-learning problem across multiple constant learning rates. The results show that the error rate predicted by the theory closely matches the empirical error rate in the numerical example. Further, the plots show that, in the given setting, the row-sum rate understates the speed of convergence relative to the JSR approach, which also empirically validates the row-sum rate as an upper bound on JSR.
Critical strengths
S1. The paper is well written and enjoyable to read. Further, the main text uses clean notation that makes it easy to follow and makes it always clear which object a symbol refers to and in what context.
S2. The proof segments in the appendix are detailed in a way that explains what steps are being taken, what properties are being used, and where properties come from. That is, they spell out things other papers might leave implicit.
Critical weaknesses
W1. Reading the paper requires many forward references to results only found in the appendix and therefore benefits from having the appendix open on the side for ease of reading. This weakens the self-contentedness of the paper's main body as the appendix is close to being a "required read" instead of a purely "supporting appendix that contains the proofs if you want to read them". A long-form journal version might be a more suitable format for this work, but since this is an issue theoretic work has within the page limitations of a conference, I will not factor this into my score.
W2. The paper suffers from a confusing structure when the main body and the appendix are taken together. The structure of the appendix is difficult to follow. This is partly due to, and accompanied by, the following issues:
1. There are naming overlaps between Lemmas that share the same number: A Lemma 1 appears on page 3 and on page 18; a Lemma 3 appears on page 15 and on page 24; a Lemma 4 appears on page 5 and on pages 16 and 24.
2. Lemma 1 on page 18 equals Lemma 19 on page 38 and the proof is repeated.
3. Lemmas numbered 10 to 18 are missing.
4. Corollary 2 exists but Corollary 1 does not.
5. There are unnumbered Lemmas on pages 43 and 51.
6. The equation number counter resets on page 29. As a result all equations numbered 1 to 49 have shadowed versions after page 29. One example is that Equation (8) on page 30 links to Equation (8) on page 7 but there is also an Equation 8 on page 30 just a few lines above the reference.
This is the primary driver behind my current score.
Questions for authors
Q1. Regarding the JSR condition I was wondering how it relates to the contractions usually used in the Bellman convergence analysis. It acts as an asymptotically contracting on the space the switching sequence is applied to, whereas the Bellman operator contracts in single steps. What are the parallels and what are the differences between these two?
Q2. Related to question 1, since you provide this new framework to complement existing analysis methods, do you have any (preliminary or speculative) guidance on when to use this new tool?
Q3. The simulation in Figure 1 shows the i.i.d. setting. Could a similar experiment using the single-trajectory Markovian sample setting be included in the paper to show how well the theory can match a numerical example in that setting?
Little Details
- Lines 83-84: With also used for the eigenvalues in the same paragraph, I would suggest using a different symbol for the weights of the convex hull.
- Line 44: Maybe extend the "linear" to "linear and non-switching" or something along these lines; since SLS is also linear, this would make the distinction cleaner.
- Line 125: The introduction of the one-step reward misses a "finite".
6 comments
Thank you very much for your detailed response. However, the PDF that can currently be downloaded still seems to be the original submission. I could not find any blue-marked changes, the numbering issues are still present, and the new Appendix M (single-trajectory experiment) is not included. The revision history also currently shows "No revisions to display". Could you please check whether the revised version was uploaded successfully?
Thank you for bringing this to our attention, and we sincerely apologize for the confusion. It appears that the revised PDF was not successfully uploaded earlier due to an oversight on our part.
We have now re-uploaded the revised manuscript. Could you please check whether you can now access the updated PDF, including the blue-marked changes, the corrected numbering, and the new Appendix M on the single-trajectory experiment?
Thank you for your patience and understanding.
We sincerely thank you for your careful review, positive comments, and detailed suggestions. We have revised the manuscript accordingly; all changes are blue.
W1. Main-text presentation: We have moved the key error-representation lemma into Section 4 (Lemma 2), added a short proof, and explained there why stochastic-policy matrices can be reduced to deterministic-policy products without changing the JSR. The Introduction now gives a roadmap connecting these steps to the rate characterization and finite-time bounds. This makes the main argument easier to follow without repeatedly consulting the appendix.
W2. Appendix structure and numbering: We have replaced manual counter resets with automatic appendix numbering, using section prefixes such as A.1. This removes overlapping lemma and equation numbers and unintended gaps, and numbers the previously unnumbered lemmas. The repeated product-growth argument is now stated and proved once (Lemma A.5); later uses refer to it. We have also repaired and checked the cross-references in the recompiled PDF. Thank you for identifying these problems.
Q1. How does the JSR condition relate to Bellman contraction?: Bellman contraction gives a one-step bound, ∥F(Q)−F(Q′)∥∞≤γ∥Q−Q′∥∞. The joint spectral radius (JSR) describes the worst long-run rate of products of error-update matrices. A JSR below one implies exponential decay of the noise-free error under arbitrary switching.
The update scale matters. For our asynchronous update with step-size α and minimum sampling frequency dmin, the appropriate comparison is ρ(Mα)≤1−αdmin(1−γ)=ρrow<1, and the first inequality can be strict. We do not claim that this asynchronous family's JSR is below the unscaled γ.
A JSR smaller than γ can arise after removing the constant-vector error direction, as in deflated Q-value iteration. Standard synchronous Q-value iteration has full-space JSR γ, but its projected family can satisfy ρ(B)<γ. Thus JSR analysis can reveal faster decay in the remaining error components. We have clarified this distinction in Section 6 and Appendix N, including a simple example. The LP also gives a weighted maximum norm with a one-step bound, linking the JSR and contraction viewpoints.
Q2. When should this tool be used?: First, it offers researchers with a control-theory background a familiar route to understanding Q-learning: study the stability of changing linear error updates. This helps communicate learning-algorithm analysis to a broader research community.
The paper's other advantages are: (i) an exact error representation without upper and lower comparison systems; (ii) retention of transition structure and unequal update frequencies, allowing a sharper decay term than a conservative row-sum estimate; (iii) an interpretable rate equal to the slowest deterministic-policy mode; (iv) an LP characterization that avoids enumerating policies and provides a weighted-norm certificate; and (v) finite-time upper bounds for both independent samples and single-trajectory samples. The viewpoint also supports analysis and design of related algorithms, as the examples added to the Introduction illustrate.
For numerical rate certificates, the model and sampling frequencies should be known or reliably estimated. A useful comparison includes the full bound's constants and noise, not only its exponential rate. We have added this guidance in Section 6.
Q3. Can a single-trajectory experiment be included?: We have added this experiment in Appendix M, Figure 3 and Tables 1-2, with 32 seeds, two mixing speeds, and two step-sizes. We compare trajectory samples with independent samples having the same stationary frequencies. The plots show initial error decay followed by a residual. The full theoretical noise bounds remain conservative, which we state explicitly.
Little details: We have changed the convex weights to θ, specified that the lower comparison system is linear and non-switching, and stated that rewards are finite. Thank you for these helpful corrections.