acceptodds
Under review as a conference paper at ICLR 2027

Switching Theory for Q-Learning

Abstract

Q-learning is a fundamental algorithmic primitive in reinforcement learning. This paper develops a new framework for analyzing constant step-size tabular Q-learning from a switching linear system (SLS) viewpoint. In particular, we derive a stochastic SLS representation of the Q-learning error, and a finite-time error analysis through the joint spectral radius (JSR) of the corresponding SLS model, where the JSR is the exact worst-case exponential rate of the associated SLS. To the best of our knowledge, this is the first convergence rate analysis of standard Q-learning whose leading exponential rate is expressed through the JSR. The resulting rate is tied to the intrinsic worst-case exponential rate of the direct SLS representation and can be sharper than row-sum upper bounds when those bounds are conservative. We further prove that the JSR of Q-learning equals the largest spectral radius among the deterministic-policy modes and give an exact linear programming characterization that can be evaluated to any prescribed accuracy.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Q-learning, TD learning, convergence, control theory, switching system

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_XcNqOpenReview ↗
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 Qk+1−Q⋆Q_{k+1}-Q^{\star} can be expanded, by plugging in the Q-update rule as well as the Bellman identity of Q⋆Q^{\star}, 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 co(Mα)\text{co}(\mathcal{M}_{\alpha}) of the switching family induced by the deterministic policies and Lemma 7 shows that the JSR of the deterministic switching family, ρ(Mα)\rho(\mathcal{M}_{\alpha}), is equal to ρ(co(Mα))\rho(\text{co}(\mathcal{M}_{\alpha})), 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 <1<1 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

  1. Lines 83-84: With λ\lambda also used for the eigenvalues in the same paragraph, I would suggest using a different symbol for the weights of the convex hull.
  2. 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.
  3. Line 125: The introduction of the one-step reward misses a "finite".
