Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning

We would like to thank the referee uNZU for careful reading of the manuscript and raising interesting questions. Next, we answer the issues raised.

Missing References on Statistical Inference We thank the referee for provided references and will add them to the revised version of the paper.

Strong Assumptions: assumption on Bounded $\varepsilon(z)$ Indeed, the assumption of bounded $\varepsilon(z)$ is strong, but can be partially relaxed. Following the stablity of matrix products technique, used in [Proposition 3][Durmus et al, 2021], we can generalize the moment bound for products of random matrices (Corollary 4) for the setting when the random variable $\|\|A(Z) - \bar{A}\|\|$ has only finite number of moments. In particular, finite $3$rd moment of $\|\|A(Z) - \bar{A}\|\|$ (which implies naturally that $\|\|\varepsilon(z)\|\|$ also admits only a finite $3$rd moment) is sufficient to obtain the first main result of the paper on the Berry-Esseen inequality (Theorem $2$). However, it will be not sufficient to prove the boostrap validity (Theorem $3$), since this result requires high-probability bounds on the product of random matrices $\Gamma_{m:k}$. Yet there are two settings when we can generalize our results without the assumption concerning bounded $\|\|\varepsilon(z)\|\|$:

1. Random matrix $A(Z)$ is almost sure bounded, but $\|\|\varepsilon(z)\|\|$ is sub-gaussian, or, more generally, for any $p \geq 2$ it holds that

for some $\beta \geq 1/2$. In such a case, we can generalize our bootstrap validity along the lines of the current proof;

2. The random variable $\|\|A(Z) - \bar{A}\|\|$ is sub-Gaussian, and $\|\|\varepsilon(z)\|\|$ is sub-Gaussian. In such a case, using the high-probability bounds outlined in [Proposition 3][Durmus et al, 2021], we can have a counterpart of Theorem $3$ up to additional powers of $\log{n}$. \end{enumerate} We will add the discussion above the the revised version of the paper.

Tightness of Derived Upper Bounds Indeed, it is a very interesting question to obtain the mathching lower bounds that can illustrate the fact that the rate $n^{-1/4}$ is indeed sharp. See the reply for all referees for details on lower bounds.

Minor Corrections Thanks, we will correct this typo and will perform additional proofreading for the revised version of the paper.

We would like to thank the referee ew5L for careful reading of the manuscript and valuable suggestions for presentation improvement. Next, we answer the issues raised.

The analysis and main text are hard to follow Indeed, there are technical details in the main text that complicates reading, yet we were willing to be precise and state exact lower bounds on sample size $n$, especially in $A3$ and $A4$. In the revised version we will modify eq. $9$ and eq. $17$, switching to $\mathcal{O}$ - notation, and move precise bounds to appendix, as was suggested.

The numerical experiments are also weak since many of the plots are not related to the contributions of the paper itself We respectfully disagree with the referee - the figure (a) explains, why step sizes $\alpha _k = c_0 / k^{\gamma}$, $\gamma > 1/2$ are less preferrable. In this case the plot (a) illustrates slow convergence of the rescaled error $\sqrt{n}(\bar{\theta}_n - \theta^*)$, which is the reason which explains slow convergence of the respective rescaled approximation errors on subfigures (b) and (c). For the new plot (see the attached PDF file veasible for all referees) we included the expression $n^{1/4} \Delta_n$ with and without logarithmic scaling. Thus we expect that this quantity converges to a constant when $\gamma = 1/2$ and grows with $n$ when $\gamma > 1/2$. We will also consider running longer experiments, as for now we have included a figure with one more observation (added point corresponding to $n = 3 276 800$ observations).

Could the authors clarify if using Polyak Ruppert averaging is necessary to obtain such a Berry-Esseen bound? No, in principle it is not necessary, but the result will be slightly different in this case. It is known that (see e.g. [Fort, 2015]), that the corresponding CLT for the last iterate can be written as

where the covariance matrix $\Sigma_{\text{last}}$ is different from $\Sigma_{\infty}$. Then, using the perturbation-expansion technique from [Aguech et al, 2000], we write that

