Matteo Papini
email: teo.papini@polimi.it>.

Damiano Binaghi

Giuseppe Canonaco

Matteo Pirotta

Marcello Restelli

Stochastic Variance-Reduced Policy Gradient

In this paper, we propose a novel reinforcementlearning algorithm consisting in a stochastic variance-reduced version of policy gradient for solving Markov Decision Processes (MDPs). Stochastic variance-reduced gradient (SVRG) methods have proven to be very successful in supervised learning. However, their adaptation to policy gradient is not straightforward and needs to account for I) a non-concave objective function; II) approximations in the full gradient computation; and III) a non-stationary sampling process. The result is SVRPG, a stochastic variancereduced policy gradient algorithm that leverages on importance weights to preserve the unbiasedness of the gradient estimate. Under standard assumptions on the MDP, we provide convergence guarantees for SVRPG with a convergence rate that is linear under increasing batch sizes. Finally, we suggest practical variants of SVRPG, and we empirically evaluate them on continuous MDPs.

Introduction

On a very general level, artificial intelligence addresses the problem of an agent that must select the right actions to solve a task. The approach of Reinforcement Learning (RL) [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] is to learn the best actions by direct interaction with the environment and evaluation of the performance in the form of a reward signal. This makes RL fundamentally different from Supervised Learning (SL), where correct actions are explicitly prescribed by a human teacher (e.g., for classification, in the form of class labels). However, the two approaches share many challenges and tools. The problem of estimating a model from samples, which is at the core of SL, is equally fundamental in RL, whether we choose to model the environment, Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s). a value function, or directly a policy defining the agent's behaviour. Furthermore, when the tasks are characterized by large or continuous state-action spaces, RL needs the powerful function approximators (e.g., neural networks) that are the main subject of study of SL. In a typical SL setting, a performance function J(θ) has to be optimized w.r.t. to model parameters θ. The set of data that are available for training is often a subset of all the cases of interest, which may even be infinite, leading to optimization of finite sums that approximate the expected performance over an unknown data distribution. When generalization to the complete dataset is not taken into consideration, we talk about Empirical Risk Minimization (ERM). Even in this case, stochastic optimization is often used for reasons of efficiency. The idea of stochastic gradient (SG) ascent [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]) is to iteratively focus on a random subset of the available data to obtain an approximate improvement direction. At the level of the single iteration, this can be much less expensive than taking into account all the data. However, the sub-sampling of data is a source of variance that can potentially compromise convergence, so that periteration efficiency and convergence rate must be traded off with proper handling of meta-parameters. Variance-reduced gradient algorithms such as SAG [START_REF] Roux | A stochastic gradient method with an exponential convergence rate for finite training sets[END_REF], SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF] and SAGA (Defazio et al., 2014a) offer better ways of solving this trade-off, with significant results both in theory and practice. Although designed explicitly for ERM, these algorithms address a problem that affects more general machine learning problems.

In RL, stochastic optimization is rarely a matter of choice, since data must be actively sampled by interacting with an initially unknown environment. In this scenario, limiting the variance of the estimates is a necessity that cannot be avoided, which makes variance-reduced algorithms very interesting. Among RL approaches, policy gradient [START_REF] Sutton | Policy gradient methods for reinforcement learning with function approximation[END_REF] is the one that bears the closest similarity to SL solutions. The fundamental principle of these methods is to optimize a parametric policy through stochastic gradient ascent. Compared to other applications of SG, the cost of collecting samples can be very high since it requires to interact with the environment. This makes SVRG-like methods potentially much more efficient than, e.g., batch learning. Unfortunately, RL has a series of difficulties that are not present in ERM. First, in SL the objective can often be de-signed to be strongly concave (we aim to maximize). This is not the case for RL, so we have to deal with non-concave objective functions. Then, as mentioned before, the dataset is not initially available and may even be infinite, which makes approximations unavoidable. This rules out SAG and SAGA because of their storage requirements, which leaves SVRG as the most promising choice. Finally, the distribution used to sample data is not under direct control of the algorithm designer, but it is a function of policy parameters that change over time as the policy is optimized, which is a form of non-stationarity. SVRG has been used in RL as an efficient technique for optimizing the per-iteration problem in Trust-Region Policy Optimization [START_REF] Xu | Stochastic variance reduction for policy gradient estimation[END_REF] or for policy evaluation [START_REF] Du | Stochastic variance reduction methods for policy evaluation[END_REF]. In both the cases, the optimization problems faced resemble the SL scenario and are not affected by all the previously mentioned issues.

After providing background on policy gradient and SVRG in Section 2, we propose SVRPG, a variant of SVRG for the policy gradient framework, addressing all the difficulties mentioned above (see Section 3). In Section 4 we provide convergence guarantees for our algorithm, and we show a convergence rate that has an O(1 /T ) dependence on the number T of iterations. In Section 5.2 we suggest how to set the meta-parameters of SVRPG, while in Section 5.3 we discuss some practical variants of the algorithm. Finally, in Section 7 we empirically evaluate the performance of our method on popular continuous RL tasks.

Preliminaries

In this section, we provide the essential background on policy gradient methods and stochastic variance-reduced gradient methods for finite-sum optimization.

Policy Gradient

A Reinforcement Learning task [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]) can be modelled with a discrete-time continuous Markov Decision Process (MDP) M = {S, A, P, R, γ, ρ}, where S is a continuous state space; A is a continuous action space; P is a Markovian transition model, where P(s |s, a) defines the transition density from state s to s under action a; R is the reward function, where R(s, a) ∈ [-R, R] is the expected reward for state-action pair (s, a); γ ∈ [0, 1) is the discount factor; and ρ is the initial state distribution. The agent's behaviour is modelled as a policy π, where π(•|s) is the density distribution over A in state s. We consider episodic MDPs with effective horizon H. 1 In this setting, we can limit our attention to trajectories of length H. A trajectory τ is a sequence of states and actions (s 0 , a 0 , s 1 , a 1 , . . . , s H-1 , a H-1 ) observed by follow-ing a stationary policy, where s 0 ∼ ρ. We denote with p(τ |π) the density distribution induced by policy π on the set T of all possible trajectories (see Appendix A for the definition), and with R(τ ) the total discounted reward provided by trajectory τ : R(τ ) = H-1 t=0 γ t R(s t , a t ). Policies can be ranked based on their expected total reward:

J(π) = E τ ∼p(•|π) [R(τ )|M ]. Solving an MDP M means finding π * ∈ arg max π {J(π)}.
Policy gradient methods restrict the search for the best performing policy over a class of parametrized policies Π θ = {π θ : θ ∈ R d }, with the only constraint that π θ is differentiable w.r.t. θ. For sake of brevity, we will denote the performance of a parametric policy with J(θ) and the probability of a trajectory τ with p(τ |θ) (in some occasions, p(τ |θ) will be replaced by p θ (τ ) for the sake of readability). The search for a locally optimal policy is performed through gradient ascent, where the policy gradient is [START_REF] Sutton | Policy gradient methods for reinforcement learning with function approximation[END_REF]Peters & Schaal, 2008a):

∇J(θ) = E τ ∼p(•|θ) [∇ log p θ (τ )R(τ )] .
(1)

Notice that the distribution defining the gradient is induced by the current policy. This aspect introduces a nonstationarity in the sampling process. Since the underlying distribution changes over time, it is necessary to resample at each update or use weighting techniques such as importance sampling. Here, we consider the online learning scenario, where trajectories are sampled by interacting with the environment at each policy change. In this setting, stochastic gradient ascent is typically employed. At each iteration k > 0, a batch D k N = {τ i } N i=0 of N > 0 trajectories is collected using policy π θ k . The policy is then updated as θ k+1 = θ k + α ∇ N J(θ k ), where α is a step size and ∇ N J(θ) is an estimate of Eq. (1) using D k N . The most common policy gradient estimators (e.g., REINFORCE [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF] and G(PO)MDP [START_REF] Baxter | Infinite-horizon policy-gradient estimation[END_REF]) can be expressed as follows

∇ N J(θ) = 1 N N n=1 g(τ i |θ), τ i ∈ D k N , (2)
where

g(τ i |θ) is an estimate of ∇ log p θ (τ i )R(τ i ).
Although the REINFORCE definition is simpler than the G(PO)MDP one, the latter is usually preferred due to its lower variance. We refer the reader to Appendix A for details and a formal definition of g.

