Yunhao Tang

Mark Rowland

Rémi Munos

Michal Valko

Michal Valko Taylor

Taylor expansion of discount factors

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

One of the most popular models for reinforcement learning (RL) is the Markov decision process (MDP) with exponential discounting over an infinite horizon (Sutton and Barto, 2018;[START_REF] Martin L Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF], with discounted objectives of the following form

V π γ (x) = E π ∞ t=0 γ t r t x 0 = x .
Discounted models enjoy favorable theoretical properties, and are also the foundation of many practical RL algorithms that enjoy empirical success (e.g. see [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF]Schulman et al., 2015a;[START_REF] Timothy P Lillicrap | Continuous control with deep reinforcement learning[END_REF][START_REF] Schulman | Proximal policy optimization algorithms[END_REF]). However, in most applications of RL, the objective of interest is the expected undiscounted cumulative return,

E π T t=0 r t x 0 = x , (1)
where T < ∞ is a (possibly random) evaluation horizon, which usually also denotes the end of the trajectory. For 1 Columbia University, New York, USA 2 DeepMind, London, UK 3 DeepMind, Paris, France. Correspondence to: yt2541@columbia.edu <Yunhao>.

Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. Copyright 2021 by the author(s). example, T could be the first time the MDP gets into a terminal state (e.g., a robot falls); when the MDP does not have a natural terminal state, T could be enforced as a deterministic horizon. This creates a technical gap between algorithmic developments and implementations: it is tempting to design algorithms that optimize V π γ (x), however, further heuristics are often needed to get strong practical performance. This issue manifests itself with the policy gradient (PG) theorem (Sutton et al., 2000). Let π θ be a parameterized policy. The policy gradient (PG) ∇ θ V π θ γ (x) is computed as

E π θ ∞ t=0 γ t Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x .
(2)

However, the practical implementation of PG updates usually omits the discount factors (see for example the high-quality open source packages [START_REF] Dhariwal | OpenAI baselines[END_REF][START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF], leading to an approximate gradient of the form

E π θ T t=0 Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x . (3)
Most prior work on PG algorithms rely on this heuristic update to work properly in deep RL applications. The intuitive argument for dropping the factor γ t is that Eqn (2) optimizes V π θ γ (x), which is very myopic compared to the objective in Eqn (1). Consequently, the exponential discount γ t is too aggressive for weighting updates with large t. As a concrete example, in many MuJoCo control tasks [START_REF] Brockman | OpenAI gym[END_REF], the most commonly used discount factor is γ = 0.99. This leads to an effective horizon of 1 1-γ = 100, which is much smaller than the evaluation horizon T = 1000. This technical gap between theory and practice has been alluded to previously (by e.g., [START_REF] Brendan | Combining policy gradient and Qlearning[END_REF] and is explicitly discussed by [START_REF] Nota | Is the policy gradient a gradient[END_REF].

To bypass this gap, a straightforward solution would be to naïvely increase the discount factor γ ≥ 1 -1 T and apply the PG in Eqn (2). In the example above, this implies using γ ≥ 0.999. Unfortunately, this rarely works well in practice, as we will also see in experiments. The failure might be due to the higher variance of the estimation (Schulman et al., 2015b) or the collapse of the action gaps [START_REF] Lehnert | On value function representation of long horizon problems[END_REF][START_REF] Laroche | In reinforcement learning, all objective functions are not equal[END_REF], which is aggravated when combined with function approximations.

Nevertheless, as a theoretical framework, it is insightful to emulate the undiscounted objective in Eqn (1) using the (un)discounted objective V π γ (x) with γ ≥ 1 -1 T . To build intuitions about this approximation, note that when the time step is small t T , the multiplicative factor (γ ) t ≈ 1 and the cumulative rewards are almost undiscounted; even when t = T , we have (γ

) t ≥ (1 -1 T ) T ≈ 1 e 0.
Overall, this is a much more accurate approximation than V π γ (x). This naturally prompts us to answer the following general question: How do we evaluate and optimize V π γ (x) with estimates built for V π γ (x) where 0 < γ < γ ≤ 1?

Main idea. We study the relation between V π γ (x) and V π γ (x) via Taylor expansions. In Section 3, we identify a family of interpolating objectives between the more myopic objective V π γ (x) and the true objective of interest V π γ (x). In Section 4, we start with insights on why the heuristic in Eqn (3) might be useful in practice. Then, we apply Taylor expansions directly to the heuristic updates, to arrive at a family of interpolating updates. In Section 5, we build on theoretical insights to derive improvements to established deep RL algorithms. We show their performance gains in Section 7.

Background

Consider the setup of a MDP. At any discrete time t ≥ 0, the agent is in state x t ∈ X , takes an action a t ∈ A, receives an instant reward r t = r(x t , a t ) ∈ [0, R max ] and transitions to a next state x t+1 ∼ p(•|x t , a t ). For simplicity, we assume r(x, a) to be deterministic. Let policy π : X → P(A) be a mapping from states to distributions over actions. Let γ ∈ [0, 1) be a discount factor, define the Q-function

Q π γ (x, a) := E π [ ∞ t=0 γ t r t | x 0 = x, a 0 = a] and value function V π γ (x) := E π [ ∞ t=0 γ t r t | x 0 = x].
We also define the advantage function A π γ (x, a) := Q π γ (x, a) -V π γ (x). Here, E π [•] denotes that the trajectories (x t , a t , r t ) ∞ t=0 are generated under policy π. Throughout the paper, we use subscripts γ to emphasize that RL quantities implicitly depend on discount factors.

Linear programs for reinforcement learning

Henceforth, we assume all vectors to be column vectors. The value functions V π γ satisfy the Bellman equations V π γ (x) = E π r(x, a) + γV π γ (x ) | x 0 = x [START_REF] Bellman | A Markovian decision process[END_REF]. Such equations can be encoded into a linear program (LP) [START_REF] Pucci | The linear programming approach to approximate dynamic programming[END_REF][START_REF] Martin L Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF]. Let V ∈ R X be the primal variables, consider the following LP,

max δ T x V, V = r π + γP π V, (4)
where r π ∈ R X is the state-dependent reward r π (x ) := a π(a |x )r(x , a ) and P π ∈ R X ×X is the transition matrix under π. Here, δ x ∈ R X encodes the one-hot distribution (Dirac) at x. Similar results hold for considering the LP objective v T V with a general distribution v ∈ P(X ).

It then follows that the optimal solution to the above LP is V * = V π γ . Now, consider the dual LP to Eqn (4), let d ∈ R X be the dual variables, min (1 -γ) -1 (r π ) T d, d = (1 -γ)δ x + γ(P π ) T d. (5) The optimal solution to the dual program has a natural probabilistic interpretation. It is the discounted visitation distribution d π

x,γ under policy π with starting state x as d π

x,γ (x ) := (1 -γ) t≥0 γ t P π (x t = x |x 0 = x) where P π (x t = x |x 0 = x) is a probability measure induced by the policy π and the MDP transition kernel. By strong duality, the value function can be equivalently written as

V π γ (x) = 1 1 -γ E x ∼d π x,γ ,a ∼π(•|x ) [r(x , a )] . (6)

Taylor Expansions of Value Functions

Below, we show how to estimate V π γ (x) with approximations constructed from value functions V π γ (x) for γ < γ . Unless otherwise stated, we always assume γ < 1 for a more convenient mathematical treatment of the problem.

Taylor expansions of discount factors

We start with some notations: we abuse the notation of value functions V π γ ∈ R X to both refer to the scalar function as well as a vector. The Bellman equation for the valuefunction is expressed in the matrix form (Puterman, 2014)

V π γ = r π + γ P π V π γ . (7)
Inverting the equation,

V π γ = (I -γ P π ) -1 r π . (8)
Now, we present the main result of Taylor expansions.

Proposition 3.1. The following holds for all K ≥ 0,

V π γ = K k=0 (γ -γ)(I -γP π ) -1 P π k V π γ + (γ -γ)(I -γP π ) -1 P π K+1 V π γ residual . (9)
When γ < γ < 1, the residual norm converges to 0, which implies

V π γ = ∞ k=0 (γ -γ)(I -γP π ) -1 P π k V π γ . ( 10
)
We provide a proof sketch here: Note that γ P π = (γγ)P π + γP π and apply the Woodbury matrix identity to obtain (I -γ P π ) -1 = (I -γP π ) -1 + (γ -γ)(I -γP π ) -1 P π (I -γ P π ) -1 . We can then recursively expand Eqn (8) K times to arrive at Eqn (9). In particular, by expanding the equation once, we see that (I -γ P π ) -1 is equivalent to the following,

(I -γP π ) -1 + (γ -γ)(I -γP π ) -1 P π (I -γP π ) -1 + (γ -γ) 2 (I -γP π ) -1 P π 2 (I -γ P π ) -1 can be expanded further
, where the last term can be expanded further by plugging in the Woodbury matrix identity. See the complete proof in Appendix A.

Extensions to γ = 1. The above result can extend to the case γ = 1. We make two assumptions: A.1 The Markov chain induced by π is absorbing and T is the absorption time;

A.2 r π (x) = 0 for absorbing states x. Under these assumptions, we can interpret such absorbing states as the terminal states. As a result,

V π γ =1 (x) = E π T t=0 r t x 0 =
x is well-defined and Proposition 3.1 still holds; see Appendix A for the complete proof.

In practice, it is infeasible to sum up all infinite number of terms in the Taylor expansion. It is then of interest to consider the K th -order expansion of V π γ , which truncates the infinite series. Specifically, we define the K th -order expansion as

V π K,γ,γ := K k=0 ((γ -γ)(I -γP π ) -1 P π ) k V π γ . ( 11
)
As K increases, the K th order expansion becomes increasingly close to the infinite series, which evaluates to V π γ (x). This is formalized next.

Proposition 3.2. The following bound holds for all K ≥ 0,

V π γ (x) -V π K,γ,γ (x) ≤ γ -γ 1 -γ K+1 R max 1 -γ . ( 12
)
3.2. Sample-based approximations of Taylor expansions We now describe how to estimate V π K,γ,γ (x) via samples. First, we build some intuition on the behavior of expansions at different orders K by considering a few special cases.

Zeroth-order expansion. By setting K = 0, we see that

V π 0,γ,γ = V π γ . ( 13
)
The zeroth order expansion approximates the value function V π γ (x) of the discount factor γ with that V π γ (x) of a lower discount factor γ < γ . This is a very straightforward approximation to use in that no sampling at all is required, but it may not be accurate.

First-order expansion. When K = 1, we consider the increments of the expansions,

V π 1,γ,γ -V π 0,γ,γ = (γ -γ)(I -γP π ) -1 P π V π γ . ( 14
)
To understand the first order expansion, recall that in the definition of value function V π γ = (I -γP π ) -1 r π , immediate rewards r π are accumulated via the matrix (I -γP π ) -1 . In general, for any X, Y ∈ R X , we can interpret X = (I -γP π )) -1 Y as accumulating Y as rewards to compute X as value functions. By analogy, we can interpret the RHS of Eqn ( 14) as the value function assuming (γ -γ)P π V π γ as immediate rewards. In other words, the first order expansion bootstraps the zeroth order expansion V π γ to form a more accurate approximation. Combined with the zeroth order expansion, we can also conveniently write the difference of first-and zeroth-order expansions as an expectation

