Year: 2021

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 (POPE), 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.

heading: 1 INTRODUCTION
text: Policy Optimization methods (PO, Deisenroth et al., 2013) have been widely exploited in Reinforcement Learning (RL, Sutton & Barto, 2018) with successful results in addressing, to name a few, continuous-control (e.g., Peters & Schaal, 2008; Lillicrap et al., 2016), robot manipulation (e.g., Gu et al., 2017; Chatzilygeroudis et al., 2020), and locomotion (e.g., Kohl & Stone, 2004; Duan et 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-based, 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 a trust region is to control the set of candidate policies whose performance can be accurately evaluated. Intuition suggests that if the candidate policy is “sufficiently close” to the current one, this off-policy evaluation problem (Precup et al., 2000) will provide a 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 at the IS estimator variance, which grows exponentially with the Rényi divergence (Rényi, 1961) between the behavioral and the target policy (Metelli et al., 2018; 2020). In this off-policy learning (Off-PL) setting, IS is employed as a 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 is 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; Hammersley, 2013) 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 behavioral 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 sampling 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 RL,
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 reduction technique, with the goal of finding an optimal behavioral policy, was proposed by (Hanna et al., 2017) for evaluation and subsequently combined with policy gradient learning (Hanna & Stone, 2018; Hanna et al., 2019). 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 Off-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 is 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, algorithmic, and experimental contributions. After having introduced the background (Section 2), we present the problem of finding the minimum-variance behavioral distribution (Section 3). Then, we study the properties of the Off-VM problem in two settings: unconstrained (Section 4) and constrained (Section 5). First, we assume that there are no restrictions for choosing the behavioral distribution. We show that the minimum-variance behavioral distribution, besides leading to the zero-variance estimator (Kahn & Marshall, 1953), is guaranteed to yield a performance improvement, requiring the non-negativity of the reward only. Furthermore, we prove that this approach allows controlling the divergence between 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 environment transition model, i.e., there might be no policy inducing it. For this reason, we move to the scenario in which the distributions are constrained in a suitable space. In this setting, the zerovariance estimator could not be achievable. Nevertheless, we prove that such a procedure can lead to a performance improvement and preserves the trust region enforcement. Based on these theoretical results, we propose Policy Optimization via Optimal Policy Evaluation (PO2PE), a novel PO algorithm, 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., 2018) and TRPO (Schulman et al., 2015), with a particular focus on the robustness of PO2PE to small batch sizes (Section 7). The proof of the results presented in the main paper are reported in Appendix A.

