PaperlayerView exact revision on arXiv

Source-linked AI summary

Switching Theory for Q-Learning

Donghwan Lee

arXiv:2604.19569v5cs.LGcs.AIeess.SY

TL;DR

Finite-time convergence analyses of constant-step-size tabular Q-learning need rates beyond asymptotic convergence. This paper derives a direct stochastic SLS error representation and analyzes it through the JSR, showing that the rate is tied to the exact worst-case exponential rate of the direct model and is computationally characterizable.

  • Problem

    Asymptotic convergence results do not quantify how rapidly Q-learning iterates approach the solution, while existing SLS comparison analyses use auxiliary systems for finite-time bounds.

  • Method

    The paper represents the Bellman maximization error through a suitable stochastic policy, derives a direct stochastic SLS error system, and analyzes its finite-time behavior using the JSR.

  • Results

    The JSR gives the leading exponential rate, equals the largest spectral radius among deterministic-policy modes, and admits an LP characterization evaluable to prescribed accuracy by bisection.

  • Takeaways & Limitations

    The direct JSR rate is tied to Q-learning’s intrinsic worst-case exponential rate and can be sharper than conservative row-sum upper bounds.

  • Takeaways & Limitations

    The comparison-system formulation addressed by prior work uses an affine error system and auxiliary upper and lower systems, while the finite-time bound’s transient constant may increase as the step-size decreases.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper reframes constant-step-size tabular Q-learning as a direct stochastic switching linear system, addressing limits of contraction and comparison-system analyses. It characterizes convergence through the system’s joint spectral radius and derives structural and computational results for that rate.

  • Existing finite-time analyses commonly treat Q-learning as nonlinear stochastic approximation and rely on Bellman contraction, while comparison-system methods do not directly exploit the original error recursion.The comparison approach controls error through auxiliary upper and lower systems, making intrinsic SLS quantities difficult to apply directly.
  • The paper develops a direct SLS representation for the error of constant-step-size tabular Q-learning.The Bellman maximization error is represented using a suitably chosen stochastic policy, producing an SLS conditional-mean error system with martingale-difference noise.
  • The resulting convergence rate is expressed through the JSR of the direct SLS drift, the exact worst-case exponential rate of the associated SLS.This rate can be sharper than row-sum comparison bounds when those bounds are conservative.
  • The paper proves that Q-learning’s JSR equals the largest spectral radius among switching modes associated with deterministic policies.This structural result makes the rate more interpretable than a generic switching-family characterization.
  • An exact LP feasibility characterization permits evaluating the JSR to any prescribed accuracy by bisection without enumerating deterministic policies.Together with the deterministic-policy result, this makes the direct rate computationally accessible.

2 PRELIMINARIES

The preliminaries define switching linear systems, their joint spectral radius, discounted MDP and Bellman-operator notation, and the stochastic setting for asynchronous constant-step-size Q-learning. They establish that JSR below one implies exponential stability and formulate the Q-learning recursion with martingale-difference noise.

  • 2.2 SWITCHING LINEAR SYSTEM (SLS): An SLS switches among matrices from a prescribed family, with optional mode-dependent affine terms and disturbance or martingale noise.When the affine term is zero, the deterministic part is a switching linear system.
  • 2.2 SWITCHING LINEAR SYSTEM (SLS): The JSR characterizes the worst-case exponential rate of a bounded matrix family, and JSR below one guarantees exponential convergence for every initial condition and switching sequence.For finite families, convex-hull notation allows products whose factors are convex combinations of family matrices.
  • 2.3 DISCOUNTED MARKOV DECISION PROCESSES AND BELLMAN OPERATOR: The MDP uses finite state and action spaces, transition probabilities, rewards, discount factor γ ∈ (0, 1), deterministic stationary policies, and Q-functions represented as state-action vectors.The Bellman optimality operator is F(Q) = R + γPVQ, with Q* as its unique fixed point.
  • 2.4 Q-LEARNING SETTING: Under the i.i.d. observation model, each state-action pair is sampled independently according to d(s, a), with dmin and dmax denoting the minimum and maximum sampling probabilities.The asynchronous update changes only the sampled coordinate; the remaining coordinates stay unchanged.
  • 2.4 Q-LEARNING SETTING: The vector Q-learning recursion is Qk+1 = Qk + α{D(F(Qk) − Qk) + wk}, where wk is a martingale-difference noise term.The conditional mean of the sampled update is D(F(Qk) − Qk), and the initial Q-table is deterministic.

