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

arXiv: https://arxiv.org/abs/2609.29961 · HTML: https://mlsanity.com/paper/2609.29961/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 21 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 10 of 10)

- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [TD Convergence: An Optimization Perspective](https://mlsanity.com/paper/2306.17750/) (2023)
- [Deep Reinforcement Learning Control for Radar Detection and Tracking in Congested Spectral Environments](https://mlsanity.com/paper/2006.13173/) (2020)
- [Why Target Networks Stabilise Temporal Difference Methods](https://mlsanity.com/paper/2302.12537/) (2023)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Nonparametric Bellman Mappings for Reinforcement Learning: Application to Robust Adaptive Filtering](https://mlsanity.com/paper/2403.20020/) (2024)
- [A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning](https://mlsanity.com/paper/2501.01774/) (2025)
- [Target Updates May Stabilize Linear Q-Learning: Periodic and Soft Dynamics](https://mlsanity.com/paper/2606.02645/) (2026)

## Abstract (arXiv)

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.