Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

Shengbo Wang

Source-linked AI summary

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

Shengbo Wang

arXiv:2608.22636v1Aug 23, 2026cs.LGmath.OCstat.ML

TL;DR

Arbitrary linear function approximation can destabilize Q-learning by failing to preserve Bellman contraction. The paper develops a stable infinite-dimensional latent framework with nonexpansive reconstruction and compression, then gives single-trajectory stochastic-approximation algorithms with near-parametric convergence and geometry-dependent complexity.

Problem
Arbitrary approximation architectures need not preserve Bellman contraction, making Q-learning with linear function approximation unstable.
Method
The paper learns a coefficient field on a compact latent metric space using nonexpansive reconstruction and compression operators, with two stochastic-approximation recursions from one behavior-policy trajectory.
Results
The algorithms achieve high-probability sup-norm guarantees with leading error eO(n^-1/2), while complexity is controlled by latent-space covering numbers rather than dim C(L).
Takeaways & Limitations
The algorithms are agnostic to the latent metric ρ and can adapt their analyzed error bounds to latent smoothness and geometry.
Takeaways & Limitations
The unnormalized algorithm’s mean-field convergence is slowed by the smallest compression multiplier c∧, while the theorem’s stronger λU > 1 condition is a simplification.

Abstract

from arXiv · show

Q-learning with linear function approximation can be unstable because an arbitrary approximation architecture need not preserve the Bellman contraction. We develop a stable infinite-dimensional linear function approximation framework for Q-learning from a single Markovian behavior-policy trajectory. The learning variable is a coefficient field $θ\in C(\mathbb L)$ on a compact latent metric space $(\mathbb L,ρ)$. The framework uses a reconstruction operator that maps $θ$ to a continuous Q-function and a compression operator that maps Bellman updates back to latent coordinates. Nonexpansiveness of both operators induces a contractive latent Bellman map on $C(\mathbb L)$, with a unique fixed point $θ^*$ whose reconstruction approximates the optimal Q-function up to representation error. We propose two stochastic approximation (SA) algorithms and establish their sup-norm convergence bounds with a leading term of order $\widetilde O(n^{-1/2})$. The infinite-dimensional formulation provides a powerful abstraction for identifying the structures that govern statistical difficulty. Smoothness of the compression map in $ρ$ is inherited by $θ^*$ and the SA iterates, allowing uniform estimation errors to be controlled through covering numbers of $(\mathbb L,ρ)$ rather than the dimension of $C(\mathbb L)$. Remarkably, the SA algorithms we propose are agnostic to the choice of $ρ$, and thus can automatically adapt to both the smoothness and the geometry. We further illustrate the framework through Q-measure-learning with linear density approximation and output-layer neural weight training under a frozen pretrained network.

1 Introduction

The paper addresses instability in Q-learning with arbitrary linear approximation by constructing a stable infinite-dimensional framework for single-trajectory learning. Its contractive latent formulation yields convergence guarantees whose complexity depends on latent geometry rather than the formal dimension of C(L).

Arbitrary linear approximation can break Bellman contraction, causing off-policy Q-learning dynamics to diverge through the deadly triad.
The framework uses nonexpansive reconstruction and compression operators to extend Bellman-contraction stability to an infinite-dimensional coefficient field.The coefficient field is learned on a latent space, while reconstruction maps it to Q-functions and compression maps Bellman updates back to latent coordinates.
The two stochastic-approximation algorithms use a single Markovian behavior-policy trajectory and achieve a leading sup-norm error of eO(n^-1/2).One recursion avoids stationary normalization, while the other estimates that normalization empirically.
Statistical complexity is governed by the latent metric-space covering number Nρ(ϵ), rather than the formal dimension of C(L).
The algorithms are agnostic to ρ, allowing their bounds to adapt to latent smoothness and geometry without optimizing the metric during learning.
Applications include Q-measure-learning with linear density approximation and output-layer training under a frozen pretrained neural network.For the neural application, covering numbers measure functionally distinct activation patterns rather than raw network width.

2 Markov Decision Processes and Behavior Policy

The paper formulates value-based reinforcement learning as optimal control of an MDP with unknown rewards and dynamics, using one behavior-policy trajectory for learning. Continuity, bounded rewards, and uniform ergodicity support a well-defined Bellman fixed point and single-trajectory analysis.

