Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the performance of the classic Relative Entropy Policy Search (REPS) algorithm of Peters et al. (2010) in the context of tabular reinforcement learning, focusing on the effect of optimization errors on the quality of the policy extracted from the solution. REPS is based on formulating the policy optimization problem as a regularized linear optimization problem which is equivalent to an unconstrained convex optimization problem, and calculating policy updates via approximately minimizing the dual function. The current paper sets out to understand the optimization issues surrounding solving these problems, and provides the following contributions:

- Showing that the policy suboptimality can be controlled in terms of the gradient norm associated with the approximate solution and some problem-dependent constants.
- Showing that the dual REPS objective is smooth, which implies that bounds on the additive optimization errors can be translated to bounds on the gradient norm at the approximate solution.
- Providing concrete performance bounds for an accelerated gradient descent method when the gradients of the objective can be evaluated exactly. This setting is rather unrealistic, but the results are insightful in that they shed light on the best attainable performance to be expected from this approach. 
- Providing concrete performance bounds for a stochastic gradient descent method that uses a generative model to obtain estimates of the gradients. The challenge here is that one cannot straightforwardly obtain unbiased gradient estimates, and one has to take several sample transitions to make sure that the bias in the updates is small enough. The authors address this challenge thoroughly and obtain guarantees that are polynomial in the desired accuracy level.
main_review: The paper is generally well-written and addresses a very important problem. REPS and its variants have achieved significant empirical successes and its exact version is known to achieve excellent performance guarantees, but understanding the performance of its empirical version using sample transitions has remained challenging. This paper takes an important step into this direction, although with some limitations: the performance bounds are proved under rather restrictive assumptions (such as uniformly lower-bounded state visitation probabilities) and are unlikely to be tight in general. Also, I am almost sure that there could be more effective ways of reducing the bias of the gradient estimator other than taking several independent samples and throwing them away after one use. That said, I believe that the merits of the paper outweigh its limitations. Indeed, studying the performance of primal-only methods like REPS is likely to be a very important direction in the future of RL theory, and the paper does a great job outlining the key challenges and providing some elementary solution methods to overcome said challenges.

While I did not have the capacity to check the proof details, the overall proof strategy is clearly explained in the main body of the paper so I could verify that it is entirely plausible. Being familiar with the related literature, I can confidently say that there are quite a few original ideas in the analysis which definitely do not follow directly from previous work. Maybe one possible complaint is that the writing sometimes becomes a bit dense with technical details, but overall I had no serious trouble understanding the main message and the technical content.

All in all, I find it very likely that this paper will inspire some further progress in the field, and that the community will benefit from it being published at NeurIPS 2021.
limitations_and_societal_impact: I foresee no negative societal impact or any limitations that are not adequately discussed in the paper itself.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies the convergence of the relative entropy policy search (REPS) method for solving LP-formulated MDP problems. The authors first assume the exact computation of gradients and prove the sublinear convergence of REPS regarding the regularized primal objective function and the policy. Second, the authors propose to estimate gradients using samples and prove the convergence or sample-complexity of sample-based REPS.

The main contribution is a convergence theory of REPS in both exact and stochastic settings. 
main_review: I have a few questions regarding originality and quality.

(1). In Section 5, the authors prove the properties of the Fenchel dual in Lemmas 1-3, relate the primal and dual variables in Lemma 4, and apply the existing gradient descent result to the Fenchel dual function in Lemma 7 and prove the convergence in Theorem 2. Most of these results are leveraged from convex optimization, e.g., [1]. An important step is Lemma 4 that gives a sufficient condition for getting a near-optimal policy. The rest is to apply the existing fast rate result (Theorem 1) to the smooth dual function under some problem assumptions. It is interesting that it does not work when $|S|=1$ due to Lemma 4. What is the technical reason? I roughly went through the proof of Lemma 4 and it still needs to explain more, e.g., weak duality, construction of $\bar{v}_s$. 

(2). The stochastic gradient method in Section 6 takes the visitation data to estimate gradients in Algorithm 2. It is less discussed the issues with high variance and biased in estimates, and thereby highly-suboptimal error rate.    

