A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning
Abstract
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.
Related
- Polynomial 𝒵-contraction: A unified approach with Application
- Fully Coupled Nonlinear Forward-Backward Stochastic Difference Equations: Spectral Contraction and Infinite-Horizon Maximum Principle
- Geometric Moment Contraction for Stochastic Nesterov Acceleration
- Wasserstein Contraction of Stochastic Systems on Manifolds: A Differential Approach
- Integral Contraction Approach to Coupled Integro-Fractional Stochastic Differential Systems
BibTeX
@misc{werf2026contraction,
title = {{A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning}},
author = {Ids van der Werf and Sergio Rozada and Antonio G. Marques},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29961},
eprint = {2609.29961},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29961},
}
RIS
TY - UNPB
TI - A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning
AU - Ids van der Werf
AU - Sergio Rozada
AU - Antonio G. Marques
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29961
UR - https://arxiv.org/abs/2609.29961
AB - 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.
ER -