heading: 2 PRELIMINARIES
text: In this section, we provide the necessary background that will be employed in the paper.
Mathematical Notation Let X be a set, and let FX be a σ-algebra over X . We denote with PpX q the space of probability measures over pX ,FX q. Let P PPpX q, whenever needed, we assume that P admits a density function p. For a subset YĎR, we denote with BpX ,Yq the space of measurable functions f :XÑY . Let P,QPPpX q be two probability measures such that P !Q, i.e., P is absolutely continuous w.r.t. Q, for every αPr0,8s, we define the α-Rényi divergence as (Rényi, 1961): DαpP }Qq“ 1α´1 log ş X ppxq αqpxq1´αdx. In the limit of αÑ1, the Rényi divergence reduces to the KL-divergence DKLpP }Qq, while for αÑ8, it corresponds to esssupx„Q tppxq{qpxqu.
Importance Sampling Let P,QPPpX q with P !Q and let f PBpX ,Rq. Importance Sampling (IS, Owen, 2013) allows estimating the expectation of f under a target distribution P , i.e., Ex„P rfpxqs having samples txiuiPrns collected with a behavioral distribution Q: pµP {Q“ 1 n ř iPrns ppxiq qpxiqfpxiq. The IS estimator is unbiased (Owen, 2013), i.e., Exi„QrpµP {Qs“Ex„P rfpxqs, but it might suffer from large variance, due to the heavy-tailed behavior (Metelli et al., 2018). The properties of pµP {Q and its transformations have been extensively studied in the literature (e.g., Ionides, 2008; Thomas et al., 2015; Papini et al., 2019; Kuzborskij et al., 2021; Metelli et al., 2020).
Policy Optimization A Markov Decision Process (MDP, Puterman, 1994) is a 6-tuple M“ pS,A,P,R,γ,D0q, where S is the state space, A is the action space, P :SˆAÑPpSq is the transition model, R :SˆAÑr0,Rmaxs is the reward function, γ Pr0,1s is the discount factor, and D0 PPpSq is the initial state distribution. The agent’s behavior is modeled by a parametric policy πθ :SÑPpAq belonging to a parametric policy space ΠΘ“tπθ :θPΘĎRdu. The interaction between an agent and the MDP generates a trajectory τ“ps0,a0,s1,a1, . . . ,sH´1,aH´1,sHq where H PN is the trajectory length and s0„D0, at„πθp¨|stq, st`1„P p¨|st,atq for all tP t0, . . . ,H´1u. Given a trajectory τ , the return is the discounted sum of the rewards Rpτq“ řH´1 t“0 γ
tRpst,atq. For a policy πθ PΠΘ, we denote with pp¨|θq the induced trajectory distribution: ppτ |θq“D0ps0q śH´1 t“0 πθpat|stqP pst`1|st,atq. In the action-based (AB) setting, an agent aims at finding a parametrization fulfilling: θ˚ PargmaxθPΘ tJpθqu, where Jpθq“Eτ„pp¨|θq rRpτqs is the expected return. πθ must be stochastic to ensure exploration. Instead, in the parameter-based (PB) setting, we consider a hyperpolicy νρ, belonging to a parametric hyperpolicy space NP“tνρ : ρPPĎRlu, from which we sample the parameters θ of the policy. In this case, the policy πθ 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: ρ˚ PargmaxρPPtJpρqu, where Jpρq“Eθ„νρrJpθqs. In the paper, we keep the presentation as general as possible, introducing the results for arbitrary distributions. Then, we will particularize for the parametric PO setting.

heading: 3 MINIMUM–VARIANCE BEHAVIORAL DISTRIBUTION
text: In this section, we revise Off-VM, i.e., the problem of finding a behavioral distribution QPPpX q that induces an IS estimate pµP {Q with minimum variance, knowing the (fixed) target distribution P PPpX q and function f PBpX , r0,8qq.1 Furthermore, we do not enforce any restriction on the possible forms of the behavioral distribution QPPpX q. The problem and the corresponding wellknown minimum-variance behavioral distribution Q˚ are stated in the following (Kahn, 1950):
min QPPpX q
"
Varx„Q
„
ppxq qpxqfpxq
*
ùñ q˚pxq“ ppxqfpxq Ex„P rfpxqs , @xPX . (1)
We observe that the IS estimator pµP {Q˚ is non-stochastic, equal to the quantity we aim to estimate, i.e., pµP {Q˚“Ex„P rfpxqs. This suggests that the construction of Q˚ is infeasible as it requires knowledge of Ex„P rfpxqs. Since Q˚ generates a non-stochastic estimator, it not only leads to zero-variance but, clearly, simultaneously minimizes the absolute central moments of any order. A second, and most remarkable property, is that Q˚ is a 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):
Ex„Q˚rfpxqs´Ex„P rfpxqs“ Varx„P rfpxqs Ex„P rfpxqs
ě0. (2) It is worth noting that the magnitude of the improvement is directly related to the reduction in variance Varx„P rfpxqs. Equation (2) suggests an appealing connection between the problem of finding the minimum-variance behavioral distribution (Off-VM) and the problem of finding a target distribution that maximizes the expectation Ex„P rfpxqs (Off-PL). In other words, we could employ Off-VM as a performance improvement tool, by repeatedly solving the problem in Equation (1).
In the following two sections, we will delve into the properties of the repeated construction of the minimum-variance distribution as a performance improvement tool under two assumptions: (i) there are no restrictions in the choice of the behavioral distribution QPPpX q (Section 4); (ii) the behavioral distribution must be chosen within a subsetQPQĎPpX q (Section 5). In both cases, we will address the following three questions: (Q1) Does this procedure always generate a distribution that is a performance improvement? (Q2) Does this procedure converge to a (global or local) maximum of f? (Q3) Can we quantify the divergence between two consecutive distributions, i.e., does this procedure enforce a 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 ppτ |θq induced by policies πθ. Instead, in the parameter-based (PB) setting, x is the pair pθ, τq, P and Q are joint distributions νρpθqppτ |θq induced by hyperpolicies νρ. In both cases, function f is the trajectory return Rpτq.
1We restrict our attention to non-negative functions. From the RL perspective, this choice is w.l.o.g. since we can always define an equivalent non-negative reward function, by means of a translation of the original one.

heading: 4 UNCONSTRAINED PROBABILITY DISTRIBUTION SPACE
text: 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 a non-negative monotonic strictly-increasing function h : r0,8qÑr0,8q. The rationale behind this choice is that if h is strictly-increasing, then h˝f has the same maxima as f .2 We start defining the operator Ih˝f :PpX qÑPpX q:
pIh˝f rP sqpxq“ ppxqhpfpxqq
Ex„P rhpfpxqqs , @xPX . (3)
Thus, Ih˝f takes as input a target distribution P PPpX q, a function h˝f PBpX , r0,8qq, and outputs the minimum-variance behavioral distribution for the IS estimation of Ex„P rhpfpxqqs, i.e., Q˚“Ih˝f rP s. Intuitively, looking at Equation (3), by iterating the application of Ih˝f , we will obtain distributions tending to assign larger probability mass to points xPX with high values of fpxq. Concerning (Q1), the following result, due to Ghosh et al. (2020), generalizes Equation (2) showing that whenever h is increasing, we can prove that Ih˝f rP s is a performance improvement w.r.t. P . Proposition 4.1 (Proposition 9 of Ghosh et al. (2020)). Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic increasing. Then, Ih˝f rP s is a performance improvement w.r.t. P :
Ex„Ih˝f rP srfpxqs´Ex„P rfpxqs“ Covx„P rhpfpxqq,fpxqs
Ex„P rhpfpxqqs ě0.
Note that, since h is a monotonic increasing function, we have that Covx„P rhpfpxqq,fpxqsě 0 (Cuadras, 2002). The following sections tackle questions (Q2) and (Q3).

heading: 4.1 CONVERGENCE PROPERTIES
text: We now address question (Q2), analyzing the effect of repeatedly applying operator Ih˝f . More formally, let us consider an initial distribution P PPpX q, and suppose to iterate the application of the operator Ih˝f , generating the sequence of distributions pQkqkPN , where Q0“P and for every kPNě0 we have Qk“Ih˝f rQk´1s“pIh˝f qk rP s. The following result shows that, under certain conditions, the operator Ih˝f admits fixed points and the sequence pQkqkPN converges to a distribution Q8 that assigns probability only to the global maxima of f , restricted to the support of P , i.e., supppP q. Theorem 4.2. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Then, the following statements hold:
(i) P is a fixed point of Ih˝f , i.e., Ih˝f rP s“P a.s., if and only if Varx„P rfpxqs“0; (ii) let X ˚“argmaxxPsupppP qtfpxqu be the set of maxima of f restricted to the support of P .
If X ˚ is non-empty and measurable then, the repeated application of Ih˝f converges to a distribution Q8“ limkÑ8 pIh˝f qk rP s with support X ˚. In particular Ex„Q8rfpxqs“ maxxPsupppP qtfpxqu.
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 is expected since, h˝f admits the same set of global optima of f . Second, as a corollary to point (i), any deterministic P is a fixed point of Ih˝f . Finally, from point (ii), we deduce that if we select P that assigns non-zero probability to all points in X , i.e., supppP q“X , the iterated application of Ih˝f converges to the distribution Q8 such that Ex„Q8rfpxqs“maxxPX tfpxqu, i.e., we are performing a global optimization of f .

heading: 4.2 IMPLICIT TRUST REGION
text: The reader might wonder what are the advantages of casting the optimization of function f as such an iterative procedure. The reason lies in question (Q3). We now prove that we are able to naturally control the divergence between two consecutive distributions Qk and Qk`1“Ih˝f rQks with kPN, with the effect of enforcing an implicit trust region. The following result shows how it is possible to obtain a bound on the α-Rényi divergence between two consecutive distributions.
2As we shall see in the following sections, the different choices of h will be useful to control the trust region of the optimization process.
Theorem 4.3. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Then, for every αPr0,8s, it holds that:
Dα pIh˝f rP s}P q“ 1 α´1 log Ex„P rhpfpxqqαs Ex„P rhpfpxqqsα .
In particular, for α“1 it holds that:
DKLpIh˝f rP s}P q“ Covx„P rhpfpxqq, loghpfpxqqs
Ex„P rhpfpxqqs .
For α“2, we obtain D2pIh˝f rP s}P q“ log Ex„P rhpfpxqq 2s Ex„P rhpfpxqqs2 ď Varx„P rhpfpxqqs Ex„P rhpfpxqqs2 . Thus, the divergence is large when the variance of hpfpxqq is. The result is particularly remarkable as we are able to control the Rényi divergences of any order αPr0,8s. This is a relevant achievement since the trust regions commonly used, like KL-divergence (Schulman et al., 2015), are unable to control higherorder divergences that can still be infinite. We can also appreciate the role of the increasing function h that works as a 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.
Example 4.1. We consider (a slight variation of) the one-dimensional Ackley function (Ackley, 2012): fpxq“´5`20expp´0.1414|x|q`expp0.5pcosp2πxq`1qq`e, shown in Figure 1 (left) and the class of increasing functions ph˝fqpxq“fpxqβ where βě0. We consider an initial uniform distribution P “Unipr´5,5sq. In Figure 1, we plot the expectation of distribution Qk“pIh˝f qkrP s (center) and the KL-divergence between two consecutive distributions (right), as a function of the number of applications k, for the different β values. We observe that convergence to the global optimum (x˚“0 and fpx˚q“15) is faster for higher powers that also lead to larger trust regions.

heading: 5 CONSTRAINED PROBABILITY DISTRIBUTION SPACE
text: The approach we have presented in Section 4 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 PpX q. However, in the action-based PO, we can intervene on the policy πθ factors only of the distribution ppτ |θq“ D0ps0q śH´1 t“0 πθpat|stqP pst`1|st,atq, leading to a constrained setting. Similarly, in the parameterbased PO, we can act on the hyperpolicy νρ while keeping the trajectory distribution ppτ |θq fixed. More in general, when considering a class of distributions QĎPpX q, even if P PQ, the distribution Ih˝f rP s might not belong to Q.Furthermore, while Ih˝f rP s minimizes all absolute central α-moments of the IS estimator, as it leads to a non-stochastic estimator (Section 3), there may exist different distributions in Q minimizing the different absolute central α-moments:
min QPQ
" Ex„Q „ ˇ ˇ ˇ
ˇ ppxq qpxqhpfpxqq´Ex„P rhpfpxqqs
ˇ
ˇ
ˇ
ˇ
α*
. (4)
Apart from α“2, where the problem in Equation (4) reduces to Equation (1), for general value of αPr0,8s, the optimization is not straightforward (e.g., Equation (4) is not differentiable for αPp0,2q). The following result shows that performing a moment projection through the α-Rényi divergence is a reasonable surrogate for minimizing the absolute central α-moments of Equation (4).
Proposition 5.1. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Then, for any αPp1,8q, it holds that:
Ex„Q „ ˇ ˇ ˇ
ˇ ppxq qpxqhpfpxqq´Ex„P rhpfpxqqs
ˇ ˇ ˇ ˇ
α
loooooooooooooooooooooooooomoooooooooooooooooooooooooon
absolute central α-moment
ďEx„Q „ˆ ppxq qpxqhpfpxqq
˙α
looooooooooooooomooooooooooooooon
(non-central) α-moment
“epα´1qDαpIh˝f rP s}QqEx„P rhpfpxqqsα.
Thus, having considered the subset of distributions QĎPpX q, whenever Ih˝f rP sRQ, we replace it with the corresponding moment projection performed through the α-Rényi divergence:
Q: Pargmin QPQ tDαpIh˝f rP s}Qqu . (5)
In the following, we shall address the questions (Q1), (Q2), and (Q3) for the constrained setting.

heading: 5.1 PERFORMANCE IMPROVEMENT
text: In Proposition 4.1, we have seen that, whenever h is strictly-increasing, Ih˝f rP s is a performance improvement w.r.t. P , evaluated under function f (and also under the composition between f and any strictly-increasing function). In this section, we address question (Q1), showing that, when considering a subset of distributions QĎPpX q, the performance improvement cannot be in general guaranteed for f , but just for a specific monotonic transformation of f , depending on h and α.
Theorem 5.2. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Let QĎPpX q, QPQ, and αPr0,8s, then, it holds that:
Ex„Q rhpfpxqqαs´Ex„P rhpfpxqqαsě Ex„P rhpfpxqqsα
α´1
´ epα´1qDαpIh˝f rP s}P q´epα´1qDαpIh˝f rP s}Qq ¯ .
In particular, for α“1, it holds that (Ghosh et al., 2020, Proposition 6): Ex„Q rhpfpxqqs´Ex„P rhpfpxqqsěEx„P rhpfpxqqspDKLpIh˝f rP s}P q´DKLpIh˝f rP s}Qqq .
The theorem shows that by minimizing the α-moment of the transformed function h˝f , we are able to guarantee a performance improvement on the function p¨qα ˝h˝f . The result holds provided that Dα pIh˝f rP s}QqďDα pIh˝f rP s}P q, which is always guaranteed when P PQ and Q“Q:, being Q: defined in Equation (5) as the minimizer of the second divergence term. In particular, if we select h“p¨q1{α, 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.3

heading: 5.2 CONVERGENCE PROPERTIES
text: We now turn to (Q2). By using Equation (5) as an iterate Qk`1 PargminQPQ tDαpIh˝f rQks}Qqu to generate a sequence of distributions pQkqkPN , we are not guaranteed to converge to any fixedpoint distribution Q8, differently form the unconstrained setting (Theorem 4.2). 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.
Theorem 5.3. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Let QĎPpX q and suppose that h˝f is bounded from above, then, the iterate Qk`1 PargminQPQ tDαpIh˝f rQks}Qqu (where possible ties are broken arbitrarily) satisfies:
(i) the sequence of divergences DαpIh˝f rQks}Qkq is convergent; (ii) the sequence of expectations Ex„Qk rhpfpxqqαs is non-decreasing in kPN and converges to
a stationary point of Ex„Q rhpfpxqqαs w.r.t. QPQ.
The convergence of the sequences DαpIh˝f rQks}Qkq and Ex„Qk rhpfpxqqαs is derived by the performance improvement of Theorem 5.2. Importantly, Theorem 5.3 shows the convergence to a stationary point of Ex„Q rhpfpxqqαs. If Q is a parametric space QΞ“tQξ PPpX q :ξPΞĎRdu, then we are guaranteed to stop when Ex„Qξ r∇ξ logqξpxqhpfpxqqαs“0, like for a general policy gradient method maximizing hpfpxqqα (Papini et al., 2018). Compared to the result for the unconstrained distribution space (Theorem 4.2), we loose the convergence to a fixed point. This property can be recovered under the assumption that the iterate in Equation (5) admits a unique solution for every P . In such a case, we will converge to a distribution Q8“argminQPQ tDαpIh˝f rQs}Qqu.
3In Appendix B, we discuss the effects of optimizing a power of f instead of f itself, i.e., when h“p¨qβ ; while in Appendix C, we discuss cases in which the performance improvement can be obtained for MDPs.