The main limitation of plain policy gradient is the high variance of these estimators. The naïve approach of increasing the batch size is not an option in RL due to the high cost of collecting samples, i.e., by interacting with the environment. For this reason, literature has focused on the introduction of baselines (i.e., functions b : S × A → R) aiming to reduce the variance (e.g., [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF]Peters & Schaal, 2008a;[START_REF] Thomas | Policy gradient methods for reinforcement learning with function approximation and action-dependent baselines[END_REF][START_REF] Wu | Variance reduction for policy gradient with action-dependent factorized baselines[END_REF], see Appendix A for a formal definition of b. These baselines are usually designed to minimize the variance of the gradient estimate, but even them need to be estimated from data, partially reducing their effectiveness. On the other hand, there has been a surge of recent interest in variance reduction techniques for gradient optimization in supervised learning (SL). Although these techniques have been mainly derived for finite-sum problems, we will show in Section 3 how they can be used in RL. In particular, we will show that the proposed SVRPG algorithm can take the best of both worlds (i.e., SL and RL) since it can be plugged into a policy gradient estimate using baselines. The next section has the aim to describe variance reduction techniques for finite-sum problems. In particular, we will present the SVRG algorithm that is at the core of this work.

Stochastic Variance-Reduced Gradient

Finite-sum optimization is the problem of maximizing an objective function f (θ) which can be decomposed into the sum or average of a finite number of functions z i (θ):

max θ f (θ) = 1 N N i=1 z i (θ) .
This kind of optimization is very common in machine learning, where each z i may correspond to a data sample x i from a dataset D N of size N (i.e., z i (θ) = z(x i |θ)). A common requirement is that z must be smooth and concave in θ.2 Under this hypothesis, full gradient (FG) ascent [START_REF] Cauchy | Méthode générale pour la résolution des systemes d'équations simultanées[END_REF] with a constant step size achieves a linear convergence rate in the number T of iterations (i.e., parameter updates) [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. However, each iteration requires N gradient computations, which can be too expensive for large values of N . Stochastic Gradient (SG) ascent (e.g., [START_REF] Robbins | A stochastic approximation method[END_REF][START_REF] Bottou | Large scale online learning[END_REF] overcomes this problem by sampling a single sample x i per iteration, but a vanishing step size is required to control the variance introduced by sampling. As a consequence, the lower per-iteration cost is paid with a worse, sub-linear convergence rate [START_REF] Nemirovskii | Problem complexity and method efficiency in optimization[END_REF]. Starting from SAG, a series of variations to SG have been proposed to achieve a better trade-off between convergence speed and cost per iteration: e.g., SAG [START_REF] Roux | A stochastic gradient method with an exponential convergence rate for finite training sets[END_REF], SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF], SAGA (Defazio et al., 2014a), Finito (Defazio et al., 2014b), and MISO [START_REF] Mairal | Incremental majorization-minimization optimization with application to large-scale machine learning[END_REF]. The common idea is to reuse past gradient computations to reduce the variance of the current estimate. In particular, Stochastic Variance-Reduced Gradient (SVRG) is often preferred to other similar methods for its limited storage requirements, which is a significant advantage when deep and/or wide neural networks are employed.

:= θ s = θ s m µ = ∇f ( θ s ) for t = 0 to m -1 do x ∼ U (D N ) v s+1 t = µ + ∇z(
[0, S -1] × [0, m -1]}
The idea of SVRG (Algorithm 1) is to alternate full and stochastic gradient updates. Each m = O(N ) iterations, a snapshot θ of the current parameter is saved together with its full gradient ∇f ( θ) = 1 N i ∇z(x i | θ). Between snapshots, the parameter is updated with f (θ), a gradient estimate corrected using stochastic gradient. For any t ∈ {0, . . . , m -1}:

f (θ t ) := v t = ∇f ( θ) + ∇z(x|θ t ) -∇z(x| θ), (3)
where x is sampled uniformly at random from D N (i.e., x ∼ U(D N )). Note that t = 0 corresponds to a FG step (i.e., f (θ 0 ) = ∇f ( θ)) since θ 0 := θ. The corrected gradient f (θ) is an unbiased estimate of ∇f (θ), and it is able to control the variance introduced by sampling even with a fixed step size, achieving a linear convergence rate without resorting to a plain full gradient.

More recently, some extensions of variance reduction algorithms to the non-concave objectives have been proposed (e.g., [START_REF] Allen-Zhu | Variance reduction for faster non-convex optimization[END_REF]Reddi et al., 2016a;[START_REF] Owen | Monte Carlo theory, methods and examples[END_REF]. In this scenario, f is typically required to be L-smooth, i.e., ∇f (θ ) -∇f (θ) 2 ≤ L θθ 2 for each θ, θ ∈ R n and for some Lipschitz constant L. Under this hypothesis, the convergence rate of SG is O( 1 / √ T ) [START_REF] Ghadimi | Stochastic first-and zeroth-order methods for nonconvex stochastic programming[END_REF], i.e., T = O( 1 / 2 ) iterations are required to get ∇f (θ) 2 2 ≤ . Again, SVRG achieves the same rate as FG (Reddi et al., 2016a), which is O( 1 T ) in this case [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. The only additional requirement is to select θ * uniformly at random among all the θ k instead of simply setting it to the final value (k being the iterations).

SVRG in Reinforcement Learning

In online RL problems, the usual approach is to tune the batch size of SG to find the optimal trade-off between variance and speed. Recall that, compared to SL, the samples are not fixed in advance but we need to collect them at each policy change. Since this operation may be costly, we would like to minimize the number of interactions with the environment. For these reasons, we would like to apply SVRG to RL problems in order to limit the variance introduced by sampling trajectories, which would ultimately lead to faster convergence. However, a direct application of SVRG to RL is not possible due to the following issues:

Non-concavity: the objective function J(θ) is typically non-concave.

Infinite dataset: the RL optimization cannot be expressed as a finite-sum problem. The objective function is an expected value over the trajectory density p θ (τ ) of the total discounted reward, for which we would need an infinite dataset.

Non-stationarity: the distribution of the samples changes over time. In particular, the value of the policy parameter θ influences the sampling process.

To deal with non-concavity, we require J(θ) to be L-smooth, which is a reasonable assumption for common policy classes such as Gaussian3 and softmax (e.g., [START_REF] Furmston | A unifying perspective of parametric policy search methods for markov decision processes[END_REF][START_REF] Pirotta | Policy gradient in lipschitz markov decision processes[END_REF]. Because of the infinite dataset, we can only rely on an estimate of the full gradient. [START_REF] Harikandeh | Stopwasting my gradients: Practical svrg[END_REF] analysed this scenario under the assumptions of z being concave, showing that SVRG is robust to an inexact computation of the full gradient. In particular, it is still possible to recover the original convergence rate if the error decreases at an appropriate rate. [START_REF] Bietti | Stochastic optimization with variance reduction for infinite datasets with finite sum structure[END_REF] performed a similar analysis on MISO. In Section 4 we will show how the estimation accuracy impacts on the convergence results with a non-concave objective. Finally, the non-stationarity of the optimization problem introduces a bias into the SVRG estimator in Eq. (3). To overcome this limitation we employ importance weighting (e.g., [START_REF] Rubinstein | Simulation and the monte carlo method[END_REF][START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF] to correct the distribution shift.

We can now introduce Stochastic Variance-Reduced Policy Gradient (SVRPG) for a generic policy gradient estimator g. Pseudo-code is provided in Algorithm 2. The overall structure is the same as Algorithm 1, but the snapshot gradient is not exact and the gradient estimate used between snapshots is corrected using importance weighting:4

J(θ t ) = ∇ N J( θ) + g(τ |θ t ) -ω(τ |θ t , θ)g(τ | θ)
for any t ∈ {0, . . . , m -1}, where ∇ N J( θ) is as in Eq. ( 2) where D N is sampled using the snapshot policy π θ , τ is

) (see Eq. (2)) for t = 0 to m -1 do Sample B trajectories {τ i } from p(•|θ s+1 t ) c s+1 t = 1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i |θ s+1 t , θ s )g(τ i | θ s ) v s+1 t = µ + c s+1 t θ s+1 t+1 = θ s+1 t + αv s+1 t end for end for return θ A := θ s+1 t with (s, t) picked uniformly at ran- dom from {[0, S -1] × [0, m -1]} sampled from the current policy π θt , and ω(τ |θ t , θ) = p(τ | θ) p(τ |θt
) is an importance weight from π θt to the snapshot policy π θ . Similarly to SVRG, we have that θ 0 := θ, and the update is a FG step. Our update is still fundamentally on-policy since the weighting concerns only the correction term. However, this partial "off-policyness" represents an additional source of variance. This is a well-known issue of importance sampling (e.g., [START_REF] Thomas | High-confidence offpolicy evaluation[END_REF]. To mitigate it, we use mini-batches of trajectories of size B N to average the correction, i.e.,

J(θ t ) := v t = ∇ N J( θ) (4) + 1 B B-1 i=0 g(τ i |θ t ) -ω(τ i |θ t , θ)g(τ i | θ) ct .
It is worth noting that the full gradient and the correction term have the same expected value:

E τi∼p(•|θt) 1 B B-1 i=0 ω(τ i |θ t , θ)g(τ i | θ) = ∇J( θ)
.5 This property will be used to prove Lemma 3.1. The use of mini-batches is also common practice in SVRG since it can yield a performance improvement even in the supervised case [START_REF] Harikandeh | Stopwasting my gradients: Practical svrg[END_REF][START_REF] Konečnỳ | Mini-batch semi-stochastic gradient descent in the proximal setting[END_REF]. It is easy to show that the SVRPG estimator has the following, desirable properties: Lemma 3.1. Let ∇ N J(θ) be an unbiased estimator of (1) and let θ * ∈ arg min θ {J(θ)}. Then, the SVRG estimate in (4) is unbiased

E [ J(θ)] = ∇J(θ).
(5)

and regardless of the mini-batch size B:6

Var [ J(θ * )] = Var ∇ N J(θ * ) . (6)
Previous results hold for both REINFORCE and G(PO)MDP.

In particular, the latter result suggests that an SVRG-like algorithm using J(θ) can achieve faster convergence, by performing much more parameter updates with the same data without introducing additional variance (at least asymptotically). Note that the randomized return value of Algorithm 2 does not affect online learning at all, but will be used as a theoretical tool in the next section.

Convergence Guarantees of SVRPG

In this section, we state the convergence guarantees for SVRPG with REINFORCE or G(PO)MDP gradient estimator. We mainly leverage on the recent analysis of nonconcave SVRG (Reddi et al., 2016a;[START_REF] Allen-Zhu | Variance reduction for faster non-convex optimization[END_REF]. Each of the three challenges presented at the beginning of Section 3 can potentially prevent convergence, so we need additional assumptions. In Appendix C we show how Gaussian policies satisfy these assumptions.

1) Non-concavity. A common assumption, in this case, is to assume the objective function to be L-smooth. However, in RL we can consider the following assumption which is sufficient for the L-smoothness of the objective (see Lemma B.2).

Assumption 4.1 (On policy derivatives). For each stateaction pair (s, a), any value of θ, and all parameter components i, j there exist constants 0 ≤ G, F < ∞ such that:

|∇ θi log π θ (a|s)| ≤ G, ∂ 2 ∂θ i ∂θ j log π θ (a|s) ≤ F.
2) FG Approximation. Since we cannot compute an exact full gradient, we require the variance of the estimator to be bounded. This assumption is similar in spirit to the one in [START_REF] Harikandeh | Stopwasting my gradients: Practical svrg[END_REF].

Assumption 4.2 (On the variance of the gradient estimator).

There is a constant V < ∞ such that, for any policy π θ :

Var [g(•|θ)] ≤ V.
3) Non-stationarity. Similarly to what is done in SL [START_REF] Cortes | Learning bounds for importance weighting[END_REF], we require the variance of the importance weight to be bounded.

Assumption 4.3 (On the variance of importance weights).

There is a constant W < ∞ such that, for each pair of policies encountered in Algorithm 2 and for each trajectory,

Var [ω(τ |θ 1 , θ 2 )] ≤ W, ∀θ 1 , θ 2 ∈ R d , τ ∼ p(•|θ 1 ).
Differently from Assumptions 4.1 and 4.2, Assumption 4.3 must be enforced by a proper handling of the epoch size m.

We can now state the convergence guarantees for SVRPG.

E ∇J(θ A ) 2 2 ≤ J(θ * ) -J(θ 0 ) ψT + ζ N + ξ B ,
where θ * is a global optimum and ψ, ζ, ξ depend only on G, F, V, W, α and m.

Refer to Appendix B for a detailed proof involving the definition of the constants and the meta-parameter constraints.

By analysing the upper-bound in Theorem 4.4 we observe that: I) the O( 1 /T ) term is coherent with results on nonconcave SVRG (e.g., Reddi et al., 2016a); II) the O( 1 /N) term is due to the FG approximation and is analogous to the one in [START_REF] Harikandeh | Stopwasting my gradients: Practical svrg[END_REF]; III) the O( 1 /B) term is due to importance weighting. To achieve asymptotic convergence, the batch size N and the mini-batch size B should increase over time. In practice, it is enough to choose N and B large enough to make the second and the third term negligible, i.e., to mitigate the variance introduced by FG approximation and importance sampling, respectively. Once the last two terms can be neglected, the number of trajectories needed to achieve ∇J(θ)

