Some limit properties of Markov chains induced by recursive stochastic algorithms

DOI10.1137/19M1258104zbMATH Open1485.93646arXiv1904.10778OpenAlexW3092741379MaRDI QIDQ5037552FDOQ5037552

Authors: A. K. Gupta, Hao Chen, Jianzong Pi, Gaurav Tendolkar 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: Recursive stochastic algorithms have gained significant attention in the recent past due to data driven applications. Examples include stochastic gradient descent for solving large-scale optimization problems and empirical dynamic programming algorithms for solving Markov decision problems. These recursive stochastic algorithms approximate certain contraction operators and can be viewed within the framework of iterated random operators. Accordingly, we consider iterated random operators over a Polish space that simulate iterated contraction operator over that Polish space. Assume that the iterated random operators are indexed by certain batch sizes such that as batch sizes grow to infinity, each realization of the random operator converges (in some sense) to the contraction operator it is simulating. We show that starting from the same initial condition, the distribution of the random sequence generated by the iterated random operators converges weakly to the trajectory generated by the contraction operator. We further show that under certain conditions, the time average of the random sequence converges to the spatial mean of the invariant distribution. We then apply these results to logistic regression, empirical value iteration, and empirical Q value iteration for finite state finite action MDPs to illustrate the general theory develop here.

Full work available at URL: https://arxiv.org/abs/1904.10778

Recommendations

• scientific article; zbMATH DE number 3980968
• scientific article; zbMATH DE number 7733450
• Stochastic recursive inclusions with non-additive iterate-dependent Markov noise
• On the convergence of markovian stochastic algorithms with rapidly decreasing ergodicity rates
• Stochastic Approximation and Large Deviations: Upper Bounds and <scp>w.p.1</scp> Convergence

zbMATH Keywords

stochastic gradient descentFeller Markov chainsiterative random mapsconstant stepsize Q learningempirical dynamic programming

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Stochastic learning and adaptive control (93E35)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• Markov Chains and Stochastic Stability
• Title not available (Why is that?)
• Acceleration of Stochastic Approximation by Averaging
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Convergence of stochastic processes
• Title not available (Why is that?)
• Robust Stochastic Approximation Approach to Stochastic Programming
• The concentration of measure phenomenon
• Title not available (Why is that?)
• Title not available (Why is that?)
• Infinite dimensional analysis. A hitchhiker's guide.
• Weak convergence of a sequence of Markov chains
• The Strong Law of Large Numbers for a Class of Markov Chains
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Iterated Random Functions
• Reinforcement learning. An introduction
• Title not available (Why is that?)
• Approximate iterative algorithms
• Approximations of Dynamic Programs, I
• Asynchronous stochastic approximation and Q-learning
• Finite-time bounds for fitted value iteration
• Abstract dynamic programming
• Recursive Stochastic Algorithms for Global Optimization in $\mathbb{R}^d $
• Stochastic Approximation for Nonexpansive Maps: Application to Q-Learning Algorithms
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
• CONVERGENCE OF SIMULATION-BASED POLICY ITERATION
• Q-learning and enhanced policy iteration in discounted dynamic programming
• On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
• Stochastic Gradient Descent on Riemannian Manifolds
• Title not available (Why is that?)
• Large-scale machine learning with stochastic gradient descent
• Convergence results for single-step on-policy reinforcement-learning algorithms
• Approximations of Dynamic Programs, II
• Concentration of measure inequalities in information theory, communications, and coding
• Error bounds for constant step-size \(Q\)-learning
• Minimizing finite sums with the stochastic average gradient
• Simulation-based optimization of Markov decision processes: an empirical process theory approach
• Asymptotic Behavior of a Markovian Stochastic Algorithm with Constant Step
• Title not available (Why is that?)
• A Universal Empirical Dynamic Programming Algorithm for Continuous State MDPs
• Ergodicity and central limit theorems for a class of Markov processes
• Real analysis on intervals
• Title not available (Why is that?)
• Metropolis-Type Annealing Algorithms for Global Optimization in $\mathbb{R}^d $
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
• Empirical dynamic programming
• A primer on monotone operator methods
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
• Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
• Riemannian Stochastic Variance Reduced Gradient Algorithm with Retraction and Vector Transport
• Bridging the gap between constant step size stochastic gradient descent and Markov chains
• A finite time analysis of temporal difference learning with linear function approximation
• Global convergence of policy gradient methods to (almost) locally optimal policies
• Performance guarantees for empirical Markov decision processes with applications to multiperiod inventory models
• Real analysis and applications
• Empirical \(Q\)-value iteration

Uses Software

• Saga
• SpiderBoost

This page was built for publication: Some limit properties of Markov chains induced by recursive stochastic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037552)