heading: 5.3 IMPLICIT TRUST REGION
text: In Theorem 4.3, we have proved that the α-Rényi divergence between Ih˝f rP s and P is bounded. In this section, we answer (Q3), wondering whether similar properties hold when we consider a limited set of distributions QĎPpX q. The following result shows that, under a particular form of convexity (van Erven & Harremoës, 2014) of Q, we are able to control the trust region as well. Theorem 5.4. Let f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictly-increasing. Let QĎPpX q be a p1´αq-convex set (van Erven & Harremoës, 2014, Definition 4), P PQ, Q: P argminQPQ tDαpIh˝f rP s}Qqu, and αPr0,8s, then it holds that:
Dα ` Q: › ›P ˘ ďDα pIh˝f rP s}P q´Dα ` Ih˝f rP s › ›Q: ˘ .
Therefore, we are always guaranteed that the trust region induced by Q: is tighter compared to the one induced by Q˚“Ih˝f rP s computed in Theorem 4.3, i.e., Dα ` Q: › ›P ˘ ďDα pIh˝f rP s}P q.

heading: 6 POLICY OPTIMIZATION VIA OPTIMAL POLICY EVALUATION
text: In this section, we build a sample-based Off-PL algorithm, named Policy Optimization via Optimal Policy Evaluation (PO2PE), which uses Off-VM as an inner loop. For generality, we consider a parametric distribution space QΞ“tQξ PPpX q :ξPΞĎRdu, a common setting met in PO.4
Algorithm 1: PO2PE. input : α divergence order, h function, f function, QΞ distribution space, ξ1 initial parameter, n batch size output: final parameter ξI`1 PΞ
1 for i“1, . . . , I do Optimization 2 ξi,1“ξi 3 for j“1, . . . ,J do Evaluation 4 Collect Di,j“tpxl,fpxlqqulPrns with Qξi,j 5 Using pDi,kqkPrjs, perform M steps of gradient descent on (Obj). 6 end 7 ξi`1“ξi,J`1 8 end The structure of PO2PE consists of two nested loops. The outer loop (Optimization) acts on the target distribution qξi . At the end of each outer iteration iP rIs, the target distribution qξi`1 is updated with the last behavioral distribution produced by the inner loop qξi,J`1 . Instead, the inner loop (Evaluation) takes the target distribution provided by the outer loop qξi and provides a new behavioral distribution. At each inner iteration j PrJs, it collects samples Di,j with the current behavioral distribution qξi,j and employs them, together with all the samples collected so far pDi,kqkPrjs, to compute the next behavioral distribution qξi,j`1 , with the goal of finding the behavioral distribution minimizing the absolute central α-moment of the IS estimator (Equation 4). As we shall see, the optimization is performed using samples and by resorting to a penalized objective.
Sample-based Optimization The problem of finding the next behavioral distribution parameter ξi,j`1 using the samples collected so far pDi,kqkPrjs is an off-policy learning problem. Let us define Φi,j“ 1j ř
kPrjs qξi,k as the mixture of the j behavioral distributions experienced so far in the inner loop. Instead of directly estimating Dα pIh˝f rQξis}Qξqq, we refer to the (non-central) α-moment, which is connected to the original objective through Proposition 5.1. Since we have samples coming from different behavioral distributions, we can use a multiple IS estimator Veach & Guibas (1995):
pdα pIh˝f rQξis}Qξ;Φi,jq“ 1
nj
ÿ
kPrjs
ÿ
lPrns
qξpxk,lq Φi,jpxk,lq loooomoooon
(aq
qξipxk,lqα qξpxk,lqα hpfpxk,lqqα loooooooooooomoooooooooooon
(b)
. (6)
The (a) factor accounts that we are using samples collected with the mixture Φi,j to estimate an expectation under qξ, whereas the (b) factor is the actual variable we want to compute the expectation of, i.e., the α-moment. It is simple to prove that the expectation of pdα is indeed the α-moment (Papini et al., 2019). To minimize Equation (6), we employ a variance correction to mitigate the effect of finite samples (Metelli et al., 2018), theoretically grounded in the following result.
4In the action-based PO ξ“θ are the policy parameters and Ξ“Θ, while in the parameter-based PO ξ“ρ are the hyperpolicy parameters and Ξ“P .
Theorem 6.1. Let QΞĎPpX q be a set of parametric distributions and let ξ,ξi PΞ. If }h˝f}8ď m, then, if samples are independent, for every δPr0,1s, with probability at least 1´δ it holds that:
Ex„ξ „ˆ qξipxq qξpxq hpfpxqq ˙α ď pdα pIh˝f rQξis}Qξ;Φi,jq`mα d 2log 1δ nj ż X qξipxq2α Φi,jpxqqξpxq2pα´1q dx loooooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooooon
(Obj)
.
Some remarks are in order. First, the integral within the square root is an upper bound to the variance of the α-moment estimator pdα pIh˝f rQξis}Qξ;Φi,jq. In particular, when ξ“ξi, we obtain the exponentiated Rényi divergence, as illustrated in (Metelli et al., 2020). When all involved distributions are Guassians, it is possible to provide a 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 (dependence on delta of the form logp1{δq ), instead of a polynomial concentration (dependence of the form 1{δ). This is 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 concentration inequalities (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 correction term. This is necessary for theoretical purposes, but, as we shall see in the Section 7, 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-PO2PE), we sample n trajectories tτlulPrns independently with the policy πθi,j and we build the dataset Di,j“tpτl,RpτlqqulPrns. Instead, in the parameter-based setting (PB-PO2PE), we sample independently n policy parameters tθlulPrns and for each of them we run policy πθl once to generate trajectory τl. The corresponding dataset is given by Di,j“tppθl, τlq,RpτlqqulPrns. For the AB case, the correction in Theorem 6.1 is estimated from samples, as done for the Rényi divergence in (Metelli et 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 a constrained setting and, thus, we are 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.

heading: 7 EXPERIMENTAL EVALUATION
text: In this section, we provide the experimental evaluation of PO2PE on continuous control tasks. We first compare the learning performance of PO2PE with POIS (Metelli et al., 2018) and TRPO (Schulman et al., 2015) on four benchmarks. Then, deepen two relevant aspects of PO2PE: 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 in Appendix E. Comparison with POIS and TRPO In Figure 2, we show the average return as a function of the number of collected episodes, with a batch size n“100, using α“2, h“ Id (identity function), and one inner iteration (J“1). In the Cartpole environment, we observe that the performance of
0 1 2 3 4 5 ×104
0
1000
2000
3000
4000
5000
Episodes
A v e ra
g e re tu
rn
n = 50
0 1 2 3 4 5 ×104
0
1000
2000
3000
4000
5000
Episodes
n = 11
AB-PO2PE (J = 1) AB-PO2PE (J = 2)
AB-PO2PE (J = 10) AB-POIS TRPO
Figure 3: Average return as a function of the number of episodes in the Cartpole environment for different algorithms, batch-size n and inner iterations J (10 runs ˘ 95% bootstrapped c.i.).
0 1 2 3 4 5 ×104
0
500
1000
1500
2000
2500
Episodes
A v e ra
g e re tu
rn
β = 1 β = 0.1
β = 0.5 β = 2 β = 4
Figure 4: Average return as a function of the number of episodes in the Inverted Double Pendulum for different choices of h“p¨qβ (5 runs˘ 95% bootstrapped c.i.).
AB-PO2PE is slightly above that of AB-POIS and PB-PO2PE; while the fastest learning curve is shown by PB-POIS. Instead, TRPO converges to a suboptimal policy that fails keeping the pole in the vertical position. In the Inverted Double Pendulum experiment, the gap between AB-PO2PE and AB-POIS and TRPO is more evident. The PB versions outperform the AB ones with PO2PE slightly faster than POIS. In the Mountain Car domain, while AB-POIS, TRPO, and PB-PO2PE display a similar convergence speed, AB-PO2PE and PB-POIS reach the optimal performance faster. Finally, in the Mujoco Swimmer domain (Todorov et al., 2012), AB-PO2PE and TRPO clearly outperform AB-POIS, although the fastest learning curves are displayed by the PB versions of POIS and PO2PE.
Robustness to Small Batch Sizes Based on the previous results, we further investigate the properties of PO2PE 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 as a function of the number of collected episodes for batch sizes nPt11,50u and different number of inner iterations J . Also considering the n“100 case (Figure 2), we notice, as expected, that the variance of each setting increases overall as n decreases. Nevertheless, PO2PE 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 PO2PE 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 iterations J 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“p¨qβ , i.e., a power function. In Figure 4, we show the learning curves of the Inverted Double Pendulum for different values of β. We notice that for β close to 1 (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 an interesting phenomenon, i.e., even if we optimize a power of return, within certain limits, we are still able to converge to a (near-)optimal policy.

heading: 8 DISCUSSION AND CONCLUSIONS
text: 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 α-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 evaluation confirmed our theoretical findings. PO2PE 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 a consequence of using the minimum-variance 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 new research opportunities. Future works include an extension of the convergence analysis to the sample-based setting and an experimentation of PO2PE coupled with more complex policy architectures.

heading: A PROOFS AND DERIVATIONS
text: In this appendix, we report the proofs and derivations, we have omitted in the main paper.

heading: A.1 PROOFS OF SECTION 4
text: Proposition 4.1 (Proposition 9 of Ghosh et al. (2020)). Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic increasing. Then, Ih˝f rP s is a performance improvement w.r.t. P :
Ex„Ih˝f rP srfpxqs´Ex„P rfpxqs“ Covx„P rhpfpxqq,fpxqs
Ex„P rhpfpxqqs ě0.
Proof. Let us consider the following derivation:
Ex„Ih˝f rP srfpxqs´Ex„P rfpxqs“ ż
X ppxqhpfpxqq Ex„P rhpfpxqqs fpxqdx´Ex„P rfpxqs
“ Ex„P rhpfpxqqfpxqs´Ex„P rfpxqsEx„P rhpfpxqqs Ex„P rhpfpxqqs
“ Covx„P rhpfpxqq,fpxqs Ex„P rhpfpxqqs ,
where we have exploited the definition of Ih˝f and the definition of covariance. The result is obtained 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) is non-negative (Cuadras, 2002).
Theorem 4.2. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Then, the following statements hold:
(i) P is a fixed point of Ih˝f , i.e., Ih˝f rP s“P a.s., if and only if Varx„P rfpxqs“0; (ii) let X ˚“argmaxxPsupppP qtfpxqu be the set of maxima of f restricted to the support of P .
If X ˚ is non-empty and measurable then, the repeated application of Ih˝f converges to a distribution Q8“ limkÑ8 pIh˝f qk rP s with support X ˚. In particular Ex„Q8rfpxqs“ maxxPsupppP qtfpxqu.
Proof. We start with (i). First of all, we observe that since h is monotonically strictly-increasing it holds that Varx„P rfpxqs“0 if and only if Varx„P rhpfpxqqs“0. P is a fixed point of Ih˝f , i.e., P “Ih˝f rP s a.s. if and only if for all xPX it holds a.s.:
ppxq“ ppxqhpfpxqq Ex„P rhpfpxqqs ,
that occurs if and only if either ppxq“0 (xRsupppP q) or hpfpxqq“Ex„P rhpfpxqqs. (ñ) Whenever ppxq is not zero, function hpfpxqq is a constant in supppP q and, consequently, its variance under P is zero. (ð) Suppose that Varx„P rhpfpxqqs“0, then hpfpxqq“Ex„P rhpfpxqqs almost surely and, consequently ppxqhpfpxqqEx„P rhpfpxqqs“ppxq almost surely. Let us now consider (ii). First of all, we can easily observe that for every kPN:
pIh˝f qk rP spxq“ ppxqfpxqk
Ex„P rfpxqks .
Let f˚“maxxPsupppP qtfpxqu, consider the function gkpxq“ppxq ´ fpxq f˚
¯k
and the limit:
lim kÑ8 gkpxq“ lim kÑ8
ppxq ˆ fpxq f˚
˙k
“ " ppxq if xPX ˚ 0 otherwise .
Thus, we have:
Q8“ lim kÑ8 pIh˝f qk rP spxq“ lim kÑ8
ppxqfpxqk ş
X ppxqfpxqkdx
“ lim kÑ8
gkpxq ş X gkpxqdx “ # ppxq ş X˚ ppxqdx if xPX ˚ 0 otherwise .
Thus, the support of Q8 is given by X ˚. Consequently, the expectation of f under Q8 is given by:
Ex„Q8rfpxqs“ ż
X q8pxqfpxqdx“f˚.
Theorem 4.3. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Then, for every αPr0,8s, it holds that:
Dα pIh˝f rP s}P q“ 1 α´1 log Ex„P rhpfpxqqαs Ex„P rhpfpxqqsα .
In particular, for α“1 it holds that:
DKLpIh˝f rP s}P q“ Covx„P rhpfpxqq, loghpfpxqqs
Ex„P rhpfpxqqs .
Proof. Let us consider the following derivation:
J :“ ż
X ppIh˝f rP sqpxqqα ppxq1´αdx“
ż
X
ˆ
ppxqhpfpxqq Ex„P rhpfpxqqs
˙α
ppxq1´αdx
“ Ex„P rhpfpxqq αs
Ex„P rhpfpxqqsα .
By observing that Dα pIh˝f rP s}P q“ 1α´1 logJ , we obtain the result. For α“1, we provide an independent derivation:
DKLpIh˝f rP s}P q“ ż
X ppxqhpfpxqq Ex„P rhpfpxqqs log ppxqhpfpxqq Ex„P rhpfpxqqsppxq dx
“ Ex„P rhpfpxqq loghpfpxqqs´Ex„P rhpfpxqqsEx„P rloghpfpxqqs Ex„P rhpfpxqqs
“ Covx„P rhpfpxqq, loghpfpxqqs Ex„P rhpfpxqqs ,
where we exploited the definition of covariance in the last line.

heading: A.2 PROOFS OF SECTION 5
text: Proposition 5.1. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Then, for any αPp1,8q, it holds that:
Ex„Q „ ˇ ˇ ˇ
ˇ ppxq qpxqhpfpxqq´Ex„P rhpfpxqqs
ˇ ˇ ˇ ˇ
α
loooooooooooooooooooooooooomoooooooooooooooooooooooooon
absolute central α-moment
ďEx„Q „ˆ ppxq qpxqhpfpxqq
˙α
looooooooooooooomooooooooooooooon
(non-central) α-moment
“epα´1qDαpIh˝f rP s}QqEx„P rhpfpxqqsα.
Proof. First of all, we observe that since Ex„Q ” ppxq qpxqhpfpxqq ı
“Ex„P rhpfpxqqs, for αě1, the absolute central α-moment is smaller or equal than the (non-central) α-moment. Thus, for αě1,
we have:
Ex„Q „ ˇ ˇ ˇ
ˇ ppxq qpxqhpfpxqq´Ex„P rhpfpxqqs
ˇ
ˇ
ˇ
ˇ
α
ďEx„Q „ˆ ppxq qpxqhpfpxqq
˙α
“ ż
X
ˆ
ppxqhpfpxqq Ex„P rhpfpxqqs
˙α
qpxq1´αdxEx„P rhpfpxqqsα
“ ż
X ppIh˝f rP sqpxqqα qpxq1´αdxEx„P rhpfpxqqsα
“exp " pα´1q 1 α´1 log ż X ppIh˝f rP sqpxqqα qpxq1´αdx * Ex„P rhpfpxqqsα.
By applying the definition of Rényi divergences, we get the result.
Theorem 5.2. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Let QĎPpX q, QPQ, and αPr0,8s, then, it holds that:
Ex„Q rhpfpxqqαs´Ex„P rhpfpxqqαsě Ex„P rhpfpxqqsα
α´1
´ epα´1qDαpIh˝f rP s}P q´epα´1qDαpIh˝f rP s}Qq ¯ .
In particular, for α“1, it holds that (Ghosh et al., 2020, Proposition 6): Ex„Q rhpfpxqqs´Ex„P rhpfpxqqsěEx„P rhpfpxqqspDKLpIh˝f rP s}P q´DKLpIh˝f rP s}Qqq .
Proof. Let us consider the following derivation:
Ex„Qrhpfpxqqαs“ ż
X qpxqhpfpxqqαdx
“ ż X ppxqqpxq ppxqhpfpxqq αdx “ ż
X ppxqhpfpxqqαdx`
ż
X ppxq
ˆ
qpxq ppxq ´1
˙
hpfpxqqαdx
ě ż X ppxqhpfpxqqαdx` 1 α´1 ż X ppxq
˜
1´ ˆ ppxq qpxq
˙α´1 ¸
hpfpxqqαdx (7)
“Ex„P rhpfpxqqαs` 1
α´1
ż
X ppxqhpfpxqqαdx
´ 1 α´1
ż
X ppxq
ˆ
ppxq qpxq ˙α´1 hpfpxqqαdx
“Ex„P rhpfpxqqαs`Ex„P rhpfpxqqsα 1
α´1
ż
X
ˆ
ppxqhpfpxqq Ex„P rhpfpxqqs
˙α
ppxq1´αdx
´Ex„P rhpfpxqqsα 1
α´1
ż
X
ˆ
ppxqhpfpxqq Ex„P rhpfpxqqs
˙α
qpxq1´αdx
“Ex„P rhpfpxqqαs
`Ex„P rhpfpxqqsα 1 α´1 exp " pα´1q 1 α´1 log ż
X
ˆ
ppxqhpfpxqq Ex„P rhpfpxqqs
˙α
ppxq1´αdx *
´Ex„P rhpfpxqqsα 1 α´1 exp " pα´1q 1 α´1 log ż
X
ˆ
ppxqhpfpxqq Ex„P rhpfpxqqs
˙α
qpxq1´αdx *
“Ex„P rhpfpxqqαs` Ex„P rhpfpxqqsα
α´1
´ epα´1qDαpIh˝f }P q´epα´1qDαpIh˝f }Qq ¯ ,
where line (7) derived from Lemma A.1. The second inequality was provided in Proposition 6 of (Ghosh et al., 2020).
Theorem 5.3. Let P PPpX q, f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictlyincreasing. Let QĎPpX q and suppose that h˝f is bounded from above, then, the iterate Qk`1 PargminQPQ tDαpIh˝f rQks}Qqu (where possible ties are broken arbitrarily) satisfies:
(i) the sequence of divergences DαpIh˝f rQks}Qkq is convergent; (ii) the sequence of expectations Ex„Qk rhpfpxqqαs is non-decreasing in kPN and converges to
a stationary point of Ex„Q rhpfpxqqαs w.r.t. QPQ.
Proof. Let us consider the sequence of distributions pQkqkPN , generated by the iterate in Equation (5), where possible ties are broken with an arbitrary (possibly with a tie-breaking rule Tk different for every k). From Theorem 5.2, we have for every kPN: Ex„Qk`1 rhpfpxqqαs´Ex„Qk rhpfpxqqαs
ě Ex„Qk rhpfpxqqs α
α´1
´ epα´1qDαpIh˝f rQks}Qkq´epα´1qDαpIh˝f rQks}Qk`1q ¯ ě0,
where we simply exploited that Qk PargminQPQ tDαpIh˝f rQks}Qqu. Thus, Ex„Qk rhpfpxqqαs is a non-decreasing function of k. Since h˝f is bounded, it must be that limkÑ8Ex„Qk rhpfpxqqαs“ µ8ă8, that proves convergence.5
Furthermore, being convergent, for kÑ8 it must be that Ex„Qk rhpfpxqqαs“Ex„Qk`1 rhpfpxqqαs and consequently DαpIh˝f rQks}Qkq“DαpIh˝f rQks}Qk`1q. Therefore, even if the tie-braking rule prescribes to select Qk`1‰Qk we could select Qk instead, since it lead to the same divergence value. Consequently, being Qk a solution, we can assert that it is a stationary point of the function DαpIh˝f rQks}¨q (as well as Qk`1):
0“∇qp¨qDαpIh˝f rQks}Qq|Q“Qk
“ 1 pα´1qepα´1qDαpIh˝f rQks}QqEx„Qk rhpfpxqqs ∇qp¨q ż X hpfpxqqαqkpxqαqpxq1´αdx|Q“Qk
“´ 1 epα´1qDαpIh˝f rQks}QqEx„Qk rhpfpxqqs
ż
X hpfpxqqαqkpxqαqpxq´αdx|Q“Qk
“´ 1 epα´1qDαpIh˝f rQks}QqEx„Qk rhpfpxqqs
ż
X hpfpxqqαdx.
We observe that the latter expression is zero if and only if the gradient of Ex„Qrhpfpxqqαs w.r.t. Q is zero. Indeed:
∇qp¨qEx„Qrhpfpxqqαs“ ż
X hpfpxqqαdx.
Thus, the process converges to a stationary point of Ex„Qk rhpfpxqqαs.
Theorem 5.4. Let f PBpX , r0,8qq, and h : r0,8qÑr0,8q monotonic strictly-increasing. Let QĎPpX q be a p1´αq-convex set (van Erven & Harremoës, 2014, Definition 4), P PQ, Q: P argminQPQ tDαpIh˝f rP s}Qqu, and αPr0,8s, then it holds that:
Dα ` Q: › ›P ˘ ďDα pIh˝f rP s}P q´Dα ` Ih˝f rP s › ›Q: ˘ .
Proof. The proof is a simple application of Lemma A.2, by taking QÐP , Q˚ÐQ:, and PÐ Ih˝f rP s.

