Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the geometric convergence of NPG parametrized by log linear function. The authors assume that approximation of Q-functions by linear function, and approximation of policy with log-linear function has some error bound, and they show that employing NPG with an increasing step size result in exponential convergence to a ball around the global optimum. This ball is proportional to these function approximation errors. 
strength_and_weaknesses: Strength: 
The paper extends the linear convergence rate shown for tabular setting in Xiao (2022) to a more general function approximation setting. 
Weakness:
- In the bound, v_\mu can be in general state and action dependent. Also it depends on 1/(1-\gamma). The authors do not specify the dependency of this parameter on state, action and 1/(1-\gamma). Since this parameter appears in an exponential manner in the upper bound, this can result in a very bad dependency on the upper bound.
- The contribution of the paper is limited compared to the prior work, specially Xiao (2022).
- The error terms appearing on the upper bound of Theorem 4.7 can be very loose. In particular, we have a very bad dependency in terms of 1/(1-\gamma).
clarity,_quality,_novelty_and_reproducibility: - In Remark 4.4 I believe by \pi you mean \phi. 
- The sample complexity stated right before Remark 4.8 is not clear. What is this sample complexity representing? What is w_t here? This is sample complexity of reaching epsilon neighborhood of what value?
summary_of_the_review: I believe the contribution of the paper is limited, and is a straightforward extension of the prior work. 
Also the paper is not well written. Some parts are not clear. There is a sample complexity which is not clear corresponds to what. 

---------------------------------------------------------------------------------

Update: After looking at the response by the authors, I would like to still keep my score. I believe the paper is a simple extension of the Xiao (2022) to the function approximation setting.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies policy optimization in single-agent RL with log-linear policy parameterization by focusing on natural policy gradient (NPG) method. In particular, this work demonstrates a linear converging error bound of NPG with increasing step sizes to the optimal policy, up to some statistical and approximation errors.
strength_and_weaknesses: Strength:

- This work investigates the problem of policy optimization with log-linear policy parameterization, which is a fundamental problem of the policy optimization theory. 
- This work extends the insight of [Xiao, 2022] from the tabular setting to the regime of linear function approximation and manages to achieve a linear converging error bound (up to some statistical and approximation errors) without introducing entropy regularization [Cayci et al., 2021].

Weaknesses:

- Assumption 4.6 imposes additional bound on the relative condition number for all iterations (compared to Assumption 6.2 in [Agarwal et al., 2021]), which is somewhat undesirable. It would be great if the authors can make this clearer when making a comparison and provide a justification.
- The claim "convergence towards an optimal policy" appears to lack some support. In particular, it remains unclear if the bound established in Theorem 4.7 is tight when compared with an optimal policy. In addition, the bound introduce a factor $\nu_\mu$ in the dependency on $\epsilon_{stat}$ and $\epsilon_{bias}$ (which is at least $1/(1-\gamma)$) compared with Theorem 6.1 in [Agarwal et al., 2021]. This makes the linear converging bound less appealing.
clarity,_quality,_novelty_and_reproducibility: See "Strength and Weakness".
summary_of_the_review: This work makes interesting contribution towards policy optimization with log-linear policy optimization, by extending the insight of [Xiao, 2022] which focused on the tabular setting. This work establishes a linear converging upper bound up to an error floor determined by $\epsilon_{stat}$ and $\epsilon_{bias}$, by deploying NPG updates with increasing step sizes. However, the magnitude of the error floor is worse than that of Theorem 6.1 in [Agarwal et al., 2021], despite introducing additional assumptions. Therefore, the reviewer vote for "5: marginally below the acceptance threshold".
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes to use increasing stepsize in Xiao, 2022, as shown in Theorem 4.7, in natural policy gradient with log-linear policy parametrization, and the main result is that the convergence rate is linear plus approximation errors, improving the $O(1/\sqrt{T})$ rate plus approximation error terms in Agarwal et al, 2021.

strength_and_weaknesses: **Strength**

The linear convergence rate was previously shown in softmax tabular parametrization, and this work shows that the same rate can be achieved with log-linear parametrization, which was not known before.

**Weaknesses**

1. The above mentioned results are new, but the novelty and technical contributions of this work are very limited to my knowledge for the following reasons.
    - The main analysis is based on decomposing $V^*(\mu) - V^T(\mu)$ into two parts of optimization error and biases, which has already been shown by Agarwal et al., 2021. This work adopted the same assumptions in Agarwal et al., 2021, i.e., Assumptions 4.1, 4.2, 4.5, and 4.6.
    - Using the decomposition of $V^*(\mu) - V^T(\mu)$, stepsize in Xiao, 2022 is then used.
    - The analyses also look very similar to those two works to me.
