Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the analysis improvement of existing policy gradient methods. The authors apply the recent new analysis of policy mirror descent to natural policy gradient methods ( and its Q-based version ) under log-linear policy class. The provided convergence results improve the state-of-the-art rates, using either adaptively increasing stepsize or constant stepsize. The authors also present a sample-based algorithm and sample complexity which improves previously-known results in the same setting. 
strength_and_weaknesses: **Strengths**

- The paper studies log-linear policy class for natural policy gradient methods. This linear function approximation setting is important since it is a basic case of widely-used policy gradient methods using general neural policy parametrization

- The authors employ the policy mirror descent analysis from Xiao, 2022 in the tabular case to analyze the log-linear version of natural policy gradient methods in the function approximation setting. This optimization perspective is meaningful to practical RL methods since it offers a more careful characterization of problem-dependent parameters and algorithm stepsizes. 

- The established convergence results improve the results from Agarwarl et al. 2021 from sublinear convergence to linear convergence (both up to some errors), with new choices of algorithm stepsizes. Achieving fast convergence is beneficial to training RL algorithms with better efficiency.


**Weaknesses**

- The established convergence rates depend on the distribution mismatch coefficients and the concentrability coefficients. Since these coefficients either depend on the optimal policy or the policy iterates that are unknown before training, it is hard to estimate them. It is not very clear how useful these convergence rates are in practice. It is useful to discuss how bad the rate could be, e.g., all these coefficients are chosen in the worst way. 

- The distribution mismatch coefficient can be very large in large MDPs even when the initial state distribution is uniform. Large distribution mismatch coefficients lead to poor convergence rates and dependence on function approximation errors, simultaneously. It is useful to discuss the reason for this limitation, and the possibility to address it.

- The established theory seems to be unique to the log-linear policy class. It is more useful if the authors could discuss its extension to the general policy class.  

- The paper hasn't supplied empirical evidence to demonstrate the practical use of the suggested theory. Since function approximation is ubiquitously employed in RL, it is useful to provide experimental results as additional support. 
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and all claimed results are supported by rigorous proofs. However, since many terminologies are borrowed from the literature, e.g., compatible function approximation, relative condition number, concentrability coefficient, and transfer error, it is helpful if the authors could add more explanations. Also, the comparison with existing results seems to be very technical. It is helpful if the authors could make a table to list all pros/cons for clarity. Although linear rate results are interesting, the improved sublinear rate is also important and I recommend stating it in the main context.  

The paper builds on the policy mirror descent analysis of Xiao, 2022 while a careful introduction of problem-dependent parameters and function approximation errors could be an additional novelty. The improved linear rates are more expected, but they do advance our understanding of the natural policy gradient method in the function approximation setting. Overall, the technical novelty is average. 

For some other questions, please find them here for consideration.

- Why call Eq. (18) 'approximated NPG' or 'approximated mirror descent'? It can be confused with approximation in the policy update, which is not your case. 

- Is the analysis restricted to the log-linear policy? How about other normalization of linear function approximation instead of using softmax functions? 

- There is a discrepancy between the transfer error type bound and the approximation error type bound. It is not very clear which one is better. 

- How do you choose features that satisfies Eq. (32)? 

-  Is there a way to increase stepsize when the discount factor is unknown? 
summary_of_the_review: The paper studies the natural policy gradient methods ( and its Q-based version ) under log-linear policy class by applying the recent new analysis of policy mirror descent. The established convergence rates improve the state-of-the-art rates using either adaptively increasing stepsize or constant stepsize. However, due to the problem/algorithm-dependence, it is not very clear how useful these convergence rates are in practice. The authors also present a sample-based algorithm and sample complexity which improves previously-known results in the same setting. The paper hasn't supplied empirical evidence to demonstrate the practical use of the provided theory. 

============================