Regarding significance, I believe that the established convergence is useful in theory. Although the authors have established some interesting results, it still needs to be improved in many aspects (some are mentioned above).

(1). The established convergence could be sub-optimal. By assuming computing gradients exactly, the minimization of dual function is strongly convex and smooth, and it might be true for linear convergence. So, Theorem 2 can be loose. Any technical reasons? The sample-based convergence in Section 6 is highly sub-optimal. 

(2). As mentioned, it is not practical to compute the REPS objective exactly. However, the theory in Section 5 still assumes the exact computation. What is the convergence if errors enter into Algorithm 1, e.g., step 1 does not have a perfect oracle? By adding this consideration, it would be useful to have a more practical convergence theory. 

(3). It seems that your convergence theory relies on the strongly convex regularizer $F$. What happens if $F$ is convex? I feel that this will bring some technical challenges in analysis since the dual function is not smooth anymore.  

(4). There is no evidence from the experimental results showing the effectiveness of the theory. This gap has to be filled to convince readers.
 
Regarding clarity, the paper does not seem to be well structured, e.g., results and definitions are mixed in Section 5, lemmas and theorems are mixed so that it is not easy for readers to tell which are key results quickly. I recommend putting thoughts into explaining your results. The proofs in Supplemental Material are also not nicely explained. Here are some other clarity questions:

(1). Line 22-30: it is a long technical description. Is this helpful to the motivation of this paper? 

(2). Line 33: what do you mean by 'is likely not optimized fully'? any evidence or examples?

(3). Line 36: any reasons why you say 'it is far from clear'?

(4). Line 128, Line 132: is $\mathbb{E}^\pi$ the same? 

(5). Line 133: what is the domain for $\lambda^\pi$?

(6). Line 414: what are $(i)$, $(ii)$, $(iii)$?

(7). Line 525: what is the contraction property of projections? Is it non-expansiveness? A typo is the norm $\Vert x_{t+1}-x_t \Vert^2$.

(8). Line 534, Line 540, Line 541: missing citations.


References:

[1] On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient. arXiv:1803.06573

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

POST-REBUTTAL: Thank you for your response. I have read the response and other reviews. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper goes back to a well known algorithm, Relative Entropy Policy Search (REPS) and provides convergence guarantees for REPS by exploiting its relationship of RL via duality. Recently, there has been a surge of work exploiting the dual formulation of RL objectives, and this paper exploits that relation to performance convergence analysis of the REPS algorithm. Besides, very recently, a number of works has provided convergence of policy search and policy gradient algorithms - and the contributions of this work can be seen in light of recent works. The major contributoon of this work is to provide convergence guarantees for the dual objective of REPS, relying solely on on-policy samples and using accelerated gradient ascent on the dual formulation (whereas prior works exploiting duality often need to rely on off-policy samples, estimating distribution ratios). 

main_review: The key contribution of this work is to exploit duality in RL, and while relying solely on on-policy samples, the paper shows convergence guarantees of the dual objective based on advantage estimates, since the primal objective of REPS relies on the commonly used dual formulation in literature, based on state-action occupancy measures. 

By exploiting literature from convex duality and its applications in RL,  and the similarity of optimizing value functions versus state-action occupancy measures, this paper proposes convergence results of REPS via looking at the objectives from the dual perspective. In the primal form, REPS optimizes an objective based on state-action distributions, and using the convex duality formulation, this paper in turn looks at the dual formulation of REPS based on advantage functions and proposes convergence results for both exact and stochastic gradient estimates. A useful corollary of the approach is that the paper shows convergence for a purely dual approach based on on-policy samples, in contrast to existing works which rely on off-policy samples with distribution ratio corrections when exploiting duality in RL. 


Overall comments on the contributions of this work : 

Firstly, an overall comment on clarity of this work and presentation : There has been a surge of recent papers establishing convergence of policy search/optimization methods, including natural policy gradients, TRPO, actor-critic etc, which startsfrom tabular to function approximation, and also ranges to sample complexity results for stochastic gradient estimates of actor-critic algorithms. To my understanding, this paper is in light of such recent works, where the key contribution is to establish convergence of the REPS algorithm. While doing this directly is difficult, since REPS optimizes an objective based on state-action occupancy measures - this paper exploits duality in RL to in turn establish convergence of the dual formulation based on advantage estimates. 

