Tadashi Kozuno

Yunhao Tang

Mark Rowland

Rémi Munos

Steven Kapturowski

Will Dabney

Michal Valko

David Abel

Revisiting Peng's Q(λ) for Modern Reinforcement Learning

Off-policy multi-step reinforcement learning algorithms consist of conservative and nonconservative algorithms: the former actively cut traces, whereas the latter do not. Recently, Munos et al. (2016) proved the convergence of conservative algorithms to an optimal Q-function. In contrast, non-conservative algorithms are thought to be unsafe and have a limited or no theoretical guarantee. Nonetheless, recent studies have shown that non-conservative algorithms empirically outperform conservative ones. Motivated by the empirical results and the lack of theory, we carry out theoretical analyses of Peng's Q(λ), a representative example of non-conservative algorithms. We prove that it also converges to an optimal policy provided that the behavior policy slowly tracks a greedy policy in a way similar to conservative policy iteration. Such a result has been conjectured to be true but has not been proven. We also experiment with Peng's Q(λ) in complex continuous control tasks, confirming that Peng's Q(λ) often outperforms conservative algorithms despite its simplicity. These results indicate that Peng's Q(λ), which was thought to be unsafe, is a theoretically-sound and practically effective algorithm.

Introduction

Q-learning is a canonical algorithm in reinforcement learning (RL) [START_REF] Watkins | Learning from Delayed Rewards[END_REF]. It is a single-step algorithm, in that it only uses individual transitions to update value estimates. Many multi-step generalisations of Q-learning have been proposed, which allow temporally-extended trajectories to be used in the updating of values (Bertsekas & 1996; [START_REF] Watkins | Learning from Delayed Rewards[END_REF][START_REF] Peng | Incremental multi-step Qlearning[END_REF]1996;[START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF][START_REF] Harutyunyan | λ) with off-policy corrections[END_REF][START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF][START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF], potentially leading to more efficient credit assignment. Indeed, multi-step algorithms have often been observed to outperform single-step algorithms for control in a variety of RL tasks [START_REF] Mousavi | Applying Q(λ)-learning in deep reinforcement learning to play Atari games[END_REF][START_REF] Harb | Investigating recurrence and eligibility traces in deep Q-networks[END_REF][START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF][START_REF] Barth-Maron | Distributed distributional deterministic policy gradients[END_REF][START_REF] Kapturowski | Recurrent experience replay in distributed reinforcement learning[END_REF][START_REF] Daley | Reconciling λ-returns with experience replay[END_REF].

However, using multi-step algorithms for RL comes with both theoretical and practical difficulties. The discrepancy between the policy that generated the data to be learnt from (the behavior policy) and the policy being learnt about (the target policy) can lead to complex, non-convergent behavior in these algorithms, and so must be considered carefully. There are two main approaches to deal with this discrepancy (cf. Table 1). Conservative methods ensure convergence is guaranteed no matter what behavior policy is used, typically by truncating the trajectories used for learning. By contrast, non-conservative methods typically do not truncate trajectories, and as a result do not come with generic convergence guarantees. Nevertheless, non-conservative methods have consistently been found to outperform conservative methods in practical large-scale applications. Thus, there is a clear gap in our understanding about non-conservative methods; why do they so work well in practice, but lack the guarantees of their conservative counterparts?

In this paper, we address this question by studying a representative non-conservative algorithm, Peng's Q(λ) [START_REF] Peng | Incremental multi-step Qlearning[END_REF]1996, PQL), in more realistic learning settings. Our results show that while PQL does not learn optimal policies under arbitrary behavior policies, a convergence guarantee can be recovered if the behavior policy tracks the target policy, as is often the case in practice. This represents a closing of the gap between the strong empirical performance of non-conservative methods and their previous lack of theoretical guarantees.

More concretely, our primary theoretical contributions bring new understanding to PQL, and are summarized as follows:

• A proof that PQL with a fixed behavior policy converges to a "biased" (i.e., different from Q * ) fixed-point.

• Analysis of the quality of the resulting policy.

Table 1. List of off-policy multi-step algorithms for control. Harutyunyan's Q(λ), Tree-backup, Watkins' Q(λ), and Peng's Q(λ) are abbreviated as HQL, TBL, WQL, and PQL, respectively (cf. Section 3.2 for details of the algorithms). Conservative column indicates if an algorithm is conservative or not (cf. Section 4). Convergence column indicates the convergence of algorithms to any fixed point, whereas Convergence to Q * column indicates the convergence of algorithms to the optimal Q-function Q * . indicates new results in the present paper. PQL converges to a biased fixed-point when the behavior policy is fixed. It converges to Q * when a behavior policy is updated appropriately. (An exact condition is given in Section 5.) • Convergence of PQL to an optimal policy when using appropriate behavior policy updates.

Algorithm

• Error propagation analysis when using approximations.

In addition to these theoretical insights, we validate the empirical performance of PQL through extensive experiments.

Our focus is on continuous control tasks, where one encounters many technical challenges that do not exist in discrete control tasks (cf. Section 7.2). They are also accessible to a wider range of readers. We show that PQL can be easily extended to popular off-policy actor-critic algorithms such as DDPG, TD3 and SAC [START_REF] 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 actorcritic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF]. Over a large subset of tasks, PQL consistently outperforms other conservative and non-conservative baseline alternatives.

Notation and Definitions

For a finite set A and an arbitrary set B, we let ∆ A and B A be the probability simplex over A and the set of all mappings from A to B, respectively.

Markov Decision Processes (MDP).

