Near Optimal Policy Optimization via REPS
Authors: Aldo Pacchiano
Jonathan Lee
Peter Bartlett
Ofir Nachum
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
REPS
linear programming

Abstract: Since its introduction a decade ago, relative entropy policy search (REPS) has demonstrated successful policy learning on a number of simulated and real-world robotic domains, not to mention providing algorithmic components used by many recently proposed reinforcement learning (RL) algorithms. While REPS is commonly known in the community, there exist no guarantees on its performance when using stochastic and gradient-based solvers. In this paper we aim to fill this gap by providing guarantees and convergence rates for the sub-optimality of a policy learned using first-order optimization methods applied to the REPS objective. We first consider the setting in which we are given access to exact gradients and demonstrate how near-optimality of the objective translates to near-optimality of the policy. We then consider the practical setting of stochastic gradients, and introduce a technique that uses generative access to the underlying Markov decision process to compute parameter updates that maintain favorable convergence to the optimal regularized policy.

Near Optimal Policy Optimization via REPS
Aldo Pacchiano
Jonathan Lee Stanford University jnl sordesrrdddd....
Peter L. Bartlett UC Berkeley
Microsoft Research
peteræberkelley edu
Ofir Nachum Google of ofirnachum@googlle.
Abstract
Since its introduction decade ago, relative entropy policy search (REPS) has demonstrated successful policy learning on a number simulated and real-world robotic domains, recently proposed reinforcement learning (RL) algorithms. While REPS is well- known the community, there exist no guarantees on its performance when using stochastic, gradient- based solvers. In this paper we aim to fill this gap by providing guarantees and convergence rates for the uub-optimality of a policy learned using first-order optimization methods applied to the REPS objective. We first consider the setting which we are given access exact gradients and demonstrate how near-optimality of the objective translates to near-optimality of the policy. We then consider the setting of stochastic gradients and introduce technique that uses generative access to the underlying Markov decision process to compute parameter updates that maintain favorable convergence to the optimal regularized policy.
mention providing algorithmic components used by many
1 Introduction
Introduced by Peters al. 23 relative entropy policy search (REPS) is algorithm for learning agent policies reinforcement learning (RL) context. REPS has demonstrated successful policy learning in variety of challenging simulated and real-world robotic tasks, encompassing table tennis 23 tether ball [2], beer pong [. and ball-in-a-cup [8 among others. Beyond these direct applications of REPS, the mathematical tools and algorithmic components underlying REPS have inspired and been utilized as a foundation for number of later algorithms, with their own collection of practical successes
25
20 2
19 in which At its core, the REPS algorithm is derived via an application of convex duality 22
Kullback Leibler Iegulargurr version of the max-return objective in terms of state-action distributions is transformed into an logsumexp objective in terms state-action advantages (i.e. the difference of the value of the state-action pair compared to the value of the state alone, with respect to some learned state value function). If this dual objective optimized, then the optimal policy of the original primal problem may be derived derivation may be generalized, using any number of entropic regularizers on the original primal to yield dual problem in the form of convex function of advantages, whose optimal values may be transformed back to optimal regularized policies
softmax of the state-action advantages. This basic
7
While the motivation for the REPS objective through the lens of convex duality is attractive, it leaves two main questions unanswered regarding the theoretical soundness of using such an approach. First, in practice, the dual objective in terms of advantages is likely not optimized fully. Rather, standard gradient- based solvers only provide guarantees on the near-optimality of a returned candidate solution. While convex duality asserts relationship between primal and dual variables at the exact optimum,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

it is far from clear whether a near-optimal dual solution will be guaranteed to yield a npar-optimal primal solution, and this is further complicated by the fact that the primal candidate solution must be transformed to yield an agent policy.
The second of the two main practical difficulties is due to the form of the dual objective. Specifically, the form of the dual objective as a convex function of advantages frustrates the use of gradient-based solvers in stochastic settings. That is, the advantage of a state-action pair consists of an expectation over next states - an expectation over the transition function associated with the underlying Markov decision process (MDP). In practical settings, one does not have explicit knowledge of this transition function. Rather, one only has access to stochastic samples from this transition function, and so calculation of unbiased gradients of the REPS objective is not directly feasible.
In this paper, we provide solutions to these two main difficulties. To the first issue, we present guarantees the near-optimality of derived policy from dual variables optimized via a first-order gradient method, relying on a key property of the REPS objective that ensures near-optimality in terms of gradient norms. To the second issue, we propose and analyze stochastic gradient descent procedure that makes use of a plug-in estimator of the REPS gradients. Under some mild assumptions on the MDP, our estimators need only sample transitions from a behavior policy rather than full access to a generative model (where one can uniformly sample transitions). We combine these results convergence rates of REPS to a near-optimal policy. In this way, we show that REPS enjoys not only favorable practical performance but also strong theoretical guarantees.
to yield
2 Related Work
As REPS is a popular and influential work, there exist number of previous papers that have studied its performance guarantees. These previous works predominantly study REPS as an iterative algorithm, where each step comprises of an exact optimization of the REPS objective and then the derived policy is used as the reference distribution for the KL regularization of the next step. This iterative scheme may be interpreted as form of mirror descent or similar proximal algorithms (6) and this interpretation can provide guarantees on convergence to near-optimal policy [29 22] However, because this approach assumes the ability to optimize the REPS objective exactly, it still suffers from the practical limitations discussed above; specifically (1) translation of near-optimality of advantages to near- opttmaattmll of the policy and (2) ability to compute unbiased gradients when one does not have explicit knowledge of the MDP dynamics. Our analysis attacks these issues head-on, providing guarantees on first-order optimization methods applied to the REPS objective. To maintain focus we do not consider iterative application of REPS, although extending our guarantees to the iterative setting is a promising direction for future research.
In a somewhat related vein, a number of works use REPS-inspired derivations to yield dynamic programming algorithms 13, 14 26 and subsequently provide guarantees on the convergence of approximate dynamic programming in these settings. Our results focus on the use of REPS in convex programming context, and optimizing these programs via standard suudient-based solvers.
The use of convex programming for RL in this way has recently received considerable interest. Works in this area typically propose to learn near-optimal policies through saddle-poing optimization p 28 10 4
Instead of solving the primal or dual max-return problem directly, these works optimize the Lagrangian in the form of min-max bilinear problem. The Lagrangian form helps to mitigate the two main issues we identify with advantage learning, since (1) the candidate primal solution can be used to derive a policy in a significantly more direct fashion than using the candidate dual solution, and (2) the bilinear form of the Lagrangian is immediately amenable to stochastic gradient computation. In contrast to these works, our analysis focuses on learning exclusively in the dual (advantage) space. The first part of our results is most comparable to the work of [.) which proposes a saddle-point optimization with runtime (1)ee), assuming access to known dynamics. While our results yield O(1/e²) rate, we show that it can be achieved via optimizing the dual objective alone.
More similar to our work is the analysis of Sas-Serrano et al. [5]. which considers an objective similar to REPS, but which is in terms of Q-values as opposed to state (V) values. Beyond these structural differences, our proof techniques also differ. For example, our result on the suboptimality of the policy derived from dual variables (Lemma 4. is arguably simpler from the analogous result in Bas-Serrano et al. [ which uses a two-step process to first connect suboptimality of the dual variables to constraint violation in the primal, and then connects this to suboptimality of the policy.
2

---

3 Contributions
The main contributions of this paper are the following:
1. We prove several structural results regarding entropy regularized objectives for reinforcement learning and leverage them to prove convergence guarantees for Accelerated Gradient Descent on the dual (REPS) objective under mild assumptions on the MDP (see Theorem 2 For discounted MDPs we show that an e-optimal policy can be found after (11((1 7)² steps and an e optimal regularized policy can be found in (11((1 - e)) steps.
2. Similarly we show that a simple version of stochastic gradient descent using biased plug-in in
gradient estimators can be used to find e-optimal policy after ((1/(1 ==) iterations (see Theorem 3 and am e-optimal regularized policy in (LL steps. Although our rates short of the ones achievable by alternating optimization methods, are the first to show meaningful convergence guarantees for a purely dual approach based on on-policy access samples from the underlying MDP.
3. In Appendix ! we extend our results beyond the REPS objective and consider the use of Tsallis Entropy regularizers. Similar to our results for the REPS objective we show that for discounted MDPs an c-optimal policy can be found after (11((1 - ?)?²²))))))) steps and an 6 o-optimal regularized policy can be found in (11((1 - ?) steps.
4 Background
In this section we review the basics of Markov decision processes and their Linear Programming primal and dual formulations (see section 4.1 and some facts about the geometry of convex functions.
4.1 RL as an LP
We consider a discounted Markov decision process (MDP) described by a tuple M (S,A, ue 7), where S is finite state space, A is finite action space, P is transition probability matrix, r is a reward vector, is an initial state distribution, and y E (0, 1) is a discount factor. We make the following assumption regarding the reward values {-
Assumption (Unit rewards). For all s, S A. the rewards satisfy, r,,a E 1].
The agent interacts with M via policy x - The agent is initialized at state sampled from an initial state distribution μ and time it 0, 1.... it uses its policy to sample an action ag ~ (sx).. The MDP provides an immediate reward xa, and transitions randomly to a next state 1 according to probabilities (a(s4+1(5E) Given a policy ı we define its infinite-horizon discounted reward as V := E= -k= 7 rsg.es) where we use ET denote the expectation over trajectories induced by the MDP M and policy π. In RL, the agent's objective is to find an optimal policy x.: that is, find policy maximizing Va over all policy mappings क - AA. We denote the optimal policy as T, == arg max, Vn.
We now review the definitions of state value functions and visitation distributions: v
Definition 1. We define the value vector
R of policy
V
ET [E k= r = s].
Definition 2. Given policy π we define its state-action visitation distribution X E R|S|X|A| as, Xr (1 7) -i 7 *1(s== s, ak = a)). Notice that by definition E., As,a =
We note that any vector of nonnegative entries X may used to define a policy mx as:
As
x (als) = EnreA As,a'
Note that Tx= IT, while the visitation distribution A of T is not necessarily A.
Definition 3. Given policy we define its state visitation distribution as X (1
1) [Ee kk "1(st = =)]. Notice that X = En N% and X7 >x <(als).
3

---

The optimal visitation distribution X is defined as X == arg m Es,a T It can be that solving for the optimal visitation distribution is equivalent to the following linear
shown 124. 9
program:
Σ Exnntaa
> -1 +
P Vs E S. (Primal-A) a'.a
Ax.a EA
A,0
Where we write P R. X| to denote the transition operator. Specifically, the |S] constraints of Primal-X Primti-AJretrrictt restrict any feasible À to be the state-action visitations for some policy (given by πT)).
The dual of this LP is given by,
min (1 717)) Σ M.Vo, s.t. 02 A E
(Dual-v)
SES
where A.. Fs,a v, + + E. Pa(''ss))) is the advantage evaluated s, a E 8 x A. It can be shown 24 that the unique primal solution X is exactly X and the unique dual solution v* is v
We finalize this section by defining the notion of suboptimality satisfied by the final policy produced by the algorithms that we propose.
Definition 4. Let > O. We say that policy π is e-optimal max.es Vv v S
Our objective is to design algorithms such that for any 0, can return an c-optimal policy.
4.2 Regularized Policy Search
Following Belousov & Peters M. consider regularizing Primal-X with convex function F
Ais x|AA + R {oo). The resulting regularized LP is given by,
Anaass ((A))a-F((A----- == JP(A), s.t. >x.a= = --, + Σ Pa(sl'')
max AASKA
3
s',0
(PrimalReg-A)
Any feasible that satisfies the [S] constraints in this regularized LP is the (true) state-action visitation distribution for some policy и; therefore, the optimal A of this problem can be used to derive an optimal F- regularized max-return policy =F := mx. To simplify our derivations, we introduce the definition of the convex conjugate of a convex function, oftentimes referred to as the Fenchel conjugate:
Henceforth we denote the primal objective function as Jp(A)=E.c
Definition 5 (Fenchel Conjugate). Let F' D + R be convex function over a convex domain D Rdd We denote its D consttaaaee Fenchel conjugate as F R. + R defined as F*(u) maxxED (x, u. - Fxx).
The dual Jp of the regularized problem is given by the following optimization problem
19
min JD(v) = (1 Σ V.H, + F* (AY),
where F* is the A Fenchel conjugate of F. The vector quantity inside F* is known as the advantage. That is, it quantifies the advantage (the difference in estimated value) taking an action at with respect optimal solution v the dual function Jn may be used to derive an optimal primal solution X as:
state value function Using
duality, the
X E V (AY')
Algorithm Relative Entropy Policy Search [Sketch).
Input: Initial iterate Vo. accuracy level > 0, gradient optimization algorithm O.
Optimize the objective in 2 using to yield a candidate dual solution v where F satisfies
Equation
2. Use the candidate dual solution to derive a candidate primal solution X using 3
3. Extract a candidate policy Txx from X via Equation
Return: Tx*

---

Relative Entropy Policy Search (REPS) is derived by setting F(A) := DKL ( the KL-divergence of À from some reference distribution q E (isIiAi. The reader should think of q as the visitation distribution of a behavior policy. As we can see, the derivation we provide here further generalizes to arbitrary regularizers F. We focus on a specific given by
F(A) =
Σ 5,a
Assa
log
1)
(4)
9x,a
for some scalar > 0. In this case F
R|S|X|4 7 R equals F*) =
log (Es,a exp (1)us,a) 9s.a + 7 its gradient satisfies VVF(u))a = Ey explatu J9uioa
1
exp(n 1)4m0
and therefore the dual function equals:
JD(v) = (1- Σ voll, + log Exx
exp (nAy as
1 +
(DualReg-V)
8,0
And the dual problem equals the unconstrained minimization problem:
min JD(v)
(5)
The objective of REPS to find the minimizer v* of DualReg-v (with regularization level 1)).
Algorithm| raises two practical issues discussed in Section D Specifically, optimization algorithms applied to REPS will typically only give guarantees the near-optimality of v*. We will need to translate near-optimality of v to near primal-ootinnnn
(w.r.t. Jp(A") of X" and then translate that to near-optimality of the final returned policy Tx* Secondly, first-order optimization of the REPS objective requires access to gradient V (v). which involved computing VF*(A") Exact computation of this quantity is often infeasible in practical scenarios where one does not have access to P, but rather only stochastic generative access to samples from P. We show how to compute approximate (biased) gradients of J (v) using samples from distribution 9s.0 (here thought of as behavior policy) and how to use them to derive convergence rates for Relative Entropy Policy Search.
5 Relative Entropy Policy Search
We start by deriving some general results regarding the geometry of regularized linear programs. Our first result (Lemma characterizes the smoothness properties of regularized LP. This will prove crucial in later sections where we make use of this result to derive convergence rates for the REPS objective. We start by recalling the definitions of both strong convexity and smoothness of function.
Definition 6. A function f R -> IR is 3 3-strongly convex w.r.f norm || Il if f(x) 2 f(y) + (VS(y), y) + x y
Let's also define smoothness:
Definition 7. A functiin h is a-soooth w.r.t norm -1 if:
h(u) S h(w) + (Vh(w), (---w] w) + a
- w/l?
(6)
We will characterize the smoothness properties of the dual of regularized linear program. Let's start by considering the generic linear program:
max (r, A), S.L. EA b, A
where r E R", E E Rmxx and b E R. and D is convex domain. Let's regularize this objective using a function f that is f-strongly convex with respect to norm || -|]
max XED
(r, A) - F(A), S.L. EA
(RegI.P)
"moothhnes is independent of the convexity properties of h.
5

---

The Lagrangian of problem RegL Therefore, the dual function 9n R th
is given by gL (A, v) (r. - - V; (b; (E));)
R with respect the original primal regularized LP
gD (v) (v. max (A AED
E) F(X) (v. b) F" (r E),
where the last equality follows from the definition of the Fenchel conjugate of F. It is possible to relate the smoothness properties of F with the strong convexity of F. crucial result that we will use in our results is the following:
Lemma 1. If F is 8-strongly convex w.t.t || over D then F is } -smooth wet the dual || 1-11--
Definitions 6 and are stated in terms of generie norm || and its dual -|- When applied to the REPS objective in Equation 2 using these general norm definitions of smoothness and strong convexity allow to obtain guarantees with milder dependence
S and A than would be possible we were to use their &2 norm characterization instead. We can use the result Lemma tto characterize the smoothness properties of the dual function JD of generic regularized LP.
Lemma 2. Consider the regularized I.P RegL. with r E TR.", E RRmx,, E IR"", and where F is -- strongly convex w.rl. norm The dual function 9D R - R of this regularized L.P is
EEI.. smooth w.r.t the dual norm
|| |l., where
E denote the || norm over the
norm of E's rows.
As consequence of Lemma we can bound the smoothness parameter of J the REPS objective: Lemma 3. The dual function JD(v) is (IS) + 1mmoshoothh in the |loe norm.
5.1 Structural results for the REPS objective
Armed with Lemma 2 we are ready to derive some useful structural properties of the REPS objective. In this section we present two main results. First show that under some mild assumptions it is possible to relate the gradient magnitude of any candidate solution to Jn with its suboptimality gap and second, we show an Lo bound for the norm of the optimal dual solution v*. For most of the analysis we make the following assumptions:
Assumption 2. There is B > 0 such that qs.a 2 Vs,a E S A.
We introduce the following assumption on the discounted state visitation distribution of arbitrary policies x in the MDP, paraphrased from Wang 27]
Assumption 3. There exists > O such that for any policy n, the discounted state visitation distribution X" defined = X5, satisfies X; 2 p.for all states E S.
Suppose we have a candidate dual solution v forJp(v) in DualReg-v with its corresponding
exp(nA")-q where the operators exp and act pointwise and
candidate primal solution
Ž Ea. exp(nA*)q.. "qs.. We denote the corresponding candidate policy (computed using Equa- tion associated with V as (alss). This candidate policy induces discounted visitation distribution म that may be substantially different from X. now show that it possible to control the deviation of primal objective value of X from (A) in terms of J [v)]l:
Lemma 4, Let V E R be arbitrary and let X be its corresponding candidate primal variable. If [V l1)ll E
and Assumptions 2nnd hold then whenever |S| > 2:
(1 + | 11V1
2
where c 1+ogl and Xr the JP optimum.
We finish this section by proving a bound on the norm of the dual variables. This bound will inform our optimization algorithms will allow to set up the right constraints. Lemma S. Under Assumptions
and b
the optimal dual variables are bounded
log [S]AA]
| x
D.
1
From now use the notation D to refer to the quantity on the RHS of Equation ?

---

5.2 Convergence rates
As warm up we derive convergence rates for the case when we have access to exact knowledge of the transition dynamics P and therefore exact gradients. We analyze the effects of using Accelerated Gradient Descent (see Section for a full description of the algorithm) on the REPS objective (v).
Theorem 1 (Accelerated Gradient Descent for general norms. Theorem 4.1 in Allen-Zhu & Orecchia BD. Let D be an upper bound to ||xo, x. 11.. Given an a a-smooth function h w.r.t. the ||+ norm over domain D, then T iterations of Algorithm 4 ensure h(y:) h(x*)()))))))))))())) - 4x
We want to find almost optimal solutions (in function value). Let's define an e-optimal solution: Definition 8. Lete >> O. We say that x is an e-optimal solution of an a --sshohh function R R if hxx) h(x*) ) S where h(x*) minlxRd hxx).
can also show the following bound on the gradient norm for any e-optimal solutions of h. Lemma 6. If is an c-optimal solution for the a-soooth function h I R w.r.f. norm then the gradient
satisfies [[Vh(x)] /2are.
When = Jn the DualReg-V seaiie-vvfuue function in the reinforcement learning setting, we set || Il+ = lxx and || -1- ||I- We are ready to prove convergence guarantees for Algorithm 4 when applied to the objective JD.
2 and hhold. Let D s.I l| DD and d'
log ISILAI
Lemma 7. Let Assumptions T steps of Algorithm the objective function Jp evaluated at the iterate Vr yr satisfies:
After
(1+ c')
JD(vT) - -JD(v") I 4n((S) 1)²
(1 71-7)
Proof. This result follows simply by invoking the guarantees of Theorem making of the fact
that JD is (IS) + 1))n))smmn smooth as proven by Lemma observing that as a consequence of Lemma 5
v* E DD and using the inequality ||x|| < | for x IS.
Lemma can be easily turned into the following guarantee the final dual function value:
(1+c')
Corollary 1. Lete O. If Algorithm 4 is ran at least T rounds where T 2 2n (1 (1->)
then Vy is an c-optimal solution for the dual objective JD.
I' satisfies the conditions of Corollary simple use of Lemma 6 allows us bound the -| || norm of the dual function's gradient at Vz:
JD((V))l S V 2[S + 1)7e
If denote My to be the policy induced by A and X; is the candidate dual solution corre- sponding to v*. A simple application of Lemma yields:
[S|AA 1 log 32pt
((AT))2J((A) /2( 1)nc
2
1-7
y
The following is the equivalent version of optimality for regularized objectives:
Definition 9, Lef We say is an e-optimal regularized policy if J Jp(A²) Jr(Ni) e.
This leads us to the main result of this section:
Corollary 2. For any & > O, and let c" 1+oog
ISILAI 3
IT 2 4n (IS) + 1)3/22 (2+c")²
(1-7)ag then
Jr(A=r)= 2 Jr(A,)) E.
Thus Algorithm accieees an O(1((1 2c) rate an c-optimal regularized policy. We proceed to show that appropriate choice for 1) can be leveraged to obtain e-optimal policy.
Theorem 2. For any > 0, let n 2c Ing( 3
I 2 ([S) + 1)3/2 (1-7)a2 then कr is an
(2-2")²
epoptnall policy.

---

The main difficulty in deriving the guarantees of Theorem liees in the need to translate the function value optimality guarantees of Accelerated Gradient Descent into e-optimality guarantees for the candidate policy тт. This is where our results from Lemma R have proven fundamental. It remains to show that it is possible to obtain an e-optimal policy when access to the true model is only via samples.
Stochastic Gradients
In this section show how to obtain stochastic (albeit biased) gradient estimators JDv for
Vv)J((v) (see Algorithm 2 We use (v) to perform biased stochastic gradient descent steps In Lemma S we prove guarantees for the bias and variance of this
on (v) (see Algorithm
estimator and show rates for convergence in function value the optimum of JD(v) in Lemma I0
We turn these results into guarantees for e-opiimality of the final candidate policy in Theorem Let's start by noting that:
(VvJD(v)), = -1- + (s' "x)) By (71(8" =) -) = =))}
Where B exp(nA"..) and Z = E., exp (nAY, (a As We will make use of this characterization to devise plug-in estimator for this quantity:
Algorithm 2 Biased Gradient Estimator
Input Number of samples Collect samples {(S,, ag, *))) such that (se, ~ while s/ ~ Pa (-182)
for (8, a) E A
Build empirical estimators (t) E x|AI and @(t) E R|Si
Compute estimators (t) exp(nA". (t)
Z(t)
Where 2(t) = Σs, exp(nAV, (t))
end
Produce final sample ($1+1, ac-1) q and 144 Parei (18841))
Compute VvJD(v) such that: (Q.JD(v)), (1 (1-7), B (1201441 m) 1(4411 =))
Output: (v.)
We now proceed to bound the bias of this estimator:
Lemma 8. Let 8, (0, 1) with min 1)-- With probability at least 1 for all & N such
120(In s1811A
that (2
max (480n~>>llvil3 1), the plugin estimator VvJ satisfies:
max (1,2,00
1
E++1
[8]l S
max (1.22200
[[ - -gll. S SE
8
E
E.+ |811
B (t)
3
where g = VvJD(v), g VvJn(v), and E. ||] E su HB
We will now make use of Lemma along with the following guarantee for projected Stochastic Gradient Descent to prove convergence guarantees for Algorithm S
Algorithm Biased Stochastic Gradient Descent
Input Desired accuracy e, learning rates {Tx )o and number-of-samples function n. N + N. Initialize Vo = for = 1,... .T do
Get (v) with ntt) samples via Algorithm
Perform update: v/ <- Ti v.J((v)) vi < 1I (v(), where Ip denotes the projection to
D [v s.t. ||v ol D}.
end
Output: VT.

---

The following holds:
Lemma 9. Let f: Rd + R be an L- function.. We consider the following update:
X(41 X, (V [xx)) + E b,) X++1 1lD(x(+1)-
I S L. then:
1x, x.
|x x.11 + 2r | [(xx)) + +r 5r|lee/1
[(x++1) f(x.)
2r
|b:l ||x: x, 1100 (et, x.).
Lemma implies the following guarantee for the following projected stochastic gradient algorithm with biased gradients (Dv)R
Lemma 10. We assume 2 4 B. Ser S) and Ti 16|8iv/ If we take t gradient steps using Vi
nt) samples from q x P (possibly reusing the samples for multiple gradient computations) with ntt) satisfying n(t)
525r In 100
+1)
Then for all t we have that with probability at least 64
1 1 35 and simultaneously for all t E N such that t
1
E ve) JDlv.))
D Vt
JD
Lemma TO implies that making use of N samples it is possible to find candidate Vy such Ddr ByN
that (n(Vx) (v)) Jn(v.) +
This in turn implies by a simple use of Lemma that
JD 11 < ō (1))) tion of Lemma yields:
If we denote as T the policy induced by X VN simple applica-
/BN1/4
1S Dn
(L-7))BN174
Thus Algorithm 3 achieves an ((1/(1 - >)) rate of convergence to an e-optimal regularized policy. We proceed to we can set to obtain an 6 6-optimal policy:
Theorem 3 (Informal). For any 0 let r
IN
then with アリーーンリン
2e log (og
probability at least 8 8 is possible to find a candidate v such that n is an e e-optimal policy.
7 Conclusion
This work presents an analysis of first-order optimization methods for the REPS objective in reinforce- ment learning. We prove convergence rates of O(1/²²) for accelerated gradient descent on the dual of the KL-regularized max-return LP in the case of a known transition function with convergence rate. For the unknown case, we propose a biased stochastic gradient descent method relying on samples from behavior policy and show that it converges to optimal policy with rate ((1/e²). There are several interesting questions that remain open. First, while directly optimizing the dual via gradient methods is convenient from algorithmic perspective. prior unregularized saddle-poid poinee-pointttc methods have been shown to achieve a faster (11/e) convergence 4 An important open direction is thus to understand if faster rates possible in order to bridge this gap, if optimizing the regularized dual directly is fundamentally limited. Second, we only considered MDPs with finite state and action spaces. It is therefore of interest see if these ideas readily extend to infinite very large spaces through function approximation.
Acknowledgments and Disclosure of Funding
This research supported by the Google-BAIe BAIR Commons program. JL is supported by NSF GRFP.

---

References
[1] Abdolmaleki, A., Lioutikov, R., Peters, J. R., Lau, N., Reis, L. P., and Neumann, G. Model- based relative entropy stochastic search. In Advances in Neural Information Processing Systems, pp. 3537-3545, 2013.
[2] Abdolmaleki, A., Springenberg. J. T., Tassa, Y., Munos, R., Heess, N., and Riedmiller, M. Maximum posteriori policy optimisation. arXiv preprint arXiv: (en:::80660022 2018.
[3] Allen-Zhu, Z. and Orecchia, L.. Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint a
2014.
[4] Bas-Serrano, J. and Neu, G. Faster saddle-pon poilt optimization for solving large-scale markov decision processes. arXiv preprint arXiv:19099 10904, 2019.
[5] Bas-Serrano, J., Curi, S., Krause, A., and Neu, Logistic q-learning, 2020.
[6] Beck, A. and Teboulle, M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3163):167-175, 2003.
[7] Belousov, B. and Peters, f-divergence constrained policy improvement. arXiv preprint arXiv: 00001100000000 2017.
[8] Boularias, A., Kober, J., and Peters, J. Relative entropy inverse reinforcement learning. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics,
pp. 182-189, 2011.
[9] Chen, Y. and Wang, M. Stochastic primal-dual methods and sample complexity of reinforcement learning. arXiv preprint arXiv:1612.00 025116,, 2016.
[10] Chen, Y.. Li, L., and Wang, M. Scalable bilinear ग learning using state and action features. arXiv preprint arXiv: 1804. 10328, 2018
[11] Cheng, C.-A,, Combes, R. T., Boots, B., and Gordon, G. A reduction from reinforcement learning to no-regret online learning. In International Conference on Artificial Intelligence and Statistics, pp. 3514-3524. PMLR, 2020.
[12] Daniel, C.,, Neumann, G., and Peters. J. Hierarchical relative entropy policy search. In Artificial Intelligence and Statistics, pp. 273-281, 2012.
[13] Fox, R., Pakman, A., and Tishby, N. Taming the noise in reinforcement learning via soft updates. 2017.
[14] Geist, M., Scherrer, B., and Pietquin, O. theory of regularized markov decision processes. arXiv preprint arXiv: /901. 1275, 2019.
[15) Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P., et al. Soft actor-critic algorithms and applications. arXiv preprint
arXiv:1812.05900 2018.
[16] Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon. J. Uniform, nonparametric, non- asymptotic confidence sequences. arXiv preprint arXiv:1810.0822 2018.
[17] Jin, Y. and Sidford, A. Efficiently solving mdps with stochastic mirror descent. In International Conference on Machine Learning, pp. 4890-4900. PMLR, 2020.
[18) Kostrikov, Nachum, O., and Tompson, Imitation learning via off off-policy distribution matching, 2019.
[19] Nachum, O. and Dai, B. Reinforcement learning via fenchel-rockafellar duality, arXiv preprint arXiv:2001.01866 2020.
[20] Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D. Bridging the gap between value and policy based reinforcement learning. Advances in Neural Information Processing Systems,
pp. 2775-2785 2017.
[21] Nachum, O., Dai, B., Kostrikov, I., Chow, Y., Li, L.. and Schuurmans, D. Algaedice: Policy gradient from arbitrary experience, 2019.
[22] Neu, G., Jonsson, A., and Gómez, V. A unified view of reguaiy-r markov decision processes. arXiv preprint arXiv: 1705.007997 2017.
[23] Peters, J., Mülling, K., and Altun, Relative entropy policy search. AAAI, volume 10, pp- 1607-1612. Atlanta, 2010.
10

---

[24] Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
[25]
Schulman, J., Levine. S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. International conference on machine learning, pp. 1889-1897, 2015.
[26] Vieillard, N., Kozuno, T., Scherrer, B., Pietquin, O., Munos, R., and Geist, M. Leverage the average: an analysis regularization rl. arXiv preprint 2xXiv:2003.14080 2020.
[27] Wang, M. Primal-dual learning: Sample complexity and sublinear time for ergodic markov decision problems. arXiv preprint arXiv:
2017.
[28] Wang, M. Randomized linear programming solves the discounted markov decision problem in nearly-linear (sometimes sublinear) running time. arXiv preprint (744000704008666 2017. [29] Zimin, A. and Neu, G. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in neural information processing systems, pp. 1583-1591, 2013.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Related Work and Conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Theoretical paper analyzing existing algorithms.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are labeled "Asssuption"" and numbered throughout.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either in the supplemental material hyperparameters, how they
URL.? [N/A]
(b) Did you specify all the training details (e.g., data splits, were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "v34-bNvR4aC", "reviewer": "Reviewer_EGrv", "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). \u000b\u000b\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "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. \u000b\u000b\n\nBy 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. \n\n\nOverall comments on the contributions of this work : \u000b\n\nFirstly, 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. \u000b\n\nIn 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…\u000b\u000b\n\nThe 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).\u000b\u000b\n\nAs 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? \u000b\u000b\n\nThe 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? \u000b\u000b\n\nMy 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?\u000b\u000b\n\nOverall, 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.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "..", "review_text": "", "extra_scores": {"ethical_concerns": "..", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "s1Gu_YCNY8I", "reviewer": "Reviewer_xopv", "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.\nNext they provide the convergence when the updates are being performed by biased stochastic gradients. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "- 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.\n- 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.  \n- 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.\ntypo: line 240: x_0-x_*\n\n****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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The result of this paper is only working for tabular setting.\n- 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).\n- Need for iid sampling of the data.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "kugeuXARtU9", "reviewer": "Reviewer_59AU", "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:\n\n- Showing that the policy suboptimality can be controlled in terms of the gradient norm associated with the approximate solution and some problem-dependent constants.\n- 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.\n- 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. \n- 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "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.\n\nWhile 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.\n\nAll 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I foresee no negative societal impact or any limitations that are not adequately discussed in the paper itself.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "S3I6FjDOutg", "reviewer": "Reviewer_u5HF", "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.\n\nThe main contribution is a convergence theory of REPS in both exact and stochastic settings. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "I have a few questions regarding originality and quality.\n\n(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$. \n\n(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.    \n\nRegarding 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).\n\n(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. \n\n(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. \n\n(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.  \n\n(4). There is no evidence from the experimental results showing the effectiveness of the theory. This gap has to be filled to convince readers.\n \nRegarding 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:\n\n(1). Line 22-30: it is a long technical description. Is this helpful to the motivation of this paper? \n\n(2). Line 33: what do you mean by 'is likely not optimized fully'? any evidence or examples?\n\n(3). Line 36: any reasons why you say 'it is far from clear'?\n\n(4). Line 128, Line 132: is $\\mathbb{E}^\\pi$ the same? \n\n(5). Line 133: what is the domain for $\\lambda^\\pi$?\n\n(6). Line 414: what are $(i)$, $(ii)$, $(iii)$?\n\n(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$.\n\n(8). Line 534, Line 540, Line 541: missing citations.\n\n\nReferences:\n\n[1] On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient. arXiv:1803.06573\n\n============================\n\nPOST-REBUTTAL: Thank you for your response. I have read the response and other reviews. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "GIppIdaf75z", "reviewer": "Reviewer_3BWW", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "The paper starts by identifying two main issues of REPS.\n\nThe 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.\nFurthermore, 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.\n\nThe 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).\n\nAt 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.\n\nIn 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. \n\n__Meriths of the paper__\n\nI 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.\n\n\n__A question__\n\nThe original paper from Peters et al, defined the stationary _undiscounted_ state distribution, i.e.,\n\n$\\sum_a \\lambda_{s,a} = \\sum_{a, s'}P_a(s|s') \\lambda_{s', a},$\n\nhence, defining an average reward setting. \nYour 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$.\n\n__Two sides notes__\n\nWould 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.\n\nAs 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. \n\n__UPDATE__\n\nI want to thank the authors for their detailed response, and all the other reviewers for the useful insights. \nThe 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. \n\nI do not detect problems with the theory. \nFor 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. \n\nThe 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. \n\nIn 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!).\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

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)