🤖 machine learning

A Switching System Theory of Q-Learning with Linear Function Approximation

This paper establishes a novel switching linear system framework for analyzing linear Q-learning, deriving finite-time error bounds and convergence certificates based on the joint spectral radius that offer less conservative guarantees than traditional one-step norm bounds.

Original authors: Donghwan Lee, Han-Dong Lim

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Donghwan Lee, Han-Dong Lim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Teaching a Robot to Navigate a Maze

Imagine you are teaching a robot to navigate a giant, complex maze to find treasure. The robot doesn't know the map; it has to learn by trial and error. This is Reinforcement Learning.

The specific algorithm the paper studies is called Q-Learning. Think of Q-Learning as the robot's "scorecard." Every time the robot is in a specific spot (state) and considers a specific move (action), it looks at its scorecard to guess how good that move will be.

The Problem:
In a simple maze, the robot can have a scorecard with a box for every single spot and move. But in a real-world maze (like a self-driving car or a video game), the number of spots is infinite. You can't write down a scorecard for every single possibility. It would take too much memory and time.

The Solution (Linear Function Approximation):
To fix this, the robot uses a "shortcut." Instead of memorizing every box, it learns a simple formula (a line) that predicts the score based on a few key features. This is called Linear Function Approximation (LFA). It's like the robot learning a general rule like "If I'm near a wall, turn left," rather than memorizing "If I'm at coordinate (5, 5), turn left."

The Core Discovery: The "Switching" System

The authors of this paper realized that even though the robot is using a simple formula, the way it updates its learning is actually very complex. It's not just a smooth, straight line toward the answer.

The Analogy: The Shifting Terrain
Imagine the robot is walking on a path toward a destination (the perfect scorecard).

In a normal math problem, the ground is flat, and the robot just walks straight.
In this paper, the authors discovered that the ground is actually a shifting landscape.

Every time the robot makes a decision, the "rules of the road" change slightly.

If the robot thinks "Turn Left" is best, the ground shifts one way.
If it thinks "Turn Right" is best, the ground shifts another way.

Because the robot is constantly changing its mind based on what it sees, it is constantly switching between different "modes" of walking. The authors call this a Switching Linear System (SLS). It's like driving a car where the steering wheel, the brakes, and the gas pedal all change their sensitivity depending on which gear you are in, and you are constantly shifting gears.

The Main Tool: The "Joint Spectral Radius" (JSR)

How do you know if the robot will eventually find the treasure, or if it will get lost in an infinite loop?

Usually, mathematicians check if the robot is taking steps that are getting smaller and smaller (like a ball rolling down a hill). But because the ground keeps shifting, a simple check isn't enough. You need to check every possible combination of shifts the robot could ever make.

The authors use a mathematical tool called the Joint Spectral Radius (JSR).

The Metaphor: Imagine the robot has a bag of different pairs of shoes. Each pair represents a different "mode" of learning. The JSR is a measure of the worst-case scenario. It asks: "If the robot puts on the worst possible combination of shoes in the worst possible order, will it still eventually stop moving?"
If the JSR is less than 1, it means that no matter how the robot switches its learning modes, it will eventually slow down and stop at the right answer.
If the JSR is greater than 1, there is a dangerous combination of moves that could make the robot run away forever, even if most moves are safe.

Key Findings of the Paper

The "Worst-Case" Guarantee: The paper proves that if the JSR is less than 1, the robot is guaranteed to learn the correct answer. This is a very strong guarantee because it accounts for the chaotic switching of the robot's decisions.
It's Not Just About One Step: Previous methods often looked at just one step of learning to see if it was safe. The authors show that this is like checking if a car is safe by looking at only one bump in the road. Their method looks at the entire journey of bumps. Sometimes, a single step looks dangerous, but the whole journey is actually safe because the robot corrects itself later.
The "Regularization" Twist: The paper also looks at a technique called Regularization.
- The Analogy: Imagine the robot is learning too fast and getting jittery. Regularization is like putting a "dampener" or a "brake" on the robot's learning speed to keep it steady.
- The authors show that adding this brake changes the "shifting landscape." Sometimes, adding the brake makes the landscape stable (the robot learns safely). Sometimes, if the brake is too heavy or the wrong type, it can actually make the robot unstable. They provide a formula to calculate exactly how much brake is needed to keep the JSR under 1.

