Stochastic Recursive Inclusions in two timescales with non-additive iterate dependent Markov noise
For researchers in stochastic approximation and optimization, this provides a more general theoretical foundation for two-timescale algorithms under Markov noise, though the contribution is incremental as it builds on prior work.
This paper extends the theory of two-timescale stochastic approximation to include set-valued drift functions and non-additive iterate-dependent Markov noise, proving that each timescale tracks a differential inclusion. The framework is applied to constrained convex optimization with Markov-averaged objectives, requiring neither differentiability nor knowledge of the averaging measure.
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. }\rm 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.