Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

1 Introduction

• Q-learning [43] must combine function approximation with Bellman learning dynamics in large or continuous state-action spaces, where arbitrary linear architectures can trigger the deadly triad and divergence.The approximation mechanism must preserve Bellman stability rather than only approximate Q∗ well.Source: §1 · pp. 1–2
• The framework preserves contraction by using nonexpansive reconstruction and compression operators on C(L), yielding a unique latent fixed point θ∗ for single-trajectory Q-learning.The compression map is stationary-normalized relative to the behavior distribution, aligning population updates with the observed Markovian trajectory.Source: §1 · p. 2
• The two stochastic-approximation algorithms estimate θ∗ from one trajectory, with high-probability last-iterate sup-norm error whose leading stochastic term is eO(n−1/2).One recursion avoids stationary normalization, while the other estimates that normalization from the same data stream.Source: §1 · p. 2
• Smoothness of the compression kernel transfers to θ∗ and the iterates, so uniform errors depend on the latent covering number Nρ(ϵ) rather than the formal dimension of C(L).The analysis controls errors on a finite ϵ-net and extends them to the full latent space using deterministic Lipschitz bounds.Source: §1 · pp. 2–3
• The algorithms are agnostic to the latent metric ρ, allowing the same trajectory to be analyzed under different smoothness–covering tradeoffs and thereby adapt automatically to latent geometry.The metric affects regularity and covering arguments, not the algorithmic updates.Source: §1 · p. 3

1.1 Literature Review

• Relative to prior work, the paper targets control rather than only policy evaluation by building contraction directly into positive compression and reconstruction on C(L), while combining Markovian dependence, learned normalization, and metric-entropy concentration.It also instantiates the framework for Q-measure-learning and frozen pretrained networks, where covering numbers reflect distinct activation patterns rather than raw width.Source: §1.1 · pp. 3–4, §1 · p. 3

• On compact state-action spaces, bounded randomized rewards yield a continuous mean reward with absolute reward and mean-reward norms bounded by 1.Rewards are realized after the next state and are generated from independent measurable random reward functions.Source: §2 · pp. 4–5
• The Bellman operator therefore has a unique fixed point Q*, bounded in [−1/(1−γ), 1/(1−γ)], whose greedy actions produce an optimal deterministic Markovian policy.Value-based reinforcement learning consequently focuses on estimating Q* and acting greedily with respect to that estimate.Source: §2 · pp. 4–5
• The learning problem uses a single trajectory generated by a Markovian behavior policy while transition and reward distributions remain unknown.The behavior chain follows the controlled transition kernel after actions sampled from the behavior policy.Source: §2 · p. 4
• Weak continuity of the controlled transition kernel and continuity of the mean reward ensure that the Bellman operator preserves C(Z) and is a γ-contraction in sup norm.The continuity argument uses integration against the transition kernel, while maximum and integration are nonexpansive.Source: §2 · p. 5
• Uniform ergodicity of the behavior chain, with unique invariant measure μb, provides the exploration condition and finite total-variation mixing time needed for convergence-rate analysis.The paper quantifies convergence to μb using the stated total-variation convention and mixing-time definition.Source: §2 · pp. 5–6

Representation framework

• The framework represents Q-functions by coefficient fields θ ∈ C(L), reconstructs qθ = Φθ, and compresses state-action functions through K.The latent space may be less complex than the state-action space, and the coefficient field may be infinite-dimensional.Source: §3 · p. 6

Stability and learning

• Nonexpansive Φ and K preserve sup-norm control around the γ-contractive Bellman update, enabling stochastic approximation of θ* from a single behavior-policy trajectory.The compression kernel depends on the stationary behavior distribution μb to induce stability in the single-trajectory algorithm.Source: §3 · pp. 6–7

Stable latent Bellman operator

• G = K T Φ is a γ-contraction with a unique fixed point θ* ∈ Θ, and θ* is ρ-Lipschitz.The contraction inherits the Bellman operator’s factor, while compression induces regularity needed for finite-sample analysis.Source: §3 · pp. 7–8

Approximation bias

• The fixed point’s Q-function approximation differs from Q* by representation error ||Q* − ΦKQ*|| amplified by at most (1 − γ)^-1.When the architecture is rich enough that ΦKQ* ≈ Q*, the latent fixed point closely approximates the true Bellman fixed point.Source: §3 · p. 8