Why This Matters (According to the Paper)

The paper doesn't claim to solve a specific real-world problem like curing a disease or building a specific robot. Instead, it provides a new mathematical lens to look at how these learning algorithms work.

Before: We looked at Q-learning as a simple, steady process.
Now: We understand it as a complex, shifting system that changes its own rules as it learns.

By using the "Switching System" view and the "Joint Spectral Radius" tool, the authors give us a more accurate way to predict when these learning algorithms will succeed and when they might fail. It's like upgrading from a simple map to a 3D simulation that accounts for shifting tectonic plates, ensuring the robot doesn't fall off the edge of the world.

Technical Summary: A Switching System Theory of Q-Learning with Linear Function Approximation

1. Problem Statement

Q-learning is a foundational algorithm for reinforcement learning in discounted Markov Decision Processes (MDPs). While tabular Q-learning is well-understood, it becomes computationally prohibitive for large state-action spaces. The standard remedy is Linear Function Approximation (LFA), where the Q-function is represented as a linear combination of features ( $Q_\theta = \Phi\theta$ ).

Despite extensive study, the convergence and stability of Linear Q-learning (Q-learning with LFA) remain complex. Existing analyses rely on stochastic approximation, Ordinary Differential Equation (ODE) methods, or Bellman contraction arguments. A critical gap exists in understanding the finite-time error behavior and the precise stability conditions, particularly because the deterministic recursion of linear Q-learning is non-linear due to the $\max$ operator in the Bellman update. Furthermore, there is a known distinction between the convergence of the projected Bellman equation (often solved via Projected Q-Value Iteration) and the actual linear Q-learning update; the former does not guarantee the convergence of the latter.

This paper addresses these issues by developing a new framework based on Switching Linear System (SLS) theory. The core problem is to characterize the stability of the linear Q-learning error dynamics, which switch between different linear modes depending on the current parameter estimates and the greedy policy derived from them.

2. Methodology

The authors propose a framework that models the linear Q-learning error dynamics as a Switching Linear System (SLS).

2.1 Switching System Representation

The key insight is that the non-linear difference between two Q-value estimates, $V_\theta - V_{\bar{\theta}}$ , can be expressed as a linear operator indexed by a stochastic policy. Specifically, for any $\theta, \bar{\theta}$ , there exists a stochastic policy $\mu_{\theta, \bar{\theta}}$ such that:
$V_\theta - V_{\bar{\theta}} = \Pi_{\mu_{\theta, \bar{\theta}}} \Phi (\theta - \bar{\theta})$
where $\Pi_\mu$ is the state-action transition matrix induced by policy $\mu$ .

Consequently, the deterministic linear Q-learning update map $T_\alpha(\theta) = \theta + \alpha g(\theta)$ (where $g$ is the projected Bellman residual) satisfies:
$T_\alpha(\theta) - T_\alpha(\bar{\theta}) = A_{\mu_{\theta, \bar{\theta}}} (\theta - \bar{\theta})$
where $A_\mu = I - \alpha \Phi^\top D \Phi + \alpha \gamma \Phi^\top D P \Pi_\mu \Phi$ .

This transforms the non-linear recursion into a switched linear error recursion:
$x_{k+1} = A_{\mu_k} x_k$
where $x_k = \theta_k - \theta^*$ is the error relative to a projected Bellman fixed point, and the switching signal $\mu_k$ is determined by the trajectory.

2.2 Joint Spectral Radius (JSR) as Stability Certificate

The stability of this switched system is analyzed using the Joint Spectral Radius (JSR) of the associated family of matrices.

Let $\mathcal{A}_\alpha$ be the finite family of matrices corresponding to all deterministic policies.
The JSR, denoted $\rho(\mathcal{A}_\alpha)$ , is defined as the exact worst-case exponential growth rate of products of matrices from this family.
The authors prove that the JSR of the convex hull of the stochastic-policy matrices is equal to the JSR of the finite deterministic family ( $\rho(\text{co}(\mathcal{A}_\alpha)) = \rho(\mathcal{A}_\alpha)$ ).

The condition $\rho(\mathcal{A}_\alpha) < 1$ serves as a robust sufficient certificate for stability. Unlike one-step norm bounds, the JSR captures the worst-case behavior over arbitrary switching sequences, providing a tighter and more intrinsic characterization of the system's stability.