clarity,_quality,_novelty_and_reproducibility: **Quality**: Technical difficulty is limited since this work is using one existing technique into another one to obtain a not surprising result. 

**Clarity**: The paper is well written and the results are clearly presented.

**Originality**: Originality is limited as mentioned above.
summary_of_the_review: Overall, this work combines two existing techniques of Agarwal et al., 2021 and Xiao, 2022, and obtains a new linear convergence rate for natural policy gradient with log-linear parametrization. The results are correct and new. However, to my understanding, the technical difficulty and novelty of this work are limited.


====Update====

Thank you for the comments. However, after reading the authors' feedback and other reviewers' comments, I would keep my score.

As mentioned by the authors in the feedback, the main introduced technique is "the mirror descent formulation of Natural Policy Gradient for non-tabular settings", which "is substantially different from the analysis in [Agarwal et al., 2021]".

The "mirror descent formulation of Natural Policy Gradient" is actually not new. For example, the Q-NPG method in Agarwal2021 is similar to Eq. (2) and Algorithm 1 in this paper. 

My understanding of the authors' claim is that the authors used the analysis in Xiao2022 to the settings in Agarwal2021. The analysis of this paper (performance difference lemma and the three point descent lemma) contains also widely used techniques in mirror decent proofs. The authors' feedback still confirms my impression of incremental technical contribution. 

If the authors wanted to emphasize more the technical innovation, I suggest comparing and illustrating the difference and difficulty more directly, such that the audience can better understand the contributions of this work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes the convergence rate of the natural policy gradient (PG) algorithm with log-linear policy parametrizations in infinite-horizon discounted MDPs. The paper shows that under standard function approximation assumption about the Q-value functions, with an increasing stepsize, a linear convergence rate of the natural PG method can be obtained for log-linear policy class in both deterministic and sample-based settings. The results strictly improve the existing results along this direction, which can only have either sublinear convergence rate, or require regularization and bounded iterate assumptions. In the sample-based setting, the results do not depend on the cardinality of the spaces, but on the dimension of the features, which is favorable for large-scale cases. The paper is clearly written in general, and the results are of interest to the community.
strength_and_weaknesses: Strength: The paper developed new results on natural PG method with log-linear parameterization, and is well-written generally (up to some small errors). The motivation is clear, and the manuscript is concise and easy to follow.

Weakness: As a pure theory paper, I am a bit uncertain about the technical novelty and solidness of the results. It seems that it strongly relies on the analysis in previous works, e.g., Agarwal et al, 2021, Xiao 2022, and Telgarsky et al., 2022. The idea of increasing the stepsize also follows from Xiao 2022. I skimmed through the proof, which reinforces my feeling as well.

Other Comments:
1. As it is a theory paper with new technical results, it would be helpful to summarize the novelty of the "Techniques" in the front, e.g., in introduction, so that the readers can better understand it and compare it with the literature.
2. It would be better if some simple experiments can be provided to corroborate the theoretical findings: how does the stepsize affect the convergence rates, how does it compare with the existing PG algorithms, and any ablation study about the algorithm parameters (stpesize, feature vector, etc.).
3. It was claimed in the abstract and intro multiple times that the results do not depend on |S|, |A| but only on d. However, in the main results in Theorem 4.7, there is still dependence on |A|. It was argued that "can be removed with a path-dependent bound". It was not very convincing to me to claim this without a valid statement. It is better to either give a formal statement here, or modify the claims in the beginning. 
4. Errors and typos:
1) Definition of $d_\rho^\pi(s,a)$ on page 3 is not correct. 
2) Some notation abbreviation in sec. 2.1 is not consistent with later sections, e.g., $\pi^t$ v.s. $\pi_t$. Where is $d_\mu^*$ defined? Since it is a theory paper, being rigorous about notation would be important and affect the credential of the paper. 
3) There is an additional "the" in the sentence right before Assumption 4.2.
4) Definition of linear MDP in Remark 4.4 is not correct: P and r should be sharing the same feature $\phi$.


**Post-rebuttal:**