heading: A.3 PROOFS OF SECTION 6
text: Theorem 6.1. Let QΞĎPpX q be a set of parametric distributions and let ξ,ξi PΞ. If }h˝f}8ď m, then, if samples are independent, for every δPr0,1s, with probability at least 1´δ it holds that:
Ex„ξ „ˆ qξipxq qξpxq hpfpxqq ˙α ď pdα pIh˝f rQξis}Qξ;Φi,jq`mα d 2log 1δ nj ż X qξipxq2α Φi,jpxqqξpxq2pα´1q dx loooooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooooon
(Obj)
.
5Notice that the improvement holds also for αă1. Indeed, while it is true that Ex„Qk rhpfpxqqs α
α´1 ă0, but in such a case function epα´1qp¨q is decreasing in its argument.
Proof. We start observing that each addendum of pdα pIh˝f rQξis}Qξ;Φi,jq is non negative. Since all terms are i.i.d., we can apply unilateral Bernstein’s inequality (Maurer et al., 2003) that allows achieving an exponential concentration. Thus, for every δPr0,1s, with probability at least 1´δ it holds that:
Ex„ξ „ˆ qξipxq qξpxq hpfpxqq ˙α ď pdα pIh˝f rQξis}Qξ;Φi,jq
` c
2Varxi„Φi,j
” pdα pIh˝f rQξis}Qξ;Φi,jq ı log 1
δ .
Thus, it remains to provide a bound on the variance term. We exploit the fact that hpfpxqqďm and that each addendum represents an i.i.d. random variable:
Varxi„Φi,j
” pdα pIh˝f rQξis}Qξ;Φi,jq ı ď
1
pnjq2 ÿ
kPrjs
ÿ
lPrns Exk,l„Φi,j
«
ˆ
qξipxk,lqα
Φi,jpxk,lqqξpxk,lqα´1 hpfpxqqα
˙2 ff
ď m 2α
pnjq2 ÿ
kPrjs
ÿ
lPrns Exk,l„Φi,j
«
ˆ
qξipxk,lqα
Φi,jpxk,lqqξpxk,lqα´1
˙2 ff
“m 2α
nj Ex„Φi,j
«
ˆ
qξipxqα
Φi,jpxqqξpxqα´1
˙2 ff
.