where $\tilde{\theta_n}^{(tr)} = \Gamma_{1:n}(\theta_0 - \theta^*), \quad \Gamma_{1:n} = \prod_{i=1}^{n} (I - \alpha_{i} A(Z_i) )$ is the transient component of the error,

is the leading (with respect to step size) component of the error and $H_{n}^{(0)}$ is a remainder term. Thus, using the argument from the current submission, $\tilde{\theta_n}^{(tr)}$ is exponentially small in $n$, $J_{n}^{(0)}$ is the linear statistics in $\epsilon(Z_j)$ that guaranttes asymptotic normality after re-normalization, and $H_{n}^{(0)}$ is the remainder term. It can be shown that

Thus, applying similar technique of randomized concentration inequalities (formula 13 in the current submission), we will obtain the Berry-Esseen bound for $\frac{\theta_n - \theta^*}{\sqrt{\alpha_n}}$, which should scale as $\sqrt{\alpha_n}$.

Typos in figure labelling Thanks, we will correct this typo and will perform additional proofreading for the revised version of the paper.

References:

[Aguech et al, 2000] Rafik Aguech, Eric Moulines, and Pierre Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization, 39(3):872–899, 2000.

[Fort, 2015] Central limit theorems for stochastic approximation with controlled Markov chain 411 dynamics. ESAIM: PS, 19:60–80, 2015.

We thank the referee for their comments. We will include a discussion on the Berry-Esseen result for last iterate as well as a longer run for simulations.

We would like to thank the referee DkFj for the work and for the positive feedback! Next, we answer the issues raised.

Bottleneck of the convergence rate and counter-example or a deeper discussion on this convergence rate This is indeed a very important question. First of all, the analysis of Theorems 1-3 can be adjusted for the whole range of step sizes $\alpha _k = c_0 / k^{\gamma}, \quad \gamma \in (0,1)$. The only modification would affect lower bounds on step size $n$ in the assumptions $A2$ and $A3$, respectively. There is a reason to believe that the moment bound of Theorem~1 is sharp, that is, the best possible bound on $\mathsf{E}^{1/2}[\|\|D\|\|^2]$ is of order $n^{-1/4}$ when setting $\gamma = 1/2$. The corresponding lower bound on moments of the remainder (in $n$) terms can be found for the setting of strongly convex optimization in [Li et al, 2022]. We expect that this result can be generalized for the LSA setting as well. However, the tightness of the moment of Theorem 1 bound does not directly imply the tightness of the bounds of Kolmogorov distance $\rho_n^{\text{(Conv)}}$. It is hard to say if the cross-correlation terms appearing between the linear statistics $W$ and non-linear statistics $D$ in the bound (13) are sharp. See also the general discussion on this topic.

We leave further exploration of this question as a promising direction for a future work.

Typos and misprints We thank the referee for careful reading of the manuscript and will fix the raised issues in the revised version of the paper. We will also re-generate Figure $1$ with longer trajectories and change legend as suggested by the referee in order to improve readability.

Line 307 asks for a sequence of "TD(0) updates", what does the "(0)" stands for? In general one can perform a policy evaluation using the whole family of TD($\lambda$) algorithms, where $\lambda \in [0,1]$. One can find the details in the paper [Tsitsiklis and Van Roy, 1996]. However, when we choose an instance of the algorithm with parameter $\lambda > 0$, corresponding dynamics of parameter updates (\theta_k)_{k \geq 0\} becomes non-Markovian. TD($0$) is arguably the most popular algorithm of this family, and the only one which falls directly into the stochastic approximation paradigm.

References: [Li et al, 2022] Li, C.J., Mou, W., Wainwright, M. and Jordan, M., 2022, June. Root-sgd: Sharp nonasymptotics and asymptotic efficiency in a single algorithm. In Conference on Learning Theory (pp. 909-981). PMLR.

[Tsitsiklis and Van Roy, 1996] Tsitsiklis, John, and Benjamin Van Roy. "Analysis of temporal-diffference learning with function approximation." Advances in neural information processing systems 9 (1996).