Summary
## Overview
Let $Z, Z_1, \dots, Z_n$ be i.i.d. random elements with a common distribution $\pi$ over $\mathbf{Z}$. Given $A : \mathbf{Z} \to \mathbb{R}^{d\times d}$ and $b : \mathbf{Z} \to \mathbb{R}^d$, the goal of the LSA procedure is to find the unique solution $\theta^\star$ of
$$\mathbb{E}\left(A(Z)\theta^\star - b(Z)\right) = 0. $$
Given a decreasing sequence of step sizes $\alpha_k$ and a starting point $\theta_0$, the standard LSA is given by
$$\theta_k = \theta_{k-1} - \alpha_k(A(Z_k)\theta_{k-1} - b(Z_k)) $$
and the Polyak-Ruppert averaged LSA is given by
$$\overline{\theta_n} = \frac{1}{n} \sum_{k=n}^{2n-1} \theta_k. $$
The authors provide Berry-Essen-type bounds for the Gaussian approximation of $\sqrt{n} \left( \overline{\theta_n} - \theta^\star \right)$ and for the corresponding multiplicative bootstrap process. Namely, for the Gaussian approximation result they upper bound the quantity
$$\rho_n = \sup_\text{B convex} \left| \mathbb{P}\left( \sqrt{n} \left( \overline{\theta_n} - \theta^\star \right) \in B \right) - \mathbb{P}\left( \Sigma_\infty^\frac{1}{2} \eta \in B \right)\right| $$
where $\eta \sim \mathcal{N}(0,I_d)$. And for the bootstrap approximation result they upper bound
$$\rho_n^b = \sup_\text{B convex} \left| \mathbb{P}\left( \left.\sqrt{n} \left( \overline{\theta_n^b} - \overline{\theta_n} \right) \in B \right| Z_1, \dots, Z_{2n} \right) - \mathbb{P}\left( \sqrt{n} \left( \overline{\theta_n} - \theta^\star \right) \in B \right)\right| $$
where $\overline{\theta_n^b}$ are obtained from a multiplier bootstrap process. It is interesting to notice that this multiplier process can be evaluated online without keeping a history in memory.
## Overall proof arguments
To provide the Gaussian approximation result the authors write
$$\theta_n - \theta^\star = (I - \alpha_n A(Z_n))(\theta_{n-1} - \theta^\star) - \alpha_n \varepsilon(Z_n) $$
where
$$\varepsilon(z) = A(z)\theta^\star - b(z). $$
The authors observe that $\varepsilon(Z_n)$ can be viewed as a noise, which is assumed to be bounded. Meanwhile, the operator $ I - \alpha_n A(Z_n) $ is a random perturbation around $ I - \alpha_n \mathbb{E}A(Z) $, which is shown to act as a contraction in an appropriate norm, provided that $-\mathbb{E}A(Z)$ is Hurwitz. Thus, when one take the PR average the noise is expected to behave as the sum of i.i.d. noises and the contraction term must shrink. This is formally done writing the PR average in the form of Theorem 2.1 [reference 60 of the paper] and bounding the terms given by the latter theorem.
The proof the bootstrap approximation result follows the standard practice in this literature:
- First, conditionally on the sample, a Gaussian approximation is obtained relating the bootstrap to a Gaussian with its covariance.
- Second, a Gaussian comparison theorem relates the latter Gaussian with the desired Gaussian, with some concentration results being used to bound their difference in high probability.
## Main claims and observations
The authors show that taking a step size of order $\frac{1}{\sqrt{k}}$ yields the best possible convergence rate in their bounds. They provide empirical evidence that this rate is optimal.
They also claim to be the first ones to fully provide a non-asymptotic bootstrap approximation result.
Strengths
The paper seems to be the first to provide non-asymptotic Gaussian and bootstrap approximation bounds for LSA. Their assumptions are quite mild and are in line with the ones made in similar papers in other domains. For instance, assumption A.2 is similar in nature to the boundness assumptions and the strong-covariance assumption made in [A]. The paper is mathematically sound and poses interesting research directions. I'm particularly curious about the convergence rate of $n^{-\frac{1}{4}}$ suggested by their theoretical results and supported by their experiment. The proposed application to policy evaluation in RL is also interesting. Finally, I point out that the code on the supplementary material was easy to reproduce.
[A] Chernozhukov, Victor, Denis Chetverikov, and Yuta Koike. "Nearly optimal central limit theorem and bootstrap approximations in high dimensions." The Annals of Applied Probability 33.3 (2023): 2374-2425.
Weaknesses
The main claim of the paper is that their bounds suggest an optimal convergence rate of $n^{-\frac{1}{4}}$ when taking $\alpha_k = \frac{c}{\sqrt{k}}$. The bottleneck of this convergence rate comes from an application of Cauchy-Schwarz inequality, the boundness of $\varepsilon$ and the MSE bound on $D$ given by Theorem 1. Meanwhile, the authors also provide experimental evidence that this convergence rate is indeed optimal (although not considering gamma values below 0.5 in Figures 1 or 3). A counter-example or a deeper discussion on this convergence rate would be beneficial to the paper: is it an artifact of the proof or is there reason to believe it cannot be improved?
Questions
Some observations:
- Line 54 has a typo in "Berry-Essee".
- In Equation (15) the $\ell$ can be removed from $\theta_{k}^{b,\ell}$ to enhance clarity. It is only used to explain that to evaluate the probability in practice one must run several samples of the bootstrap process.
- Line 263 has a typo in "date".
- The Equation after line 303 is using $\phi$ instead of $\varphi$.
- Line 307 asks for a sequence of "TD(0) updates", what does the "(0)" stands for?
- Figure 1 lacks x and y labels. The legend can also be improved for clarity.
Limitations
The authors adequately addressed the limitations and the potential impact of their work.