heading: A.4 TECHNICAL LEMMAS
text: Lemma A.1. For every xě0 and αPp0,1qYp1,8q, it holds that:
x´1ě 1 α´1
ˆ
1´ 1 xα´1
˙
.
Furthermore, for α“1, it holds that: x´1ě logx.
Proof. Consider the auxiliary function gαpxq“x´1´ 1α´1 ` 1´ 1xα´1 ˘
. We are going to prove that the minimum of gαpxq is zero. Suppose αą1, then gαp0q“8 and gap8q“8. Thus, the minimum must lie in between and since function gα is differentiable, we have:
B Bxgαpxq“1´x ´α“0 ùñ x“1.
Thus, we have gαp1q“0. Suppose now that αă1, we have gαp0q“ α1´αą0 and gαp8q“8. Thus, again, the minimum must lie in between and with the same calculations as before, we conclude gαp1q“0. The case α“1 is trivial.
Lemma A.2. Let P PPpX q and let αPp0,8q. Let QĎPpX q be an pα´1q-convex (van Erven & Harremoës, 2014, Definition 4) subset of distributions. Let Q˚ PQ be the α-moment projection:
Q˚“argmin QPQ tDαpP }Qqu .
If Q˚ exists, then for every QPQ if holds that: DαpP }QqěDαpP }Q˚q`DαpQ˚}Qq.
Proof. The proof of the result is inspired to (van Erven & Harremoës, 2014, Theorem 14). Let λPr0,1s and let us define Qλ as the p1´α,p1´λ,λqq-mixture of Q˚ and Q:
qλpxq“Z´1λ ` p1´λqq˚pxq1´α`λqpxq1´α ˘
1 1´α ,
Zλ“ ż
X
` p1´λqq˚pxq1´α`λqpxq1´α ˘ 1 1´α dx.
Let us first observe that for λ“0, we have Q0“Q˚ and Z0“ ş X q ˚pxqdx“1. Since Q is p1´ αq-convex and Q˚ is the minimizer over Q, it holds that BBλDαpP }Qλq|λ“0ě0. First of all, we compute:
ż
X ppxqαqλpxq1´αdx“Zα´1λ
ż
X
“ p1´λqppxqαq˚pxq1´α`λppxqαqpxq1´α ‰ dx
B BλZλ“ 1 1´α
ż
X
` p1´λqq˚pxq1´α`λqpxq1´α ˘
α 1´α `
qpxq1´α´q˚pxq1´α ˘ dx.
The latter, for λ“0, becomes: BBλZλ ∣∣∣ λ“0 “ 11´α “ş X q ˚pxqαqpxq1´α´1 ‰ . For calculation easiness, instead of directly operating on DαpP }Qλq, we consider: B Bλ ż X ppxqαqλpxq1´αdx“Zα´1λ ż X “ ´ppxqαq˚pxq1´α`ppxqαqpxq1´α ‰ dx,
`pα´1qZα´2λ B BλZλ
ż
X
“ p1´λqppxqαq˚pxq1´α`λppxqαqpxq1´α ‰ dx.
We now evaluate it at λ“0: B Bλ ż X ppxqαqλpxq1´αdx ∣∣∣ λ“0 “´ ż X ppxqαq˚pxq1´αdx` ż X ppxqαqpxq1´αdx
´ ż
X ppxqαq˚pxq1´αdx
„ ż
X q˚pxqαqpxq1´αdx´1