We consider an MDP defined by a tuple X, A, P, P 0 , R, γ , where X is the finite state space, A the finite action space, P : X×A → ∆ X the state transition probability kernel, P 0 ∈ ∆ X the initial state distribution, R the (conditional) reward distribution, and γ ∈ [0, 1) the discount factor [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. We let r ∈ R X×A be a reward function defined by r(x, a) := r R(dr |x, a).

On the Finiteness of the State and Action Spaces.

While we assume both X and A to be finite, most of theoretical results in the paper hold in continuous state spaces with appropriate measure-theoretic considerations. The finiteness assumption on the action space is necessary to guarantee the existence of the optimal policy [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. In Appendix B, we discuss assumptions necessary to extend our theoretical results to continuous action spaces.

Policy and Value Functions. Suppose a policy π : X → ∆ A . We consider the standard RL setup where an agent interacts with an environment, generating a sequence of state-action-reward tuples (X t , A t , R t ) t≥0 with A t being an action sampled from some policy; throughout, we denote random variables by upper cases. Define G = ∞ t=0 γ t R t as the cumulative return. The state-value and Q-functions are defined by V π (x) := E[G|X 0 = x, π] and Q π (x, a) := E[G|X 0 = x, A 0 = a, π], respectively, where the conditioning by π means A t ∼ π(•|X t ).

Evaluation and Control. Two key tasks in RL are evaluation and control. The problem of evaluation is to learn the Q-function of a fixed policy. The aim in the control setting is to learn an optimal policy π * defined as to satisfy

V π * := V * ≥ V π , ∀π (the inequality is point-wise, i.e., V * (x) ≥ V π (x) for all x ∈ X). Similarly to V * , we let Q * denote the optimal Q-function Q π * .
As a greedy policy with respect to Q * is optimal, it suffices to learn Q * . In this paper, we are particularly interested in the off-policy control setting, where an agent collects data with a behavior policy µ, which is not necessarily the agent's current policy π. On-policy settings are a special case where π = µ.

Multi-step RL Algorithms and Operators

Operators play a crucial role in RL since all value-based RL algorithms (exactly or approximately) update a Qfunction based on the recursion Q k+1 := O k Q k , where O k : R X×A → R X×A is an operator that characterizes each algorithm. In this section, we review multi-step RL algorithms and their operators.

Basic Operators. Assume we have a fixed policy π. With an abuse of notations, we define operators π : R X×A → R X and P : R X → R X×A by (πQ)(x) := a∈A π(a|x)Q(x, a), and (PV )(x, a) := y∈X P(y|x, a)V (y) for any Q ∈ R X×A and V ∈ R X , respectively (hereafter, we omit "for any..." in definitions of operators for brevity). We define their composite P π := Pπ. As a result, the Bellman operator T π : R X×A → R X×A is defined by

T π Q := r + γP π Q. For a function Q ∈ R X×A ,
we let G(Q) be the set of all greedy policies1 with respect to Q. The Bellman optimality operator T is defined by

T Q = T π Q Q with π Q ∈ G(Q) 2 . Q-learning approximates the value iteration (VI) updates Q k+1 := T Q k .

On-policy Multi-step Operators for Control

We first introduce on-policy multi-step operators for control. [START_REF] Puterman | Modified policy iteration algorithms for discounted Markov decision problems[END_REF], where

Modified Policy Iteration (MPI). MPI uses the recursion

Q k+1 := T π k n Q k for Q-function updates
π k ∈ G(Q k ). The n-step return operator T π n : R X×A → R X×A is defined by T π n Q := (T π ) n Q.
λ-Policy Iteration (λ-PI). λ-PI uses the recursion [START_REF] Bertsekas | Temporal differences-based policy iteration and applications in neuro-dynamic programming[END_REF], where π k ∈ G(Q k ). The λ-return operator T π λ : R X×A → R X×A is defined as

Q k+1 := T π k λ Q k for Q-function updates
T π λ Q := (1 -λ) ∞ n=1 λ n-1 T π n Q = Q + (I -γλP π ) -1 (T π Q -Q),
where

(I -γλP π ) -1 := ∞ t=0 (γλP π ) t , and λ ∈ [0, 1].

Off-policy Multi-step Operators for Control

Next, we explain off-policy multi-step operators for control. We note that on-policy algorithms in the last subsection can be converted to off-policy versions by using importance sampling [START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF][START_REF] Casella | Statistical Inference[END_REF].

Uncorrected n-step Return. For a sequence of behavior policies (µ) k≥0 , the uncorrected n-step return algorithm uses the recursion [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF][START_REF] Kapturowski | Recurrent experience replay in distributed reinforcement learning[END_REF], where

Q k+1 := N µ k ,π k n Q k for Q-function up- dates
π k ∈ G(Q k ).
Here, the uncorrected n-step return operator N µ,π n is defined for any policies π and µ by

N µ,π n Q := (T µ ) n-1 T π Q.
Peng's Q(λ) (PQL) For a sequence of behavior policies (µ) k≥0 , PQL uses the recursion [START_REF] Peng | Incremental multi-step Qlearning[END_REF]1996), where

Q k+1 := N µ k ,π k λ Q k for Q-function updates
π k ∈ G(Q k ).
Here, the PQL operator N µ,π λ is defined for any policies π and µ by

N µ,π λ Q := (1 -λ) ∞ n=1 λ n-1 N µ,π n Q , (1)
where λ ∈ [0, 1]. Note that PQL is a generalization of λ-PI because it reduces to λ-PI when µ k = π k . In other words, PQL is λ-PI with one additional degree of freedom in µ k .

General Retrace. We next introduce a general version of the Retrace operator [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF], from which other operators are obtained as special cases.

For a behavior policy µ and a target policy π, we let P cµ : R X×A → R X×A be an operator defined by

(P cµ Q)(x, a) := (y,b)∈X×A P(y|x, a)c(y, b)µ(b|y)Q(y, b),
where c is an arbitrary non-negative function over X × A whose choice depends on an algorithm. Note that for any n, ((P cµ ) n Q)(x, a) can be estimated off-policy with data collected under the behavior policy µ.

A general Retrace operator R cµ,π λ : R X×A → R X×A is obtained by replacing P π of (I -γλP π )

-1 in the λ-return

operator T π λ with P cµ . Concretely, R cµ,π λ Q := Q + (I -γλP cµ ) -1 (T π Q -Q).
The general Retrace algorithm updates its Q-function by

Q k+1 := R c k µ k ,π k λ Q k ,
where (c k ) k≥0 is a sequence of arbitrary non-negative functions over X × A, (µ k ) k≥0 is an arbitrary sequence of behavior policies, and (π k ) k≥0 is a sequence of target policies that depends on an algorithm. Given the choices of c k and π k in Table 2, we recover a few known algorithms [START_REF] Watkins | Learning from Delayed Rewards[END_REF][START_REF] Peng | Incremental multi-step Qlearning[END_REF]1996;[START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF][START_REF] Harutyunyan | λ) with off-policy corrections[END_REF][START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF][START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF].

The general Retrace algorithm is off-policy as

(R c k µ k ,π k λ Q k )(x 0 ,
a 0 ) can be estimated off-policy by the following estimator given a trajectory (x t , a t , r t ) t≥0 collected under µ k :

Q k (x 0 , a 0 ) + ∞ t=0 t u=1 c(x u , a u ) γ t λ t δ t , (2)
where 0 u=1 c(x u , a u ) := 1, and δ t is the TD error

r t + γ(π k Q k )(x t+1 ) -Q k (x t , a t ) at time step t.

Conservative and Non-conservative

Multi-step RL Algorithms [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF] showed that the following conditions suffice for the convergence of the general Retrace to Q * :

Algorithm

c k π k α-TRACE min{1, ρ k } απ Q k + (1 -α)µ k C-TRACE min{1, ρ k } απ Q k + (1 -α)µ k HQL 1 π Q k RETRACE min{1, ρ k } ANY TBL π k ANY WQL min{1, ρ k } π Q k PQL 1 λπ Q k + (1 -λ)µ k 1. c k (x, a) ∈ [0, π k (a|x)/µ k (a|x)] for any k and (x, a) ∈ X × A.
2. π k satisfies some greediness condition, such as εgreediness with decreasing ε as k increases; cf. [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF] for further details.

We call algorithms that satisfy the first condition conservative algorithms for reasons to be explained below. Otherwise, we call the algorithms non-conservative. See Table 1 for the classification of algorithms. The uncorrected n-step return algorithm can also be viewed as a non-conservative algorithm with non-Markovian traces that depend also on the past.

Conservativeness, Theoretical Guarantees, and Empirical Performance of Algorithms. Recall that in the general Retrace update estimator (2), the effect of the TD error δ t is attenuated by t u=1 c(x u , a u ) in addition to γ t λ t . Hence, from the backward view [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], the first condition intuitively requires that the trace must be cut if a sub-trajectory (x 0 , a 0 , . . . , x t , a t ) is unlikely under π k relative to µ k . As a result, conservative algorithms only carry out safe updates to Q-functions.

As shown in [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF], such conservative updates enable a convergence guarantee of general conservative algorithms. However, [START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF] observed that it often results in frequent trace cuts, and conservative algorithms usually benefit less from multi-step updates.

In contrast, non-conservative algorithms accumulate TD errors without carefully cutting traces. As a result, nonconservative algorithms might perform poorly. As we show later (Proposition 5), it is the case at least for Harutyunyan's Q(λ) [START_REF] Harutyunyan | λ) with off-policy corrections[END_REF], HQL), an instance of nonconservative algorithms, when a behavior policy is fixed. Nonetheless, non-conservative algorithms are known to per-form well in practice [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF][START_REF] Kapturowski | Recurrent experience replay in distributed reinforcement learning[END_REF][START_REF] Daley | Reconciling λ-returns with experience replay[END_REF]. To understand its reason, it is important to characterize what kind of updates to the behavior policy entail the convergence of the overall algorithm. In the following sections, we take a step forward along this direction. We establish the convergence guarantee of PQL under two setups: (1) when the behavior policy is fixed; (2) when the behavior policy is updated in an appropriate way. Peng's Q(λ) In this section, we analyze Peng's Q(λ). We start with the exact case where there is no update errors in value functions. Later, we will consider the approximate case when accounting for update errors. The following lemma is particularly useful in theoretical analyses as well as practical implementations. Lemma 1 [START_REF] Harutyunyan | λ) with off-policy corrections[END_REF]. The PQL operator can be rewritten in the following forms:

Theoretical Analysis of

N µ,π λ Q = Q + (I -γλP µ ) -1 T λµ+(1-λ)π Q -Q = (I -γλP µ ) -1 (r + γ(1 -λ)P π Q) .
Proof. This is proven in [START_REF] Harutyunyan | λ) with off-policy corrections[END_REF], but we provided a proof in Appendix C for completeness.

Exact Case with a Fixed Behavior Policy

We now analyze PQL with a fixed behavior policy µ. While the behavior policy is not fixed in a practical situation, the analysis shows a trade-off between bias and convergence rate. This trade-off is analogous to the bias-contractionrate trade-off of off-policy multi-step algorithms for policy evaluation [START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF] and sheds some light on important properties of PQL.

Concretely, we analyze the following algorithm:

π k ∈ G(Q k ) and Q k+1 := N µ,π k λ Q k .
(3) [START_REF] Harutyunyan | λ) with off-policy corrections[END_REF] has proven that a fixed point of the PQL operator coincides with the unique fixed point of λT µ + (1 -λ)T , which is guaranteed to exist since λT µ + (1 -λ)T is a contraction with modulus γ under L ∞ -norm (see Appendix A for details about the contraction and other notions).

The existence of a fixed point does not imply the convergence of PQL, and we need to show that the distance between Q k and the fixed point is decreasing. With the following theorem, we show that PQL does converge. Theorem 2. Let π † be a policy such that Q λµ+(1-λ)π † ≥ Q λµ+(1-λ)π for any policy π, where the inequality is pointwise. Then,

π † ∈ G(Q λµ+(1-λ)π † ), and Q k of PQL (3) uni- formly converges to Q λµ+(1-λ)π † with the rate β k , where β := γ(1 -λ)/(1 -γλ).
Proof. See Appendix E.

We build intuitions about the bias-convergence-rate tradeoff implied in Theorem 2. When λ increases, the fixed point is Q λµ+(1-λ)π † , whose bias against Q * arguably increases; at the same time, the contraction rate β decreases, so that the contraction is faster. Remark 1. In Section 7.6 of [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], it is conjectured that PQL with a fixed policy would converge to a hybrid of Q µ and Q * . Theorem 2 gives an answer to this conjecture and shows that Sutton & Barto (1998)'s conjecture is not necessarily true. Rather, the theorem shows that PQL converges to the Q-function of the best policy among policies of the form λµ + (1 -λ)π.

Approximate Case with a Fixed Behavior Policy

In practice, value-update errors are inevitable due to e.g., finite-sample estimations and function approximation errors.

In this subsection, we provide the error propagation analysis of PQL with a fixed behavior policy. As we will see, the analysis depicts a trade-off between fixed point bias and error tolerance.

We analyze the following algorithm:

π k ∈ G(Q k ) and Q k+1 := N µ,π k λ Q k + ε k ,
where ε k ∈ R X×A denotes the value-update error at iteration k. For simplicity, we use

ρ k := λµ + (1 -λ)π k and ρ † := λµ + (1 -λ)π † in this subsection.
Remark 2. We emphasize that ε k should be rather understood as

Q k+1 -N µ,π k λ Q k ,the difference between the function Q k+1 at k + 1-th iteration and the ideal update N µ,π k λ Q k . In practice, Q k+1 is obtained by first construct- ing a sample estimate N µ,π k λ
Q k and then fitting a parametric model to it by, for example, the square loss minimization. As a result, ε k typically consists of estimation error and function approximation error.

In Section 5.1, we showed

lim k→∞ Q k = Q λµ+(1-λ)π † when ε k (x, a) = 0 at every (x, a) ∈ X × A, and π † ∈ G(Q λµ+(1-λ)π † ).
Therefore, π k is an approximation to π † , and thus it is natural to define V ρ † -V ρ k as the loss of using π k rather than π † . The following theorem provides an upper bound for the loss. Theorem 3. For any K, the following holds:

V ρ † -V ρ K ∞ ≤ O(β K ) + 2 1 -γ K-1 k=0 β K-k-1 ε k ∞ , where • ∞ is the L ∞ -norm defined for any real-valued function f by f ∞ := max v |f (v)|.
Proof. See Appendix G.

Remark 3. In Theorem 3, we provide an upper bound of the L ∞ -norm of V ρ † -V ρ K . As a result, the L ∞ -norm of ε k appears in the upper-bound. However in Appendix G, we prove a point-wise upper-bound of V ρ † -V ρ K , from which an L p -norm upper-bound can be obtained in a straightforward way (e.g., see Lemma 6 of [START_REF] Scherrer | Approximate modified policy iteration and its application to the game of Tetris[END_REF]). For simplicity, we present the L ∞ -norm upper-bound.

As we have already explained the bias-convergence-rate trade-off, for now we ignore the O(β K ) term and focus on the error term. For simplicity, we assume ε k ∞ = ε for every k. Then, , 2013). When λ = 0, these results coincide, which is expected since both λ-PI and PQL degenerate to value iteration. When λ = 1, PQL's error depen-