In context of this, it seems to me that the presentation and clarity of this work is overly complicated. It can be written in a much more precise and clear formulation. While I appreciate the extensive details on RL via duality included in text - I think the main contribution of this work is not presented in a clear way. To me, almost the entire section of section 4 is a repetition of existing works, except explaining it in the context of REPS? Do we really need this? Instead of it, maybe clear objectives and explaining why the dual formulation is need along with the difficulty of optimizing REPS in the primal form would have been sufficient? Or am I missing something here? Can the authors point exactly on what's different in section 4 compared to existing works - I understand this is a background section establishing context of the work - but perhaps we do not need such in depth discussion, as it seems to make the paper overly complicated to understand. For example, I believe even equation 5, derived based on the Fenchel conjugate is known to the community now…

The first key result is established in section 5 Theorem 1? Is this correct? This is a re-establishment of existing work based on accelerated gradient ascent. Why do we have to resort to accelerated gradient ascent in this context for REPS? To me it seems like it is just another well known tool from the optimization community that is directly plugged in here? I expected a more clearer explanation of why we need this, compared to say using standard gradient estimates (since the main contribution is to analyse REPS via the dual formulation anyway).

As stated by the authors, the main difficulty is to ensure that the value function optimality guarantees will ensure convergence to a sub-optimal policy. This is similar to perhaps establishing a performance bound or sub-optimality gap for value functions and then deriving the convergence result based on that, for example, as in Agarwal et al., or Cen et al (for convergence of NPG with entropy regularization). What is so different here and what is the main difficulty? If we start with the dual objective of REPS based on advantages, why can we not similarly establish a performance difference bound for the advantage function, with an entropy regularization in the objective, and derive the convergence result from there? 

The paper includes a lot of details for the analysis, but is written in a very poor manner and it is difficult to understand the key technical contributions. As stated before, the main trick is to use accelerated gradient ascent on the dual formulation of REPS based on advantage estimates. The majority of the appendix is known to the optimization community, and is a direct plug in for the REPS formulation. Can the authors please comment on the key pillars of the convergence result, and what the main technical contribution is? 

My opinion is it seems there is a lot of tools used here from the optimization community establishing convergence results for the dual forms of the objective. While it seems like a lot of technical contributions, I could not find the key novel technical contribution used, specifically for the convergence of REPS? For example, if I do NPG/PG or TRPO with an accelerated gradient ascent - the same analysis would hold anyway? Yes, the paper is different since it uses the dual formulation, but this is already known to the community too. Therefore, can the authors comment on what are the major contributions from a theoretical viewpoint for this work?

Overall, my opinion is that the novelty of technical contributions is limited here, even though a lot of details are included (they are mostly from existing literature anyway). I agree analysing convergence of REPS is an important problem to consider - but I am not convinced there is a significantly new tool used for the analysis that would benefit the community. This paper seems more of a combination of different theoretical result blocks merged together and applied to REPS for deriving a convergence result. The length of the paper, including appendix, and the way the paper is written highlighting major contributions, therefore seems a bit misleading.  
limitations_and_societal_impact: ..
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the convergence rate of (tabular) Relative Entropy Policy Search (REPS), both assuming the knowledge of the transition matrix $P$ and then relaxing this assumption.
main_review: The paper starts by identifying two main issues of REPS.

The first issue is that convex duality asserts a relationship at the exact optimum of the primal or dual variables. However, REPS does not fully optimize the dual, and therefore it is not clear whether a near-optimal solution of the dua results in a near-optimal solution of the primal.
Furthermore, the dual problem of REPS identifies the minimization of (an entropic mapping of) the advantage; but this requires the knowledge of the transition matrix $P$. One way to overcome the problem is to rely on samples, at the cost of the introduction of a biased solution.

The paper starts with a gentle introduction of a linear program in Section~4, and then introduces a regularized version where a convex regularization $F$ is added to the linear objective. The convex constraint is usually a $f$-divergence (such as the Kullback-Leibler).

