Thank You for the Comments
Dear AC,
**The Difference:** We thank the AC for pointing out Leslie and Collins (2003), which we will include in our literature review. The main difference between Algorithm 1 of this work and the one in Leslie and Collins (2003) is that our learning dynamics is *single time-scale* while the one in Leslie and Collins (2003) is *two time-scale* as they require $\lambda_n/\mu_n\rightarrow 0$. Technically, the fact that we do not have a time-scale separation between the two sets of iterates presents major technical challenges in establishing the finite-sample bound, which we overcome with our coupled Lyapunov approach. In terms of results, Leslie and Collins (2003) consider only the asymptotic convergence in matrix games while we establish the rate of convergence (*which is more informative and challenging compared with asymptotic convergence*) in both matrix and stochastic games.
**Our Results Imply the Mean-Square Convergence of the Last Policy Iterate** Thanks to reviewer r3LS’s second comment, we realized that algorithm 1 does enjoy a stronger convergence guarantee (not just in expectation for the regularized Nash gap). Specifically, recall that the Nash distribution (denoted by $(\pi_\tau^1,\pi_\tau^2)$) is the unique minimizer of the regularized Nash gap defined right before Corollary 2.2.1, where the uniqueness part follows from the regularized Nash gap being a strongly convex function. Therefore, by the quadratic growth property of strongly convex functions, we have $\sum_{i=1,2}\lVert \pi_k^i-\pi_\tau^i \rVert_2^2\leq c RNG(\pi_k^1,\pi_k^2)$ for some constant $c>0$, which, after combining with Corollary 2.1.1., provides the mean-square convergence of the last iterate $(\pi_k^1,\pi_k^2)$. We will include this result as a corollary in our next version.
**Single Time-Scale vs Two Time-Scale** The stepsize condition imposed in Leslie and Collins (2003) is standard for establishing the almost sure convergence (Borkar 2009) while our goal is to characterize the rate of convergence, where the stepsize choice might be different to obtain the best possible rate. While it is theoretically unclear if there is a fundamental gap between the convergence rates of two time-scale stochastic iterative algorithms (of which the algorithm in Leslie and Collins (2003) is a special case) and their single time-scale counterparts, in the existing literature for finite-sample analysis, the established upper bounds for two time-scale algorithms are mostly **sub-optimal**. For example, the convergence rate of two time-scale SGD established in Zeng et al (2022) was $k^{-1/4}$ while single time-scale SGD achieves $k^{-1/2}$. The convergence rate of the two time-scale natural actor-critic algorithm established in Khodadadian et al. (2022) was $k^{-1/6}$ while the lower bound for RL is $k^{-1/2}$, which is achieved with single time-scale algorithms such as $Q$-learning (Li et al. 2020). To obtain the best possible rate of convergence (cf. the $1/k$ rate convergence in Corollary 2.1.1 of Algorithm 1), we adopt a single time-scale framework.
**Almost Sure Convergence vs. Finite-Sample Analysis** Asymptotic convergence in general does *not* imply any rate of convergence. In addition, the techniques and conditions to establish asymptotic convergence and finite-sample bound are fundamentally different. In particular, consider the requirements on choosing the stepsizes. Asymptotic convergence typically requires the stepsizes to be squared summable (Robbins and Monro 1951), recent results in Bhandari et al.( 2018); Chen et al (2022) show that mean-square finite-sample bound can be established with stepsizes of the form $1/k^z$ for all $z\in (0,1]$. Note that when $z\in (0,1/2)$, the stepsizes are not squared summable.
Borkar, V. S. (2009). Stochastic approximation: a dynamical systems viewpoint (Vol. 48). Springer.
Zeng, S., Doan, T. T., & Romberg, J. (2021). A two-time-scale stochastic optimization framework with applications in control and reinforcement learning. arXiv preprint arXiv:2109.14756.
Bhandari, J., Russo, D., & Singal, R. (2018, July). A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory (pp. 1691-1692). PMLR.
Chen, Z., Zhang, S., Doan, T. T., Clarke, J. P., & Maguluri, S. T. (2022). Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automatica, 146, 110623.
Khodadadian, S., Doan, T. T., Romberg, J., & Maguluri, S. T. (2022). Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control.
Li, G., Wei, Y., Chi, Y., Gu, Y., & Chen, Y. (2020). Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Advances in neural information processing systems, 33, 7031-7043.
Best,
Authors