2 1 -γ K-1 k=0 β K-k-1 ε k ∞ = O 1 -γλ (1 -γ) 2 ε , In contrast, an analogous result of λ-PI is O(ε/(1 -γ) 2 ) (Scherrer
dency is O(ε/(1 -γ)), which is significantly better than O(ε/(1 -γ) 2
). However in this case, PQL is completely biased and converges to Q µ . At intermediate values of λ, PQL achieves a trade-off between error tolerance with bias by changing λ.

Approximate Case with Behavior Policy Updates

Previously, we have analyzed PQL with a fixed behavior policy. However, in practice, the behavior policy is updated along with the target policy. Besides, value-update errors are inevitable in complex tasks. As a result, PQL may behave quite differently in a practical scenario. This motivates our analysis for the following algorithm:3 andα ∈ [1 -λ, 1]. Note that when α = 1, this algorithm reduces to λ-PI as a special case. Though this behavior policy update closely resembles to that of conservative policy iteration [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF], here we require α ≥ 1 -λ.

Q k+1 := N µ k ,π k λ Q k + ε k (4) µ k := απ k + (1 -α)µ k-1 , where π k ∈ G(Q k ),
This algorithm has the following performance guarantee. Theorem 4. For any K, the following holds:

V * -V π K ∞ ≤ O(ζ K ) + 2 1 -γ K-1 l=0 ζ K-l-1 ε l ∞ ,
where ζ := 1 -α + αγ. Hence, PQL with behavior policy updates converges to the optimal policy with the rate ζ K .

Proof. See Appendix H.

Remark 4. As noted in Remark 3, we can derive an L pnorm upper-bound of V * -V π K given its point-wise upperbound. In Appendix H, we actually provide its point-wise upper-bound.

Remark 5. Our results differ from existing work on offpolicy learning and multi-step methods in several important respects. [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF] also analyse multi-step off-policy algorithms, but focus on identifying conditions for algorithms to be conservative, and provide asymptotic convergence guarantees of Q k in the tabular setting under any choice of behaviour policies. In contrast, our analysis focuses on non-conservative algorithms, and provides a finite-time error bound for V * -V π k that incorporates approximation in the algorithm steps. In this regard, these results bear similarity with earlier analysis of multi-step on-policy algorithms such as λ-policy iteration [START_REF] Scherrer | Performance bounds for λ policy iteration and application to the game of Tetris[END_REF]. The central distinction is that our analysis clarifies what conditions are sufficient in non-conservative off-policy algorithms to retain convergence of

V π k to V * .
The first term on the right hand side shows the convergence of PQL with behavior policy updates in an exact case, i.e., ε k ∞ = 0 for any k. It states that the fastest convergence rate is γ K (achieved when α = 1), which is the same as the convergence rate of VI [START_REF] Munos | Error bounds for approximate value iteration[END_REF], policy iteration [START_REF] Munos | Error bounds for approximate policy iteration[END_REF], MPI [START_REF] Scherrer | Approximate modified policy iteration[END_REF]2015), and λ-PI [START_REF] Scherrer | Performance bounds for λ policy iteration and application to the game of Tetris[END_REF]. When α = 1, the convergence rate coincides with that of conservative policy iteration [START_REF] Scherrer | Approximate policy iteration schemes: A comparison[END_REF]). However we are not aware of a similar result of conservative λ-PI, which would be an analogue of PQL considered here. Theorem 4 also provides the error dependency of PQL (the second term on the right hand side). It coincides with the previous result of the above algorithms when α = 1, as one would expect, since PQL with α = 1 is precisely λ-PI. Nonetheless PQL allows some degree of off-policiness when α = 1.

Oscillatory Behavior of HQL

In this section, we have proven the convergence of exact PQL (i.e., no value-update errors). However, the following proposition shows that exact HQL, an instance of non-conservative algorithms, does not converge in an MDP when the behavior policy is fixed. Nonetheless, in the same MDP, setting the behavior policy µ k to a greedy policy π k ∈ G(Q k ) guarantees the convergence.

Proposition 5. There is an MDP such that when exact HQL is run with a fixed policy µ k = µ for all k, λ = 1, and

Q 0 = Q µ , HQL's Q-function Q k oscillates
between two functions, and its greedy policy π k oscillate between optimal and sub-optimal policies. Contrarily, if µ k ∈ G(Q k ), HQL converges to an optimal policy. Proof. A proof of the first claim is given in Appendix D. The second claim immediately follows by noting that if

µ k = π k ∈ G(Q k ), HQL is λ-PI,
which is known to converge [START_REF] Bertsekas | Temporal differences-based policy iteration and applications in neuro-dynamic programming[END_REF].

While this result is specialized to HQL, it sheds light on an important aspect of non-conservative algorithms in general:

While non-conservative algorithms may perform poorly when the behavior policy is fixed, they may converge to Q * when the behavior policy is updated.

The above captures a critical aspect of how algorithms behave in practice, where the behavior policy is continuously updated.

Deep RL Implementations

We next show that Peng's Q(λ) can be conveniently implemented with established off-policy deep RL algorithms. Our experiments focus on continuous control problems where the action space A = [-1, 1] m . A primary motivation for considering continuous control benchmarks (e.g., [START_REF] Brockman | [END_REF][START_REF] Tassa | dm control: Software and Tasks for Continuous Control[END_REF]) is that they are usually more accessible to a wider RL research community, compared to challenging discrete control benchmarks such as Atari games [START_REF] Bellemare | The Arcade Learning Environment: An Evaluation Platform for General Agents[END_REF].

Off-policy Actor-critic Algorithms

Off-policy actor-critic algorithms maintain a policy π θ (a|x) with parameter θ and a Q-function critic Q φ (x, a) with parameter φ. For the policy, a popular choice is the point mass distribution π θ (a|x) = δ(a -π θ (x)), where π θ (x) ∈ R A [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF][START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF][START_REF] Barth-Maron | Distributed distributional deterministic policy gradients[END_REF]. The algorithm collects data with an exploratory behavior policy µ and saves tuples (x t , a t , r t ) into a replay buffer D. At each training iteration, the critic [START_REF] Silver | Deterministic policy gradient algorithms[END_REF]. See further details in Appendix J.

Q φ (x, a) is updated by minimizing squared errors against a Q-function target E D (Q φ (x, a) -Q target (x, a)) 2 . The policy is updated via the deterministic policy gradient θ ← θ + αE µ [∇ θ Q φ (x, π θ (x))]

Implementations of Multi-step Operators

While approximate estimates to T Q(x, a) are arguably the simplest to implement, it only myopically looks ahead for one step. Usually, the learning can be significantly sped up when the targets are constructed with multi-step operators. (See, e.g, empirical examples in [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF][START_REF] Barth-Maron | Distributed distributional deterministic policy gradients[END_REF][START_REF] Kapturowski | Recurrent experience replay in distributed reinforcement learning[END_REF] and theoretical insights in [START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF]) For example, the uncorrected n-step operator is estimated as follows (Hessel et al., 2018): given a n-step trajectory (x i , a i , r i ) n i=0 , the target at (x 0 , a 0 ) is computed as

Q target (x 0 , a 0 ) = n-1 i=0 γ i r 0 + γ n Q φ -(x n , π θ -(x n ))
. Similar estimates could be derived for all multi-step operators introduced in Section 3, especially Peng's Q(λ). We present full details in Appendix J.

Desirable empirical properties of Peng's Q(λ). The estimates of Peng's Q(λ) do not require importance sampling ratios π(a|x) µ(a|x) . This is especially valuable for continuous control, where the policy could be deterministic, in which case algorithms such as Retrace [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF]) cuts traces immediately. Even when policies are stochastic and traces based on IS ratios are not cut immediately, prior work suggests that the trace cuts are usually pessimistic especially for high-dimensional action space (see, e.g., [START_REF] Wang | Sample efficient actor-critic with experience replay[END_REF] for implementation techniques to mitigate the issue).

Experiments

To build better intuitions about Peng's Q(λ), we start with tabular examples in Section 7.1. We will see that the empirical properties of Peng's Q(λ) echo the theoretical analysis in previous sections. In Section 7.2, we evaluate Peng's Q(λ) in the deep RL contexts. We combine Peng's Q(λ) with baseline deep RL algorithms and compare its performance against alternative operators.

A tabular example

Tree MDP. We consider toy examples with a tree MDP of depth D. The MDPs are binary trees, with each node corresponding to a state. Starting from any non-leaf state, the two actions a ∈ {L, R} transition the agent to one of its child nodes with probability one. Each episode lasts for D steps and the agent always starts at the root node. The rewards are zero everywhere except r = 1 at the leftmost leaf node and r = 0.5 at the rightmost leaf node. The behavior policy µ is µ(L|x) = 0.3, µ(R|x) = 0.7 for all states x.

Note that there is a sub-optimal policy of collecting r = 0.5 at the rightmost leaf. The behavior policy is by design biased towards taking right moves, such that it is easy for the agent to learn the sub-optimal policy. The optimal policy is to take left moves and collect r = 1. Throughout training, we optimize the target policy π while fixing the behavior policy µ. This echos the theoretical setup in Section 5.2. See Appendix J for further details on the setup.

Results.

In Figure 1(a), we show the performance of different algorithms after 10, 000 iterations as a function of the MDP's tree depth D. When D = 2, all algorithms achieve the optimal performance; when λ = 1, as D increases, the fixed point bias of Peng's Q(λ) hurts the performance dras- tically. This is less severe for λ = 0.5, whose performance decays less quickly. On the other hand, both Retrace and the one-step operator learn the optimal policy even for D ≤ 6. However, when D increases, it becomes difficult to sample the optimal trajectory. As such, the sparse rewards make it difficult to learn meaningful Q-functions in a reasonable amount of time, unless the return signals get propagated effectively (i.e,. do not cut traces). This is shown in . Small λ corresponds to less bias in the Q-function fixed points and should asymptotically converge to higher performance, but its ineffective reward signal propagation hinders policy improvement in a reasonable time when D is large; on the other hand, large λ suffers sub-optimality when D is small, but its initial policy improvement is substantially expedited when the D is large.

Deep RL experiments

Evaluations. We evaluate performance over environments with a number of different physics simulation backends, such as MuJoCo [START_REF] Todorov | A physics engine for model-based control[END_REF] based Deep-Mind (DM) control suite [START_REF] Tassa | dm control: Software and Tasks for Continuous Control[END_REF] and an open sourced simulator Bullet physics (Coumans & Bai, 2016-2019). Due to space limit, below we only show results for DM control suite and provide a more complete set of evaluations in Appendix J.

Baseline comparison. We use TD3 [START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF] as the base algorithm. 4 We compare with a few multistep baselines: (1) one-step (also the base algorithm); (2) Uncorrected n-step with a fixed n;

(3) Peng's Q(λ) with a fixed λ; (4) Retrace and C-trace. Among all baselines, uncorrected n-step operator is the most commonly used non-conservative operator while Retrace is a representative conservative operator. See Appendix J for more details. All algorithms are trained with a fixed number of steps and results are averaged across 5 random seeds.