At this point, the authors notice that if $F$ is strongly convex, then its Fenchel conjugate must be $1/\beta$-smooth. This helps to characterize the smoothness of the dual function for REPS.

In Section 5.1, the authors provide a bound on the optimality of the solution. Building on these results and assuming Accelerated Gradient Descent as used optimization technique, the authors provide convergence rates in Section 5.2., assuming known $P$. In Section~6, the authors assume a sample estimate of the advantage (which causes a biased gradient) and provided a convergence rate for this scenario as well. 

__Meriths of the paper__

I was not able (both due to time constraints and also on the complexity of this work) to check in detail the proposed theoretical results. However, the work seems to follow a logical structure, and I find that most of the assumptions made are not particularly restrictive. Yet, the results presented, to the best of my knowledge, are new and important.


__A question__

The original paper from Peters et al, defined the stationary _undiscounted_ state distribution, i.e.,

$\sum_a \lambda_{s,a} = \sum_{a, s'}P_a(s|s') \lambda_{s', a},$

hence, defining an average reward setting. 
Your theory is instead defined on the discounted setting. _How do you plan to overcome this limitation?_ Lemma~4, and other results in your paper seem to do not allow $\gamma \to 1$.

__Two sides notes__

Would be nice if the authors could support some of their theoretical statements with empirical analysis. This should be doable since the theory is defined for a tabular setting and does not require strong assumptions.

As a future work (as also mentioned in the paper) would be really nice to extend this to continuous state space using a linear assumption of the state distribution w.r.t. a set of (non-linear) features. Even though, I am convinced that the current state of the paper is ready to be accepted at NeurIPS. 

__UPDATE__

I want to thank the authors for their detailed response, and all the other reviewers for the useful insights. 
The authors addressed my concerns in a satisfying manner, however, I think that other reviewers raised very important points. I do agree that the work needs to be polished. In particular, it needs to be a clearer separation of contributions and background, as highlighted by other reviewers; and a better justification of choice made. 

I do not detect problems with the theory. 
For example, I think that the strong convexity required on $F$ is reasonable, or the choice of utilizing an oracle in section 5 and then relaxing later the assumption by assuming stochastic gradients. I do not think that the analysis is immediate (e.g., although NAC and REPS are linked, I agree with the author that the results on NAC cannot be transported easily on REPS). As I also remarked in my previous review, I think that the assumption of finite state-action spaces is still interesting (even though continuous state-action might be desirable) and helps to analyze the algorithm. 

The fact that I do not detect the problems might be due to the fact that I do not have a strong background in convergence analysis (that is why I score my confidence with 3). I did not check derivations in detail. 

In light of the other reviewer's analysis, and considering the points of agreement with them, I will downgrade the score to 8 (therefore, still a good submission!).




limitations_and_societal_impact: The authors present the limitations of their submission. They do not discuss the societal impact, as there is no need.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper the authors the sample complexity of the relative entropy policy search (REPS). This algorithm aims at finding the optimal policy in an MDP using linear programming formulation. First the authors consider the planning setting where they assume access to the exact model of the environment. For this result they show that near stationary policies result in a near optimal policy.
Next they provide the convergence when the updates are being performed by biased stochastic gradients. 
main_review: - First of all, the setting of the paper is tabular, which is a limited setting for RL applications. Furthermore, the sample complexity is worse than the state of the art sample complexity in the literature for actor-critic and Q-learning methods. These two reasons puts the benefit of the results in the paper in jeopardy.
- Secondly, in the writing of the paper there are multiple definitions and lemmas (such as definition 6,7 or Theorem 1) which are well known in the literature. If the authors remove these definitions from the main body of the paper and just mention them briefly, it would save more space. As a suggestion, stating Theorem 3 somewhere earlier in the paper would make the presentation more clear.  
- The sampling scheme in Algorithm 2 is completely iid. This is indeed another limitation of this paper compared to the related work. In addition, is there a way to obtain unbiased estimate of the gradient? Since the data sampling is iid, I suspect it should be possible.
typo: line 240: x_0-x_*

****After rebuttal comment: After reading through the responses of the authors, I decided to increase my score to 6. I believe this is a good paper, and deserve presentation in Neurips.
limitations_and_societal_impact: - The result of this paper is only working for tabular setting.
- The sample complexity provided for relative entropy policy search in this paper is significantly worse than the state of the art sample complexity for actor critic and Q-learning type of algorithms which is O(1/epsilon^2).
- Need for iid sampling of the data.
review_title: null

Meta-review: This is a challenging paper, as the reviewers have a wide range of opinions about it.
We had a lot of discussions among the reviewers: there are more than 40 messages in total in the forum (including authors' responses), which is more than any other paper in my batch (most messages are private). Even though one of the reviewers changed their stance from the negative side to the positive side, the majority kept their initial viewpoints. In order to help with the final decision, I invited an expert emergency reviewer who provided a positive evaluation of this work. At the end of the day, we have 3 positive reviewers and 2 negative ones.

Several issues have been brought up. The core issues can be summarized into the following two categories. I explain the viewpoint of reviewers and provide my commentary:

1) Whether the results are novel and significant or not.

Some reviewers believe that the results are not novel or significant, yet others believe that they are.

In my viewpoint, the results are novel because they theoretically analyze one of the important RL algorithms (REPS) for the first time.
The provided convergence rates may or may not be optimal, as we do not know what the lower bound is. This is the first work with such an analysis, and I believe is an important one.

The negative reviewers' complaints regarding the novelty and significance are along these lines:

Concern: The results look suboptimal because the rates are not fast (perhaps compared to other policy search algorithms).

My take: Given that this is the first result for REPS, and we do not have a lower bound for the rate, this is not a real concern.

Concern: The results are not novel because similar papers analyzed similar algorithms. Are we going to analyze all algorithms using similar tools and claim novelty?

My take: I would argue that REPS is not any algorithm. It is one of the important RL algorithms in the past two decades, and its analysis is worthwhile.

Concern: The technical tools used in the analysis are standard; each component of the result (lemmas, etc.) have been proved elsewhere; the proofs are not creative applications of prior tools.

My take: I did not check the proofs myself, so I do not have a strong opinion about their content and technical novelty and creativity, but I do not think this is the most significant evaluation criteria for this type of paper.
Even if the proof techniques might be well-established, some of the results (Lemmas 4 and 5 and 9) appear to be novel.
How difficult is it to prove them? I do not know, but I do not think it matters much. They are not trivial corollaries of already known results.
Since NeurIPS is not a math venue, the novelty and creativity of the proof techniques are not the main consideration anyway, in my opinion.

I believe some of the reviewers have a different standard of novelty and significance in evaluating this paper from mine, and that might be the main reason for the difference in opinion.

2) The exposition should be improved.

