PaperlayerView exact revision on arXiv

Source-linked AI summary

A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning

Ids van der Werf, Sergio Rozada, Antonio G. Marques

arXiv:2609.29961v1cs.LGeess.SPmath.OC

TL;DR

Convergence guarantees for sampled updates with periodically refreshed targets have relied on specific update structures. This paper analyzes such updates as stochastic operators, deriving geometric convergence to a ball under stated conditions; TD simulations track the predicted contraction and error-floor scaling.

  • Problem

    Convergence guarantees for sampled updates with targets refreshed every K steps remain limited beyond specific structures such as linear approximation or gradient-based inner steps.

    Source: §1 · p. 1

  • Method

    The paper models updates as stochastic operators and analyzes contraction in the updated variable, stability to the frozen variable, and mean-square sampling error.

    Source: §2 · p. 2

  • Results

    Outer iterates converge geometrically in root mean square to a ball around the fixed point; TD simulations track the contraction factor, and the error floor scales as Θ(√α).

    Source: §2.2 · p. 3, §4 · p. 4

  • Takeaways & Limitations

    Increasing K improves contraction per outer iteration but does not improve steady-state accuracy and is not necessarily sample efficient.

    Source: §2.2 · p. 3, §4 · p. 4

    For nonlinear value functions, Ass. 1 is an assumption, and the authors do not claim it holds for arbitrary approximators.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

Many iterative algorithms rely on bootstrapping. A variable is updated using a second, frozen copy as a target, which is periodically replaced with the updated variable. Majorize-minimize and inexact proximal-point methods share this structure, as does temporal-difference (TD) learning. However, existing convergence guarantees for scenarios that combine sampled updates with targets refreshed only every $K$ steps rely on the specific structure of the update, such as linear approximation or gradient-based inner steps, and on uniformly bounded sampling error. We instead model the sampled update as a stochastic operator on the parameter space, which reduces the analysis to a contraction argument that needs no gradient structure and allows the sampling error to grow with the iterates. Within this framework, we derive a finite-time bound for i.i.d. samples and any target-update period $K$. We show that the iterates converge geometrically in root mean square to a ball around the fixed point, provided the sensitivity to the frozen target is smaller than the contraction slack of the inner map. Existing deterministic frozen-target contraction and stochastic-gradient-type bounds follow as special cases of our framework, and simulations of TD learning reproduce the predicted contraction rate and scaling of the error floor with the step size.

1. INTRODUCTION

TD learning estimates value functions from sampled transitions using bootstrapped targets, making convergence challenging because the update is not the gradient of a fixed objective. The paper adopts an operator perspective to address gaps in convergence guarantees for sampled updates with periodically refreshed targets.

1. INTRODUCTION

  • TD estimates value functions from sampled transitions using bootstrapped targets that depend on the current estimate, so its update is not the gradient of a fixed objective.Practical implementations hold the target fixed for a number of steps using a target network.Source: §1 · p. 1
  • For large Markov decision processes, parametric value-function approximations make convergence analysis more involved than tabular methods.Classical results establish convergence for linear approximators with targets computed from the current estimate.Source: §1 · p. 1
  • Guarantees remain scarce for sampled updates with targets refreshed every K > 1 steps and approximators beyond the linear class.Existing approaches rely on specific update structures and analytical techniques, limiting transfer to inner updates that are not gradient steps.Source: §1 · p. 1
  • The paper formulates parametric TD learning from an operator perspective and establishes convergence with i.i.d. samples, without linearity assumptions and for arbitrary target-update periods K.The framework is introduced to characterize conditions under which TD learning converges.Source: §1 · p. 1

2. CONVERGENCE RESULTS VIA OPERATOR THEORY

The section models frozen-target iterations as stochastic operators, so convergence can be analyzed without requiring gradient structure. Under contraction and sampling assumptions, it establishes geometric root-mean-square convergence to a ball around a fixed point.

2. CONVERGENCE RESULTS VIA OPERATOR THEORY

  • The framework treats each sampled update as a stochastic operator, freezes θt for K inner updates from wt,0 = θt, then refreshes the target with wt,K.The population operator is the mean sampled map, and sampling error is its deviation from that mean.Source: §2 · p. 2
  • The population K-step map is contractive when target sensitivity Lθ is smaller than the inner map’s contraction slack, and its unique fixed point does not depend on K.The frozen-target operator and the K-step map share that fixed point.Source: §2 · p. 2
  • I.i.d. samples give martingale-difference errors controlled by an affine mean-square envelope rather than a uniform variance bound; Markovian sampling is outside the analyzed scope.The affine envelope is used because TD sampling error depends on the iterates, so a uniform bound would presuppose bounded iterates.Source: §2 · pp. 1–2