Standard benchmark results. In the top row of Figure 2, we show evaluations on standard benchmarks. Across most tasks, Peng's Q(λ) performs more stably than other baseline algorithms. We see that Peng's Q(λ) learns generally as fast as other baselines, and in some cases significantly faster than others. Note that though Peng's Q(λ) does not necessarily obtain the best learning performance per each task, it consistently ranks as the top two algorithms (with ties). This is in contrast to baseline algorithms whose performance rank might vary drastically across tasks. For example, the one-step TD3 performs well in CheetahRun while performs poorly in WalkerWalk. Also, both Ctrace and Retrace generally significantly perform more poorly. We provide further analysis in Appendix J.

Sparse rewards results. In the bottom row of Figure 2, we show evaluations on sparse reward variants of the benchmark tasks. See details on these environments in Appendix J. Sparse rewards are challenging for deep RL algorithms, as it is more difficult to numerically propagate learning signals across time steps. Accordingly, sparse rewards are natural benchmarks for operator-based algorithms. Across all tasks, Peng's Q(λ) consistently outperforms other baselines. In a few cases, uncorrected n-step also outperforms the baseline TD3 -we speculate that this is because the former propagates the learning signal more efficiently, which is critical for sparse rewards. Compared to uncorrected n-step, Peng's Q(λ) seems to achieve a better trade-off between efficient propagation of learning signals and fixed point biases, which leads to relatively stable and consistent performance gains across all selected benchmark tasks.

Additional deep RL experiments

Maximum-entropy RL. In Appendix I, we show how Peng's Q(λ) could be extended to maximum-entorpy RL [START_REF] Ziebart | Maximum entropy inverse reinforcement learning[END_REF][START_REF] Fox | Taming the noise in reinforcement learning via soft updates[END_REF][START_REF] Haarnoja | Reinforcement learning with deep energy-based policies[END_REF][START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF]. We combine multi-step operators with maximumentropy deep RL algorithms such as SAC [START_REF] Haarnoja | Soft actorcritic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF] and show performance gains over benchmark tasks. See Appendix J for further details.

Ablation study on λ. In Appendix J, we provide an ablation study on the effect of λ. We show that the performance of Peng's Q(λ) depends on the choice of λ. Nevertheless, we find that a single λ can usually lead to fairly uniform performance gains across a large number of benchmarks.

Conclusion

In this paper, we have studied the non-conservative offpolicy algorithm Peng's Q(λ), and shown that while in the worst case its convergence guarantees are less strong than conservative algorithms such as Retrace, convergence guarantees to the optimal policy are recovered when the behavior policy closely tracks the target policy. This has important consequences for deep RL theory and practice, as this condition often holds when agents are trained through replay buffers, and serves to close the gap between the strong empirical performance observed with non-conservative algorithms in deep RL, and their previous lack of theory.

We expect this to have several important consequences for deep RL theory and practice. Firstly, these results make clear that the degree of off-policyness is an important quantity that has real impact on the success of deep RL algorithms, and incorporating quantities related to this into the analysis of off-policy algorithms will be important for developing theoretical understanding of deep RL. Secondly, these findings add weight to growing empirical work highlighting that quantities such as replay buffer size and replay ratio are crucial to the success of deep RL agents [START_REF] Zhang | A deeper look at experience replay[END_REF][START_REF] Daley | Reconciling λ-returns with experience replay[END_REF][START_REF] Fedus | Revisiting fundamentals of experience replay[END_REF], and deserve further attention.

We believe the analysis presented in this paper is an important step towards a deeper understanding of nonconservative methods, and there are several open questions suitable for future work. For example, the convergence guarantee in Theorem 4 requires α ≥ 1 -λ. However we conjecture that this assumption can be lifted. Besides, while we did not analyze the concentrability coefficients of PQL, Scherrer (2014) reports that conservative policy iteration, which is analogous to PQL, has a better concentrability coefficients. Finally, careful error propagation analyses of gap-increasing algorithms [START_REF] Azar | Dynamic policy programming[END_REF][START_REF] Kozuno | Theoretical analysis of efficiency and robustness of softmax and gap-increasing operators in reinforcement learning[END_REF] and policy-update-regularized algorithms [START_REF] Vieillard | Leverage the average: an analysis of KL regularization in reinforcement learning[END_REF] show a slow update of policies confer the stability against errors on algorithms. In PQL with behavior policy updates, we expect a similar result when α takes an intermediate value.

A. Preliminaries for Theoretical Analyses

In this appendix, we explain important notions we used in our theoretical analyses.

Contraction and Monotonicity of Operators. An operator O from a normed space (F, • ) to another normed space (F , | • |) is said to be a contraction if there is a constant c ∈ [0, 1) such that Of -Og ≤ c|f -g|. This constant c is sometimes called as modulus. For example, T :

(R X×A , • ∞ ) → (R X×A , • ∞
) is a contraction with modulus γ. In the main text, we usually meant a contraction under • ∞ and did not always mention which norm is considered.

A related notion is a non-expansion. If an operator O satisfies only Of -Og ≤ |f -g|, it is said to be a non-expansion. For example, P is a non-expansion, as proven later.

Monotonicity is probably the most important property in our analyses. An operator O is said to be monotone if Of ≥ Og for any f and g satisfying f ≥ g. For example, P is monotone: if V ≥ V (point-wisely, i.e., V (x) ≥ V (x) at every x), PV -PV holds too, as one can easily confirm from

(PV -PV )(x, a) = E[V (X 1 ) -V (X 1 )|X 0 = x, A 0 = a] ≥ 0.
Let 1 ∈ F be a constant function taking 1 everywhere. If a linear operator

O : (F, • ∞ ) → (F , • ∞ ) is monotone and satisfies O1 = c1 with a scalar c, we have Of -Og ∞ ≤ c f -g ∞ . Indeed, Of -Og = O(f -g) ≤ O f -g ∞ 1 = c f -g ∞ 1 and Of -Og ≥ -c f -g ∞ 1 imply Of -Og ∞ ≤ c f -g ∞ . Thus, P is non-expansive as P1 = 1. Note that (1 -γλ)(I -γλP π )
-1 is also a non-expansive operator for any π, as one can easily confirm.

B. On an Extension of Theoretical Results to Continuous Action Spaces