2 2 ≤ is O( B+ N /m
). In this sense, an advantage over batch gradient ascent can be achieved with properly selected meta-parameters. In Section 5.2 we propose a joint selection of step size α and epoch size m. Finally, from the return statement of Algorithm 2, it is worth noting that J(θ A ) can be seen as the average performance of all the policies tried by the algorithm. This is particularly meaningful in the context of online learning that we are considering in this paper.

Remarks on SVRPG

The convergence guarantees presented in the previous section come with requirements on the meta-parameters (i.e., α and m) that may be too conservative for practical applications. Here we provide a practical and automatic way to choose the step size α and the number of sub-iterations m performed between snapshots. Additionally, we provide a variant of SVRPG exploiting a variance-reduction technique for importance weights. Despite lacking theoretical guarantees, we will show in Section 7 that this method can outperform the baseline SVRPG (Algorithm 2).

Full Gradient Update

As noted in Section 3, the update performed at the beginning of each epoch is equivalent to a full-gradient update. In our setting, where collecting samples is particularly expensive, the B trajectories collected using the snapshot trajectory π θ s feels like a waste of data (the term

i g(τ i ) -ω(τ i )g(τ i ) = 0 since θ 0 = θ).
In practice, we just perform an approximate full gradient update using the N trajectories sampled to compute ∇ N J( θ s ), i.e.,

θ s+1 1 = θ s + α ∇ N J( θ s ) θ s+1 t+1 = θ s+1 t + α J(θ s+1 t ) for t = 1, . . . , m -1.
In the following, we will always use this practical variant.

Meta-Parameter Selection

The step size α is crucial to balance variance reduction and efficiency, while the epoch length m influences the variance introduced by the importance weights. Low values of m are associated with small variance but increase the frequency of snapshot points (which means many FG computations). High values of m may move policy π θt far away from the snapshot policy π θ , causing large variance in the importance weights. We will jointly set the two meta-parameters.

Adaptive step size. A standard way to deal with noisy gradients is to use adaptive strategies to compute the step size. ADAptive Moment estimation (ADAM) [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] stabilizes the parameter update by computing learning rates for each parameter based on an incremental estimate of the gradient variance. Due to this feature, we would like to incorporate ADAM in the structure of the SVRPG update. Recall that SVRPG performs two different updates of the parameters θ: I) FG update in the snapshot; II) corrected gradient update in the sub-iterations. Given this structure, we suggest using two separate ADAM estimators:

θ s+1 1 = θ s + α FG s ∇ N J( θ s ) θ s+1 t+1 = θ s+1 t + α SI s+1,t J(θ s+1 t ) for t = 1, . . . , m -1,
where α FG s is associated with the snapshot and α SI s+1,t with the sub-iterations (see Appendix D for details). By doing so, we decouple the contribution of the variance due to the approximate FG from the one introduced by the subiterations. Note that these two terms have different orders of magnitude since are estimated with a different number of trajectories (B N ) and the estimator in the snapshot does not require importance weights. The use of two ADAM estimators allows to capture and exploit this property.

Adaptive epoch length. It is easy to imagine that a predefined schedule (e.g., m fixed in advance or changed with a policy-independent process) may poorly perform due to the high variability of the updates. In particular, given a fixed number of sub-iterations m, the variance of the updates in the sub-iterations depends on the snapshot policy and the sampled trajectories. Since the ADAM estimate partly captures such variability, we propose to take a new snapshot (i.e., interrupt the sub-iterations) whenever the step size α SI proposed by ADAM for the sub-iterations is smaller than the one for the FG (i.e., α FG ). If the latter condition is verified, it amounts to say that the noise in the corrected gradient has overcome the information of the FG. Formally, the stopping condition is as follows

If α FG N > α SI B then take snapshot,
where we have introduced N and B to take into account the trajectory efficiency (i.e., weighted advantage). The less the number of trajectories used to update the policy, the better.

Including the batch sizes in the stopping condition allows us to optimize the trade-off between the quality of the updates and the cost of performing them.

Normalized Importance Sampling