V π 1,γ,γ (x) - V 0,γ,γ (x) = (γ -γ)E π ∞ t=1 γ t-1 V π γ (x t ) x 0 = x . Let τ ∼ Geometric(1 -γ) be a random time such that P (τ = t) = (1 -γ)γ t , ∀t ∈ Z ≥1 .
The difference can also be expressed via this random time

V π 1,γ,γ (x) -V 0,γ,γ (x) = γ -γ 1 -γ E π,τ V π γ (x τ ) .
Note that from this expression, we obtain a simple unbiased estimate for V π 1,γ,γ (x) -V 0,γ,γ (x), using a sampled trajectory and a random time step τ .

General K th -order expansion. We now present results for general K. Consider the incremental term,

V π K,γ,γ -V π K-1,γ,γ = (γ -γ) K (I -γP π ) -1 P π K V π γ . ( 15
)
Note that the aggregate matrix (I -γP π ) -1 P π K suggests a recursive procedure to bootstrap from lower order expansions to construct higher order expansions. To see why, we can rewrite the right-hand side of Eqn (15) as

(γ -γ)(I -γP π ) -1 P π V π K-1,γ,γ -V π K-2,γ,γ .
Indeed, we can interpret the difference

V π K,γ,γ -V π K-1,γ,γ
as the value function under the immediate reward (γ -

γ)P π V π K-1,γ,γ -V π K-2,γ,γ
. This generalizes the bootstrap procedure of the first order expansion as a special case where we naturally assume V π -1,γ,γ = 0.

Given K i.i.d. random times τ i ∼ Geometric(1 -γ), we can write V π K,γ,γ (x) -V π K-1,γ,γ (x) as the expectation γ -γ 1 -γ K E τi,1≤i≤K V π γ (x τ1+•••+τ K ) .
Based on the above expression, Algorithm 1 provides a subroutine that generates unbiased estimates of V π K,γ,γ (x) by sub-sampling an infinite trajectory (x t , a t , r t ) ∞ t=0 with the random times.

Practical implementations. While the above and Algorithm 1 show how to compute one-sample estimates, in practice, we might want to average multiple samples along a single trajectory for variance reduction. See Appendix F for further details on the practical estimates.

Algorithm 1 Estimating the K th order expansion Require: A trajectory (x t , a t , r t ) ∞ t=0 ∼ π and discount factors γ < γ < 1 1. Compute an unbiased estimate V π γ (x t ) for states along the trajectory, e.g.,

V π γ (x t ) = t ≥t γ t -t r t . 2. Sample K random time {τ i } 1≤i≤K , all i.i.d. geometrically distributed τ i ∼ Geometric(1 -γ).

Return the unbiased estimate

K k=0 γ -γ 1-γ k V π γ (x t k ) where t k = k i=1 τ i .
Interpretation of expansions in the dual space. Recall that V π γ = (I -γ P π ) -1 r π = I(I -γ P π ) -1 r π where the identity matrix I = [δ 0 , δ 1 , ...δ X ] concatenates Dirac delta vectors δ x , ∀x ∈ X . Since r π is a constant vector, Taylor expansions essentially construct approximations to the matrix (I -γ P π ) -1 . By grouping the matrix with the reward vector (or the density matrix), we arrive at the primal expansion (or the dual expansion),

I (I -γ P π ) -1 r π primal expansions of V π γ (x) = I(I -γ P π ) -1 dual expansions of d π x,γ r π
The derivations above focus on the primal expansion view. We show a parallel theory of dual expansion in Appendix B.

The equivalence of primal-dual view of Taylor expansions suggests connections with seemingly disparate lines of prior work: [START_REF] Janner | Gammamodels: Generative temporal difference learning for infinite-horizon prediction[END_REF] propose a density model for visitation distribution of different γ in the context of model-based RL. They show that predictions of large discount factors could be bootstrapped from predictions of small discount factors. This corresponds exactly to the dual space expansions, which is equivalent to the primal space expansions.

Extensions to Q-functions. In Appendix C, we show that it is possible to build approximations to Q π γ using Q π γ as building blocks. The theoretical guarantees and estimation procedures are similar to the case of value functions.

Approximation errors with finite samples

Proposition 3.2 shows that the expected approximation error decays as

V π K,γ,γ (x) -V π γ (x) = O γ -γ 1-γ K+1
for γ < γ < 1. This motivates using a high value of K when constructing the approximation. However, in practice, all constituent terms in the K th order expansion are random estimates, each with a non-zero variance. This might lead the variance of the overall estimate to increase as K increases. As a result, K mediates a trade-off between bias (expected approximation error) and variance. We formalize such intuitions in Appendix E, where we theoretically analyze the trade-off using the phased TD-learning framework [START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF].

A numerical example. The policy π(a|x) is uniformly random. We take γ = 0.2 and γ = 0.8. The agent generates N = 10 trajectories (x t , a t , r t ) T t=0 with a very large horizon T with a fixed starting state x 0 . We assume access to base estimates V π γ (x t ) and the Taylor expansion estimates V π K,γ,γ (x 0 ) are computed based on Algorithm 1. We estimate the relative error as

E K (x 0 ) = V π γ (x 0 ) -V π K,γ,γ (x 0 )
. For further experiment details, see Appendix F.

In Figure 1(a), we show how errors vary as a function of K. We study two settings: (1) Expected estimates (red), where V π K,γ,γ (x 0 ) is computed analytically through access to transition tables. In this case, similar to how the theory suggests, the error decays exponentially; (2) Sample-based estimates (blue) with base estimates V π γ (x t ) = ∞ s=0 γ s r t+s . The errors decay initially with K but later start to increase a bit as K gets large. The optimal K in the middle achieves the best bias-variance trade-off. Note that in this particular example, the estimates do not pay a very big price in variance for large K. We speculate this is because increments to the estimates are proportional to γ -γ 1-γ

K+1

, which scales down additional variance terms quickly as K increases.

In Figure 1(b), we study how the optimal expansion order K * depends on the noise level of base estimates. To emulate the noise, we assume access to base estimates V π γ (x t ) = V π γ (x t ) + N (0, σ 2 ) for some noise level σ. The optimal order K * is computed as K * = arg min k E k (x 0 ). In general, we observe that when σ increases, K * decreases. Intuitively, this implies that as the base estimates V π γ (x) become noisy, we should prefer smaller value of K to control the variance. This result bears some insights for practical applications such as downstream policy optimization, where we need to select an optimal K for the tasks at hand.

Taylor Expansions of Gradient Updates

In Section 3, we discussed how to construct approximations to V π γ (x). For the purpose of policy optimization, it is of direct interest to study approximations to ∇ θ V π θ γ (x). As stated in Section 1, a major premise of our work is that in many practical contexts, estimating discounted values under γ ≈ 1 is difficult. As a result, directly evaluating the full gradient ∇ θ V π θ γ (x) is challenging, because it requires estimating Q-functions Q π θ γ (x, a). Below, we start by showing how the decomposition of ∇ θ V π θ γ (x) motivates a particular form of gradient update, which is generally considered a deep RL heuristic. Then we construct approximations to this update based on Taylor expansions.

4.1. V π γ as a weighted mixture of V π γ
We can explicitly rewrite V π γ (x) as a weighted mixture of value functions V π γ (x ), x ∈ X . This result was alluded to in [START_REF] Romoff | Separating value functions across time-scales[END_REF] and formally shown below.

Lemma 4.1. Assume γ < γ < 1. We can write V π γ (x) = (ρ π x,γ,γ ) T V π γ , where the weight vector ρ π x,γ,γ ∈ R X is I -γ(P π ) T I -γ (P π ) T -1 δ x .
Also we can rewrite V π γ (x), using an expectation, as:

V π γ (x) + E π ∞ t=1 (γ -γ)(γ ) t-1 V π γ (x t ) x 0 = x . (16)
When γ = 1, ρ π x,γ,γ might be undefined. However, Eqn (16) still holds if assumptions A.1 and A.2 are satisfied. 4.2. Decomposing the full gradient ∇ θ V π θ γ (x) Lemma 4.1 highlights that V π γ (x) depends on π in two aspects: (1) the value functions V π γ (x ), x ∈ X ;

(2) the statedependent distribution ρ π x,γ,γ (x ). Let π θ be a parameterized policy. For conceptual clarity, we can write V π θ γ (x) = F (V π θ γ , ρ π θ x,γ,γ ) with a function F : R X × R X → R. Though this function is essentially the inner product, i.e., F (V, ρ) = V T ρ, notationally, it helps stress that V π θ γ (x) depends on θ through two vector arguments. Now, we can decompose ∇ θ V π θ γ (x).

Lemma 4.2. The full gradient ∇ θ V π θ γ (x) can be decomposed into the sum of two partial gradients as follows,

(∂ V F (V, ρ)) T ∇ θ V π θ γ + (∂ ρ F (V, ρ)) T ∇ θ ρ π θ x,γ,γ = E ∇ θ V π θ γ (x )
first partial gradient

+ E V π θ γ (x )∇ θ log ρ π θ x,γ,γ (x )
second partial gradient , where the above partial gradients are both evaluated at V = V π θ γ , ρ = ρ π θ x,γ,γ and both expectations are with respect to x ∼ ρ π θ

x,γ,γ .

We argue that the second partial gradient introduces most challenges in practical optimization. Intuitively, this is because its unbiased estimator is equivalent to a REINFORCE gradient estimator which requires estimating discounted values that accumulate V π γ (x ) as 'reward' under discount factor γ . By the premise of our work, this estimation would be difficult. We will detail the discussions in Appendix D.

The following result characterizes the first partial gradient.

Proposition 4.3. For any γ < γ < 1, the first partial gradient

(∂ V F (V π θ γ , ρ π θ x,γ,γ )) T ∇ θ V π θ γ can be expressed as E π θ ∞ t=0 (γ ) t Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x . (17)
When γ = 1, under assumptions A.1 and A.2, the first partial gradient exists and is expressed as

