Decoupled Functional Central Limit Theorems for Two-Timescale Stochastic Approximation

References

• [1] Antsaklis PJ, Michel AN (2005) Linear Systems, 2nd ed. (Birkhäuser/Springer Science & Business Media, Boston).Google Scholar
• [2] Bach F, Moulines E (2011) Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Technical report hal-00608041, HAL. Accessed July 22, 2026, https://hal.science/hal-00608041v1/document.Google Scholar
• [3] Benveniste A, Métivier M, Priouret P (2012) Adaptive Algorithms and Stochastic Approximations, vol. 22 (Springer Science & Business Media, Berlin).Google Scholar
• [4] Billingsley P (2013) Convergence of Probability Measures (John Wiley & Sons, New York).Google Scholar
• [5] Blanchet J, Mijatović A, Yang W (2024) Limit theorems for stochastic gradient descent with infinite variance. Preprint, submitted October 21, https://arxiv.org/abs/2410.16340.Google Scholar
• [6] Borkar V (1997) Stochastic approximation with two time scales. Systems Control Lett. 29(5):291–294.Crossref, Google Scholar
• [7] Borkar V (2009) Stochastic Approximation: A Dynamical Systems Viewpoint, vol. 48 (Hindustan Book Agency, Gurgaon, India).Google Scholar
• [8] Borkar V, Konda VR (1997) The actor-critic algorithm as multi-time-scale stochastic approximation. Sadhana 22:525–543.Crossref, Google Scholar
• [9] Borkar V, Chen S, Devraj A, Kontoyiannis I, Meyn S (2025) The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. Ann. Appl. Probab. 35(2):936–982.Crossref, Google Scholar
• [10] Chandak S (2025) Non-expansive mappings in two-time-scale stochastic approximation: Finite-time analysis. Preprint, submitted January 18, https://arxiv.org/abs/2501.10806.Google Scholar
• [11] Chao SK, Cheng G (2019) A generalization of regularized dual averaging and its dynamics. Preprint, submitted September 22, https://arxiv.org/abs/1909.10072.Google Scholar
• [12] Chen T, Sun Y, Yin W (2021) Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Red Hook, NY), 25294–25307.Google Scholar
• [13] Chen X, Lai Z, Li H, Zhang Y (2024) Online statistical inference for stochastic optimization via Kiefer-Wolfowitz methods. J. Amer. Statist. Assoc. 119(548):2972–2982.Crossref, Google Scholar
• [14] Dalal G, Szorenyi B, Thoppe G (2020) A tale of two-timescale reinforcement learning with the tightest finite-time bound. Conitzer V, Sha F, eds. Proc. AAAI Conf. Artificial Intelligence, vol. 34 (AAAI Press, Palo Alto, CA), 3701–3708.Crossref, Google Scholar
• [15] Dalal G, Thoppe G, Szörényi B, Mannor S (2018) Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. Bubeck S, Perchet V, Rigollet P, eds. Conf. Learn. Theory, vol. 75 (PMLR, New York), 1199–1233.Google Scholar
• [16] Dann C, Neumann G, Peters J (2014) Policy evaluation with temporal differences: A survey and comparison. J. Machine Learn. Res. 15(24):809–883.Google Scholar
• [17] Doan TT (2022) Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. IEEE Trans. Automatic Control 68(8):4695–4705.Crossref, Google Scholar
• [18] Ethier SN, Kurtz TG (2009) Markov Processes: Characterization and Convergence (John Wiley & Sons, New York).Google Scholar
• [19] Faizal FZ, Borkar V (2023) Functional central limit theorem for two timescale stochastic approximation. Preprint, submitted June 9, https://arxiv.org/abs/2306.05723.Google Scholar
• [20] Gadat S (2017) Stochastic optimization algorithms, non asymptotic and asymptotic behaviour. Lecture notes for M2RI UT3, S10, Toulouse School of Economics, Université Toulouse I Capitole, Toulouse, France, https://perso.math.univ-toulouse.fr/gadat/files/2012/12/cours_Algo_Stos_M2R3.pdf.Google Scholar
• [21] Gadat S, Panloup F, Saadane S (2018) Stochastic heavy ball. Electronic J. Statist. 12(1):461–529.Crossref, Google Scholar
• [22] Ghadimi S, Wang M (2018) Approximation methods for bilevel programming. Preprint, submitted February 6, https://arxiv.org/abs/1802.02246.Google Scholar
• [23] Ghiassian S, Patterson A, Garg S, Gupta D, White A, White M (2020) Gradient temporal-difference learning with regularized corrections. Daumé III H, Singh A, eds. Internat. Conf. Machine Learn., vol. 119 (PMLR, New York), 3524–3534.Google Scholar
• [24] Gitman I, Lang H, Zhang P, Xiao L (2019) Understanding the role of momentum in stochastic gradient methods. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 9630–9640.Google Scholar
• [25] Gupal AM, Bazhenov LT (1972) A stochastic analog of the conjugate gradient method. Cybernetics 8:138–140.Crossref, Google Scholar
• [26] Han Y, Li X, Zhang Z (2026) Finite-time decoupled convergence in nonlinear two-time-scale stochastic approximation. J. Machine Learn. Res. 27(112):1–69.Google Scholar
• [27] Haque SU, Maguluri ST (2025) Stochastic approximation with unbounded Markovian noise: A general-purpose theorem. Li Y, Mandt S, Agrawal S, Khan E, eds. Internat. Conf. Artificial Intelligence Statist., vol. 258 (PMLR, New York), 3718–3726.Google Scholar
• [28] Haque SU, Khodadadian S, Maguluri ST (2023) Tight finite time bounds of two-time-scale linear stochastic approximation with Markovian noise. Preprint, submitted December 31, https://arxiv.org/abs/2401.00364.Google Scholar
• [29] Hong M, Wai HT, Wang Z, Yang Z (2023) A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM J. Optim. 33(1):147–180.Crossref, Google Scholar
• [30] Howard SR, Ramdas A, McAuliffe J, Sekhon J (2021) Time-uniform, nonparametric, nonasymptotic confidence sequences. Ann. Statist. 49(2):1055–1080.Crossref, Google Scholar
• [31] Hu J, Doshi V, Eun DY (2024) Central limit theorem for two-timescale stochastic approximation with Markovian noise: Theory and applications. Dasgupta S, Mandt S, Li Y, eds. Internat. Conf. Artificial Intelligence Statist., vol. 238 (PMLR, New York), 1477–1485.Google Scholar
• [32] Johari R, Koomen P, Pekelis L, Walsh D (2017) Peeking at A/B tests: Why it matters, and what to do about it. Matwin S, Yu S, Farooq F, eds. Proc. 23rd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 1517–1525.Google Scholar
• [33] Kaledin M, Moulines E, Naumov A, Tadic V, Wai HT (2020) Finite time analysis of linear two-timescale stochastic approximation with Markovian noise. Abernethy J, Agarwal S, eds. Conf. Learn. Theory, vol. 125 (PMLR, New York), 2144–2203.Google Scholar
• [34] Karmakar P, Bhatnagar S (2018) Two time-scale stochastic approximation with controlled Markov noise and off-policy temporal-difference learning. Math. Oper. Res. 43(1):130–151.Link, Google Scholar
• [35] Khasminskii R, Yin G (2005) Limit behavior of two-time-scale diffusions revisited. J. Differential Equations 212(1):85–113.Crossref, Google Scholar
• [36] Khasminskij RZ (1968) On the principle of averaging the Itov’s stochastic differential equations. Kybernetika 4:260–279.Google Scholar
• [37] Kidambi R, Netrapalli P, Jain P, Kakade S (2018) On the insufficiency of existing momentum schemes for stochastic optimization. 2018 Inform. Theory Appl. Workshop (IEEE, Piscataway, NJ), 1–9.Google Scholar
• [38] Kingma DP, Ba J (2015) Adam: A method for stochastic optimization. Internat. Conf. Learn. Representations (ICLR, San Diego, CA).Google Scholar
• [39] Kokotović PV (1984) Applications of singular perturbation techniques to control problems. SIAM Rev. 26(4):501–550.Crossref, Google Scholar
• [40] Konda VR, Tsitsiklis JN (2003) On actor-critic algorithms. SIAM J. Control Optim. 42(4):1143–1166.Crossref, Google Scholar
• [41] Konda VR, Tsitsiklis JN (2004) Convergence rate of linear two-time-scale stochastic approximation. Ann. Appl. Probab. 14(2):796–819.Crossref, Google Scholar
• [42] Kushner H (1988) Almost optimal controls for wideband noise driven systems. Fleming W, Lions PL, eds. Stochastic Differential Systems, Stochastic Control Theory and Applications (Springer, New York), 255–273.Crossref, Google Scholar
• [43] Kushner H, Yang J (1993) Stochastic approximation with averaging of the iterates: Optimal asymptotic rate of convergence for general processes. SIAM J. Control Optim. 31(4):1045–1062.Crossref, Google Scholar
• [44] Kushner H, Yin GG (2003) Stochastic Approximation and Recursive Algorithms and Applications, vol. 35 (Springer, New York).Google Scholar
• [45] Kwon J, Dotson L, Chen Y, Xie Q (2024) Two-timescale linear stochastic approximation: Constant stepsizes go a long way. Preprint, submitted October 16, https://arxiv.org/abs/2410.13067.Google Scholar
• [46] Lee S, Liao Y, Seo MH, Shin Y (2022) Fast and robust online inference with stochastic gradient descent via random scaling. Sycara K, Honavar V, Spaan MTJ, eds. AAAI Conf. Artificial Intelligence, vol. 36 (AAAI Press, Palo Alto, CA), 7381–7389.Google Scholar
• [47] Lee S, Liao Y, Seo MH, Shin Y (2025) Fast inference for quantile regression with tens of millions of observations. J. Econometrics 249:105673.Crossref, Google Scholar
• [48] Li R, Lin DK, Li B (2013) Statistical inference in massive data sets. Appl. Stochastic Models Bus. Indust. 29(5):399–409.Crossref, Google Scholar
• [49] Li X, Liang J, Zhang Z (2023) Online statistical inference for nonlinear stochastic approximation with Markovian data. Preprint, submitted February 15, https://arxiv.org/abs/2302.07690.Google Scholar
• [50] Li X, Liang J, Chang X, Zhang Z (2022) Statistical estimation and online inference via local SGD. Conf. Learn. Theory (PMLR), 1613–1661.Google Scholar
• [51] Li X, Liang J, Chen X, Zhang Z (2026) Convergence and inference of stream stochastic gradient descent, with applications to queueing systems and inventory control. Oper. Res., ePub ahead of print January 28, https://doi.org/10.1287/opre.2025.1662.Google Scholar
• [52] Li X, Yang W, Liang J, Zhang Z, Jordan MI (2023) A statistical analysis of Polyak-Ruppert averaged Q-learning. Internat. Conf. Artificial Intelligence Statist., vol. 206.Google Scholar
• [53] Li G, Wu W, Chi Y, Ma C, Rinaldo A, Wei Y (2024) High-probability sample complexities for policy evaluation with linear function approximation. IEEE Trans. Inform. Theory 70(8):5969–5999.Crossref, Google Scholar
• [54] Liang J, Han Y, Li X, Zhang Z (2023) Asymptotic behaviors and phase transitions in projected stochastic approximation: A jump diffusion approach. Preprint, submitted April 25, https://arxiv.org/abs/2304.12953.Google Scholar
• [55] Liu T, Chen Z, Zhou E, Zhao T (2021) A diffusion approximation theory of momentum stochastic gradient descent in nonconvex optimization. Stochastic Systems 11(4):307–323.Link, Google Scholar
• [56] Ma J, Yarats D (2019) Quasi-hyperbolic momentum and Adam for deep learning. Internat. Conf. Learn. Representations (ICLR, New Orleans, LA).Google Scholar
• [57] Maei H, Szepesvari C, Bhatnagar S, Precup D, Silver D, Sutton RS (2009) Convergent temporal-difference learning with arbitrary smooth function approximation. Bengio Y, Schuurmans D, Lafferty JD, Williams CKI, Culotta A, eds. Adv. Neural Inform. Processing Systems, vol. 22 (Curran Associates, Red Hook, NY), 1204–1212.Google Scholar
• [58] Mokkadem A, Pelletier M (2006) Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms. Ann. Appl. Probab. 16(3):1671–1702.Crossref, Google Scholar
• [59] Mou W, Pananjady A, Wainwright MJ (2023) Optimal oracle inequalities for projected fixed-point equations, with applications to policy evaluation. Math. Oper. Res. 48(4):2308–2336.Abstract, Google Scholar
• [60] Mou W, Khamaru K, Wainwright MJ, Bartlett PL, Jordan MI (2022) Optimal variance-reduced stochastic approximation in Banach spaces. Preprint, submitted January 21, https://arxiv.org/abs/2201.08518.Google Scholar
• [61] Mou W, Li CJ, Wainwright MJ, Bartlett PL, Jordan MI (2020) On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. Abernethy J, Agarwal S, eds. Conf. Learn. Theory, vol. 125 (PMLR, New York), 2947–2997.Google Scholar
• [62] Negrea J, Yang J, Feng H, Roy DM, Huggins JH (2022) Tuning stochastic gradient algorithms for statistical inference via large-sample asymptotics. Preprint, submitted July 25, https://arxiv.org/abs/2207.12395.Google Scholar
• [63] Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838–855.Crossref, Google Scholar
• [64] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Crossref, Google Scholar
• [65] Ruppert D (1988) Efficient estimations from a slowly convergent Robbins-Monro process. Technical report, Cornell University Operations Research and Industrial Engineering, Ithaca, NY.Google Scholar
• [66] Sarkar D, Aggarwal V (2026) Nonlinear two-time-scale stochastic approximation: A sharp phase transition and how to beat it. Preprint, submitted June 12, https://arxiv.org/abs/2606.14488.Google Scholar
• [67] Sharrock L (2022) Two-timescale stochastic approximation for bilevel optimisation problems in continuous-time models. Preprint, submitted June 14, https://arxiv.org/abs/2206.06995.Google Scholar
• [68] Srikant R (2025) Rates of convergence in the central limit theorem for Markov chains, with an application to TD learning. Math. Oper. Res., ePub ahead of print October 3, https://doi.org/10.1287/moor.2024.0444.Link, Google Scholar
• [69] Stroock DW, Varadhan SS (1997) Multidimensional Diffusion Processes, vol. 233 (Springer Science & Business Media, Berlin).Google Scholar
• [70] Sutton RS, Szepesvári C, Maei HR (2008) A convergent O(n) algorithm for off-policy temporal-difference learning with linear function approximation. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Adv. Neural Inform. Processing Systems, vol. 21 (MIT Press, Cambridge, MA), 1609–1616.Google Scholar
• [71] Sutton RS, Maei HR, Precup D, Bhatnagar S, Silver D, Szepesvári C, Wiewiora E (2009) Fast gradient-descent methods for temporal-difference learning with linear function approximation. Danyluk AP, Bottou L, Littman ML, eds. Proc. 26th Annual Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 993–1000.Google Scholar
• [72] Tadic VB (2004) Almost sure convergence of two time-scale stochastic approximation algorithms. Proc. 2004 Amer. Control Conf., vol. 4 (IEEE, Piscataway, NJ), 3802–3807.Google Scholar
• [73] Tang K, Liu W, Zhang Y, Chen X (2023) Acceleration of stochastic gradient descent with momentum by averaging: Finite-sample rates and asymptotic normality. Preprint, submitted May 28, https://arxiv.org/abs/2305.17665.Google Scholar
• [74] Wang Y, Wu S (2020) Asymptotic analysis via stochastic differential equations of gradient descent algorithms in statistical and computational paradigms. J. Machine Learn. Res. 21(199):1–103.Google Scholar
• [75] Wang Y, Zou S, Zhou Y (2021) Non-asymptotic analysis for two time-scale TDC with general smooth function approximation. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Red Hook, NY), 9747–9758.Google Scholar
• [76] Wang Z, Wang Y, Narang I, Wang F, Wang Y, Maguluri ST (2026) Steady-state behavior of constant-stepsize stochastic approximation: Gaussian approximation and tail bounds. Preprint, submitted February 15, https://arxiv.org/abs/2602.13960.Google Scholar
• [77] Whitt W (1970) Weak convergence of probability measures on the function space C[0,∞). Ann. Math. Statist. 41(3):939–944.Crossref, Google Scholar
• [78] Wu YF, Zhang W, Xu P, Gu Q (2020) A finite-time analysis of two time-scale actor-critic methods. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin HT, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Red Hook, NY), 17617–17628.Google Scholar
• [79] Xie C, Zhang Z (2022) A statistical online inference approach in averaged stochastic approximation. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Adv. Neural Inform. Processing Systems, vol. 35 (Curran Associates, Red Hook, NY), 8998–9009.Google Scholar
• [80] Xie C, Jin K, Liang J, Zhang Z (2024) Asymptotic time-uniform inference for parameters in averaged stochastic approximation. Preprint, submitted October 19, https://arxiv.org/abs/2410.15057.Google Scholar
• [81] Xu T, Liang Y (2021) Sample complexity bounds for two timescale value-based reinforcement learning algorithms. Banerjee A, Fukumizu K, eds. Internat. Conf. Artificial Intelligence Statist., vol. 130 (PMLR, New York), 811–819.Google Scholar
• [82] Xu T, Wang Z, Liang Y (2020) Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. Preprint, submitted May 7, https://arxiv.org/abs/2005.03557.Google Scholar
• [83] Xu T, Zou S, Liang Y (2019) Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 10633–10643.Google Scholar
• [84] Yaji VG, Bhatnagar S (2020) Stochastic recursive inclusions in two timescales with nonadditive iterate-dependent Markov noise. Math. Oper. Res. 45(4):1405–1444.Link, Google Scholar
• [85] Yang H, Lim HD, Lee D (2026) Periodic regularized Q-learning. Preprint, submitted February 3, https://arxiv.org/abs/2602.03301.Google Scholar