O ( 1 / k ) O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation
Siddharth Chandak · 2025
Read O ( 1 / k ) O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation by Siddharth Chandak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19375.txt.
Introduction
Siddharth Chandak sharpens the speed guarantees for a workhorse learning algorithm, in a 2025 paper. Two-time-scale stochastic approximation runs two coupled updates at different speeds, a pattern behind many reinforcement learning and control methods. Chandak derives mean squared error bounds for the nonlinear version with contractive mappings. When both steps shrink at the same rate, the error falls as one over the step count, the first such result without extra smoothness demands.
With true time-scale separation, the previous best rate is improved to nearly the same speed. The proof rewrites the iteration around an averaged noise sequence whose variance decays fast enough. Rates like these tell practitioners how long an algorithm must run before its answers can be trusted.
Catalog record
| CREATOR | Siddharth Chandak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19375
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
O ( 1 / k ) O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation Siddharth Chandak Abstract Two-time-scale stochastic approximation (SA) is an algorithm with coupled iterations which has found broad applications in reinforcement learning, optimization and game control. In this work, we derive mean squared error bounds for non-linear two-time-scale iterations with contractive mappings. In the setting where both stepsizes are order Θ ( 1 / k ) \Theta(1/k) , commonly referred to as single time-scale SA with multiple coupled sequences, we obtain the first 𝒪 ( 1 / k ) \mathcal{O}(1/k) rate without imposing additional smoothness assumptions. In the setting with true time-scale separation, the previous best bound was 𝒪 ( 1 / k 2 / 3 ) \mathcal{O}(1/k^{2/3}) . We improve this to 𝒪 ( 1 / k a ) \mathcal{O}(1/k^{a}) for any a < 1 a<1 approaching the optimal 𝒪 ( 1 / k ) \mathcal{O}(1/k) rate. The key step in our analysis involves rewriting the original iteration in terms of an averaged noise sequence whose variance decays sufficiently fast. Additionally, we use an induction-based approach to show that the iterates are bounded in expectation. Our results apply to Polyak averaging, as well as to algorithms from reinforcement learning, and optimization, including gradient descent-ascent and two-time-scale Lagrangian optimization. Keywords: stochastic approximation, two-time-scale stochastic approximation, finite-time bound, optimization, reinforcement learning. 1 Introduction Stochastic Approximation (SA) is a popular class of iterative algorithms used in finding the fixed point of an operator given its noisy realizations [ 1 ] . These algorithms have been widely studied in the past few decades due to their applications in fields such as reinforcement learning, optimization, communication networks, and stochastic control [ 2 ] . Two-time-scale SA is a variant of SA where the fixed points for two coupled operators are found using two iterations with different rates of update. These coupled iterations have been used in various fields including reinforcement learning (RL) and optimization. For example, SSP Q-learning [ 3 ] is a two-time-scale algorithm for control of average reward MDPs. Actor-critic algorithms are another example where the ‘actor’ and the ‘critic’ update at different rates [ 4 ] . Gradient descent-ascent algorithm for learning saddle points [ 5 ] is an example of two-time-scale SA in optimization. Game control algorithms can often be modeled using two time-scales, as the players update their actions on a faster time-scale and the manager updates the game parameters on a slower time-scale [ 6 ] . Consider the following coupled iterations. \displaystyle x_{k+1}=x_{k}+\alpha_{k}(f(x_{k},y_{k})-x_{k}+M_{k+1}) \displaystyle y_{k+1}=y_{k}+\beta_{k}(g(x_{k},y_{k})-y_{k}+M^{\prime}_{k+1}). Here x_{k}\in\mathbb{R}^{d_{1}} and y_{k}\in\mathbb{R}^{d_{2}} are the iterates updated on the faster and slower time-scale, respectively. These time-scales are dictated by the stepsizes \alpha_{k} and \beta_{k} , respectively, where \beta_{k} decays faster than \alpha_{k} . Here, f(\cdot) and g(\cdot) are the non-linear Lipschitz functions whose fixed points we aim to obtain. M_{k+1} and M^{\prime}_{k+1} denote additive and multiplicative martingale noise. The objective of the algorithm is to find solutions to f(x^{*},y^{*})=x^{*} and g(x^{*},y^{*})=y^{*} . We assume that operators f(x,y) and g(x^{*}(y),y) are contractive with respect to x and y , respectively. Here, x^{*}(y) is the fixed point for f(\cdot,y) . This assumption is sufficient to ensure uniqueness of (x^{*},y^{*}) and asymptotic convergence of the iterates to the fixed points. Such an assumption is standard in the literature on finite-time analysis of SA algorithms and is satisfied by a wide range of RL and optimization algorithms [ 7 , 8 , 9 ] . While classical analysis of SA schemes has focused on asymptotic analysis [ 10 , 2 ] , there has been a recent interest in obtaining finite-time guarantees on performance of these algorithms. These finite-time guarantees can also be broadly divided into two types: high probability or concentration bounds (e.g., [ 11 , 12 ] ) and mean square error bounds (e.g., [ 13 , 14 , 15 ] ). We focus on the latter in this paper. 1.1 Main Contributions Our aim in this paper is to obtain mean square error bounds for non-linear two-time-scale SA, i.e., obtain bounds on \mathbb{E}\left[\|x_{k}-x^{*}\|^{2}+\|y_{k}-y^{*}\|^{2}\right] where \|\cdot\| denotes the Euclidean norm. The existing results on such bounds can be broadly classified into two categories. We next describe these categories, and how we improve on the existing results. 1. Single time-scale SA with multiple coupled sequences: This is the setting where \beta_{k} and \alpha_{k} are both of the order \Theta(1/k) . In this setting, the time-scale separation is decided by \lim_{k\uparrow\infty}\beta_{k}/\alpha_{k}=\gamma<1 . A bound of \mathcal{O}(1/k) was obtained in [ 16 ] but they assumed smoothness of the operator x^{*}(y) . We obtain the first \mathcal{O}(1/k) bound in this setting without any additional assumptions (Theorem 1 ). 2. ‘True’ two-time-scale SA: This is the setting where \lim_{k\uparrow\infty}\beta_{k}/\alpha_{k}=0 , i.e., the two-time-scales are truly separated. The previous best known bound in this setting was \mathcal{O}(1/k^{2/3}) obtained for stepsizes of the form \beta_{k}=1/k and \alpha_{k}=1/k^{2/3} [ 15 ] . We significantly improve this bound to \mathcal{O}(1/k^{\mathfrak{a}}) obtained when stepsizes are of the form \alpha_{k}=\mathcal{O}(1/k^{\mathfrak{a}}) and \beta_{k}=\mathcal{O}(1/k) . Here \mathfrak{a} can be arbitrarily close to 1 (Theorem 2 ). An advantage of this setting is that the stepsize sequences can be chosen independently of system parameters. This allows for a more robust bound, while still achieving a bound of \mathcal{O}(1/k^{\mathfrak{a}}) where \mathfrak{a} can be arbitrarily close to one. We identify that the reason for a bound of \mathcal{O}(1/k^{2/3}) in [ 15 ] was the manner in which M^{\prime}_{k+1} , the martingale noise in the slower time-scale iteration, was handled. In fact, in [ 17 ] , a bound of \mathcal{O}(1/k) is obtained for a special case where the slower time-scale is noiseless. In this work, we introduce an averaged noise sequence and auxiliary iterates for the slower time-scale. The key intuition behind introducing these is to transform the original iteration into one in which the noise sequence has a decaying variance, instead of the constant variance as in the original iteration. We emphasize that analyzing this averaged noise sequence is just a proof technique. Neither does our algorithm have an additional averaging step, nor do we give bounds on averaged iterates. Concretely, we introduce the averaged noise sequence U_{k+1}=\beta_{k}M^{\prime}_{k+1}+(1-\beta_{k})U_{k} (with U_{0}=0 ) and define the iterates z_{k}=y_{k}-U_{k} . We analyze the iterations for x_{k} and z_{k} , obtaining a bound of \mathcal{O}(1/k) on \mathbb{E}\left[\|z_{k}-y^{*}\|^{2}\right] . Moreover, we show that \mathbb{E}\left[\|y_{k}-z_{k}\|^{2}\right] decays at a rate of \mathcal{O}(1/k) . This allows us to obtain a rate of \mathcal{O}(1/k) on the mean square error. 1.2 Outline and Notation This paper is structured as follows: Section 2 sets up the problem and gives examples of algorithms that fit into our framework. Section 3 presents the main results of this paper after defining the stepsize sequences. Section 4 contains a proof sketch for our main results. Section 5 concludes the paper and presents some future directions. Throughout this work, \|\cdot\| denotes the Euclidean norm, and \langle x_{1},x_{2}\rangle denotes the inner product given by x_{1}^{T}x_{2} . 1.3 Related Works Finite-time bounds for two-time-scale SA have primarily focused on the linear case, i.e., where the functions f(\cdot) and g(\cdot) are linear. In [ 18 ] , an asymptotic rate of \mathcal{O}(1/k) is obtained. This has been