E π θ T t=0 Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x . ( 18
)
Connections to common deep RL heuristic. Many highquality deep RL algorithms (see, e.g. [START_REF] Dhariwal | OpenAI baselines[END_REF][START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF] implement parameter updates which are very similar to Eqn (18). As such, Proposition 4.3 provides some insights on why implementing such a heuristic might be useful in practice: though in general Eqn ( 18) is not a gradient [START_REF] Nota | Is the policy gradient a gradient[END_REF], it is a partial gradient of V π θ γ =1 (x), which is usually the objective of interest at evaluation time. Compared with the formula of vanilla PG in Eqn (2), Eqn (18) offsets the over-discounting by via a uniform average over states. However, it is worth noting that in deep RL practice, the definition of the evaluation horizon T might slightly differ from that specified in A.1. In such cases, Proposition 4.3 does not hold. By A.1, T is the absorption time that defines when the MDP enters a terminal absorbing state. In many applications, however, for MDPs without a natural terminatal state, T is usually enforced by an external time constraint which does not depend on states. In other words, an environment can terminate even when it does not enter any terminal state (see, e.g., [START_REF] Brockman | OpenAI gym[END_REF] for such examples). To bypass this subtle technical gap, one idea is to incorporate time steps as part of the state x ← [x, t]. This technique was hinted at in early work such as (Schulman et al., 2015b) and empirically studied in [START_REF] Pardo | Time limits in reinforcement learning[END_REF]. In this case, the random absorbing time T depends fully on the augmented states, and Proposition 4.3 holds.

Taylor expansions of partial gradients

We now consider approximations to the first partial gradients

∂ V F (V π θ γ , ρ π θ x,γ,γ ) T ∇ θ V π θ γ = (ρ π θ x,γ,γ ) T ∇ θ V π θ γ .
Since ∇ θ V π θ γ does not depend on γ , the approximation is effectively with respect to the weight vector ρ π θ

x,γ,γ . Below, we show results for the K th order approximation.

Proposition 4.4. Assume γ < γ < 1. For any x ∈ X , define the K th Taylor expansion to ρ π

x,γ,γ as

ρ π x,K,γ,γ = K k=0 (γ -γ) I -γ(P π ) T -1 (P π ) T k δ x .
It can be shown that

V π K,γ,γ (x) = (ρ π x,K,γ,γ ) T V π γ and ρ π x,K,γ,γ -ρ π K,γ,γ ∞ = O γ -γ 1-γ K+1 .
We build some intuitions about the approximations. Note that in general we can write the partial gradient as a weighted mixture of local gradients

Q t ∇ θ log π θ (a t |x t ) where Q t := Q π θ γ (x t , a t ), E π ∞ t=0 w K,γ,γ (t)Q t ∇ θ log π θ (a t |x t ) x 0 = x , (19)
for some weight function w K,γ,γ (t) ∈ R. When K → ∞, lim w K,γ,γ (t) = (γ ) t and we recover the original first partial gradient defined in Eqn (17); when K = 0, w K,γ,γ (t) = γ t recovers the vanilla PG in Eqn (2). For other values of K, we show the analytic weights w K,γ,γ (t) in Appendix D. Similar to how V π K,γ,γ interpolates V π γ and V π γ , here the K th order expansion to the partial gradients interpolate the full partial gradients and vanilla PG. In practice, we might expect an intermediate value of K achieve the best bias and variance trade-off of the update.

Policy optimization with Taylor expansions

Based on theoretical insights of previous sections, we propose two algorithmic changes to baseline algorithms. Based on Section 3, we propose Taylor expansion advantage estimation; based on Section 4, we propose Taylor expansion update weighting. It is important to note that other algorithmic changes are possible, which we leave to future work.

Baseline near on-policy algorithm

We briefly introduce backgrounds for near on-policy policy optimization algorithms (Schulman et al., 2015a;[START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF][START_REF] Schulman | Proximal policy optimization algorithms[END_REF][START_REF] Espeholt | Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures[END_REF]. We assume that the data are collected under a behavior policy (x t , a t , r t ) ∞ t=0 ∼ µ, which is close to the target policy π θ . The on-policyness is ensured by constraining D(π θ , µ) ≤ ε for some divergence D and threshold ε > 0. Usually, ε is chosen to be small such that little off-policy corrections are needed for estimating value functions. With data

(x t , a t , r t ) ∞ t=0 , the algorithms estimate Q-functions Q π θ γ ≈ Q π θ γ .
Then the estimates Q π θ γ (x, a) are used as plug-in alternatives to the Q-functions in the definition of gradient updates such as Eqn (2) for sample-based updates.

Taylor expansion Q-function estimation

In Section 3, we discussed how to construct approximations to Q π θ γ using Q π θ γ as building blocks. As the first first algorithmic change, we propose to construct the K th order expansion Q π θ K,γ,γ as a plug-in alternative to Q π θ γ when combined with downstream optimization. Since

Q π θ K,γ,γ ≈ Q π θ
γ , we expect the optimization subroutine to account for an objective of a longer effective horizon.

In many baseline algorithms, we have access to a value function critic V φ (x) and a subroutine which produces Q-function estimates

Q π θ γ (x, a) (e.g., Q π θ γ (x t , a t ) = ∞ s=0 γ s r t+s ). We then construct the K th order expan- sion Q π θ K,γ,γ (x, a) using Q π θ γ .
This procedure is similar to Algorithm 1 and we show the full algorithm in Appendix C. See also Appendix F for further experimental details.

Taylor expansion update weighting

In Section 4, we discussed Taylor expansions approximation ρ π θ

x,K,γ,γ to the weight vector ρ π θ x,γ,γ . As the second algorithmic change to the baseline algorithm, we update parameters in the direction of K th order approximations to the

partial gradient θ ← θ + α ρ π θ x,K,γ,γ T ∇ θ V π θ γ . Eqn (19)
shows that the update effectively translates into adjusting the weight w t = w K,γ,γ (t). When combined with other Algorithm 2 Taylor expansion Q-function estimation Require: policy π θ with parameter θ and α while not converged do

1. Collect partial trajectories (x t , a t , r t ) T t=1 ∼ µ. 2. Estimate Q-functions Q π θ γ (x t , a t ). 3. Construct K th order Taylor expansion estimator Q π θ K,γ,γ (x t , a t ) using Q π θ (x t , a t ). 4. Update the parameter via gradient ascent θ ← θ + α T t=1 Q π θ K,γ,γ (x t )∇ θ log π θ (a t |x t )
. end while components of the algorithm, the pseudocode is shown in Algorithm 3. Under this framework, the common deep RL heuristic could be recovered by setting w t = 1.

Algorithm 3 Taylor expansion update weighting Require: policy π θ with parameter θ and α while not converged do [START_REF] Jiang | On structural properties of MDPs that bound loss due to shallow planning[END_REF], potentially due to increased complexities of the optimal value functions or collapses of the action gaps [START_REF] Lehnert | On value function representation of long horizon problems[END_REF][START_REF] Laroche | In reinforcement learning, all objective functions are not equal[END_REF]. However, optimal policies defined with small discounts can be very sub-optimal for RL objectives with a large discount factor. To entail numerical stability of using large discounts, prior work has suggested nonlinear transformation of the Bellman targets for Q-learning [START_REF] Pohlen | Observe and look further: Achieving consistent performance on atari[END_REF]van Hasselt et al., 2019;[START_REF] Kapturowski | Recurrent experience replay in distributed reinforcement learning[END_REF]Van Seijen et al., 2019). However, when data is scarce, small discount factors might prove useful due to its implicit regularization effect [START_REF] Amit | Discount factor as a regularizer in reinforcement learning[END_REF].

1. Collect partial trajectories (x t , a t , r t ) T t=1 ∼ µ. 2. Estimate Q-functions Q t = Q π θ γ (x t ,
As such, there is a trade-off mediated by choosing different values of discount factors. Similar trade-off effects are most well-known in the context of TD(λ), where λ ∈ [0, 1] trades-off the bias and variance of the TD updates (Sutton and Barto, 2018;[START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF].

Adapting discount factors & multiple discount factors.

In general, when selecting a single optimal discount factor for training is difficult, it might be desirable to adjust the discount during training. This could be achieved by human-designed [START_REF] Danil | Adaptive critic designs[END_REF][START_REF] Franc ¸ois-Lavet | How to discount deep reinforcement learning: Towards new dynamic strategies[END_REF] or blackbox adaptation (Xu et al., 2018). Alternatively, it might also be beneficial to learn with multiple discount factors at the same time, which could improve TDlearning (Sutton, 1995) or representation learning [START_REF] Fedus | Hyperbolic discounting and learning over multiple horizons[END_REF]. Complementary to all such work, we study the connections between value functions defined with different discounts.

Taylor expansions for RL. Recently in (Tang et al., 2020), Taylor expansions were applied to study the relationship between V π γ and V µ γ , i.e., value functions under the same discount factor but different policies π = µ. This is useful in the context of off-policy learning. Our work is orthogonal and could be potentially combined with this approach.

Experiments

In this section, we evaluate the empirical performance of new algorithmic changes to the baseline algorithms. We focus on robotics control experiments with continuous state and action space. The tasks are available in OpenAI gym [START_REF] Brockman | OpenAI gym[END_REF], with backends such as MuJoCo (Todorov et al., 2012) and bullet physics [START_REF] Coumans | Bullet physics simulation[END_REF]. We label the tasks as gym (G) and bullet (B) respectively. We always compare the undiscounted cumulative rewards evaluated under a default evaluation horizon T = 1000.

Hyper-parameters. Throughout the experiments, we use the same hyper-parameters across all algorithms. The learning rate is tuned for the baseline PPO, and fixed across all algorithms. See Appendix F for further details.

Taylor expansion Q-function estimation

We use Q π θ K,γ,γ (x, a) with K = 1 as the Q-function estimator plug-in for the gradient update. When combining with PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF], the resulting algorithm is named PPO(K). We compare with the baseline PPO and TRPO (Schulman et al., 2015a). In practice, we consider a mixture of advantage estimator

Q π θ (x, a) = (1 -η) Q π θ γ (x, a) + η Q π θ K,γ,γ (x, a)
with η ∈ [0, 1] a constant that interpolates between the PPO (i.e., η = 0) and PPO(K). Note that though η should be selected such that it balances the numerical scales of the two extremes, as a result, we usually find η to work well when it is small in absolute scale (η = 0.01 works the best).

Results. In Figure 2, we compare a few baselines: (1) PPO with γ = 0.99 (default); (2) PPO with high discount factor γ = 1 -1 T = 0.999; (3) PPO with Taylor expansion based advantage estimator, PPO(K). Throughout, we use a single hyper-parameter η = 0.01. We see that in general, PPO(K) leads to better performance (faster learning speed, better asymptotic performance or smaller variance across 5 seeds). This shows Taylor expansion Q-function estimation could lead to performance gains across tasks, given that the hyper-parameter η is carefully tuned. We provide a detailed ablation study on η in Appendix F, where we show how the overall performance across the benchmark tasks vary as η changes from small to large values.

A second observation is that simply increasing the discount factor to γ = 1 -1 T = 0.999 generally degrades the performance. This confirms issue with instability of directly applying high discount factors which motivates this work.

We also compare with the open source implementation of [START_REF] Romoff | Separating value functions across time-scales[END_REF] in Appendix F, where they estimate Q π γ based on recursive bootstraps of Q-function differences. Conceptually, this is similar to Taylor expansions with K = ∞. We show that without a careful trade-off mediated by smaller K, this algorithm does not improve performance out of the box.

Taylor expansion update weighting

As introduced in Section 5, we weigh local gradients Q t ∇ θ log π θ (a t |x t ) with K th order expansion weights w K,γ,γ (t). Here, we take γ = 1 -1 T . Note that since K = ∞ corresponds to lim w K,γ,γ (t) = (γ ) t ≈ 1, this is very close to the commonly implemented PPO baseline. We hence expect the algorithm to work better with relatively large values of K and set K = 100 throughout experiments. In practice, we find the performance to be fairly robust in the choice of K. We provide further analysis and ablation study in Appendix F.

Results. We compare a few baselines: (1) default PPO;

(2) PPO with time limit [START_REF] Pardo | Time limits in reinforcement learning[END_REF]. In this case, the states are augmented with time steps x ← [x, t] such that the augmented states x are Markovian; (3) PPO with Taylor expansion update weighting PPO(K). In Figure 3, we see that in general, PPO(K) and PPO with time limit outperform the baseline PPO. We speculate that the performance gains arise from the following empirical motivation: since the evaluation stops at t = T , local gradients close to t = T should be weighed down because they do not contribute as much to the final objective. However, the default PPO ignores such an effect and weighs all updates uniformly. To tackle this issue, PPO(K) explicitly weighs down the update while and PPO with time limit augments the state space to restore stationarity. Empirically, though in some cases PPO with time limit also outperforms PPO(K), it behaves fairly unstably in other cases.

Extensions to off-policy algorithms. Above, we mainly focused on on-policy algorithms. The setup is simpler because the data are collected (near) on-policy. It is possible to extend similar results to off-policy algorithms [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF][START_REF] Timothy P Lillicrap | Continuous control with deep reinforcement learning[END_REF][START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF][START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF]. Due to the space limit, we present extended results in Appendix F, where we show how to combine similar techniques to off-policy actor-critic algorithms such as TD3 [START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF] and SAC [START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF] in continuous control domains.

Conclusion

We have proposed a family of objectives that interpolate value functions defined with two discount factors. We have shown that similar techniques are applicable to other cumulative quantities defined through discounts, such as PG updates. This framework allowed us to achieve trade-off in estimating value functions or gradient updates, and led to empirical performance gains.

We also highlighted a new direction for bridging the gap between theory and practice: the gap between a fully discounted objective (in theory) and an undiscounted objective (in practice). By building a better understanding of this gap, we shed light on seemingly opaque heuristics which are necessary to achieve good empirical performance. We expect this framework to be useful for new practical algorithms. Lemma A.1. The matrix (I -P ) π is invertible and its inverse is

(I -P ) π = ∞ k=0 ( P ) k .
Proof. Define a matrix N = ∞ k=0 ( P π ) k , then N [x, y] defines the expected number of times it takes to transition from x to y before absorption. By definition of the absorbing chain, N is finite. This further shows that (I -P π ) is invertible, because

N (I -P π ) = (I -P π )N = I.
Lemma A.2. Let f (A, B) be a matrix polynomial function of matrix A and B. Then

f P π , (I -γP π ) -1 =   f P π , I -γ P π -1 B 0 1   ,
where B is some matrix.

Proof. The intuition for the above result is that polynomial transformation preserves the block triangle property of P π and (I -γP π ) -1 . In general, we can assume

f (A, B) = m,n≤K c m,n A m B n ,
for some K ≥ 0 and c m,n ∈ R are scalar coefficients. First, note that (P π ) k , k ≥ 0 is of the form

(P π ) k = P π k C 0 1 , for some matrix C. Since (I -γA) -1 = ∞ k=0 A k for A ∈ {P π , P π }, this implies that (I -γP π ) -1 = ∞ k=0 (γP π ) k = P π k D 0 1 = I -γ P π -1 D 0 1
, for some matrix D. The above two results show that both polynomials of P π and (I -γP π ) -1 are block upper triangle matrices. It is then straightforward that

(P π ) m (I -γP π ) -1 n =   P π m I -γ P π -1 n E 0 1   ,
for some matrix E. Finally, since f (P π , (I -γP π ) -1 ) is a linear combination of (P π ) m (I -γP π )

-1 n

, we conclude the proof.

Lemma A.3. Under assumption (1) and (2), one could write the value function V π γ =1 as

V π γ =1 = ∞ k=0 (P π ) t r π ,
where the infinite series on the RHS converges. In addition, for any transient state

x, V π γ =1 (x) = ∞ k=0 ( P π ) k r π (x). Proof. Recall that V π γ (x) := E [ ∞ t=0 r t | x 0 = x].
Under assumption (2), for any absorbing state x, V π γ (x) = 0 = ∞ k=0 (P π ) k r π (x). We can instead constrain the Markov chain to the transient states. For any transient state x, recall the definition of N from Lemma A.1, it follows that

V π γ =1 (x) = y N (expected number of times in y|x 0 = x)r π (y) = [N r π ] (x) = I -P π -1 r π (x) = ∞ k=0 ( P π ) k r π (x).
By Lemma A.2, this is equivalent to [ ∞ k=0 (P π ) t r π ] (x). We thus complete the proof.

Lemma A.4. The following holds for any γ < 1,

I -P π -1 = I -γ P π -(1 -γ) P π -1 = K k=0 (1 -γ) I -γ P π -1 P π k I -γ P π -1 + (1 -γ) I -γ P π -1 P π K+1 I -P π -1 = ∞ k=0 (1 -γ) I -γ P π -1 P π k I -γ P π -1 . ( 20
)
Proof. The first two lines derive from a straightforward application of Woodbury matrix identity to (I -P π ) -1 . This is valid because by Lemma A.1, (I -P π ) is invertible. The convergence of the infinite series is guaranteed for all γ < 1. To see why, recall that the finiteness of N = ∞ k=0 ( P π ) k implies ( P π ) K+1 → 0. We can bound the residual,

(1 -γ) I -γ P π -1 P π K+1 I -P π -1 ∞ ≤ ( P π ) K+1 I -P π -1 ∞ → 0.
Finally, we combine results from the above to prove the main claim. First, consider the absorbing state x. Due to Assumption (2), V π γ (x) = 0 for any γ ∈ [0, 1]. The matrix equalities in Proposition 3.2 holds in this case. In the following, we consider any transient states x. By Lemma A.3 and Lemma A.4

V π γ =1 (x) = ∞ k=0 ( P π ) k r π (x) = K k=0 (1 -γ) I -γ P π -1 P π k I -γ P π -1 r π + (1 -γ) I -γ P π -1 P π K+1 I -P π -1 r π (x)
Now, notice that because the last entries of r π , V π γ , V π γ =1 are zero (for the absorbing state),

I -γ P π -1 r π (x) = (I -γP π ) -1 r π (x).
Combining with Lemma A.2,

V π γ =1 (x) = K k=0 (1 -γ) (I -γP π ) -1 P π k (I -γP π ) -1 r π + (1 -γ) (I -γP π ) -1 P π K+1 V π γ =1 (x) =       K k=0 (1 -γ) (I -γP π ) -1 P π k V π γ K-th order expansion + (1 -γ) (I -γP π ) -1 P π K+1 V π γ =1 residual       (x).
The residual term → 0 as K → 0 with similar arguments used for Lemma A.4. We hence conclude the proof.

Proposition 3.2. The following bound holds for all K ≥ 0,

V π γ (x) -V π K,γ,γ (x) ≤ γ -γ 1 -γ K+1 R max 1 -γ . ( 12
)
Proof. The proof follows directly from the residual term in Proposition 3.1. Recall that the residual term takes the form

V π γ -V π K,γ,γ = (γ -γ)(I -γP π ) -1 P π K+1 V π γ .
Its infinity norm can be bounded as

( γ -γ 1-γ ) K+1 Rmax 1-γ Lemma 4.1. Assume γ < γ < 1. We can write V π γ (x) = (ρ π x,γ,γ ) T V π γ
, where the weight vector ρ π x,γ,γ ∈ R X is

I -γ(P π ) T I -γ (P π ) T -1 δ x .
Also we can rewrite V π γ (x), using an expectation, as:

V π γ (x) + E π ∞ t=1 (γ -γ)(γ ) t-1 V π γ (x t ) x 0 = x . (16)
When γ = 1, ρ π x,γ,γ might be undefined. However, Eqn ( 16) still holds if assumptions A.1 and A.2 are satisfied.

Proof. We will derive the above result with the matrix form. Recall by applying Woodbury inversion identity to (Iγ P π ) -1 = (I -(γ -γ)P π -γP π ) -1 , we get

(I -γ P π ) -1 = ∞ k=0 (γ -γ)(I -γP π ) -1 P π k (I -γP π ) -1 = (I -γP π ) -1 + ∞ k=1 (γ -γ)(I -γP π ) -1 P π k (I -γP π ) -1 = (I -γP π ) -1 + (γ -γ) ∞ k=1 (γ -γ)(I -γP π ) -1 P π k • (I -γP π ) -1 • P π (I -γP π ) -1 = (I -γP π ) -1 + (γ -γ)(I -γ P π ) -1 • P π • (I -γP π ) -1 .
Then, right multiply the above equation by r π ,

V π γ = V π γ + (γ -γ)(I -γ P π ) -1 P π V π γ = V π γ + (γ -γ) ∞ t=1 (γ ) t-1 (P π ) t V π γ .
By indexing both sides at state x, we recover the following equality,

V π γ (x) = V π γ (x) + E π ∞ t=1 (γ -γ)(γ ) t-1 V π γ (x t ) x 0 = x .
To derive the expression for ρ π x,γ,γ , note that also

V π γ = (I -γ P π ) -1 r π = (I -γP π )(I -γ P π ) -1 (I -γP π ) -1 r π = (I -γP π )(I -γ P π ) -1 weight matrixW V π γ ,
where we use the fact that (I -γP π ) commutes with (I -γ P π ) -1 . Since we define ρ π x,γ,γ as such that V π γ (x) = ρ π x,γ,γ T V π γ , we can derive the matrix form of ρ π x,γ,γ by indexing the x-th row of weight matrix W . This directly leads to the desired result

ρ π x,γ,γ = I -γ(P π ) T I -γ (P π ) T -1 δ x .
Proposition 4.3. For any γ < γ < 1, the first partial gradient

(∂ V F (V π θ γ , ρ π θ x,γ,γ )) T ∇ θ V π θ γ can be expressed as E π θ ∞ t=0 (γ ) t Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x . (17)
When γ = 1, under assumptions A.1 and A.2, the first partial gradient exists and is expressed as

E π θ T t=0 Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x . (18)
Proof. First we assume γ < 1, we will consider the extension to γ = 1 at the end of the proof. Recall that the policy gradient takes the following form,

∇ θ V π θ γ (x) = E π θ ∞ t=0 γ t Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x.
We plug in the above, the partial derivative

∂ V F (V π θ γ , ρ π θ x,γ,γ ) T ∇ θ V π θ γ evaluates to the following ∇ θ V π θ γ (x) + E π θ (γ -γ) ∞ t=1 (γ ) t-1 ∇ θ V π θ γ (x t ) = E π θ ∞ t=0 γ t Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x + E π θ (γ -γ)(γ ) t-1 ∞ t=1 ∞ s=0 γ s Q π θ γ (x t+s , a t+s )∇ θ log π θ (a t+s |x t+s ) x 0 = x = E π θ      ∞ t=0      γ t + t u=1 (γ -γ)(γ ) u-1 γ t-u coefficient at time t      Q π θ γ (x t , a t )∇ θ log π θ (a t |x t ) x 0 = x.     
In the above, the coefficient term at time t can be calculated by carefully grouping terms across different time steps. It can be shown that the coefficient term evaluates to (γ ) t for all t ≥ 0. This concludes the proof.

Alternative proof based on matrix notations. We introduce an alternative proof based on matrix notations as it will make the extension to γ = 1 simpler. First, note that

V π γ = (I -γ P π ) -1 r π = (I -γ P π ) -1 (I -γP π ) (I -γP π ) -1 r π = (I -γP π ) (I -γ P π ) -1 (I -γP π ) -1 r π ,
where for the second equality we exploit the fact that (I -γP π ) commutes with (I -γ P π ) -1 . Now, notice that the above rewrites as

V π γ = (I -γP π ) (I -γ P π ) -1 W γ,γ V π γ
where W γ,γ is the weight matrix. This matrix is equivalent to the weighting distribution ρ π x,γ,γ by W γ,γ [x] = ρ π

x,γ,γ

where A[x] is the x-th row of matrix A. The first partial gradient corresponds to differentiating V π θ γ only through V π θ γ . To make the derivation clear in matrix notations, let θ i be the i-th component of the parameter θ.

Define ∇ θi V π θ γ ∈ R X such that ∇ θi V π θ γ (x) = ∇ θi V π θ γ (x)
, This means the i-th component of the first partial gradient across all states is

W γ,γ ∇ θi V π θ γ ∈ R X .
Let G θi γ ∈ R X to be the vector of local gradient (for parameter θ i ) such that G θi γ (x) = a ∇ θi π θ (a|x)Q π θ γ (x, a). Vanilla PG (Sutton et al., 2000) can be expressed as

∇ θi V π θ γ = (I -γP π ) -1 G θi γ .
We can finally derive the following,

W γ,γ ∇ θi V π θ γ = (I -γP π )(I -γ P π ) -1 G θi γ = (I -γP π )(I -γ P π ) -1 (I -γP π ) -1 G θi γ = (I -γP π )(I -γP π ) -1 (I -γ P π ) -1 G θi γ = (I -γ P π ) -1 G θi γ
Now, consider the x-th component of the above vector. We have

∇ θ [J(π θ , π t )] πt=π θ is equal to E π θ ∞ t=0 (γ ) t a ∇ θi π θ (a|x t )Q π θ γ (x t , a) x 0 = x = E π θ ∞ t=0 (γ ) t ∇ θi log π θ (a t |x t )Q π θ γ (x t , a) x 0 = x
When concatenating the gradient for all component θ i i of θ, we conclude the proof.

Extensions to the case γ = 1. Similar to the arguments made in the proof of Proposition 3.2, under assumptions A.1 and A.2, we can decompose the transition matrix P π as

P π = P p 0 1 ,
where the last state is assumed to be absorbing. Though (I -γ P π ) -1 for γ = 1 is in general not necessarily invertible, the matrix (I -P ) -1 is invertible. Since r π (x) for the absorbing state x, we have deduced that Q π γ (x.a) = V π γ (x) = 0, and accordingly G θi γ (x) = 0. As such, though (I -γ P π ) -1 for γ = 1 might be undefined, the multiplication (I -γ P π ) -1 G θi γ is defined, with the last entry being 0. Since at time t = T , the chain enters the absorbing states, all local gradient terms that come after T are zero. As a result, the x-th component of (I

-γ P π ) -1 G θi γ is E π θ T t=0 (γ ) t ∇ θi log π θ (a t |x t )Q π θ γ (x t , a) x 0 = x
Proposition 4.4. Assume γ < γ < 1. For any x ∈ X , define the K th Taylor expansion to ρ π x,γ,γ as

ρ π x,K,γ,γ = K k=0 (γ -γ) I -γ(P π ) T -1 (P π ) T k δ x .
It can be shown that

V π K,γ,γ (x) = (ρ π x,K,γ,γ ) T V π γ and ρ π x,K,γ,γ -ρ π K,γ,γ ∞ = O γ -γ 1-γ K+1 .
Proof. Recall from Lemma 4.1, by construction,

ρ π x,γ,γ = I -γ (P π ) T -1 I -γ(P π ) T δ x .
Simialr to the case of primal space expansions in Section 3.1, we construct the K th order expansion to ρ π x,γ,γ via the expansion of the matrix I -γ(P π ) T -1 . Recall that

I -γ (P π ) T -1 = ∞ k=0 (γ -γ)(P π ) T I -γ(P π ) T -1 k I -γ(P π ) T -1 .
When truncating the infinite series to the first K + 1 terms, we derive the K th order expansion ρ π x,K,γ,γ ,

(γ -γ)(P π ) T I -γ(P π ) T -1 k I -γ(P π ) T -1 I -γ(P π ) T δ x = K k=0 (γ -γ)(P π ) T I -γ(P π ) T -1 k δ x .
Note that since

∞ k=K+1 (γ -γ)(P π ) T I -γ(P π ) T -1 k I -γ(P π ) T -1 ∞ ≤ γ -γ 1 -γ K+1 1 1 -γ .
This concludes the proof.

B. Further results on Taylor expansions in the dual space

The dual representation of value function

V π γ (x) in Eqn (6) is V π γ (x) = (1 -γ ) -1 (r π ) T d π
x,γ where r π , d π x,γ ∈ R X are vector rewards and visitation distribution starting at state x. Here, we abuse the notation d π

x,γ to denote both a function and a vector, i.e., d π

x,γ (x ) can be interpreted as both a function evaluation and a vector indexing. Given such a dual representation, one natural question is whether the K th expansion in the primal space corresponds to some approximations of the discounted visitation distribution d π K,γ,γ ≈ d π x,γ . Below, we answer in the affirmative.

Let δ x ∈ R X be the one-hot distribution such that [δ x ] x = 1 only when x = x. The visitation distribution satisfies the following balance equation in matrix form

d π x,γ = (1 -γ )δ x + γ (P π ) T d π x,γ . ( 21
)
Inverting the equation, we obtain an explicit expression for the visitation distribution d π x,γ = (1 -γ )(I -γ P π ) -1 δ x . Following techniques used in the derivation of Propo 3.1, we can derive similar approximation results for dual variables. See Appendix B.

Proposition B.1. The following holds for all K ≥ 0,

d π x,γ = 1 -γ 1 -γ K k=0 (γ -γ) I -γ(P π ) T -1 (P π ) T k d π x,γ . + (γ -γ) I -γ(P π ) T -1 (P π ) T K+1 d π x,γ residual . ( 22
)
When γ < γ < 1, the residual norm → 0, which implies that the following holds

d π x,γ = 1 -γ 1 -γ ∞ k=0 ((γ -γ) I -γ(P π ) T -1 (P π ) T ) k d π x,γ . (23)
Proof. Starting from the fixed point equation satisfied by d π γ , we can apply Woodbury inversion indentity

d π γ = (1 -γ ) I -γ (P π ) T -1 δ x = (1 -γ ) K k=0 (γ -γ)(I -γP π ) -1 (P π ) T k δ x + (1 -γ ) (γ -γ) I -γ(P π ) T -1 (P π ) T K I -γ (P π ) T -1 δ x = 1 -γ 1 -γ K k=0 (γ -γ) (I -γ(P π )) -1 P π k d π γ + (1 -γ ) (γ -γ)(I -γP π ) -1 (P π ) T K d π γ
The norm of the residual term could be bounded as

(1 -γ ) (γ -γ)(I -γP π ) -1 P π K d π γ ∞ ≤ (1 -γ ) γ -γ 1 -γ K+1 → 0.
With a similar motivation as expansions in the primal space, we define the K th order expansion by truncating to first K + 1 terms,

d π x,K,γ,γ := 1 -γ 1 -γ K k=0 ((γ -γ)(I -γP π ) -1 P π ) k d π x,γ (24)
The following result formalizes the connection between the K th order dual approximation to the visitation distribution d π K,γ,γ and the primal approximation to the value function at state x, V π K,γ,γ (x).

Proposition B.2. The K th order primal and dual approximations are related by the following equality for any K ≥ 0,

V π K,γ,γ (x) = (1 -γ ) -1 d π x,K,γ,γ T r π (25)
Proof. The proof follows by expanding out the RHS of the equation. Recall the definition of d π K,γ,γ ,

(d π K,γ,γ ) T = 1 -γ 1 -γ K k=0 (d π γ ) T (γ -γ) (I -γP π ) -1 k = (1 -γ ) K k=0 δ T x (I -γP π ) -1 (γ -γ) (I -γP π ) -1 k = (1 -γ )δ T x K k=0 (γ -γ)(I -γP π ) -1 P π k • (I -γP π ) -1 .
Now multiply the RHS by r π and recall that V π γ = (I -γP π ) -1 r π , we conclude the proof,

RHS = 1 -γ 1 -γ δ T x K k=0 (γ -γ)(I -γP π ) -1 P π k V π γ = (1 -γ )δ T x V π K,γ,γ = (1 -γ )V π K,γ,γ (x).
Proposition B.2 shows that indeed, the K th order approximation of the value function is equivalent to the K th order approximation of the visitation distribution in the dual space. It is instructive to consider the special case K = 1.

C. Details on Taylor expansion Q-function advantage estimation

Proposition C.1. Let Q π γ ∈ R X ×A be the vector advantage functions. Let P π ∈ R (X ×A)×(X ×A) be the transition matrix such that P π (x, a, x , a ) = π(x |x )p(x |x, a). Define the K th order Taylor expansion of advantage as

Q π K,γ,γ := K k=0 ((γ -γ)(I -γP π ) -1 P π ) k Q π γ . Then lim K→∞ Q π K,γ,γ = Q π γ for any γ < γ < 1.
Algorithm 4 Estimating the K th term of the expansion (Q-function) Require: A trajectory (x t , a t , r t ) ∞ t=0 ∼ π and discount factors γ < γ < 1 1. Compute advantage function estimates Q π γ (x t , a t ) for states on the trajectory. For example, Q π γ (x t , a t ) = t ≥t γ t -t r t . One could also apply other alternatives (e.g., (Schulman et al., 2015b)) which potentiall reduce the variance of Q π γ (x t , a t ).

Sample

K random time τ i , 1 ≤ i ≤ K, all i.i.d. geometrically distributed τ i ∼ Geometric(1 -γ). 3. Return (γ -γ) K (1-γ) K Q π γ (x τ , a τ ), where τ = K i=1 τ i .
Proof. The proof follows closely that of Taylor expansion based approximation to value functions in Proposition 3.2. Importantly, notice that here we define P π , which differs from P π used in the derivation of value functions. In particular, P π (x, a, y, b) = p(y|x, a)π(b|y) for any x, y ∈ X , a, b ∈ A. Let r be the vector reward function. The Bellmen equation for Q-function is

Q π γ = r + γ P π Q π γ .
Inverting the equation and applying the Woodbury inversion identity,

Q π γ = (I -γ P π ) -1 r = ∞ k=0 (γ -γ) I -γP π -1 P π k Q π γ
The above equality holds for all γ < γ < 1 due to similar convergence argument as in Proposition 3.2. Truncating the infinite series at step K, we arrive at the K th order expansion

Q π K,γ,γ . By construction, lim K→∞ Q π K,γ,γ = Q π γ .

D. Details on Taylor expansion update weighting

Proposition D.1. The following is true for all K ≥ 0,

ρ x,K,γ,γ (x ) = I[x = x] + E π ∞ t=1 f (K, t, γ, γ )I[x t = x ] x 0 = x ,
Equivalently, the K th order Taylor expansion of

V π γ (x) is V π K,γ,γ (x) = V γ (x) + E π ∞ t=1 f (K, t, γ, γ )V π γ (x t ) x 0 = x , (26)
where

f (K, t, γ, γ ) = min(K,t) u=1 (γ -γ) u γ t-u t-1 t-u is a weight function.
Proof. We start with a few lemmas.

Lemma D.2. For any n ≥ 0, k ≥ 1, define a set of k-dimensional vector x 1 , ...x k |x i ∈ Z ≥0 , k i=1 x i = n and let F (n, k) be the size of this set. Then

F (n, k) = n + k -1 k -1 .
Proof. By construction, the above set can be decomposed into smaller sets by fixing the value of x k , i.e.,

x 1 , ...x k |x i ∈ Z ≥0 , k i=1 x i = n = ∪ n s=0 x 1 , ...x k-1 , x k |x i ∈ Z ≥0 , k i=1 x i = n, x k = s
Since these sets do not overlap, we have a recursive formula,

F (n, k) = n s=0 F (n -s, k -1).
Starting from the base case F (n, 1) = 1, ∀n ≥ 0, it is straightforward to prove by induction that for all n ≥ 0, k ≥ 1

F (n, k) = n + k -1 k -1 . Lemma D.3. Consider V π K+1,γ,γ -V π K,γ,γ for K ≥ 0. It can be shown that V π K+1,γ,γ -V π K,γ,γ = (γ -γ) K+1 ∞ t=0 F (t, K + 1) (P π ) t (P π ) K+1 V π γ .
Proof. Starting with the definition,

V π K+1,γ,γ -V π K,γ,γ = (γ -γ) (I -γP π ) -1 P π K+1 V π γ = (γ -γ) (I -γP π ) -1 K+1 (P π ) K+1 V π γ ,
where for the second equality we use the fact that P π commutes with (I -γP π ) -1 . Then consider (I -γP π ) -1 K+1 ,

(I -γP π ) -1 K+1 = ∞ t=0 (γP π ) t K+1 = s1≥0 ... s K+1 ≥0 (γP π ) K+1 i=1 si = ∞ s=0 F (s, K + 1) (γP π ) s .
Note that the last equality corresponds to a regrouping of terms in the infinite summation -instead of summing over s 1 , ...s K+1 sequentially, we count the number of examples such that K+1 i=1 s i = s and then sum over s. This count is exactly F (s, K + 1) as defined in Lemma D.2. Hence the proof is completed.

With the above lemmas, we are ready to prove the final result. We start by summing up all the differences of expansions,

V π K,γ,γ = V π 0,γ,γ + K-1 k=0 V π k+1,γ,γ -V π k,γ,γ = V π γ + K-1 k=0 (γ -γ) k+1 ∞ t=0 F (t, k + 1) (γP π ) t (P π ) k+1 V π γ = V π γ + ∞ t=0 K-1 k=0 (γ -γ) k+1 γ -k-1 F (t, k + 1) (γP π ) t+k+1 V π γ = V π γ + ∞ t=0 K u=1 (γ -γ) u γ -u F (t, u) (γP π ) t+u V π γ = V π γ + ∞ s=0 K u=1 (γ -γ) u γ -u F (s -u, u) (γP π ) s V π γ = V π γ + ∞ s=1 K u=1 (γ -γ) u γ -u F (s -u, u) (γP π ) s V π γ = V π γ + ∞ s=1 K u=1 (γ -γ) u γ s-u s -1 u -1 (P π ) s V π γ = V π γ + ∞ s=1 min(K,s) u=1 (γ -γ) u γ s-u s -1 u -1 (P π ) s V π γ
In the above derivation, we have applied the transformation u = k + 1, s = t + u. Then we have modified the bound of the summation with the definition of F (s -u, u) (in particular, if s < u, F (s -u, u) = 0). If we index the x-th component of the vector, we recover the desired result.

D.1. Further discussions on the objectives

Recall that the full gradient

∇ θ V π θ γ (x) is ∇ θ V π θ γ (x) = E x ∼ρ π θ γ,γ (•;x) ∇ θ V π θ γ (x ) + E x ∼ρ π θ γ,γ (•;x) V π θ γ (x )∇ θ log ρ π θ γ,γ (x ; x).

second term

Proof. Recall the results from [START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF]:

Let ∆ γ t := max x∈X |V π γ (x) -V π γ (x)|.
Then with probability at least 1 -δ, the following holds

∆ γ t ≤ A(γ, δ) + B(γ)∆ γ t-1 .
In the following, we condition all analysis on the event set that the above inequality holds. Now, using V π γ (x) as a subroutine, define the estimator for the K th Taylor expansion as in Eqn (28),

V K,γ (x 0 ) = K k=0 1 n n i=1 (γ -γ) k V π γ (x i,k ). Define the error ∆ γ K,t := max x∈X |V π γ (x) -V π K,γ (x)|
, which is measured against the value function V π γ (x) with a higher discount factor γ . Consider for a given starting state x 0 ,

|V π γ (x 0 ) -V π K,γ (x 0 )| = V π γ (x 0 ) -V π K,γ (x 0 ) + V π K,γ (x 0 ) -V π K,γ (x) ≤ |V π γ (x 0 ) -V π K,γ (x 0 )| + V π K,γ (x 0 ) -V π K,γ (x 0 ) ≤ E(γ, γ , K) + V π K,γ (x 0 ) -E V π K,γ (x 0 ) second term + E V π K,γ (x 0 ) -V π K,γ (x 0 ) third term
. Now, we bound each term in the equation above. Recall

ε := K k=0 (γ -γ) k = 1-(γ -γ) K+1 1-γ +γ
. The second term is bounded as follows

V π K,γ (x 0 ) -E V π K,γ (x 0 ) ≤ ε∆ γ t .
The third term is bounded by applying concentration bounds. Recall that the estimator

V π K,γ (x 0 ) := K k=0 1 n n i=1 (γ - γ) k V π γ (x i,k
) decomposes into K + 1 estimators, each being an average over n i.i.d. samples drawn from the K th step visitation distribution

(P π • d π γ ) k , 0 ≤ k ≤ K.
Applying similarly naive techniques in [START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF], we bound each of the K + 1 terms individually and then take a union bound over all K + 1 terms. This implies that, with probability at least 1 -δ, the following holds

E V π K,γ (x 0 ) -V π K,γ (x 0 ) ≤ εU = ε 2 log 2(K + 1) δ /n.
Aggregating all results, we have

|V π γ (x 0 ) -V π K,γ (x 0 )| ≤ E(γ, γ , K) + ε∆ γ t + εU ≤ ε(A(γ, δ) + U ) + E(γ, γ , K) + εB(γ)∆ γ t-1 .
This holds with probability at least (1 -δ) 2 ≥ 1 -2δ.

Bias-variance trade-off via K. The error terms come from two parts: the first term contains errors A(γ, δ) in the subroutine estimator V π γ (x), and its propagated errors through the sampling of K th order approximations for 1 ≤ k ≤ K (shown via the multiplier ε). This first term also contains U , a concentration bound that scales with O( √ log K), which shows that the variance of the overall estimator grows with K. This first error term scales with √ n and vanishes as the number of samples increases. The second term is due to the gap between the expected K th order Taylor expansion and V π γ (x 0 ), which decreases with K and does not depend on sample size n. The new contraction coefficient is εB(γ), where it can be shown that ε ∈ [1, 1 1-γ +γ ]. Since typical estimators have B(γ) ≤ γ, in general εB(γ) < 1 and the error contracts with respect to ∆ t . In general, the contraction becomes slower as K increases. For example, for TD(λ), B(γ) = (1-λ)γ 1-γλ .

F. Further experiment details

Below, we provide further details on experiment setups along with additional results.

F.1. Further details on the toy example We presented a toy example that highlighted the trade-off between bias and variance, mediated by the order parameter K.

Here, we provide further details of the experiments.

Toy MDP. We consider tabular MDPs with |X | = 10 states and |A| = 2 actions. The transition table p(y|x, a) is drawn from a Dirichlet distribution (α, . . . , α) for α = 0.01. Here, α is chosen such that the MDP is not very communicative (i.e., the distribution p(•|x, a) concentrates only on a few states). The rewards are random r(x, a) = r(x, a)(1 + ε) where ε ∼ N (0, 0.22 ) and mean rewards r(x, a) are drawn from Uniform(0, 1) and fixed for the problem.

F.2. Deep RL algorithms

Proximal policy optimization (PPO). PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] implements a stochastic actor π θ (a|x) as a Gaussian distribution a ∼ N (µ θ (x), σ 2 I) with state-conditional mean µ θ (x) and a global standard deviation σ 2 I; and a value function

V φ (x).
The behavior policy µ is the previous policy iterate. The policy is updated as

A µ γ (x, a)∇ θ clip( π θ (a|x) µ(a|x) , 1 -ε, 1 + ε) with ε = 0.2 2 .
The advantages A µ γ (x, a) estimated using generalized advantage estimation (GAE, (Schulman et al., 2015b)) with γ = 0.99, λ = 0.95. Value functions are trained by minimizing (V φ (x)-R(x)) 2 with returns R(x) = V φ (x)+ A µ γ (x, a) with φ being a prior parameter. Both parameters θ, φ are trained with the Adam optimizer (Kingma and Ba, 2014) with learning rate α = 3 • 10 -4 . We adopt other default hyper-parameters in [START_REF] Dhariwal | OpenAI baselines[END_REF], for details, please refer to the code base.

Trust region policy optimization (TRPO). TRPO (Schulman et al., 2015b) implements the same actor-critic pipeline as PPO, the difference is in the updates. Instead of enforcing a soft clipping constraint, TRPO enforces a strict KL-divegergence constraint E x∼µ [KL(π θ (•|x), µ(•|x)] ≤ ε with ε = 0.01. The policy gradient is computed as A µ γ (x, a)∇ θ log π θ (a|x), and then the final update is constructed by approximately solving a constrained optimization problem, see (Schulman et al., 2015a) for details. The scale of the final update is found through a line search, to ensure that the KL-divergence constraint is satisfied. The implementations are based in [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF].

F.3. Deep RL architecture

Across all algorithms, the policy π θ (a|x) = N (µ θ (x), σ 2 I) has a parameterized mean µ θ (x) and a single standard deviation σ 2 . The mean µ θ (x) is a 2-layer neural network with hidden units h = 64, and f (x) = tanh(x) activation functions. The output layer does not have any activation functions; The value function V φ (x) is a 2-layer neural network with hidden units h = 64 and f (x) = tanh(x) as activation functions. The output layer does not have any activation functions.

F.4. Additional deep RL experiment results

F.4.1. TAYLOR EXPANSION Q-FUNCTION ESTIMATION: ABLATION STUDY ON η Recall that throughout the experiments, we choose K = 1 and construct the new Q-function estimator as a mixture of the default estimator and Taylor expansion Q-function estimator. In particular, the final Q-function estimator is

Q(x, a) = (1 -η) Q π γ (x, a) + η Q π K,γ,γ (x, a).
We choose η ∈ [0, 1] such that it balances the numerical scales of the two combining estimators. In our implementation, we find that the algorithm performs more stably when η is small in the absolute scale. In Figure 5(a)-(b), we show the ablation study on the effect of η, where we vary η ∈ [0.01, 0.03]. The y-axis shows the normalized performance against PPO baselines (which is equivalent to η = 0), such that the PPO baseline achieves a normalized performance of 1.

Overall, we see on different tasks, η impacts the performance differently. For example: on HalfCheetah(B), better performance is achieved with larger values of η, this is consistent with the observation that PPO with γ = 0.999 also achieves better performance; on Ant(B), however, as η increases from zero, the performance increases marginally before degrading. In Figure 5, we show the median and mean performance across all tasks. Note that in general, the average performance increases as η increases from zero, but later starts to decay a bit. When accounting for the effect of performance variance across all tasks, we chose η = 0.01 as the fixed hyper-parameter throughout experiments in the main paper.

Further details on computing Q π K,γ,γ (x, a). Below we assume K = 1. In Algorithm 4, we showed we can construct unbiased estimates of Q π K,γ,γ (x, a) using Q π γ (x, a) as building blocks. With a random time τ ∼ Geometric(1 -γ), the estimator takes the following form

Q K,γ,γ (x t , a t ) = Q π γ (x t , a t ) + γ -γ 1 -γ Q π γ (x t+τ , a t+τ ).
However, since the estimator is based on a single random time, it can have high variance. To reduce variance, we propose the following procedure: let (x t , a t ) be the target state-action pair, we can compute the estimate as

Q K,γ,γ (x t , a t ) = Q π γ (x t , a t ) + γ -γ 1 -γ H s=1 γ s H s =1 γ s Q π γ (x t+s , a t+s ).
When H = ∞, the above estimator corresponds to an estimator which marginalizes over the random time. This should achieve variance reduction compared to the random time based estimate in Algorithm 4. However, then the estimate requires computing cumulative sums over an infinite horizon (or in general a horizon of T ), which might be computationally expensive. To mitigate this, we propose to truncate the above summation up to H = 10 steps. This choice of H aims to achieve a trade-off between computation efficiency and variance. Note that this estimator was previously introduced in (Tang et al., 2020) for off-policy learning.

F.4.2. TAYLOR EXPANSION UPDATE WEIGHTING: ABLATION ON K In Figure 5(c)-(d), we carry out ablation study on the effect of K for the update weighting. Recall that K interpolates two extremes: when K = 0, it recovers the vanilla PG (Sutton et al., 2000) while when K = ∞, it recovers the deep RL heuristic update. We expect an intermediate value of K to achieve some trade-off between bias and variance of the overall update.

In Figure 5(c), we see the effect on individual environments. The effect is case dependent. For HalfCheetah(G), larger K improves the performance; however, for Walker(G), the improvement is less prominent over a large range of K. When aggregating the performance metric in Figure 5(d), we see that intermediate values of K indeed peak in performance. We see that on average, both K = 10 and K = 100 achieve locally optimal mean performance, while K = 10 also achieves the locally optimal median performance.

Note on how the practical updates impact the effect of K. Based on our theoretical analysis, when K = 0 the update should recover the vanilla PG (Sutton et al., 2000), which is generally considered too conservative for the undiscounted objective in Eqn (1). However, in practice, as shown in Figure 5(d), the algorithm does not severely underperform even when K = 0. We speculate that this is because practical implementations of PG updates use batches of data instead of the full trajectories. This means that the relative weights w(t) of the local gradients Q t ∇ θ log π θ (a t |x t ) are effectively self-normalized: w(t) ← w(t) w(t ) where the summation is over the time steps in a sampled mini-batch. The self-normalized weights w(t) are increased in the absolute scale relative to w(t) and partly offset the effect of an initially aggressive discount w(t) = γ t . F.4.3. COMPARISON TO RESULTS IN (ROMOFF ET AL., 2019) Recently, [START_REF] Romoff | Separating value functions across time-scales[END_REF] derived a recursive relations between differences value functions defined with different discount factors. This was shown in Lemma 4.1. Given a sequence of discount factors γ 1 < γ 2 < . . . < γ N < γ , they derived a value function estimator to V π γ (x) based on recursive bootstraps of value function differences V π γi (x) -V π γi-1 (x ). Because they aim at recovering the exact value functions, this estimator could be interpreted as similar to Taylor expansions but with K = ∞.

Different from their motives, we focus on the trade-off achieved by intermediate values of K. We argued that by using K = 0, the estimate might be too conservative; however, using K = ∞ might be challenging due to the variance induced in the recursive bootstrapping procedure. Though it is not straightforward to theoretically show, we conjecture that using the Taylor expansion Q-function estimator with K = ∞ is as difficult as directly estimating V π γ (x). Empirical comparison. The base algorithm of [START_REF] Romoff | Separating value functions across time-scales[END_REF] is PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF]. Their algorithm uses the recursive bootstraps to estimate Q-functions and advantage functions. The new estimate is used as a direct plug-in replacement to Q π γ (x, a) and A π γ (x, a) adopted in the PPO algorithm. We run experiments with the open source implementation of [START_REF] Romoff | Separating value functions across time-scales[END_REF] from the original authors3 . We evaluate the algorithm's performance over continuous control benchmark tasks. We applied the default configurations from the code base with minimum changes to run on continuous problems (note that [START_REF] Romoff | Separating value functions across time-scales[END_REF] focused on a few discrete control problems). Overall, we find that the algorithm does not learn stably (see Figure 4).

G. Extensions of update weighting techniques to off-policy algorithms

Below, we show that techniques developed in this paper could be extended to off-policy learning algorithms. We provide both details in theoretical derivations, algorithms, as well as experimental results.

G.1. Off-policy actor-critic algorithms

Off-policy actor-critics [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF][START_REF] Timothy P Lillicrap | Continuous control with deep reinforcement learning[END_REF] maintain a deterministic policy π θ (x) and a Q-function critic Q φ (x, a). The agent takes exploratory actions under the environment, and saves data (x t , a t , r t ) into a common replay buffer D. At training time, the algorithm samples data from the replay to update parameters. The policy is updated via the deterministic policy gradient (Silver et al., 2014)

, θ ← θ + α∇ θ E µ [Q φ (x, π θ (x))],
where µ is implicitly defined by the past behavior policy.

Deep deterministic policy gradient (DDPG). DDPG [START_REF] Timothy P Lillicrap | Continuous control with deep reinforcement learning[END_REF] maintains a deterministic policy network π θ (a|x) ≡ π θ (x) and a Q-function critic Q φ (x, a). The algorithm explores by executing a perturbed policy a = ε + π θ (x) where ε ∼ N (0, σ 2 ) for σ = 0.1, and then saves the data (x, a, r, x ) into a replay buffer D. At training time, the behavior data is sampled uniformly from the replay buffer (x i , a i , r i , x i ) B-1 i=0 ∼ U(D) with B = 100. The critic is updated via TD(0), by minimizing:

1 B B-1 i=0 (Q φ (x i , a i ) -Q target (x i , a i )) 2 where Q target (x i , a i ) = r i + γQ φ (x i , π θ (x i ))
, where θ , φ are delayed versions of θ, φ respectively [START_REF] Mnih | Humanlevel control through deep reinforcement learning[END_REF]. The policy is updated by maximizing

1 B B-1 i=0 Q φ (x i , π θ (x i ))
with respect to θ. Both parameters θ, φ are trained with the Adam optimizer (Kingma and Ba, 2014) with learning rate α = 10 -4 . We adopt other default hyper-parameters in [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF], for details, please refer to the code base.

Twin-delayed DDPG (TD3). TD3 [START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF] adopts the same training pipeline and architectures as DDPG. TD3 also adopts two critic networks Q φ1 (x, a), Q φ2 (x, a) with parameters φ 1 , φ 2 , in order to minimize the over-estimation bias [START_REF] Hasselt | Double Q-learning[END_REF]Van Hasselt et al., 2016).