4 Two Algorithms and Their Regularities

• The two implementable algorithms address the unknown compression denominator: unnormalized updates remove it, while empirical-normalized updates estimate it from the behavior trajectory.An idealized recursion assuming known c provides the basis for both designs.Source: §4 · p. 9, §4.1 · p. 10

4.1 An Idealized Algorithm

• The idealized stochastic approximation has stationary mean drift Gθ−θ, and its mean-field flow converges exponentially to θ* with sup-norm time constant 1−γ.The one-sample target has conditional mean equal to the Bellman operator applied to the current reconstruction.Source: §4.1 · pp. 9–10

4.2 Unnormalized Algorithm

• The unnormalized algorithm preserves θ* as its fixed point by treating c as a preconditioner, but its worst-case convergence time constant becomes c∧(1−γ).Because c∧≤1, this flow generally converges more slowly than the idealized flow.Source: §4.2 · pp. 10–11

4.3 Normalized Algorithm

• The normalized algorithm recursively estimates and clips the stationary denominator, converges almost surely toward the idealized dynamics, and has worst-case contraction time constant 1−γ.Clipping at c∧ is a numerical safeguard and requires only a practitioner-specified lower bound.Source: §4.3 · p. 11

4.4 Regularities of the Iterates

• Initialization and rescaled linear step sizes keep both algorithms’ iterates bounded and regular, yielding Lipschitz control that supports covering-number-based uniform concentration.The resulting deterministic regularity does not require smoothness of θ*, and compact latent spaces have finite covering numbers.Source: §4.4 · pp. 11–12, Normalized algorithm · pp. 13–14

Finite-time convergence

• Under Assumptions 1–4 and λU > 1, the unnormalized latent recursion converges uniformly over n ≥ 16αU with probability at least 1 − δ.The theorem’s stronger λU > 1 condition can be relaxed to λU > 1/2 while preserving the leading n^-1/2 term.Source: §5 · p. 14
• The bound combines an initial-transient term n^-λU, a martingale term at parametric n^-1/2 up to logarithms, and an n^-1 transient/discretization term.For λU in (1/2, 1), the higher-order term becomes n^-λU; regularity affects the rate through the covering scale.Source: §5 · p. 14

Rate dependence and metric adaptation

• The slower ODE convergence rate requires αU > 1/(c∧(1 −γ)), and this large step-size requirement introduces a factor of at least c−3/2 in front of the eO(n−1/2) error term.For a fixed latent space L, metric ρ can significantly shape complexity because geometry and covering numbers vary across metrics; ρ also enters through the smoothness of K, affecting ϵU.Source: §5 · p. 14
• Because the algorithm is agnostic to ρ, its statistical complexity automatically adapts by optimizing over admissible compact metrics for which κ is Lipschitz.The paper identifies this adaptation as potentially reducing complexity, including in the frozen neural-network application.Source: §5 · pp. 14–15

Finite and Euclidean latent spaces

• For finite latent spaces, the leading stochastic term scales as log J/n up to logarithmic factors; under Euclidean-type entropy, it scales as dL log D/n.Lipschitz regularity preserves the canonical n^-1/2 rate even when C(L) is infinite dimensional, with latent-space diameter entering logarithmically.Source: §5 · p. 15

6.4 Error Propagation Through Epoch Iteration

• The full horizon is partitioned into constant-length ODE epochs, and the within-window bound is combined with ODE tracking to form an inter-epoch error recursion.The proof establishes a simultaneous high-probability event across epochs using confidence allocation and a union bound before applying the epoch recursion to the last iterate.Source: §6 · p. 16, §6.4 · p. 23

6.1 Existence, Uniqueness, and Stability of the Mean-Field ODE

• The mean-field ODE has unique solutions that remain in the feasible set and converge exponentially toward θ* under the sup norm.Lipschitzness ensures existence and uniqueness, while nonexpansiveness and the Bellman contraction establish invariance and exponential stability.Source: §6.1 · pp. 16–17

6.2 Time-Scale Conversion and ODE Tracking Error

• The proof aligns SA iterations with continuous ODE time and bounds their tracking error over any fixed ODE-clock window.The comparison treats the recursion as an Euler discretization perturbed by stochastic noise and uses the corresponding τU clock.Source: §6.2 · pp. 17–19

