Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new policy gradient method that is based on stochastic mirror descent. It has been shown theoretically and empirically that the method achieves more sample efficiency. 

Overall, the proposed idea is interesting. The paper has good contributions in both theoretical and algorithmic aspects to policy optimization family. The empirical results are also very promising. I have only some following concerns.

- It would be really nice if the discussions on connections to existing policy gradient methods on page 4 can be elaborated. This is to make the readers understand better how the reduction from the proposed method to an existing one can be made. It would also be more interesting after such reductions can be made, one can compare the sample efficiency of the proposed method with such state-of-the-art policy gradient methods. That means Table 1 can be extended with rows of such methods. 

- The convergence analysis in Theorem 2 and 3 are really strong, but it would be very useful if there are ablations that can reflect the trade-off between the convergence property and hyperparamters used in those theorems.

- The contribution of the Bregman distance D to the update should be worth further discussions. It is an important part of SMD, but for policy optimization one might want to see how it contributes to stabilizing the update OR policy exploration. As seen, with a different choice of D, the method is reduced to policy gradient or entropy-regularized policy optimization. Ablations without D might show some interesting results too.


- Some minor comments:
page 8: "The result in Figure 1 shows that MPO converges faster significantly and achieves a better performance than both REINFORCE and MPO." -> should be "... both REINFORCE and VPG."
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 
[Summary]
This paper proposes MPO, a policy optimization method with convergence guarantees based on stochastic mirror descent that uses the average of previous gradients to update the policy parameters. A lower-variance method, VRMPO, is then proposed that matches the best known convergence rate in the in the literature. Experiments show that (1) MPO converges faster than basic policy optimization methods on a small task, and (2) VRMPO achieves a performance comparable to, and often better than, popular policy optimization methods (TD3, DDPG, PPO, and TRPO) on MuJoCo.

[Decision]
The proposed methods are well-grounded. The experiments are, however, limited and miss important baselines discussed in previous sections. The presentation is not clear. Imprecise statements, undefined terms, and grammatical errors make the paper hard to follow. Overall, I am leaning towards rejecting the paper.

[Explanation]
Section 5 provides a comparison between the convergence rates of VRMPO and previous methods (VPG, REINFORCE, SVRPG, and HAPG). I was expecting to see a similar comparison in the experiments section but SVRPG and HAPG do not appear in the experiments although their convergence rates are comparable to VRMPO. I especially want to know how VRMPO differs from HAPG. Their convergence rates are the same and their updates look similar.

The description below Fig. 1 says that VRMPO converges faster and achieves a better performance than the baselines. While VRMPO does converge faster, all the three methods seem to converge to the same (optimal) solution.

The paper needs more polished presentation. Here are some examples for improving the writing:
- The introduction section: "our algorithm outperforms state-of-the-art bandit algorithms in...." The compared methods are RL algorithms.
- "converges faster significantly and achieves a better performance than both REINFORCE and MPO" -> "... than both REINFORCE and VPG".
- "The task is to estimate the value function of state s_1" -> This seems to be a control task where the goal is to achieve the highest return.
- "Eq.(23) has a closed implementation" -> What is a closed implementation?
- Some terms like "projected gradient" and "baseline" (in the context of variance reduction) are not defined. The compared methods in 6.2 are not described in the paper (except TD3 whose brief description appears in D.5).
- "The traditional policy gradient methods such as REINFORCE, VPG, and DPG are all the algorithms update parameters in Euclidean distance" -> "... such as REINFORCE, VPG, and DPG update parameters in Euclidean distance"
- In Table 1 the performance of VRMPO on Reacher is in bold while it is not the maximum value.
- "It is different from (Du et al., 2017)..." -> "VRMPO is different from..."
- "due to it doesn't require..." -> "because it does not require..."

[Minor comments]
- How is the bound in Eq. (18) proved?

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper proposed a variant of policy gradient algorithm with mirror descent update, which is a natural generalization of projected policy gradient descent. The authors also proposed a variance reduced policy gradient algorithm following the variance reduction techniques in optimization. The authors further proved the convergence of the proposed algorithms and some experiments are conducted to show the effectiveness of their algorithms. The paper is not written in a very good way due to many typos and misleading notations. Moreover, there seem to be some technical issues in the proofs of both main theorems.

The notations are inconsistent. In eq (14) the trajectory index is k, while in eq (16) the index changed to n. In eq (28), the trajectory is denoted by $\tau_j^t$, while in the algorithm, there is no index $t$ in $\tau_j$.

