Stochastic Fixed-Point Iterations for Nonexpansive Maps: Convergence and Error Bounds
From MaRDI portal
\(Q\)-learningconvergence rateserror boundsfixed pointsnonexpansive mapsstochastic gradient descentstochastic iterations
Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Fixed-point theorems (47H10) Fixed-point iterations (47J26) Stochastic approximation (62L20) Numerical methods for mathematical programming, optimization and variational techniques (65Kxx) Analysis of algorithms and problem complexity (68Q25)
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
- 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
- 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?)
- 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 and its applications
- Stochastic Approximation for Nonexpansive Maps: Application to Q-Learning Algorithms
- Stochastic approximation, cooperative dynamics and supermodular games
- Stochastic approximations and perturbations in forward-backward splitting for monotone operators
- Stochastic Estimation of the Maximum of a Regression Function
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- 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
Cited in
(4)
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)