The objective is to learn the optimal action-value function Q* and derive an optimal greedy policy when rewards and dynamics are unknown.
Data consist of a single state-action-reward trajectory generated by a Markovian behavior policy.
Continuous rewards and weakly continuous transitions ensure that the Bellman operator maps continuous Q-functions into continuous Q-functions.
The Bellman optimality operator is a γ-contraction, so it has a unique fixed point Q* bounded within [−1/(1−γ), 1/(1−γ)].
Uniform ergodicity of the behavior chain provides a unique invariant distribution μb for the observed state-action process.

3 Stable Linear Function Approximation

The framework transfers Bellman updates into a latent coefficient space through reconstruction and compression operators designed to preserve sup-norm stability. Nonexpansiveness gives a unique latent fixed point, while compression smoothness supports finite-sample control and bounds representation bias.

The learner represents Q-functions using a possibly infinite-dimensional coefficient field θ in C(L), reconstructed through a linear feature map Φ.
The framework transfers the Bellman equation into latent coordinates to support stable and sample-efficient Q-learning approximation.
The compression kernel K averages candidate Q-functions against the behavior policy’s stationary distribution μb, aligning updates with single-trajectory sampling.
Nonexpansive Φ and K preserve the Bellman contraction, making G = K∘T∘Φ a γ-contraction with a unique fixed point θ*.
Lipschitz compression in ρ is inherited by θ* and keeps compressed Bellman targets continuous, enabling covering-based finite-sample analysis.
The reconstructed fixed point approximates Q* with representation error amplified by at most (1−γ)^-1.

4 Two Algorithms and Their Regularities

The paper develops two implementable stochastic-approximation recursions for estimating the latent fixed point when the stationary compression denominator is unknown. Both preserve bounded, regular coefficient fields, while differing in how they handle normalization.

Idealized algorithm: The idealized update assumes knowledge of the stationary denominator c, which is generally unavailable because it depends on the unknown behavior-chain distribution.The paper therefore uses the idealized recursion only as a basis for implementable alternatives.
Unnormalized algorithm: The unnormalized recursion removes c entirely while retaining the same fixed point θ* as the idealized flow.Removing c changes the mean-field dynamics but acts as a coordinate-wise preconditioner rather than changing the equilibrium.
Algorithm comparison: The unnormalized flow can converge more slowly because its sup-norm contraction time constant is c∧(1−γ), whereas normalization removes this minimum-denominator factor.The normalized recursion is expected to track an idealized flow with time constant 1−γ in the worst case.
Normalized algorithm: The normalized recursion estimates the stationary denominator empirically from the trajectory and clips it below by c∧ for numerical safety.The empirical denominator converges almost surely to the population denominator c.
Regularity: Both recursions maintain bounded coefficient fields through convex-combination updates and use rescaled step sizes to obtain the usual n−1/2 last-iterate rate.Their iterates also inherit Lipschitz regularity, enabling sup-norm control through latent-space covering numbers.

5 Convergence Rate of the Unnormalized Algorithm

The unnormalized algorithm admits high-probability sup-norm convergence bounds whose stochastic term has the canonical n−1/2 order. The effective complexity depends on the metric entropy of the latent space, including finite and Euclidean cases.

Theorem 1: Theorem 1 gives a simultaneous high-probability last-iterate bound for all n≥16αU under the stated assumptions and step-size condition.The theorem uses λU=αU c∧(1−γ)>1 as a simplifying condition.
Rate conditions: For λU∈(1/2,1), the leading n−1/2 term is preserved, but the higher-order term becomes n−λU instead of n−1.The stronger λU>1 condition prevents this higher-order term from changing order.
Error decomposition: The leading stochastic error has order eO(n−1/2), while initialization, nonstationarity, and discretization contribute additional terms.The parametric term arises from Bellman and Poisson martingales; the final n−1 term includes initial Markov-chain bias and higher-order discretization error.
Metric adaptation: The metric ρ shapes both covering-number complexity and compression-kernel smoothness, while the algorithm itself is agnostic to the metric choice.This permits automatic adaptation to the geometry and smoothness represented by admissible metrics.
Latent-space complexity: For infinite latent spaces, Lipschitz regularity preserves the canonical n−1/2 rate; under Euclidean entropy, dimension enters through dL log D/n up to common logarithmic factors.For finite latent spaces, the corresponding dependence is log J/n up to common logarithmic factors.

6 Proof of Theorem 1

The proof establishes convergence by comparing the stochastic recursion with a stable mean-field ODE over finite ODE-clock windows. It combines deterministic tracking, martingale concentration, and Markov-noise decomposition before assembling the global bound.