Definition of P in eq (36) seems to overlap with that of $\mathcal{G}$ in eq (10), which means the same quantity was defined twice using two different notations.

Section 3.1 is almost the same as in Ghadimi et al., (2016), both the theorem and remarks. Since this is not a new finding, I suggest the authors to simplify the current statement in this subsection.

In Theorem 1 & 2, the authors used the criteria $\mathbb{E}[\|\mathcal{G}(\theta_n)\|_2^2]$ to establish the convergence result. However, they used $\mathbb{E}[\|\mathcal{G}(\theta_n)\|_2]$ to establish the convergence result in Theorem 3. This is kind of confusing because in different criteria, the complexity result will be different. 

It seems that eq (32) is the same as eq (28). Can the authors elaborate the differences discussed in the paragraph after eq (32) in more detail? 

In eq (40), $\hat g_k$ is defined as the average gradient over all the iterates up to $k$, which means $\hat g_k$ is a function of $\theta_1,\ldots,\theta_k$. But $g_k$, according to eq (21) in Algorithm 1, is just defined based on the current policy parameter $\theta_k$. I am skeptical why these two terms will be equal. This seems to be a technical issue of the whole proof of Theorem 2. 

The derivation in (55) seems incorrect. In particular, the authors called Lemma 3, which is the result in Fang et al. (2018). However, the recursive gradient is defined differently in the current paper and in Fang’s paper. In Fang’s paper, at different iterations, the data are sampled from an unknown but fixed data distribution. But in this paper, since the data are sampled from the current policy which varies at each iteration, the data distribution is changing all the time. Therefore, Lemma 3 does not hold in the setting of this paper. 

In all the experiments, it is strange that the proposed VRMPO was not compared with any of the other variance reduced algorithms listed in Table 1. I think it would be more convincing to demonstrate the improvement in Table 1 by comparing the proposed VRMPO with at least one other variance reduced algorithm.

Other comments:

1. On page 15, the first sentence of the proof: “trjecories” -> “trajectories”
2. What is $\mathcal{J^*}$ in eq (39)? It was not defined in the paper.
3. In the statement of Lemma 3, the authors said “telescoping Eq. (3) ...” However, Eq (3) in this paper is the definition of policy gradient. I assume this is a typo? 
4. What is $\epsilon_1$ in eq (50)? It seems that this term does not appear in Lemma 4.

====after rebuttal====
Thanks for the authors' response. I am not satisfied with their response since they did not directly answer many of my questions about the technical flaws in this paper. 

The response of the authors on the difference between estimator in Shen et al (2019) and the estimator in this paper is incorrect. The estimator in Shen et al. (2019) can also be constructed recursively based on G_0. 

The authors also claimed that equation (40) is correct. However, this is not true. Although the authors removed $\hat g_k$ from equation (40), they still used the property that $\hat g_k$ is an unbiased estimator in the equation after (40). Note that $\epsilon_k$ is defined based on $\hat g_k$. Therefore, the proof is still problematic. The authors did not show how to fix it.

A more important issue of the direct use of Lemmas from Fang et al. (2018) is not fixed either. In their response, the authors simply changed the data generation in the inner loop of their algorithm such that all the iterates generate data from the initial policy $\pi_{\theta_k,0}$. However, this will cause the expectation of all the stochastic gradients used in their proof to be equal to the true policy gradient at the initial point, i.e., $\nabla J(\theta_{k,0})$. In other words, they can never obtain the full gradient $\nabla J(\theta_{k,t})$ even though their goal is to bound $\|\theta_{k,t+1}-\theta_{k,t}\|^2$ which definitely requires an approximation of $\nabla J(\theta_{k,t})$. Therefore, the issue cannot be fixed by simply using the same distribution in all the inner loop iterates. I suggest the authors to read more carefully the paper by Fang et al. (2018) and Papini et al. (2018) to understand the difference in the two settings.

review_title: Official Blind Review #2

Meta-review: This paper proposes a new policy gradient method based on stochastic mirror descent and variance reduction. Both theoretical analysis and experiments are provided to demonstrate the sample efficiency of the proposed algorithm. The main concerns of this paper include: (1) unclear presentation in both the main results and the proof; and (2) missing baselines (e.g., HAPG) in the experiments. This paper has been carefully discussed but even after author response and reviewer discussion, it does not gather sufficient support.

Note: the authors disclosed their identity by adding the author names in the revision during the author response. After discussion with PC chair, the openreview team helped remove that revision during the reviewer discussion to avoid desk reject. 

Decision: Reject