POST-REBUTTAL. Thank you for your response. Since my concerns are addressed in the new draft, I am inclined to recommend acceptance. The score has been updated.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the geometric convergence of NPG and Q-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 or Q-NPG with a geometrically increasing step size results in exponential convergence to a ball around the global optimum. This ball is proportional to these function approximation errors. For the Q-NPG algorithm, the authors state their result under two different set of assumptions, and for NPG, the authors consider one set of assumption. Furthermore, by a standard sample based analysis of their result, the authors show 1/epsilon^2 sample complexity of their algorithm, which matches the best known result for Q-learning. 
strength_and_weaknesses: Strength: 
- The authors consider a wide range of assumptions. 
- For these settings the authors establish a geometric rate of convergence, which is superior to the prior work with function approximation
- The authors establish a tight 1/epsilon^2 sample complexity
Weakness: 
- Some of the constants, such as C_v, can be arbitrary bad, and might be in the cardinality of state*action space. Appearance of this constant in the upper bound besides the 1/(1-\gamma), can result in a very poor bound. 
- The contribution of the paper is limited compared to the prior work, specially Xiao (2022). It seems just a direct extension of Xiao (2022) theorem 10 to the linear function approximation, where we through all the errors due to function approximation to a big constant in the upper bound.
- 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). Can the authors comment on (possible) lower bounds of NPG or Q-NPG in terms of 1/(1-\gamma)?
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly, and it is easy to follow. The results seem to be sound.
summary_of_the_review: I believe the paper is a minor extension of the prior work. The different set of assumptions that the authors consider are not all that different. 
---------------------------------------------------------------------------------------------------------------- 
After reviewing the rebuttal, I believe there are interesting points compared to the prior works. Specifically, the extension of this work compared to Xiao (2022) is not direct, specifically for the sample complexity analysis. I am increasing my score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers infinite-horizon discounted Markov decision process with finite state and action space. By re-formulating the natural policy gradient (NPG) and the Q-NPG methods as approximate versions of the policy mirror descent (PMD) method, the paper shows that both methods enjoy linear convergence rates and \tilt{O}(1/{\epsilon}^2) sample complexities with the help of the compatible function approximation. 
strength_and_weaknesses: Strength:
  The paper shows the both the natural policy gradient (NPG) and the Q-NPG methods have linear convergence rate and \tilt{O}(1/{\epsilon}^2) sample complexities, which is an improvement to the limited tabular setting shown in the previous works.

Weakness:
  Although the result is new and is an improvement to the existing literature, the technics it uses are very incremental to the existing tabular setting one. By using linear function approximation and reformulating the resulted update rules as approximate versions of the policy mirror descent (PMD) method, it's very incremental to demonstrate the linear convergence rate results in this paper.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to read. For the novelty, please refer to my previous comments.
summary_of_the_review: The paper has improvement in terms of demonstrating the linear convergence rate of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy for the linear function approximation setup in the infinite-horizon discounted Markov decision processes. However, the efforts are incremental considering the previous works on the policy mirror descent result on tabular setting as well as the linear function approximation used in similar settings.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes linearly converging variants of NPG and Q-NPG methods, with log-linear policy class and compatible function approximation. The convergence results bare a similar spirit as the recent development of policy gradient methods in the tabular setting. In the stochastic setting, the authors establish an $O(1/\epsilon^2)$ sample complexity by showing an $O(1/T)$ convergence rate for the policy evaluation. Both of these results seem to improve upon previous results on policy gradient (NPG) method in the linear function approximation setting. 
strength_and_weaknesses: Strength:
The paper is technically correct, and addresses the existing literature sufficiently. In addition to showing an improved convergence rate for the policy optimization, the paper also exploits a faster convergence result for the policy evaluation procedure, which seems the crucial factor in obtaining the final $O(1/\epsilon^2)$ complexity.

Weakness:
The only comment and suggestion that I have is the presentation of assumptions. There are some assumptions that seem less clearly motivated (e.g. Assumptions 3 and 4). Although some of these appear also in prior literature, it would be beneficial to provide some more context on why/where certain assumptions are needed.

Minor comment: The policy evaluation (e.g., Algorithm 6) seems to require the state-action pairs (Line 2, Algorithm 6) to be independent for different timesteps. Can the author comment on the feasibility of using Markovian sampling?
clarity,_quality,_novelty_and_reproducibility: The paper has a clear presentation, with new results on the analysis of policy gradient methods in the linear function approximation setting. 
summary_of_the_review: I appreciate the technical effort this paper puts into developing new understandings of how natural policy gradient converges with compatible function approximation, yielding a linearly converging policy optimization error and $O(1/\epsilon^2)$ sample complexity. The analysis bears certain novelty in terms of two perspectives. First, the analysis of policy optimization with compatible and linear function approximation is established, while accounting for both the error in policy evaluation and function approximation error. Second, the policy evaluation analysis exploits a sharper result than the one used in prior literature, which is needed for establishing the $O(1/\epsilon^2)$ sample complexity. 

I believe the paper contains enough new results to the field of policy gradient methods.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work studies  natural policy gradient algorithms to solve Markov Decision Problems when the policy is a log-linear parameterization in terms of features. A specific inexact model that incorporates stochastic approximation error is studied in contrast to prior works. The key contribution is the establishment of linear convergence rate under a set of conditions that are strictly weaker than prior work. 

Strengths are in contributing a novel analysis technique that exploits compatible function approximation, the extension to the log-linear policy parameterization, and the relaxation of the prior assumption on the infinity norm approximation error of the Q function estimator.

Weaknesses are in the fact that the problem class is extremely similar to prior work, and the the contribution of the work is clearly in the minutiae of the convergence analysis of natural policy gradient methods. In particular, policy mirror ascent is already well-studied, and the main contribution is the study of the log-linear class under compatible function approximation. 
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Accept: poster