6.3 Within-Window Error Decomposition and Bounds

• Within each window, the perturbation separates into Bellman target noise and Markov-sampling noise, with Poisson’s equation isolating transient nonstationary bias.The C(L)-valued martingale is controlled using Lipschitz smoothness, covering numbers, and interpolation over an ϵ-net, while the remaining bias is bounded separately.Source: §6.3 · pp. 20, 21, 23

6.4 Error Propagation Through Epoch Iteration

• On an event with probability at least 1 − δ, the epoch recursion holds simultaneously for every epoch and all intermediate sample sizes.This establishes the uniform event needed for the subsequent recursion analysis.Source: §6.4 · p. 25
• Applying Lemma 14 to the recursion yields the claimed bound simultaneously for every integer n ≥ m0.The argument combines the preceding epoch estimates with Lemma 14 to conclude the theorem’s uniform-in-n result.Source: §6.4 · p. 25
• Because λU > 1 and the step-size condition gives m0 = ⌈16αU⌉ ≤ 16nU_0, the recursion’s coefficient and initialization satisfy the required proof conditions.The coefficient comparison uses αU λU^−1/2 < αU λU/2 = 2 c∧(1 − γ).Source: §6.4 · p. 25

Limitations and proof structure

• Normalization can amplify sampling noise by c−1∧ and require longer burn-in because the empirical denominator must stabilize before stable error decay begins.The proof additionally handles dependence between the denominator estimate and the one-sample Bellman target.Source: §7 · pp. 25–26

Finite-time convergence

• Theorem 2 establishes finite-time convergence of the normalized latent recursion under Assumptions 1–4, uniformly for all n≥m0(δ) with probability at least 1−δ.The burn-in m0(δ) controls the empirical denominator uniformly over subsequent iterations.Source: §7 · pp. 25–26

Convergence-rate comparison

• Normalization removes c∧ from the contraction exponent, potentially allowing a smaller step-size factor αN, but the leading stochastic term scales with c−1∧.The normalized mean-field ODE contracts at rate (1−γ), rather than c∧(1−γ) in the unnormalized case.Source: §7 · pp. 25–26

Metric adaptation

• The normalized algorithm is agnostic to ρ and automatically adapts to latent geometry through the best metric choice, with burn-in adjusted according to ρ-dependent complexity.The leading last-iterate error bound applies for fixed n satisfying Theorem 2’s assumptions.Source: §7 · p. 26

Finite and Euclidean latent spaces

• Corollary 2.1 specializes the finite-time guarantee to finite latent spaces with discrete metrics and to Euclidean latent spaces under covering-number conditions.In both cases, the displayed bounds hold simultaneously for all n≥m0(δ) with probability at least 1−δ.Source: §7 · p. 26

8 Applications and Architectures

• The framework applies directly to two architectures: linear-density Q-measure-learning and a pretrained neural decoder indexed by a compact parameter space.Finite latent spaces permit exact implementation, while suitable metrics such as graph distance can induce coefficient-field smoothness.Source: §8 · p. 27

8.1 Q-Measure-Learning with Linear Density Approximation

• Q-measure-learning becomes a stable reconstruction-and-compression instance with G = KT, while linear-density approximation learns θ* through G = KTΦ.The normalized and unnormalized convergence theorems apply under the stated assumptions; Gaussian compression satisfies them under compactness, continuity, and local stationary coverage.Source: §8.1 · pp. 27–29
• For Q-measure-learning, conservative c∧ choices slow unnormalized convergence but affect only normalized-algorithm burn-in, not its leading-order rate.The unnormalized method requires αU > 1/[2c∧(1 −γ)] for the canonical n−1/2 rate, whereas αN does not require a lower bound on c∧.Source: §8.1 · p. 29

8.2 Pretrained Wide Network and Induced Geometry

• In pretrained networks, coefficient fields over output neurons enable exact recursions and yield complexity governed by activation-pattern covering numbers rather than raw width.With the geometry-aware metric ρ⋆, Nρ⋆(ϵ) equals the covering number of normalized activation patterns, and clustering is advantageous when Nρ⋆(ϵ) ≪J.Source: §8.2 · pp. 29–31
• The normalized neural update is a gradient step for an L2 Bellman-regression loss with the current coefficient field frozen inside the target.The same interpretation applies to the unnormalized algorithm.Source: §8.2 · p. 30

