Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise

DOI10.1287/MOOR.2019.1037zbMATH Open1460.62136arXiv1611.05961OpenAlexW3044123424MaRDI QIDQ3387930FDOQ3387930

Authors: Vinayaka G. Yaji, Shalabh Bhatnagar 

Publication date: 8 January 2021

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: In this paper we study the asymptotic behavior of a stochastic approximation scheme on two timescales with set-valued drift functions and in the presence of non-additive iterate-dependent Markov noise. It is shown that the recursion on each timescale tracks the flow of a differential inclusion obtained by averaging the set-valued drift function in the recursion with respect to a set of measures which take into account both the averaging with respect to the stationary distributions of the Markov noise terms and the interdependence between the two recursions on different timescales. The framework studied in this paper builds on the works of it{A. Ramaswamy et al. } m by allowing for the presence of non-additive iterate-dependent Markov noise. As an application, we consider the problem of computing the optimum in a constrained convex optimization problem where the objective function and the constraints are averaged with respect to the stationary distribution of an underlying Markov chain. Further the proposed scheme neither requires the differentiability of the objective function nor the knowledge of the averaging measure.

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

Recommendations

• Stochastic recursive inclusions with non-additive iterate-dependent Markov noise
• A Recurrence Principle for Stochastic Difference Inclusions
• Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem
• A generalization of the Borkar-Meyn theorem for stochastic recursive inclusions
• Stochastic inclusions driven by two-parameter martingales
• On the recurrence of some time inhomogeneous Markov processes
• On the growth rate of a linear stochastic recursion with Markovian dependence
• Limit theorems for stochastic recursions with Markov dependent coefficients
• scientific article; zbMATH DE number 3896036

zbMATH Keywords

stochastic approximationdifferential inclusionsset-valued mapsconstrained convex optimizationiterate-dependent Markov noise

Mathematics Subject Classification ID

Stochastic approximation (62L20) Stochastic programming (90C15) Variational inequalities (49J40) Processes in random environments (60K37) Numerical methods for variational inequalities and related problems (65K15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Stochastic Approximation Method
• Convex optimization theory.
• Stability of Stochastic Approximation under Verifiable Conditions
• Title not available (Why is that?)
• Subgradient methods for saddle-point problems
• Applications of a Kushner and Clark lemma to general classes of stochastic algorithms
• Numerical solution of saddle point problems
• Envelope Theorems for Arbitrary Choice Sets
• Stochastic Approximation Approaches to the Stochastic Variational Inequality Problem
• Multivariate stochastic approximation using a simultaneous perturbation gradient approximation
• Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
• Stochastic approximation with two time scales
• Title not available (Why is that?)
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
• Stochastic Approximations and Differential Inclusions
• On dynamical properties of general dynamical systems and differential inclusions
• A Dynamical System Approach to Stochastic Approximations
• Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds
• Title not available (Why is that?)
• The inflation of attractors and their discretization: The autonomous case
• Convergence of Markovian stochastic approximation with discontinuous dynamics
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Asynchronous stochastic approximation with differential inclusions
• Analysis of Stochastic Approximation Schemes With Set-Valued Maps in the Absence of a Stability Guarantee and Their Stabilization
• Two Time-Scale Stochastic Approximation with Controlled Markov Noise and Off-Policy Temporal-Difference Learning
• Stochastic approximation with `controlled Markov' noise
• Simultaneous perturbation Newton algorithms for simulation optimization
• Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem
• A generalization of the Borkar-Meyn theorem for stochastic recursive inclusions
• Stochastic recursive inclusions with non-additive iterate-dependent Markov noise

Cited In (5)

• Constant step stochastic approximations involving differential inclusions: stability, long-run convergence and applications
• Stochastic recursive inclusions with non-additive iterate-dependent Markov noise
• A Recurrence Principle for Stochastic Difference Inclusions
• Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem
• Full gradient DQN reinforcement learning: a provably convergent scheme

This page was built for publication: Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise

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