Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides a novel analysis to the linear MDP setting through an actor critic setup where the policy is softmax-parameterized. The claim is that we can avoid mixing time and exploration based assumptions by using this analysis. This is attractive since its much simpler/cleaner, but also comes with a slower convergence rate. The main steps include bounding the policy within a KL ball of the maximum entropy optimal policy through a mirror descent style analysis, followed by controlling the critic approximation error given the policy is within the KL ball.
main_review: The paper is well written, fairly simple to follow, and provides good justifications and reminders about the overall story to the reader when going into mathematical details. I was able to follow the main story but not the specific details for proving the different lemmas. Overall, I think the motivation is strong and a cleaner analysis is definitely much appreciated. On the downside, there aren't any algorithmic insights I could gather from the paper. Particularly, is there anything a practitioner can take away from this? This might not be a concern if the paper was offering a novel result, however the question in this case is what exactly do we gain from this alternate analysis. Right now, I don't think we learn much but hopefully the authors can comment more on this point. Finally, below are some questions I hope the authors can reply to for me to understand the work better:

- So the assumption that the optimal maximum entropy policy places a positive mass on every state + the KL bound allows us to use the same assumption on any policy within the KL bound. How should one contrast this with the assumption that the softmax parameterization itself places a positive mass on each state (+ is that even true)?

- The KL is upper bounded by the number of actions k. Can you say something about how growing number of actions affects the KL bound? Moreover, wouldn't the horizon term dominate for common cases here? How tight is this KL bound overall? Intuitively, it seems like the KL ball should be growing smaller as we explore more of the MDP, whereas here it is fixed across all 't'. Can you provide an intuitive explanation for why this is still fine?
summary_of_the_review: The paper is nicely written and provides an interesting alternative to analysing a linear MDP with an actor critic setup. I have some doubts about how much insight can be gained from this analysis for future work, especially algorithmically and therefore I am currently advocating for a weak accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This heavily technical theoretical paper main contribution is to show that Natural Actor-Critic is "philosophically" implicitly biased toward high entropy policies. 
More precisely, the key result is to show that Actor-Critic, when set as a batched  mirror descent algorithm applied on a linear finite states and linear finite actions MDP with linear softmax policies, without regularization or explicit exploration, but with properly chosen parameters, maintains its policies in a KL ball of radius 1+ ln(k) + 1/(1-gamma)^2 around the maximum entropy optimal policy (the optimal policy which samples uniformly the optimal actions) with high probability (Theorem 1.4).
It is worth noting that this result is obtained without global mixing assumptions on the MDP (only with a mixing assumption on the target policy). 
This is an improvement from previous work (Khodadadian 2021) who assumed uniform mixing and provided only expectation bounds.

Dropping these assumption is however costly: with a step size set to 1/sqrt(t), the number of iterations required to obtain and epsilon-optimal policy is epsilon^{-14}.

The core of the paper is in the detailed proof which spans 11 pages of appendix.
main_review: With a very slow convergence rate 1/epsilon^{14}, the provided algorithm is strictly theoretical and is not intended to be applied (the authors are clear and honest on that ground).
Despite the real author's efforts, the paper is very hard to read and requires an advanced mathematical background coupled with a vast culture on theoretical aspects of RL. The main paper and the few pages of proof that I checked seemed solid but I must admit that this paper is behind my reach.
That said, I find interesting for the community to get a few theoretical results on actor-critic, and I do not expect such results to be easy to handle. 

Minor remarks:
page 12 line 3 "is just ... and need not be" -> is just ... and needs not to be"

summary_of_the_review: A highly theoretical paper underlying an interesting result on the bias of actor critic toward high entropy policies. The proofs are long and technical and assessing their correctness is behind my reach. But my bet is that it is a good and correct paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes and analyzes the convergence rate and optimality of a natural-actor-critic-like actor critic with linear function approximation in linear MDPs. The most important discovery is that once the policy is within the ball of the maximum entropy optimal policy, it remains there forever provided that the critic is sufficiently accurate. Consequently, one now needs to make ergodicity assumption for only the optimal policy, instead of all policies along the optimization path.
main_review: I think the paper makes a reasonable contribution to the field. 
First, it explicitly uses the results from mirror descent to analyze their actor update, which confirms that once the policy is within the ball of the maximum entropy optimal policy, it remains there forever provided that the critic is sufficiently accurate. This result appears novel to my knowledge and is useful in eliminating previously used strong assumptions. 
Second, it analyzes the converge of linear TD without using a projection, which also appears novel to my knowledge.

However, I do have some concerns. I find the proofs are not very reader-friendly. I cannot really verify the proof of Lemma C.2, though I tend to believe it is correct. I think the coupling used in page 18 is not clearly defined. What is the distribution of z_{i, j} and can E_{i, j} be clearly defined? And I cannot get why the inequality leading to 32m / B ... holds. This is the major concern for my score 5; I'd like to raise my score if  this concern is clarified. In general, I think there are many skipped steps in the proofs, it would be good if all the proofs can be verified directly by looking at the pdf without doing extra computation.

A possible improvement: I am not sure if linear MDP is a necessary ingredient for this work. In my understanding, it's used only to ensure that the TD fixed point is the true value function. I think this can also be ensured by either considering tabular setting or linear function approximation with compatible features. It would be good if the authors can briefly discuss this, after all linear MDP is a very strong assumption.

summary_of_the_review: I think the paper makes reasonable contribution but the presentation of the proofs can be improved.

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

The authors successfully addressed my concerns and I increased my score accordingly.
review_title: null

Meta-review: The paper makes a significant contribution in the rather sparse and challenging field of convergence analyses of actor-critic style algorithms, under the linear MDP structural assumption, showing that there is a natural bias towards being high-entropy. As one of the reviewers points out, although it is unlikely that the strategy actually proposed is amenable to implementation, the paper nevertheless provides a clean and novel analysis of convergence of learning by eschewing the usual mixing time type assumptions often found in the theoretically-oriented RL literature. Based on this strength of the paper, I am glad to recommend its acceptance.
Decision: Accept (Poster)