Policy Optimization with Stochastic Mirror Descent
Authors: Long Yang
Gang Zheng
Zavier Zhang
Yu Zhang
Qian Zheng
Jun Wen
Gang Pana sample efficient policy gradient method with stochastic mirror descent.
Venue:  (2020)
Keywords: reinforcement learning
policy gradient
stochastic variance reduce gradient
sample efficiency
stochastic mirror descent

Abstract: Improving sample efficiency has been a longstanding goal in reinforcement learning.
In this paper, we propose the $\mathtt{VRMPO}$: a sample efficient policy gradient method with stochastic mirror descent.
A novel variance reduced policy gradient estimator is the key of $\mathtt{VRMPO}$ to improve sample efficiency.
Our $\mathtt{VRMPO}$ needs only $\mathcal{O}(\epsilon^{-3})$ sample trajectories to achieve an $\epsilon$-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.

Under review as a conference paper at ICLR 2020
POLICY OPTIMIZATION WITH STOCHASTIC MIRROR DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Improving sample efficiency has been a longstanding goal in reinforcement learn- ing. 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 sample trajectories to achieve an c-approximate first-order stationary point, which matches the best-known sample complexity. We conduct extensive experiments to show our algorithm outperforms state-of-the-an policy gradient methods vari- ous settings.
INTRODUCTION
Reinforcement learning (RL) is one of the most wonderful fields of artificial intelligence. and it has achieved great progress recently (Mnih et al., [211 Silver et al.] (0017). To learn the optimal policy from the delayed reward decision system is the fundamental goal of RL. Policy gradient methods
(Williams 1992] Sutton et al. (000) are powerful algorithms to learn the optimal policy.
Despite the successes of policy gradient method, suffering from high sample complexity is still critical challenge for RL. Many existing popular methods require more samples to be collected for each step update the parameters (Silver al. 2014 Lillicrap al. 2016 Schulman al. 2015 Mnih et al. 2016)] Haarnoja et al.] 2018), which partially reduces the effectiveness of the sample. Although all the above existing methods claim improves sample efficiency, they are all empirical results which lack strong theory analysis of sample complexity.
To improve sample efficiency, this paper, we explore how to design an efficient and stable algo- rithm with stochastic mirror descent (SMD). Due to its advantage of the simplicity of implemen- tation, low memory requirement, and low computational complexity (Nemirovsky
Yudin 1983] Beck & Teboulle, 2003 Lei & Tang 2018), SMD is one of the most widely used methods in machine learning. However,
not sound to apply SMD to policy optimization directly, and the challenges two-fold: (I) The objective of pelicy-based RL is a typical non-convex function, but Ghadimi (ct al. (2016) show that it may cause instability and even divergence when updating the parameter of non-convex objective function by SMD via single batch sample. (IT) Besides, the large variance of gradient estimator is the other bottleneck of applying SMD to policy optimization for improving sample efficiency. In fact, in reinforcement learning, the non-stationary sampling process with the environment leads to the large variance of existing methods on the estimate of policy gradient, which results in poor sample efficiency (Papini et al. 2018 Liu al. 2018).
Contributions To address the above two problems correspondingly. in this paper (I) We analyze the theoretical dilemma of applying SMD policy optimization. Our analysis shows that under the common Assumption [ for policy-based RL. designing the algorithm via SMD directly can not guarantee the convergence. Hence, we propose the MPO algorithm with a provable convergence guarantee. Designing an efficiently computable, and unbiased gradient estimator by averaging its historical policy gradient is the key to KPO. (II) We propose the VRMPO: a sample efficient policy op- timization algorithm via constructing a variance reduced policy gradient estimator. Specifically, we propose an efficiently computable policy gradient estimator, utilizing fresh information and yielding more accurate estimation of the gradient w.r.t the objective, which is the key to improve sample efficiency. We prove VRMPO needs O sample trajectories to achieve an e-approximate first- order stationary point (c-FOSP) (Nesterov 2004 To our best knowledge, VRMPO matches the

---

Under review as a conference paper at ICLR 2020
best-known sample complexity among the existing literature. Besides, conduct extensive periments, which further show that our algorithm outperforms state-of-the-are art bandit algorithms in various settings.
2
BACKGROUND AND NOTATIONS
2.1 POLICY- BAASED REINFORCEMENT LEARNING
We consider the Markov decision processes M A. R,,,R Po: (o:T), where S is state space, A action space; At time I, the agent is in a state S, E and takes an action A, A, then it receives feedback Re+1; pa P(s [s, a) E P is the probability of the state transition from taking E A: The bounded reward function R. S A [- R, RJ. RS BIRe++ 8, Ar a); Po S + 1] is the initial state distribution and 7 E (0, 1) is discounted factor. Policy mo(a H, is a probability distribution on S x A with the parameter 0 E Rº. Let T = {st, dz, Te+1 Je- be trajectory, where So Pu(Su), a₂ x0(+|s)), r++1 R(st, at), S1t1 P(-|st, and H, the finite horizon of r. The expected return ((TO) is defined as:
under
((0) J(TT) = P(T)0))(()dd= = E,NOO [[(T]]-
(1)
where P(r(0) = (0)) II P(s++1 118,, as (t) is the probability of generating R(T)
=
EED 7'r+41 the accumulated discounted return.
Let [(0)- J(A), the central problem of Policy-based RL to solve the problem:
8 = arg max J(0) - l" = arg min [
(2)
9
Computing the (0) analytically, have
H
((0) E
V log To (a.ls:))
(3)
t=
For any trajectory т, let g J(O).. Vanilla policy gradient (VPG) is straightforward way to solve problem (2):
Σ H
Vo
which is an unbiased estimator of
=
< 0 + og(r())
where a is step size.
Assumption 1. (uutoon et al. 2000 Papini et al. 2018) For euch pair (8, u), any O E RP, and all
components j, there exists posilive constants G, F s.l.
2²
Ve, log le SG
log no (a|s)) S
(4)
00,00,
According to the Lemma B.2 of Papini al. 2018 ie., (0:) - v.J(O2) < L
Assumption | iiplies (J( is L-Lipschiz,
0g where
I. = RHG + F)/(1 7),
(5)
Besides, Assumption I limplies the following property of the policy gradient estimator.
Lemma (Properties of stochastic differential estimators (Shen et al. 2019)). Under Assumption
1 for any policy ma and 7 Te. we have
R²R² def o2
- -
<
(6)
(1 (1-7)4
2.2 STOCHASTIC MIRROR DESCENT
Now, we review some basic concepts of SMD; in this section, the notation follows (Nemrovski
al. 2009). Let's consider the stochastic optimization problem,
min (f(() E (F; BED,
2

---

Under review as a conference paper at ICLR 2020
where D9 E R" is nonempty convex compact set, is random vector whose probability dis- tribution. μ is supported on E I2 and F : Do x E + R. We assume that the expectation [)) = J= (0: ()du(E) is well defined and finite-valued for every 0 E Do- Definition 1 (Proximal Operator (Moreau 1965)). T a function defined on a closed convex X, and a > 0. MM, (z) is the proximal operator of which is defined as:
M arg (T(()) xEX
D. 2)). a
(8)
where (x)x) is a continuously canttinoouss-dfffeeenttbbu (-strictly convex finntiio:: (I (x- Vv(() - (b(y)) <|| yll?, Ç > 0, D is Bregman distance: (z, y) = exz) (())-v(y)- (V)()(V(())))))))))))))))))))))) y) Vz,y
Stochastic Mirror Descent The SMD solves by generating an iterative solution as follows,
1 ((0) (0.) arg min (ge. 0) + att 0.41 M
(0, 0,)).
OED,
where 0z > is step-size, {(0) (gr, 0) is the first-order approximation of [(0) fc. 91 g( Er) is stochastic subgradient such that g(O,) = (lg(0, &.)] E @f(0)leze,, {&r12 represents a draw form distribution and (0) {ol f(w) s 90 - w), Ve E dom(f))
1 If we choose (b(x)- マ 1=:12 which implies De (1t v) 2 vl since then iteration (9) is the
proximal gradient (Rockafellar 1976) view of SGD. Thus, SMD is a generalization of SGD.
Convergence Criteria: Bregman Gradient Bregman gradient is generation of projected gradi- ent (Ghadimi et al.) 2016). Recently, Zhang & He (2018); Davis & Grimmer (2019) develop it to
measure the convergence of an algorithm for the non-convex optimization problem. Evaluating the
difference between each candidate solution x and its proximity is the critical idea of Bregman gra- dient to measure the stationarity of x. Specifically, let X' be a closed convex set on R", a 0, T(x) is defined on X. The Bregman gradient of T at E X is:
g (x) = a (x Mwr(()))
(10)
where M (a is defined in Eq. If (x)) | 122. then x" is critical point of T if and only if
(2,) = VT(x*) = 0 Bauschkee et al. (2011 Theorem 27.1). Thus, Bregman gradient (10 is
generalization of gradient. The following Remark [ is helpful for us to understand the significance of Bregman gradient, and it gives some insights understand this convergence criterion.
Remark 1. Let T be a convex function, by the Proposition 5.4.7 of Bertsekas (2009; x² is a sla- tionarity point of T if and only if
0 a(T + 6x)(z"),
(11)
where (x(-) is the indicator function on X. Furthermore, suppose (xx)) is twice continuously differ- entiable, let ā (x)( by the definition of proximal operator M) we have
0 DT 5x) (VV(E) Vi((x)) ② a(T + +x))() + ogH, ( (x)))
(12)
Eq.(*) holds due the furst-order Taylor expansion of V Vub(x). By the criteria of 11, if (x) Rs O.
Eq. implies the origin point 0 is near the set 0(T + (Z), i.e., is close stationary point.
In practice we choose T(0)- = (O:), 0). since then discriminant criterion 12 is suitable to RL problem (2). For the non-convex problem (2). we are satisfied with finding an e-approximate First-Order Stationary Point (e-FOSP) (Nesterov 2004), denoted by 0., such that
| (0.)l S.
(13)
POLICY OPTIMIZATION WITH STOCHASTIC MIRROR DESCENT
In this section, solve the problem via SMD. Firstly, we analyze the theoretical dilemma of applying SMD directly to policy optimization. Then, we propose a convergent mirror policy optimization algorithm (MPO).
3

---

Under review as a conference paper at ICLR 2020
3.1 THEORETICAL DILEMMA
Let T = 1T be a collection of trajectories, ~ To. we receive gradient information:
Hrg
-g(Tx(0k))
Vo log (a)
(14)
t=
then by SMD ② to solve 2 for each S < N we define the update rule as follows,
0k+1 M oa.l--(r1 () (0x) arg min ( + - D. (0,00))) (x),
(15)
OEk
where ag > is step-size and other symbols are consistent to previous paragraphs. Due to (0) non-convex, according (Ghadimi al. 2016), a standard strategy for analyzing non-convex
optimization methods is to pick up the output NN randomly according to the following distribution over (1,2,..,,
P(ON 0n) Can La
(16)
Σx (5ax La
where Ç is defined in Definition 1 0 an < [..m 1.2.....
Theorem 1. (Ghadimi et al. 2016 Under Assumption [ and the total trajectories are {Tk 1 k=1 Consider the sequence {0x 22= k=1 generated by
15), the output x = follows the probability mass distribution of 16). Let < ag < f. E(g, u) (g, u), the term and a are defined Eq. and ( correspondingly. Then, we have
(J(Ag) - -((0)) E Osk
El an. M(-n a.,) (0m)) (0,))
(17)
Ek=i(Cave - Laz)
where is short for (nn)
Unfortunately, it is worth to notice that the lower bound of (17 reaches d² k= ag
Ex=1
(18)
-
which can not guarantee the convergence of the iteration (5). no matter how the step-size ag is specified. Thus, under the Assumption [ generating the solution {0x) according to (15) and the output following (16) lack strong convergence guarantee.
An Open Problem The iteration is very important and general scheme that unifies many ex-
isting algorithms. For example, the mirror map (i) = - 11012, then the update (15) is reduced to policy gradient algorithm (Sutton al. 2000) which is widely used modern RL. The update (15) is natural policy gradient (akkade 2002 Peters & Schaal 2008 Thomas et al. 2013) if we choose (8.a) (8, entropy function (Shannon) 1948). ). then D., is known
mirror map (0) 100 FO)0, where
Ey~ea Vo log No
V log ne
8, ax)) is Fisher in-
formation matrix. If th is SoltzzannnSShanen
as KI. divergence and update (15) is reduced to relative entropy policy search (Peters et al.) 2010) Fox et al.) 2016; Chow et al. 2018). Despite the vast body of work around above specific meth- ods, current works are scattered and fragmented both theoretical and empirical aspects (Agarwal et al. 2019). Thus, it is of great significance to establish the fundamental theoretical convergence properties iteration (15).
Please notice that for the non-convexity of problem 2 the lower bound of 18 holds under As- sumption] [ is natural to ask:
What conditions guarantee the convergence of scheme 15
This is an open problem. Although, the iteration 15) is intuitively a convergent scheme, as dis- cussed above that particular mirror maps i can lead (15) to some popular empirically effective RL algorithms; there is still no generally complete theoretical convergence analysis of (15). Such con- vergence properties not only help us to understand better why those methods work but also inspire us design novel algorithms with the principled approaches. We leave this open problem and the related questions, e.g.. how fast the iteration (15) converges to global optimality or its finite sample analysis, as future works.
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Mirror Policy Optimization Algorithm (MPO)
1: Initialize: parameter 0,, step-sizear > 0, 90 = O, parametric policy To(a)s), and map v.
2: for k ==1 to N do
3: Generate trajectory
{st, de, re+1 Je= To,, temporary variable yo 0.
Hru
9k
Vo log (a (((x))
(21)
t=)
9k t k 9k + (1
k g
(22)
xk+1 t arg min {<- w) + (D((w, 0k)
(23)
4: end for
5: Output: dy according (6
3.2 AN IMPLEMENTATION WITH CONVERGENT GUARANTEE
In this section, we propose a convergent implementation defined as follows, for each step k:
1 (v, 0x)),
8 8 = M anil-án .x. 8) (0x) = arg minn((-9s 0)
(19)
1E
where ÿN is arithmetic mean of previous episodes' gradient estimate {g(T; [4))
4 9 Σ (.).))).
(20)
We present the details of an implementation in Algorithm Notice that Eq. (2) is an incremental
implementation of the average (20). thus, (22) enjoys lower storage cost than (20).
For given episode, the gradient flow 22 2 of MPD is slightly different from the traditional VPG,
REINFORCE (Williams 1992). A2C (Mnih et al. 2016) or DPG (Silver et al. 2014) whose gradient
estimator follows (14) that is according to the trajectory of current episode, while our MPD uses an arithmetic mean of previous episodes' gradients. The estimator (14)
natural way to estimate k=D log To (o(a))s))R(()) i.e. using single current trajectory to estimate policy gradient. Unfortunately, under Assumption [], the result of (18) shows using (14) with SMD lacks guarantee of convergence. This is exactly the reason why we abandon the way (4) and turn to propose (22) to estimate policy gradient. We provide the convergence analysis of our scheme (20) in the next Theorem
the term (()( -
Hr,
Theorem (Convergence Rate of Algorithm I. Under Assumption 7 and the total trajectories are (Tr Consider the sequence {0x H generated by Algorithm) | and the output 0N = 6 follows the distribution of Eq.(16). Let 0 < as < &, E(g, u) (g. u), the term L and are defined in Eq 5
and Eq. correspondingly. Let ON = Eh Is. where 9: Then we have
L.z H.; Vo log R((:)
T (. (0,)) (0n)l99 ((01)) Ek=1 a6
ElI 2
(24)
E - Laaz)
We prove the proof in Appendix A. Let C/2L, then, Eq 24 is Elll
-.. (0a)
<
(((0))))(e))) E N/nN/N). Our scheme of MPO partially answers the previous
NC open problem through conducting new policy gradient estimator.
4 VRMPO: A VARIANCE REDUCTION IMPLEMENTATION OF MPO
In this section, we propose a variance reduction version of MPO: VRMPO. In optimization commu- nity, variance reduction gradient estimator is very popular method with provable convergence
5

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Variance- Mirror Policy Optimization (VRMPO).
1: Initialize: Policy (a(a))) with parameter by mirror map sistep--ize on 0, epoch size K m..
2: for k = to K do
3: 0z.0 0k-1, 1. generate TA (ni) #0,.0
4: B fk.0 agGR.
where G =
= - E 9(T.(Ok,.).
5: for = 1 to m 1 do
6: Generate {r) To,.
1 N₂
Gk = Gk + g(Ty((0,t) + 0(T5|02,,-1)
Σ
(25)
N₂
- Dw On
1
0,1111 = arg min (Gk,eek w) +
(26)
Ocke
7: end for
8: 0g = 0k.t with t chosen uniformly randomly from {0, 1,... m).
9: end for
10: Output: 0x-
guarantee (Reddi al. 2016 Fang et al. 2018 Horváth & Richtárik 2019). Inspired by the above works, now, we present an efficiently computable policy gradient estimator. For any initial lg. let (7 ( Tep we calculate the initial gradient estimate as follows,
N Σ 1=1
Go = - del
0o).
(27)
N
Let 01 0. aGo, for each time N+, let { define the policy gradient estimate G2 and the update rule of parameter as follows,
be the trajectories generated by Teo
N
G. = G.-1 +
Σ
(-g(T)(0,) o(1)(0-1)))
(28)
N
1
0+11= arg mig 0) + (0. 0.))
(29)
where a > is step-size. We present more details in Algorithm
In 28). -g(T((06) and 9(T])0(--1 (t-1) share the same trajectory { =- which plays critical role
in reducing the variance of gradient estimate (Shen et al. 2019 Besides, it is different from
20 we admit a simple recursive formulation conduct the policy gradient estimator G, (28).
which captures some techniques from SARAH (Nguyen et al.] 2017a|b). At each time t. the term N
N و (- (-9(T)10.)- + 9(7)(0--)) can be seen an additional "noise" for the policy gradient es- timate. A lot of practices show that conducting a gradient estimator with the additional noise enjoys
a lower variance and speeding up the convergence (Reddi et al. 2016 Schmidt al. 2017 Nguyen
et
al. 2017a b) Fang et al. 2018).
Theorem 3 (Convergence Analysis of Algorithm
2 The sequence (ūx) is generated accord-
ing to Algorithum 2 Under Assumption 7 let <
32 for any positive scalar the batch size of
5
the trajectories of outer loop N1 = (LLC +
(1 + 32द2) E. the iteration times of in- 2(C- 2
ner loop m - = N₂ /
8TC2
+
2(0- 32
(1
+
उेद
σ the iteration times of outer loop
K [((E J(8'))
-(()))
(1
1
and step size as 1. Then, Algorithm outputs the
(m 1)(5 - 5))
2'
point 0x achieves
E 1
(0k) Sc
(30)
a ((

---

Under review as a conference paper at ICLR 2020
By the result in Theorem 3 under Assumption to achieve the c-FOSP, Algorithm 2 (VRMPO) needs
K (Ni + (m-11) -6)
(1+
T6Ç7 1+
324 -
(<-#2)
8T.
(+)) random trajectories. As far we know, our VRMPO matches the best-known sample complex-
ity as the HAPG algorithm (Shen et al. 2019).
In fact, according to (Shen et al. 2019). REINFORCE needs O(e=)) random trajectory trajectories to achieve the e-FOSP, and no provable improvement on its complexity has been made so far. The same order of sample complexity of REINFORCE shown by Xu et al. (2019). With the additional Teo (ax 9h.)
assumptions Var
I
Varlu(=|0)] < +o0, Papini et al. (208) show that the SVRPG To, (an (sh))
achieves the sample complexity of O(c-)). Later, under the same assumption as (Papini et al. 2018), Xu et al. (019) reduce the sample complexity of SVRPG to O(e 3) ). We provide more details of the comparison in Table I, from which is easy to see that our VRMPO matches the best-known sample complexity with least conditions.
RELATED WORKS
Stochastic Variance Reduced Gradient in RL Although it has achieved considerable successes in supervised learning, stochastic variance reduced gradient optimization is rarely a matter of choice in RL. To our best knowledge, Du et al. (2017) firstly introduce SVRG (Johnson & Zhang] 2013) to off-policy evaluation. Du et al. (017)) transform the empirical policy evaluation problem into (quadratic) convex-concave saddle-pons point problem, then they solve the problem via SVRG straightfor-
wardly. Later, to improve sample efficiency for complex RL. Xu et al. (2017) combine SVRG with TRPO (Schulman al., 2015). Similarly, Yuan et al. (2019) introduce SARAH (Nguyen et al.) (017a) to TRPO to improve sample efficiency. However, the results presented by Xu et al. (2017) and Yuan jet al. (2019) are empirical, which lacks a strong theory analysis. Metelli al. (2018) present a sur- rogate objective function with Rényi divergence (Rényi et al. 1961) to reduce the variance caused by importance sampling.
Recently, Papini et al. (2018) propose stochastic variance reduced version of policy gradient (SVRPG), and they define the gradient estimator via important sampling.
C(-9(1) ( + II Too Too (anlsn) 1=1
G. G. +
To, (an|sn) g( ((T))0--1))
(31)
where G--1 is an unbiased estimator according to the trajectory generated by πØ Although the above algorithms are practical empirically, their gradient estimates are dependent heavily on impor- tant sampling. This fact partially reduces the effectiveness of variance reduction. Later, Shhnn et al.) (019) remove the important sampling term, and they construct the gradient estimator as follows,
1 N
G G +
Σ
((-(7)100) 9(7)10011)).
(32)
It is different from (Du et al. 2017 Xu et al. 2017 Papini et 2018 Shen al.) 2019) the proposed VRMPO admits a stochastic recursive iteration to estimate the policy gradient, see Eq (88 Our VRMPO exploits the fresh information to improve convergence and reduce variance. Besides, VRMPO reduces the storage cost significantly due to it doesn't 't require to store the complete historical information. We provide more details of the comparison in Table 1.
Baseline Methods for Variance Reduction of Policy Gradient Baseline (also also known as con-
trol variates (Cheng et al.) (019a) or reward reshaping (Ng et al. 1999 Jie & Abbeel 2010 is a widely used technique to reduce the variance (Weaver & Tao. [000]] Greensmith et al. 2004). For example, A2C (Sutton& & Barto 1998, Mnih et al.) (016) introduces the value function as baseline function, Wu et al. 2018)) consider action-dependent baseline, and Liu et al. (2018) use the Stein's 's identity (Stein 1986) as baseline. Q-Prop (Gu et al. 2017) makes use of both the linear dependent baseline and GAE (Schulman et 2016) to reduce variance. Cheng et al. (201b)) present predictor- corrector framework that can transform a first-order model-free algorithm into a new hybrid method that leverages predictive models to accelerate policy learning. Mao al. (2019) derive bias-free,
7

---

Under review as a conference paper at ICLR 2020
Algorithm
Estimator
Conditions
Complexity
VPG/ /REINFORCE 2018
Eq. 14
Assumption
War(g(T[0) < +oc
O(e
SVRPG Papini et
Eq.31
Assumption
Var(ar) (arl:l)) +o0
O
SVRPG
Xu al. 2019
Eq.
Assumption
+o0
0(e-10/3)
HAPG Shen al. 2019
Eq.
Assumption
O(e
VRMPO (Our Works)
Eq. (28)
Assumption
O
Table 1: Comparison on complexity required to achieve [|V]())]
Σ c. Particularly, if (b(0) =
||
then the result (30) of our VRMPO measured by gradient. Beside, Pt [ No, (ox
def Reo (ox]=s) (sa.
input-dependent baseline to reduce variance, and analytically show its benefits over state-dependent baselines. Recently, Grathwohll et al. (2018); CChen et al. (2019a) provide a standard explanation for the benefits of such approaches with baseline function.
However, the capacity all the above methods is limited by their choice of baseline function (Luu et al. 2018). In practice, it is troublesome to design proper baseline function to reduce the variance of policy gradient estimate. Our VRMPO avoids the selection of baseline function, and uses a current sample trajectory to construct novel, efficiently computable gradient estimator to reduce variance and speed convergence.
EXPERIMENTS
6.1 NUMERICAL. ANALYSIS OF MPO
In this section, we use experiment to demonstrate MPO converges faster than VPG/REINFORCE. Then, we test how the mirror map & effects the performance MPO.
Performance Comparison We compare the convergence rate of MPO with REINFORCE and VPG em- pirically on the Short Corridor with Switched Actions domain (Chapter 13, Sutton & Barto (2018); We provide some details in Appendix B). The task is to estimate the value function of state S1, ((s)) = Go ~3 11.6.
Figure 1: Comparison the performance of MPO with REINFORCE and VPG on the short-corridor grid world domain.
-00
Total reward episdee: Go
In this experiment, use features ((8, right) [1,0]T and Φ(s, l(ft)
-30
[0, 8 E S.
-40
Let Lg(s,a) A. where = (right, left). Ta(aas) is exponential soft-max distribution defined as exp(Lo(s,a)
o (s, (s. S
-11.6
-50
VPG
-60
REINFORCE
To Ee E expl Lo(s,')) The initial pa-
-70
MPO
rameter 0g -1.0,, 0.5,. where U is uniform distribution.
100
200
100
400
100
800
Episode
Before we report the experimental results, it is necessary to explain why we only use VPG and REIMFORCE as the baseline to compare with our MPO. VPG/REINFORCE is one of the most basic policy gradient methods in RL, and extensive modern policy-based algorithms are derived from VPG/REINFORCE, Our MPO is a novel framework via mirror map to learn the parameter, see 23 Thus, it is natural compare with VPG and REINFORCE. The result in Figure/ 1 shows that MPO converges faster significantly and achieves a better performance than both REINFORCE and MPO.
Effect of Mirror Map & We use 1é L, norm test how the mirror map affects the performance of MPO. Particularly, the iteration (23 reduces to gradient descent update if ab = norm... For ab = lp-
norm, Fq. (3) has closed implementation. Let o (y) (E 1y: ()) / be the conjugate map of db.
8

---

Under review as a conference paper at ICLR 2020
Avanage PapaaggePna Phoum
Avcray Ruzam
beet
-200
y ty-morm
4 fo-nrrm
fy-norm
Ey-n
Fy-oom
f4 fomorrm
= l norm Es-norm
f. nom
4y-rrrm
tyom
4000
300
000 Epllade
100
300
20p
300
Ope
Epiaade
(a) MountainCar-vl
(b) Acrobot-v1
(c) CartPole-vl
Figure 2: Comparison of the empirical performance of MPO between non- -on-Euclidean distance (p # 2) and Euclidean distance (p 2) on standard domains: MountainCar, Acrobot and CartPole.
where p-1 + 1, P.P 1. According (Beck & Tehoulle 2003
23
equivalent
Bx+1 Val (Vi(0;)) + augk))
where (x))(x) and V4z are p-norm link functions sign(a, 12, (v)
(Gentile
2003 E Vel(()) =
sign(y, N2, and is coordinate index of the vector Váù, Val".
Iill
To compare fairly, we use the same random seed, and let run in [P] (1.1, 1.9, 2, 4, 5}. For the non-Euclidean distance case, we only show p 3, 4,5, and "best", where p= "best" value is that case it achieves the best performance among the set [P]. For the limitation of space, we provide more details of experiments in Appendix D.1.
The result in Figure 2 shows that the best method is produced by nun-Euelidean distance, not the Euclidean distance. The traditional policy gradient methods such as REINFORCE, VPG, and DPG are all the algorithms update parameters in Euclidean distance. This simple experiment gives us some lights that one can create better algorithms by combining the existing approaches with non-Euclidean distance, which is interesting direction, and we left it future work.
6.2 EVALUATE VRMPO ON CONTINUOUS CONTROL TASKS
In this section, we compare VRMPO on the MuJoCo continuous control tasks (Todorov et 2012 from OpenAl Gym (Brockman et al. 2016). We compare VRMPO with DDPG (Lillicrap et al., 2016), PPO (Schulman et al. 2017). TRPO (Schulman et al. 2015), and TD3 (Fujimoto et al. 2018). For fairness, all the setups mentioned above share the same network architecture that computes the policy and state value. We run all the algorithms with ten random seeds. The results of max-average epoch return are present in Table 2] and return curves space, we present all the details of experiments and some practical tricks for the implementation of VRMPO in Appendix D.2-D.5; in this section, we only offer experimental results. We evaluate the performance of VRMPO by the following three aspects: score performance, the stability of training, and variance.
shown in Figure 3. For the limitation of
Score Performance Comparison From the results of Figure 3 and Table 2, overall, VRMPO outper- forms the baseline algorithms in both final performance and learning process. Our VRMPO also learns considerably faster with better performance than the popular TD3 on Walker2d-v2, HalfCheetah-v2, H2pper-v2, Inv Dwwuubbeeenduuuum-// and Reacher-v2 domains. On the InwDDubblePenduluumy task, our VRMPO has only a small advantage over other algorithms. This is because the InyPendulum-v2 task relatively easy. The advantage of our VRMPO becomes more powerful when the task is more difficult. It is worth noticing that the HalfCheetah-v2 domain, our VRMPO achieves significant max-average score 16000+, which outperforms far more than the second-best score 11781.
Stability The stability of an algorithm is also important topic in RL. Although DDPG exploits the off oollco sample, which promotes its efficiency in stable environments, DDPG is unstable on the Reacher-v2 v2 task, while our VRMPO learning faster significantly with lower variance. DDPG fails to make any progress on Inv wwwulleeendduuummy domain, and the result is corroborated by the work DDai et al. 2018). Although TD3 takes the minimum value between a pair of critics to limit overes-

---

Under review as a conference paper at ICLR 2020
1900
600
1400
TRPOO
2000
1000
190
Walker2d-v2
(b) HalfCheetah-v2
(c) Reacher-v2
1990
3000
2000
1509
VISFO
VIND
200
0070
790
(d) Hopper-v2
(e) LnwDouubleenndulun-22
(i) InyPendullum-22
Figure 3: Learning curves for continuous control tasks. The shaded region represents the standard
deviation the score over the best three trials. Curves are smoothed uniformly for visual clarity.
Environment
Our VRMPO
TD3
DDPG
PPO
TRPO
Walker2d-v2
5251.83
4887.85
5795.13
3905.99
3636.59
HalfCheetah-v2
16095.51
11781.07
8616.29
3542.60
3325.23
Reacher-v2
-0.49
-1.47
-1.55
-0.44
-0.66
Hopper-v2
3751.43
3482.06
3558.69
3609.65
3578.06
LnwDDobblePendulum-2
9359.82
9248.27
6958.42
9045.86
9151.56
Inv InvPPendulum-v2
1000.00
1000.00
907.81
1000.00
1000.00
Table 2: Max-average return over 500 epochs, where 5000 iterations for each epoch. Maxi- mum value for each task is bolded.
timation, it learns severely fluctuating in the InvertedDaublePenddulums environment. In contrast, VRMPO is consistently reliable and effective in different tasks.
Variance Comparison As we can see from the results Figure 3, our VRMPO converges with considerably low variance in the Hopper-v2, inwDoublePenduulms the asymptotic variance of VRMPO is slightly larger than other algorithms HalfCheetah-v2. the final performance of VRMPO outperforms all the baselines significantly. The result in Figure also implies conducting a proper gradient estimator not only reduce the variance the score during the learning but speed the convergence of training.
and Reacher-v2. Although
CONCLUSION
In this paper, we propose the mirror policy optimization (MPO) by estimating the policy gradient via dynamic batch-size of historical gradient information. Results show that making use of historical gradients estimate policy gradient is more effective speed convergence. We also propose variance reduction implementation for MPO: VRMPO, and prove the complexity of VRMPO achieves 3c.-3). To our best knowledge, VRMPO matches the best-known sample complexity so far. Finally, we evaluate the performance of VRMPO the MuJoCo continuous control tasks, results show that VRMPO outperforms matches several state-of-art algorithms DDPG, TRPO, PPO, and TD3.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. arXiv preprint arXiv: /90:: 008.00261, 2019.
Navid Azizan and Babak Hassibi. Stochastic gradient/mirror descent: Minimax optimality and im- plicit regularization. International Conference on Learning Representations, 2019.
Heinz H Bauschke, Patrick L Combettes, al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Dimitri P Bertsekas. Convex optimizution theory. Athena Scientific Belmont, 2009.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint 1rXiv:1606.01 2016.
Ching-An Cheng, Xinyan Yan, Nolan Wagener, and Byron Boots. Fast policy learning through imitation and reinforcement. In Conference on Uncertainty in Artificial Intelligence, 2018.
Ching-An Cheng, Xinyan Yan, and Byron Boots. Trajectory-wise control variates for variance re- duction in policy gradient methods. arXiv preprint arXiv: 1908. 03263, 2019a.
Ching-An Cheng, Xinyan Yan, Nathan Ratliff, and Byron Boots. Predictor-corrector policy opti- mization. In Proceedings of International Conference on Machine Learning, 2019b.
Yinlam Chow, Ofir Nachum, and Mohammad Ghavamzadeh. Path consistency learning in tsallis entropy regularized mdps. In International Conference on Machine Learning, pp. 978-987, 2018.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. International Confer- on Machine Learning, 2018.
Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nons- mooth, nonconvex problems. SIAM Journal on Optimization, 1908):198- 2019.
Simon Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, 2017.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances Neural Information Processing Systems, pp. 686-696, 2018.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. In Conference on Uncertainty in Artificial Intelligence, 2016.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. International Conference on Machine Learning, 2018.
Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265-299, 2003.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical 267-305, 2016.
ProptaaaaiaaaPPPPaaaaaaaiaaaaaa Programming, 155(1-2):
Will Grathwohl, Dami Choi, Yuhuai Wu. Geoffrey Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. International Conference Learning Representations, 2018
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5(Nov):4471-1530, 2004.
11

---

Under review as a conference paper at ICLR 2020
Shixiang Gu, Timothy Lillicrap, Zoubin Ghahramani, Richard E Turner, and Sergey Levine. Q-prop: Sample-efficient policy gradient with an off-policy critic. International Conference on Learning Representation, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, 2018.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sam- pling. International Conference on Machine Learning, 2019.
Tang Jie and Pieter Abbeel. On connection between importance sampling and the likelihood ratio policy gradient. In Advances in Neural Information Processing Systems, pp. 1000-1008, 2010.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp. 315-323, 2013.
Sham M Kakade. A natural policy gradient. Advances in Neural Information Processing Systems, pp. 1531-1538, 2002.
Yunwen Lei and Ke Tang. Stochastic composite mirror descent: optimal bounds with high probabil- ities. In Advances in Neural Information Processing Systems, pp. 1519-1529, 2018.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. ICLR, 2016.
Hao Liu, Yihao Feng, Yi Mao, Dengyong Zhou, Jian Peng, and Qiang Liu. Action-dependent con- trol variates for policy optimization via stein identity. International Conference on Learning Representation, 2018.
Hongzi Mao, Shaileshh Bojja Venkatakrishnan, Malte Schwarzkopf, and Mohammad Alizadeh. Variance reduction for reinforcement learning in input-driven environments. International Con- ference on Learning Representations, 2019.
Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, pp. p 5442-5454, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference Machine Learning, pp. 1928-1937 2016.
Jean-Jacques Moreau. Proximité dualité dans espace hilbertien. Bull. Soc. Math. France, 93
(2):273-299, 1965.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4): 1609, 2009.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Y Nesterov. Introductory lectures on convex optimization: basic course. Kluwer Academic Pub- lishers, Dordrecht, 2004.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference on Machine Learning, volume 99, pp. 278-287, 1999.
12

---

Under review as a conference paper at ICLR 2020
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning. 2017a.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Stochastic recursive gradient algo- rithm for nonconvex optimization. arXiv preprint wrXiv:170.007200 2017b.
Matteo Papini, Giuseppe Canonaco Damiano Binaghi, and Marcello Restelli Matteo Pirotta. Stochastic auriuece-reduced policy gradient. In International Conference on Machine Learning, 2018.
Jan Peters and Stefan Schaal. Natural actor-critic, Neurocomputiig, 71(7-9): 180--1190, 2008
Jan Peters, Katharina Mülling, and Yasemin Altun. Relative entropy policy search. In AAAI, pp. 1607-1612, 2010.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning, pp- 314-323, 2016.
Alfréd Rényi et On measures entropy and information. In Proceedings of the Fourth Berkeley Symposium Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, 1961.
R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 1475):877-898, 1976.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-112 2017.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Picter Abbeel. High- dimensional continuous control using generalized advantage estimation. International Confer- ence on Learning Representations, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Claude Elwood Shannon. A mathematical theory of communication. Bell system technical journal, 27(3):379-422 1948.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International Conference Machine Learning, pp. 5729-5738, 2019.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International Conference Machine Learning, 2014.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. Nature, 550(7676)3354, 2017.
Charles Stein. Approximate computation of expectations. Lecture Notes-Monograph Series, 7:
i-164, 1986.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 1998.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Infor- mation Processing Systems, pp. 1057-1063, 2000.
13

---

Under review as a conference paper at ICLR 2020
Philip S Thomas, William C Dabney, Stephen Giguere, and Sridhar Mahadevan. Projected natural actor-critic. In Advances in neural information processing systems, pp. 2337-2345, 2013.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033.
IEEE, 2012.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Lex Weaver and Nigel Tao. The optimal reward baseline for gradient- reinforcement learning. In Proceedings of the Seventeenth conference Uncertainty in artificial intelligence, pp. 538- 545. Morgan Kaufmann Publishers Inc., 2001.
Ronald J Williams. Simple statistical following algorithms for connectionist reinforcement learning, Machine learning, 8(3-4):229-256, 1992.
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. International Conference on Learning Representation, 2018.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. Conference on Uncertainty in Artificial Intelligence. 2019.
Tianbing Xu, Qiang Liu, and Jian Peng. Stochastic variance reduction for policy gradient estimation. arXiv preprint arXiv: 1710.06044, 2017.
Huizhuo Yuan, Chris Junchi Li, Yuhao Tang, and Yuren Zhou. Policy optimization via stochastic recursive gradient algorithm. 2019. https:/popeerrvvw......//om/////
Siqi Zhang and Niao He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization, arXiv preprint /00.::/800077000 2018
14

---

Under review as a conference paper at ICLR 2020
A PROOF OF THEOREM 2
Let f(x) be a L-smooth function defined on IR",, i. [V - vf(y)l - L| - yll. Then, for
Vx, y ER"", the following holds
L [If(x) (V w>1l - 2
x - y11²
(33)
The following Lemma 2 is useful for our proof.
Lemma 2 (Ghadimi al. (2016), Lemma 1 and Proposition 1). Let X be closed convex set in
R2, h X +k be a convex functioon, but possibly nonsmooth, and Dvp X x X - R is Bregman divergence. Moreover, define
u) u) - + M(a) +(())
xt arg arggin uEd
Px(E, - (x-
(34)
where g Rd, x E X, and 11 0. Then, the following statement holds
(g, (x, 2 (1),x(1, 9. m)1 + 1 [=x=)) - hx))),
(35)
where Ç positive constant determined by 1p (i.e. is a continnously-diiffreettata and Ç- strictly convex function) that satisfying (æ y, Vv(x) Vv(lu) 2 <| - wll Moreover, for any gr 92 E Rd, the following statement holds
|| PP n) - Px(x, 02, m)ll - 5 1191 92ll-
(36)
Theorem Convergence Rate of Algorithm I Under Assumption 7 and the total trajectories are (Th
A k Consider the sequence L.W generated by Algorithm ] and the output 0N = follows the distribution of Eq. 16 Let 0 < as < f. [(g, u) = (g, u). the term L and a are defined in Eq. 5
and Eq. correspondingly. Let 9n = Ein 9i. where 9; = EtTo Vo log To (a,l s, R(()) T-) Then have
(J(OP) -(O))) + + 2K=1
d E
an 0.) (0n)l
Σk - Laa)
Proof. (Proof of Theorem 2
Let T = ( be the trjecories generated by the differentiable parametric policy my. At each Hyg
terminal end of trajectory Th {st, ar 114 E T, let
H
9h
V log (a(aa 8m0
Bx 9N
1: gi.
according to Algorithm I at the terminal end of k-tth episode, h 1,2, N. the following holds,
1 Ox+1 = arg min 0 { (- 0) Dv 0k) = M
0) 0) (0x).
OAk
To simplify expression, let ((0) = -J0), then J(0) is L-smooth, from Eq 33 we have
[(0++1) J(0k) + (VoJ (0) -= ( 0++1 0k) + L 0.+1 -
= -((k) - au V (Bx). G f( Dw) ((B (8x)) - Lag
|
2
-((A) - on (Be -hh p(- .)) (8x) + Ta2 | (( (Ba))
2
+ an ck. GV (00
15

---

Under review as a conference paper at ICLR 2020
where Ek - (- VJ(())) = 9 V.((f.). By (3 and let h(x) 0 and a, then let ay and g -kk then we have
Px(0,g,a) G lg (0). Furthermore, by Eq. 35
l| + La
J(0++1) ((b))
oL (8x)
2
+ +ax ck. Sa. (a (0x))
La
= I(ww) - -an (0a)
g
an (on.e(-9e 9n. (1.00 (0x)
+
2
+ an (k. - (0k)
+ an Ek, 9 ( -0000000
(0x)
(37)
Rearrange E3) we have
J(6x+1) S ((b.) (cax= 2 - (O)) ark cks (0
+allleal| _0m. (cy. a (o (Bx)
By (3). let x 0k.91 = 9k: 92 -VJ(O),, = then the following statement holds
J(0++1)
s (0s) - (Cors
Lak
gy an (( (0+) + ar ( cx. 9 v...))))))))))))))))))))))
O'k llea 112
2
T
(38)
Summing the above Eq. from = to N and with the condition 0g 1 L' we have the following statement
La? /|
(0x)
Cax
1/ a (0.
Lag
(ax
2
+ ak ||eall? + ((u+t))
a4 cki (
N
aak cx. 94 Tee ( + a# ||eb112]
+ +J(()) -J(())-) - -r
(39)
5
k=1
Recall
9k
Vo log (og()())))))((1
Σ 9s.
k
by policy gradient theorem
VJ
(40)
Let F3 be the o-field generated by all random variables defined before round k, E, 9t ((x)))
then the Eq.440 implies: for l: = 1,... N,
E [(
ce. 9 a (Pk) Fr Fa-1] = E( Fr-1] 0.
Let 6, Ei=1 & noticing that for 1,... Ahi,
E E((E,, (041)111] 0.
(41)
16

---

Under review as a conference paper at ICLR 2020
Furthermore, the following statement holds
||||0|| [1]] EB [1ók- 2 2 Ek) + |&
IB
|
1|2
1|ē:|1?
Σ
E
(42)
By Lemma I and Eq.(42) we have
1 El 11
o²
Blll<|
(43)
k2
Taking Eq. 43 in to Eq. 39 and taking expections w.r.t FN. we have
(ax Lak E ||0. o.) & J0i) J
0²
N
OCk
5
k
k=1
Now, consider the output ON = On follows the distribution of Eq. 16
we have
E ..) - (J(O)) - -(O.)) =2 Ek=1 ai
Σk=I(Say Lak)
Particularly, if the step-size ag is fixed to a constant:(/21, then
A - +20 -k=1
M. ) (0n)113)
NÇ²
Recall the following estimation
N Σ k=1
h N +
where C is the Euler constant positive real number and o(1) is infinitesimal. Thus the overall convergence rate reaches O Wn
N
as
4LD3 20 Ex=1
In N
Blllga.. (..... (0m)1
Billg
0
NC
17

---

Under review as a conference paper at ICLR 2020
B SHORT CORRIDOR WITH SWITCHED ACTIONS
Consider the small corridor grid world which contains three sates S = 2,3/. The reward is -1 per step. each of the three nonterminal states there are only actions, right and left. These actions have their usual consequences in the state 1 and state 3 (left causes no movement in the first state), but in the state 2 they are reversed. so that right moves to the left and left moves to the right.
S
2
G
3
(a)
Figure 4: Short corridor with switched actions (Chapter 13, (Sutton & Barto 2018
action- value method with c-greedy action selection is forced choose between just two policies: choosing right with high probability 1 on all steps choosing left with the same high probability on all time steps. If 0.1, then these two policies achieve value (at the start state) of less than 44 and -82, respectively, as shown in the following graph
Short corridor with switched actions
-10
-20
((0) =i Vng (5)
-40
-50
-60
optimal point: (1.66))
e-gready
-80
egreedy right
0.0
0.2
0.4
0.8
Probability of right action (a)
Figure 5: Short corridor with switched actions (Chapter 13, (Sutton & Barto 2018)).
method can do significantly better it can learn specific probability with which select right. The best probability is about 0.58, which achieves value of about - 11.6.
18

---

Under review as a conference paper at ICLR 2020
C PROOF OF THEOREM 3
We need the following lemmas to prove the convergence result.
Lemma (Lemmal (Fang et al. 2018)). Under Assumption [ GR. is generated according to Ou. is generated according (26). thenfor any 0 S S m, the following holds
25
L2
G VJ (0
11 02.1-1111
O2.
B1I|G==-I J [(,,,-
(44)
N₂
Telescoping Eq.(3) over from the time t, then the following holds
L
El||GE - (0
Bl1 - 0x.; - -
(45)
N₂
Lemma 4. Let 5
5
the batch size of the trajectories of outer loop N1
32
(1
+1+
0²
8TC2
2(5 52
32
the iteration times of inner loop 1 N2
e2
8LC²
215
52<
and step size Oi aL- For each ls and t, Gk.o and 0k.o are then the the following holds,
generated by Algorithm
1
E
(B -
SLC² +
2
(46)
2(5
32
Proof.
N;
= JO ((T 0
1
Σ
(47)
N₁
i=1
1
( (T.100..0)
(48)
N
(49)
N1
1
1
+
(50)
8L
2(
32
32
Theorem Algorithm
Convergennee Rate of VRMPO)
The sequence 1K is generated according to the batch size of the trajectories of outer loop
Under Assumption 1 let
N1 =
8L + +
2(C
+
32
2. the iteration times of inner loop
- N₂
8L
(1+
32 ) the iteration times of outer loop K (m
(1+
SLC2
2(
+.
1)(C
and step size on
T.- Then, Algorithm outputs the point Öx achieves
I0C
El a () (ōx) S
(51)
Proof. (Proof of Theorem 3
19

---

Under review as a conference paper at ICLR 2020
By the definition of Bregman grdient mapping in Eq.(00) and iteration 26 let 0% a, have
1
(0k,e (x.l+1)
20
Oktt arg min (Gr.L u) + ar
Dulu, 02.11)
10
-e (n (Ok,e);
(52)
where we introduce Jk.t to simplify notations.
Step 1: Analyze the inner loop of Algorithm Now, we analyze the inner loop of Algorithm this step, our goal is to prove
2 In
B[J(OA) - E[J (6x-1) n 1991,,,,11 1 -22)
In fact,
((nn.) + (VJ(Okn))) (0,,,),0,,41 Ou,z) L 10 0m.el2
I (0u,4411)
[(On.)) - a (VJ (0 gr.e) + La²
11.
La²
I(0p,) - a (O.) Gu. - a (Gk,s,9u.d
+
|
2
Iaa2
S I(0,,)) + (J(0k.)) GR - (Gk,t, +
+
|1gk,el|
(53)
2
35
La
J(Ok.) + " ([](k..)))) GR,,ll - (allgge,
+
|19
(54)
2
E5.
holds due to the Cauchy-Schwarc inequality (u, v\ S ||u|||[|||| = (11u]]
[||u|2= +/+++[|]]] [|vll(²) for any
2
u, R.. (54 holds if by Eq (5).
Taking expectation on both sides of 54). we have
B[J 5 -
[(v.))
Garll]] -(sa-
La² a
E
2
2
< B[J(Ok.)] + Σ
E
0k.141 0R.i11
N2
1=1
La
VJ (a
Ellgh.ell?
EE
(55)
2
2
(5) holds due Lemma 3
By Lemma Eq. 55 and Eq 52
we have
ac?
-(sa
La²
B[J(Ok.441) 5 [[J(0k))) +
Σ
E
11
1|
+
E gl
2N2
2
2
1=1
20

---

Under review as a conference paper at ICLR 2020
Recall the parameter 0 0 is generated by the last time of (l- - 1)-th episode, we now consider the following equation
((x,0k)) - E[J(( ((x-1))
L²
Bllgg,ell
12++
a
2
((x
La
a
Bllge 11
2N₂
2
2
2
j=1
L2
Bl
12
+ 2
a
Σ
{a
La²
a
11
2N₂ j=1
2
2
/=1
j=1
1
B| 11.
+
5ed
c
La
Laa
a
Σ
Bl 11
2N₂
2
2
2
j=1
3 (m2(m - 1)
a
Σ
t
ςa
La
2
a
El 1l 1|
(56)
2N₂
2
2
2
i=1
j=1
j=1
1
La
a² L2 (m
c
(a
Ellgg 11?
2
2
2N2
j=1
{ =
5
32
4L
-1
a
1
+
(1
+
2
(57)
2
8LC²
2(5
5
32
32
=c
(5. holds due to t. S m - 1.
If t m 1. then by the last Eq (5) implies
E[J(Aa) B (0.-
1 -2-
(58)
Step 2: Analyze the outer loop of Algorithm
2
We now consider the output of Algorithm 2
- = - -BI700)) + (0]J(
+... [B]](K)] - -E,](Kx))]]
1 o 12 ( Σ
n 11 - -7
m-1
(MEllox..11
a
2
K m-1
2 a 2
Ka 2
611
then we have
K
K (mm- 1)a 2
BBBl....)1)) < [0T - -((0') +
61.
(59)
2
21

---

Under review as a conference paper at ICLR 2020
Recall the notation in Eq. 52)
1 Ik.t (Ok,t - arg min (( u) + Dv, (x,)) = 9 (a (Ok,t),
and we introduce following ((0k,)) simplify notations,
g(On,z) = 9a, (V)(()))))))) (Ox,c) def
gk.t
1 (u. arg min{( (-V.((-)))))).))))))) u) + 1 (u(l)
(60)
Then, the following holds
E
2|
< 19..
+ Ellge, - gk,ell
36
EE
e
[(V)(( - Gk.lll.
(61)
(q. holds due to the E4.36).
Let be the number that is selected randomly from {1.... (m 1)K} which is the output of Aggorihtm@foor the convenience of proof the there is no harm in hypothesis that v = k (m - 1) +
and we denote the output Og ORR,-
Now, we analyze above (61 and show it bounded as following two parts 63 and (66)
1
[OO())) - T(0))
(l,g(+,)112 (m 1)K
. 12
ci'
(62)
(m
1)K1
21
which implies the following holds
B[J[Bu)] - T(0))
E o 11 2
+ a
Ei.
(63)
(m 1)K1
2nj
For another part of (1. notice kmm 1) + t, then we have
Gr.el
-E E1 V
-
(64)
45
L
01,02,111 - 02.111 EEI -
E
N₂
12
0|002,111 - 0k,i11 + a
E
N₂
2
L²a²
E
E ig 112
+ a 2
-2 2
N2
m
Lia² m-1
E
N₂
Ellgg. 21
2 c
1 12 K m-
E3 Bllg 1| + a
(65)
K KN₂ 1=
1=1
o22
- + ( 1mm-1) 1)
(.2aa
2 -
(66)
K KN
2N21
Eq.
holds due the fact that the probability of selecting v == k- (m 11) + is less than
+
Taking Eq 62) and Eq. 655 into Eq. (TI, then we have the following inequity
L²a²
(R(J( -((0)) (
(m
Ell 11 <
2m ?
(m 1)
3
2N
2
22

---

Under review as a conference paper at ICLR 2020
+
(1
+1
0²
1L
2(C -
32
Recall
Ni
N2
IL
(1 +
BLC²
2(1 3)
32<
then we have
[- 12 =llike S
41.
(1+
1662)
1
J(x))
+
22²
K(m 1)(s
32
(67)
8T(11 T6
B[J(06)) -(0))
Furthermore, K
have
(m 1)(s
5.
62
32
a. (- (0k)
(68)
D EXPERIMENTS
D.1 EXPERIMENTS DETAILS OF FIGURE 2
For all tp. we set p [P] 11,1, 1,9,2,3,,, we 7 0.99. The learning rate is chosen by grid search from the (0.01, 0.02, 0.04, 0.08, 0.1). For our implementation of MPO, we use two layer feedforward neural network of 200 and 100 hidden nodes respectively, with rectified linear units (ReLU) between each layer.
D.2 SOME PRACTICAL TRICKS FOR THE IMPLEMENTATION OF VRMPO
We present the details of the practical tricks we apply to VRMPO in the following Algorithm 3
(I) For the complex real-world domains, should tune necessitate meticulous hyper-parametter In order to improve sample efficiency, we draw on the technique of Double Q-learning (Van Hasselt al. 2016) to VRMPO.
(II) For Algorithm 2 the update rule policy gradient 28 25 is a full-return update accord- ing to R(T), which the expensive Monte Carlo method and it tends to learn slowly. In prac- tice, we use the one-step actor-critic structure. Let D be the replay memory, replacing the term - (-g(r(00m)))))) + I(T,) (k))-)) (in 25 as the following ōc,t
1 N VoLon 0:) -
5R =
0z)),
(69)
N₂
where La(s, a) - (8, a (s a) is the training loss of actor, ((),, ai)) an estimate of action-value value that can be trained to minimize the loss critic
D, (s(),))
1 E (en (8i, a:) - (si,
Lu N
(70)
More details of implementation are provided in the following Algorithm 3 In this section, we Ep the mirror map.
23

---

Under review as a conference paper at ICLR 2020
Algorithm 3 On-line VRMPO
Initialize: Policy To(als) with parameter Og. mirror map ssste--size >> O, epoch size K .m. Initialize: Parameter W/.. 1,2,0 1.
for k = to K do for each domain step do ~ Tb__, _0__,(-(5) (-18c) 8t+11 P(1(st, (z)
D= D=Du DU (8e, ae, rt, 81+1))
end for sample mini-batch {(s;, a.) a.) ~ DD
0u.0 = 01 4k,00 = --1 = 1,2
L = - log a)(
min Qul. (s,a)) 1=1.2
Double Q-Learning Hasseli 2016
0R,1 = 0k.o ag GR where Gk.0
N 2 i= VoLo(si,a;) 1000000
for 1 to do /* Update Actor (m 1) Epochs */ sample mini-batch {(,,, a,)) D
N
1 N
6R
1
Σ 1=1
VoLo(si, 0=0sa
VoLu VoLu(si,an az)
(71)
N
0=02.-1
Gk.E = 5x, + Gk
(72)
0a11+1 arg min (G u) Dv(u,
(73)
an
end for for = 1 to 1 do 1a Update Critic (m 1) Epochs */ sample mini-batch {(si, N
N
L w/ 1,1-1
(w)
QQ
(st,a) - (u(s:: = 112
(74)
N
w/ 11--1111
i=1
wh, arg arg min L
(w).j 1,2
(75)
end for
0g
def
0
2 def w k. 1: = 1,2
1t Soft Update #/
0. kOR-11
5/ < näjh
küo + (1-R) 1.2
end for
D.3 TEST SCORE COMPARISON
We compare the VRMPO with baseline algorithm on test score. All the results are shown in the following Figure 6.
D.4 MAX-RETURN COMPARISON
We compare the VRMPO with baseline algorithm on max-retumn All the results are shown in the following Figure 7.
24

---

Under review as a conference paper at ICLR 2020
4000
10000
TRPTO
2000
1000
Walker2d-v2
(b) HalfCheetah-v2
(c) Reacher-v2
2000
6000
1.00
4000
1000
WISFO
VI3I7
VINPO
2000
700
(d) Hopper-v2
(e) Inw.DoublePendulun--2
(l) InyPendulumm-2
Figure 6: Learning curves of test score over epoch, where we run 5000 iterations for each epoch. The shaded region represents the standard deviation of the test score over the best trials. Curves are smoothed uniformly for visual clarity.
DCPG
2000
0900
13310
1000
2000
7500
2000
TOO
0
(a) Walker2d-v2
(b) HalfChectah-v2
(c) Reacher-v2
2000
2000
anon
Vitutoo
191
2009
20
101
(d) H2pper-v2
(c) InwDDubieeenndulmm-2
(f) InvPendulum-v2
Figure 7: Learning curves of max-return over epoch, where we run 5000 iterations for each epoch. The shaded region represents the standard deviation of the test score over the best trials. Curves are smoothed uniformly for visual clarity.
D.S DETAILS BASELINE IMPLEMENTATION
For all algorithms, set 0.99. For VRMPO, the learning rate is chosen by grid search from the set 10.1, 0.01, 0.004, 0.008}, batch-size N 100. Memory size |D| 10 We rum 5000 iterations for each epoch.
25

---

Under review as a conference paper at ICLR 2020
DDPG For implementation of DDPG,
two layer feedforward neural network of 400
and 300 hidden nodes respectively, with rectified linear units (ReLU) between each layer for both the actor and critic, and final tanh unit following the output of the actor. This implementation is largely based on the recent work by (Fujimoto et al. 2018).
TD3 For our implementation of TD3, refer the work TD3 (Fujimoto et al. 2018) and https: /ggthub.com//fujjm//
We excerpt necessary details about the implementation of TD3 (Fujimoto et al. maintains pair of crities along with a single actor. For each time step, we update the pair of critics towards the minimum target value of actions selected by the target policy:
2018 TD3
- +ー++7 min Qo (8 Tar + +c,
1.1
clip(N((,,)) -c.c).
Every d iterations, the policy is updated with respect to Qs. following the deterministic policy gradient algorithm. The target policy smoothing is implemented by adding e ~ (N 0.2) to the actions chosen by the target actor network, clipped to (-0.5, 0.5), delayed policy updates consists of only updating the actor and target critic network every d iterations, with d d= 2. While a larger would result in larger benefit with respect accumulating errors, for fair comparison, the critics only trained once per time step, and training the actor for too few iterations would cripple learning. Both target networks are updated with 0.005.
TRPO and PPO For implementation of TRPO/PPO, we refer to https///ithub..co//penaa Dasclinestrre/nasee//sselnsss and http:///gnnniigggoooooooo//////p
26


Reviews:
[{"review_id": "rJxuWhn2YS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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$.\n\nDefinition 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.\n\nSection 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.\n\nIn 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. \n\nIt 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? \n\nIn 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. \n\nThe 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. \n\nIn 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.\n\nOther comments:\n\n1. On page 15, the first sentence of the proof: “trjecories” -> “trajectories”\n2. What is $\\mathcal{J^*}$ in eq (39)? It was not defined in the paper.\n3. 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? \n4. What is $\\epsilon_1$ in eq (50)? It seems that this term does not appear in Lemma 4.\n\n====after rebuttal====\nThanks 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. \n\nThe 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. \n\nThe 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.\n\nA 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.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJe4JbcTtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n[Summary]\nThis 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.\n\n[Decision]\nThe 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.\n\n[Explanation]\nSection 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.\n\nThe 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.\n\nThe paper needs more polished presentation. Here are some examples for improving the writing:\n- The introduction section: \"our algorithm outperforms state-of-the-art bandit algorithms in....\" The compared methods are RL algorithms.\n- \"converges faster significantly and achieves a better performance than both REINFORCE and MPO\" -> \"... than both REINFORCE and VPG\".\n- \"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.\n- \"Eq.(23) has a closed implementation\" -> What is a closed implementation?\n- 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).\n- \"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\"\n- In Table 1 the performance of VRMPO on Reacher is in bold while it is not the maximum value.\n- \"It is different from (Du et al., 2017)...\" -> \"VRMPO is different from...\"\n- \"due to it doesn't require...\" -> \"because it does not require...\"\n\n[Minor comments]\n- How is the bound in Eq. (18) proved?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lx1SBgqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nOverall, 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.\n\n- 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. \n\n- 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.\n\n- 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.\n\n\n- Some minor comments:\npage 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.\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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