3 AFFINE SLS REPRESENTATION OF Q-LEARNING

Earlier analyses represent constant-step-size Q-learning through a stochastic affine SLS whose offset reflects disagreement between the current greedy policy and an optimal policy. The paper identifies this offset as a parametrization artifact motivating a direct representation.

  • A deterministic greedy policy πQ is selected from the maximizing actions of each state, and πk denotes the greedy policy induced by Qk.An optimal deterministic policy π* satisfies Q* = R + γPΠπ*Q*.
  • Subtracting the fixed-point equation from the recursion yields the stochastic affine SLS error form (Qk+1 − Q*) = Aπk(Qk − Q*) + bπk + αwk.The matrices and affine term are defined by Aπ := I − αD + αγDPΠπ and bπ := αγDP(Ππ − Ππ*)Q*.
  • The affine offset is generally nonzero when the current greedy policy is not optimal, so the representation is affine rather than linear.The paper states that this offset is an artifact of the chosen parametrization and motivates a direct representation using action-wise errors averaged under a suitable stochastic policy.

4 SLS REPRESENTATION OF Q-LEARNING

The paper removes the affine offset from Q-learning’s error recursion by expressing the Bellman maximization error through a suitable stochastic policy, yielding a direct SLS representation. Its deterministic switching family is exponentially stable in the JSR sense, and the row-sum rate can be strictly looser than the JSR.

  • Direct SLS representation: A suitable stochastic policy represents the Bellman maximization error as an exact average of action-wise Q-errors, removing the affine offset.This produces the direct SLS error recursion used throughout the analysis.
  • Direct SLS representation: The resulting conditional-mean error dynamics use stochastic-policy matrices, while the stochastic component remains handled separately.The switching family is connected to deterministic-policy modes, and convergence requires checking the relevant spectral condition.
  • JSR stability: The row-sum rate is an upper bound on the switching-family rate and can be strictly larger than the JSR.Thus, the JSR can provide a sharper characterization of the switching dynamics than the row-sum bound.

5 FINITE-TIME ERROR BOUND UNDER I.I.D. OBSERVATION

For i.i.d. observations, the paper derives a finite-time error bound by comparing direct SLS dynamics with a stochastic reference system driven by the same noise. The resulting bound separates a noise floor from transients governed by the JSR rate, with a step-size-dependent product-growth constant.

  • Proof strategy: The analysis compares direct SLS dynamics with a stochastic reference system driven by the same noise, making the noise cancel pathwise in the residual.The remaining residual terms are controlled by the JSR product bound and a covariance estimate.
  • Finite-time bound: The finite-time bound applies when βε := ρ(Mα) + ε < 1, with Kβε controlling products generated by the switching family.The product of length zero is defined as the identity.
  • Finite-time bound: The bound separates a noise floor from transient terms governed by the JSR rate.The noise floor is identified separately from the remaining JSR-controlled transients.
  • Finite-time bound: Kβε can increase as α decreases because it depends on the gap between βε and ρ(Mα), enlarging the initial transient size.An explicit admissible choice of βε with Kβε = 1, independently of α, is given in Appendix A.6.

6 ANALYSIS OF THE JSR OF Q-LEARNING

The Q-learning switching family has positive structure that makes its JSR more tractable than that of a generic matrix family. The paper reduces the JSR to deterministic-policy spectral radii and provides an LP-bisection characterization that reaches any prescribed accuracy without enumerating those policies.

  • Motivation: Generic JSR computation and approximation are computationally hard, often requiring numerical upper and lower bounds rather than an exact value.The Q-learning family’s additional positive structure enables a more tractable analysis.
  • Deterministic-policy characterization: Theorem 3 reduces the Q-learning JSR to the largest ordinary spectral radius among deterministic-policy modes.This is a substantial simplification relative to a generic switching family.
  • LP characterization: The LP characterization expresses ρ(Mα) as the infimum of β admitting q and v satisfying entrywise vector inequalities.The formulation avoids explicit enumeration of deterministic policies.
  • LP characterization: For fixed β, LP feasibility followed by bisection locates the JSR infimum to any prescribed accuracy.A feasible pair (q, v) also yields a common weighted maximum norm and an explicit finite upper bound for Kβε.

7 FINITE-TIME ERROR BOUND UNDER MARKOVIAN OBSERVATION