Global convergence: The final argument partitions the horizon into constant-length ODE epochs, applies within-window bounds, and solves the resulting inter-epoch recursion.This combines stochastic concentration, deterministic bias, and initialization effects into the theorem’s global rate.
Mean-field stability: The proof first establishes existence, uniqueness, boundedness, and exponential stability of the mean-field ODE.The flow contracts toward θ* at rate e−(1−γ)c∧t in the unnormalized setting.
ODE comparison: The stochastic approximation is interpreted as an Euler discretization of the mean-field ODE plus a stochastic perturbation.An ODE clock aligns discrete SA iterations with the continuous flow over fixed windows.
ODE tracking: Within each ODE-clock window, a deterministic tracking bound controls the discrepancy between the SA iterates and the restarted ODE.The analysis bounds the tracking error using step-size-weighted cumulative perturbations.
Noise decomposition: The proof decomposes perturbations into Bellman target noise and Markov sampling noise, with the latter requiring Poisson’s equation because the chain is Markovian and initially nonstationary.Poisson decomposition separates a martingale difference from a transient initialization bias.

7 Convergence Rate of the Normalized Algorithm

The normalized algorithm estimates the stationary compression denominator to improve mean-field contraction, while its finite-time analysis accounts for burn-in and possible noise amplification. Its guarantees remain metric-agnostic and apply across finite and Euclidean latent spaces.

Convergence-rate comparison: In the worst case, normalization amplifies sampling noise by a factor of c−1.This creates a trade-off between faster contraction and greater stochastic variability.
Finite-time guarantee: Theorem 2 provides a high-probability finite-time convergence bound simultaneously for all n ≥ m0(δ), including finite and Euclidean latent-space corollaries.The finite-space case uses cardinality J and the discrete metric; Euclidean cases use covering assumptions involving dL and D.
Burn-in and denominator estimation: The normalized recursion requires burn-in to control the empirical denominator uniformly over all later iterations.The proof must handle dependence between the denominator estimate and one-sample Bellman targets.
Convergence-rate comparison: Normalization removes c∧ from the contraction exponent, potentially allowing a smaller step-size factor αN.The leading stochastic term instead scales with c−1.
Metric agnosticism: The normalized algorithm is agnostic to ρ, with the leading last-iterate error retaining the same metric-adaptive form after burn-in adjustment.The metric affects the burn-in through rc and the complexity terms through smoothness and covering quantities.

8 Applications and Architectures

The framework is instantiated in linear-density Q-measure-learning and frozen pretrained neural networks. These examples verify the required regularity conditions and show how latent geometry and normalization enter concrete architectures.

8.1 Q-Measure-Learning with Linear Density Approximation: The linear-density Q-measure-learning construction learns a density coefficient field whose reconstruction approximates the optimal Q-function.Its population operator has the form G = KTΦ, with stationary-normalized compression.
8.1 Q-Measure-Learning with Linear Density Approximation: Unlike original Q-measure-learning, the framework updates a coefficient field directly rather than an empirical measure supported on the behavior trajectory.The connection holds at the operator level, while the data-update mechanisms differ.
8.1 Q-Measure-Learning with Linear Density Approximation: A Gaussian-type compression kernel satisfies the framework’s assumptions under compact Euclidean latent spaces, continuous embeddings, and a local-coverage condition.The resulting convergence bounds apply, although the lower bound c∧ may be conservative.
8.2 Pretrained Wide Network and Induced Geometry: For a frozen pretrained network, pre-output neurons index the latent space and activation patterns define a geometry in which nearby neurons have similar responses.A bias coordinate is included as a constant activation.
8. Applications and Architectures: The normalized stochastic update is a gradient step on a stationary L2 Bellman-regression loss with the current coefficient field frozen inside the target.The same interpretation applies to the unnormalized algorithm.
8.2 Pretrained Wide Network and Induced Geometry: The induced covering number measures functionally distinct neuron clusters rather than raw network width.Clustering is advantageous when Nρ⋆(ϵ) ≪ J at the learning-relevant resolution.

Appendices

The appendices establish denominator concentration for Markovian samples using nets, martingale tools, and Lipschitz extension. These controls supply the uniform high-probability event needed by the normalized convergence theorem.