.
For αě1, we require BBλ ş X ppxq αqλpxq1´αdx ∣∣∣ λ“0
ě0, to obtain: ż
X ppxqαqpxq1´αdxě
ż
X ppxqαq˚pxq1´αdx
ż
X q˚pxqαqpxq1´αdx.
By applying both sides the log function and dividing by 1α´1ą0 we get the result. Symmetrically, for αă1, we require the converse BBλ ş X ppxq αqλpxq1´αdx ∣∣∣ λ“0
ď0. Recalling that 1α´1ă0, we obtain the desired result.
B OPTIMIZING MOMENTS OF f
In this appendix, we analyze the effect of optimizing a power of f instead of f .
Lemma B.1. Let P PPpX q and f PBpX , rm,ms. If αPp1,8q, it holds that: 0ďEx„P rfpxqαs´pEx„P rfpxqsqα
ďm αpm´Ex„P rfpxqsq`mαpEx„P rfpxqs´mq´Ex„P rfpxqsα pm´mq
m´m .
In particular for α“2, we have:
0ďEx„P “ fpxq2 ‰ ´pEx„P rfpxqsq2ďpm´Ex„P rfpxqsqpEx„P rfpxqs´mq , that is the Bhatia-Davis inequality for the variance.
Proof. We explicitly consider the optimization problem, for αě1 and having denoted µ“ Ex„P rfpxqs:
max f :XÑR
ż
X ppxqfpxqαdx
s.t. ż
X ppxqfpxq“µ
mďfpxqďm. Since αě1, the optimization problem corresponds to the maximization of a concave function subject to linear and box constraints. It is simple to prove that the optimal solution must assign extreme values to function f . Let pPr0,1s, the linear and box constraints enforce:
pm`p1´pqm“µ ùñ p“ m´µ m´m.
From which, by substitution in the objective function, we have: ż
X ppxqfpxqαdx“pmα`p1´pqmα“m αpm´µq`mαpµ´mq m´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 Ex„P rfpxqs approaches the extreme value m (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 4).

