Stochastic contraction framework improves td learning convergence analysis

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

Machine Learning

Summary

Many methods that learn by updating estimates based on parts of themselves use a technique called bootstrapping, but analyzing how well this works when updates happen intermittently and with some randomness is hard. The authors model these updates as a kind of shrinking process called a stochastic contraction, which simplifies the analysis and allows for greater flexibility in errors growing with the learning steps. They prove the learning process converges steadily to near the correct answer under clear conditions. This general approach helps unify previous specific results and matches test simulations on temporal-difference learning.

What this means in practice

Tested on simulated data.

Authors

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

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.
View PDFOpen arXiv