6 comments

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′∥∞.\|F(Q)-F(Q')\|_\infty\le\gamma\|Q-Q'\|_\infty. 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 α\alpha and minimum sampling frequency dmin⁡d_{\min}, the appropriate comparison is ρ(Mα)≤1−αdmin⁡(1−γ)=ρrow<1,\rho(\mathcal M_\alpha)\le 1-\alpha d_{\min}(1-\gamma)=\rho_{\rm row}<1, and the first inequality can be strict. We do not claim that this asynchronous family's JSR is below the unscaled γ\gamma.

A JSR smaller than γ\gamma can arise after removing the constant-vector error direction, as in deflated Q-value iteration. Standard synchronous Q-value iteration has full-space JSR γ\gamma, but its projected family can satisfy ρ(B‾)<γ\rho(\overline{\mathcal B})<\gamma. 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 θ\theta, specified that the lower comparison system is linear and non-switching, and stated that rewards are finite. Thank you for these helpful corrections.

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.

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

The paper develops an exact switching linear system representation of constant-step-size tabular Q-learning errors and derives finite-time bounds with JSR-governed transient terms. It also characterizes the JSR through deterministic-policy spectral radii and LP feasibility, extends the analysis to Markovian observations, and provides a small numerical illustration.

Critical strengths

I am not an expert in tabular Q-learning, but I learned something useful from the JSR perspective. The exact error representation and tractable JSR characterization provide an interesting connection between Q-learning and switching-system theory, supporting my weak-accept recommendation.

Critical weaknesses

Although the paper explicitly does not aim for uniformly better bounds, the broader insight for finite-time Q-learning remains somewhat unclear to me beyond advancing the existing SLS analysis. In particular, the exact worst-case rate of the switching family need not be tight for actual Q-learning dynamics. Clarifying what additional understanding this characterization provides would strengthen the paper’s significance.

Questions for authors
  1. Beyond improving the existing SLS analysis, what concrete insight into Q-learning convergence does the JSR characterization reveal?
  2. Are there conditions under which the JSR is a tight characterization of the actual Q-learning transient rate, supported by a matching lower bound? I am asking whether the current results establish such a connection; a new general lower-bound theorem would be a future-work direction rather than a requirement.
5 comments

We sincerely thank you for your positive assessment and for these helpful questions. We have revised the Introduction and Conclusion to clarify the direct analysis, its broader relevance, and the remaining open question. The manuscript changes are blue.

  1. Insight beyond the existing switching-system analysis: Earlier switching-system analyses handle an affine error model indirectly through upper and lower comparison systems. We instead represent the Q-learning error directly as ek+1=Mμkek+αwk,e_{k+1}=M_{\mu_k}e_k+\alpha w_k, where ek=Qk−Q∗e_k=Q_k-Q^*, MμkM_{\mu_k} is the current error-update matrix, and wkw_k is the sampling noise. This representation needs no upper or lower comparison systems. A reference system is still used later to bound the noise contribution.

Consequently, we can attach the joint spectral radius (JSR) to the direct error drift and retain transition structure and update frequencies that the earlier row-sum estimate discards. This can give a tighter exponential decay term in the convergence upper bound. For this matrix family, the JSR equals the rate of the slowest fixed deterministic-policy mode, providing a concrete interpretation and a way to compute the rate. The constants and noise term still matter for the complete finite-time comparison.

This also gives a useful starting point for analyzing and developing other algorithms, including methods with linear function approximation and Double Q-learning. Deriving their error-update models can help identify stability conditions and guide algorithm design. The revised Introduction cites existing applications of the broader switching-system viewpoint to minimax, deflated, heavy-ball, and value-advantage methods; these are separate results, while further extensions of the present framework need their own analysis.

  1. Tightness for actual Q-learning and a matching lower bound: The current paper does not establish this connection or provide a matching lower bound for the actual Q-learning transient rate. Its exact characterization concerns the associated switching matrix family. Thank you for suggesting this valuable research direction. We plan to investigate when actual learning dynamics attain the JSR-based rate and whether a matching lower bound can be proved under suitable conditions. We have explicitly identified this as future work in the Conclusion.
Reviewer_Sw2HOpenReview ↗

Response to authors

Thanks to the authors for their thorough rebuttal and for updating the paper.

The central question for me was what specific insight the JSR characterization provides into Q-learning itself, apart from strengthening the existing switching-system analysis. Having read their reply, I still do not have a clear answer to this. The JSR gives a worst-case rate across the switching family, and the authors acknowledge that their paper does not establish whether the actual Q-learning algorithm attains that rate. As for the applications to other algorithms discussed in the rebuttal, those appear in other papers rather than the present manuscript. Reviewer moF8 voiced a similar concern about the paper's takeaway for the wider community.

I do appreciate the candid answers, but given that my core concern is still unresolved, I am reducing my rating to 2 and increasing my confidence to 3.

Thank you for clarifying your concern. We would like to state the Q-learning-specific consequence more directly and focus on the results established in this manuscript.

Under our assumptions, the direct error-drift family satisfies

ρ^(Mα)=max⁡π∈Πdetρ(Mπ),\widehat{\rho}(\mathcal{M}_{\alpha}) = \max_{\pi \in \Pi_{\mathrm{det}}} \rho(M_{\pi}),

where MπM_{\pi} is the error-update matrix associated with a deterministic policy. This means that, within this family, arbitrary switching introduces no additional worst-case asymptotic exponential slowdown beyond the slowest fixed deterministic-policy mode. The characterization therefore identifies a specific structural property of Q-learning’s error representation: its worst exponential behavior over all switching sequences is already captured by a fixed policy-associated mode.

This result has a direct role in our finite-time guarantees for Q-learning. Through the exact error representation, the resulting quantity governs the transient terms in those bounds while retaining the interaction between transition structure and unequal update frequencies. The row-sum estimate 1−αdmin⁡(1−γ)1-\alpha d_{\min}(1-\gamma) compresses this information into the minimum update frequency. Our LP characterization makes the former quantity computable without enumerating deterministic policies and also provides a weighted-norm contraction certificate. These are results of the present manuscript, including their use in the analysis of independent and Markovian samples.

We fully agree that this does not establish whether actual Q-learning trajectories attain the worst-case rate. We also do not claim that a smaller exponential factor always yields a tighter complete finite-time bound, since constants and sampling noise remain relevant. Applications developed in other papers provide context but are not contributions of this submission.

The takeaway we wish to emphasize is this structural reduction and the computable, problem-dependent transient guarantee it provides for Q-learning. We appreciate your feedback and will make this takeaway and its precise scope clearer in the presentation.

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

This paper studies Q-learning from the perspective of switching linear system (SLS). Prior work on this topic controls the Q-learning error through auxiliary systems, while in this work, the authors directly exploit the SLS structure of the original error recursion. Under this framework, the convergence rate is characterized by the joint spectral radius (JSR) of the resulting SLS.

Critical strengths

The paper is generally well-written. The authors give a clear comparison between the SLS viewpoint of the framework used in current paper and those in prior works. The writing of the technical parts are also good.

The result looks technically solid, and the connection between the convergence rate of Q-learning and JSR of the SLS model looks interesting.

Critical weaknesses

The impact of the paper seems limited. Although the SLS viewpoint of Q-learning has been explored in the literature, and the current indeed brings novel technical insights compared to existing work, I am not sure what the conceptual messages it brings to the community. In this current, this paper might be interesting to experts working on the same topic, but I am not sure if the broad audience of ICLR will find it interesting. Given this my recommendation will be a weak accept.

Questions for authors

See weaknesses above.

2 comments

We sincerely thank you for your positive assessment of the presentation and technical soundness, and for encouraging us to clarify the paper's broader value. We have revised the Introduction and Conclusion to explain three contributions.

  1. More precise convergence upper bounds: The joint spectral radius (JSR) of the direct error model retains transition structure and update frequencies that a row-sum estimate can lose. It can therefore give a sharper exponential decay term when that estimate is conservative. The complete bound also includes constants and sampling noise, so the improvement depends on the problem.

  2. A clearer interpretation of Q-learning: We write the error as linear updates whose matrix changes during learning. The JSR summarizes their worst long-run exponential rate. This directly connects the update rule with convergence and offers an accessible explanation, especially for researchers familiar with stability analysis in control theory.

  3. Usefulness for analyzing and developing other algorithms: This viewpoint has already been applied beyond standard Q-learning: to minimax Q-learning for two-player zero-sum games, deflated Q-value iteration, corrected heavy-ball Q-learning, and dueling Q-learning / centered AV-learning. The last is a value-advantage method related to VA-learning, with a different update. These studies demonstrate the usefulness of switching-system analysis across several algorithm families, including how changes to an update can improve stability or convergence. They are applications of the broader viewpoint, not extensions proved in the present paper.

The same perspective provides a systematic starting point for further analysis and algorithm design, including linear function approximation and Double Q-learning: derive the error-update matrices, identify conditions that reduce errors, and use these conditions to guide new updates. We have added the existing examples and references to the Introduction and clarified the future directions in the Conclusion. All manuscript changes are blue. Thank you for helping us communicate this broader relevance.

Thanks for the response. I will keep my positive score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.