Exploiting Minimum-Variance Policy Evaluation for Policy Optimization
Authors: Alberto Maria Metelli
Samuele Meta
Marcello Restelli
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Policy Optimization
Importance Sampling
Variance Reduction

Abstract: Off-policy methods are the basis of a large number of effective Policy Optimization (PO) algorithms. In this setting, Importance Sampling (IS) is typically employed as a what-if analysis tool, with the goal of estimating the performance of a target policy, given samples collected with a different behavioral policy. However, in Monte Carlo simulation, IS represents a variance minimization approach. In this field, a suitable behavioral distribution is employed for sampling, allowing diminishing the variance of the estimator below the one achievable when sampling from the target distribution. In this paper, we analyze IS in these two guises, showing the connections between the two objectives. We illustrate that variance minimization can be used as a performance improvement tool, with the advantage, compared with direct off-policy learning, of implicitly enforcing a trust region. We make use of these theoretical findings to build a PO algorithm, Policy Optimization via Optimal Policy Evaluation (PO2PE), that employs variance minimization as an inner loop. Finally, we present empirical evaluations on continuous RL benchmarks, with a particular focus on the robustness to small batch sizes.

Under review as a conference paper at ICLR 2022
EXPLOITING MINIMUM- VARIANCE POLICY EVALUA- TION FOR POLICY OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Off-policy methods are the basis of large number of effective Policy Optimiza- tion (PO) algorithms. In this setting, Importance Sampling (IS) is typically em- ployed as a what-if analysis tool, with the goal of estimating the performance of a target policy, given samples collected with different behavioral policy. How- ever, in Monte Carlo simulation, IS represents a variance minimization approach. In this field, a suitable behavioral distribution is employed for sampling, allowing diminishing the variance of the estimator below the one achievable when sam- pling from the target distribution. In this paper, we analyze IS in these two guises, showing the connections between the two objectives. We illustrate that variance minimization can be used performance improvement tool, with the advantage, compared with direct off-policy learning, of implicitly enforcing a trust region. We make use of these theoretical findings to build a PO algorithm, Policy Op- timization via Optimal Policy Evaluation (PO*PE), that employs variance mini- mization as an inner loop. Finally, we present empirical evaluations on continuous RL benchmarks, with particular focus on the robustness to small batch sizes.
INTRODUCTION
Policy Optimization methods Fei,eneisootth et al. 2013) have been widely exploited in Reinforce-
ment Learning (RL., Sutton& & Barto 2018) with successful results in addressing, to name few,
continuous-contro) (e.g.. Peters & Schaal 2008 Lillicrap et al.) 2016). robot manipulation (e.g.. Gu
al. 2017 Chatzilyyeroodds et al./ (2200. and locomotion (e.g.. Kohl & Stone 2004 Duan al.
2016). Most of these algorithms employ the notion of trust region (Conn et al. 2000 introduced
ante litteram in the RL literature by the safe RL. approaches (Kakade & Langford 2002 Pirotta
et al. 2013), giving rise to a surge of effective algorithms, having TRPO (Schulman et al. 2015) as the progenitor. The core of any RL algorithm, being value-based or policy-basede lies in the ability to employ the samples collected with the current (or behavioral) policy to evaluate the performance of a candidate (or target) policy (Sutton & Barto 2018). The skeleton rationale behind the usage of trust region is to control the set of candidate policies whose performance can be accurately eval- uated, Intuition suggests that if the candidate policy is "sufficiently close" to the current one, this off-policy evaluation problem (Precup et al. (000)) will provide good estimate for the performance of the candidate policy. Formally, this idea has been studied in the field of Importance Sampling (IS, Owen 2013) and the phenomenon is particularly evident looking the IS estimator variance, which grows exponentially with the Rényi divergence (Rényi 1961) between the behavioral and the target policy (Metelli et al. 2018, 2020). In this off-policy learning (Off-L) setting, IS is employed as what-if analysis tool (Owen, 2013) and its role is passive, as samples have been already collected with the current behavioral policy. In this sense, the trust region an a-posteriori remedy for the limitations of off-policy evaluation, for controlling the uncertainty injected by the IS procedure.
However, IS originated in the Monte Carlo simulation community (Hesterberg 1988, Hammers- ley| (013) as an active tool for variance minimization (Off-VM). While in Off-PL, the behavioral policy is fixed and we look for the best target policy, whose performance we aim to estimate, here the roles are reversed. Indeed, in Off.VM, the target policy is fixed and we search for the behav- ioral policy (from which to collect samples) that yields an IS estimate with the minimum possible variance (Hammersley) 2013 Kahn & Marshall, 1953). It might seem surprising, at first, that sam- pling from a policy, other than the target one, can lead to an estimator with less variance (even zero in some cases) w.r.t. the on-policy estimate. In this role, IS has been previously employed in RI.,

---

Under review as a conference paper at ICLR 2022
mainly to address rare events (Frank et al., 2008: Ciosek & Whiteson 2017) which naturally lead to high- variance estimates, when tackled on-policy. The idea of explicitly using IS as a variance reduc- tion technique, with the goal of finding optimal behavioral policy, proposed by (Hanna al. 2017) for evaluation and subsequently combined with policy gradient learning (Hanna & Stone, 2018 Hanna al., (019). However, in these works, the variance minimization (Off-VM) process and the off-policy learning (Off-PL) problem are treated separately.
The goal of this paper is to investigate the relation between variance minimization (Off-VM) and off-policy learning (Off-PL). The core question we address can be summarized as: "Can Ofj-VM VM be employed as a tool for Off.PL. overcoming the need for an explicit trust region?" ? Intuitively, given a target policy, when the reward function is positive, one way to reduce the variance of the IS estimator to assign larger probability to the trajectories that have a large impact on the mean, i.e., those with high returns. This provides a first hint about the connection between the minimum-variance sampling policy and the performance improvement, i.e., between Off-VM and Off-PL. Furthermore, it suggests that we could repeatedly apply the process of identifying the minimum-variance policy as a tool for policy improvement. The interesting aspect of such an approach is that, by minimizing the variance, it implicitly controls the divergence between two consecutive policies. In other words, it allows enforcing a trust region, without the need for divergence constraints or penalizations.
Outline of the Contributions In this paper, we provide theoretical, algorithmie, and experimen- tal contributions. After having introduced the background (Section 2 we present the problem of finding the minimum-variane the Off-VM problem in two settings: unconstrained (Section 4 and constrained (Section (5). First, assume that there are no restrictions for choosing the behavioral distribution. We show that the Sanimum-varianne behavioral distribution, besides leading to the zero-variance estimator (Kahn & Marshall 1953). is guaranteed to yield performance improvement, requiring the non non- non-neeatiivtyy of the reward only. Furthermore, we prove that this approach allows controlling the divergence be- tween two consecutive distributions, thus enforcing an implicit trust region. Although this provides a valuable starting point, the minimum-variance distribution might be unrealizable given the envi- ronment transition model, i.c., there might be no policy inducing it. For this reason, we move to the scenario in which the distributions are constrained in suitable space. In this setting, the zero- variance estimator could not be achievable. Nevertheless, we prove that such a procedure can lead to performance improvement and preserves the trust region enforcement. Based on these theoretical results, we propose Policy Optimization via Optimal Policy Evaluation (PO*PE), a novel PO algo- rithm, that we particularize for parametric policy spaces (Section 6). Finally, we provide numerical simulations on continuous-control benchmarks, in comparison with POIS (Metelli et al. (008)) and TRPO (Schulman et al. 2015). with particular focus on the robustness of PO to small batch sizes (Section) 7) The proof of the results presented in the main paper are reported in Appendix A
behavioral distribution (Section 33). Then, we study the properties of
2 PRELIMINARIES
In this section, we provide the necessary background that will be employed in the paper.
Mathematical Notation Let X' be a set, and let 3x be a o-algebra over X. We denote with (X)) the space of probability measures over (X' 3x). Let Pe (X)), whenever needed, we assume that P Padmits density function p. For subset y RR we denote with B( the space of measurable functions f' - )) Let P, Q (X) be two probability measures such that P << Q, i.e., P is abso- lutely continuous w.r.t. Q, for every [ [0, co]. we define the a- RéRényi divergence as (Rényi 1961): (a(PIIQ)= - log Sxx ((=))(()))))))))))((((((())))) -=x))-dzz. In the limit of a 1, the Rényi divergence reduces to the KL-divergence (PIl)) while for a it corresponds esssup,-q (xxx)/((x)).
Importance Sampling Let P.QEP9(X with P&Q and let (E).. Importance Sam-
pling (IS. Owen 2013) allows estimating the expectation of f under a target distribution P, ie., Ex- [x]] having samples (Ia)ie(m) collected with behavioral distribution Q: f0p:00
1 [iijn] p(m.) (aaa). The IS estimator is unbiased (Owen 2013), i.e., Ee,-o[@p:ol - [n [x))
but it might suffer from large variance, due to the heavy-tailed behavior (Metelli et al., 2018). The
properties of fo: and its transformations have been extensively studied in the literature (e.g.. lon
ides
2008
Thomas et al. 2015 Papini et al. 2019 Kuzborskij et al. 2021 Metelli et al. 2020
2

---

Under review as a conference paper at ICLR 2022
1994) is 6-tuple =M= Du). where S is the state space, A is the action space, P: A (S)) ) is the transition model, R:S x A- Rmax] is the reward function, ye [0. 1] is the discount factor, and D (S) is the initial state distribution. The agent's 's behavior is modeled by a parametric pol- icy No:S- (A) belonging to parametric policy space Th (To: :0:00000 O5 R... The interac- tion between an agent and the MDP generates trajectory T= (so, a0, $1: -H-,, --1-1...H..H.. (H) where HeN the trajectory length and so Do. at ~ ( S:+1 -ar~ptt P(-]s,,a,) for all tE H [O....H--1] 111. Given trajectory т, the return is the discounted sum of the rewards R(r)= EkT 7,((s,,,,) a,). For a policy To E Ilg,
Policy Optimization A Markov Decision Process (MDP, Puterman A, R, 7
R.
denote with p(-10) the induced trajectory distribution:
p(T]))= IT To(ar)s)) ((sLa))) oz). In the action- based (AB) setting, an agent aims at finding parametrization fulfilling: 0" E arg max (J(0)), where (00)=-r-p(-10) [R(T)] is the expected return. To must be stochastic to ensure exploration. Instead, in the parameter-based (PB) setting, consider hyperpolicy up. belonging peP=R'), from which we sample the parameters 0 of the policy. In this case, the policy To can be deterministic since exploration is managed at the hyperpolicy level and the agent goal becomes to learn a hyperpolicy parametrization maximizing the expected return: p* E arg max (J(p)) where J(p) Eg-v, [J()). In the paper, we keep the presentation as general possible, introduc- ing the results for arbitrary distributions. Then, we will particularize for the parametric PO setting.
parametric hyperpolicy space Np - {up:
3 MINIMUM-VARIANCE BEHAVIORAL. DISTRIBUTION
In this section, we revise VM, i.e., the problem of finding a behavioral distribution QE (X) that induces an IS estimate pa/Q with minimum variance, knowing the (fixed) target distribution PE (X)) and function f c0)) D Furthermore, we do not enforce any restriction on the possible forms of the behavioral distribution (X). The problem and the corresponding well-
known minimum- minimum-vvriance
variance behavioral distribution Q* are stated in the following (Kahn 1950):
p(ar)
((x)
min VVaz-=
((x)
('(x)= ((x))= [x=r([(=)]]
Vee
(1)
(29)
((x)
We observe that the IS estimator PryQ* is non-stochastic, equal to the quantity we aim to estimate,
i.e., ppp:Q* = (x))) This suggests that the construction of Q" is infeasible it requires knowledge of [x=]]f Since Q* generates a non-stochastic estimator, it not only leads to acro-variance but, clearly, simultancously minimizes the absolute central moments of any order. A second, and most remarkable property, is that Q* is performance improvement w.r.t. P, i.e., the expectation of f under Q* is larger than the expectation of f under the target P (Owen 2013):
Varz=rfffs)
Ex-q* ((a=))]Ee--P(()))) E [[(x)[(x)]]]]] >0.
It is worth noting that the magnitude of the improvement is directly related to the reduction in variance Var.~ plf(=)]. Equation 2 suggests an appealing connection between the problem of finding the minimum -inimum-vvrrance behavioral distribution (Off- and the problem of finding target distribution that maximizes the expectation [x-r(((=) (Off-PL). other words, we could employ Off-VM as a performance improvement tool, by repeatedly solving the problem in Equation (
In the following two sections, we will delve into the properties of the repeated construction of the minimum-varianee distribution as performance improvement tool under two assumptions: (i) there are no restrictions the choice of the behavioral distribution QE ((X)) (Section 4): (ii) the behavioral distribution must be chosen within a subset QE Q (XX) (Section 5) In both cases, will address the following three questions: (Q1) Does this procedure always generate a distribution that is performance improvement? (Q2) Does this procedure converge (global local) maximum of f? (Q3) Can we quantify the divergence between two consecutive distributions, i.e., does this procedure enforce trust region?
Before proceeding, let us map this general setting to PO. In the action-based (AB) setting, x is the trajectory т, P and Q are trajectory distributions p()(0) induced by policies ve- Instead, in the parameter-basee (PB) setting, x is the pair (0,r). P and Q are joint distributions 1/ (0(0))((T))) induced by hyperpolicies v In both cases, function is the trajectory return R()).
We restrict our attention to non-negative functions. From the RI. perspective, this choice is w.l.o.g. since we can always define an equivalent non-negative reward function, by means of translation of the original one.
3

---

Under review as a conference paper at ICLR 2022
4 UNCONSTRAINED PROBABILITY DISTRIBUTION SPACE
In Section 3 we have seen that Q* is a performance improvement w.r.t. P. We now generalize this construction, by composing function f with non-negative monotonic stricily-inceeasing function h: (o) - co) The rationale behind this choice is that if h is strictly-increasingg then ho has the same maxima as f We start defining the operator Inoy: Inot:19()) (2))-9()))
p(x))(((()))
(x) (P)o
VxEX..
(3)
Eg Pice-Phhit pf((f((((])(() Thus, Inof takes input a target distribution PE (X)) function ho fe ( (0))).) and out- puts the minimum-vvriance behavioral distribution for the IS estimation of Eg- ((-(((((()))) i.e. Q* Q==In=a [ Intuitively, looking at Equation (3), by iterating the application of Znaf- will ob- tain distributions tending to assign larger probability mass to points IE with high values of f(r). Concerning (Q1), the following result, due to Ghosh al. (2020), generalizes Equation (2) showing that whenever h is increasing, we can prove that Lh f P| is performance improvement w.r.t. P.
Proposition 4.1 (Proposition 9 of Ghosh et al. (2000). ). Let PE (X), (x, and h: [0,00)- - [0, oo) monotonic increasing. Then, f is performance improvement w.r.t. P:
Cov=~r(h(((()) f(x) 20.
(e-Inn((P][[[xd) -Eg-))]]))---)
(e-r(((((a))
Note that, since h monotonic increasing function, we have that Cov=-r((((())), 0 (Cuadras) 2002). The following sections tackle questions (Q2) and (Q3).
4.1 CONVERGENCE PROPERTIES
We now address question (Q2), analyzing the effect of repeatedly applying operator Ihof- More formally, let us consider an initial distribution Pe (X),, and suppose to iterate the application of the operator I generating the sequence of distributions (Qu)keN, where Qo= and for every k No we have Qx = 5 [Q=-1]= (Zhor) The following result shows that, under certain conditions, the operator / admits fixed points and the sequence (Q*)keN converges a distribu- tion Qoc that assigns probability only to the global maxima of f. restricted to the support of P. i.e., (Pp
Theorem 4.2. Let (X) fe o))) and h: h: - 10, monotonic strictly- increasing. Then, the following statements hold:
(i) P is a fixed point Ino i.e., Inof P a.s. if and only if Var [r
(ii let X* = -arggma -argmax meeupppp)) (x)() be the set of maxima of f restricted to the support of P. If X* is non-emply and measarable then, the repeated application of Thos converges to a distribution Qx = =lima-oe (Inof)* [P] with support X In particular [x=]=
maXzesupp(P)) (z))
Some remarks are in order. First, both properties are independent of the function h as long as it is non-negative and monotonic strictly-increasing. This expected since, ho f admits the same set of global optima of f. Second, as a corollary to point (i), any deterministic P is fixed point of Thof- Finally, from point (ii), we deduce that we select P that assigns non-zero probability to all points in X, i.c., supp(P)= XX, the iterated application of Inof converges to the distribution Qzo such that Ex-Qu [f(])) max (f (x)). i.e., we are performing a global optimization f.
4.2 IMPLICIT TRUST REGION
The reader might wonder what are the advantages of casting the optimization of function f as such an iterative procedure. The reason lies question (Q3). We now prove that we are able to naturally control the divergence between two consecutive distributions Q: and Q++1 Ino [[Qu] with &e N. with the effect of enforcing an implicit trust region. The following result shows how it is possible to obtain a bound on the a- RéRényi divergence between two consecutive distributions.
As we shall see in the following sections, the different choices of h will be useful to control the trust region of the optimization process.
4

---

Under review as a conference paper at ICLR 2022
DRu(QullQu-i
10a
Er
10
12
10-2
10
10-5
5
20
40
h
k
8 0.01
0.1 5
0.2 8 3
8 10 ----- B 100
Figure 1: The Ackley function (left), the expectation of the distribution Qx (ohof) [P] (center), and the KL-divergence (right) between two consecutive distributions Qx-1 and Qi: with h h= (.)%
Theorem 4.3. Let (X), [E (0, and h:[0,00)~10,000 monotonic strictly- increasing. Then, for every at [0), it holds that:
log E [h([()))
Da (Ino [Poo[P) a-1
E Bm-p(h([())]
In particular, for = 1 it holds that:
Dri(Ino [P][P]= P Plvls
Ex (e-((h((()))
For a= a= we obtain D [P]I Ba
P((((e))))))))
E. [b(()) Thus, the divergence is large when the variance of h((())) is. The result is particularly remarkable as are able to control the Rényi divergences of any order (0,0,00 o0]. This is a relevant achievement since the trust regions commonly used, like KL-divergence (Schulman et al. 2015), are unable to control higher- order divergences that can still be infinite. We can also appreciate the role of the increasing function h that works regularizer with the effect of controlling the size of the trust region. The following example shows that the faster h increases, the larger the induced trust region becomes.
Fg Ph>
Example 4.1. We consider slight variation of) the one-dimensional Ackley function (Ackley 2012): f(z) = -5 (eoeep(((01144//ppp
exxp(005(oos(22n))) + 1)) + shown in Figure (left) (left) and the class of increasing functions (ho f) f(x)² where 3 We consider an initial uniform distribution P= Uni (n-[5]])]). In Figure ! we plot the expectation of distribution Qx= {Inoo) [P] (center) and the KL-divergence between two consecutive distributions (right), as a function of the number of applications k. for the different B values. We observe that convergence to the global
optimum (x* = and (x= )== = 15) is faster for higher powers that also lead to larger trust regions.
CONSTRAINED PROBABILITY DISTRIBUTION SPACE
The approach we have presented in Section can be applied when there are no restrictions on the class of distributions that can be played, i.e., we can select Q in the whole space (X). However, the action-based PO, we can intervene on the policy wo factors only of the distribution p(r(0)- Do(so) - Te [ar ) P(s 1ls. leading to a constrained setting. Similarly, in the parameter- based PO, we can act on the hyperpolicy Up while keeping the trajectory distribution p(r(0) fixed.
More in general, when considering a class of distributions Q (X') even if P the distri- bution I might not belong to Q.Furthermore, while Ine [P] minimizes all absolute central a-moments of the IS estimator, as it leads to a non-stochastic estimator (Section 3), there may exist different distributions Q minimizing the different absolute central a-moments:
p(x) (((())) - ( [M([==))
min En-Q Q=
((x))
Apart from 2, where the problem in Equation (4) reduces to Equation L for general value of ar co]. the optimization is not straightforward (e.g., Equation (4 not differentiable for a (0,2)) The following result shows that performing moment projection through the a- a-Rényi divergence is a reasonable surrogate for minimizing the absolute central a-moments Equation
Proposition 5.1. Let PE (X), BE [0, ()). and h: (0) - [0,,0) monotonic strictly- increasing, Then, for any a (1, ), it holds that:
5

---

Under review as a conference paper at ICLR 2022
pla (())
( pla ((x)
-
absodate centrol ni-tooment
(unticentraaf) (e-tenmment
Thus, having considered the subset of distributions Q (X), whenever T [] Q we replace with the corresponding moment projection performed through the a-Rényi divergence:
Q E'Eargmn min (aaaamaaaoo Pa([hor[P]liC
(5)
QEQ
In the following, we shall address the questions (QI), (Q2), and (Q3) for the constrained setting.
5.1
PERFORMANCE IMPROVEMENT
In Proposition 4.1 we have seen that, whenever h is strictly-increasing. ] [P] is performance improvement w.r.t. evaluated under function f (and also under the composition between f and any strictly-incrassing function). In this section, we address question (Q1), showing that, when considering a subset distributions Q (X),, the performance improvement cannot in general guaranteed for f, but just for a specific monotonic transformation of f. depending on h and a.
Theorem 5.2. Let PEO increasing. Let == (X)), QE Q, and a [0, o0], then, it holds that:
(x.[0,, and h: -0,,0)-(0000 (0,00) monotonic strictly-
B Pa-p|M((())] a-1
(da-1)) (0-
In particular, for - it holds that (Ghosh et al.
2020 Proposition 6):
Ex-Q ([-=[h(((z))] p( pf (f))) > h( (x)) (DeL PP]] DRL (Ino/ (PP)))))
The theorem shows that by minimizing the a-moment of the transformed function he f. we are able to guarantee a performance improvement on the function (+) oho f. The result holds provided that Da (Inoy[P]llQQ () < Da [Ino|[P]]]
which is always guaranteed when Pe Q and Q=Q', Q', being Q' defined in Equation (5) the minimizer of the second divergence term. In particular, if select h- (-) the guarantee holds for the function f directly. For all other choices, the performance improvement can be guaranteed for a monotonic transformation of f only
5.2 CONVERGENCE PROPERTIES
We now turn to (Q2). By using Equation ( as an iterate Qk+1 Earg me (Da(Zoo QQ)))
to generate a sequence of distributions (Qx keN, we are not guaranteed to converge to any fixed- point distribution Q differently form the unconstrained setting (Theorem 4.2p. This is because the minimization might yield multiple solutions. Nevertheless, we are able to provide guarantees on the final divergence value and on the performance of the distributions Qk-
and h: - (0, monotonic strictly- increasing. Let Q (X) and suppose that ho f is bounded from above, then, the iterate QK+1 E arg argminges (Ine, (Qx (where possible ties are broken arbitrarily) satisfies:
Theorem 5.3. Let Pe ((X), (x.,
(i) the sequence of divergences Da (Iho [Q+]]lQx) is convergent;
(ii) the sequence of expectations E, Qu [=) is non-decreasing in keN and converges to a stationary point of ET [f x: W.E. QE Q.
The convergence of the sequences D., ho f [Q111 and Ex-Qu fx))) 11 is derived by the per-
formance improvement of Theorem 5.2 Importantly, Theorem 5.3 shows the convergence to stationary point of Ezzq [=([(()))]] If is parametric space Q= = {Q& ( IRd), 0. like for a general policy gradient method maximizing (x))) (Papini et al. 2018). Compared to the result for the uncon- strained distribution space (Theorem (.2), we loose the convergence
then we are guaranteed to stop when E Qa [ (x)
fixed point. This property can be recovered under the assumption that the iterate in Equation (5) admits unique solution for every P. In such case, we will converge to a distribution Q. = arg min Qeo (Ino
II Appendix B discuss the effects of optimizing power of f instead of f itself, i.c., when h (.);; while in Appendix we discuss in which the performance improvement be obtained for MDPs.

---

Under review as a conference paper at ICLR 2022
5.3 IMPLICIT TRUST REGION
In Theorem 4.3 we have proved that the a-Rényi divergence between Z and P is bounded. In this section, we answer (Q3), wondering whether similar properties hold when we consider limited set of distributions Q (2). The following result shows that, under a particular form of convexity (van Erven & Harremoës 2014) of 2, we are able control the trust region as well.
Theorem 5.4. Let f [X, (0, and 1::10. -0)..oo))0.oo)) monotonic strietly-iccreasing. Let set (van Erven & Harremoës 2014 Definition 4), Pe Qte
O= (X) be arg argminge (Da (Iho [P]lQ)) and at [ then it holds that: Da (Q & Da
Da (Ine (Ine)LP]]Q').
Therefore, we always guaranteed that the trust region induced by Qt is tighter compared the one induced by Q = f [P] computed in Theorem 4.3 i.e., Da (Q1 )) & Dr (Ine P]]
POLICY OPTIMIZATION VIA OPTIMAL POLICY EVALUATION
In this section, we build a cample-based Off-PL algorithm. named Policy Optimization via Optimal Policy Evaluation (PO*PE), which uses Off-VM as an inner loop. For generality, we consider a parametric distribution space Q= = (Q₂ E 9 RR),
, a common setting met in PO
The structure of POPPE consists of two nested loops. The outer loop (Optimi (Optimization) acts on the target distribution qE.: At the end of each outer iteration ie
Algorithm 1: PO"PE.
input a divergence order, h function, f function, Q distribution space, E initial parameter, n batch size
output: final parameter E1+1
[7]. the target distribution gets1 updated with the last behav- ioral distribution produced by the inner loop 9g...-1" Instead, the
for 1...../oo
Optimization
5,1 E for j= do
Evaluation
Collect Di, ((1)))et) with Qe,,,
inner loop (Eva 1 vat on) takes the target distribution provided by the outer loop ge, and provides new behavioral distribution. At each inner iteration jee [J], it col- lects samples Di, with the current behavioral distribution (g.,, and employs them, together with all the samples collected so far
Using (Di,)) perform M steps of gradient descent on (Ob)
end
Eif
8 iend
(Di,)) Re(r) to compute the next behavioral distribution "+, with the goal of finding the be- havioral distribution minimizing the absolute central a-moment of the IS estimator (Equation 4 As
we shall see, the optimization is performed using samples and by resorting to penalized objective.
Sample-based Optimization The problem of finding the next behavioral distribution parameter E.,+1 using the samples collected far (Dt,s) ke(] is off-policy learning problem. Let define P..- = E ke I.,, as the mixture of the j behavioral distributions experienced so far in the inner loop. Instead of directly estimating D. (Ine [Qe, Qe)). we refer to the (non-central) a-moment, which is connected to the original objective through Proposition[5.]] Since have samples coming from different behavioral distributions, we can use a multiple IS estimator Veach & Guibas (1995): :
d. (Ine, Qe:
1
Σ
(e(().)) 9g, (#x,,) h (*x,)))
n
q6 (Fr.)))
(*
(b)
The (a) factor accounts that we are using samples collected with the mixture p.j to estimate an expectation under ge, whereas the (b) factor is the actual variable we want to compute the expectation of, i.e., the a-moment. is simple to prove that the expectation of d is indeed the a-moment (Papini et al. 2019). To minimize Equation (6). we employ a variance correction to mitigate the effect of finite samples (Metelli al. 2018), theoretically grounded in the following result.
'In the action-hased PO 0 are the policy parameters and = = while in the parameter-hased PO = the hyperpolicy parameters and E
7

---

Under review as a conference paper at ICLR 2022
Cartpole
Inverted Double Pendulum
Mountain Car
Swimueer
5000
4000
4000
100
80
3000
200
60
Awrrage
2000
2000
300
40
1000
1000
20
2
5
0
2
3
x10
x10*
x10*
Episodes
Episodes
Episodes
Episodes
AB-PO²PE
AB-POIS
TRPO -.- PB-POIS -#-- PB-POPPE
Figure 2: Average return as a function of the number of episodes for different environments and algorithms with batch size n= 100, a= h- Id, and J= (20 runs i 95% bootstrapped c.i.).
Theorem 6.1. Let 2= (X) be set of parametric distributions and let E. I fllo & m, then, if samples are independent, for every de 10, with probability at least 1 - 5 it holds that:
(0c.(0) (g(())
A(F())))
| <da (Ino 1Q.111 m
2log !
LE, (x)
Ex-g
nj X (e) (a) dr.
(Ob))
Some remarks are in order. First, the integral within the square root is an upper bound to the variance In particular, when & = E.. obtain the
of the a-moment estimator du (Ine (1 P.z). ponentiated Rényi divergence, as illustrated in (Metelli et al. 2020). When all involved distributions Guassians, it is possible provide closed-form tight bound on this quantity (Appendix (D). Second, unlike the results available in the literature about concentration of IS estimator, without corrections or transformations, we are able to provide an exponential concentration inequality (de- pendence on delta of the form log(1/8) ), instead of a polynomial concentration (dependence of the form 1/5). This due to the fact that we are dealing with random variables that are bounded to zero from below and they allow applying stronger unilateral Bernstein's 's concentration inequal- ities (Boucheron et al. 2009). The reader might object that to optimize the proposed objective function, designed to enforce an implicit trust region, we are actually introducing an additional cor- rection term. This is necessary for theoretical purposes, but, as we shall see in the Section Z the need for a penalization or constraint is significantly less relevant than in existing approaches, like TRPO (Schulman et al. 2015), or POIS (Metelli et al., 2018).
Sample Collection In the action-based setting (AB-PO*PE),
sample n trajectories (m he(]
independently with the policy To.., and we build the dataset D., = ((,,((()))))))) R(n)) Instead, in the parameter-based setting (PB-PO"PE), we sample independently n policy parameters [te]e and for each of them we run policy To, once generate trajectory 7i The corresponding dataset is given
by Di,= { ((0), n, ((T)) he(n)) For the AB case, the correction in Theorem 6.1 is estimated from
samples, done for the Rényi divergence in [Metelli al. 2018 since it involves integrals between trajectory distributions, while the closed form exists for Gaussian distributions (Appendix D
As noted in Section 5 PO corresponds to constrained setting and, thus, we in general unable to provide a performance improvement guarantee for every h (Theorem 5.2) We show in Appendix C that performance improvement, independently on h, is ensured for deterministic environments and we show some (only theoretical) approaches to extend the guarantee to stochastic environments.
7 EXPERIMENTAL EVALUATION
In this section, we provide the experimental evaluation of POPPE on continuous control tasks. We first compare the learning performance of PO with POIS (Metelli et al. 2018)) and TRPO (Schul- man et al.) 2015) on four benchmarks. Then, deepen two relevant aspects of P its robustness to small batch sizes and the effect of the function h. All experiments are conducted with Gaussian policies, linear in the state, with fixed variance. The experimental details are reported Appendix D Comparison with POIS and TRPO In Figure 2 we show the average return a function of the number of collected episodes, with a batch size n= 100, using a == 2, h= Id (identity function), and one inner iteration (J 1). In the Cartpole environment, observe that the performance of
8

---

Under review as a conference paper at ICLR 2022
Average retturn
2500
Average return
5000
5000
2000
4000
4000
1500
3000
3000
1000
2000
2000
500
0
0
0
4
X10
5
3
4
X10*
6
Episodes x 110
3 5
Episodes
Episodes
AB-PORPR (J
AB-PO (J
8
B 0.1
BI AB-PO'PE (J=
AB-POIS --- TRPO
/ = 0.5
-.
3
= 2 -..... B =
Figure 3: Average return a function of the number of episodes in the Cartpole environment for different algorithms, batch-size and inner iterations / (10 runs + 95% bootstrapped c.i.).
Figure 4: Average return as function of the number of episodes in the Inverted Double Pendulum for different choices of h (.) 8 (5 runs + 95% bootstrapped c.i.).
AB-POOPE is slightly above that of AB-POIS and PB-PO PB-POÅPE; while the fastest learning curve is shown by PB-POÍS. Instead, TRPO converges to suboptimal policy that fails keeping the pole in the vertical position. In the Inverted Double Pendulum experiment, the gap between AB- AB-PO*PE and AB-POIS and TRPO is more evident. The PB versions outperform the AB ones with PO slightly faster than POIS. In the Mountain Car domain, while AB-POIS TRPO, and PB-PO*PE display similar convergence speed, AB-PO*PE and PB-POIS reach the optimal performance faster. Finally, in the Mujoco Swimmer domain (Todorov et al. 2012), AB-PO*PE and TRPO clearly outperform AB-POIS, although the fastest learning curves are displayed by the PB versions of POIS and PO
Robustness to Small Batch Sizes Based on the previous results, further investigate the prop- erties of PO in terms of variance control. In the Cartpole domain, we test the robustness to the reduction of the batch size. In Figure 3 we show the average return function of the number of collected episodes for batch sizes ne { [11, 50} and different number of inner iterations J. Also considering the = 100 case (Figure 2). we notice, as expected, that the variance of each setting increases overall as n decreases. Nevertheless, PO*PE proves to be robust, always succeeding in reaching the optimal performance. Differently, POIS suffers the reduced batch size, while TRPO always converging to the same suboptimal policy. The desirable behavior of PO*PE is indeed an effect of the kind of objective function we employ that explicitly accounts for the variance of the estimator, trying to minimize it, and, as we have shown in the previous sections, it allows enforcing an implicit trust region. Finally, a small number of inner itcrations is beneficial for the stability.
Effect of the Function h While previous experiments consider h as the identity function, we now investigate the effects of using h= (-) i.c., a power function. In Figure we show the learning curves of the Inverted Double Pendulum for different values of 3. We notice that for 8 close (0.5, 1, 2) the curves are not very dissimilar, while for too extreme powers (0.1 and 4) the learning performance degrades. This example shows interesting phenomenon, i.e., even if we optimize power of return, within certain limits, we are still able to converge to a (near-)optimal policy.
DISCUSSION AND CONCLUSIONS
In this paper, we have deepened the study of importance sampling beyond its usage as a passive tool for off-policy evaluation and learning. We imported the role of IS as a variance reduction active tool, typical of the Monte Carlo simulation, to the off-policy learning setting. We have illustrated that by minimizing the absolute central a-moment of the IS estimator we are able to guarantee the performance improvement for a monotonic transformation of the original objective and eventually converge. at least, to a stationary point. Interestingly, this approach is able to naturally induce a trust region, mitigating the need for an explicit penalization or constraint. The experimental evalu- ation confirmed our theoretical findings. PO?PE is able to outperform POIS and TRPO on several continuous control tasks. Our algorithm has proved to be remarkably robust to the reduction of the batch size. This is consequence of using the minimum- variiance behavioral distribution that has the benefit of inducing an implicit trust region. We believe that this work contributes to shed light on an appealing facet of off- policy learning with possible research opportunities. Future works include an extension of the convergence analysis to the sample- setting and an experimentation of PO coupled with more complex policy architectures.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
David Ackley. A connectionist machine for genetic hillelimbing, volume 28. Springer Science & Business Media, 2012.
Stéphane Boucheron, Gábor Lugosi, Pascal Massart, et al. On concentration of self- self-bounding func- tions. Electronic Journal of Probability, 14:1884-1899, 2009.
Konstantinos Chatzilygeroudis. Vassilis Vassiliades, Freek Stulp. Sylvain Calinon, and Jean- Baptiste Mouret. A survey policy search algorithms for learning robot controllers in a handful of trials. IEEE Trans. Robotics, 36(2):328 347, 2020. doi: 10.10997R0.20112255821.. URL
https:://ooi org/ 1 TRO 299821111.2111111
Kamil Andrzej Ciosek and Shimon Whiteson. OFFER: off off-environment reinforcement learning, In Satinder P. Singh and Shaul Markovitch (eds.), Proceedings of the Thirty-First AAAI Conference Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pp. 1819-1825. AAAI Press, 2017.
Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
Carles M Cuadras. On the covariance between functions. Journal of Multivariate Analysis, 81(1): 19-27, 2002.
Mare Peter Deisenroth, Gerhard Neumann, and Jan Peters. A survey on policy search for robotics. Found. Trends Robotics, 211-2):1-142 2013, doi: 10.1561/2300000021. URL httpsstss://d1.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford,
John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines.
https:
//github com/ opena wpwnai/bassee.....eepppppppaaaae /baselllleee ines, 2017.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep re- inforcement learning for continuous control. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICM1.2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceed- ings, pp. 1329-1338. JMLR.org, 2016. URL http: hiet:://proceedinee mlr press/v48/
duan html
Jordan Frank, Shie Mannor, and Doina Precup. Reinforcement learning the presence of rare events. In William W. Cohen, Andrew McCallum, and Sam T. Roweis (eds.), Machine Learning, Proceedings of the Twenty-Fin Seentt-Fifthhaaa International Conference (ICML 2008), Helsinki, Finland, June 5-9, 2008, volume 307 of ACM International Conference Proceeding Series, pp. 336-343, ACM, 10. 1et...1141119000
2008. doi: 10.1145/139015, 139011999611199..1 1390199
URL
Dibya Ghosh, Marlos C. Machado, and Nicolas Le Roux. An operator view of policy gradient methods. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Elsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL htt.htttss://rrceeeiiiee neur ips. cc/ppaperr/222//haa. Cttereoeeeo---ssttttttc. Abstract.htt html
neur
Shixiang Gu Ethan Holly, Timothy P. Lillicrap, and Sergey Levine. Deep reinforcement learn- ing for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE Interna- tional Conference on Robotics and Automation, ICRA 20/7, Singapore, Singapore, May 29 June 3, 2017, pp. 3389-3396. IEEE, 2017. doi: 10. 10.100//RA URL https: RTA.O////CRAAOO 2017.
John Hammersley. Monte carlo methods. Springer Science & Business Media, 2013.
Josiah P. Hamna and Peter Stone. Towards a data efficient off-policy policy gradient. In 2018 AAAI Spring Symposia. Stanford University, Palo Alto. California. USA, March 26-28, 2018. AAAI Press. 2018. URL htLhttts: //aaai/aaaaa..aa//aaaaaaaa http://aaaaaaa//....ea/a /inw/x.dexx./em//
T7578
10

---

Under review as a conference paper at ICLR 2022
Josiah P. Hanna, Philip S. Thomas, Peter Stone, and Scott Niekum. Data-efficient policy evaluation through behavior policy search. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW, Australia. 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1394-1403. PMLR, 2017.
Josiah Paul Hanna al. Data efficient reinforcement learning with off-policy and simulated data. PhD thesis, 2019.
Timothy Classen Hesterberg. Advances in importance sampling, PhD thesis, Citeseer, 1988.
Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statis- lics, 17(2)2295-111, 2008.
H. Kahn and A. W. Marshall. Methods of reducing sample size in monte carlo computations Oper. Res., (5):263-278 1953. doi: 10. 10.12877opre.1.35 1.t./...r......6.... 1.5.263. URL https:://@a..ot//110.122
opre. 1 1.5.26. 263
Herman Kahn. Random sampling (monte carlo) techniques in neutron attenuation problems. i. Nucleonics (US) Ceased publication, 6(See also NSA 3-990), 1950.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Claude Sammut and Achim G. Hoffmann (eds.), Machine Learning, Proceedings of the Nine- teenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, Morgan Kaufmann, 2002.
July 8-1 2002, pp. 267-274,
Nate Kohl and Peter Stone. Policy gradient reinforcement learning for fast quadrupedal locomotion. In Proceedings of the 2004 IEEE International Conference on Robotics and Automation, ICRA 2004, April 26 May 1, 2004, New Orleans, LA, USA. pp. 2619-2624, IEEE, 2004. doi: 10. 109/ 21B80T.2004.1077444
/tt.///oiiooaa URL pttttp::/doi.orr//110 1109 ROBOT. 2004. 1307456
Пía Kuzborskij, Claire Vernade, András György, and Csaba Szepesvári. Confident off-policy evalu- ation and selection through seff-normalized importance weighting. 130:640-648, 2021.
Timothy Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa,
David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016. Conference Track Proceedings, 2016. EtRhttp: 7/ 7/arxiv. wrg. abs 1509 02971
Andreas Maurer et al. A bound on the deviation probability for sums of non-negative random variables. J. Inequalities in Pure and Applied Mathematics, 4(1):15, 2003.
Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grau- man, Nicold Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Process- ing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 5447-5459, 2018
Alberto Maria Metelli, Matteo Papini, Nico Montali, and Marcello Restelli. Importance sampling techniques for policy optimization. J. Mach. Learn. Res., 21:141:11111:75 2020.
Art Owen. Monte carlo theory, methods and examples, 2013.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stock- holmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. preas/v80/papini: 8a. html
PMLR, 2018. URL htttp://prcceedingg mlr.
11

---

Under review as a conference paper at ICLR 2022
Matteo Papini, Alberto Maria Metelli, Lorenzo Lupo, and Marcello Restelli. Optimistic policy op- timization via multiple importance sampling. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 1989-49999, PMLR, 2019.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural Networks, 21(4):682-66) 697, 2008. doi: 00.10066..emmme22208..0222 org/10. 00111111116/100 nwunet............. 2008 0003
URL htttps://dot
Matteo Pirotta, Marcello Restelli, Alessio Pecorino, and Daniele Calandriello. Safe policy itera- tion. In Proceedings of the 30th International Conference Machine Learning, ICML 2013, Atlanta, GA. USA. 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceed- ings, pp. 307-315. Jor.. 2013. URL http: pirotta13: 3.mml
Doina Precup. Richard S. Sutton, and Satinder P. Singh, Eligibility traces for off-policy policy evaluation. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference on Machine Learning (ICMI. 2000), Stanford University, Stanford, CA, USA, June 29 -July 2, 2000, pp. 759-766. Morgan Kaufmann, 2000.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wi- ley Series in Probability and Statistics. Wiley, 1994. ISBN 978-0-47161977-2. doi: 10.1002/ 9780470316887 URL
Alfréd Rényi. On measures of entropy and information. Technical report, Hungarian Academy of Sciences Budapest Hungary, 1961.
John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust re- gion policy optimization. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, vol- ume 37 of JMLR Workshop and Conference Proceedings, pp. 1889-1897. 1889-1897.JM1RR.o00 JMLR.org. 2015. URL http::/procceddinn mll.. wwwpppees///7 http///////chmmamnmm 5 .html
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Philip S. Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off- policy evaluation. In Blai Bonet and Sven Koenig (eds.), Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Jamuary 25-30, 2015, Austin, Texas, USA, pp. 3000-3006. AAAI Press, 2015.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based con- trol. In 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, IROS 2012, Vilamoura, Algarve, Portugal, October 7-12, 2012, pp. 5026 5033. IEEE, 2012. doi: 00.1009/R00..2212.36661111
Tim van Erven and Peter Harremoës. Rényi divergence and kullback-leibler divergence. IEEE Trans. Inf. Theory, 6077):397,-3800, 2014. doi: 10.1 10.1109/TT22001422206000 URL https:
//doi.org/10 10. 1109/1101111 www.1111111....222225522.0 2014.2320500
Eric Veach and Leonidas J. Guibas. Optimally combining sampling techniques for monte carlo rendering. In Susan G. Mair and Robert Cook (eds.), Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1995, Los Angeles, CA, USA, August 6-11, 1995, pp. 428. ACM, 1995. URL https: /ttl///l./// acm. org/citation. efm?id=215498
12

---

Under review as a conference paper at ICLR 2022
A PROOFS AND DERIVATIONS
In this appendix, we report the proofs and derivations, we have omitted in the main paper.
A.1 PROOFS SECTION 4
Proposition 4.1 (Proposition 9 of Ghosh et al. (2020)),
) Let Px) fe (2) and h: [0, 00) (0,cs) monotonic increasing. Then, Ine is performance improvement w.r.t. P:
(ov== 20.
Eg-In 1e--
Ex p=-p({(((2)]
Proof. Let us consider the following derivation:
p(z)h(f(z))
[x-r([(()]] [[.[=))]][x--p(a00 Ex-Ino 1P= [x]]] -
-x,d(())) E p-([(([)(())
E P ((([()) (Ba
Ex-p[h(f(z)]
Co (b((())).
[h(f((((=)))
where we have exploited the definition Inof and the definition of covariance. The result is ob- tained by recalling that h is increasing and the covariance between two increasing functions of the same random variable (i.e., h and the identity function) non-negative (Cuadras 2002).
Theorem 4.2. Let (x) [x. and h:(0,00) 10, 10,00) monotonic strictly- increasing. Then, the following statements hold:
(i) iss a fixed point Inuf, i.e., [P a.s. if and only if [ar
(ii) let X* arg max (1x) be the of maxima of f restricted the support of P. X* is non-emply and measarable then, the repeated application of Tnof converges to a distribution Qx = =lima-ae (Ino)) [P] with support X*. In particular [f=)]
maxzesuppl P) (f()).
Proof. We start with (i). First of all, observe that since h is monotonically strietly- holds that (ara=p[[(xx)) 0 if and only if Var>==[M[[[<)]]]- P a fixed point of Thof, i.e., P Inef [P] a.s. if and only if for all & it holds a.s.:
p(x) p(z))(f(x))
E. ((((()))
that occurs if and only if either p(x) = (r P)) or h(f(()) E,- -{))))))()((((((]]]]]])))))){})) (-> Whenever p(x: is not zero, function h( (x)) constant in supp( P) and, consequently, its variance under P is zero. (=) Suppose that Var Par==p(((f()))) =0, then h(f(z)) = Ex almost surely and, consequently [x-[(A((a)) p(x) almost surely. Let
((x))((((x)
consider (ii). First of all,
easily observe that for every keN:
f())
(Inet) (P)())
[P]
E.
Let f max paX.eeappp()) (x))) consider the function _ı(x))
p(x:)
[(())
and the limit:
f(x)
k
(((z)
X
lim g1(2x) = lim p(x))
k- k=00
ft
otherwise
13

---

Under review as a conference paper at ICLR 2022
Thus, have:
(())
Qx lim k-
(Trof)
[P](2)
lim
k-
Sx
(()
(z)
p(x) p(z)dr
x
lim
Ok (2))
otherwise
Thus, the support of Qu is given by X Consequently, the expectation of f under Qxc given by:
2x - [ (x)x))(x)dx
Theorem 4.3. Let PE (X), fe fe.((x(0,x))) and h: - (0) monotonic strictly- increasing. Then, for every aE 00), it holds that:
B [x{()))
Da hTo [ [P][P)]
log
E ph([fz))]
In particular, for a 1 holds that:
Cov
DRu(Ino [P][[]= [P]]P)
E p [({(]]]]
Proof. Let us consider the following derivation:
J:= [
p())))'pp0--0))00)))))) ((x)
x En-p[h(((>)]] )
p(x))-odz
E [h(((((()))))
[b-p)((((=)]]
By observing that Da ( independent derivation:
[)][[)) - log we obtain the result. For a= we provide an
Drt,(hos(P]]IP) = p(z))(f(>)) log E. [.,
p(z) dx
x [r-r[(((())]
E p log (og E,, - AI ((x)))
[)-P((((T)) Ex [((())))
Cov Pl [o)
where we exploited the definition of covariance in the last line.
A.2 PROOFS OF SECTION 5
c)) and h: (u((0,0)) (0, monotonic strictly- increasing. Then, for any at (1, it holds that:
Proposition 5.1. Let Pe (XX),
E,s p(u) Mf(=)) - ((())
(lee)ccco)) < Ren ( (lxx)
)" = ela 11
absulaae
Proof. First of all, we observe that since Ex-q = for a 1, the absolute central a-moment is smaller equal than the (non-central) a-moment. Thus, for a 1,
14

---

Under review as a conference paper at ICLR 2022
have:
p(x)
R
h(f(z)) -B
((x))
((E))(((()) dxt
(Esr[h(((=))))
((Thoy (z)) do
exp (a - X
(Inor (x) d<x) B Re Pa>p(((())))
By applying the definition of Rényi divergences, we get the result.
Theorem 5.2. Let (X), fe B o.)) and h: -0 monotonic strictly- increasing. Let = (X)), QEQ. and a [0, 00), then, it holds that:
Ex-q [..]((((())]]]] [2_ Ex- [M((()))
(oo-1)D.(ms((p11) (lo-1)D,(Gn,,11133))
In particular, for a= it holds that GGhosh et al. 2020 Proposition 6):
(Ihof (Zass Dxr (no(
Proof. Let consider the following derivation:
Ex [x==(h(((=)))1 ((=))(((=)))dr
g(x)) h h(())))) p(x)
p(x)
(((a)
p()))((()))dd dx
p(xx)
-1) h(f(z)))
xx
x
(((x)
1
1- (p(x)
( h(f()))
p(x))(f(=))
dx
p(x))
a
a-1
x
q(x)
1
= =E>=[(((((z))
p(z))(f(=))ddr
((())
p(z)
h(f(z)))dz
a
((x)
p(a))((())) [e-p(L(((<))
( p(x)'-ada
= E, (ll.-ll(fc))01==--pllP a-1
p(x){(((x))
((x)'
(x)r(h((())]
= -Em-p(((f=)))]
1
1
p(z)h(f(z))
+ PEo=P(((((z)]
exp (a
log
p(z)) la -a
a-1
P(<(((((())]]
1
1
p(z)h(f(x))
-E))(((((())
exp
(a-
1)
a-1
log
Ex- [h([))]
x(x)2~aax
E [([[)))]
B.-r(M((=))))
(a- ((a=1))a(Tnns1P)) _ (Inef 12)
a-1
where line 7 derived from Lemma A.I of (Ghosh 2020).
The second inequality was provided in Proposition
Theorem 5.3. Let PE fe o))) and h0) 20) monotonic strictly- increasing. Let Qc (x) and suppose that ho f bounded from above, then, the iterate Qkt BerrEargmnnee [Qx]]()) (where possible tiey are broken arbitrarily) satisfies:
15

---

Under review as a conference paper at ICLR 2022
(i) the sequence of divergences (a [Q+]]Qs) is convergent; (i) the sequence of expectations Eg-Qq, (x))) is non-decreasing keN and converges to a stationary point of - [h
W.E. QE Q
Proof. Let us consider the sequence of distributions (QN) generated by the iterate in Equa- tion (5), where possible ties are broken with an arbitrary (possibly with a tie-breaking rule Tç dif- ferent for every k). From Theorem 5.2 have for every keN:
Eg-Qu+1 [h(f(z)) Ex Ex~Q, [h(f(x))²
E E [h(f(=))11 (cla-1))a ((0-1DD.Chn/Q01110))---e-- (har-1)) 3
a-1
where we simply exploited that Q& arggaiinng (Da (Ine (QuII Thus, Ex~Qu [h(f(z)) is a non-decreasing function of k. Since ho f is bounded, it must be that lim En Qu [/( (x)) Mo <C,, that proves convergence
Furthermore, being convergent, for k- oc it must be that E..-Q. [ [ and consequently Da
D (Ine IQx Qk++)) Therefore, even if the tie-braking rule prescribes select Q Qu could select Qa instead, since it lead to the same divergence value. Consequently, being Qx solution, we can assert that it is stationary point of the function
Da P (as well Q8+1):
= V 9()) Pa (noo 19x]1191111
(a (a-1)ela-11)) 1)D Jnno 1Q) E [h(f(x)) Va() J. (lffc))
cla 1)Da ela-1))D((2a) (4 [h([()))]
2lc-1) (b J
h(f(x))ddr:
We observe that the latter expression is zero if and only if the gradient of (2=q(1(((=))]] w.r.t. Q zero. Indeed:
Thus, the process converges stationary point of E. Qu (x)())))
Theorem 5.4. Let fe and h:10.co)~10..c
monotonic strictly-increasing. Let
Qc (X) be (1-a)-convex set (van Erven & Harremoës 2014 Definition 4), PE Qte argmingeq (Da [[a[Ino[[P]][)) and [0 then it holds that:
Da Da (Q & Da (In [P][P) - Da, (Ine (P]
Proof. The proof is simple application of Lemma A.2 by taking Q-P. @*+ Q', and P Ihef [P].
A.3 PROOFS SECTION 6
Theorem 6.1. Let Q= (X) be set of parametric distributions and let E,E,E If ho fleo m. then, samples are independent, for every 8e [0, 1], with probability at least 1 5 it holds that:
Ex-g (
(g.((x)) ( (x( ( A(F()))
"] <dw = 1 m
21og 1
q3, (x)
(x) (2)) dr.
nj
(Ob))
'Notice that the improvement holds also for 1. Indeed, while it is true that E,-o, [h(f(x))) <., but in such case function ( (e-1))) is decreasing in its argument.
16

---

Under review as a conference paper at ICLR 2022
Proof. We start observing that each addendum of da (Q,, Qe: is non negative. Since all terms are ii.d.. we can apply unilateral Bernstein's 's inequality (Maurer et al. 2003) that allows achieving exponential concentration. Thus, for every òe [0,1], with probability at least 1 - 8 it holds that:
(( (00 b(F(()) ((( (E(())
"]]
Ex-E
& du (E.o199.]11Q::44
+ v /2
[ā ( (..))
log 1og3
Thus, it remains to provide a bound on the variance term. We exploit the fact that (x) " and that each addendum represents an i.i.d. random variable:
Varz,=0., da (Ihof (Q,,110;;;
2 (..j( (F (((()))
Le. (Tx,))
E 1iss
(nj)²
keLi [=(n]
20
qs, (Tk,,)
27
Exc, Ris
(nj)²
kE LE(n)
27
qg, (2)
)
Ba-oss
(2)
nj
A.4 TECHNICAL LEMMAS
Lemma A.1. For every x = O and or (0,1) (1,00), it holds that:
x- a (1-18) 1
1--2--)
Furthermore, for a holds that:
x - 1 log.r
Proof. Consider the auxiliary function 9a (x) ( -- _ We are going prove that
the minimum of (x) zero. Suppose > 1, then ga (0)= -00== and ga (o)) xo. Thus, the minimum must lie in between and since function Ja is differentiable, we have:
2 dx Ia (x)
=
r=
Thus, we have go (1)=0. O. Suppose now that a< 1, we have again, the minimum must lie in between and with the same calculations as before, we conclude (1) The case a trivial.
and (00) 0o. Thus,
Lemma A.2. Let PE and let ae (0) Let (P) be an (a 1)-convex (van Erven & Harremoës 2014 Definition 4) subset of distributions. Let Q2* E Q be the a-moment projection:
= argmin (PIQ))
Qeo
If Qa exists, then for every QE Q holds that:
+
17

---

Under review as a conference paper at ICLR 2022
Proof. The proof of the result is inspired to (van Erven & Harremoes 2014 Xe [0,1] and let us define Qx as the (1 a, (1 - -mixture of Q and Q:
Theorem 14). Let
[x(=)= = _ ((1 - 1)9a (x) (x) +1q(x)= -0) -
r'o
2x -x x
{ ((1 (1) (x) (x) +Xq(z)
T-o dx.
Let first observe that for A= have Qo Q== and Zu= = Jn qr (z)dx=1. Since Q is (1- a--convex and Q* is the minimizer over Q, it holds that 2x Da (P(P(NN)\a First of all, we compute:
S( -o 2--11 S (1
1aa Jdr
2 01 24 - S (1=
(g(x)) - - -9 (x) (x) dx.
The latter, for x= becomes:
1]. For calculation easiness,
8X A-0
instead of directly operating on Da (P)))) we consider:
S p(x) (x)) dr= Z
as x
x
+(a-1) 1)2
(11 (11-))(z)0' (() "dd..
x
We now evaluate it at 2=
Œd I (x))
dr+ p(z))
=
A-0
x
dæ J (()))
p(x)
xx
For a 1, we require a (x))
7 0. to obtain:
2-n
J (())) dx>
(z))
dx (1)))
By applying both sides the log function and dividing by a- > we get the result. Symmetrically, for a<1, 1, we require the converse obtain the desired result.
r-o $0. Recalling that a-r <0, we
B OPTIMIZING MOMENTS OF f
In this appendix, we analyze the effect of optimizing a power instead of f.
Lemma B.I. Let PE (X)) and fe M(, [m. m.. If (1, it holds that:
0 (cExPL((<))) [E (
(m En- [(x))) (En~ [f(x)]([)))))))(((( m) E. [f(x)) (m- m)
m
m
In particular for a = 2, we have:
EsE [[x)) (E.- (m- ( Ez- [f(x))) (En-~ [[(()) mm),
that is the Bhatia-Davis inequality for the variance.
18

---

Under review as a conference paper at ICLR 2022
Proof. We explicitly consider the optimization problem, for a and having denoted μ Bg=P[f(x))
plz)f(x)ddz
F:X .x
S.t.
p(x))(x)=1
(=)
Since a> 1, the optimization problem corresponds to the maximization of concave function subject linear and box constraints. is simple prove that the optimal solution must assign extreme values to function f. Let pe [O, 11, the linear and box constraints enforce:
pm + (1 p)m
m m
From which, by substitution in the objective function, we have:
S( p(a) pmn + -p)mm m ( 11) 177 m
Thus, in general, optimizing moments of the function f, leads to different optimal policies compared to optimizing function f directly. However, from the above results, we see that this discrepancy reduces when the expectation Eg approaches the extreme value (and also m. but this is less interesting since we are maximizing). The value m can be indeed achieved if we have no restrictions on the distribution space (Section
C PERFORMANCE IMPROVEMENT FOR THE MDP SETTING
As already mentioned in Section when consider the MDP setting, we do not have the full control of the trajectory distribution p(r[0)= (oo) 1 H=1
Te ((st)))
ar) the factors
involving the transition model P and the initial state distribution Do are out of the control of the policy and the policy itself me is limited due to the parametrization. As consequence, performing a step of optimization of the a-moment is able to provide improvement guarantees on J(0) only by choosing the transformation function h= (-) (Theorem 5.2 In this appendix, prove that under specific conditions we are able to provide guarantees on the improvement of J(0). Moreover, show approaches, with main theoretical interest, to extend the performance improve- ment guarantees to the case of stochastic MDPs. They must not to be intended as implementation proposals, but rather as theoretical approaches to cope with this phenomenon.
C.I ACTION-BASED PO
We start with the action-based PO setting.
Deterministic MDPs If the MDP is deterministic (i.e., P and Do are deterministic), we denote the next state 81+1 = P(ss; Thus, the trajectory distribution is governed by the policy mo only: p(r[0)= = 8- To (a)l)s))). In such case, provided that the policy space θ is sufficiently powerful, by minimizing any of the a-moments, we are able to guarantee the performance improvement. Indeed, in such a case, neglecting the limits of the parametrization O, we are in an unconstrained setting.
For general stochastic MDPs, the trajectory density function depends the transition model probabilities. Thus, we need to design an estimator that get rids these elements. To this purpose, denote with 0)) the probability of having observed sequence of actions a= (An, 41 (n when playing policy To in the MDP. we take E=E[R(T)le i.e., the ex- pectation of the return conditioned to the sequence of actions,
Stochastic MDPs
again in unconstrained
19

---

Under review as a conference paper at ICLR 2022
setting, neglecting the limits of O Therefore, are able to guarantee the performance improve- ment on ((0). Nevertheless, this requires to design an estimator of EE [[[(r)]a), that might be a not easy task.
C.2 PARAMETER-BASE BASED PO
We now consider the parameter- based PO setting.
Deterministic MDPs and Policies In the case of deterministic MDPs and deterministic policy me. we have that for every 0 θ the support of the trajectory distribution is made of one trajectory only. In such case, ignoring the limits of the hyperpolicy parameter space P, we in an unconstrained setting.
Stochastic MDPs Policies In the of stochastic MDP or stochastic policy (or both), we have a trajectory distribution in which we do not have the possibility to intervene on the pol- icy and transition model factors. Thus, need to consider estimators that get rid of these stochastic elements. If we take f= [[ parametrization 0, we reduce the unconstrained setting, with the corresponding performance im- provement guarantee. It is worth noting that, compared to the action-based setting, estimating J(0) notably simpler compared to the estimation of E [T]]]]a]
i.e., the expected return conditioned to a policy
D CLOSED FORM OF THE INTEGRAL FOR GAUSSIANS
In this appendix, we derive a closed form for the integral involved in the computation of the bound of Theorem in the case that all involved distributions are Gaussians and for a a= 2. Let us introduce the notation:
# == - En),
o=N(us Ed);
v=N(Ha, En).
(8)
We have to compute the following integral:
Jx Φ(x (x))x(x)² dx.
(x)
Let us start elaborating on the integrand function, denoting for properly sized vector and matrix S, mils =xx Sx and [S] the determinant of S:
(x d(x)v(x)²
(2x) 2k (all-exx]
-22
(2 k/2 EB 1/2 exp
(-1/2] 11 x
-1|E ( 111x-1ue1l,,- mulls
(-1x-
(2x) k/2 -1/2 E, -2
11/2 Σx -1 exp -2 - - + 1/2/X- 1 1 ||x Hullz 1
Now, we have deal with the argument of the exponential:
2||x x uu
2 S 1/2
| ES | Mu 2 ΣS
T (1E, -1
- -1---_1 x (1E,p -1 " Es -1- 2E,, -1p)))
2
M
br
1 T En 14 - us "Es us
(4pp
-Me 241 T TE -1,m)
2
We now proceed completing the square:
x Mx-2b"x x= x-=xx=-i-
(x-M b/ MD b 'b..
Thus, we have:
1
x Mx - 2b" 1)
1 M M- b- 1 cc
2
20

---

Under review as a conference paper at ICLR 2022
Moreover, observe that the following expression is the density of v-variate normal distribution with mean b and covariance matrix M
(2T)
h/2 M
11
1/2 exp -x (x MM
Thus, its integral is 1. Therefore, coming to the initial expression:
(x) dx
(2nr)
k/2 pu -2
(2T))
M M 1
-
b MMM
1 -c M
x ((x)x(x)²
EΦl
11/ 1/2 Σn
exp
2
//1
EΦl
1//
(b
(
b b-c)
exp
En
P 1/2
E EXPERIMENTAL DETAILS
In this appendix, report the experimental details and additional experimental results.
Infrastructure The experiments have been run on two machines:
2 CPUs Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz (22 cores, 44 thread, 55 MB cache) and 128 GB RAM;
x Intel(R) (eon(R) CPU ES-4610 v2 @ 2.30GHz (8 cores, 16 thread, 16 MB cache) and 256 GB RAM.
Environments The environments are the rllab implementations DDann et al. 2016). MIT li- cense, https://githttii com/r11/rlla) The Swimmer environment belongs the Mu- joco suite [Todorov et al. 2012). MuJoCo Personal License, http::/t//wtt mu www.ooooooooooooooooooooooooo org/
Algorithms The TRPO implementation is taken from baselines (Dhariwal et al. 2017 7 MIT li- cence, https:///// ht//gtttu com/ wttp///paaeeeinneeeeee For POIS the original imple- mentation (Metelli et al. 2018), MIT license, httpttps:///gttuu...oot...
ines
Hyperparameters In order properly compare the algorithms,, set of 20 seeds has been chosen. A subset of 5 seeds, underlined, was used to test the performances during the tuning phase. Once the optimal hyperparameters were found, the experiments were extended the other 15 seeds. In the following, we report the hyperparameter values for PO?PE.
The shift return refers the need for making the return non-negative in order to perform the opti- mization of the a-moment in PO?PE. This procedure is carried out independently at each algorithm iteration by subtracting the minimum return among the ones observed. The variance init hyperpa- rameter refers to the logarithm of the standard deviation. All experiments have been carried out with Gaussian policies linear with mean linear in the state variables and constant variance uniform over the state space.
Cartpole
seeds: 0, 11, 16, 19, 42, 66, 72, 84, 87, 90, 123, 222, 343, 404, 452, 542, 875, 943, 999
max iters: 500
policy: linear
policy init: zeros
capacity:
inner:
variance init: -1
step size: 1 gradient norm
penalization: True
delta: 0.75
21

---

Under review as a conference paper at ICLR 2022
max offline iters: 10
Mountain Car
seeds: 0 3, 11, 16, 19, 42, 66, 72, 84, 87, 90, 123, 222, 343, 404, 452, 542, 875, 943, 999
iters: 500
policy: linear
policy init: zeros
capacity:
inner:
variance init: -1
step size: 2/ gradient norm
penalization: True
delta: 0.9
max offline iters: 10
shift return: True
Inverted Double Pendulum
seeds: 0, 3, 11, 16, 19, 42, 66. 72, 84, 87, 90, 123, 222, 343, 404, 452, 542, 875, 943, 999
max iters: 500
policy: linear
policy init: zeros
capacity:
inner:
variance init: -1
step size: 2 gradient norm
penalization: True
delta: 0.99
max offline iters: 10
Swimmer
seeds: 0, 3, 11, 16, 19, 42, 66, 72, 84, 87, 90, 123, 222, 343, 404, 452, 542, 875, 943, 999
max iters: 500
policy: linear
policy init: zeros
capacity:
inner:
log-std init: -0.6
step size: 1 gradient norm
penalization: True
delta: 0.99
offline iters: 10
shift return: True
22

---

Under review as a conference paper at ICLR 2022
7
0
0.01
0.1
5000
5000
4000
4000
3000
3000
400
Average
2000
2000
2000
300
1000
1000
200
100
0
0.5
1.5
0.5
1.5
0
0.5
1.5
0.5
1.5
x 10
x
x x10
x
Episodes
Episodes
Episodes
Episodes
PR-POIS
PR-POOPE
Figure 5: Learning curves comparing PB-POIS and PB-PO*PE with increasing magnitude of the noise (20 runs, 95% c.i.).
For POIS (both AB and PB) and TRPO, the same hyperparameter value have been used, except for the algorithm-specffic ones that have been tuned with the same protocol diseussed above (őgL {0.001, 0..0,,0.1,11 In particular, for POIS, we employ the line search procedure presented in the original paper for setting the step-size. The following table summarizes the algorithn-specifcc hyperparameter values for the different algorithms and environments.
Environment / Algorithm
PO?PE (delta)
AB-POIS (delta)
TRPO (max kl)
Cartpole
0.75
0.4
0.01
Mountain Car Inverted Double Pendulum
0.9
0.9
0.01
0.99
0.1
0.001
Swimmer
0.99
0.8
0.01
Environment / Algorithm
PB-POIS (delta)
PB-PO*PE (delta)
Cartpole Mountain Car
0.4
0.6
1
0.00001
Inverted Double Pendulum
0.1
0,999999
Swimmer
0.4
0.4
E. NOISE ROBUSTNESS
As we have shown in Appendix using the trajectory return R(7) function f does longer allow to provide performance improvement guarantees. Nevertheless, we conjecture that the loss of this property compensated by the variance reduction implicit our approach. In the direction of empirically showing this aspect, we tested the parameter-base Double Pendulum environment, with forced stochasticity in the environment. Specifically, whenever an action is prescribed by the policy the actual action to be executed is obtained by adding while Gaussian noise with standard deviation a. The results are shown in Figure 5
version of PO in the Inverted
We observe that our algorithm is overall competitive with PB-POIS and, in the case of a 1, significantly outperforms PB-POIS.
E.2 ABOUT RETURN TRANSLATION
Our approach be employed for non-negative functions f. Since in the PO experimental evaluation we employ f f Under the assumption that the immediate reward is bounded R(s a) [ Rmax] for all ( A, can make the return function with simple transla- tion and preserving the optimality of policies:
R(()= = R(()) - Rmin
Cmnin
23

---

Under review as a conference paper at ICLR 2022
1-7" is the minimum achievable return. Of course, we can perform the translation where Rmin I-y
even by using a constant ca Cmin Rmin 1-y and still obtain a translated return that remains
positive, It is worth noting, from Theorem that the size of the trust region is larger as the constant approaches the its minimum possible value.
For instance, we consider a a= 2, f 0, and we apply a further translation with ca 0. From Theo- rem we have:
Ex- [x-r([((x)+ +c) = log Ex- R=.r11/100)++++2__-111 (PIl))
Eg pl)x() +c-
Since E, [f(x))
32 P[xx[[((]] we have that this expression maximized with the smallest
value of c, i.e. c=0. 0.
24


Reviews:
[{"review_id": "wJYSYFB2G1T", "reviewer": "Reviewer_9jPT", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "Strengths:\n\nThe paper considers an important problem: the minimization of variance in off-policy policy gradient methods.\nUsual (unbiased) estimators rely on importance sampling. In the community, such estimators, are considered to suffer from high variance. \nThe high variance comes from the \"mismatch\" between the behavior policy and the optimization policy.\nCleverly, the authors turn the utilization of importance sampling as a variance minimization approach, by finding the optimal behavior policy w.r.t. this objective.\n\nThe method is sound and sheds light on different aspects of of-policy gradient estimation. In particular, this minimum-variance approach is shown to theoretically improve the policy and to provide implicitly a trust region (which is usually needed in off-policy policy optimization).\n\nThe authors provide a theoretical analysis of their approach, considering approximation due to the impossibility of the realization of the trajectory distribution. \n\nThe authors provide also an empirical analysis of their algorithm, comparing it with TRPO and POIS, analyzing its robustness w.r.t. small batch-sizes (which, usually, can affect negatively the variance), and analyzing the effect of the function $h$.\n\nTo conclude, the problem considered is important, the proposed method is sound, the theoretical and empirical analysis are satisfying. \nIn addition, I think that the authors made a good job in drawing connections with related work.\n\nWEAKNESSES\n\nAs also considered in POIS, the usual policy gradient can happen at two different levels: parameter and action. In fact, the authors of POIS provided both a parameter-based POIS and an action-based POIS. \n\nThe most common policy gradient methods, like SAC, PPO, TRPO, DDPG, are action-based. It seems to me that PO^2PE, instead, is parameter-based. I ask the author to confirm or deny this.\n\nI think that this is actually the most unclear point of the paper. All the derivations are kept abstract, by considering generic samples $x$. It is not clear to me if the sample $x$ (for example in Equation 6) are policy parameters (i.e., like in $\\omega_{\\rho'/\\rho}(\\theta)$ in page 16 of https://www.jmlr.org/papers/volume21/20-124/20-124.pdf) are trajectories, or are something different. In my understanding, $x$ should be regarded as \"lower-level\" policy parameters, and $q$ is a process sampling policy parameter (what \"A Survey on Policy Search for Robotics\", calls Exploration in Parameter Space, page 16). \n\nIf this is the case, then I do not fully understand the comparison with TRPO. TRPO performs exploration in the action space. \n\nFurther, I think it was not specified in parameter-base POIS or action-based POIS was utilized.\n\nMy suggestion, however, is to well clarify what $x$ is at the beginning of the document. \n\nIn general, I think that while the authors did a great job in explaining the theory, they used little space in the paper to describe the actual algorithm. In general, I would enjoy more reading the paper, if more and clear references were made in the theory about the RL problem and the designing of the algorithm. \n\n\nTo outline another minor issue, the experiments consider only low-dimensional benchmarks. The usage of a more complicated high-dimensional environment would have made this submission stronger. \n\n\n\n\n", "summary_of_the_paper": "Importance sampling (IS) is at the core of many off-policy reinforcement learning (RL) algorithms. \nThe common use of IS in RL is to consider a _fixed_ policy behavior, say $q$ and an optimization policy $p$. The samples are acquired with the behavior policy $q$. The objective is to maximize\n\n$$\n\\max_p \\mathbb{E}_{x\\sim q}\\left[\\frac{p(x)}{q(x)}f(x)\\right].\n$$\n\nThis approach suffers from high variance. \n\nThis paper highlight that originally, IS was thought to _reduce_ the variance of Monte-Carlo estimates. The main idea of this paper is to use IS as a variance minimization technique. It is interesting to see that the $\\min_q Var[p(x)/q(x)f(x)]$ leads to a _policy improvement_.\n\nThe paper is structured as follow:\n\n1. The authors show in Equation 1 the _minimum variance_ $q^*$. This analytical result is (as far as I understand) purely theoretical and cannot be used directly in RL. Note that Equation 2 also shows how the minimum variance behavior is a policy improvement.\nThe authors, therefore, suggest that one could simply iterate the minimum variance to consistently improve the policy. At this point, a few questions remain open: will this process converge to a local or global optimum? Can one quantify the divergence between consecutive distributions?\n\n2. To study the convergence properties, the authors introduce an operator $\\mathcal{I}$ which takes in input a distribution $p$ and produces the next _minimum variance_ distribution $q$, which will be the next behavior policy. The operator $\\mathcal{I}$ has several fixed points: if $p$ is deterministic then $p = \\mathcal{I}p$. Theorem 4.2 ensures that the iterated application of $\\mathcal{I}$ converges to the optimum in the domain of $p$.\n\n3. Often, trust-region methods are used in RL to ensure stability in the learning process. Theorem 4.3 shows that the application of $\\mathcal{I}$ produces a policy with bounded Renyi divergence with the previous policy. Interesting, this result is valid for any order of the divergence. This result is stronger than many other results in RL, where the divergence is only bounded for a unique order (typically 2: KL divergence), leaving the divergence on other orders unbounded. \n\n4. However, the finding $q^*$ is often not possible. In short, if we consider a generic set of distribution, the application of $\\mathcal{I}$ to an element of the set, might produce a distribution not contained in the set. The authors need at this point to devise an _approximation_ of $\\mathcal{I}$, and check again for the convergence properties. \nThe first approximation consists in minimizing a $\\alpha$-Renyi divergence. The difference between classic divergence minimization (or constraint) approaches is that in this paper, the authors are constraining divergence between \"return distribution\" (even though modified by the monotonic function $h$) rather than the divergence between parameter distribution or state distribution like in REPS or TRPO (@authors: correct me if I am wrong on this point).\n\n5. The authors analyze the policy improvement of this \"approximated\" operator. They notice that the policy improvement happens only for some particular choice of $h$  \n\n6. The authors prove in Theorem 5.4 that the approximated operator has a tighter trust region (for every single choice of $\\alpha$) w.r.t. the unconstrained operator $\\mathcal{i}$.\n\n7. The authors provide a practical algorithm in Section 6, and evaluate its efficacy in four classic control benchmarks. They also provide an analysis of the hyperparameters used (monotonic function $h$ and batch-size).\n\n\nTo summarize, the paper proposes a different use of IS, which allows both for variance reduction and policy improvement. \nThe improvement scheme is new (although it can be related to other approaches) and sheds new light on policy gradient optimization. \n\n\n \n", "summary_of_the_review": "PROS\n\nThe paper considers an important problem and proposes a sound solution to it. I did personally enjoy learning the application of the importance sampling technique to reduce the estimation variance. I think that the theory shed new light on off-policy policy gradient algorithms.\n\nThe theoretical and empirical analyses are satisfying. \n\nCONS\n\nThe clarity of exposition could be improved by making the theory more linked to the actual RL problem. \n\nThe authors considered only low-dimensional problems in the empirical evaluation, raising the question of whether the algorithm could be applied to more complex domains. However, I think that the theoretical analysis compensates for this minor weakness.\n\n\nI would like the authors to clarify the doubt I wrote in the main review.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XncbK7Hwc5", "reviewer": "Reviewer_pKkx", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "## Strengths:\n\n1. The paper raises an interesting connection between the two types of importance sampling. Usually in RL we are thinking of using importance sampling to re-weight off-policy updates, but here the authors take inspiration from the Monte Carlo estimation community and instead try to find the policy that will yield the lowest variance importance-weighted estimator. While this connection seems to have been briefly made by Hanna et al. for policy evaluation (as cited in the paper), the idea to use this in policy optimization seems novel and interesting.\n2. The connection yields a novel algorithm that will potentially have different strengths than previous policy optimization methods. This has the potential to expand the array of available policy optimization algorithms. \n\n\n\n## Weaknesses:\n\n1. Clarity. The entire paper is presented at such a level of generality that it is often unclear how the method and theory pertain to the RL problem and how the algorithm compares with other methods. One particularly stark example of this problem is the function $ f$. Throughout the paper everything is presented as trying to optimize $ f$, but it is never made clear how $ f$ relates to the RL problem in particular (which seems to be the ultimate goal of the paper). This makes it especially difficult to compare POPE to related algorithms. There is not a clear explanation in the paper about how POPE is similar and different to TRPO for example in a formal way. This sort of context would make the paper much easier to understand.\n2. A fundamental problem is hidden by the lack of clarity. The issue of defining $ f $ is finally addressed in Appendix C where it is explained that $ f $ can only easily be defined for RL problems in deterministic MDPs and even then relies on having a \"sufficiently powerful\" policy space, where the exact definition of this sufficiency is left vague. The fact that the algorithm cannot function in stochastic environments without estimate $ \\mathbb{E}[\\mathcal{R}(\\tau)|\\underline{a}]$ (according to appendix C) seems like a serious problem.  This seems to be a fundamental limitation of the proposed algorithm and the misdirection and obfuscation of the problem in the paper is a serious issue. Moreover, it is very unclear how the algorithm is actually implemented in experiments given this limitation. \n3. The paper provides no clear reason to prefer the proposed algorithm over alternatives. There doesn't seem to be any theory as to what particular cases the proposed algorithm would improve over something like TRPO. There is some evidence in the experiment section of a slight improvement on some small-scale problems, but I will address this more fully below. In general, the paper lacks a coherent comparison to related policy optimization methods.\n4. The algorithm is proposed as a multi-level optimization where evaluation is carried out inside of an inner loop. However, in practice the number of iterations of the inner loop is set to $ J=1$. This calls into question why the algorithm needed the complicated multi-level structure to begin with. Is the inner loop of the algorithm necessary? Why might it be beneficial? When $ J=1$, the algorithm seems to be much simpler. Is it more similar to related policy optimization algorithms in this case?\n5. I see a few problems with the experiments in the paper:\n   1. Hyperparameter tuning. Were all algorithms tuned in the same way? Appendix E does not give enough information to tell. It seems that 4 values of one hyper parameter were tuned for TRPO, but that perhaps several times more hyperparameters were tuned for POPE (between delta, std/variance init, and step size, not to mention $ \\beta$ and $J$ which also seem to be tuned from Figures 3 and 4). \n   2. Scale of experiments is small. A major motivation for TRPO and PPO is that they work well wit neural net policies on large-scale problems. It is difficult to conclude that POPE is a better or more useful algorithm without a comparison in those larger settings with neural network policies and larger MDPs. \n   3. The batch-size experiments don't seem to have very clear motivation. The paper emphasizes some experiments using very small batch sizes, but it is not clear why the different between batch sizes of ~10 and ~50 matters very much. They are all small enough to easily fit into memory and be computed quickly, especially with linear policies. It's unclear why this is a benefit of the proposed approach.\n\n\n\n**Typos**:\n\n- Page 4 after Thm 4.2: \"all three properties\", but there are only two properties listed in the theorem \n- Page 5, example 4.1, last sentence: \"elad\" should be \"lead\"\n- Page 5, section 5, second paragraph \"More in general, when consider\" is not grammatical", "summary_of_the_paper": "This paper proposes a novel policy optimization algorithm called POPE that is based off of ideas about how to use importance sampling for variance reduction from the Monte Carlo estimation community. The paper proves that the policy that minimizes the variance of the evaluation step actually provides a policy improvement, and then creates an algorithm that repeatedly estimates the minimal variance policy as a policy improvement step. It concludes with some small-scale experiments with linear policy classes on low-dimensional control tasks and claims modest improvements over TRPO and POIS baselines. ", "summary_of_the_review": "While the paper provides an interesting connection that yields a (to my knowledge) novel algorithm, I don't think it is ready for publication at this time. There are major issues with clarity that make it unclear how the algorithm is implemented at all and I am wary of a few parts of the experimental setup too. But, the core idea is interesting enough that I would encourage the authors to resolve these issues and re-submit the paper to another conference. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "L943EbLVnIA", "reviewer": "Reviewer_P7sd", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## Strong points:\nSignificance and Novelty: The paper is motivated by the technical tools of importance sampling (IS). The starting point of the paper is the difference of using IS in different communities, in RL community, IS is served as a **passive** tool but in Monte Carlo simulation community the behavior policy of IS can be **actively** picked and learned to reduce the variance. The minimum-variance behavior distribution can also be served as an improved policy compared with the original one. The paper later discuss how this minimum-variance policy can connect with the trust region improvement by discussing several theorems with the Renyi's Divergence.\nI enjoy reading those connections and I think the discussion of the minimum-variance policy reveals a new way to thinking trust region/safe RL algorithm, which can draw a potential interest of the RL community.\n\nTechnical Clarity: The paper is well-organized the easy to follow. The mathematical formula is clear and strict.\n\nSoundness: all the proof is sound to me.\n\n## Weak points:\nEmpirical Clarity: I feel like the final algorithm is not that clear from the first pass of my reading especially the inner loops of the algorithm (see detailed questions below).\n\nEmpirical Evaluation: The design of the experiment is fine and clear to me, but I would expect for more ablation study coming up along the the detailed discussion in the previous Section, such as the choices of $\\alpha$ and more choices of h (such as Ackley function you mentioned in Figure 1).  I would feel like the empirical results does not fully support the theoretical discussion.\n\nThe Original Motivation: Most of the paper (section 4-5) discussed the policy improvement property of the minimum-variance policy. But I think the **variance** itself is as importance as a topic you might also want to highlight, as you mentioned the robustness to small batch size in the experiment. I would expect a paragraph to make this point more clear (for now from Eq. (6) I could have a vague sense why the algorithm is robust to small batch size)\n\n## Questions:\nHere are a few questions I would like the authors to answer to clarify my understanding.\n\n1. Does Eq. (6) your final objective? Or do you include the finite sample upper bound in Theorem 6.1 as well? If you use Eq, (6), how do you guarantee a minimization of Line 5 in your algorithm? It seems to me in Appendix D you mention a closed form for Gaussian, is that the closed form for minimization of Eq. (6) (or Theorem 6.1)? Or do you just use several steps of stochastic gradient descent?\n\n2. It seems to me that in the experimental session you fix $\\alpha = 2$. Have you tried different $\\alpha$? How will $\\alpha$ affect the robustness of batch sizes.\n\n3. The model assumption you use for TRPO, POIS and you algorithm is a linear Gaussian policy. What happened if you use a more complex policy class such as neural network? Will your algorithm still outperform TRPO in this case?\n\n4. Most of the analysis in your algorithm is not specific to RL. But in RL, there is a famous \"curse of horizon\" phenomenon in long horizon setting [1] when your importance ratio is using the product of policy ratio for each time step. Is that a problem in your experiment? How long is the horizon you use in your experiments? \n\n## Minors:\nIn the paragraph under Theorem 4.2, \"all three properties\" should be \"both properties\" (I did not see 3 properties in Theorem 4.2).\n\nReferences:\n1. Liu, Q., Li, L., Tang, Z., & Zhou, D. (2018). Breaking the curse of horizon: Infinite-horizon off-policy estimation. arXiv preprint arXiv:1810.12429.", "summary_of_the_paper": "The paper proposes a policy improvement algorithm inspired by the minimum-variance policy of importance sampling (IS) technique in Monte Carlo simulation community. Properties of the new policy improvement algorithm such as convergence and implicit trust region are well studied in the paper. And in practical, the paper leverages a surrogate objective with the non-central alpha-moment as the finite sample objective for the algorithm. The new algorithm is used in the policy optimization in reinforcement learning. Empirical experiments on several continuous control demonstrate the benefit of the new proposed algorithm compared with existing trust region baselines, especially on the robustness to the small batch sizes.", "summary_of_the_review": "Although there are several points need to be addressed by the authors, I feel the theoretical contribution is strong enough to recommend at least a borderline acceptance at this point. I am open to raise my score if my questions can be addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L7eMvCn5lNH", "reviewer": "Reviewer_Ruth", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "========== Novelty =============\n\nThe idea of relating importance sampling (IS) to policy optimization and policy evaluation is not new. However, this paper digs into the technique of finding variance-minimization behavior distribution of IS, and establishes a few interesting & novel results related to policy optimization.\n\n========== Literature reviews =============\n\nThis paper has followed the general logic and narrative of [1], relating \"trajectory-based\" policy optimization with IS. In \"stepwise-based\" formulation of RL, which is more common in the general RL literature, [2-5] also adopt ideas of stepwise IS for policy evaluation and optimization. I think such prior work and direct references therein should be of direct interest.\n\n[1] Metelli et al, policy optimization via importance sampling, 2018\n[2] Jiang et al, doubly robust off-policy value estimation for reinforcement learning, 2015\n[3] Munos et al, safe and sample efficient off-policy reinforcement learning, 2016\n[4] Huang et al, from importance sampling to doubly robust policy gradient, 2020\n[5] Tang et al, taylor expansion policy optimization, 2020\n\n========== Detailed questions =============\n\n1. Throughout the paper, the authors assume the function f to be non-negative, such that the mathematical treatment of the variance-minimizing behavior distribution is more straightforward. I wonder how this can be implemented in practice, when the return functions are negative. For example, in many high-d continuous control benchmarks (e.g. Ant from openai gym), the initial returns are negative. Since on these environments, the trajectory lengths are not constant, adding a constant positive reward to each time step will not work since it modifies the optimal policy of the problem. If we add a single positive constant to the entire return, what constant should we choose? How does the additive constant impact stability of the algorithm?\n\n2. Eqn 2 shows that the improvement is proportional to the variance of f under the previous distribution. In case the algorithm erroneously converges to a locally optimal deterministic policy, does it mean that the algorithm cannot get out of the local optimal because in such cases the improvement is zero (zero variance from a deterministic policy). Do such observations happen in practice with sampling errors & function approximations?\n\n3. The implicit trust region in Thm 4.3 is interesting from a theoretical perspective, in that one could adjust the effective trust region size based on diff choices of the function h. However, I wonder how useful this result is in practice. In particular, can we choose h in a computationally efficient way to enforce a trust region of particular sizes? How do we estimate the implicit trust region given that it takes the form of a ratio? The trust region also depends on the numerical scale of f itself, which brings back to the issue of tackling problems where f is originally negative -- in this case, adding diff positive offset values will impact trust regions too. Can the authors elaborate on such points?\n\n4. I suggest that the authors update algo 1 to reflect how the algorithm is implemented in practice. From what I understand, algo 1 specifies the ideal algorithm of finding variance minimizing behavior dist at each iteration. However, since the objective is rather diff to estimate, one resorts to an upper bound optimization with finite samples in Eqn 6, backed by Prop 5.1. Then the authors introduce a finite sample correction in Thm 6.1. This makes the algorithm a bit difficult to understand.\n\n5. On experiments, I think the TRPO results in Fig 2-4 are a bit questionable. TRPO has long been considered a good performing algorithm if not state-of-the-art, yet I am rather surprised to see TRPO gets underperformed by many IS baseline algorithms on such low-dimensional problems. I wonder if the TRPO implementation deviates much from the original TRPO algorithm in Schulman et al, 2015.\nDo the authors adopt a trajectory-based TRPO implementation or the stepwise-based TRPO implementations in Schulman et al, 2015?\n\n6. Trajectory-based formulation of policy optimization is easier for mathematical treatment but I would argue it has limited application in large-scale practices. I think this is because product of IS ratios usually induce too much variance that in practice such methods are not quite stable. On toy examples, I could understand that such methods are still useful. This leads me to wonder -- is there a way to extend such formulations to step-wise optimization algorithms (PPO, TRPO, IMPALA, MPO...), in which case such ideas could be made more practically appealing.\n\n7. All toy examples seem to have a natural non-negative return function. I wonder if the algorithm could be useful when returns are by design negative, in which case the choice of h is critical.\n\n8. Minor note: I suggest replacing Q_theta by another notation as Q_theta confuses with Q-function, whereas here it refers to the parametric dist.", "summary_of_the_paper": "The paper analyzes the connection between searching for an optimal behavior policy that minimizes variance, and policy improvement in RL. The paper shows a number of interesting theoretical results, such as non-negative policy improvements, convergence and connections to implicit trust regions between consecutive policy iterates. The paper also shows results in constrained case where the policy class is parameterized. Finally, the paper shows empirical results on a few low-dimensional RL examples.", "summary_of_the_review": "Overall, I think the paper is solid in its theoretical contributions, yet is a bit lacking in a few important practical aspects.\n\n1. Trajectory-based formulations of policy optimization is not practical when horizons are long. The application of such techniques to RL feels very black-box, as they do not leverage the Markov structure of the problem at all. I think extending such techniques to step-wise based policy optimization algorithm would make the approach more practically appealing.\n\n2. Empirical results are a little bit suspicious in that TRPO underperforms in a significant manner. I would even argue that the combination of this approach with ideas from TRPO can make a more solid empirical case.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received a split of scores, from 3 to 10. Among the reviewers, there are both strong advocates and strong rejects. All reviewers agree that finding a policy that is not only improving value but also has lowered variance is an interesting ideas. However, many reviewers point out that are major clarity issues that might hide fundamental problems. The proved guarantees seem to require strong assumptions that are unlikely to hold in practice, and experimental comparisons also have some subtleties. Taking together, although this could be a very interesting work, it will require a major revision and another round of review+discussions before it can be shaped into an acceptable paper.
Decision: Reject