Improving sample efficiency has been a longstanding goal in reinforcement learning. In this paper, we propose the VRMPO: a sample efficient policy gradient method with stochastic mirror descent. A novel variance reduced policy gradient estimator is the key of VRMPO to improve sample efficiency. Our VRMPO needs only O( −3 ) sample trajectories to achieve an -approximate first-order stationary point, which matches the best-known sample complexity. We conduct extensive experiments to show our algorithm outperforms state-of-the-art policy gradient methods in various settings.
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.