A Proof of Theorem 2

• Theorem 2 follows the ODE-tracking proof of Theorem 1, with uniform denominator control ensuring a contractive normalized mean field.On the good event, stochastic terms are handled as in the earlier proof.Source: A Proof of Theorem 2 · p. 35

A.1 Uniform Control of the Empirical Denominator

• After burn-in, the empirical denominator is controlled uniformly over every iteration k ≥ n.The proof first constructs a high-probability event providing a safety margin for all subsequent iterations.Source: §A.1 · p. 35
• The denominator fluctuation is analyzed on an r_c-net using centered functions g(ℓ, ·) with norm at most 1.Centering follows from the population denominator definition, while boundedness follows because κ(ℓ,z) and c(ℓ) lie in [0,1].Source: §A.1 · p. 35
• The Poisson-equation argument converts the Markovian denominator process into martingale differences with solution norm bounded by 2t_mix.This bound yields increments with range at most 4t_mix, enabling exponential-supermartingale concentration.Source: §A.1 · p. 35
• Ville’s inequality, applied to both signs and combined with a union bound over the net, gives a high-probability uniform net estimate.The argument extends over all k ≥ n+1 without a fixed horizon.Source: §A.1 · pp. 35–36
• The net estimate extends to all ℓ ∈ L because both empirical and population denominators are L_κ,ρ-Lipschitz.Their difference is therefore 2L_κ,ρ-Lipschitz, and taking the supremum over ℓ and k completes the lemma.Source: §A.1 · pp. 36–37

A.2 Mean-Field ODE and Tracking Error

• The mean-field dynamics use the vector field H_N,k and a step-size-induced T-window with a piecewise-defined ODE clock.The ODE evolves according to H_N,k on each interval [τ_N(n,k), τ_N(n,k+1)), starting from θ.Source: §A.2 · p. 37
• When sup_k≥n ||ĉ_k−c||≤c∧/4, the ODE has a unique solution in Θ and is exponentially stable around θ*.The trajectory remains in Θ, making clipping ineffective along the ODE path.Source: §A.2 · pp. 37–38
• Under the same denominator event, Lemma 7 bounds the normalized stochastic approximation’s tracking error over every window T>0.The bound follows the unnormalized analysis with factors adjusted by the ratio bound, including e2T·(5/4) and 2·(5/4)^2.Source: §A.2 · p. 39

A.3 Within-Window Error Bound

• Within each window, the error decomposes into cumulative martingale and nonmartingale terms, with denominator truncation preserving boundedness and Lipschitz control.The truncation satisfies [ĉ_k]ρ≤[ĉ_k]ρ≤Lκ,ρ, enabling uniform control through an ε-net and Lipschitz extension.Source: §A.3 · pp. 39–41
• For n sufficiently large and fixed T_N=1/5, the within-window martingale and total errors hold with probability at least 1−δ.The probability bounds are obtained by applying the martingale inequality on an ε-net and combining it with the deterministic estimates.Source: §A.3 · pp. 40–41

A.4 Error Propagation Through Epoch Iteration

• Epoch iteration sets m_r+1=max W_N(m_r,1/5) and allocates confidence δ_r=4δ/[π^2(r+1)^2] across windows.The construction combines the good denominator event with per-epoch window events.Source: §A.4 · p. 41
• Applying the stability, tracking, within-window, and recursion bounds yields the stated high-probability last-iterate result simultaneously for all n≥m_0(δ).The final substitution uses T=1/5, g=4(1−γ)/5, and λ=λ_N on the combined good event.Source: §A.4 · p. 42

B.1 Existence and Uniqueness of Solutions

• A globally Lipschitz map on a Banach space generates, from every initial value, a unique continuously differentiable solution trajectory.This result supplies existence and uniqueness for the continuous-time dynamics.Source: §B.1 · p. 42

B.2 Discrete Gr¨onwall’s Inequality

• The discrete Grönwall argument establishes the required inductive bounds through weighted recursions and an exponential inequality.The proof proceeds by induction and uses e^x ≥ 1 + x.Source: §B.2 · p. 43

B.3 Poisson’s Equation

