# Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis

arXiv: https://arxiv.org/abs/2501.10806 · HTML: https://mlsanity.com/paper/2501.10806/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 18 Jan 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 17 of 17)

- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Convergence rate analysis of several splitting schemes](https://mlsanity.com/paper/1406.4834/) (2014)
- [Convergence Rates with Inexact Non-expansive Operators](https://mlsanity.com/paper/1404.4837/) (2014)
- [Efficient Projection-Free Algorithms for Saddle Point Problems](https://mlsanity.com/paper/2010.11737/) (2020)
- [Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces](https://mlsanity.com/paper/1705.09340/) (2017)
- [Inertial Krasnoselskii-Mann Iterations](https://mlsanity.com/paper/2210.03791/) (2022)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)

## Built on by (most cited first, 3 of 3)

- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration](https://mlsanity.com/paper/2607.13414/) (2026)

## Abstract (arXiv)

Two-time-scale stochastic approximation algorithms are iterative methods used in applications such as optimization, reinforcement learning, and control. Finite-time analysis of these algorithms has primarily focused on fixed point iterations where both time-scales have contractive mappings. In this work, we broaden the scope of such analyses by considering settings where the slower time-scale has a non-expansive mapping. For such algorithms, the slower time-scale can be viewed as a stochastic inexact Krasnoselskii-Mann iteration. We also study a variant where the faster time-scale has a projection step which leads to non-expansiveness in the slower time-scale. We show that the last-iterate mean square residual error for such algorithms decays at a rate O(1/k1/4-ε), where ε>0 is arbitrarily small. We further establish almost sure convergence of iterates to the set of fixed points. We demonstrate the applicability of our framework by applying our results to minimax optimization, linear stochastic approximation, and Lagrangian optimization.