Soft actor-critic. SAC [START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF] adopts a similar training pipeline and architectures as TD3. A major conceptual difference is that SAC is based on the maximum-entropy formulation of RL (Ziebart et al., 2008;[START_REF] Fox | Taming the noise in reinforcement learning via soft updates[END_REF]. The Q-function is augmented by entropy regularization bonus and the policy is optimized such that it does not collapse to a deterministic policy.

G.2. Architecture

All algorithms share the same architecture. The policy network π θ (x) takes as input the state x, and is a 2-layer neural network with hidden units h = 256 and f (x) = relu(x) activation functions. The output is squashed by f (x) = tanh(x) to comply with the action space boundaries; The critic Q φ (x, a) takes a concatenated vector [x, a] as inputs, is 2-layer neural network with hidden units h = 256 and f (x) = relu(x) activation functions. The output does not have any activation functions.

For stochastic policies, the policy network parameterizes a Gaussian also parameterizes a log standard deviation vector log σ(x), which is a neural network with the same architecture above. The stochastic output is a reparameterized function a = π θ (x) + exp(log σ(x)) • ε where the noise ε ∼ N (0, 1). Finally, the action output is squashed by tanh(x) to comply with the action boundary [START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF].

G.3. Algorithm details for update weighting

To derive an update based on update weighting, we start with the undiscounted on-policy objective

V γ (x) = E x ∼ρ π θ x,γ,γ V π θ γ (x )
. Given behavior data generated under µ, we abuse the notation and also use µ to denote the state distribution under µ (usually implicitly defined by sampling from a replay buffer D). By rewriting the objective with importance sampling (IS),

V π θ γ (x) = E x ∼ρ π θ x,γ,γ V π θ γ (x ) = E x ∼µ ρ π θ x,γ,γ (x ) µ(x ) V π θ γ (x ) , (30)
we derive an off-policy learning objective. By dropping a certain terms (see [START_REF] Degris | Offpolicy actor-critic[END_REF] for details about the justifications for dropping such terms), we can derive the IS-based gradient update

E x ∼µ ρ π θ x,γ,γ (x ) µ(x ) ∇ θ V π θ γ (x ) ≈ E x ∼µ ρ π θ x,γ,γ (x ) µ(x ) ∇ θ Q φ (x , π θ (x ))
To render the update feasible, we need to estimate the ratio

ρ π θ x,γ,γ (x ) µ(x )
. Inspired by (Sinha et al., 2020), we propose to maintain a fast replay buffer D f which contains the most recent sampled data (which implicitly defines ρ π θ

x,γ,γ ), then the estimator w ψ is trained to estimate the density ratio between D (which implicitly defines µ) and D f . See Appendix F for further details. The full off-policy actor-critic algorithm is summarized in Algorithm G.3. In practice, we implement a undiscounted uniform distribution instead of ρ π x,γ,γ (x ) with γ = 1. The main motivation is that this distribution is much easier to specify as it corresponds to sampling from the replay buffer uniformly without discounts, as explained below.

As an important observation for practical implementations, note that ρ π

x,γ,γ (x ) =

γ γ I[x 0 = x ] + (γ -γ)E π   t≥1 (γ ) t-1 I[x t = x ] x 0 = x  
when setting γ = 1, we see that the second term of the distribution is proportional to E π t≥1 I[x t = x ] x 0 = x , which corresponds to a uniform distribution over states on sampled trajectories, without discounting. This will make implementations much simpler. We will see that this could also lead to performance gains. We leave Taylor expansion based extension of this method for future work.

Details on training the density estimator w ψ (x). The density estimator w ψ (x) is parameterized with exactly the same architecture as the policy network π θ (x), except that its output activation is replaced by log(1 + exp(x)) to ensure that w ψ (x) > 0. The off-policy actor-critic algorithm maintains an original buffer D of size |D| = 10 6 ; in addition, we maintain a fast replay buffer D f with |D f | = 10 4 , which is used for saving the most recently generated data points. For ease of analysis, assume that the data sampled from D f come from π θ , while the data sampled from D come from µ.

To learn the ratio

ρ π θ x,γ,γ (x ) µ(x )
, we adopt a simple discriminative loss function as follows

L(ψ) = -E x ∼ρ π θ x,γ,γ log w ψ (x ) 1 + w ψ (x ) -E x ∼µ log 1 1 + w ψ (x ) ≈ -E x∼D f log w ψ (x ) 1 + w ψ (x ) -E x∼D log 1 1 + w ψ (x )
.

The optimal solution to ψ * = arg min ψ L(ψ) is w ψ * (x ) = ρ π θ

x,γ,γ (x ) µ(x )

(assuming enough expressiveness). Then, the density estimator is used for weighting the policy update: when sampling a batch of B data from the buffer, the weight w ψ (x i ), 1 ≤ i ≤ B is computed for each data point x i . Then the weights are normalized across batch w i = where the inverse temperature is τ = 0.1. Then w i is used for weighting the such that the policy is updated as θ ← θ + α 1 B B i=1 w i ∇ θ Q φ (x i , π θ (x i )).

Algorithm 5 Update weighting Off-policy actor-critic Require: policy π θ (x), Q-function critic Q φ (x, a), density estimator w ψ (x) and learning rate α ≥ 0 while not converged do 1. Collect data (x t , a t , r t ) ∼ µ and save to the buffer D and the fast buffer D f 2. Estimate the density by the discriminative loss between D, D f , such that w ψ (x ) ≈ ρ π θ x,γ,γ (x )/µ(x ), where x is the initial state of the MDP. 3. Sample data from (x i , a i , r i ) B i=1 ∼ D. 3(a). Update the Q-function critic Q φ (x, a) via TD-learning, such that Q φ (x, a) ≈ Q π θ γ (x, a). 3(b). Update the policy parameter with the gradient θ ← θ + α B i=1 w ψ (x i )∇ θ Q φ (x i , π θ (x i )). end while

We carry out the update in Algorithm 2, where the density estimator w ψ (x) is trained based on a discriminative loss between D and D f . For any given batch of data {x i } B i=1 , we normalize the prediction w i = w ψ (x i ) τ / B j=1 w ψ (x j ) τ with hyper-parameter τ = 0.1 as similarly implemented in (Sinha et al., 2020). The temperature annealing moves w i closer to a uniform distribution and tends to stabilize the algorithm. See Appendix F for further details.

Discussion on relations to other algorithms. Previous work focuses on re-weighting transitions to stabilize the training of critics. For example, prioritized replay [START_REF] Schaul | Prioritized experience replay[END_REF] prioritizes samples with high Bellman errors. Instead, Algorithm 2 reweighs samples to speed up the training of the policy. Our observation above also implies that when sampling from D, D f for training the estimates w ψ ≈ ρ π θ

x,γ,γ (x ) µ(x )

, it is not necessary to discount the transitions. This is in clear contrast to prior work, such as (Sinha et al., 2020), where they propose to train w ψ (x ) ≈ d π θ x,γ (x )/d µ x,γ (x ) , which is the fully discounted visitation distribution under γ based on the derivation of optimizing a discounted objective V π θ γ (x).

Results. We build the algorithmic improvements based on TD3 [START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF] and SAC [START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF], and name the correspinding algorithms TD3(γ) and SAC(γ) respectively. We compare with TD3, SAC, and DDPG [START_REF] Timothy P Lillicrap | Continuous control with deep reinforcement learning[END_REF], all of which are off-policy algorithms.

We first compare TD3(γ) with TD3 in Figure 6. To highlight the default sample efficiency of off-policy methods, we include PPO as a baseline as well. Across all four presented tasks, we see that TD(γ) performs similarly or marginally outperforms the TD3 baseline. To make concrete the comparison between final performance, we report the final score mean ± 0.5std of each algorithm in Table 1. As a default baseline, we also show the results of DDPG reported in [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF]. Overall, TD3(γ) provides a modest yet consistent boost over baseline TD3.

Then we compare SAC(γ) with SAC in Figure 7 and Table 1. We see that SAC(γ) provides marginal performance gains over Walker2d and Ant, while it is slightly overperformed by baseline SAC for HalfCheetah and Hopper. We speculate that this is partly because the hyper-parameters of baseline SAC are well tuned on HalfCheetah, and it is difficult to achieve further significant gains without exhaustive hyper-parameter search. Overall, SAC(γ) is competitive compared to SAC. 1. Final performance of baseline algorithms over benchmark tasks. The final performance is computed as the mean scores over the last 10 iterations of each algorithm, averaged over 5 seeds. When compared with TD3, the performance of DDPG-v1 is taken from [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF]; when compared with SAC, the performance is based on re-runs of the DDPG-v2 baselines with [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF]. For each task, the best algorithms are highlighted in bold fonts (potentially with ties).

Figure 1 .

 1 Figure 1. Comparison of Taylor expansions with different orders. The x-axis shows the order K, the y-axis shows the log relative errors of the approximations. The blue curve shows the exact computations while the red curve shows the sample based estimations. See Appendix F for more details.

Figure 2 .

 2 Figure 2. Comparison of Taylor expansion Q-function estimation with other baselines. Each curve shows median ± std results across 5 seeds. Taylor expansion outperforms PPO baselines with both lower and high discount factors.

Figure 3 .

 3 Figure 3. Comparison of Taylor expansion update weighting with other baselines. Each curve shows median ± std results across 5 seeds. Taylor expansion outperforms the default PPO baseline most stably.

Figure 4 .Figure 5 .

 45 Figure 4. Learning curves generated by running the open source implementation of[START_REF] Romoff | Separating value functions across time-scales[END_REF] on Walker2d(G), averaged across 5 runs. There is little progress of learning for the algorithm on other benchmark tasks.

Figure 6 .Figure 7 .

 67 Figure 6. Evaluation of near off-policy actor-critic algorithms over continuous control domains. Each curve corresponds to a baseline algorithm averaged over 5 random seeds. TD3(γ) (red curve) consistently outperforms or performs similarly as other baselines.

  a t ). 3. Compute weights for each state w t = w x0,K,γ,γ (t), and averageg θ = T t=1 w t Q t ∇ θ log π θ (a t |x t ). 4. Update parameters θ ← θ + αg θ .

	end while
	6. Related work
	Discount factors in RL. Discount factors impact RL
	agents in various aspects. A number of work suggest that
	RL problems with large discount factors are generally more
	difficult to solve

  policy gradient algorithms. In Proceedings of the International Conference on Machine Learning, 2014.Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. Experience replay with likelihood-free importance weights. arXiv, 2020.

	Richard S Sutton. TD models: Modeling the world at a mix-
	ture of time scales. In Proceedings of the International
	Conference on Machine Learning. 1995.
	Richard S Sutton and Andrew G Barto. Reinforcement
	learning: An introduction. MIT Press, 2018.
	Richard S Sutton, David A McAllester, Satinder P Singh,
	and Yishay Mansour. Policy gradient methods for rein-
	forcement learning with function approximation. In Ad-
	vances in Neural Information Processing Systems, 2000.
	Yunhao Tang, Michal Valko, and Rémi Munos. Taylor
	expansion policy optimization. In Proceedings of the
	International Conference on Machine Learning, 2020.
	Hado van Hasselt, John Quan, Matteo Hessel, Zhongwen
	Xu, Diana Borsa, and André Barreto. General non-linear
	Bellman equations. arXiv, 2019.
	Harm Van Seijen, Mehdi Fatemi, and Arash Tavakoli. Using
	a logarithmic mapping to enable lower discount factors
	in reinforcement learning. In Advances in Neural Infor-
	mation Processing Systems, 2019.
	Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-
	gradient reinforcement learning. Advances in Neural
	Information Processing Systems, 2018.
	Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell, and
	Anind K. Dey. Maximum entropy inverse reinforcement
	learning. In Proceedings of the AAAI Conference on
	Artificial Intelligence, 2008.