The fact that some of the reviewers got confused about what is novel here and what is not, and the authors had to correct them in the rebuttal multiple times (a frustration that was expressed in their rebuttal too) should be a signal to the authors that maybe their paper is not written very well.
All reviewers spent a lot of time on this paper. Many of them are expert in areas closely related to the topic of this paper. The closeness of their expertise to this paper is way more than a typical RL researcher at NeurIPS. The reviews show that they tried hard to understand the paper, yet they occasionally misunderstood some important aspects of the paper, for example, the relationship of the results of this paper and the currently existing results in the literature.

This issue was not raised only by the negative reviewers. The expert emergency reviewer also believed that the writing sometimes becomes a bit dense with technical details. I shared this sentiment after reading the paper myself.

Although I realize that writing a paper that can be understood by everyone is challenging, especially a theoretical paper, I would recommend the authors to seriously consider the feedback provided by the reviewers to improve the exposition of their work.

**Evaluation:** Overall, given the novelty and significance of the paper, according to what I believe should be the novelty and significance criteria for a venue such as NeurIPS, and that we have enough positive and enthusiastic support from three reviewers, I recommend the acceptance of this paper.
I encourage the authors to revise the exposition of their paper and make it more accessible to a broader range of NeurIPS audience.
Decision: Accept (Poster)