Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation
This work provides theoretical guarantees for a class of algorithms used in reinforcement learning and optimization, offering insights into error decomposition for practitioners, though it is incremental in extending existing analysis to projected settings.
The paper tackles the finite-time convergence analysis of projected linear two-time-scale stochastic approximation with constant step sizes and Polyak-Ruppert averaging, establishing an explicit mean-square error bound that decomposes into approximation and statistical error components, as validated through numerical experiments on synthetic and reinforcement learning problems.
We study the finite-time convergence of projected linear two-time-scale stochastic approximation with constant step sizes and Polyak--Ruppert averaging. We establish an explicit mean-square error bound, decomposing it into two interpretable components, an approximation error determined by the constrained subspace and a statistical error decaying at a sublinear rate, with constants expressed through restricted stability margins and a coupling invertibility condition. These constants cleanly separate the effect of subspace choice (approximation errors) from the effect of the averaging horizon (statistical errors). We illustrate our theoretical results through a number of numerical experiments on both synthetic and reinforcement learning problems.