Uniform denominator control: The denominator analysis begins with an rc-net of the latent space and centered bounded functions derived from the compression kernel.The net reduces uniform control to finitely many scalar martingale problems.
Uniform denominator control: Mixing-time bounds control the Poisson-equation solution used to represent denominator fluctuations as martingale differences.The solution norm is bounded by 2tmix under the stated assumptions.
Uniform denominator control: Exponential-supermartingale arguments extend the concentration uniformly over all later iterations rather than a fixed time horizon.This yields high-probability bounds after the burn-in period.
Uniform denominator control: Lipschitz extension from the net to the full latent space uses the 2Lκ,ρ-Lipschitz bound on the denominator error.The resulting burn-in lemma controls the empirical denominator uniformly over latent coordinates and later times.

A.2 Mean-Field ODE and Tracking Error

The normalized recursion is analyzed through a piecewise mean-field ODE whose denominator estimates vary across step-size intervals. On a good denominator event, the ODE remains stable, and tracking plus martingale bounds control the last-iterate error.

Mean-field ODE: Uniform denominator accuracy ensures rk remains bounded, making the interval vector fields globally Lipschitz and the ODE solution unique.The good event requires supk≥n ||ĉk − c|| ≤ c∧/4.
Mean-field ODE: The analysis defines an ODE clock and T-window from the normalized step sizes, then drives a piecewise ODE with HN,k.The interval vector field uses the clipped denominator ratio rk.
ODE stability: Exponential stability follows from the contraction of G together with the lower bound on the normalized denominator ratio.The proof applies integrating factors and Gronwall’s inequality across successive intervals.
Mean-field ODE: The ODE stays in Θ because G maps Θ into itself, so clipping is ineffective along the trajectory.This permits agreement between the clipped and unclipped solutions.
Tracking error: ODE tracking decomposes the normalized error into discretization and stochastic terms within each T-window.The tracking bound incorporates the factor 5/4 induced by denominator estimation.
Tracking error: Uniform martingale control is obtained on an ϵ-net and extended using Lipschitz seminorm bounds, producing high-probability last-iterate guarantees.The final recursion is solved on the denominator-control event and combined over successive windows.

B Auxiliary Results

The auxiliary results establish existence and uniqueness for a globally Lipschitz evolution, bounds for centered Markov-chain Poisson equations, concentration for bounded martingale differences, and step-size timing estimates.

A globally Lipschitz map on a Banach space admits a unique continuously differentiable solution for every initial condition.
The centered Poisson equation has a unique bounded centered solution, with absolute and uniform convergence of its defining sum.The resulting sup-norm bound is ∥v∥≤2t_mixb.
The mixing-time distance decays geometrically at multiples of t_mix, satisfying d(kt_mix)≤2^-k.
For bounded conditionally mean-zero increments, a maximal concentration bound follows from Hoeffding’s lemma, Ville’s inequality, and a union bound over signs and a finite index set.

C.1 Unnormalized Algorithm: Proof of Lemma 3

The proof controls the unnormalized algorithm through bounds on Poisson solutions, contraction properties, span seminorms, and changes in the recursion and step-size terms.

The proof begins with a uniform bound on the Poisson-related quantity ∥v_k(ℓ,·)∥.
Contraction of T_Φ and centering arguments are used to control function differences in the span seminorm.The span seminorm is defined as |f|_span=sup_z∈Z f(z)−inf_z∈Z f(z).
The error term is decomposed into sums whose bounds use the estimates in (6.14), (C.1), and (C.2), together with the definition of W_U(n,T).
The proof also bounds contributions involving successive Poisson solutions through interval-length arguments and centering, then combines the resulting estimates to complete the claim.
The recursion update yields the step-size-difference bound ∥c̃_k−c̃_{k−1}∥≤1/[c^2∧(k+1)].

D Epoch Error Recursion Analysis

The epoch analysis propagates error-recursion bounds across contraction epochs, using ODE-clock timing, monotone auxiliary sequences, and exponential-sum estimates to obtain the final bound.

Lemma 14 assumes an epoch-wise recursion for a nonnegative error sequence with nondecreasing H_n and constants K_1,K_2, then derives a bound for every n≥m_0.
The analysis considers T=1/4 or T=1/5 and imposes corresponding constraints on g, including g≤1 for T=1/4 and g≤4/5 for T=1/5.
Each epoch has ODE-clock length between T/2 and T, so the epoch endpoints increase strictly and tend to infinity.
Errors introduced in earlier epochs are multiplied by subsequent contraction factors whose product is e^{-gτ(m_{j+1},m_r)}.
Monotonicity of H_n reduces the relevant sums to bounds involving the final completed epoch, while end-time estimates control the exponential terms.
Substitution of the auxiliary exponential bounds into the recursion estimate proves the stated error bound.