$O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation

1. Problem Formulation

The paper addresses the finite-time convergence analysis of Two-Time-Scale Stochastic Approximation (SA) algorithms in a non-linear setting. The goal is to find the fixed points $(x^*, y^*)$ of a system of coupled iterations:

$$\begin{aligned} x_{k+1} &= x_k + \alpha_k (f(x_k, y_k) - x_k + M_{k+1}) \\ y_{k+1} &= y_k + \beta_k (g(x_k, y_k) - y_k + M'_{k+1}) \end{aligned}$$

Where:

• $x_k$ and $y_k$ are iterates updated on fast and slow time-scales, respectively.
• $\alpha_k$ and $\beta_k$ are step sizes, with $\beta_k$ decaying faster than $\alpha_k$.
• $f$ and $g$ are non-linear Lipschitz functions.
• $M_{k+1}$ and $M'_{k+1}$ represent martingale difference noise (which can be multiplicative, scaling with the iterates).

Core Assumptions:

1. Contractivity: $f(\cdot, y)$ is $\lambda$-contractive in $x$, and $g(x^*(y), \cdot)$ is $\mu$-contractive in $y$ (where $x^*(y)$ is the fixed point of $f$ for a given $y$).
2. Lipschitz Continuity: Both $f$ and $g$ are Lipschitz continuous.
3. Noise: The noise sequences are martingale differences with second moments scaling affinely with the squared norm of the iterates.

The objective is to derive Mean Squared Error (MSE) bounds of the form $E[\|x_k - x^*\|^2 + \|y_k - y^*\|^2]$.

2. Methodology

The paper introduces a novel proof technique to overcome the limitations of previous analyses, which struggled to achieve optimal rates in non-linear settings due to the handling of noise in the slower time-scale.

Key Innovation: Averaged Noise and Auxiliary Iterates

The central difficulty in non-linear two-time-scale SA is that the noise $M'_{k+1}$ in the slow iteration ($y_k$) has constant variance, which hinders the derivation of tight $O(1/k)$ bounds. The author proposes:

1. Averaged Noise Sequence ($U_k$): Define a new sequence $U_{k+1} = (1-\beta_k)U_k + \beta_k M'_{k+1}$ (with $U_0=0$). This sequence effectively averages the noise, causing its variance to decay over time.
2. Auxiliary Iterates ($z_k$): Define a modified iterate $z_k = y_k - U_k$.

By rewriting the original system in terms of $x_k$ and $z_k$, the noise term in the $z_k$ iteration becomes the difference between the original noise and the averaged noise. Crucially, the variance of this new effective noise sequence decays sufficiently fast. This transformation allows the authors to treat the system similarly to a single-time-scale problem with decaying noise, facilitating tighter bounds.

Proof Strategy

• Induction on Boundedness: The authors use an induction-based approach to prove that the iterates remain bounded in expectation ($E[\|x_k\|^2 + \|y_k\|^2] < \infty$). This is necessary because the noise variance depends on the magnitude of the iterates.
• Recursive Bounds: They derive recursive inequalities for the error terms $E[\|x_k - x^*(z_k)\|^2]$ and $E[\|z_k - y^*\|^2]$.
• Decoupling: The analysis separates the fast and slow dynamics by leveraging the contractive properties and the decay of the averaged noise variance.

3. Key Contributions

The paper makes two primary contributions, improving upon the state-of-the-art in two distinct settings:

A. Single Time-Scale with Coupled Sequences ($\alpha_k, \beta_k \sim \Theta(1/k)$)

• Context: Both stepsizes decay at the same rate ($1/k$), but the ratio $\beta_k/\alpha_k \to \gamma < 1$ ensures time-scale separation.
• Previous Best: An $O(1/k)$ bound existed but required the strong assumption that the fixed point mapping $x^*(y)$ is smooth (differentiable).
• New Result: The paper achieves the first $O(1/k)$ bound without assuming smoothness of $x^*(y)$. It relies only on the standard contractive and Lipschitz assumptions.

B. True Two-Time-Scale Separation ($\beta_k \ll \alpha_k$)

• Context: The stepsizes are chosen such that $\lim_{k \to \infty} \beta_k/\alpha_k = 0$. Specifically, $\beta_k = O(1/k)$ and $\alpha_k = O(1/k^a)$ for $a \in (0.5, 1)$.
• Previous Best: The best known bound was $O(1/k^{2/3})$ (from [15]), achieved with specific stepsize choices.
• New Result: The paper improves this to $O(1/k^a)$ for any $a < 1$. By choosing $\alpha_k = O(1/k^a)$, the convergence rate approaches the optimal $O(1/k)$ arbitrarily closely.
• Significance: This result holds for multiplicative martingale noise (where noise scales with iterates), a more general and challenging setting than the additive noise considered in prior works.

4. Main Results (Theorems)

• Theorem 1: Under Assumptions 1-4 and stepsizes $\alpha_k, \beta_k = \Theta(1/k)$, the MSE converges as:
  $$E[\|x_k - x^*\|^2 + \|y_k - y^*\|^2] \leq \frac{C}{k}$$
  This holds without additional smoothness assumptions on the fixed point map.

• Theorem 2: Under Assumptions 1-4 and stepsizes $\beta_k = O(1/k)$, $\alpha_k = O(1/k^a)$ with $a \in (0.5, 1)$, the MSE converges as:
  $$E[\|x_k - x^*\|^2 + \|y_k - y^*\|^2] \leq \frac{D}{k^a}$$
  This significantly improves upon the $O(1/k^{2/3})$ bound of previous literature.

5. Significance and Applications

• Theoretical Advancement: The work bridges a gap between linear and non-linear SA analysis. It demonstrates that the optimal $O(1/k)$ rate (or near-optimal) is achievable in non-linear settings without relying on local linearity or smoothness of the fixed-point map, which are often unrealistic in complex RL and optimization problems.
• Robustness: The ability to handle multiplicative noise makes the results applicable to algorithms where noise magnitude depends on the state (e.g., off-policy learning in RL).
• Practical Relevance: The results apply to a wide range of algorithms, including:
  • Reinforcement Learning: Actor-Critic algorithms, SSP Q-learning, TDC, and GTD2.
  • Optimization: Gradient Descent-Ascent (for minimax problems), Polyak averaging, and constrained optimization via Lagrangian methods.
• Proof Technique: The "averaged noise" technique is a powerful new tool for analyzing stochastic iterations. It simplifies the analysis by transforming a system with constant variance noise into one with decaying variance, potentially applicable to other stochastic approximation problems.

Conclusion

Siddharth Chandak's paper establishes that non-linear two-time-scale stochastic approximation can achieve near-optimal finite-time convergence rates ($O(1/k)$ or $O(1/k^{1-\epsilon})$) under standard contractive assumptions. By introducing an auxiliary iterate and an averaged noise sequence, the author overcomes the analytical barriers that previously limited convergence rates to $O(1/k^{2/3})$ or required restrictive smoothness assumptions. This provides a stronger theoretical foundation for the use of two-time-scale algorithms in modern reinforcement learning and optimization.