Thank the authors for the rebuttal. I have read it, and also read other reviewers' comments. Now I get that the mirror descent reformulation of the NPG update in the linear function approximation case is new. But I am still a bit unsure if the overall novelty clears the bar of ICLR. I recommend the authors to maybe add the results regarding neural network and even general function parameterization more formally, to make the results more complete and stronger. I will hence stick to my previous evaluation. Thank you.
clarity,_quality,_novelty_and_reproducibility: In general the paper is well written and has good clarity. However, the technical novelty seems a bit limited. It is a theory paper so there is no reproducibility issue.
summary_of_the_review: In sum, the paper presented some interesting results about natural policy gradient for log-linear policy classes. The techniques and idea about the algorithm (increasing the stepsize specifically), are based on several most related literature, making the novelty and orginality of the work a bit limited to make the cut.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the NPG in softmax policy with linear function approximation. By proposing a new updating strategy, in which the stepsize increases at a designed rate, this paper is able to show that the NPG enjoys a per-iteration geometry convergence rate w.r.t a factor $1-1/\nu_\mu$. Since previous works of NPG in the similar setting mostly focus on establishing sublinear convergence rate, the result established in this paper is interesting.
strength_and_weaknesses: Strength:
(1) This paper is well-written and easy to follow
(2) The technique proof is solid and clear
(3) The result established in this paper is different from all previous works in the same setting, which is interesting.

Weakness:
(1) The major technique contribution of this paper is in exploring how the incremental increasing stepsize with the special RL optimization nature can provide a linear convergence rate, which is interesting but not strong enough.
(2) The linear convergence rate in this paper may not be very useful in most of the case. The major reason is that the contraction factor $(1-1/\nu_\mu)$ is significantly larger than \gamma (or very close to 1 as $\nu_\mu$ is usually very large. With a given sample complexity $\epsilon$, if $\nu_\mu$ scale as $\mathcal{O}(\exp(1/\epsilon))$ then the sample complexity in this paper may actually looser than standard NPG complexity results established in many previous works. Thus, the linear convergence rate established in this paper only improves the real sample complexity of NPG within a very limited scenario. 
clarity,_quality,_novelty_and_reproducibility: The author may need to discuss in what scenario their established result really outperforms the pervious SOTA results of NPG. After doing that, readers are able to justify the real contribution of this paper.
summary_of_the_review: Overall this paper provide a very interesting result of NPG. However, the result is more like provide a different formulation of the sample complexity result of NPG instead of establishing a more tighter bound (for detail see my comment in weakness in previous section).


============ post rebuttal ============


After reviewing author's response, I will raise my score to 6. The contribution in this paper is not strong enough given the state-of-the-art. The linear convergence rate of PG without entropy regularization has been explored in previous work. For example, in [1], when adopting l2 regularization in their mirror descent update, the result in [1] naturally implies a linear convergence rate for PG algorithm. However, since this paper explore a new technique for analyzing the PG type algorithm, it might be interesting to the community.

[1] Lan, G. (2022). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 1-48.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: There has been a lot of recent work on the convergence of policy gradient methods. [Agarwal et al., 2021] provide a very thorough analysis of natural policy gradient (NPG), which divides error into three parts: 
1) Optimization error -- which vanishes as more gradient updates are conducted
2) Statistical error -- which vanishes as more samples are used for estimation 
3) Bias due to error in the approximation architecture. 

Agarwal et. al gave a sublinear convergence rate for the optimization error. Subsequently, several papers point out that this could be made linear when stepsizes are large, at least for tabular representations which avoid issue (3). The idea is that NPG with large stepsizes is policy iteration, which converges linearly. The current submission particularly builds on [Xiao, 2022], who show linear convergence of NPG in the tabular case. 

*Strengths*: Linear convergence is not surprising. When there is no error in function approximation and step-sizes are large, NPG essentially   reduces to policy iteration. Still, the literature lacks results that provide policy iteration style convergence rates when large stepsizes are used AND one assumes approximation errors are uniformly small (in an appropriate sense). This paper closes the gap. 

Most interesting, perhaps, is that the term capturing limiting bias depends on a certain maximal mean squared error rather than infinity norm error. To my reading, the main trick in the paper is to strengthen an assumption in Agrawal et. al so that large stepsizes are possible while still controlling error. (The authors do not call call this out and instead write that they make a similar assumption...) 

*Weaknesses:*  Generalizing NPG with tabular representations to NPG with accurate function approximation is not as substantial as it might first appear: with perfectly accurate approximation, the two algorithms are identical. It feels a bit as if someone stitched Xiao [2022] together with the control of error terms in Agrawal et. al [2022]. All five reviewers worry that the novelty relative to past work is limited. All feel the paper is below the bar. If theoretically minded reviewers who are actively interested in this topic feel this way, it is hard to argue that the work should be highlighted to the broader ICLR community. 
justification_for_why_not_higher_score: The weakness section above gives somewhat succinct answer.
Decision: Reject