Technical Summary: Geometrically Averaged Hard Target Updates for Linear Q-Learning

Problem Statement

In modern deep Q-learning, periodic hard target updates (copying the online network to a target network every $m$ steps) are a standard stabilization mechanism. While empirically robust, the precise theoretical dynamics of these updates in the presence of function approximation remain an active area of study. Specifically, existing literature has not fully characterized the exact boundary dynamics of periodic hard target updates within the tractable setting of linear Q-learning.

The core challenge is that while different target update strategies (e.g., standard periodic updates vs. projected Q-value iteration) may share the same fixed-point equation (the projected Bellman equation), their convergence properties and stability certificates differ significantly. The paper seeks to bridge the gap between the period-one deterministic linear Q-learning (DLQL) and the projected Q-value iteration (PQVI) by introducing a continuous parameterization of the target update mechanism.

Methodology

1. Theoretical Framework: Switching Systems and JSR

The paper analyzes linear Q-learning using a switched linear system model. In this framework:

• The Bellman maximum operator is represented as a switching signal that selects among a finite set of deterministic greedy policies (modes).
• Stability is certified using the Joint Spectral Radius (JSR) of the family of matrices generated by these switching modes. A JSR strictly less than one ($\rho < 1$) guarantees uniform exponential decay of the error under arbitrary switching.
• The analysis relies on the switching-system model developed by Lee and Lim (2026) and the target-update analysis of Lee (2026a).

2. The $\lambda$-Target Update Mechanism

The paper introduces $\lambda$-DLQL, a method that replaces the choice of a single integer target period $m$ with a geometric average over all possible hard-target periods.

• Definition: The update map is defined as a weighted sum of the $m$-period boundary maps $A_{\mu, m}^{\text{DLQL}}$ with geometric weights $(1-\lambda)\lambda^{m-1}$, where $\lambda \in [0, 1]$.
• Endpoints:
  • $\lambda = 0$: Recovers the standard period-one DLQL (one-step update).
  • $\lambda \uparrow 1$: Recovers the projected Q-value iteration (PQVI), effectively corresponding to an infinite target period.
• Interpolation: The parameter $\lambda$ continuously interpolates between short-horizon (DLQL) and long-horizon (PQVI) updates, analogous to the spirit of TD($\lambda$) but applied to hard-target boundary maps rather than eligibility traces or multi-step returns.

3. Implementation Strategies

To make the geometric average computationally feasible without simulating infinite periods, the paper proposes three equivalent implementations:

1. Recursive Solver (Inverse-Form): Derives a closed-form linear correction equation:
   $$\bar{\theta}_{n+1} = \bar{\theta}_n + \alpha \left[ (1-\lambda)I + \lambda \alpha \Phi^\top D \Phi \right]^{-1} \Phi^\top D (R + \gamma P \Pi_{\pi_n} \Phi \bar{\theta}_n - \Phi \bar{\theta}_n)$$
   This requires solving a linear system of size $m \times m$ (feature dimension) at each boundary.
2. Inverse-Free Recursion: Uses an auxiliary variable $w_n$ and a Richardson iteration to track the correction term, avoiding explicit matrix inversion. This results in a two-line recursion with an augmented state space.
3. Sampled Period-$m$ Implementation: Instead of averaging, the algorithm samples a period $M$ from a geometric distribution $P(M=m) = (1-\lambda)\lambda^{m-1}$ and performs exactly $M$ online updates before the next target copy.

Key Contributions

1. Geometric Averaging of Hard Targets: The paper constructs a continuous family of target update maps ($\lambda$-DLQL) that connects the discrete endpoints of DLQL and PQVI without altering the underlying fixed-point equation (the projected Bellman equation).
2. Stability Analysis via JSR: The authors provide a rigorous stability analysis showing that the convergence of $\lambda$-DLQL is determined by the JSR of the resulting switched family $A_{\lambda}^{\text{DLQL}}$.
   • They prove that as $\lambda \to 0$, the JSR converges to that of the DLQL family.
   • As $\lambda \to 1$, the JSR converges to that of the PQVI family.
   • The paper establishes that stability at one endpoint does not guarantee stability at the other, and the intermediate $\lambda$ values can potentially offer stability certificates where endpoints fail.
3. Algorithmic Equivalence: The paper demonstrates that the recursive inverse-form, the inverse-free auxiliary recursion, and the sampled period-$m$ implementation all converge to the same projected Bellman fixed point (assuming uniqueness) and share the same theoretical stability properties under specific conditions (e.g., small step-sizes for the inverse-free version).
4. Theoretical Characterization of Endpoints: The paper clarifies that while DLQL and PQVI solve the same projected Bellman equation, their error dynamics are governed by different switching families ($A^{\text{DLQL}}$ vs. $A^{\text{PQVI}}$), necessitating separate stability certificates.

Results

• Convergence: Under the condition that the step-size $\alpha$ satisfies $0 < \alpha < 2/\lambda_{\max}(\Phi^\top D \Phi)$, the paper proves that if the JSR of the relevant switched family (either $A_{\lambda}^{\text{DLQL}}$ for $\lambda < 1$ or $A^{\text{PQVI}}$ for $\lambda=1$) is strictly less than one, the boundary errors converge uniformly exponentially to zero.
• Endpoint Behavior: Theorem 7.1 details four scenarios based on the JSR values of the DLQL and PQVI endpoints:
  • If both are stable, small and large $\lambda$ are stable.
  • If only PQVI is stable, large $\lambda$ is stable while small $\lambda$ is unstable.
  • If only DLQL is stable, small $\lambda$ is stable while large $\lambda$ is unstable.
  • If both are unstable, the endpoints are unstable, though an intermediate $\lambda$ might theoretically improve the JSR (though the paper notes this is not guaranteed).
• Implementation Validity: The recursive and inverse-free implementations are shown to be mathematically equivalent to the geometric average definition in terms of the fixed point and the induced error dynamics (for the inverse-form) or an augmented system (for the inverse-free).

Significance and Claims

The paper claims to provide a unified theoretical framework for understanding hard target updates in linear Q-learning. Its primary significance lies in:

• Bridging the Gap: It connects the discrete, periodic hard-copy mechanism (common in deep RL) with the continuous projected value iteration (a standard theoretical benchmark) through a single parameter $\lambda$.
• Precision: It moves beyond empirical observations to provide exact boundary dynamics and JSR-based stability certificates for linear function approximation.
• Flexibility: It offers a mechanism to tune the "effective period" of target updates continuously, potentially allowing practitioners to select a $\lambda$ that optimizes stability when the standard endpoints (period-1 or infinite-period) are suboptimal.
• Implementation: It provides practical, implementable algorithms (recursive and inverse-free) that realize this theoretical mechanism without requiring the simulation of infinite horizons.

The authors explicitly state that this formulation is for a deterministic version of linear Q-learning but note that the formulation extends to stochastic reinforcement learning settings. The work does not claim to solve the non-linear deep RL case directly but aims to clarify the fundamental dynamics of target updates in the linear regime.