Emanuel Todorov, Tom Erez, and Yuval Tassa. MuJoCo: A physics engine for model-based control. In International Conference on Intelligent Robots and Systems, 2012. Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.

The error bounds could be further improved, e.g., by adapting the concentration bounds at different steps 1 ≤ k ≤ K. Note that its purpose is to illustrate the bias and variance trade-off induced by the Taylor expansion order K.

The exact PPO update is more complicated than this. Refer to[START_REF] Schulman | Proximal policy optimization algorithms[END_REF] for the exact formula.

See https://github.com/facebookresearch/td-delta.

Acknowledgements. Yunhao thanks Tadashi Kozuno and Shipra Agrawal for discussions on the discrepancy between policy gradient theory and practices. Yunhao acknowledges the support from Google Cloud Platform for computational resources. The authors also thank Pooria Joulani for reviewing a draft of the paper.

APPENDICES: Taylor Expansions of Discount Factors A. Proofs

Proposition 3.1. The following holds for all K ≥ 0,

When γ < γ < 1, the residual norm converges to 0, which implies

Proof. Recall the Woodbury matrix identity (I -γ P π ) -1 = (I -γP π ) -1 + (γ -γ)(I -γP π ) -1 P π (I -γ P π ) -1 .

Recall the equality V π γ = (I -γ P π ) -1 r π . By plugging in the Woodbury matrix identity, this immediate shows