For single-trajectory Q-learning under Markovian observations, the paper combines the direct SLS representation with a Poisson-equation decomposition of the Markovian noise. The resulting finite-time bound retains JSR-governed transients while adding a mixing-time term that vanishes with the step-size.

  • Markovian observation model: The analysis models the behavior-induced state-action process as a Markov chain with transition kernel P^b(s′, a′ | s, a) := P(s′ | s, a)b(a′ | s′).The chain is generated by the transition kernel and behavior policy used in single-trajectory Q-learning.
  • Markovian observation model: The Markovian analysis assumes the behavior-induced chain is irreducible and aperiodic and satisfies a uniform geometric mixing condition.The initial state-action distribution may be arbitrary.
  • Finite-time analysis: The direct SLS representation is combined with a Poisson-equation decomposition to control temporal dependence in the noise.The resulting bound retains the same JSR-governed transient terms as in the i.i.d. case.
  • Finite-time analysis: The single-trajectory finite-time bound includes a product-growth factor Kβε and an error term indexed by βε.The convention kβk−1 ε = 0 applies when k = 0.

8 NUMERICAL ILLUSTRATION

The numerical example compares exact JSR and row-sum rates for Q-learning across three step-sizes, then evaluates these rates against simulated relative error.

  • The four deterministic policies generate the Q-learning switching family in a two-state, two-action MDP with γ = 0.9.
  • The simulation uses rewards 1 and −9, with action 1 optimal in both states and Q∗(s, 1) = 10, Q∗(s, 2) = 0.
  • Each empirical curve averages 20 independent trajectories and compares normalized relative error with the exact-JSR and row-sum curves, which are not sample-complexity bounds.

9 CONCLUSION

The paper develops a direct-SLS finite-time analysis of constant-step-size Q-learning whose intrinsic rate is the JSR of its switching family. It further characterizes this JSR through deterministic-policy spectral radii and an LP-based computation, while showing that row-sum rates can be conservative.

  • The direct SLS representation yields a stochastic conditional-mean error recursion whose deterministic drift rate is the JSR ρ(Mα).
  • The exact stochastic-policy representation of Bellman maximization error produces the direct SLS recursion while retaining martingale noise.
  • The row-sum rate is a simple upper bound on the JSR and can be strictly larger, making it conservative.
  • The JSR equals the largest spectral radius among switching modes corresponding to deterministic policies.
  • An exact LP characterization enables JSR evaluation to prescribed accuracy by bisection without enumerating deterministic policies.
  • The direct-SLS framework complements Bellman-contraction and comparison-system analyses by exposing instance-dependent drift rates and potentially removing comparison-induced transient terms.

D STOCHASTIC FINITE-TIME ERROR BOUND

The analysis extends the JSR-based deterministic SLS framework to stochastic Q-learning, separating transient decay from the noise floor. Under a feasible weighted-norm certificate, it derives finite-time control of the error recursion.

  • Stochastic finite-time analysis: The stochastic recursion is analyzed through a product-defined Lyapunov estimate that separates transient behavior from the noise floor.The argument applies conditional Jensen’s inequality and norm equivalence to control the stochastic terms.
  • Stochastic finite-time analysis: Proposition 4 provides the stochastic finite-time estimate when βε < 1, using the JSR-based contraction parameter and an instance-dependent constant Cε.The supplied passage states the proposition and its admissible condition, while the constant’s scope is qualified separately.
  • Proof mechanism: The proof treats the error and noise vectors as measurable with respect to the current filtration, enabling conditional bounds for the active mode.The active mode Mµk(Qk − Q∗) is Fk-measurable before the stochastic noise is handled.
  • Proof mechanism: The Lyapunov argument uses the triangle inequality rather than cross-term cancellation because the constructed quantity is a norm.This choice supports separate control of the deterministic and noise contributions.
  • Proof mechanism: The finite-time derivation combines norm-equivalence bounds, conditional Jensen’s inequality, and the deterministic initial condition to establish the stated estimates.The proof proceeds by substituting intermediate bounds into the main recursion and then taking conditional expectations.

E DETAILED NUMERICAL EXAMPLE

