Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
arXiv:1904.10778
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.
arXiv commentAccepted in SIMODS, 37 pages
References in corpus (17)
- Regularizing and Optimizing LSTM Language Models
- Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
- Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning
- Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
- 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
- Stop Wasting My Gradients: Practical SVRG
- Averaging Stochastic Gradient Descent on Riemannian Manifolds
- Variance-reduced -learning is minimax optimal
- Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
- Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
- Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
- SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
- Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
- Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
- Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization
- Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling