Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes two variance-reduced (VR) algorithms for a specific nonconvex strongly concave min-max problem obtained after reformulating the policy evaluation problem as a min-max game with nonlinear function approximation for the value function of the policy. They provide the first O(1/K) convergence and the possibility of removing the full gradient computation required in VR methods in certain iterations. 
strength_and_weaknesses: The convergence results are provided for the first time and they look theoretically sound to me. 

Weakness:
1. I am not sure about the role of \Theta in the paper. It seems that it is mentioned in the last paragraph on page 4 and then dropped subsequently in the min-max formulation (2) or (4). Would the analysis work if such \Theta is explicitly imposed on the min-max problem? Note that in such a case, the \|J(\theta)\| may not converge to zero.

2. The maximization over \omega \in R^d of equation (2) changes to \omega \in \mathcal{W} in equation (4). Does that change the policy evaluation problem? There is no justification provided for this abrupt change. Is compactness of \mathcal{W} necessary for convergence?

3. Why does the paper say it is a single timescale algorithm? I see two timescales \alpha and \beta in the algorithm. Are they set the same in the implementation? 

4. I don't see how the sample complexity is O(\kappa/\eps) in Theorem 1. Based on the step-size policy, I believe it should be a larger power of \kappa. E.g., \kappa^3/\eps. 

3. Since the main technical thrust of the paper is VR algorithms for the min-max problem, I was expecting some literature review of such algorithms, at least for nonconvex settings. It is important to put this result in the context of such literature and show the novelty of their work over the state-of-the-art in the optimization literature. I recommend that the authors include papers/articles working on VR algorithms for smooth nonconvex (note that J(\theta) is a smooth nonconvex function) and nonconvex-concave minx-max problems. 


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to follow. The proofs seem clear to me. The only comment I have is to define \epsilon_\theta in the proof of Theorem 1.

In terms of quality and novelty, the algorithm design is not new. A similar VR gradient design was used in Nonconvex smooth optimization in the past. Applying this to the extended nonconvex strongly concave minmax problem is new in the literature if I am not missing something. Although I am not updated with the state-of-the-art in this specific area.


summary_of_the_review: Overall, the paper makes some new contributions to both areas: VR algorithms for minmax problems and Policy evaluation in RL. Although, the paper does lack significantly in terms of literature review. It ignores the first area completely. The single-timescale part is fuzzy at best. The order of condition number in the sample complexity seems wrong to me.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors developed a new efficient, single-timescale variance-reduced primal-dual method (VRPD) with an emphasis on the feasibility of solving non-convex policy evaluation problem in reinforcement learning (RL) with nonlinear function approximation, also known as the value function estimation or on-policy learning with nonlinear function approximations. VRPD is a single-timescale algorithm that meets an $\mathcal{O}(1/K)$-rate of convergence to a first-order stationary point for general non-convex-strongly-concave (NCSC) minimax optimiztion, under mild assumptions and appropriate parameter choices. The authors claim that they provide the best-known result in the literature. An enhanced VRPD method is also proposed, namely VRPD${}^{+}$, to allow adaptive batch sizes using historical information while maintaining the theoretical convergence rate. The authors empirically validated the proposed method and concluded higher sample efficiency over comparable methods including VRPD.
strength_and_weaknesses: Page 2, middle part.
I am confused when the authors indicate "new proof techniques in convergence rate analysis". To quote words in your paper it "resolves an open question and clarifies an ambiguity in the state-of-the-art convergence analysis ...". Can you clarify what was the ambiguity and how did you clean it?

Page 3, middle part (related work).
My understanding is that Du et al. (2017) study the TD(0) formulation of policy evaluation with linear function approximation, which can be re-cast as a strongly-convex-concave problem. What is the true novelty of this work, in comparison with Du et al. (2017)? Du et al. (2017) solved this problem via VR-based methods and achieves a linear convergence rate via the gradient descent-ascent type method. Is it correct that nonlinear function approximation leads to possible non-concavity?

Page 4, first paragraph.
SREDA adopts "PiSARAH" subroutine but the latter is not detailed.

Page 4, second paragraph.
It should be desirable if the dependency on *all* problem-dependent constants should be considered when discussing matching the lower bounds. At first glance, it seems that the method is not sharp in terms of $\kappa$, and this is natural due to that no acceleration method is adopted. In my opinion, even if the resulting upper bound failed to match the lower bound by Zhang et al. (2021) in certain regimes, some discussions in fine-grained angles should be added.

Page 7, middle part (Remark after Theorem 1).
The author wrote "Theorem 1 states that VRPD achieves an $\mathcal{O}(1/K)$ convergence rate to an $\epsilon$-FOSP". The complexity and rate of convergence have been awkwardly mixed together and caused confusion. One should modify it accordingly. I like the more detailed stochastic sample complexity of $\mathcal{O}(M + \sqrt{M}\kappa\epsilon^{-1})$ where $\kappa$ denotes the condition number of the strongly convex part. Also, "The most challenging part in proving Theorem 1 stems from the fact that one needs to simultaneously evaluate the progress of the gradient descent in the primal domain and the gradient ascent in the dual domain of the minimax problem". This is merely a standard technique and is well-known in recent minimax optimization.

Some reference bibitems are duplicated, e.g. Sutton et al. Authors are encouraged to clean them when preparing their next version.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written with words and sentences of good quality, and the single-timescale method for the given problem is novel in literature to my best knowledge. The complexity result matches the one in Luo et al in the regime $\kappa=O(1)$, and hence somewhat expected.
summary_of_the_review: In summary, the authors did a satisfactory job introducing the single-timescale method that solves an important practical problem (policy evaluation in RL), achieving sharp convergence rates matching the lower bound under certain regimes ($\kappa=O(1)$). With that said, the paper potentially admits some issues of overclaiming their results. Plus, the author seems to have solved a much broader problem but applied it to a very specific problem (of policy evaluation with nonlinear function approximation). Extending such a framework to wider application instances as the next step might be a good idea. As of the current form I give my rating of borderline inclining rejection and encourage the authors to address these main points in their revised version.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the policy evaluation problem of reinforcement learning. Based on a primal-dual formulation of the objective, the authors apply a variance reduction technique to solve the problem under the nonlinear function approximation. They claim that the algorithm attains $O(\frac{1}{K})$ iteration complexity.
strength_and_weaknesses: Strength:

- The paper proposes a variance reduction method for solving a problem that seems to have a connection with the policy evaluation problem. They obtain the $O(\frac{1}{K})$ iteration complexity.

Weakness:
- The considered finite-sum objective differs from the original MSPBE objective. In fact, the objective cannot even be viewed as an unbiased substitute, as the sample from a trajectory doesn’t follow the stationary distribution. Such an objective is not justified.
- The algorithm’s update is poorly explained. From my view, it’s just SPIDER’s update [1], which is a popular variance reduction approach. However, there is no discussion with existing variance reduction methods.
- The projection step in (8) is not explained.
- There are too many typos and unprecise claims, making the paper hard to read. Here are examples:
1. The last $g_\theta(s)$ in (1) should not have a transpose.
2.  The strongly-concavity definition in assumption 4.2 is wrong; the function should also be additionally concave.
3.  The L_f-smoothness definition in assumption 4.3 is unprecise; theta and omega should be in the same norm.

[1] Spider: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator.
clarity,_quality,_novelty_and_reproducibility: The paper is poorly organized and hard to follow. There are too many unjustified and misleading claims.
summary_of_the_review: The paper’s motivation is not clearly centered. The optimization objective is not justified and the algorithm is not explained. There are many typos and technical flaws which make the paper hard to understand. Thus, I believe the work is not finished and is far from its fine shape for publication in ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies policy evaluation with nonlinear function approximation. It proposes and analyzed two algorithms called VRPD and VRPD+ to optimize the primal-dual form of the MSBPE. The VRPD algorithm utilizes variance reduction techniques to achieve $O(1/K)$ convergence rate.
strength_and_weaknesses: Strength:
1. Paper is well-written and easy to follow.
2. Compared with previous work on the non-convex-strongly-concave minimax optimization problem, the convergence rate of this work achieves $O(1/K)$, which is the same as before and has fewer constraints.

Weakness:
1. The convergence metric is unconventional. The first term in Eqn (9) is the full gradient w.r.t. $\theta$, which (I believe) includes both the partial derivative of the first input and the chained gradient w.r.t. $\theta$ via the second input. This first term already suffices to guarantee a first-order stationary point, rendering the second term redundant. On the other hand, bounding the partial gradient of both inputs is also acceptable. I wonder why the analysis of this paper fails to provide a guarantee for either of these metrics.
2. The technical novelty of the minimax optimization technique used here is not clearly stated and compared with previous works. I believe it helps to also make a list to compare with previous NCSC minimax optimization algorithms.
clarity,_quality,_novelty_and_reproducibility: The paper is of high quality and clarity. 

Questions:
1. Regarding the weakness mentioned above, can you establish guarantees for the two terms in Eqn (9) separately?
2. It seems to sample a trajectory with a length of $M$ cannot be used as a finite-sample approximation of the stationary distribution. In discounted setting, the classical way to do so is to run the trajectory with a stopping probability of $1-\gamma$, and only use the last step as an unbiased sample from the stationary distribution. This doesn't really affect your optimization results but should be made clear under the context of RL or policy evaluation.
summary_of_the_review: Currently, the paper shows strong theoretical results compared with previous literature. Some concerns still need to be addressed. Thus I recommend weak acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a variance-reduced primal-dual method (VRPD) for policy evaluation, which can achieve a fast convergence speed with nonlinear function approximation. 

Strengths:

It provides a detailed convergence analysis.

Weaknesses:

The novelty of the algorithm is limited.

The dependence on the condition number is not optimal.

The presentation is poor
 
The author's response partly addressed some concerns from reviewers. However, not all the reviewers are excited about this paper. Therefore, I recommend rejection.

justification_for_why_not_higher_score: The novelty of the algorithm and its analysis is limited. The presentation is poor.
Decision: Reject