Summary
This paper studies constant step-size stochastic approximation algorithms with Markovian noise. It is known that in this case, the error of a stochastic does not vanish asymptotically, even when consider averaging. This is \theta_n has a bias. Previous work have show how to study the bias of such algorithm for linear stochastic approximation. In this paper, the authors tackle the more challenging case of non-linear stochastic approximation. Most of the paper is devoted to proving that the bias is of order O(\alpha). Some discussion on the applicability of results is presented.
Strengths
The paper proposes a characterization of the bias under the challenging setting of Markovian noise plus non-linear drifts.
The analysis is asymptotically tight as the step size \alpha converges to 0, i.e., the expression for the bias is not a bound but an equality plus smaller order terms.
The implications of the results are discussed.
Weaknesses
Most of the assumptions needed to obtain the results are relatively mild but two conditions are quite strong:
1. strong monotonicity (A3)
2. Smoothness (A2)
I think that the paper should discuss in more details these assumption and highlight that they are really limiting the applicability of the result.
The assumption developed in part 4.2 to avoid assuming that the iterates are bounded seems quite strong, not verified in many practical cases (for instance any instance of stochastic gradient descent where the noise has a finite support would not satisfy this assumption), and very artificial (is the only purpose of this assumption to
The paper is extremely long (54 pages including proofs and references). To me, this says that there is either too much content or that the results are too diluted. As a result, the paper is very technical and hard to read. There should be more effort to make the paper more readable. Some suggestions:
- consider a slightly less general setting
- avoid considering sub-cases (like section 4.2) that are a bit orthogoal to the paper
The practical applications of the results are unclear. Some potential applications are presented in Section 4.5 / 4.6 but there are no experiments or simulations to confirm that this actually work (these sections are interesting, though).
There is a lot of papers on the subject. This can be seen as a good sign (this is an active area of research), but at the same time, it is hard for me to really assess the novelty of the results. Note that there are some (recent) papers that seem related to these work and that might be cited. This last point is not a weakness since some of them are extremely recent (available online after the submission deadline):
- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise. S Allmeier, N Gast (2024)
- Bias in Stochastic Approximation Cannot Be Eliminated With Averaging, Caio Kalil Lauand, Sean P. Meyn (2022)
- Revisiting Step-Size Assumptions in Stochastic Approximation. Caio Kalil Lauand, Sean Meyn (2024)
A comparison with these papers might be useful (even of this is not mandatory for the two 2024 papers).
Questions
There are some questions / comments in the limit that would deserve some comments from the authors.
The Markovian noise (x_k) is assumed exogeneous (it does not depend on \theta). For some application (like Q-learning with a navigating policy derived from \theta), this would not be satisfied. Could this assumption be lifted?
The next order term is a O(\alpha^{3/2}): is it the sharpest bound or could O(\alpha^2) be obtained?
Limitations
The limitation of the assumptions (see "weaknesses") should be better discussed.