In this appendix, we explain how to extend our theoretical results to a case where both the state and action spaces are continuous. We mainly follow Appendix B in [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. We ask interested readers to refer to the textbook.

Notation. Let S and S be Polish spaces. We denote by B(S; c) the set of all Borel-measurable functions from S to a bounded closed interval [-c, c], where c ∈ [0, ∞); throughout this appendix, the Borel σ-algebra is always considered. We denote by P(S) the set of all Borel probability measures on S. We say that a real-valued function f on S is upper semicontinuous (usc) at a point p * if lim sup n→∞ f (p n ) ≤ f (p * ) for any sequence of points (p n ) n≥0 converging to p * . We say that f is usc if it is usc at any point. We denote by U(S; c) the set of all usc functions from S to a bounded closed interval [-c, c], where c ∈ [0, ∞). We say that a stochastic kernel q : S → P(S ) is continuous if lim n→∞ f (p )q(dp |p n ) = f (p )q(dp |p) for any bounded continuous function f and any sequence of points (p n ) n≥0 converging to p.

Main Discussion. We impose the following assumption on MDPs. It is necessary to guarantee that all functions in the analyses are usc, as we shall explain soon.

Assumption 6. The state and action spaces are compact subsets of finite-dimensional Euclidean spaces equipped with Borel σ-algebras. The reward function r is an usc function bounded by r max , and the state transition probability kernel P is continuous.

We first explain that there exists an optimal policy that is a measurable function from the state space X to the action space A. Let V max := r max /(1 -γ). We denote by M : U(X × A; V max ) → U(X; V max ) the max operator defined by (MQ)(x) := max a∈A Q(x, a) for any Q ∈ U(X × A; V max ). Theorem B.5 in [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] guarantees that MQ is usc. Furthermore, Proposition B.4 in [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] guarantees that PMQ is usc. It is easy to confirm that both MQ and PMQ are bounded by V max . Since a sum of usc functions is again usc (Puterman, 1994, Proposition B.1.a), [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] guarantees that [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] guarantees that there exists a measurable function π * : X → A such that Q * (x, π * (x)) = max a∈A Q * (x, a). Accordingly, there exists an optimal policy that is a measurable function from X to A.

r + γPMQ = T Q belongs to U(X × A; V max ). Suppose the recursion Q k+1 := T Q k . Proposition B.1.e in
lim k→∞ Q k = Q * is usc. Proposition B.4 in
From the above discussion, it is easy to confirm that all Q k in the exact version of PQL (3) belong to U(X × A; V max ) given that the behavior policy µ is continuous. Therefore, the proof of Theorem 2 in Appendix E is valid under the assumption that µ is continuous. We note that it is a weak assumption because the behavior policy µ is often continuous in practice. Indeed, an action distribution µ(•|x) is frequently a normal distribution whose mean and diagonal covariance matrix are continuous functions of a state x expressed by, for example, neural networks. As a result, as long as all elements of the diagonal covariance matrix are bounded from below by some constant, the probability density function of µ(•|x) is bounded. Therefore, the dominated convergence theorem can be used to show that µ is continuous. When there is an element of the diagonal covariance matrix converging to 0, this argument does not hold. However, it is a pathological case that usual implementations, such as SpinningUp [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF], try to avoid by value clipping.

For other theoretical results, we need two additional assumptions: (i) all behavior policies µ and µ k are continuous, and (ii) all error functions ε k belong to U(X × A; V max ). As for the assumption (i), it is a weak assumption as noted above.

(See also the following paragraph on the relaxation of π k 's exact greediness.) As for the assumption (ii), it is also a weak assumption: because

Q k+1 approximates (N µ λ ) k Q 0 ∈ U(X × A; V max ),
there is no strong reason to use a function approximator that does not belong to U(X × A; V max ); using a function approximator belonging to U(X × A; V max )

guarantees that ε k = Q k+1 -N µ λ Q k belongs to U(X × A; V max ).
Similar arguments can be made even when the behavior policy is updated, and we can conclude that these assumptions are weak.

We finally mention how to relax the exact greedy assumption that π k ∈ G(Q k ). When the action space is continuous, it is not feasible to find an exact greedy policy even if Q k is continuous. In addition, it is often the case that a policy is expressed by a neural network. However, it is relatively straightforward to extend our theoretical analyses to a case where this exact greedy assumption is relaxed to a δ k -greedy assumption, that is,

π k Q k ≥ MQ k -δ k , where δ k ∈ U(X; V max ).
A similar near-greedy condition is found in, for example, [START_REF] Scherrer | Approximate policy iteration schemes: A comparison[END_REF].

C. A Proof of Lemma 1 (Different Forms of the PQL Operator)

In this appendix, we prove Lemma 1, which provides the following forms of the PQL operator:

N µ,π λ Q = Q + (I -γλP µ ) -1 T λµ+(1-λ)π Q -Q = (I -γλP µ ) -1 (r + γ(1 -λ)P π Q).
We first recall the original PQL operator (1):

N µ,π λ Q := (1 -λ) ∞ n=0 λ n (T µ ) n T π Q.
Note that each term in the sum can be rewritten as

(T µ ) n T π Q = n m=0 γ m (P µ ) m r + γ n+1 (P µ ) n P π Q. Therefore, (1 -λ) ∞ n=0 λ n (T µ ) n T π Q = (1 -λ) ∞ n=0 λ n n m=0 γ m (P µ ) m r + γ n+1 (P µ ) n P π Q = (1 -λ) ∞ n=0 λ n n m=0 γ m (P µ ) m r + ∞ n=0 λ n γ n+1 (1 -λ)(P µ ) n P π Q. Note that (1 -λ) ∞ n=0 λ n n m=0 γ m (P µ ) m r = ∞ n=0 λ n n m=0 γ m (P µ ) m r - ∞ n=0 λ n+1 n m=0 γ m (P µ ) m r = ∞ n=0 λ n n m=0 γ m (P µ ) m r - ∞ n=1 λ n n-1 m=0 γ m (P µ ) m r = ∞ n=0 λ n γ n (P µ ) n r.
Consequently,

(1 -λ) ∞ n=0 λ n (T µ ) n T Q = ∞ n=0 λ n γ n (P µ ) n (r + γ(1 -λ)P π Q) = (I -γλP µ ) -1 (r + γ(1 -λ)P π Q).
The right hand side can be rewritten as follows:

(I -γλP µ ) -1 (r + γ(1 -λ)P π Q) = (I -γλP µ ) -1 (λT µ Q + (1 -λ)T π Q -λP µ Q) = (I -γλP µ ) -1 (λT µ Q + (1 -λ)T π Q -Q + (I -γλP µ )Q) = Q + (I -γλP µ ) -1 (λT µ Q + (1 -λ)T π Q -Q).
This concludes the proof.

D. A Proof of Proposition 5 (HQL's Oscillation)

In this appendix, we prove that under a certain circumstance, HQL oscillates. We prove it by using an example shown in Figure 3. In this MDP, there are two types of states X 1 = {x|x = 1, 2, . . .} and X 2 = {x |x = 1, 2, . . .}. We denote a state in X 1 by x and a state in X 2 by x . There are two actions go and exit. When an agent chooses go at x, it moves to x + 1 with a reward of -1. When an agent chooses exit at x, it moves to x with a reward of 1. At x , any action results in a state transition to the same state x with a reward of 1. Therefore, an agent must exit from x as soon as possible. We assume that λ = 1, γ > 0.5, µ chooses go everywhere, Q 0 (x, exit) = Q µ (x, exit) = 1/(1 -γ), and

Q 0 (x, go) = Q µ (x, go) + δ = -1/(1 -γ) + δ with δ > 2/(1 -γ).
For other state-action pairs, Q 0 = Q µ . As a result, π 0 = µ. (At a state x ∈ X, any policy is effectively the same as µ.)

Step 1. HQL's update can be rewritten as follows [START_REF] Harutyunyan | λ) with off-policy corrections[END_REF]:

Q k+1 := Q k + (I -γλP µ ) -1 (T π k Q k -Q k ) = Q k + (I -γλP µ ) -1 (T µ Q k -Q k + γP(π k -µ)Q k ).
Since π 0 = µ, and µ chooses go everywhere (that is, A t = go for every t in the following equations), we deduce that

Q 1 (x, go) = Q 0 (x, go) + ∞ t=0 γ t E[(T µ Q 0 )(X t , A t ) -Q 0 (X t , A t )|X 0 = x, A 0 = go, µ] = Q µ (x, go) = - 1 1 -γ . Besides, Q 1 (x, exit) = Q 0 (x, exit) = Q µ (x, exit) = 1/(1 -γ). Accordingly, arg max a Q 1 (x, a) = exit, and Q 1 = Q µ .
Step 2. Let us consider what happens at the next iteration. Since µ chooses go everywhere (that is, A t = go for every t in the following equations), we deduce that

Q 2 (x, go) = Q 1 (x, go) + ∞ t=0 γ t E[(T µ Q 1 )(X t , A t ) -Q 1 (X t , A t ) + γ(π 1 Q 1 -µQ 1 )(X t+1 )|X 0 = x, A 0 = go, µ] = Q µ (x, go) + ∞ t=0 γ t E[γ(π 1 Q 1 -µQ 1 )(X t+1 )|X 0 = x, A 0 = go, µ] = Q µ (x, go) + 2γ (1 -γ) 2 > 1 1 -γ = Q µ (x, exit). Besides, Q 2 (x, exit) = Q µ (x, exit) = 1/(1 -γ). Accordingly, arg max a Q 1 (x, a) = go.
Step 3. Now, note that by setting δ in Step 1 to be 2γ/(1 -γ) 2 , the situation is completely the same as the one we considered in Step 1. Accordingly, arg max a Q 3 (x, a) = exit, and Q 3 = Q µ . The situation of the next iteration is completely the same as the one we considered in Step 2. This argument can be repeated forever, and thus, Q k (as well as π k ) oscillates.

E. A Proof of Theorem 2 (PQL's Convergence with a Fixed Behavior Policy)

We define N µ λ as an operator such that

N µ λ Q = N µ,π Q λ Q for any Q ∈ R X×A , where π Q ∈ G(Q).
This operator is analogous to T , whereas N µ,π λ is analogous to T π .

From Lemma 1, we deduce that

N µ λ Q -N µ λ Q = (1 -λ)(I -γλP µ ) -1 (T Q -T Q ) for any Q, Q ∈ R X×A . Because (I -γλP µ )
-1 is linear and monotonic, and satisfies (I -γλP µ )

-1 1 = 1/(1 -γλ), we have that N µ λ Q -N µ λ Q ∞ ≤ (1 -λ) T Q -T Q ∞ /(1 -γλ). As noted in Appendix A, T is a contraction with modulus γ. Therefore, N µ λ Q -N µ λ Q ∞ ≤ γ(1 -λ) Q -Q ∞ /(1 -γλ) = β Q -Q ∞ .
Combining this with Banach's fixed point theorem [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], it is proven that PQL with a fixed behavior policy converges to a unique fixed point with the rate β k . Let Q fixed and π fixed be the fixed point and a greedy policy with respect to the fixed point, respectively. (It will turn out to be

Q fixed = Q λµ+(1-λ)π † and π fixed = π † .) As noted in Section 5.1, Q fixed is the fixed point of λT µ + (1 -λ)T . It is easy to confirm that it is also the fixed point of T λµ+(1-λ)π fixed as π fixed ∈ G(Q fixed ). Therefore, Q fixed = Q λµ+(1-λ)π fixed . As π fixed ∈ G(Q fixed ), Q fixed = T λµ+(1-λ)π fixed Q fixed ≥ T λµ+(1-λ)π Q fixed for
any policy π. Therefore, for any positive integer n, we have that

Q fixed ≥ (T λµ+(1-λ)π ) n Q fixed . As a result, Q λµ+(1-λ)π fixed = Q fixed ≥ Q λµ+(1-λ)π for any π.
This implies that π fixed is π † .

F. Double-loop PQL

In this appendix, we analyze PQL in which N µ k λ is applied multiple times to Q k , and then, the current behavior policy µ k is updated to µ k+1 . (See Appendix E for the definition of N µ λ .) Concretely, we consider the following algorithm:

µ k ∈ G δ k (Q k ) , and Q k+1 := (N µ k λ ) ∞ Q k + ε k , (5)
where δ k ∈ R X is a non-negative function over X, and G δ k (Q k ) is the set of δ k -greedy policies π defined by πQ k ≥ π Q k -δ k for a greedy policy π ∈ G(Q k ). Here, we used a shorthand notation

(N µ k λ ) ∞ Q k := lim n→∞ (N µ k λ ) n Q k . Note
that this algorithm involves a double-loop structure: in the inner loop N µ k λ is repeatedly applied to (N µ k λ ) n Q k , and in the outer loop the Q-function and policies are updated. Hence, we call this algorithm as a doule-loop PQL.

There are two main differences from approximate PQL with behavior policy updates (4): first, the behavior policy is required to be near-greedy rather than a mixture policy; second, the Q-function is updated to

(N µ k λ ) ∞ Q k + ε k rather than N µ k λ Q k + ε k .
As for the first difference, we think that the behavior policy update in (4) is more practical, but we are unsure if Theorem 4 can be extended to double-loop PQL. As for the second difference, this Q-function update is an abstraction of a situation where N µ k λ is applied only finitely many times, and

Q k+1 deviates from (N µ k λ ) ∞ Q k as a result. Because it is impossible to compute (N µ k λ )
∞ Q k in a practical situation, this abstraction is necessary. We note that other errors such as function approximation errors can be also included to ε k .

For this algorithm, we have the following guarantee. Proposition 7. For any non-negative integer k, the following holds:

Q * -Q µ k+1 ≤ 2γ 1 -γ k j=0 γ k-j ε j ∞ 1 + γ(1 + γ) 1 -γ k j=0 γ k-j δ j+1 ∞ 1 + γ k+1 Q * -Q µ0 ∞ . Thus, if δ k ∞ → 0 and ε k ∞ → 0, then Q µ k → Q * . Proof. First let us prove that Q µ k -ε k ∞ 1 ≤ Q k+1 ≤ Q µ k+1 + 1 + γ 1 -γ ε k ∞ 1 + γ 1 -γ δ k ∞ 1. By definition of Q k+1 , Q k+1 -ε k = (N µ k λ ) ∞ Q k ≥ Q λµ k +(1-λ)π =⇒ Q k+1 ≥ Q λµ k +(1-λ)π -ε k ∞ 1
for any policy π, where the first inequality follows from Theorem 2. Now, setting π

= µ k yields Q k+1 ≥ Q µ k -ε k ∞ 1. Next, recall that Q k+1 -ε k = (N µ k λ ) ∞ Q k is a fixed point of λT µ k + (1 -λ)T . Accordingly, Q k+1 -ε k = λT µ k (Q k+1 -ε k ) + (1 -λ)T (Q k+1 -ε k ) ≤ T (Q k+1 -ε k ) ≤ T Q k+1 + γ ε k ∞ 1 ,
where the last inequality follows from the monotonicity of T and -ε k ≤ ε k ∞ . Furthermore, from the fact that

µ k+1 ∈ G δ k+1 (Q k+1 ), we deduce that Q k+1 -ε k ≤ T µ k+1 Q k+1 + γ ε k ∞ 1 + γ δ k ∞ 1. This implies that Q k+1 ≤ T µ k+1 Q k+1 + (1 + γ) ε k ∞ 1 + γ δ k ∞ 1.
By induction on k and the monotinicity of T µ k+1 , we deduce that

Q k+1 ≤ Q µ k+1 + 1 + γ 1 -γ ε k ∞ 1 + γ 1 -γ δ k ∞ 1 .

Now we have

Q * -Q µ k+1 = γP π * Q * -γP π * Q k+1 + γP π * Q k+1 -γP µ k+1 Q k+1 ≤γ δ k+1 ∞ 1 +γP µ k+1 Q k+1 -γP µ k+1 Q µ k+1 ≤ γP π * (Q * -Q k+1 ) + γ δ k+1 ∞ 1 + γP µ k+1 (Q k+1 -Q µ k+1 ) ≤ 1+γ 1-γ ε k ∞ 1+ γ 1-γ δ k+1 ∞ 1 ≤ γ(1 + γ) 1 -γ ε k ∞ 1 + γ(1 + γ) 1 -γ δ k+1 ∞ 1 + γP π * (Q * -Q k+1 ) ≤ 2γ 1 -γ ε k ∞ 1 + γ(1 + γ) 1 -γ δ k+1 ∞ 1 + γP π * (Q * -Q µ k )
By induction on k, we see that

Q * -Q µ k+1 ≤ 2γ 1 -γ k j=0 γ k-j ε j ∞ 1 + γ(1 + γ) 1 -γ k j=0 γ k-j δ j+1 ∞ 1 + (γP π * ) k+1 (Q * -Q µ0 ) . By upper-bounding Q * -Q µ0 by Q * -Q µ0 ∞ , the claimed result is obtained.
G. A Proof of Theorem 3 (PQL's Error Propagation with a Fixed Behavior Policy)

Here, we provide the error propagation analysis of PQL with a fixed behavior policy. While the behavior policy is not fixed in a practical situation, the error propagation analysis of PQL with a fixed behavior policy shows the trade-off between bias and convergence rate of PQL. This result is analogous to trade-offs explained in [START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF] and sheds some light on a fundamental property of PQL.

Definition and Notation. We first recall our problem setting: (approximate) PQL updates its Q-function by

π k ∈ G(Q k ) and Q k+1 := N µ,π k λ Q k + ε k , We know that ε k (x, a) = 0 guarantees the convergence of Q k to Q λµ+(1-λ)π † , where π † is arg max π Q λµ+(1-λ)π .
(See Section 5.1.) Therefore, π K is an approximation of π † , and thus, it is natural to define a loss of using the policy π k rather than π † by V ρ † -V ρ K .

We define the following notations:

• ρ † := λµ + (1 -λ)π † • ρ k := λµ + (1 -λ)π k • d k := Q ρ † -Q k • b k := Q k -T ρ k Q k • A † := γ(1 -λ)(I -γλP µ ) -1 P π † • A k := γ(1 -λ)P π k (I -γλP µ ) -1 • β := γ(1 -λ)/(1 -γλ)
Note that A k is a contraction with respect to L ∞ -norm • ∞ with modulus β. (See Appendix C.)

Proofs. Now we start proofs. The main strategy is the following: we first decompose

V ρ † -V ρ K (≥ 0 since π † is a policy such that Q λµ+(1-λ)π † ≥ Q λµ+(1-λ)π for any policy π) to V ρ † -ρ K Q K and ρ K Q K -V ρ K = ρ K (Q K -Q ρ K ); then we note that V ρ † -ρ K Q K ≤ ρ † (Q ρ † -Q K ) because of π K ∈ G(Q K ) and ρ K = λµ + (1 -λ)π K ; these results tell us that we need upper bounds of Q ρ † -Q K and Q K -Q ρ K , which we shall derive.
We first prove an upper bound of

d K = Q ρ † -Q K .
Lemma 8. For any non-negative integer K, the following holds:

d K ≤ A † K d 0 + K-1 k=0 A † K-k-1 ε k ,
where -1 l=0 f l := 01 for any sequence of functions (f l ) l≥0 .

Proof. From Lemma 1, we may deduce that

d K = Q ρ † -(I -γλP µ ) -1 (r + γ(1 -λ)P π K-1 Q K-1 ) -ε K-1 = (I -γλP µ ) -1 [Q ρ † -γλP µ Q ρ † -r -γ(1 -λ)P π K-1 Q K-1 ] -ε K-1 = (I -γλP µ ) -1 (γP ρ † Q ρ † -γλP µ Q ρ † -γ(1 -λ)P π K-1 Q K-1 ) -ε K-1 = γ(1 -λ)(I -γλP µ ) -1 (P π † Q ρ † -P π K-1 Q K-1 ) -ε K-1 ,
where the last line follows from ρ

† = λµ + (1 -λ)π † . Because π K-1 ∈ G(Q K-1 ), we have P π K-1 Q K-1 ≥ P π † Q K-1 . Furthermore, since (I -γλP µ ) -1 = ∞ t=0 γ t λ t (P µ ) t is monotone, (I -γλP µ ) -1 P π K-1 Q K-1 ≥ (I -γλP µ ) -1 P π † Q K-1 . As a result, d K ≤ γ(1 -λ)(I -γλP µ ) -1 P π † (Q ρ † -Q K-1 ) -ε K-1 = A † d K-1 -ε K-1 .
By induction on K, the claim is proven.

We next prove an upper bound for Q K -Q ρ K . To this end, note that

Q K -Q ρ K = (I -γP ρ K ) -1 (Q K -T ρ K Q K ) = (I -γP ρ K ) -1 b K .
Therefore, we need an upper bound for b K , which is given below.

Lemma 9. For any non-negative integer K, the following holds:

b K ≤ A K-1 • • • A 0 b 0 + K-1 k=0 A K-1 • • • A k+1 (I -γP ρ k )ε k , where A K-1 • • • A K := I and
K ∈ G(Q K ), b K = Q K -r -γλP µ Q K -γ(1 -λ)P π K Q K ≤ (I -γλP µ )Q K -r -γ(1 -λ)P π K-1 Q K .
From Lemma 1, we may deduce that b

K ≤ γ(1 -λ)P π K-1 Q K-1 + (I -γλP µ )ε K-1 -γ(1 -λ)P π K-1 Q K = γ(1 -λ)P π K-1 (Q K-1 -Q K ) + (I -γλP µ )ε K-1 = γ(1 -λ)P π K-1 (I -γλP µ ) -1 (Q K-1 -T ρ K-1 Q K-1 ) + (I -γP ρ K-1 )ε K-1 = A K-1 b K-1 + (I -γP ρ K-1 )ε K-1 .
By induction on K, the claim is proven. Now we are ready to prove an upper bound for V ρ † -V ρ K . It is easy to derive the following two inequalities from the monotonicity of A k and A † :

b K ≤ A K-1 • • • A 0 b 0 ∞ 1 + (1 + γ) K-1 k=0 A K-1 • • • A k+1 ε k ∞ 1 = β K b 0 ∞ 1 + (1 + γ) K-1 k=0 β K-k-1 ε k ∞ 1 , and
d K ≤ A † K d 0 ∞ 1 + K-1 k=0 A † K-k-1 ε k ∞ 1 = β K d 0 ∞ 1 + K-1 k=0 β K-k-1 ε k ∞ 1 . Note that V ρ † -V ρ K = ρ † Q ρ † -ρ K Q K + ρ K Q K -V ρ K ≤ ρ † (Q ρ † -Q K ) + ρ K Q K -V ρ K = ρ † d K + ρ K (I -γP ρ K ) -1 b K .
Therefore, we may deduce that

V ρ † -V ρ K ≤ β K d 0 ∞ + b 0 ∞ 1 -γ 1 + 2 1 -γ K-1 k=0 β K-k-1 ε k ∞ 1, where we used 1 + (1 + γ)/(1 -γ) = 2/(1 -γ). Because V ρ † -V ρ K ≥ 0 and the right hand side is independent of a state, V ρ † -V ρ K ∞ ≤ β K d 0 ∞ + b 0 ∞ 1 -γ + 2 1 -γ K-1 k=0 β K-k-1 ε k ∞ ,
This concludes the proof.

H. A Proof of Theorem 4 (PQL's Error Propagation with Behavior Policy Updates)

Here we provide error propagation analysis of PQL with behavior policy updates. We prove a bound tighter than the one provided in Theorem 4 and derive the one in Theorem 4 as a corollary.5 Concretely, we derive the following bound:

V * -V π K ∞ ≤ ζ K Q * -Q 0 ∞ + ζ K 1 -γ b 0 ∞ + K-1 l=0 2ζ K-l-1 1 -γ ε l ∞ ,
where ζ := 1 -α + αγ. It is not difficult to confirm that ζ ≤ η when α ≥ 1 -λ. Therefore, this bound implies the bound in Theorem 4. (Note that 0.5 ≤ max{λ, 1 -γλ} ≤ 1 and it is negligible in the O notation.)

Definition and Notation. We first recall our problem setting: (approximate) PQL updates its Q-function by

π k ∈ G(Q k ) , µ k = απ k + (1 -α)µ k-1 and Q k+1 := N µ k ,π k λ Q k + ε k ,
where µ -1 is arbitrary.

We define the following notations, some of which differ from those defined in Appendix G:

• ρ k := λµ k + (1 -λ)π k • b k := Q k -T ρ k Q k • d k := Q * -Q k • A k := γ(1 -λ)P π k (I -γλP µ k ) -1 • β := γ(1 -λ)/(1 -γλ) • P * := P π * • T * := T π *
Here we highlighted (by red color texts) differences from the definitions in Appendix G. Note that A k is still a contraction with modulus β.

Proofs. Now we start the proof. The main strategy is the almost same as the one we used in Appendix G: we first decompose

V * -V π K to two components V * -π K Q K and π K Q K -V π K
, and then, we show an upper bound to each of them.

We first prove an upper bound for b k , which turns out to be useful later. Lemma 10. For any non-negative integer k, the following holds:

b k ≤ A k-1 • • • A 0 b 0 + k-1 l=0 A k-1 • • • A l+1 (I -γP ρ l )ε l ,
where A -1 • • • A 0 = I, and -1 l=0 f l := 01 for any sequence of functions (f l ) l≥0 .

Proof

. Because π k ∈ G(Q k ), T ρ k Q k = λT µ k Q k + (1 -λ)T π k Q k ≥ T µ k Q k . Therefore, b k ≤ Q k -T µ k Q k . By the assumption on µ k , T µ k Q k = r + γ(1 -α)P µ k-1 Q k + γαP π k Q k = r + γλP µ k-1 Q k + γ(1 -λ)P π k Q k + γ(α -(1 -λ))(P π k Q k -P µ k-1 Q k ) ≥ r + γλP µ k-1 Q k + γ(1 -λ)P π k Q k ≥ r + γλP µ k-1 Q k + γ(1 -λ)P π k-1 Q k ,
where the third line follows since α

≥ 1 -λ. Consequently b k ≤ Q k -r -γλP µ k-1 Q k -γ(1 -λ)P π k-1 Q k = (I -γλP µ k-1 )Q k -r -γ(1 -λ)P π k-1 Q k .
From Lemma 1, we may deduce that

b k ≤ r + γ(1 -λ)P π k-1 Q k-1 + (I -γλP µ k-1 )ε k-1 -r -γ(1 -λ)P π k-1 Q k = γ(1 -λ)P π k-1 (Q k-1 -Q k ) + (I -γλP µ k-1 )ε k-1 = A k-1 (Q k-1 -T ρ k-1 Q k-1 ) -γ(1 -λ)P π k-1 ε k-1 + (I -γλP µ k-1 )ε k-1 = A k-1 (Q k-1 -T ρ k-1 Q k-1 ) =b k-1 +(I -γP ρ k-1 )ε k-1 ,
where the last line follows from the definition of ρ K-1 = λµ K-1 + (1 -λ)π K-1 . Therefore, by induction on k, we may deduce that

b k ≤ A k-1 • • • A 0 b 0 + k-1 l=0 A k-1 • • • A l+1 (I -γP ρ l )ε l .
This concludes the proof.

We use a simple corollary of this lemma, derived based on the monotonicity of (A k ) k≥0 and (P ρ k ) k≥0 .

Corollary 10.1. For any non-negative integer k, the following holds:

b k ≤ β k b 0 ∞ 1 + (1 + γ) k-1 l=0 β k-l-1 ε l ∞ 1 := bk .
where -1 l=0 f l := 01 for any sequence of functions (f l ) l≥0 .

We next prove an upper bound for Q * -Q K . Lemma 11. For any non-negative integer K, the following holds:

d K ≤ ζ K Q * -Q 0 ∞ + K-1 l=0 ζ K-1-l 1 -α(1 -γλ) 1 -γλ bl + ε l ∞ 1 ,
where ζ := 1 -α + γα, -1 l=0 f l := 01 for any sequence of functions (f l ) l≥0 , and bl is defined in Corollary 10.1.

Proof. We note that

Q K = Q K-1 + (I -γλP µ K-1 ) -1 (T ρ K-1 Q K-1 -Q K-1 ) + ε K-1 = T ρ K-1 Q K-1 -γλP µ K-1 (I -γλP µ K-1 ) -1 b K-1 + ε K-1 .
Let us focus on deriving a lower bound of T ρ K-1 Q K-1 . From the definition of ρ K-1 and µ K-1 ,

T ρ K-1 Q K-1 = (1 -λ)T π K-1 Q K-1 + λT µ K-1 Q K-1 = (1 -λ + αλ)T π K-1 Q K-1 + (1 -α)λT µ K-2 Q K-1 = (1 -λ + αλ)T π K-1 Q K-1 -(1 -α)(1 -λ)T π K-1 Q K-1 + (1 -α)Q K-1 + (1 -α)[λT µ K-2 Q K-1 + (1 -λ)T π K-1 Q K-1 -Q K-1 ] = αT π K-1 Q K-1 + (1 -α)Q K-1 -(1 -α)[Q K-1 -λT µ K-2 Q K-1 -(1 -λ)T π K-1 Q K-1 ] .
Recall that the first step of proving Lemma 10 is showing that b

k ≤ Q k -λT µ k-1 Q k -(1 -λ)T π k Q k .
Therefore the upper bound of b K-1 in the lemma can serve as an upper bound of

Q K-1 -λT µ K-2 Q K-1 -(1 -λ)T π K-1 Q K-1 too. Accordingly, Q * -Q K ≤ Q * -αT π K-1 Q K-1 -(1 -α)Q K-1 + 1 -α(1 -γλ) 1 -γλ bK-1 + ε K-1 ∞ 1 ≤ [(1 -α)I + αγP * ](Q * -Q K-1 ) + 1 -α(1 -γλ) 1 -γλ bK-1 + ε K-1 ∞ 1 .
By induction on K, we deduce that

Q * -Q K ≤ [(1 -α)I + αγP * ] K (Q * -Q 0 ) + K-1 l=0 ζ K-1-l 1 -α(1 -γλ) 1 -γλ bl + ε l ∞ 1 ≤ ζ K Q * -Q 0 ∞ 1 + K-1 l=0 ζ K-1-l 1 -α(1 -γλ) 1 -γλ bl + ε l ∞ 1 .
This concludes the proof.

J.7. Experiment results on maximum-entropy RL

We build on soft actor-critic (SAC) [START_REF] Haarnoja | Soft actorcritic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF] and evaluate algorithmic variants over standard benchmark tasks. For Peng's Q(λ), we use λ = 0.7. In Figure 6 we show the results across all selected benchmark tasks. Peng's Q(λ) generally performs more stably than other baselien variants. This is highlighted by the fact that Peng's Q(λ) always ranks as the top two baselines per each task. As an additional empirical observation, we find that SAC generally performs not as well as TD3 on DM control suites. We speculate that this might be because throughout the experiments we use α = 0.2. An adaptive entropy coefficient might further improve the performance.

J.8. Ablation on λ

In Figure 7, we show the ablation study on the sensitivity of Peng's Q(λ) to its only hyper-parameter λ. We choose λ ∈ {0.3, 0.5, 0.7, 0.9} and examine the performance of the resulting algorithms over DM control suite (sparse rewards). Overall, we see that the best hyper-parameter is achieved λ ≈ 0.7. When λ deviates from this value, its performance is still relatively robust. When λ decreases, we see its performance degrades more drastically than when it increases. Finally, it is worth noting that across all our previous evaluations, we always select λ ∈ {0.7, 0.9} and adopt a single λ for benchmark tasks with the same simulation backend. This shows the robustness of Peng's Q(λ) in practical applications.

Figure 1 .

 1 Figure 1. Performance on tree MDPs. Figure(a) shows how performance (after 10, 000 iterations) changes as a function of tree depth D; Figure(b) shows the learning curves of different operators.

  Figure 1(a), where Peng's Q(λ) with λ = 1 is the only method that finds a policy with non-zero expected return. Similar observations are made in Figure 1(b), where we compare Peng's Q(λ) for various λ under D = 10 (solid lines) and D = 5 (dotted lines)

Figure 2 .

 2 Figure 2. Evaluation of baseline algorithms over standard DM control domains. The first row shows results on standard benchmarks; the second row shows results on sparse reward variants of the benchmarks. Four task names are labeled at the bottom. In each plot, x-axis shows the number of training steps and y-axis shows the performance. In standard benchmarks, Peng's Q(λ) generally performs more stably than other algorithms; in sparse reward benchmarks, Peng's Q(λ) outperforms all other algorithms across all presented tasks.

Figure 3 .

 3 Figure 3. An MDP in which HQL may oscillate.

  := 01 for any sequence of functions (f l ) l≥0 .. Proof. By a simple calculation, and π

Figure 4 .

 4 Figure 4. Evaluation of TD3 baselines over continuous control domains. Each curve corresponds to a baseline algorithm averaged over 5 random seeds. (B) denotes tasks from Bullet physics and (G) denotes tasks from OpenAI gym.

Figure 5 .

 5 Figure 5. Evaluation of TD3 baselines over continuous control domains with sparse rewards. Each curve corresponds to a baseline algorithm averaged over 5 random seeds. (B) denotes tasks from Bullet physics and (G) denotes tasks from OpenAI gym.

Figure 6 .

 6 Figure 6. Evaluation of soft actor-critic (SAC) variants over standard continuous control domains. Each curve corresponds to a baseline algorithm averaged over 5 random seeds. We consider tasks from gym (G), bullet physics (B) and DM control suite (D).

Figure 7 .

 7 Figure 7. Ablation study on the sensitivity of Peng's Q(λ) to the hyper-parameter λ. Each curve corresponds to a choice of λ averaged over 5 random seeds.

  Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. Copyright 2021 by the author(s).

Ioffe,

Table 2 .

 2 Choices of c k and π k in off-policy multi-step operators for control. See Section 3.2 for details. The same abbreviations as those in Table1are used. For brevity, we defined πQ k ∈ G(Q k ). We denote π k (a|x)/µ k (a|x) by ρ k (x, a) and (1 -α) + απQ k (a|x)/µ k (a|x) by ρ k (x, a). α-trace and C-trace look the same in the table, but C-trace adaptively changes α so that the trace length matches to a target trace length.

Note that there may be multiple greedy policies due to ties.

Note that this definition is independent of the choice of πQ.

This algorithm updates the behavior policy after each application of the PQL operator. In Appendix F, we analyze a case where the behavior policy is updated after multiple applications of the PQL operator.

TD3 reasonably echoes the theoretical setup in Section

5.3: both the behavior and target policies are near-greedy policy (slowly) trying to maximize Q k , and Q-value updates are performed by using data obtained by following the behavior policy and stored in the replay buffer.

We found this tighter bound after the submission of the main paper. We intend to include this result in a camera ready version of the main paper if the paper is accepted.

Acknowledgement

We are grateful to all reviewers for their time spent on reviewing this paper and writing feedback. TK was supported by JSPS KAKENHI Grant Numbers 16H06563. TK thanks Prof. Kenji Doya, Dongqi Han, and Ho Ching Chiu at Okinawa Institute of Science and Technology (OIST) for their valuable comments. TK is also grateful to the research support of OIST to the Neural Computation Unit, where TK partially conducted this research. In particular, TK is thankful for OIST's Scientific Computation and Data Analysis section, which maintains a cluster we used for many of our experiments. YHT acknowledges the computational support from Google Cloud Platform.

Now we are ready to prove an upper bound for V * -V π K . Note that from Corollary 10.1 and Lemma 11

We simplify K-1 l=0 ζ K-1-lb l as follows:

where the last line follows from

Using this result and

we deduce that

This concludes the proof.

I. Details on Maximum-entropy RL

The maximum-entropy RL [START_REF] Ziebart | Maximum entropy inverse reinforcement learning[END_REF][START_REF] Fox | Taming the noise in reinforcement learning via soft updates[END_REF][START_REF] Asadi | An Alternative Softmax Operator for Reinforcement Learning[END_REF][START_REF] Haarnoja | Reinforcement learning with deep energy-based policies[END_REF][START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF] formulates that the agent maximizes both cumulative rewards and entropy at the same time. In particular, for a fixed α > 0,

It is then possible to define Bellman operators as well as their multi-step variants as in Section 3. Due to space limit, we postpone their details in Appendix I.

It is straightforward to extend off-policy Q(λ) actor-critic algorithm to the formulation of maximum-entropy RL [START_REF] Fox | Taming the noise in reinforcement learning via soft updates[END_REF][START_REF] Haarnoja | Reinforcement learning with deep energy-based policies[END_REF]. Maximum-entropy actor-critic algorithms also maintain a Q-function Q φ (x, a) along with a stochastic policy π θ (a|x). With off-policy data (x t , a t , r t ) ∞ t=0 , one could modify Equation 7 to recursively compute the Q-function targets as

where the value target Vent (

Contrasting Equation 6 and Equation 7, the major difference is that the Q-function target is augmented with an entropy bonus α td H(π θ -(•|x i+1 )). Given a batch of data (x

)). See Appendix I for the pseudocode of the full algorithm.

In theory, here, one should set α pol = α td = α to ensure that the fixed point is unbiased when the collected data are on-policy µ = π. However, in practice, we find that large α td tends to destabilize the update. In particular, when setting α pol = α td = 0.1 chosen as the default hyper-parameter, multi-step SAC does not learn stably. We hypothesize that this is because when α td > 0, an entropy bonus term is added to the target Q-function at each step (over n ≥ 1 steps), whose numerical scale makes it much more difficult to learn a proper Q-function.

Instead, we find that a stable alternative is to set α td = 0 except at the last time step, where α td = α = 0.2. This greatly stablizes the update as the intermediate entropy bonus is effectively removed. It is of interest to study how such bonus term affects the performance of multi-step algorithms and how to align the practice more consistently with theory.

J. Experiments J.1. Further details on implementations of Peng's Q(λ) Generic off-policy actor-critic deep RL algorithms. We provide pseudocode for generic off-policy actor-critic deep RL algorithms in Algorithm 1. These algorithms maintain a Q-function critic Q φ (x, a) and a policy π θ (x). In general, The algorithm collects data with an exploratory behavior policy µ and saves tuples (x t , a t , r t ) into a replay buffer D. At each training iteration, the critic [START_REF] Silver | Deterministic policy gradient algorithms[END_REF]. Now, we focus on the definition of targets Q target (x, a). Given the transitions (x, a, r, x ), one popular choice (see, e.g., [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF][START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF]) is to compute the target as

where θ -, φ -are delayed copies of θ, φ respectively [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF]. An interpretation is that since the policy follows the deterministic gradient through Q φ (x, a), it serves as an approximate greedy operator π θ (x) ≈ arg max a Q φ (x, a). Note that when A is continuous, the exact greedy operation max a Q φ (x, a) is not tractable. In this sense, the above update is an approximate stochastic estimate of the Bellman operator T Q(x, a).

Algorithm 1 Off-policy Q(λ) actor-critic algorithm Require: policy π θ (x), critic Q φ (x, a), target parameters θ -, φ -and learning rate α while not converged do 1. Collect partial trajectories (x t , a t , r t ) T t=1 under behavior policy µ. 2. Samples B partial trajectories each of length n from the replay buffer D.

Recursive computations of Q-function targets. The target value defined by the Q(λ) operator could be computed recursively. In particular, given an infinite trajectory (x 0 , a 0 , r 0 , x 1 , a 1 , r 1 , ...). Assume that we have a Q-function critic Q φ (x, a). Let Qi be the target value estimate at time step i, then

For continuous action space where computing max a Q(x i , a) is difficult, we propose to replace max a Q φ (x, a) ≈ Q φ (x, π θ (x)). In addition, in practice, it is not feasible to generate trajectories of an infinite length. For a partial trajectory (x 0 , a 0 , r 0 , x 1 , a 1 , r 1 , ...x n ) of length n, we bootstrap the Q-function value at the end of the trajectory as

Then the target at (x 0 , a 0 ) can be recursively computed as

J.2. Implementations and algorithms for continuous control in deep RL Implementation code base. We adapt the base implementations in OpenAI SpinningUp [START_REF] Achiam | Spinning Up in Deep Reinforcement Learning[END_REF]. All algorithmic variants adopt default hyper-parameters from the code base. These include learning rates, batch size, replay buffer size, target network update rules, as well as other missing hyper-parameters.

Deep deterministic policy gradient (DDPG). DDPG [START_REF] 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:

, where θ , φ are delayed versions of θ, φ respectively [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF]. The policy is updated by maximizing

with respect to θ. Both parameters θ, φ are trained with the Adam optimizer [START_REF] Kingma | A method for stochastic optimization[END_REF] 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 deep deterministic policy gradient (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].

Soft actor-critic (SAC). SAC [START_REF] Haarnoja | Soft actorcritic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF] adopts the same training pipeline and architecture as DDPG and TD3. However, the critical difference is that SAC augments the reward functions with state-wise entropy to discourage the policy from collapsing to a deterministic distribution. It also maintains two networks to counter the over-estimation bias as TD3. Please see Appendix I for further backgrounds regarding maximum-entropy RL.

J.3. Further details on baseline operators (algorithms)

Uncorrected n-step. We implement uncorrected n-step as one of the baseline algorithms [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF]. This implements the target Q-functions as Qi = i+n-1 j=i

It is uncorrected because there is no importance sampling ratios that adjust the discrepancy between the π and µ. In continuous control, the maximization operation is replaced by the output of the policy network, i.e. Q φ -(x i+n , π θ -(x i+n ). When n = 1, we recover the one-step baseline of a vanilla baseline algorithm.

Peng's Q(λ). As briefly discussed in the main paper, we implement a version Peng's Q(λ) with finite horizon n. This means that the recursive computation of target defined in Eqn 7 holds until the n-th step, where Qi+n = Q φ -(x i+n , π θ (x i+n )). This is because in practice, trajectories are always truncated and of finite lengths, which implies that at the end of trajectories we need to bootstrap directly from the learned Q-functions.

Retrace. We implement Retrace [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF] as a baseline algorithm for comparison. Retrace computes the Q-function target recursively as

Here, the trace coefficient c i = λ min( π θ (ai|xi) µ(ai|xi) , c) where c is the truncation level. By default, λ = c = 1. The motivation is that the variance is controlled by truncating the importance sampling ratio. As a result of the update, TD3 is not directly compatible with the update because it requires π, µ to be both stochastic. We implement a version of TD3 with a stochastic actor: π θ (a|x) = tanh (µ θ (x) + σ θ (x) • ), where ∼ N (0, I) and tanh(x) = (exp(x)-exp(-x))/(exp(x)+exp(-x)) ∈ (-1, 1). The log probability ln π(a|x) is still tractable and can be analytically computed (see, e.g., similar computations in [START_REF] Haarnoja | Soft actorcritic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF]). The behavior policy µ is implemented as µ(a|x) = tanh (µ θ (x) + σ • ) with a fixed standard deviation parameter σ = 0.1. These hyper-parameters are chosen such that they match the scale of action perturbation in the original TD3 implementation.

Ctrace. Ctrace [START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF] is an adaptive off-policy learning algorithm based on Retrace. Its main idea is to adjust the target policy at evaluation time. Instead of evaluating Q π , the target Q-function is changed to Q απ+(1-α)µ where α ∈ [0, 1] is a trainable coefficient that interpolates target policy and behavior policy. By changing α, Ctrace achieves a trade-off between fixed point bias (against Q π ) and contraction rate. We always adapt α such that the contraction rate of the overall operator matches a particular value Γ. Since we implement a version of Ctrace with finite horizon n, we use the following modified definition of the contraction rate so that the contraction rate ranges from 0 to 1 regardless of n:

where ρ s := π θ (a s |x s )/µ(a s |x s ). Throughout experiments, we set Γ = 0.7. See [START_REF] Rowland | Adaptive tradeoffs in off-policy learning[END_REF] for more comprehensive description of the algorithm.

Tree-backup. Similar to Retrace, algorithms such as tree-backup [START_REF] Precup | Eligibility traces for off-policy policy evaluation[END_REF] also preserve the unbiased fixed point of the operator as Q π . Tree-backup adopts the same recursive computation as Retrace in Eqn 8 except that the trace coefficient is c i = π θ (a i |x i ). However, the tree-backup algorithm was developed for discrete action space alone, where the probability π θ (a i |x i ) ∈ [0, 1]. For continuous control tasks, this is not true because π θ (a|x) is a density. We observe that naive implementations of tree-backup algorithm leads to very unstable update because of the numerical scale of ln π θ (a|x). Empirically, we find that the performance of tree-backup to be very poor on continuous control tasks and we do not include the results.

J.4. Further details on the toy example

At each iteration t of the algorithm, we maintain a Q-function table Q (t) (x, a). Given a sampled trajectory (x t , a t , r t ) D-1 t=0 , the operator (e.g. Retrace or Peng's Q(λ)) constructs targets Q target (x, a). The Q-functions are updated as Q (t+1) (x, a) ← (1 -α)Q (t) (x, a) + αQ target (x, a). Then the policy is updated as π (t) ← (1 -α)π + απ g (Q (t) (x, a)) where π g (Q (t) (x, a)) is the greedy policy with respect to Q (t) (x, a). Throughout experiments, the learning rate is fixed α = 0.1.

When computing the target Q-functions Q target (x, a), we apply the recursive computations introduced in previous sections. This is applied to all state-action pairs along sampled trajectories. At each iteration, the algorithm collects N = 1 trajectory from the MDP.

J.5. Additional evaluations on standard benchmarks

Detailed hyper-parameters. In the main paper, we use n = 5 for all multi-step algorithms to cap the length of the partial trajectories. For Peng's Q(λ), we set λ = 0.9 throughout the experiments.

Further results. See Figure 4 for additional experiments on evaluations over standard benchmarks. We further evaluate TD3 variants over tasks from Bullet physics (B) and OpenAI gym (G). Throughout the experiments, we use n = 5 for all multi-step algorithms to cap the length of the partial trajectories. For Peng's Q(λ), we set λ = 0.7. Overall, Peng's Q(λ) performs fairly stably, though it does not perferm the best per task. Interestingly, Retrace performs fairly well on Ant(G), which is in sharp contrast to its relatively poor performance across other tasks. We no longer include DDPG as a baseline as it is generally considered a slightly less competitive baseline compared to TD3. J.6. Additional evaluations on sparse rewards benchmarks Sparse rewards. We implement delayed rewards as a form of sparse rewards. Delayed reward environment tests algorithms' capability to tackle delayed feedback in the form of sparse rewards [START_REF] Oh | Self-imitation learning[END_REF]. In particular, a standard benchmark environment returns dense reward r t at each step t. Consider accumulating the reward over d consecutive steps and return the sum at the end k steps, i.e. r t = 0 if t mod k = 0 and r t = t τ =t-d+1 r τ if t mod d = 0. Throughout the