Stochastic Fixed-Point Iterations for Nonexpansive Maps: Convergence and Error Bounds
From MaRDI portal
Publication:6180255
error bounds\(Q\)-learningconvergence ratesfixed pointsstochastic gradient descentnonexpansive mapsstochastic iterations
Stochastic approximation (62L20) Analysis of algorithms and problem complexity (68Q25) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Fixed-point theorems (47H10) Fixed-point iterations (47J26) Numerical methods for mathematical programming, optimization and variational techniques (65Kxx)
Abstract: We study a stochastically perturbed version of the well-known Krasnoselski--Mann iteration for computing fixed points of nonexpansive maps in finite dimensional normed spaces. We discuss sufficient conditions on the stochastic noise and stepsizes that guarantee almost sure convergence of the iterates towards a fixed point, and derive non-asymptotic error bounds and convergence rates for the fixed-point residuals. Our main results concern the case of a martingale difference noise with variances that can possibly grow unbounded. This supports an application to reinforcement learning for average reward Markov decision processes, for which we establish convergence and asymptotic rates. We also analyze in depth the case where the noise has uniformly bounded variance, obtaining error bounds with explicit computable constants.
Recommendations
- scientific article; zbMATH DE number 7733450
- Stochastic Approximation for Nonexpansive Maps: Application to Q-Learning Algorithms
- Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces
- On the rate of convergence of Krasnosel'skiĭ-Mann iterations and their connection with sums of Bernoullis
- A stochastic contraction mapping theorem
Cites work
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- scientific article; zbMATH DE number 1405930 (Why is no real title available?)
- A Stochastic Approximation Method
- Acceleration of Stochastic Approximation by Averaging
- Asynchronous stochastic approximation and Q-learning
- Construction of fixed points of nonlinear mappings in Hilbert space
- Learning algorithms for Markov decision processes with average cost
- On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Quelques propriétés des opérateurs angle-bornes et n-cycliquement monotones
- Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces
- Reinforcement learning. An introduction
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic Approximation for Nonexpansive Maps: Application to Q-Learning Algorithms
- Stochastic Estimation of the Maximum of a Regression Function
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic approximation and its applications
- Stochastic approximation, cooperative dynamics and supermodular games
- Stochastic approximations and perturbations in forward-backward splitting for monotone operators
- Stochastic forward-backward splitting for monotone inclusions
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
- Variance-based extragradient methods with line search for stochastic variational inequalities
This page was built for publication: Stochastic Fixed-Point Iterations for Nonexpansive Maps: Convergence and Error Bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180255)