2.3 Lyapunov Construction

When $\rho(\mathcal{A}_\alpha) < 1$ , the paper constructs a piecewise quadratic Lyapunov function (a norm $p_\epsilon$ ) directly from the products of the switching matrices. This function certifies that the map $T_\alpha$ is a global contraction in the $p_\epsilon$ -norm, ensuring the existence of a unique fixed point and exponential convergence of the deterministic recursion.

2.4 Stochastic and Regularized Extensions

Stochastic Case: The framework is extended to the i.i.d. sampling model. The stochastic recursion is decomposed into the deterministic switched dynamics plus a martingale-difference noise term. Finite-time error bounds are derived, showing that the error converges to a neighborhood of the fixed point, with the size of the neighborhood depending on the step size and noise characteristics.
Regularized Case: The analysis is applied to $\ell_2$ -regularized Q-learning. Regularization shifts the switching matrices by $-\alpha \eta I$ . The stability is determined by the JSR of this shifted family, $\rho(\mathcal{A}_{\alpha, \eta})$ . The paper derives bounds showing how regularization interacts with the step size and the intrinsic problem data.

3. Key Contributions and Results

3.1 Finite-Time Error Analysis

The paper derives explicit finite-time error bounds for linear Q-learning. The convergence rate is tied to the JSR of the switching family. Specifically, if $\rho(\mathcal{A}_\alpha) < 1$ , the error decays exponentially at a rate determined by $\rho(\mathcal{A}_\alpha) + \epsilon$ . The bounds include terms for the initial error, the step size, and the noise floor.

3.2 Distinction Between Iterations

The paper rigorously demonstrates that the convergence of Projected Q-Value Iteration (PQVI) does not imply the convergence of Deterministic Linear Q-Learning, and vice versa.

Example 1 & 2: The authors provide counterexamples where PQVI diverges while linear Q-learning converges (and vice versa). This highlights that the two algorithms, while sharing the same fixed point, have fundamentally different dynamic behaviors.
Example 4: A case is shown where the JSR of the switching family is greater than 1 (implying instability under arbitrary switching), yet the actual Bellman-generated non-linear recursion converges globally. This illustrates that the JSR condition is a conservative sufficient condition for the actual trajectory, as the actual trajectory does not explore all possible switching sequences allowed by the JSR definition.

3.3 Regularization Analysis

The paper provides a unified view of regularized Q-learning. It shows that regularization shifts the switching modes, leading to a new JSR condition.

Proposition 4: Establishes an exact identity relating the regularized JSR to a rescaled unregularized JSR: $\rho(\mathcal{A}_{\alpha, \eta}) = |1 - \alpha \eta| \rho(\mathcal{B}_{\alpha/(1-\alpha \eta)})$ .
Insight: This reveals that increasing the regularization parameter $\eta$ does not monotonically improve stability in a fixed-step-size setting. While it increases the "accretivity" (stability margin), it also alters the effective step size scaling, which can tighten stability constraints.

3.4 Lyapunov Certificates

The paper constructs a common piecewise quadratic Lyapunov function (a norm) that certifies contraction for the non-linear map. This certificate is less conservative than standard one-step norm bounds because it accounts for the product structure of the switching dynamics.

4. Significance and Claims

The paper claims to offer a unified framework for analyzing linear Q-learning through the lens of switching systems. Its primary significance lies in:

Exact Worst-Case Characterization: By using the JSR, the analysis captures the exact worst-case exponential rate of the system, moving beyond conservative one-step bounds.
Unified View of Regularization: It connects regularized Q-learning to the same switching system theory, showing how regularization modifies the switching family and providing explicit conditions for stability.
Clarification of Convergence Mechanisms: It explicitly separates the dynamics of linear Q-learning from projected Bellman iterations, explaining why they may exhibit different convergence behaviors despite sharing fixed points.
Robustness: The JSR-based condition is a robust certificate for the actual stochastic policy switching, as it guarantees stability even under arbitrary switching, which is a superset of the actual trajectory's switching behavior.

The authors note that their analysis focuses on i.i.d. observations for clarity, though the switching decomposition can be extended to Markovian noise. The work does not propose new algorithms but rather provides a deeper theoretical understanding of existing linear Q-learning dynamics and their stability properties.