As mentioned in Section 5.2, importance weights are an additional source of variance. A standard way to cope with this issue is self-normalization (e.g., [START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF][START_REF] Owen | Monte Carlo theory, methods and examples[END_REF]. This technique can reduce the variance of the importance weights at the cost of introducing some bias (Owen, 2013, Chapter 9). Whether the trade-off is advantageous depends on the specific task. Introducing self-normalization in the context of our algorithm, we switch from Eq. (4) to:

J(θ t ) = ∇ N J( θ) + 1 B B-1 i=0 [g(τ i |θ t )] - 1 Ω B-1 i=0 ω(τ i |θ t , θ)g(τ i | θ) .
where

Ω = B-1 i=0 ω(τ i |θ t , θ).
In Section 7 we show that self-normalization can provide a performance improvement.

Related Work

Despite the considerable interest received in SL, variancereduced gradient approaches have not attracted the RL community. As far as we know, there are just two applications of SVRG in RL. The first approach [START_REF] Du | Stochastic variance reduction methods for policy evaluation[END_REF] aims to exploit SVRG for policy evaluation. The policy evaluation problem is more straightforward than the one faced in this paper (control problem). In particular, since the goal is to evaluate just the performance of a predefined policy, the optimization problem is stationary. The setting considered in the paper is the one of policy evaluation by minimizing the empirical mean squared projected Bellman error (MSPBE) with a linear approximation of the value function. [START_REF] Du | Stochastic variance reduction methods for policy evaluation[END_REF] shown that this problem can be equivalently reformulated as a convex-concave saddle-point problem that is characterized by a finite-sum structure. This problem can be solved using a variant of SVRG [START_REF] Palaniappan | Stochastic variance reduction methods for saddle-point problems[END_REF] for which convergence guarantees have been provided. The second approach [START_REF] Xu | Stochastic variance reduction for policy gradient estimation[END_REF] uses SVRG as a practical method to solve the optimization problem faced by Trust Region Policy Optimization (TRPO) at each iteration. This is just a direct application of SVRG to a problem having finite-sum structure since no specific structure of the RL problem is exploited. It is worth to mention that, for practical reasons, the authors proposed to use a Newton conjugate gradient method with SVRG.

In the recent past, there has been a surge of studies investigating variance reduction techniques for policy gradient methods. The specific structure of the policy gradient allows incorporating a baseline (i.e., a function b : S × A → R) without affecting the unbiasedness of the gradient (e.g., [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF]Weaver & Tao, 2001;Peters & Schaal, 2008b;[START_REF] Thomas | Policy gradient methods for reinforcement learning with function approximation and action-dependent baselines[END_REF][START_REF] Wu | Variance reduction for policy gradient with action-dependent factorized baselines[END_REF]. Although the baseline can be arbitrarily selected, literature often refers to the optimal baseline as the one minimizing the variance of the estimate. Nevertheless, even the baseline needs to be estimated from data. This fact may partially reduce its effectiveness by introducing variance. Even if these approaches share the same goal as SVRG, they are substantially different. In particular, the proposed SVRPG does not make explicit use of the structure of the policy gradient framework, and it is independent of the underlying gradient estimate (i.e., with or without baseline). This suggests that would be possible to integrate an ad-hoc SVRPG baseline to further reduce the variance of the estimate. Since this paper is about the applicability of SVRG technique to RL, we consider this topic as future work. Additionally, the experiments show that SVRPG has an advantage over G(PO)MPD even when the baseline is used (see the half-cheetah domain in Section 7).

Concerning importance weighting techniques, RL has made extensive use of them for off-policy problems (e.g., [START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF][START_REF] Thomas | High-confidence offpolicy evaluation[END_REF]. However, as mentioned before, SVRPG cannot be compared to such methods since it is in all respects an on-policy algorithm. Here, importance weighting is just a statistical tool used to preserve the unbiasedness of the corrected gradient.

Experiments

In this section, we evaluate the performance of SVRPG and compare it with policy gradient (PG) on well known continuous RL tasks: Cart-pole balancing and Swimmer (e.g., [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF]. We consider G(PO)MDP since it has a smaller variance than REINFORCE. For our algorithm, we use a batch size N = 100, a mini-batch size B = 10, and the jointly adaptive step size α and epoch length m proposed in Section 5.2. Since the aim of this comparison is to show the improvement that SVRG-flavored variance reduction brings to SG in the policy gradient framework, we set the batch size of the baseline policy gradient algorithm to B. In this sense, we measure the improvement yielded by computing snapshot gradients and using them to adjust parameter updates. Since we evaluate on-line performance over the number of sampled trajectories, the cost of computing such snapshot gradients is automatically taken into consideration. To make the comparison fair, we also use Adam in the baseline PG algorithm, which we will denote simply as G(PO)MDP in the following. In all the experiments, we use deep Gaussian policies with adaptive standard deviation (details on network architecture in Appendix E). Each experiment is run 10 times with a random policy initialization and seed, but this initialization is shared among the algorithms under comparison. The length of the experiment, i.e., the total number of trajectories, is fixed for each task. Performance is evaluated by using test-trajectories on a subset of the policies considered during the learning process. We provide average performance with 90% bootstrap confidence intervals. Task implementations are from the rllab library [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF], on which our agents are also based. 7 More details on meta-parameters and exhaustive task descriptions are provided in Appendix E.

Figure 1a compares SVRPG with G(PO)MDP on a continuous variant of the classical Cart-pole task, which is a 2D balancing task. Despite using more trajectories on average for each parameter update, our algorithm shows faster convergence, which can be ascribed to the better quality of updates due to variance reduction.

The Swimmer task is a 3D continuous-control locomotion task. This task is more difficult than cart-pole. In particular, the longer horizon and the more complex dynamics can have a dangerous impact on the variance of importance weights. In this case, the self-normalization technique proposed in Section 5.3 brings an improvement (even if not statistically significant), as shown in Figure 1b. Figure 1c shows self-normalized SVRPG against G(PO)MDP. Our algorithm outperforms G(PO)MDP for almost the entire learning process. Also here, we note an increase of speed in early iterations, and, toward the end of the learning process, the improvement becomes statistically significant.

Preliminary results on actor-critic. Another variancereduction technique in policy gradient consists of using baselines or critics. This tool is orthogonal to the methods described in this paper, and the theoretical results of Section 4 are general in this sense. In the experiments de- scribed so far, we compared against the so-called actor-only G(PO)MDP, i.e., without the baseline. To move towards a more general understanding of the variance issue in policy gradient, we also test SVRPG in an actor-critic scenario. To do so, we consider the more challenging MuJoCo [START_REF] Todorov | Mujoco: A physics engine for model-based control[END_REF] Half-cheetah task, a 3D locomotion task that has a larger state-action space than Swimmer. Figure 1d compares self-normalized SVRPG and G(PO)MDP on Halfcheetah, using the critic suggested in [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF] for both algorithms. Results are promising, showing that a combination of the baseline usage and SVRG-like variance reduction can yield an improvement that the two techniques alone are not able to achieve. Moreover, SVRPG presents a noticeably lower variance. The performance of actorcritic G(PO)MDP 8 on Half-Cheetah is coherent with the one reported in [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF]. Other results are not comparable since we did not use the critic.

Conclusion

In this paper, we introduced SVRPG, a variant of SVRG designed explicitly for RL problems. The control prob-8 [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF] report results on REINFORCE. However, inspection on rllab code and documentation reveals that it is actually PGT [START_REF] Sutton | Policy gradient methods for reinforcement learning with function approximation[END_REF], which is equivalent to G(PO)MDP (shown by Peters & Schaal, 2008b). Using the name REINFORCE in a general way is inaccurate, but widespread. lem considered in the paper has a series of difficulties that are not common in SL. Among them, non-concavity and approximate estimates of the FG have been analysed independently in SL (e.g., [START_REF] Allen-Zhu | Variance reduction for faster non-convex optimization[END_REF]Reddi et al., 2016a;[START_REF] Harikandeh | Stopwasting my gradients: Practical svrg[END_REF] but never combined. Nevertheless, the main issue in RL is the non-stationarity of the sampling process since the distribution underlying the objective function is policy-dependent. We have shown that by exploiting importance weighting techniques, it is possible to overcome this issue and preserve the unbiasedness of the corrected gradient. We have additionally shown that, under mild assumptions that are often verified in RL applications, it is possible to derive convergence guarantees for SVRPG. Finally, we have empirically shown that practical variants of the theoretical SVRPG version can outperform classical actor-only approaches on benchmark tasks. Preliminary results support the effectiveness of SVRPG also with a commonly used baseline for the policy gradient. Despite that, we believe that it will be possible to derive a baseline designed explicitly for SVRPG to exploit the RL structure and the SVRG idea jointly. Another possible improvement would be to employ the natural gradient [START_REF] Kakade | A natural policy gradient[END_REF] to better control the effects of parameter updates on the variance of importance weights. Future work should also focus on making batch sizes N and B adaptive, as suggested in [START_REF] Papini | Adaptive batch size for safe policy gradients[END_REF].

We present a brief overview of the two most widespread gradient estimators (REINFORCE [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF] and G(PO)MDP [START_REF] Baxter | Infinite-horizon policy-gradient estimation[END_REF])) both in on-policy and off-policy settings. Let τ = { s t , a t } H t=0 = {z t } H t=0 = z 0:H is a (H + 1)-steps trajectory. Given that τ depends on the MDP M = {S, A, P, R, γ, ρ} and the actual policy π, the trajectory is said drawn from density distribution p(τ |π, M ) defined as:

p(τ |π, M ) = ρ(s 0 )π(z 0 ) H k=1 P(s k |z k-1 )π(z k ).
We can now recall the definition of policy performance

J(π θ ) = E τ ∼p(•|π θ ) [R(τ )|M ] ,
where

R(τ ) = H t=0 γ t R(z t ). The policy gradient ∇J(θ) is ∇J(θ) = E τ ∼p(•|π θ ) [∇ log p(τ |θ)R(τ )] = E τ ∼p(•|π θ )   H j=0 γ j R(z j ) H i=0 ∇ log π(z i )   . ( 7
)
On-policy setting. Consider a policy π θ and let D N = {τ i } N i=1 be a dataset collected using policy π θ . The REINFORCE gradient estimator [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF] provides a simple, unbiased way of estimating the gradient:

∇ N J(θ) = 1 N N n=1 H h=0 ∇ log π θ (z n h ) H h=0 γ h r n h -b(z n h ) g(τn|θ):=∇ log p(τn|θ)R(τn)
, where subscripts denote the time step, superscripts denote the trajectory, r n h is the reward actually collected at time h from trajectory τ n and b : S × A → R (e.g., [START_REF] Thomas | Policy gradient methods for reinforcement learning with function approximation and action-dependent baselines[END_REF]. The G(PO)MDP gradient estimator [START_REF] Baxter | Infinite-horizon policy-gradient estimation[END_REF]) is a refinement of REINFORCE which is subject to less variance [START_REF] Zhao | Analysis and improvement of policy gradient estimation[END_REF] while preserving the unbiasedness:

∇ N J(θ) = 1 N N n=1 H h=0 h k=0 ∇ log π θ (z n h ) γ h r n h -b(z n h ) g(τn|θ)
.

G(PO)MDP can be seen as a more efficient implementation of the REINFORCE algorithm. In fact, the latter does not perform an optimal credit assignment since it ignores that the reward at time t does not depend on the action performed after time t. G(PO)MDP overcomes this issue taking into account the causality of rewards in the REINFORCE definition of policy gradient.

Off-policy setting. In off-policy setting two policies, called behavioural π B and target π T , are involved. The first is used to select actions for the interaction with the system, while the second is used to evaluate the agent performance and it is improved in each update. Suppose now that we aim to estimate the performance of the target policy π T but we have samples collected using policy π B . We can use importance weight correction to correct the shift in the distribution and obtain an unbiased estimate of J(π T ):

J(π T ) = E τ ∼p(•|π T ) [R(τ )] = E τ ∼p(•|π B ) [ω(τ )R(τ )]
where ω(τ |π B , π

T ) = p(τ,π T ) p(τ |π B ) = ω(z 0:H |π B , π T ) = H w=0 ω(z w |π B , π T ) and ω(z w |π B , π T ) = π T (aw|sw) π B (aw|sw)
The definition of the off-policy version of ( 7) is (e.g., [START_REF] Jurčíček | Reinforcement learning for spoken dialogue systems using off-policy natural gradient method[END_REF])

∇J(π T ) = E τ ∼p(•|π B ) ω(τ |π B , π T )∇ log p(τ |π T )R(τ ) = E τ ∼p(•|π B ) ω(τ |π B , π T )g(τ |π T ) . ( 8
)
For ω(τ |π B , π T ) being well defined the behavioural policy should have non-zero probability of selecting any action in every state i.e., π B (a|s) > 0 for any (s, a) ∈ S × A. Equation 8 is important for proving Theorem 4.4 since it provides a common representation of REINFORCE and G(PO)MDP.

The off-policy version of REINFORCE is easily obtained by taking the empirical average of (8):

∇J(π T ) = 1 N N n=1 ω(τ n |π B , π T ) H h=0 ∇ log π T (z n h ) H h=0 γ h R(z n h ) g(τn|π T )
.

The G(PO)MDP off-policy estimator is defined as follows

∇J(π T ) = 1 N N n=1 H h=0 h k=0 ∇ log π T (z n k ) γ h R(z n h )ω(z 0:h |π B , π T ) ω(τn|π B ,π T )g(τn|π T )
.

B. Proofs

In this section, we prove all the claims made in the paper, with the primary objective of proving Theorem 4.4. Our proof is adapted from the one of Theorem 2 from (Reddi et al., 2016a) and has a very similar structure, but with all the additional challenges and assumptions described in Section 4.

Note that in the following we will make wide use of the following properties.

Assumption B.1. We consider an estimate ∇ N J(θ) as in Eq. 2 such that 1. On-policy Unbiased Estimator.

E τi∼π(•|θ) ∇ N J(θ) = E τi∼π(•|θ) 1 N N i=0 g(τ i |θ) = ∇J(θ)
2. Off-policy Unbiased Estimator.

E τi∼∆(•|π B ) 1 N N i=0 ω(τ i |π B , θ)g(τ i |θ) = ∇J(θ)
Note that these assumptions are verified by REINFORCE and G(PO)MDP.

Definitions

We give some additional definitions which will be useful in the proofs.

Definition B.1. For a random variable X:

E s [X] = E τj ∼π(•| θ s )∀j∈N X| θ s ,
where θ s is defined in Algorithm 2 and N = [0, . . . , N ).

We introduce the notation τ i,h to denote the h-th trajectory collected using policy θ s+1 i where s will be clear from the context. Definition B.2. For a random variable X:

E t|s [X] := E τj ∼π(•| θ s )∀j∈N τ i,h ∼π(•|θ s+1 i )∀h∈B, for i = 0, . . . , t X| θ s := E τj ∼π(•| θ s )∀j∈N E τ 0,h ∼π(•|θ s+1 0 )∀h∈B . . . E τ t,h ∼π(•|θ s+1 t )∀h∈B X|θ s+1 t . . . |θ s+1 0 | θ s = E t-1|s E τ t,h ∼π(•|θ s+1 t ) X|θ s+1 t
where the sequence θ s , θ s+1 0 , . . . , θ s+1 t is defined in Algorithm 2, N = [0, . . . , N ), and B = [0, . . . , B). To avoid inconsistencies, we also define

E (-1)|s [X] := E s [X].
Intuitively, the E t|s [•] operator computes the expected value with respect to the sampling of trajectories from the snapshot θ s up to the t-th iteration included. Note that the order in which expected values are taken is important since each θ s+1 t is function of previously sampled trajectories and is used to sample new ones. Definition B.3. For random vectors X, Y:

Cov s (X, Y ) := Tr E t|s (X -E t|s [X])(Y -E t|s [Y ]) T , Var s [X] := Cov s (X, Y ) ,
where Tr(•) denotes the trace of a matrix. From the linearity of expected value we have the following:

Var s [X] = E s X -E s [X]
∇ ∇J(θ s+1 t ) := ∇J( θ s ) + g(τ i |θ s+1 t ) -ω(τ i |θ s+1 t , θ s )g(τ i | θ s ) = J(θ s+1 t ) -∇ N J( θ s ) + ∇J( θ s ) = J(θ s+1 t ) -e s

Basic Lemmas

We prove two basic properties of the SVRPG update. Lemma 3.1. Let ∇ N J(θ) be an unbiased estimator of (1) and let θ * ∈ arg min θ {J(θ)}. Then, the SVRG estimate in (4)

is unbiased E [ J(θ)] = ∇J(θ). ( 5
)
and regardless of the mini-batch size B: 9

Var [ J(θ * )] = Var ∇ N J(θ * ) . (6)
Proof.

E [ J(θ)] = E ∇ N J( θ) + E ∇ B J(θ) -E 1 B B-1 i=0 ω(τ i |θ, θ)g(τ i | θ) = ∇J( θ) + ∇J(θ) -∇J( θ) = ∇J(θ).
9 For any vector x, we use Var[x] to denote the trace of the covariance matrix, i.e., Tr(E (x

-E [x])(x -E [x]) T ).
Note that the importance weight is necessary to guarantee unbiasedness, since the τ i are sampled from π θ . As θ → θ * , also θ → θ * . Hence, by continuity of J(θ):

Var [ J(θ)] → Var ∇ N J(θ * ) + 1 B Var g(τ |θ * ) - ω(τ |θ * , θ * ) g(τ |θ * ) = Var ∇ N J(θ * ) .
Note that it is important that the trajectories used in the second and the third term are the same for the variance to vanish.

Ancillary Lemmas

Before addressing the main convergence theorem, we prove some useful lemmas.

Lemma B.2. Under Assumption 4.1, J(θ) is L-smooth for some positive Lipschitz constant L J .

Proof. By definition of J(θ):

∂ 2 J(θ) ∂θ i ∂θ j = T ∂ 2 ∂θ i ∂θ j p(τ |θ)R(τ ) dτ = T p(τ |θ)∇ log p θ (τ )∇ log p θ (τ ) T R(τ ) dτ + T π θ (τ ) ∂ 2 ∂θ i ∂θ j log p(τ |θ)R(τ ) dτ ≤ sup τ ∈T {|R(τ )|} H 2 G 2 + HF (10) = 1 -γ H 1 -γ RH HG 2 + F ,
where 10 is from Assumption 4.1. Since the Hessian is bounded, J(θ) is Lipschitz-smooth.

Lemma B.3. Under Assumption 4.1, whether we use the REINFORCE or the G(PO)MDP gradient estimator, g(τ |θ) is Lipschitz continuous with Lipschitz constant L g , i.e., for any trajectory τ ∈ T :

g(τ |θ) -g(τ |θ ) 2 2 ≤ L g θ -θ 2 2 .
Proof. For both REINFORCE and G(PO)MDP, g(τ |θ) is a linear combination of terms of the kind ∇ log π θ (a t |s t )γ t r t (Peters & Schaal, 2008b). These terms have bounded gradient from the second inequality of Assumption 4.1 and the fact that |r t | ≤ R. If a baseline is used in REINFORCE or G(PO)MDP, we only need the additional assumption that said baseline is bounded. Bounded gradient implies Lipschitz continuity. Finally, the linear combination of Lipschitz continuous functions is Lipschitz continuous.

Lemma B.4. Under Assumption 4.1, whether we use the REINFORCE or the G(PO)MDP gradient estimator, for every τ ∈ T and θ ∈ Θ, there is a positive constant Γ < ∞ such that:

g(τ |θ) 2 2 ≤ Γ.
Proof. For REINFORCE we have, from Assumption 4.1:

g(τ |θ) 2 2 = ∇ log p θ (τ )R(τ ) 2 2 = H-1 t=0 ∇ log p θ (a t |s t ) H-1 t=0 γ t r t 2 2 ≤ H 2 G 2 (1 -γ H ) 2 (1 -γ) 2 R 2 dim(Θ) := Γ
For G(PO)MDP, we do not have a compact expression for g, but since it is derived from REINFORCE by neglecting some terms of the kind ∇ log π θ (a t |s t )γ t r t [START_REF] Baxter | Infinite-horizon policy-gradient estimation[END_REF]Peters & Schaal, 2008b), the above bound still holds. If a baseline is used in REINFORCE or G(PO)MDP, we only need the additional assumption that said baseline is bounded.

Lemma B.5. For any random vector X, the variance (as defined in Definition B.3), can be bounded as follows:

Var s [X] ≤ E s X 2 .
Proof. By using basic properties of expected value and scalar variance:

Var s [X] = E s X -E s [X] 2 = E s   dim(X) i=1 (X i -E s [X i ]) 2   = dim(X) i=1 E s (X i -E s [X i ]) 2 ≤ dim(X) i=1 E s X 2 i = E s   dim(X) i=1 X 2 i   = E s X 2 .
Lemma B.6. Under Assumption 4.1 , the expected squared norm of the SVRPG gradient can be bounded as follows:

E t|s J(θ s+1 t ) 2 2 ≤ E t-1|s ∇J(θ s+1 t ) 2 2 + L 2 g B E t-1|s θ s+1 t -θ s 2 2 + 1 N Var s g(•| θ s ) + ΓW B
Proof. For ease of notation denote ω(τ

i ) := ω(τ i |θ s+1 t , θ s ).
Then,

E t|s J(θ s+1 t ) 2 2 = E t|s   ∇ N J( θ s ) + 1 B B-1 i=0 g(τ i |θ s+1 t ) - 1 B B-1 i=0 ω(τ i )g(τ i | θ s ) 2   = E t|s   ∇ N J( θ s ) + 1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) ± ∇J(θ s+1 t ) ± ∇J( θ s ) 2   ≤ E t-1|s ∇J(θ s+1 t ) 2 + E s ∇ N J( θ s ) -E s ∇ N J( θ s ) 2 + E t|s   1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) -E t|s 1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) 2   = E t-1|s ∇J(θ s+1 t ) 2 + Var s ∇ N J( θ s ) + E t|s   1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) -E t|s 1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) 2   (11) = E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θ s ) + E t|s   1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) -E t|s 1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) 2   (12) ≤ E t-1|s ∇J(θ s+1 t ) 2 2 + 1 N Var s g(•| θ s ) + E t|s   1 B B-1 i=0 g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) 2 2   (13) ≤ E t-1|s ∇J(θ s+1 t ) 2 2 + 1 N Var s g(•| θ s ) + 1 B 2 B-1 i=0 E t|s g(τ i |θ s+1 t ) -ω(τ i )g(τ i | θ s ) ± g(τ i | θ s ) 2 2 ≤ E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θ s ) + 1 B 2 B-1 i=0 E t|s g(τ i |θ s+1 t ) -g(τ i | θ s ) 2 + 1 B 2 B-1 i=0 E t|s g(τ i | θ s ) -ω(τ i )g(τ i | θ s ) 2 ≤ E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θ s ) + L 2 g B E t-1|s θ s+1 t -θ s 2 + 1 B 2 B-1 i=0 E t|s (1 -ω(τ i ))g(τ i | θ s ) 2 (14) ≤ E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θ s ) + L 2 g B E t-1|s θ s+1 t -θ s 2 + Γ 1 B 2 B-1 i=0 E t|s (ω(τ i ) -1) 2 (15) = E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θ s ) + L 2 g B E t-1|s θ s+1 t -θ s 2 + Γ B 2 B-1 i=0 Var t|s [ω(τ i )] ≤ E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θ s ) + L 2 g B E t-1|s θ s+1 t -θ s 2 + ΓW B , (16)
where ( 11) is from ( 9), ( 12) is from the definition of ∇ N J(θ), ( 13) is from Lemma B.5, ( 14

E t|s J(θ s+1 t ), ϕ(θ s+1 t ) -E t|s ∇J(θ s+1 t ), ϕ(θ s+1 t ) = Cov t-1|s ∇ N J( θ s ), ϕ(θ s+1 t ) ≤ Var s ∇ N J( θ s ) • Var t-1|s ϕ(θ s+1 t ) (21) ≤ 1 2 Var s ∇ N J( θ s ) + 1 2 Var t-1|s ϕ(θ s+1 t ) (22) = 1 2N Var s g(•| θ s ) + 1 2 Var t-1|s ϕ(θ s+1 t ) (23) ≤ 1 2N Var s g(•| θ s ) + 1 2 E t-1|s ϕ(θ s+1 t ) 2 , (24)
where ( 21) comes from Cauchy-Schwarz inequality

| Cov(X, Y )| = | E (X -µ X )(Y -µ Y ) T | ≤ E (X -µ X ) 2 1/2 E (Y -µ Y ) 2 1/2 = Var(X) Var(Y ), (22)
is from Young's inequality, ( 23) is from the definition of ∇ N J(θ), and ( 24) is from Lemma B.5.

Lemma B.8. Under Assumptions 4.1 ans 4.3, the expected squared norm of the true gradient ∇J(θ s+1 t ), for appropriate choices of α t ≥ 0 and β t > 0, can be bounded as follows:

E t-1|s ∇J(θ s+1 t ) 2 ≤ R s+1 t+1 -R s+1 t Ψ t + d t V N Ψ t + f t W BΨ t ,
where

R s+1 t := E t-1|s J(θ s+1 t ) -c t θ s+1 t -θ s 2 , c m = 0, c t = c t+1 1 + α t β t + α t + α 2 t L 2 B + α 2 t L 3 2B , Ψ t = α t 1 2 - c t+1 β t - α t L 2 -α t c t+1 , d t = α t 2 (1 + 2c t+1 + α t L + 2α t c t+1 ) , f t = α 2 t Γ(L + 2c t+1 ) 2 ,
where L = max {L J , L g }, i.e., the greater of the Lipschitz constants from Lemmas B.2 and B.3.

In particular, the following constraints on α t and β t are sufficient:

0 ≤ α t < 1 -2ct+1 /βt L + 2c t+1 β t > 2c t+1 .
Proof. We have:

E t|s J(θ s+1 t+1 ) ≥ E t|s J(θ s+1 t ) + ∇J(θ s+1 t ), θ s+1 t+1 -θ s+1 t - L 2 θ s+1 t+1 -θ s+1 t 2 (25) = E t|s J(θ s+1 t ) + α t ∇J(θ s+1 t ), J(θ s+1 t ) - α 2 t L 2 J(θ s+1 t ) 2 (26) ≥ E t|s J(θ s+1 t ) + α t ∇J(θ s+1 t ) 2 - α 2 t L 2 J(θ s+1 t ) 2 - α t 2N Var s g(•| θ s ) - α t 2 E t-1|s ∇J(θ s+1 t ) 2 , (27)
where ( 25) is from the L-smoothness of J(θ) [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]

) := ∇J(θ s+1 t ).
Next, we have:

