1. I think it is a bit overstated (Line 10 and Line 673) to use the term \epsilon-approximate stationary point of J -- there is still function approximation error as in Theorem 4.5. I think the existence of this function approximation error should be explicitly acknowledged whenever the conclusion about sample complexity is stated. Otherwise readers may have the impression that compatible features (Konda, 2002, Sutton et al 2000) are used to deal with these errors, which are not the case. 2. As shown by Konda (2002) and Sutton et al (2000), compatible features are useful tools to address the function approximation error of the critic. I'm wondering if it's possible to introduce compatible features and TD(1) critic in the finite sample complexity analysis in this paper to eliminate the \epsilon_app term. 3. I feel the analysis in the paper depends heavily on the property of the stationary distribution (e.g., Line 757). I'm wondering if it's possible to conduct a similar analysis for the discounted setting (instead of the average reward setting). Although a discounted problem can be solved by methods for the average reward problem (e.g., discarding each transition w.p. 1 - \gamma, see Konda 2002), solving the discounted problem directly is more common in the RL community. It would be beneficial to have a discussion w.r.t. the discounted objective. 4. Although using advantage instead of q value is more common in practice, I'm wondering if there is other technical consideration for conducting the analysis with advantage instead of q value. 5. The assumption about maximum eigenvalues in Line 215 seems artificial. I can understand this assumption, as well as the projection in Line 8 in Algorithm 1, is mainly used to ensure the boundedness of the critic. However, as in Line 219, R_w indeed depends on \lambda, which we do not know in practice. So it means we cannot implement the exact Algorithm 1 in practice. Instead of using this assumption and the projection, is it possible to use regularization (e.g., ridge) for the critic to ensure it's bounded, as done in asymptotic analysis in Zhang et al (2020)? Also Line 216 is a bit misleading. Only the first half (negative definiteness) is used to ensure solvability. But as far as I know, in policy evaluation setting, we do not need the second half (maximum eigenvalue). 6. Some typos: Line 463 should include \epsilon_app and replace the first + with \leq \epsilon_app (the last term of Line 587) is missing in Line 585 and 586 There shouldn't be (1 - \gamma) in Line 589 In Line 618, there should be no need to introduce the summation from k=0 to t - \tau_t, as the summation from k=\tau_t to t is still used in Line 624. In Line 625, it should be \tau_t instead of \tau In Line 640, I personally think it's not proper to cite [25] (the S & B book) -- that book includes too many. Referring to the definition of w^* should be more easy to follow. In Line 658, it should be ||z_k||^2 In Line 672, \epsilon_app is missing In Line 692, it should be E[....] = 0 In Line 708, there shouldn't be \theta_1, \theta_2, \eta_1, \eta_2 In Line 774, I think expectation is missing in the LHS Konda, V. R. Actor-critic algorithms. PhD thesis, Massachusetts Institute of Technology, 2002. Zhang, S., Liu, B., Yao, H., & Whiteson. Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation. ICML 2020.
4. Although using advantage instead of q value is more common in practice, I'm wondering if there is other technical consideration for conducting the analysis with advantage instead of q value.