We can plug in the definition of V π γ = (I -γ P π ) -1 r π and invoke the Woodbury matrix identity again. This produces

By induction, it is straightforward to show that iterating the above procedure K ≥ 0 times produces the following equalities

Consider the norm of the residual term. Since P π is a transition matrix, P π ∞ < 1. As a result, (I -

When γ < γ < 1, the residual norm decays exponentially and → 0 as K → ∞. This implies that the infinite series converges,

Additional consideration when γ = 1. When γ = 1, in order to ensure finiteness of V π γ =1 , we assume the following two conditions: (1) The Markov chain induced by π is absorbing; (2) for any absorbing state x, r π (x) = 0. Without loss of generality, assume there exists a single absorbing state. In general, the transition matrix P π can be decomposed as follows [START_REF] Miller | Introduction to probability[END_REF][START_REF] Sheldon | Introduction to probability models[END_REF], 1) . Here, the first X -1 states are transient and the last state is absorbing. For convenience, define r π as the reward vector r π constrained on the first X -1 transient states. We provide a few lemmas below.

Consider the second term. Now, we derive this term in an alternative way which imparts more intuitions on why its estimation is challenging. Note that

The second term of the full gradient is equivalent to differentiating through the above expression, while keeping all V π θ γ (x t ) fixed. This leads the following gradient