E t|s θ s+1 t+1 -θ s 2 = E t|s θ s+1 t+1 -θ s+1 t + θ s+1 t -θ s 2 = E t|s θ s+1 t+1 -θ s+1 + α t N Var s g(•| θ s ) + α t E t-1|s θ s+1 t -θ s 2 (30) ≤ E t|s α 2 t J(θ s+1 t ) 2 + θ s+1 t -θ s 2 + 2α t E t-1|s ∇J(θ s+1 t ), θ s+1 t -θ s + α t N Var s g(•| θ s ) + α t E t-1|s θ s+1 t -θ s 2 ≤ E t|s α 2 t J(θ s+1 t ) 2 + θ s+1 t -θ s 2 + 2α t E t-1|s ∇J(θ s+1 t ) θ s+1 t -θ s + α t N Var s g(•| θ s ) + α t E t-1|s θ s+1 t -θ s 2 ≤ E t|s α 2 t J(θ s+1 t ) 2 + θ s+1 t -θ s 2 + 2α t E t-1|s 1 2β t ∇J(θ s+1 t ) 2 + β t 2 θ s+1 t -θ s 2 (31) + α t N Var s g(•| θ s ) + α t E t-1|s θ s+1 t -θ s 2 , (32)
where ( 28) is obtained using the triangular inequality, ( 29

:= E t|s J(θ s+1 t+1 ) -c t+1 θ s+1 t+1 - θs 2 . ( 33
)
The objective is now to provide a lower bound to it.

R s+1 t+1 ≥ E t|s J(θ s+1 t ) - α 2 t L 2 J(θ s+1 t ) 2 + E t-1|s α t 2 ∇J(θ s+1 t ) 2 - α t 2N Var s g(•| θs ) -c t+1 E t|s θ s+1 t+1 - θs 2 (34) ≥ E t|s J(θ s+1 t ) - α 2 t L 2 J(θ s+1 t ) 2 + E t-1|s α t 2 ∇J(θ s+1 t ) 2 - α t 2N Var s g(•| θs ) -c t+1 E t|s α 2 t J(θ s+1 t ) 2 + θ s+1 t - θs 2 -2c t+1 α t E t-1|s 1 2β t ∇J(θ s+1 t ) 2 + β t 2 θ s+1 t - θs 2 -c t+1 α t N Var s g(•| θs ) -c t+1 α t E t-1|s θ s+1 t - θs 2 (35) = E t-1|s J(θ s+1 t ) -c t+1 (1 + α t β t + α t ) E t-1|s θ s+1 t -θ 2 -α 2 t L 2 + c t+1 E t|s J(θ s+1 t ) 2 + α t 2 1 - 2c t+1 β t E t-1|s ∇J(θ s+1 t ) 2 - α t 2N (1 + 2c t+1 ) Var s g(•| θs ) ≥ E t-1|s J(θ s+1 t ) -c t+1 (1 + α t β t + α t ) E t-1|s θ s+1 t -θ 2 -α 2 t L 2 + c t+1 E t-1|s ∇J(θ s+1 t ) 2 + 1 N Var s g(•| θs ) + L 2 B E t-1|s θ s+1 t - θs 2 + ΓW B + α t 2 1 -2 c t+1 β t E t-1|s ∇J(θ s+1 t ) 2 - α t 2N (1 + 2c t+1 ) Var s g(•| θs ) (36)
Next, summing over epochs:

S-1 s=0 m-1 t=0 E t|s ∇J((θ s+1 t )) 2 ≤ S-1 s=0 E m|s J( θs+1 ) -J( θs ) ψ + T ζ N + T ξ B ≤ E J( θS ) -J( θ0 ) ψ + T ζ N + T ξ B (38) ≤ J(θ * ) -J(θ 0 ) ψ + T ζ N + T ξ B , (39)
where the expectation in (38) is w.r.t. all the trajectories sampled in a run of Algorithm 2 and ( 39) is from the definition of θ * (i.e., the policy performance maximizer). Finally, we consider the expectation w.r.t. all sources of randomness, including the uniform sampling of the output parameter:

E ∇J((θ s+1 t )) 2 = 1 T S-1 s=0 m-1 t=0 E t|s ∇J((θ s+1 t )) 2 ≤ J(θ * ) -J(θ 0 ) ψT + ζ N + ξ B .

C. Applicability to Gaussian Policies

We provide more details on the applicability of Theorem 4.4 on the case of Gaussian policies. We start from the case of one-dimensional bounded action space A ⊂ R, linear mean µ(s) = θ T φ(s) and fixed standard deviation σ:

π θ (a|s) = 1 √ 2πσ exp - (θ T φ(s) -a) 2 2σ 2 ,
where φ(s) ≤ M φ is a bounded feature vector, and we see under which conditions the three assumptions of Section 4 hold. Assumption 4.1 (On policy derivatives). For each state-action pair (s, a), any value of θ, and all parameter components i, j there exist constants 0 ≤ G, F < ∞ such that:

|∇ θi log π θ (a|s)| ≤ G, ∂ 2 ∂θ i ∂θ j log π θ (a|s) ≤ F.
For the Gaussian policy defined above, it's easy to show that:

∇ θi log π θ (τ ) = φ i (s) a -θ T φ(s) σ 2 , ∂ 2 ∂θ i ∂θ j log π θ (τ ) = φ i (s)φ j (s) σ 2 .
Hence, Assumption 4.1 is automatically satisfied10 by taking G =

M φ |A| σ 2
and F = M 2 φ σ 2 . Assumption 4.2 (On the variance of the gradient estimator). There is a constant V < ∞ such that, for any policy π θ :

Var [g(•|θ)] ≤ V.
As mentioned, [START_REF] Pirotta | Adaptive step-size for policy gradient methods[END_REF] provides a bound on the variance of the REINFORCE estimator, adapted from [START_REF] Zhao | Analysis and improvement of policy gradient estimation[END_REF], which does not depend on θ:

Var ∇ N J(θ i ) ≤ R 2 M 2 φ H(1 -γ H ) 2 N σ 2 (1 -γ) 2 .
The same authors provide a similar bound for G(PO)MDP.

Assumption 4.3 (On the variance of importance weights).

There is a constant W < ∞ such that, for each pair of policies encountered in Algorithm 2 and for each trajectory,

Var [ω(τ |θ 1 , θ 2 )] ≤ W, ∀θ 1 , θ 2 ∈ R d , τ ∼ p(•|θ 1 ).
It is noted in [START_REF] Cortes | Learning bounds for importance weighting[END_REF] that, for any two Gaussian distributions N (µ 1 , σ 1 ) and N (µ 2 , σ 2 ), the variance of the importance weights from the latter to the former is bounded whenever σ 2 > √ 2 2 σ 1 . This is automatically satisfied by our fixed-variance Gaussian policies, since σ 2 = σ 1 = σ.

We now briefly examine some generalizations of the simple Gaussian policy defined above that can be found in applications:

Multi-dimensional actions. When actions are multi-dimensional, factored Gaussian policies are typically employed, so the results trivially from the one-dimensional case. Actual multi-variate Gaussian distributions would require more calculations, but we do not expect substantially different results.

Non-linear mean. In complex continuous tasks, µ(s) often represents a deep neural network, or multi-layer perceptron, where θ are the weights of the network. The analysis of first and second order log-derivatives in such a scenario is beyond the scope of this paper.

Adaptive variance. It is a common practice to learn also the variance of the policy in order to adapt the degree of exploration. The variance (or diagonal covariance matrix in the multi-dimensional case) can be learned as a separate parameter or be state-dependent like the mean. In any case, adaptive variance must be carefully employed since it can clearly undermine all the three assumptions of Theorem 4.4.

D. Practical SVRPG Versions

We provide more details on the practical variants of SVRPG.

D.1. Adpative Step Size Algorithm 3 Adam

Input: A gradient estimate g t and parameters β 1 , β 2 , and α. κ t = β 1 κ t-1 + (1 -β 1 )g t ν t = β 2 ν t-1 + (1 -β 2 )g t • g t (• is the Hadamard (component-wise) product)

κt = κ t 1 -β t 1 νt = ν t 1 -β t 2 ∆(g t ) = α √ νt + κt
Return: The increment ∆(g t ) of the parameters.

Let us give a deeper insight on the two different learning rate schedules used by our algorithm. We report pseudo-code of the original ADAM [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] in Algorithm 3. As mentioned, we use two distinct instances of ADAM to manage different sources of variance: one related to the snapshots, and one to the sub-iterations. In this way the ADAM associated to the snapshots takes into account only the history of gradient moments at the snapshots. By using Algorithm 3 as a subroutine ADAM(g, α, β), we can explicitly define our gradient updates: where separate histories are kept for estimated first moments κ F G , κ IS and estimated second moments ν F G , ν IS . The meta-parameters α, β 1 , β 2 are constant and set to default values or with minor manual tuning (see table 1). Note that we double the sub-iterations' learning rate for the snapshot ADAM since we can rely on a larger number of trajectories (N instead of B) to control the variance.

D.2. Baseline

The baseline used in the Half Cheetah experiment is the one used in [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF]. It is a linear state-value function estimator, or critic. The (time-varying) feature encoding for the linear baseline is:

φ(s, t) = [s, s s, 0.01t, (0.01t) 2 , (0.01t) 3 , 1],

where s ∈ R d is the state vector and is the element-wise product. The baseline is then:

b(s t , a t ) = λ T φ(s t , t).

The baseline is fitted from scratch at each policy gradient iteration, with least squares, to match state-value function V π (s).

When used with SVRPG, the critic parameter λ is updated only at the snapshot.

E. Experimental Details

We describe the RL tasks of Section 7 in more detail:

1. Cart-Pole Balancing : an inverted pendulum mounted on a cart must be kept standing by moving the cart backward or forward ;4-dimensional state space: cart position x, pole angle θ, cart velocity ẋ and pole velocity θ; 1-dimensional action space: the horizontal force applied to the cart body. Reward function is defined as r(s, a) := 10 -(1 -cos(θ)) -10 -5 a 2 . The episodes terminate when |x| > 2.4 or |θ| > 0.2 or the number of time steps T is greater than 100.

2. Mujoco Swimmer: a snake-like robot immersed in a fluid must move forward; 13-dimensional state space: 3 links velocities (v x and v y of center of masses) and 2 actuated joints angles. 2-dimensional action space: the two momentums applied on actuated joints. The reward function is defined as r(s, a) := v x -10 -4 a 2 2 . The episodes terminate when the number of time steps T is greater than 500.

3. Mujoco Half Cheetah: a planar biped robot must move forward; 20-dimensional state space: 9 links and 6 actuated joints angles. 6-dimensional action space: the 6 momentums applied on actuated joints. The reward function is defined as r(s, a) := v x -0.05 a 2 2 . The episodes terminate when the number of time steps T is greater than 500.

All the parameters used in the experiments, including neural network architectures, are reported in the following Where not specified, meta-parameters are shared among G(PO)MDP and SVRPG. Refer to [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF] for more details about G(PO)MDP (REINFORCE in the paper) on the Half Cheetah task.

  dataset D N , number of epochs S, epoch size m, step size α, initial parameter θ 0 m := θ 0 for s = 0 to S -1 do θ s+1 0

Theorem 4. 4 (

 4 Convergence of the SVRPG algorithm). Assume the REINFORCE or the G(PO)MDP gradient estimator is used in SVRPG (see Equation (4)). Under Assumptions 4.1, 4.2 and 4.3, the parameter vector θ A returned by Algorithm 2 after T = m × S iterations has, for some positive constants ψ, ζ, ξ and for proper choice of the step size α and the epoch size m, the following property:

  Self-Normalized SVRPG vs G(PO)MDP on Half-Cheetah.

Figure 1 :

 1 Figure 1: Comparison of on-line performance over sampled trajectories, with 90% confidence intervals.

2 ( 9 )

 9 Cov t|s (X, Y ) and Var t|s [X] are defined in the same way from E t|s [X]. Definition B.4. The full gradient estimation error is: e s := ∇ N J( θ s ) -∇J( θ s ) Definition B.5. The ideal SVRPG gradient estimate is:

  1 , β 2 , α ,θ s+1 t+1 = ADAM J(θ s+1 t ), β 1 , β 2 , α 2 for t = 1, . . . , m -1,

  Var s [•]; (20) is from E t|s [e s ] = 0. Hence:

																) is from Lemma B.3, (15) is
	from Lemma B.4, and (16) is from Assumption 4.3.
	Lemma B.7. Under Assumption 4.1, for any function ϕ(θ s+1 t	) which is deterministic for a fixed θ s+1 t	:
	E t|s	J(θ s+1 t	), ϕ(θ s+1 t	) -E t|s ∇J(θ s+1 t	), ϕ(θ s+1 t	)		≤	1 2N	Var s g(•| θ	s	) +	1 2	E t-1|s ϕ(θ s+1 t	)	2
	Proof.
		E t|s	J(θ s+1 t	), ϕ(θ s+1 t	) = E t|s ∇ ∇J(θ s+1 t	), ϕ(θ s+1 t	) + E t-1|s e s , ϕ(θ s+1 t	)	(17)
							= E t|s ∇J(θ s+1 t	), ϕ(θ s+1 t	) + E t-1|s e s , ϕ(θ s+1 t	)	(18)
							= E t|s ∇J(θ s+1 t	), ϕ(θ s+1 t	)
							+ E t|s [e s ] , E t|s ϕ(θ s+1 t	) + Cov t-1|s ∇ N J( θ	s	), ϕ(θ s+1 t	)	(19)
							= E t|s ∇J(θ s+1 t	), ϕ(θ s+1 t	)
							+ Cov t-1|s ∇ N J( θ	s	), ϕ(θ s+1 t	)	(20)
	where (17) is from Definition B.5; (18) is from the fact that ∇ ∇J(θ s+1 t w.r.t. the sampling at time t alone, which is not true for J(θ s+1 t ); (19) is from the fact that ∇J( θ ) is both unbiased and independent from ϕ(θ s+1 t s ) is constant w.r.t. )

