Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

1. Problem Statement

The paper addresses the convergence analysis of Projected Two-Time-Scale Stochastic Approximation (TTSA) algorithms operating with constant step sizes and Polyak–Ruppert (PR) averaging.

• Context: TTSA is a fundamental method for solving coupled root-finding problems where two variables, $x$ (fast) and $y$ (slow), are updated at different rates. It is widely used in Actor-Critic reinforcement learning (RL), Gradient Temporal-Difference (GTD) methods, and bilevel optimization.
• The Challenge: In high-dimensional settings (e.g., large state spaces in RL), direct computation is infeasible. Variables must be restricted to low-dimensional linear subspaces ($\mathcal{X}, \mathcal{Y}$) via projection.
• The Gap: While asymptotic convergence of TTSA is well-understood, there is a lack of finite-time analysis for the projected variant with constant step sizes. Existing literature often focuses on decaying step sizes or single-time-scale settings. Crucially, there is no explicit decomposition of the error into approximation bias (due to subspace restriction) and statistical variance (due to noise) for this specific setting.

2. Methodology

The authors analyze the iterates generated by the projected update rule:
$$\begin{aligned} x_{t+1} &= \Pi_{\mathcal{X}} [x_t + \alpha(g(x_t, y_t) + \epsilon_t)] \\ y_{t+1} &= \Pi_{\mathcal{Y}} [y_t + \beta(h(x_t, y_t) + \psi_t)] \end{aligned}$$
where $\Pi$ denotes orthogonal projection onto linear subspaces, $\alpha \gg \beta$ are constant step sizes, and $\epsilon, \psi$ are martingale difference noise.

Key Analytical Techniques:

1. Polyak–Ruppert Averaging: Instead of analyzing the final iterate, the paper studies the average of the iterates $\bar{x}_T = \frac{1}{T}\sum x_t$ and $\bar{y}_T = \frac{1}{T}\sum y_t$. This technique is known to improve statistical efficiency, achieving an $O(1/T)$ convergence rate.
2. Bias-Variance Decomposition: The authors decompose the Mean Squared Error (MSE) into two distinct components:
   • Approximation Error: The irreducible distance between the true unconstrained solution $(x^*, y^*)$ and the constrained solution $(x^*_p, y^*_p)$ that lies within the subspaces.
   • Statistical Error: The error arising from the noise in the samples, which decays as the number of iterations $T$ increases.
3. Telescoping Sums & Linear Algebra: The proof utilizes telescoping identities derived from the constant step sizes. By defining instantaneous constrained solutions and utilizing the linearity of the projection operators, the authors invert the projected system matrices to bound the error terms explicitly.
4. Restricted Stability Margins: The analysis introduces constants based on the "restricted" stability of the system matrices projected onto the subspaces (e.g., $\mu_x, \mu_y$) and coupling invertibility conditions ($\kappa_{xy}, \kappa_{yx}$).

3. Key Contributions

• Explicit Finite-Time Bound: The paper establishes the first explicit non-asymptotic MSE bound for projected TTSA with constant step sizes and PR averaging.
• Clean Error Decomposition: The bound is rigorously decomposed into:
  $$\mathbb{E}[\|\bar{x}_T - x^*\|^2] \leq \underbrace{2B_{xx}\epsilon_x^2 + 2B_{xy}\epsilon_y^2}_{\text{Approximation Error}} + \underbrace{\frac{2L_x}{T}}_{\text{Statistical Error}}$$
  where $\epsilon_x^2$ and $\epsilon_y^2$ are the distances from the true solution to the subspaces.
• Interpretable Constants: The constants in the bound ($B$ for approximation, $L$ for statistics) are expressed in terms of:
  • Restricted Stability Margins: How well the system behaves when confined to the subspace.
  • Coupling Invertibility: How the fast and slow variables interact within the subspace.
  • Noise Variances: The magnitude of the sampling noise.
• Separation of Effects: The analysis clearly separates the impact of subspace choice (which determines the approximation floor) from the averaging horizon (which determines the statistical decay rate).

4. Main Results

Theorem 1 states that under standard assumptions (Hurwitz stability of the system and projected matrices, bounded noise variance), the PR-averaged iterates satisfy:
$$\mathbb{E}[\|\bar{x}_T - x^*\|^2] \leq C_{approx} + \frac{C_{stat}}{T}$$

• Convergence Rate: The statistical error decays at a rate of $O(1/T)$, which is optimal for stochastic approximation with constant step sizes.
• Approximation Floor: The error does not converge to zero but plateaus at a level determined by the subspace approximation error ($\epsilon_x^2, \epsilon_y^2$).
• Cross-Coupling Effects: The error in the slow variable ($y$) depends on the approximation error of the fast variable ($x$) and vice versa, mediated by the coupling constants.
• Robustness: The $O(1/T)$ rate holds regardless of the subspace choice, though the constant factor $L$ depends on the subspace stability.

5. Numerical Experiments

The authors validate their theory using two scenarios:

1. Synthetic Coupled Linear Systems: A controlled environment where the ground truth and subspaces are known. The results show the PR error decaying and plateauing exactly at the predicted approximation error floor, with the decay rate matching $O(1/T)$.
2. GTD in Reinforcement Learning: Applied to policy evaluation with linear function approximation.
   • They tested feature subspaces with varying alignment to the true value function (well-aligned, random, and poorly-aligned).
   • Findings:
     • Well-aligned features yielded the lowest approximation error (lowest plateau).
     • Poorly-aligned features resulted in a higher plateau but maintained the same $O(1/T)$ decay rate for the statistical error.
     • This confirms that while feature selection controls the bias (approximation error), the variance reduction rate is robust across different subspace choices.

6. Significance

• Theoretical Foundation: This work bridges a critical gap between asymptotic TTSA theory and practical finite-time performance, specifically for constrained settings common in modern machine learning.
• Practical Guidance for Subspace Selection: The results provide a quantitative framework for the "bias-variance tradeoff" in subspace selection. Practitioners can now understand that choosing a subspace reduces dimensionality (and variance) but introduces a bias floor; the $O(1/T)$ rate ensures that statistical noise can be driven down efficiently regardless of the subspace, provided the system is stable.
• Algorithm Design: The analysis supports the use of constant step sizes combined with Polyak–Ruppert averaging as a computationally efficient strategy for large-scale RL and optimization problems, offering better finite-time guarantees than decaying step-size schedules in many contexts.