The numerical example constructs the deterministic-policy modes and computes the Q-learning JSR exactly for three step-sizes. It then compares empirical relative errors with JSR- and row-sum-based curves, while also illustrating LP feasibility and nonattainment issues.

  • Model construction: The example uses a two-state, two-action asynchronous Q-learning problem with γ = 0.9 and four deterministic policies.The policies are enumerated under the state-action ordering (1,1), (2,1), (1,2), (2,2).
  • Model construction: The constructed mode matrices share a common vector structure, with the two action coordinates agreeing at each state.This equality lets the example verify the LP inequalities and compute the optimal feasibility value.
  • Simulation: The simulation averages 20 independent trajectories and compares empirical relative error with normalized exact-JSR and row-sum curves.These curves illustrate rate separation rather than empirical sample-complexity bounds.
  • LP feasibility: For a general transition kernel, the LP infimum need not be attained at β = β⋆, so feasibility at the limiting value must be treated separately.Entrywise-positive transition kernels guarantee feasibility at β⋆, whereas general kernels may not.
  • LP certificates: A feasible certificate (β, q, v) yields a common weighted maximum norm and bounds arbitrary products of the mode matrices.The certificate also supports an explicit finite-time bound, with β = ρ(Mα) when the infimum is attained.
  • Stability: The exact SLS is exponentially stable whenever its JSR is below one, and the finite-time bounds can use β = ρ(Mα) when the LP infimum is attained.The same conclusion is stated for the deterministic switching system and the stochastic error analysis.

J PROOF OF THEOREM 3

The proof establishes that Q-learning’s JSR equals the largest spectral radius among its deterministic-policy modes. It does so by constructing a positive common vector and weighted norm, then extending the argument from positive to general transition kernels.

  • Structural ingredients: The proof uses continuity, monotonicity, positive homogeneity, and a fixed-point argument for the Bellman map.These properties produce a positive fixed point whose maximizing deterministic policy identifies a mode with the relevant eigenvalue.
  • Positive-kernel case: When the transition kernel is entrywise positive, a positive fixed point generates a deterministic policy and a common weighted maximum norm for all stochastic-policy modes.The resulting norm contracts every mode by a common factor λ.
  • Spectral-radius equality: For every deterministic policy π, the weighted induced norm bounds ρ(Mπ), while repeating the maximizing mode gives the matching lower bound.The upper and lower bounds combine to identify the JSR with the largest deterministic-mode spectral radius.
  • General-kernel extension: For a general transition kernel, the proof perturbs the kernel to an entrywise-positive matrix and takes a continuity limit.The perturbation preserves entrywise domination of the original modes and transfers the spectral-radius bound.
  • Conclusion: The structural theorem concludes that the Q-learning JSR is the maximum spectral radius over deterministic-policy modes.The proof explicitly takes the maximum over π after establishing the corresponding upper and lower bounds.
  • LP characterization: The LP characterization follows by proving feasibility for every β > ρ(Mα) and identifying the infimum of feasible β values with the JSR.The inequalities are interpreted entrywise and the argument uses the same weighted-norm construction.

L PROOF OF THEOREM 5

The proof extends the direct SLS analysis to Markovian observations by centering the update under the stationary behavior-chain distribution and controlling the resulting noise. It establishes finite-time iterate bounds using Poisson-equation estimates, martingale components, and JSR-based product-growth control.

  • Noise control: The Markovian noise is generally not a martingale difference, so the proof replaces the i.i.d. second-moment argument with pathwise and Poisson-equation controls.The Poisson solution decomposes the centered conditional update into terms that support martingale and telescoping estimates.
  • Finite-time bound: The resulting single-trajectory iterates satisfy the theorem’s finite-time estimate, including the case β = ρ(M_α) when the LP infimum is attained.The bound uses a feasible (β,q,v) certificate, the product-growth constant K_βε, and W_max.
  • Stationary centering: The stationary centering identity holds without requiring the finite-time law of X_k to equal the stationary distribution d.For each fixed table Q, multiplying conditional coordinate updates by d(s,a) and summing gives D(F(Q) − Q) = h(Q).
  • Stationary averaged recursion: The stationary averaged recursion has the same direct SLS matrix family as the i.i.d. analysis, while only the noise process becomes Markovian.The averaged drift is centered using the stationary distribution of the behavior-induced chain, yielding Q_k+1 − Q* = M_μk(Q_k − Q*) + αw_k.
  • Poisson equation: The Poisson equation admits a measurable, continuously selectable solution on the bounded Q-table set, with uniformly convergent series construction and stacked norm control.The construction provides the regularity and bounds needed to handle the Markovian reference-system noise.
Loading 2604.19569v5…