heading: C PERFORMANCE IMPROVEMENT FOR THE MDP SETTING
text: As already mentioned in Section 5, when we consider the MDP setting, we do not have the full control of the trajectory distribution ppτ |θq“D0ps0q śH´1 t“0 πθpat|stqP pst`1|st,atq as the factors involving the transition model P and the initial state distribution D0 are out of the control of the policy and the policy itself πθ is limited due to the parametrization. As a consequence, performing a step of optimization of the α-moment is able to provide improvement guarantees on Jpθq only by choosing the transformation function h“p¨q 1α (Theorem 5.2). In this appendix, we prove that under specific conditions we are able to provide guarantees on the improvement of Jpθq. Moreover, we show some approaches, with a main theoretical interest, to extend the performance improvement 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.

heading: C.1 ACTION-BASED PO
text: We start with the action-based PO setting.
Deterministic MDPs If the MDP is deterministic (i.e., P and D0 are deterministic), we denote the next state as st`1“P pst,atq. Thus, the trajectory distribution is governed by the policy πθ only: ppτ |θq“
śH´1 t“0 πθpat|stq. In such a case, provided that the policy space Θ is sufficiently powerful,
by minimizing any of the α-moments, we are able to guarantee the performance improvement. Indeed, in such a case, neglecting the limits of the parametrization Θ, we are in an unconstrained setting.
Stochastic MDPs For general stochastic MDPs, the trajectory density function depends on the transition model probabilities. Thus, we need to design an estimator that get rids of these elements. To this purpose, we denote with ppa|θq as the probability of having observed a sequence of actions a“pa0,a1, . . . ,aH´1q when playing policy πθ in the MDP. If we take f“E rRpτq|as, i.e., the expectation of the return conditioned to the sequence of actions, we are again in an unconstrained
setting, neglecting the limits of Θ. Therefore, we are able to guarantee the performance improvement on Jpθq. Nevertheless, this requires to design an estimator of E rRpτq|as, that might be a not easy task.

heading: C.2 PARAMETER-BASED PO
text: We now consider the parameter-based PO setting.
Deterministic MDPs and Policies In the case of deterministic MDPs and deterministic policy πθ, we have that for every θPΘ, the support of the trajectory distribution is made of one trajectory only. In such a case, ignoring the limits of the hyperpolicy parameter space P , we are in an unconstrained setting.
Stochastic MDPs or Policies In the case of a stochastic MDP or a stochastic policy (or both), we have a trajectory distribution in which we do not have the possibility to intervene on the policy and transition model factors. Thus, we need to consider an estimators that get rid of these stochastic elements. If we take f“ErR|θs“Jpθq, i.e., the expected return conditioned to a policy parametrization θ, we reduce to the unconstrained setting, with the corresponding performance improvement guarantee. It is worth noting that, compared to the action-based setting, estimating Jpθq is notably simpler compared to the estimation of E rRpτq|as.