• For bounded centered functions under the mixing assumption, Poisson’s equation has a unique bounded centered solution represented by an absolutely and uniformly convergent series.The solution satisfies the sup-norm bound ∥v∥ ≤ 2t_mix b.Source: §B.3 · p. 44
• The mixing-time decay argument yields the Poisson sup-norm estimate ∥v∥ ≤ 2t_mix b.The proof uses d(t_mix) ≤ 1/2, geometric decay at multiples of t_mix, and monotonicity of d(t).Source: §B.3 · p. 44

B.4 Martingale Maximal Inequality on a Net

• For bounded martingale differences indexed by a finite net, weighted partial sums admit a high-probability maximal inequality obtained with Hoeffding’s lemma, Ville’s inequality, and a union bound.The bound controls all times and net points simultaneously.Source: §B.4 · p. 45

B.5 Step Size Properties

• With step sizes α_k = α/(k + n_0), the accumulated step-size horizon has controlled end times when the next step is at most T/2.The lemma also gives explicit conditions for T = 1/4 or T = 1/5.Source: §B.5 · p. 46
• For T = 1/4 with n + n_0 ≥ 8 or T = 1/5 with n + n_0 ≥ 10, the relevant exponential factor is less than 3/2.These conditions provide concrete numerical control for the step-size estimates.Source: §B.5 · p. 46

C.1 Unnormalized Algorithm: Proof of Lemma 3

• The unnormalized proof begins with auxiliary bounds on v_k and uses contraction of TΦ to control the error decomposition.The bound on v_k includes a centering term independent of z.Source: §C.1 · pp. 46–47
• The unnormalized error estimate is obtained by reindexing the sum and applying bounds from (6.14), (C.1), and (C.2), together with W_U(n,T).The argument measures variation using the span seminorm |f|_span = sup_z f(z) − inf_z f(z).Source: §C.1 · pp. 47–48

C.2 Normalized Algorithm: Proof of Lemma 8

• The normalized proof treats the trivial case m = n separately and otherwise reuses the decomposition from the unnormalized argument for m ≥ n + 1.It isolates the last sum term for additional analysis.Source: §C.2 · p. 48
• The normalized proof subtracts Poisson equations and bounds the resulting terms by interval lengths, including a second-term span bound of at most 2c^-1.These interval arguments control the first and second terms separately.Source: §C.2 · pp. 48–49
• Centering preserves span while bounding the centered function’s sup norm, so Lemma 11 converts the interval estimates into the required norm bound.This is the key bridge from span control to sup-norm control.Source: §C.2 · p. 49
• The normalized recursion controls successive ˜c_k differences by 1/[c^2 ∧ (k + 1)] and combines this with summed bounds on the remaining terms.The proof uses α_N > 5/4, implied by λ_N > 1, and the step-size difference bound (C.2) before concluding.Source: §C.2 · p. 49

Error recursion bound

• Lemma 14 bounds the error sequence for α > 1 when m_0 + n_0 ≥ 16α, under windowed recursion assumptions and nondecreasing H_n.The result applies to T = 1/4 or T = 1/5, with λ = αg and corresponding restrictions on g.Source: D Epoch Error Recursion Analysis · p. 50

Epoch control

• Epoch clock bounds ensure each epoch has ODE length between T/2 and T, so epoch endpoints increase and the epoch sequence diverges.These bounds also support geometric control of the contraction-weighted sums.Source: D Epoch Error Recursion Analysis · pp. 50–51

Proof strategy

• The proof decomposes the error at n into completed-epoch contributions and a final partial-epoch contribution, with earlier errors weighted by subsequent contraction factors.Additivity of the epoch clock τ makes the contraction product equal to e^-gτ across later epochs.Source: D Epoch Error Recursion Analysis · p. 50

Accumulated-error control

• Monotonicity of H_n lets the proof replace intermediate H_{m_j} terms by H_n before bounding the resulting sums through their endpoint behavior.The argument uses logarithmic bounds and exponential decay in the epoch-clock gaps to control both accumulated terms.Source: D Epoch Error Recursion Analysis · pp. 51–52

Constant bounds

• The final constants are bounded separately for p ∈ {1/2, 1} using x = 1/α, λ = αg, and elementary exponential inequalities, yielding the stated recursion bound.The parameter restrictions ensure the required inequalities for both T choices and complete the proof of (D.2).Source: D Epoch Error Recursion Analysis · p. 52