Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers a statistical inference problem for which parameters are estimated by stochastic approximation (SA) with a constant step size. The main theoretical results are derivations of functional central limit theorems (FCLTs) under a Markov chain setting. Three important cases are analyzed: linear stochastic approximation (LSA), stochastic gradient descent (SGD), and Q-learning. The inference method is based on random scaling that has been recently proposed in the literature. The numerical experiments involve SGD in the context of linear and logistic regression with a large sample but a small number of covariates.   
strengths_and_weaknesses: - Originality: Recent work has applied random scaling to SGD with a decreasing step size for the purpose of inference. This paper is new in the sense that it applies random scaling to SGD with a constant step size. 

- Quality: The theoretical work is of high quality. Assumptions are clearly stated and the results are impressive. The numerical work is of medium quality. The experimental design is simple but adequate to make the point that random scaling works for SGD with a constant step size in the linear regression model. 

- Clarity: The paper is very clear.

- Significance: The results in the paper are non-trivial and useful. The inference method is incomplete when the bias is nonzero but the results in this paper may lead to a new line of research that can estimate or bound the bias. 

questions: (1) The nonzero bias problem is unfortunate, as the confidence interval does not center around the true parameter value. It is nice to have an upper bound on the bias at the order of the square root of the learning rate.  Is there any way to develop lower bounds on the bias? It would be interesting to know what type of nonlinearity matters for the bias.

Here are some minor suggestions.

(a) References 13 and 14 are now in the conference proceedings, 13 in AAAI-22 and 14 in COLT-22, respectively.

(b) In line 205, what is "i" in collected i the $t$-th iteration; perhaps "in"?



 
limitations: Generally speaking, the authors addressed the limitations. A few things, which can be mentioned (additionally or in more detail), are as follows:

(1) SGD with a constant step size leads to an inefficient estimator and as a result, the resulting confidence interval with random scaling will be wider than that with a decreasing step size. 

(2) How to choose the learning rate (step size) in applications is not discussed; furthermore, there is no real data application which would provide a more difficult environment for choosing the step size.

(3) No replication files are provided in the supplementary material.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper suggests a procedure for constructing confidence intervals for constant step-size SA algorithms. The suggested procedure is based on FCLT and random scaling procedure. This technique might be viewed as an alternative to the methods based on estimations of the asymptotic variance of the Markov chain, such as batch mean or spectral variance. The method is tested on a constant step-size SGD procedure for low-dimensional linear and logistic regressions.
strengths_and_weaknesses: Originality.

Results similar to Theorem 2.1 are well-known in the Markov chain literature (see e.g. [Douc et al, 2018], sections 21.2-21.3). It is also typical that there are no additional requirements for the moments of order $(2+\delta)$. It is also possible to mention the paper [Atchade, 2013]. Generalizations of these results to the multidimensional scenario are rather straightforward. CLT for the Markov kernels which are W-uniformly geometrically ergodic (the scenario considered in Proposition 2.1) is also well-known in MCMC literature. 
Moreover, CLT results in theorems 3.1--3.3 do not require novel methods and easily follow from obtaining the Wasserstein contractility of the corresponding transition kernels. So the theoretical findings of the paper are limited.  In the empirical evaluation, the authors also consider only model examples of low-dimensional logistic and linear regressions. 

Clarity
The paper is quite well-written, and the suggested methodology and theoretical derivations are clear.  I would suggest to fix the statement of Theorem 3.3 in order to mention explicitly the access to generative model $P(\cdot | s,a)$ for each state-action pair $(s,a)$.

Significance.
Constant step-size SGD and $Q$-learning with constant step size are of moderate interest. Q-learning without bonuses and with constant step size makes sense only with access to generative model, which is of limited practical interest. More interesting scenarios invoke the decreasing step size in SA and/or the Markovian noise dynamics, which require much more sophisticated analysis. Another problem concerns the bias of constant SA scheme. For example, in theorem 3.2 the covariance matrix $\Sigma_{\pi_{\eta}}$ scales as $\|\|\Sigma_{\pi_{\eta}}\|\| \lesssim \eta$, which is of the same order as the bias term in th.3.2.2. Thus bounding the bias as $O(\eta^{1/2})$ is not enough. 