table : Table 1 :

 :1 Parameters used in the experiments of Section 7.

		Cart-Pole Swimmer Half Cheetah
	NN hidden weights	8	32x32	100x50x25
	NN activation	tanh	tanh	tanh
	Adam α (SVRPG)	5• 10 -2	10 -3	10 -3
	Adam α (GPOMDP)	10 -2	10 -3	10 -2
	Adam β 1	0.9	0.9	0.9
	Adam β 2	0.99	0.99	0.99
	Snapshot batch size N (SVRPG)	100	100	100
	Mini-batch size B (SVRPG)	10	10	10
	Batch size (GPOMDP)	10	10	100
	Max number of sub-iterations	50	20	20
	Task horizon	100	500	500
	Baseline	No	No	Yes
	Discount factor γ	0.99	0.995	0.99
	Total number of trajectories	10000	20000	50000

The episode duration is a random variable, but the optimal policy can reach the target state (i.e., absorbing state) in less than H steps. This has not to be confused with a finite horizon problem where the optimal policy is non-stationary.

Note that we are considering a maximization problem instead of the classical minimization one.

See Appendix C for more details on the Gaussian policy case.

Note that g can be any unbiased estimator, with or without baseline. The unbiasedness is required for theoretical results (e.g., Appendix A).

The reader can refer to Appendix A for off-policy gradients and variants of REINFORCE and G(PO)MDP.