Here, we introduce

, which is equivalent to a value function that treats V π θ γ (x) as rewards and with discount factor γ . Naturally, constructing an unbiased estimator of the second term of the full gradient requires estimating W π θ γ,γ , which is difficult in at least two aspects: (1) in practice, value functions are already estimated, which could introduce additional bias and variance; (2) as a premise of our work, estimating discounted values with discount factor γ is challenging potentially due to high variance.

E. Details on approximation errors with finite samples

Intuitively, as K increases, the K th order expansion V π K,γ,γ approximates V K γ more accurately in expectation. However, in practice where all constituent terms of the approximation are built from the same batch of data, the variance might negatively impact the accuracy of the estimate.

To formalize such intuitions, we characterize the bias and variance trade-off under the phased TD-learning framework [START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF]. Consider estimating the value function

| be the absolute error of value function estimates V π γ . Assume from each state x, there are independent n trajectories generated under π, [START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF] shows that commonly used TD-learning methods (e.g. TD(λ)) have error bounds of the following form with probability 1 -δ,

Here, the factor A(γ, δ) is an error term which characterizes the errors arising from the finite sample size n. As n → ∞, A(γ, δ) → 0; the constant B(γ) is a contraction coefficient that shows how fast the error decays in expectation. See Appendix E for details.

With the calculations of estimators V π γ (x) as a subroutine, we construct the n-sample K th order estimator V π K,γ,γ (x),

where x i,k is sampled from

), the estimator analyzed by [START_REF] Michael | Bias-variance error bounds for temporal difference updates[END_REF]. We are interested in the error ∆ 1-(γ -γ) . Then with probability at least 1 -2δ if K ≥ 1 and probability 1 -δ if K = 0, the following holds 1 , ∆ γ K,t ≤ ε(A(γ, δ) + U ) finite sample error + E(γ, γ , K)

expected gap error

where U = 2 log 2(K+1) δ /n for K ≥ 1 and U = 0 if K = 0. The expected gap error E(γ, γ , K) = γ -γ 1-γ

K+1 Rmax

1-γ is defined in Proposition 3.2.