References:
[Douc et al, 2018] - R. Douc, E. Moulines, P. Priouret, and P. Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering, 2018.
[Atchade, 2013] Y.F. Atchad´e (2016), Markov Chain Monte Carlo confidence intervals. Bernoulli 22(3), 1808–1838.

questions: 1. I would be curious to see the empirical performance of the random scaling approach in RL applications. For example, I suggest the authors consider the grid-world type example and a Q-learning procedure on it. Another scenario could be TD-learning with linear functional approximation, studied e.g. in the paper [17] (cited in the paper);
limitations: The authors addressed the limitations correctly. Yet the main limitation is that only the constant step-size SA problems are considered, which lowers the potential applicability of the result.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the online statistical inference problem under a constant step size stochastic approximation setting. The authors first present a functional central limit theorem type result. Then given the FCLT result for the stochastic approximation problem, they further propose an online statistical inference framework using random scaling. They also illustrate their theoretical results in three cases, i.e., linear stochastic approximation, stochastic gradient descent, as well as Q-learning. Some numerical experiments are given to further support their findings.



strengths_and_weaknesses: **Strengths**

- This paper is overall well written, and the authors present their theoretical findings clearly. 
- In the literature, there is much work established on the diminishing step-size SGD and its corresponding statistical inference, from Polyak and Juditsky (1992). On the contrary, the constant step size SGD (and its parameter inference) is rarely studied, this paper enriches the theoretical results in this area. 
- The authors also have a theoretical contribution to relaxing the $2+\delta$  moment condition. 
- In Section 3, the authors also give theoretical results on three useful examples.

In summary, I would like to emphasize this paper's theoretical contribution to the constant step size stochastic approximation problem, both the asymptotic distribution part and the online statistical inference part.

**Weakness**

This paper is very good in general, I have a few concerns that are stated below,

1. Some related work should be cited properly, e.g.,  [1] present an online statistical inference framework for SGD-type estimator; 
[2] gives the very first asymptotic results and a statistical inference framework for adaptively collected data; [3] gives some nice theoretical results on the constant step-size SGD.
2. The assumption (strong convexity) in Theorem 3.2 is a little bit strong, and cannot be applied to the logistic regression case that the authors used in the experiment section. The authors could find an extension to the locally strong convexity in [4], under which the logistic regression satisfies the assumption.

[1] Chen, Xi, Jason D. Lee, Xin T. Tong, and Yichen Zhang. "Statistical inference for model parameters in stochastic gradient descent." The Annals of Statistics 48, no. 1 (2020): 251-273.

[2] Chen, Haoyu, Wenbin Lu, and Rui Song. "Statistical inference for online decision making via stochastic gradient descent." Journal of the American Statistical Association 116, no. 534 (2021): 708-719.

[3] Dieuleveut, Aymeric, Alain Durmus, and Francis Bach. "Bridging the gap between constant step size stochastic gradient descent and Markov chains." The Annals of Statistics 48, no. 3 (2020): 1348-1382.

[4] Su, Weijie J., and Yuancheng Zhu. "Uncertainty quantification for online learning and stochastic approximation via hierarchical incremental gradient descent." arXiv preprint arXiv:1802.04876 (2018).
questions: I have just one question for the authors: under the constant step SGD setting, the bias ( $\mathbb{E}_{\pi} \beta - \beta^*$) is not negligible, and in practice, the statistical inference cannot be done. The authors state that when $\eta \rightarrow 0$, the bias term is diminishing as well, but wouldn't that becomes the case where we have a diminishing step size and where traditional Polyak-Judisky type estimator and inference will be used instead?
limitations: None
review_title: null

Meta-review: metareview: This paper provides an online framework for stochastic approximation algorithms with fixed step size. Several reviewers commended the work, and I agree that the contributions are sound and relevant to the NeurIPS community. The more negative review provides very constructive criticism, and the knowledgeable reviewer points out flaws that should be addressed in the final version. The authors have done a good job responding to reviewer comments, and have added additional experimental details to bolster the results. Some discussion on the limitations of restricting to constant step size regimes (including some of the points laid out in the discussion/responses to reviewers) will also help readers contextualize and clarify the scope 
confidence: Less certain
Decision: Accept