# Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2024.

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

- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)
- [Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way](https://mlsanity.com/paper/2410.13067/) (2024)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications](https://mlsanity.com/paper/2410.13743/) (2024)
- [Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis](https://mlsanity.com/paper/2509.15392/) (2025)
- [Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence](https://mlsanity.com/paper/2509.11039/) (2025)
- [Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It](https://mlsanity.com/paper/2606.14488/) (2026)
- [ABC-Align: Prediction-Powered Alignment with Adaptive Bias Control](https://mlsanity.com/paper/2609.34374/) (2026)

## Abstract (arXiv)

In two-time-scale stochastic approximation (SA), two iterates are updated at varying speeds using different step sizes, with each update influencing the other. Previous studies on linear two-time-scale SA have shown that the convergence rates of the mean-square errors for these updates depend solely on their respective step sizes, a phenomenon termed decoupled convergence. However, achieving decoupled convergence in nonlinear SA remains less understood. Our research investigates the potential for finite-time decoupled convergence in nonlinear two-time-scale SA. We demonstrate that, under a nested local linearity assumption, finite-time decoupled convergence rates can be achieved with suitable step size selection. To derive this result, we conduct a convergence analysis of the matrix cross term between the iterates and leverage fourth-order moment convergence rates to control the higher-order error terms induced by local linearity. To further investigate the necessity of local linearity for decoupled convergence, we also construct an example showing that, even when the fast-time-scale update is linear, the nonlinearity of the slow-time-scale update alone can destroy decoupled convergence.