Summary
This paper studies the asymptotic bias in non-linear stochastic approximation algorithms with Markovian noise and fixed step-size. Upon applying the averaging technique of Polyak and Ruppert, the authors identify that, in general, the bias is of the same order of the step-size. The main source of bias is characterized, and an extrapolation technique is employed so that bias is attenuated. Finally, a few numerical studies are presented for illustration of the theoretical contributions.
Strengths
I find the overall contribution of the paper to be very interesting. As far as the reviewer is aware, the characterization of bias for nonlinear SA with parameter dependent Markovian noise is novel and original.
The analysis seems sound. The reviewer did not have time to look over every single proof carefully, but haven't found egregious errors in the proofs revised.
The problem setup, assumptions and approach to analysis are clearly stated. The paper is well-written, but some polishing is needed.
Weaknesses
In particular, there have been recent papers, achieving similar bias characterizations and higher order error bounds for stochastic approximation with Markovian noise (see for example [R1] and [R2] which both deal with linear recursions). The approach to analysis in [R2] is similar to the present paper in the sense that the bias characterization is also given in terms of solutions to Poisson's equations. Moreover, this is not the first time that Richardson-Romberg extrapolation is used for bias attenuation in stochastic approximation: it was previously proposed in [R1] to kill the dominant term of order O(\alpha) just like the present paper.
The authors do cite [R1] in the present work, but the reviewer feels that a deeper discussion is needed on how the present paper improves upon [R1] and [R2]. I encourage the authors to include a citation on previous uses of this technique as well.
[R1] Huo, Dongyan, Yudong Chen, and Qiaomin Xie. "Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes." Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 2023.
[R2] Lauand, Caio Kalil, and Sean Meyn. "The curse of memory in stochastic approximation." 2023 62nd IEEE Conference on Decision and Control (CDC). IEEE, 2023.
Questions
- Is it possible to relax the assumption that the parameters remain within the compact set \Theta with probability one? It seems likely that the authors can obtain their results subject to a moment bound, which I believe is more realistic based upon standard SA stability theory.
- One thing that sets this paper apart from others is that they allow Markovian noise that is parameter dependent. This is extremely valuable in RL applications such as Q-learning (for example, epsilon-greedy policies induce such a model), and actor-critic methods. Could the authors provide more discussion regarding applications in which the Markovian noise is parameter dependent?
-Could the authors clarify whether the experiments display in Figure 1 (a) and (b) pertain to the same run? It is hard to identify the improvement between RR exploration and the regular algorithm for the choice of \alpha =0.01. I encourage the authors to include sample paths for \alpha =0.01 and \alpha =0.005 instead of the \alpha =0.0025 for visualization.
Limitations
The authors discuss the limitations of their work and assumptions in section 3.3.