For any vector x, we use Var[x] to denote the trace of the covariance matrix, i.e., Tr(E (x -E [x])(x -E [x]) T ).

This relies on the fact that θ T φ(s) lies in bounded A. In practice, this is usually enforced by clipping the action selected by π θ . A more rigorous way would be to employ the truncated Gaussian distribution.

Acknowledgments

This research was supported in part by French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council and French National Research Agency (ANR) under project ExTra-Learn (n.ANR-14-CE24-0010-01).

where ( 34) is from (27) noticing that E t|s ∇J(θ s+1 t

, ( 35) is from ( 32), ( 36) is from Lemma B.6, and ( 37) is from Assumption 4.2. To complete the proof, besides rearranging terms, we have to ensure that Ψ t > 0 for each t. This gives the constraints on α t and β t .

Main theorem

We finally provide the proof of the convergence theorem: Theorem 4.4 (Convergence of the SVRPG algorithm). Assume the REINFORCE or the G(PO)MDP gradient estimator is used in SVRPG (see Equation (4)). Under Assumptions 4.1, 4.2 and 4.3, the parameter vector θ A returned by Algorithm 2 after T = m × S iterations has, for some positive constants ψ, ζ, ξ and for proper choice of the step size α and the epoch size m, the following property:

where θ * is a global optimum and ψ, ζ, ξ depend only on G, F, V, W, α and m.

Proof. We prove the theorem for the following values of the constants:

where Ψ, d t and f t are defined in Lemma B.8. Starting from Lemma B.8, summing over iterations of an epoch s and using telescopic sum we obtain

By using the definition of R s t in (33), the fact that c m = 0 and θ s+1

Videos: The supplementary materials include videos showing the behavior of the final SVRPG agents on the three considered tasks.