heading: D CLOSED FORM OF THE INTEGRAL FOR GAUSSIANS
text: In this appendix, we derive a closed form for the integral involved in the computation of the bound of Theorem 6.1 in the case that all involved distributions are Gaussians and for α“2. Let us introduce the notation:
µ“N pµµ,Σµq, φ“N pµφ,Σφq, ν“N pµν ,Σνq. (8) We have to compute the following integral:
ż
X
µ4pxq φpxqνpxq2 dx.
Let us start elaborating on the integrand function, denoting for properly sized vector x and matrix S, }m}S“xTSx and |S| the determinant of S:
µ4pxq φpxqνpxq2 “
p2πq´2k|Σµ|´2 exp ´ ´2}x´µµ}2Σµ´1 ¯
p2πq´k{2|Σφ|´1{2 exp ´ ´1{2}x´µφ}2Σφ´1 ¯ p2πq´k|Σν |´1 exp ´ ´}x´µν}2Σν´1 ¯
“ p2πq ´k{2|Σµ|´2
|Σφ|´1{2|Σν |´1 exp
´
´2}x´µµ}2Σµ´1`1{2}x´µφ} 2 Σφ´1 `}x´µν}2Σν´1 ¯ .
Now, we have to deal with the argument of the exponential:
´2}x´µµ}2Σµ´1`1{2}x´µφ} 2 Σφ´1 `}x´µν}2Σν´1
“´1 2 xT ` 4Σµ ´1´Σφ´1´2Σν´1 ˘ loooooooooooooooomoooooooooooooooon
M
x` ` 4Σµ ´1µµ´Σφ´1µφ´2Σν´1µν ˘T
loooooooooooooooooooooooomoooooooooooooooooooooooon
bT
x
´ 1 2 ` 4µµ TΣµ ´1µµ´µφTΣφ´1µφ´2µνTΣν´1µν ˘ loooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooon
c
.
We now proceed completing the square:
xTMx´2bTx“px´M´1bqTMpx´M´1bq´bTM´1b. Thus, we have:
´1 2 ´ xTMx´2bTx`c ¯ “´1 2 px´M´1bqTMpx´M´1bq` 1 2 bTM´1b´ 1 2 c.
Moreover, we observe that the following expression is the density of a k-variate normal distribution with mean M´1b and covariance matrix M´1:
p2πq´k{2|M´1|´1{2 exp ˆ ´1 2 px´M´1xqTMpx´M´1bq ˙ .
Thus, its integral is 1. Therefore, coming to the initial expression: ż
X
µ4pxq φpxqνpxq2 dx“ p2πq´k{2|Σµ|´2 |Σφ|´1{2|Σν |´1 ´ p2πq´k{2|M´1|´1{2 ¯´1 exp ˆ 1 2 bTM´1b´ 1 2 c ˙
“ |Σφ| 1{2|Σν |
|Σµ|2|M|1{2 exp
ˆ
1
2
´ bTM´1b´c ¯
˙

heading: E EXPERIMENTAL DETAILS
text: In this appendix, we report the experimental details and additional experimental results.
Infrastructure The experiments have been run on two machines:
• 2 x CPUs Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz (22 cores, 44 thread, 55 MB cache) and 128 GB RAM;
• 4 x Intel(R) Xeon(R) CPU E5-4610 v2 @ 2.30GHz (8 cores, 16 thread, 16 MB cache) and 256 GB RAM.
Environments The environments are the rllab implementations (Duan et al., 2016), MIT license, https://github.com/rll/rllab. The Swimmer environment belongs to the Mujoco suite (Todorov et al., 2012), MuJoCo Personal License, http://www.mujoco.org/.
Algorithms The TRPO implementation is taken from baselines (Dhariwal et al., 2017), MIT licence, https://github.com/openai/baselines. For POIS we use the original implementation (Metelli et al., 2018), MIT license, https://github.com/T3p/baselines.
Hyperparameters In order to properly compare the algorithms, a 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 to the other 15 seeds. In the following, we report the hyperparameter values for PO2PE.
The shift return refers to the need for making the return non-negative in order to perform the optimization of the α-moment in PO2PE. This procedure is carried out independently at each algorithm iteration by subtracting the minimum return among the ones observed. The variance init hyperparameter 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, 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: 1 • inner: 1 • variance init: -1 • step size: 1 / gradient norm • penalization: True • delta: 0.75
• 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
• max iters: 500
• policy: linear
• policy init: zeros
• capacity: 1
• inner: 1
• 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: 1
• inner: 1
• 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: 1
• inner: 1
• log-std init: -0.6
• step size: 1 / gradient norm
• penalization: True
• delta: 0.99
• max offline iters: 10
• shift return: True
For POIS (both AB and PB) and TRPO, the same hyperparameter value have been used, except for the algorithm-specific ones that have been tuned with the same protocol discussed above (δKL P t0.001,0.01,0.1,1u). 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 algorithm-specific hyperparameter values for the different algorithms and environments.
Environment / Algorithm PO2PE (delta) AB-POIS (delta) TRPO (max kl)
Cartpole 0.75 0.4 0.01 Mountain Car 0.9 0.9 0.01 Inverted Double Pendulum 0.99 0.1 0.001 Swimmer 0.99 0.8 0.01
Environment / Algorithm PB-POIS (delta) PB-PO2PE (delta)
Cartpole 0.4 0.6 Mountain Car 1 0.00001 Inverted Double Pendulum 0.1 0.999999 Swimmer 0.4 0.4

heading: E.1 NOISE ROBUSTNESS
text: As we have shown in Appendix C, using the trajectory return Rpτq as function f does no longer allow to provide performance improvement guarantees. Nevertheless, we conjecture that the loss of this property is compensated by the variance reduction implicit in our approach. In the direction of empirically showing this aspect, we tested the parameter-based version of PO2PE in the Inverted 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 σ. The results are shown in Figure 5. We observe that our algorithm is overall competitive with PB-POIS and, in the case of σ“1, significantly outperforms PB-POIS.

heading: E.2 ABOUT RETURN TRANSLATION
text: Our approach can be employed for non-negative functions f . Since in the PO experimental evaluation we employ f“Rpτq. Under the assumption that the immediate reward is bounded Rps,aqPrRmin,Rmaxs for all ps,aqPSˆA, we can make the return function with a simple translation and preserving the optimality of policies:
Rpτq“Rpτq´Rmin 1´γH
1´γ loooooomoooooon
´cmin
,
where Rmin 1´γ H
1´γ is the minimum achievable return. Of course, we can perform the translation
even by using a constant cěcmin“´Rmin 1´γ H
1´γ and still obtain a translated return that remains positive. It is worth noting, from Theorem 4.3 that the size of the trust region is larger as the constant approaches the its minimum possible value.
For instance, we consider α“2, fě0 , and we apply a further translation with cě0. From Theorem 4.3, we have:
D2pI`c˝f rP s}P q“ log Ex„P rpfpxq`cq2s Ex„P rfpxq`cs2 “ log Ex„P rfpxq 2s`c2`2cEx„P rfpxqs Ex„P rfpxqs2`c2`2cEx„P rfpxqs .
Since Ex„P rfpxq2sěEx„P rfpxqs2, we have that this expression is maximized with the smallest value of c, i.e., c“0.

Review summaries:
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.

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. 

Importance sampling (IS) is at the core of many off-policy reinforcement learning (RL) algorithms.  The 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  $$ \max_p \mathbb{E}_{x\sim q}\left[\frac{p(x)}{q(x)}f(x)\right]. $$  This approach suffers from high variance.   This 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_.  The paper is structured as follow:  1. 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. The 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?  2. 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$.  3. 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.   4. 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.  The 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).  5. The authors analyze the policy improvement of this "approximated" operator. They notice that the policy improvement happens only for some particular choice of $h$    6. 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}$.  7. 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).   To summarize, the paper proposes a different use of IS, which allows both for variance reduction and policy improvement.  The improvement scheme is new (although it can be related to other approaches) and sheds new light on policy gradient optimization.      

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.