2.1. Particularization to TD learning with a frozen target

  • For TD, the sampled update is a semi-gradient step on squared TD error; K = 1 gives standard TD(0), while K > 1 uses a target network refreshed every K updates.For linear approximation, the population operator is affine and the framework’s assumptions hold under the stated conditions on q and α.Source: §2.1 · p. 2
  • For nonlinear value functions, the population-operator contraction condition is an assumption; the paper does not claim it holds for arbitrary approximators.The theorem applies to general parametrizations only when they satisfy the framework’s assumptions.Source: §2.1 · p. 3, §2.2 · p. 3

2.2. Main result

  • Outer iterates converge geometrically in root mean square to a ball around the fixed point when the theorem’s contraction condition holds.The error floor is independent of K, while the contraction factor decreases with K; additional inner steps accelerate outer iterations but do not improve steady-state accuracy.Source: §2.2 · p. 3

0 S2, and the roots are κ′

The proof bounds the error by a steady-state floor plus a geometrically decaying term. The discussion relates the guarantees to earlier analyses and clarifies what the bound does—and does not—say about increasing K.

0 S2, and the roots are κ′

  • The proof iterates an excess-error recurrence to obtain d_t,0 ≤ d_hat + ρ^t e_0,0.The recurrence bounds error above the floor across inner steps and then outer iterations.Source: §0 · p. 3

2.3. Discussion

  • The guarantees cover stochastic TD with i.i.d. sampling, arbitrary target-update periods, and general parametrizations satisfying the assumptions.Source: §2.3 · p. 3
  • The framework recovers a stochastic-gradient-type floor when target sensitivity vanishes and a deterministic frozen-target contraction bound when sampling noise vanishes.The deterministic bound has the form ∥θ_t − θ⋆∥ ≤ L_G(K)^t∥θ_0 − θ⋆∥, of the same nature as.Source: §2.3 · p. 4
  • For nonlinear TD with K > 1, the analysis gives a root-mean-square error bound under i.i.d. sampling and permits variance to grow with the iterates, unlike the cited uniformly bounded-variance result [16].Source: §2.3 · p. 4
  • When ρ < 1, increasing K improves the bound’s contraction rate per target update while leaving d_hat unchanged, but need not improve sample efficiency or determine actual stability and steady-state error.The bound’s properties do not rule out stabilization from larger K in deterministic linear approximation.Source: §2.3 · p. 4

3. SIMULATIONS

In the two-state linear TD(0) simulation, the bound tracks the observed contraction rate across target-update periods, while larger periods are not necessarily more sample-efficient. The error-floor bound captures its dependence on the step size, with Θ(√α) scaling.

3. SIMULATIONS

  • The bound reproduces the observed root-mean-square error decay rate for K ∈ {1, 2, 3, 5}, though it is conservative at steady state.Predicted contraction factors decrease with K toward ˜Lθ/(1 − ˜q), with rapidly diminishing returns from additional inner steps.Source: §3 · p. 4
  • Against sample count n = tK, larger K performs slightly worse, so faster progress per outer iteration does not imply better sample efficiency.The bound shows the same behavior.Source: §3 · p. 4
  • The error-floor bound ˆd captures the steady-state error’s dependence on step size α; for linear TD(0), ˆd = Θ(√α).This scaling matches the variance scaling of constant-step stochastic approximation.Source: §3 · p. 4

4. CONCLUSION

The paper proposes a stochastic contraction framework for frozen-target iterations and uses it to bound outer-iterate root-mean-square error under i.i.d. sampling. Its simulations show the predicted contraction behavior, while the error floor scales as Θ(√α).

4. CONCLUSION

  • The framework bounds outer-iterate root-mean-square error under i.i.d. sampling for any target-update period K, without requiring gradient structure in the inner map.The conclusion states that this framework is for stochastic iterations with a frozen target.Source: §4 · p. 4
  • In the linear TD(0) simulations, the derived contraction factor tracks observed decay, and both improve with K per outer iteration, though larger K is not necessarily sample-efficient.The conclusion reports these simulation findings without claiming improved sample efficiency.Source: §4 · p. 4
  • The error floor scales as Θ(√α), matching the variance scaling of constant-step stochastic approximation.The conclusion identifies this as the error-floor scaling.Source: §4 · p. 4

6. COMPLIANCE WITH ETHICAL STANDARDS

The numerical simulation study required no ethical approval.

6. COMPLIANCE WITH ETHICAL STANDARDS

  • The numerical simulation study required no ethical approval.The paper explicitly states this compliance determination.Source: §6 · p. 5
Loading 2609.29961v1…