Title: OFF-POLICY MULTI-STEP Q-LEARNING

Abstract: In the past few years, off-policy reinforcement learning methods have shown promising results in their application for robot control. Deep Q-learning, however, still suffers from poor data-efficiency which is limiting with regard to realworld applications. We follow the idea of multi-step TD-learning to enhance data-efficiency while remaining off-policy by proposing two novel Temporal-Difference formulations: (1) Truncated Q-functions which represent the return for the first n steps of a target-policy rollout w.r.t. the full action-value and (2) Shifted Q-functions, acting as the farsighted return after this truncated rollout. We prove that the combination of these short-and long-term predictions is a representation of the full return, leading to the Composite Q-learning algorithm. We show the efficacy of Composite Q-learning in the tabular case and compare our approach in the function-approximation setting with TD3, Model-based Value Expansion and TD3(∆), which we introduce as an off-policy variant of TD(∆). We show on three simulated robot tasks that Composite TD3 outperforms TD3 as well as state-of-the-art off-policy multi-step approaches in terms of data-efficiency.

1. INTRODUCTION:

In recent years, Q-learning (Watkins and Dayan, 1992) has achieved major successes in a broad range of areas by employing deep neural networks (Mnih et al., 2015; Silver et al., 2018; Lillicrap et al., 2016) , including environments of higher complexity (Riedmiller et al., 2018) and even in first real world applications (Haarnoja et al., 2019) . Due to its off-policy update, Q-learning can leverage transitions collected by any policy which makes it more data-efficient compared to onpolicy methods. Deep Q-learning, however, still has a very high demand for data samples which is limiting with regard to robot applications.

One reason for the low data-efficiency is the long temporal horizon the reward signal has to propagate through. Data-efficiency of on-policy Temporal-Difference methods can be enhanced by the use of n-step returns, where a Monte Carlo rollout of length n is combined with a bootstrap of the value function. To employ n-step returns in an off-policy setting, subtrajectories of the exploratory policy have to be stored. These stored multi-step returns, however, will differ from the true value of the target-policy. In order to benefit from n-step data, the replay buffer has to be restricted in size or n has to be set to a small value to keep the samples close to the target-policy (Barth-Maron et al., 2018; Hessel et al., 2018) . To avoid these problems, a dynamics model can be used for imaginary rollouts, the so-called Model-based Value Expansion (MVE) (Feinberg et al., 2018) . Alternatively, the full return can be composed of value functions with increasing discount, an approach called TD(∆) (Romoff et al., 2019) . In this work, we define a model-free Temporal-Difference formulation which follows the idea of multi-step learning while remaining off-policy.

Our contributions are threefold. First, we introduce the Composite Q-learning algorithm. For its formulation, we define Truncated Q-functions, representing the return for the first n steps of a target-policy rollout w.r.t. the full action-value. In addition, we introduce Shifted Q-functions which represent the farsighted return after this truncated rollout. Both are then combined in a mutual recursive definition of the Q-function for the final algorithm. Second, we evaluate MVE within TD3, leading to MVE-TD3. And third, we introduce TD3(∆), an extension of TD(∆) to deep Q-learning. We discuss related work in Section 2, describe the theoretical background in Section 3 and define Composite Q-learning, MVE-TD3 and TD3(∆) in Section 4. By breaking down the long-term return into a composition of several short-term predictions, our method increases data-efficency which we show in the tabular case and for three simulated robot tasks in Section 5. We then conclude in Section 6.

2. RELATED WORK:

In order to correct for the deviation from the current target-policy, several methods suggest the use of Importance Sampling (Precup et al., 2000; 2001; Munos et al., 2016) . Approaches based on Importance Sampling, however, can come with a vast increase in variance or can be of high cost and are not easily applicable to deterministic policies.

One way to remain off-policy in multi-step Q-learning is to get the Monte Carlo rollout on the basis of the current target-policy applied to a learned dynamics model (Feinberg et al., 2018; Buckman et al., 2018) . Due to accumulating errors of single-step models, this can lead to severe stability issues in the Q-update, which is also the conclusion of Feinberg et al. (2018) . The authors suggest to average all intermediate i-step returns to smoothen out the model error, the so-called TD-k trick. In contrast to our work, Feinberg et al. assume to have access to the true reward function. In order to balance the length of the model-assisted rollout, Buckman et al. (2018) couple it with an uncertainty estimate from value function and model ensembles. We alleviate the problem of accumulating error by estimating a multi-step dynamics model implicitly via consecutive bootstrapping.

Most related to our approach is TD(∆) (Romoff et al., 2019) . Romoff et al. formalize a Bellmanoperator over the differences between value functions of increasing discount values. Their approach is on-policy and can therefore benefit directly from n-step returns. We extend TD(∆) to the offpolicy case below. Q-learning can also be extended to a SARSA-like tree-backup called Q(σ) (Asis et al., 2018; Hernandez-Garcia and Sutton, 2018) . However, it is an open question how to adjust this idea to continuous action-spaces and deterministic policies. In the Hybrid Reward Architecture (HRA), van Seijen et al. (2017) suggest a decomposition of the reward and the estimation of value functions for each part of this decomposition which are then combined as an approximation of the full return. HRA addresses the problem of complex rewards and is thus complementary to our work focusing on long time scales. Concurrently to our work, Asis et al. (2019) introduced Fixed Horizon TD-learning, formalizing action-value functions for different horizons in time. In contrast to our work, however, Asis et al. define a consecutive bootstrapping formulation w.r.t. the target policies of the different truncated horizons and not the full return. A first general description of using intermediate predictions in Temporal Differences to restrict predictions to a fixed temporal horizon has been introduced in (Sutton, 1988) .

3. BACKGROUND:

We consider tasks modelled as Markov decision processes (MDP), where an agent executes action a t ∈ A in some state s t ∈ S following its stochastic policy π. According to the dynamics model M of the environment, the agent transitions into some state s t+1 ∈ S and receives scalar reward r t . The agent aims at maximizing the expected long-term return:

EQUATION

)

where T is the (possibly infinite) temporal horizon of the MDP and γ ∈ [0, 1] the discount factor. It therefore tries to find π * , s.t. R π * ≥ R π for all π. If the model of the environment is unknown, model-free methods based on the Bellman Optimality Equation over the so-called action-value can be used:

EQUATION

In the following, we abbreviate E aj>t∼π,sj>t∼M (Lillicrap et al., 2016) . In DDPG, actor µ is a deterministic mapping from states to actions, µ : S → A, representing the actions that maximize the critic Q µ , i.e.

Q Tr 1 + Q Tr 2 • • • Q Tr n r t r t Q Sh 1 Q Sh 2 • • • Q Sh n + Q r t γ γ γ γ γ γ γ Intermediate Predictions Composite Q (a)

st at 2 fully connected layers (500, leaky ReLU) fully connected (500, leaky ReLU) µ(s t ) = arg max a Q µ (s t , a). Q and µ are estimated by function approximators Q(•, •|θ Q ) and µ(•|θ µ ), parameterized by θ Q and θ µ . The critic is optimized on the mean squared error between predictions Q(s j , a j |θ Q ) and targets y j = r j + γQ (s j+1 , µ (s j+1 |θ µ )|θ Q ), where Q and µ are target networks, parameterized by θ Q and θ µ . The parameters of µ are optimized following the deterministic policy gradient theorem (Silver et al., 2014) :

Q Tr 1 Q Tr 2 . . . Q Tr n fully connected (500, leaky ReLU) Q Sh 1 Q Sh 2 . . . Q Sh n Q (b)

EQUATION

and the parameters of the target networks are updated according to:

EQUATION

with τ ∈ [0, 1].

TD3 (Fujimoto et al., 2018) adds three adjustments to vanilla DDPG. First, the minimum prediction of two distinct critics is taken for target calculation to alleviate overestimation bias, an approach belonging to the family of Double Q-learning algorithms (van Hasselt et al., 2016) . Second, Gaussian smoothing is applied to the target-policy, addressing the variance in updates. Third, actor and target networks are updated every d-th gradient step of the critic, to account for the problem of moving targets.

4. OFF-POLICY MULTI-STEP Q-LEARNING:

In this section, we introduce the Composite Q-learning algorithm, an off-policy multi-step reinforcement learning method to enhance data-efficiency, along with MVE-TD3 and TD3(∆) as baselines.

4.1. COMPOSITE Q-LEARNING:

The main motivation behind this work is the assumption that learning values on short time scales can be achieved faster than for the full temporal horizon of a task, which can be prohibitively long.

As Murphy (2005) shows for the fixed-batch fitted Q-iteration case, the number of samples needed to achieve a certain generalization error is exponential in the horizon of the MDP. As discussed in Jin et al. (2018) , Q-learning with UCB-exploration has total regret polynomial in the horizon of the MDP and exponential with -greedy exploration (Kearns and Singh, 2002) . We thus argue that truncated horizons for a fixed MDP translate to lower sample complexity of value-estimation.

Building upon this idea, we estimate the return of n-step rollouts of the target-policy via Truncated Q-functions which we then combine to the full return with model-free Shifted Q-functions, an approach we call Composite Q-learning, while remaining purely off-policy. Since these quantities cannot be estimated directly from single-step transitions, we introduce a consecutive bootstrapping scheme based on intermediate predictions. For an overview, see Figure 1a . The full algorithm is in the appendix. Code based on the implementation of TD31 can be found in the supplementary.

4.1.1. TRUNCATED Q-FUNCTIONS:

In order to formalize the off-policy estimation of n-step returns, assume that n (T -1) and that (T -1t) mod n = 0 for task horizon T . We make use of the following observation:

Q π (s t , a t ) = E t,π,M r t + γr t+1 + γ 2 r t+2 + γ 3 r t+3 + • • • + γ T -1 r T -1 = E t,π,M   t+n-1 j=t γ j-t r j   + γ n   t+2n-1 j=t+n γ j-(t+n) r j   + • • • + γ T -n   T -1 j=T -n γ j-(T -n) r j   .

(5)

That is, we can define the action-value as the combination of partial sums of length n. We can then define the Truncated Q-function as

Q π n (s t , a t ) = E t,π,M [ t+n-1 j=t γ j-t r j ],

which we plug into Equation ( 5):

Q π (s t , a t ) = E t,π,M [Q π n (s t , a t ) + γ n Q π n (s t+n , a t+n ) + • • • + γ T -n Q π n (s T -n , a T -n )]. (6) Theorem 1. Let Q π 1 (s t , a t ) = r t be the one-step Truncated Q-function and Q π i>1 (s t , a t ) = r t + γE t,π,M [Q π i-1 (s t+1 , a t+1 )] the i-step Truncated Q-function. Then Q π i (s t , a t ) represents the truncated return Q π i (s t , a t ) = E t,π,M [ t+i-1 j=t γ j-t r j ].

Following Theorem 1 (the proof can be found in the supplementary), we approximate

Q π n (s t , a t ) off-policy via consecutive bootstrapping. Let Q Tr (•, •|θ Q Tr ) denote a function approximator with parameters θ Q Tr

and n outputs, subsequently called heads, estimating Q π i . Each output Q Tr i bootstraps from the prediction of the preceding head, with the first approximating the immediate reward function. The targets are therefore given by: y Tr j,1 = r j and y Tr j,i>1 = r j + γQ Tr i-1 (s j+1 , µ (s

EQUATION

where µ corresponds to the actor maximizing the full Q-value as defined in Section 3. That is, Q Tr represents evaluations of µ at different stages of truncation and y Tr j,i<n serve as intermediate predictions to get y Tr j,n . We then only use Q Tr n , which implements the full n-step return, as the first part of the composition of the Q-target. Please note that in order to estimate Equation ( 6), the dynamics model would be needed to get s t+c•n of a rollout starting in s t . In the following, we describe an approach to achieve an estimation of Equation ( 6) model-free.

4.1.2. SHIFTED Q-FUNCTIONS:

To get an estimation for the remainder of the rollout

Q π n:∞ = E t,π,M [γ n Q(s t+n , a t+n )] after n steps, we use a consecutive bootstrapping formulation of the Q-prediction. Theorem 2. Let Q π 1:∞ (s t , a t ) = E t,π,M [γQ π (s t+1 , a t+1 )] be the one-step Shifted Q-function and Q π i>1:∞ (s t , a t ) = E t,π,M [γQ π i-1:∞ (s t+1 , a t+1 )] the i-step Shifted Q-function. Then Q π i:∞ (s t , a t ) represents the shifted return Q π i:∞ (s t , a t ) = E t,π,M [γ i Q π (s t+i , a t+i )].

Again, the proof of Theorem 2 can be found in the supplementary. Let

Q Sh (•, •|θ Q Sh ) denote the function approximator estimating the Shifted Q-function Q π n:∞ , parameterized by θ Q Sh .

We can shift the Q-prediction by bootstrapping without taking the immediate reward into account, so as to skip the first n rewards of a target-policy rollout. The Shifted Q-targets for heads Q Sh i therefore become:

y Sh j,1 = γQ (s j+1 , µ (s j+1 |θ µ )|θ Q ) and y Sh j,i>1 = γQ Sh i-1 (s j+1 , µ (s j+1 |θ µ )|θ Q Sh i-1 ). (8) 4.1.3 COMPOSITION

Following the definitions of Truncated and Shifted Q-functions, we can compose the full return.

Theorem 3. Let Q π n (s t , a t ) = E t,π,M [

t+n-1 j=t γ j-t r j ] be the truncated return and

Q π n:∞ (s t , a t ) = E t,π,M [γ n Q(s t+n , a t+n )] the shifted return. Then Q π (s t , a t ) = Q π n (s t , a t ) + Q π n:∞ (s t , a t ) represents the full return, i.e. Q π (s t , a t ) = E t,π,M [ ∞ j=t γ j-t r j ].

The incorporation of truncated returns breaks down the time scale of the long-term prediction by the Shifted Q-function. For details, see the proof of Theorem 3 in the supplementary. We can thus define the Composite Q-target as:

EQUATION

approximated by Q(•, •|θ Q ) with parameters θ Q . Since we have true reward r j , we include it in the target. Please note, that shifting the action-value in time imposes a bottleneck, since it relies on the estimation of the full action-value. We therefore jointly estimate Q Tr , Q Sh and Q with function approximator

Q C (•, •|θ Q C ).

Let SE C denote the squared error between targets y C j and predictions Q C (s j , a j |θ Q C ). See Figure 1b for the detailed architecture of the Composite Q-network.

Each pair Q Tr i +Q Sh i | 1≤i≤n is a complete approximation of the true Q-value. The circular dependency can lead to stability issues, due to the amplification of propagated errors. We add a regularization term to the loss penalizing the deviation between the prediction of Q and the n different Q-pairs to keep estimates in a narrow range. It is implemented as the weighted mean squared error, i.e. the loss function becomes:

EQUATION

for batch of size m and with β being the regularization weight. Actor µ is then updated on Q.

4.2. TD3(∆) AND MVE-TD3:

Most related to Composite Q-learning are TD(∆) (Romoff et al., 2019) and MVE-DDPG (Feinberg et al., 2018) . In this section, we describe how to extend TD(∆) to an off-policy setting and how to combine MVE and TD3.

TD3(∆) Another way to divide the value function into multiple time scales is TD(∆) (Romoff et al., 2019) . To this point, it has only been applied in an on-policy setting. In favor of comparability, we extend TD(∆) to Q-learning, yielding TD3(∆). The main idea of TD(∆) is the combination of different value functions corresponding to increasing discount values. Let γ ∆ denote a fixed ordered sequence of increasing discount values, i.e. γ ∆ = (γ 1 , γ 2 , . . . , γ k ) | γi>1>γi-1 . We can then define delta functions W i as:

EQUATION

) Let Q ∆ (•, •|θ Q ∆ ) denote the function approximator estimating Q γ 1≤i≤k .

Based on the derivations in (Romoff et al., 2019) , the targets for Q-learning can be formalized as:

EQUATION

which can then be used in any Q-learning algorithm. The authors suggest the use of n-step targets within TD(∆) which is not easily applicable in an off-policy setting. In our experiments, we therefore compare our approach to single-step TD3(∆). The algorithm can be found in the appendix.

MVE-TD3:

We also apply Model-based Value Expansion within TD3, subsequently called MVE-TD3. We add Gaussian policy smoothing to the rollout of the model. In contrast to Feinberg et al. (2018) , however, we do not assume to have knowledge about the reward function. Our model therefore approximates both, dynamics and reward.

5. EXPERIMENTAL RESULTS:

We evaluate Composite Q-learning in both, the tabular setting and the actor-critic method TD3.

5.1. TABULAR COMPOSITE Q-LEARNING:

To analyze the effect of incorporating short-term prediction Q Tr n in the Q-update, we apply Composite Q-learning in the tabular case to the MDP of horizon K given in Figure 2a . We compare it to vanilla Q-learning, as well as multi-step Q-learning based on subtrajectories of the exploratory policy and imaginary rollouts of the target-policy with the true model of the MDP. Results for K = 20 are depicted in Figure 2b . All approaches update the Q-function with a learning rate of 10 -3 on the same fixed batch of 10 3 episodes with a percentage of 10% non-optimal transitions. For the multi-step approaches, we set rollout length n = 4. Since there is no generalization among states in the tabular setting, we update the Shifted Q-function with a learning rate of 10 -2 and the Truncated Q-functions with a learning rate of 10 -3 . An evaluation of different learning rates for the Shifted Q-functions is depicted in Figure 3 . We compare Composite Q-learning and vanilla Q-learning to Shifted Q-learning, which corresponds to Q-learning with a one-step shifted target (without approximate n-step returns from a Truncated Q-function). The results show that shifting the value in time alone is slowing down convergence. Precisely, Shifted Q-learning with a learning rate of 1.0 is equivalent to vanilla Q-learning, the same holds for Composite Q-learning with a learning rate of 10 -3 for the Shifted Q-function. The counterpart with different learning rates for the Truncated Q-functions, while keeping the learning rates for the full Q-estimate and Shifted Q-functions fixed, can be seen in Figure 4 . While there is improvement in convergence using a larger learning rate for the Truncated Q-functions, the results show higher variance and less benefit than the Shifted Q-functions in Figure 3 . The results suggest that the interplay between short-and long-term predictions yields the most benefit if the learning rate for the Shifted Q-functions can be set to a higher value. We believe this to be due to two possible reasons. The higher learning rates for the Truncated Q-functions might lead to overfitting to the shorter horizons (given that it represents an easier learning problem compared to the full return), whereas the Shifted Q-functions allow for higher learning rates, since they only have to consider the variability of the distribution over next states leading to decreased variance in their targets. In the experiments in Section 5.2, we show that this can also be achieved by generalization as in the given architecture in Figure 1b . The erroneous updates of on-policy multi-step Q-learning lead to convergence to a wrong action-value which is underlining the importance of truly off-policy learning. However, if the true model can be used for the rollout, this can be really effective. The difference in convergence speed between Q-learning and Composite Q-learning is highly significant (p-value of 4 • 10 -8 according to a t-test) and grows with increasing horizon, as shown in Table 1 . This is in line with the findings of Jin et al. (2018) who establish a connection between the horizon of an MDP and the sample complexity of value estimation.

s 0 s 1 s 2 . . . s K-3 s K-2 s K-1 a, -1 a, -1 a, -1 a, -1 a, -100 b, -2 b, -2 b, -2 b, -2 b, -2 c, -3 c, -3 c, -3 c, -30 c, -3 (a)

Table 1 : Comparison of convergence speed between tabular Q-learning and tabular Composite Qlearning for exemplary runs on the MDP given in Figure 2a with n = 4.

Horizon K 10 20 50 100

Speed up to Q-learning 11% 44% 57% 66%

5.2. COMPOSITE Q-LEARNING WITH FUNCTION APPROXIMATION:

We evaluate TD3, Composite TD3, MVE-TD3 and TD3(∆) on three robot simulation tasks of OpenAI Gym (Brockman et al., 2016) based on MuJoCo (Todorov et al., 2012): Walker2d-v2, Ant-v2 and Hopper-v2 . A visualization of the environments is depicted in Figure 5 .

Parameter Setting Our main focus is on the analysis of the structure of Q-functions and not to achieve maximum possible performance. We therefore keep the main parameters the same across all approaches (the underlying algorithm was TD3 in all cases), since this would lead to another source of potential differences otherwise. Learning rate (10 -3 ), target update (5 • 10 -3 ) and actor setting (two hidden layers with 400 and 300 neurons and ReLU activation) are the same as in the default setting of TD3. We use Gaussian exploration noise with σ = 0.15. The critic in Composite Q-learning consists of four layers with 500 neurons and leaky ReLU activation, the critic in all other approaches and the model in MVE-TD3, with a learning rate of 10 -3 , has two layers. However, we also evaluate TD3 and TD3(∆) with the same critic setting as Composite TD3, see Figure 8 in the supplementary. This corresponds to the most stable setting we could find for TD3 with the given subset of MuJoCo tasks. For Composite TD3, we set n = 50 and β = 10 -4 for Walker2d-v2 and Hopper-v2 and β = 5 • 10 -5 for Ant-v2. For TD3(∆), we use the γ-schedule as suggested by the authors, i.e. γ 1 = 0 and γ i>1 = γi-1+1 2 , with an upper limit of 0.99 (Romoff et al., 2019) . For MVE-TD3, we use a rollout length of 3, as described in Feinberg et al. (2018) .

Data Efficiency:

We choose the area under the learning curve as performance measure, which is a common way to evaluate data-efficiency and learning stability (see e.g. Hessel et al. (2018) ). Since vanilla TD3 can have severe stability issues for a small number of runs, we compare median and interquartile ranges (IQR). As listed in Table 2 , Composite TD3 outperforms TD3, as well as state-of-the-art multi-step approaches, in terms of learning speed throughout training. After the considered time frame of 4 • 10 5 transitions, Composite TD3 has a 19%, 11% and 19% larger area under the median learning curve, in comparison to vanilla TD3. As depicted in Figure 6 , MVE-TD3 is highly sensitive w.r.t. accumulating errors in reward and state prediction, even when applying the TD-k trick. However, if dynamics and reward are estimated with high accuracy, model-based rollouts can be very effective, as the results show for Ant-v2. Based on our experiments, TD3(∆) seems to be less sensitive than MVE-TD3, albeit also less efficient than Composite TD3. The maximum return found by all approaches within 4 • 10 5 transitions can be seen in Table 3 . TD-error Analysis To test our intuition stated in the motivation, we refer to the lower row of Figure 6 which shows the TD-errors for the different stages of truncation, as well as the TD-errors for the complete Q-estimate. All Truncated Q-estimates have lower TD-error throughout learning and it can be seen that the TD-error is consistently higher for longer horizons. This reaffirms our hypothesis that learning is easier on shorter horizons. The Composite Q-target therefore reflects the true action-value faster which is beneficial for Q-learning. Sensitivity to Hyperparameters Lastly, we evaluate the influence of n and β, exemplary for the Walker2d-v2 environment. The results can be seen in Figure 7 . Shorter truncation horizons can lead to faster convergence, but the variance increases. If n is rather large, however, it can slow learning down. The same holds if the regularization weight β is set to a high value. On the other hand, regularization is needed to keep the predictions in a narrow range, since it can lead to stability issues, otherwise.

6. CONCLUSION:

We introduced Composite Q-learning, an off-policy learning method that divides the long-term value into smaller time scales. It combines Truncated Q-functions acting on a short horizon with Shifted Q-functions for the remainder of the rollout. We analyzed the efficacy of Composite Q-learning in the tabular case and showed that the benefit of short-term predictions increases with growing task horizon. We further evaluated MVE-TD3 and introduced TD3(∆), an off-policy variant of TD(∆). We showed on three simulated robot tasks that Composite TD3 outperforms vanilla TD3 by 19%, 11% and 19% in terms of area under the median learning curve. The given results provide evidence that Composite TD3 enhances data-efficiency compared to other approaches in off-policy multi-step learning.

Going forward, the uncertainty estimate based on the variance of the Composite Q-network could be of benefit in both, update calculation and exploration. We further leave the application of the truncated formulation of other quantities such as state change or auxiliary costs as future work.

C TRUNCATED Q-FUNCTIONS

Theorem 1. Let Q π 1 (s t , a t ) = r t be the one-step Truncated Q-function and Q π i>1 (s t , a t ) = r t + γE t,π,M [Q π i-1 (s t+1 , a t+1 )] the i-step Truncated Q-function. Then Q π i (s t , a t ) represents the truncated return Q π i (s t , a t ) = E t,π,M [ t+i-1 j=t γ j-t r j ].

Proof. Proof by induction. Q π 1 (s t , a t ) = r t by definition. The theorem follows from induction step:

Q π i (s t , a t ) = r t + γE t,π,M Q π i-1 (s t+1 , a t+1 ) = r t + γE t,π,M   (t+1)+(i-1)-1 j=(t+1) γ j-(t+1) r j   = r t + γE t,π,M   t+i-1 j=(t+1) γ j-(t+1) r j   = r t + E t,π,M   t+i-1 j=(t+1) γ j-t r j   = E t,π,M   t+i-1 j=t γ j-t r j   .

D SHIFTED Q-FUNCTIONS:

Theorem 2. Let Q π 1:∞ (s t , a t ) = E t,π,M [γQ π (s t+1 , a t+1 )] be the one-step Shifted Q-function and Q π i>1:∞ (s t , a t ) = E t,π,M [γQ π i-1:∞ (s t+1 , a t+1 )] the i-step Shifted Q-function. Then Q π i:∞ (s t , a t ) represents the shifted return Q π i:∞ (s t , a t ) = E t,π,M [γ i Q π (s t+i , a t+i )].

Proof. Proof by induction. Q π 1:∞ (s t , a t ) = E t,π,M [γQ π (s t+1 , a t+1 )] by definition. The theorem follows from induction step: Repeating this process then gives Q π (s t , a t ) = E t,π,M [ ∞ j=t γ j-t r j ].

Q π i:∞ (s t , a t ) = E t,π,M γQ π i-1:∞ (s t+1 , a t+1 ) = E t,π,M γ(γ i-1 Q π (s t+1+i-1 , a t+1+i-1 )) = E t,π,M γ(γ i-1 Q π (s t+i , a t+i )) = E t,π,M γ i Q π (s t+i , a t+i ) .

E RESOLVING THE MUTUAL RECURSION:

Due to the composite structure, the Shifted Q-function represents the long-term sum of partial returns provided by the Truncated Q-function, as opposed to single reward values.

F TD3 AND TD3(∆) WITH LARGER NETWORKS:

To further analyze the impact of the Composite Q-learning structure, we evaluate TD3 and TD3(∆) with the same number of parameters for the critic, as depicted in Figure 8 . The approaches do not seem to make use of the additional capacity and reveal a worse performance in the given time frame. 

:

https://github.com/sfujim/TD3

Figures and Tables:

Figure 1: (a) Structure of Composite Q-learning. Target networks are omitted for visibility. Q • i denotes the Truncated and Shifted Q-functions at step i and Q the Composite Q-function. Incoming edges yield the targets for the corresponding heads. Edges denoted by γ are discounted. (b) Architecture of the Composite Q-network used in our experiments in Section 5.2.

Figure 2: (a) In this MDP of horizon K, the agent ought to arrive at terminal state s K-1 using actions {a, b, c}. The initial state is s 0 and the optimal policy is given in red. (b) Mean results and two standard deviations over 10 runs on the MDP with a horizon of K = 20. The left plot depicts the value of s 0 and action a as estimated by the different approaches over time. Dashed lines indicate convergence to the optimal policy. The predicted Truncated Q-values for state s 0 and action a with horizons 1 to 4, denoted by Tr 1 , . . . , Tr 4 , and predicted Shifted Q-values for state s 0 and action a, denoted by Sh 1 , . . . , Sh 4 , are to the right. Dotted lines indicate the true optimal respective Q-values.

Figure 3: Results of four individual runs on the MDP with a horizon of K = 20 for Composite and Shifted Q-learning, with different learning rates for the Shifted Q-function (denoted by the numbers in parentheses). The learning rates for the full Q-function and for the Truncated Q-functions are set to 10 -3 in all experiments.

Figure 4: Results of four individual runs on the MDP with a horizon of K = 20 for Composite Q-learning, with different learning rates for the Truncated Q-function (denoted by the numbers in parentheses). The learning rates for the full Q-function and for the Shifted Q-functions are set to 10 -3 in all experiments.

Figure 5: Visualization of Walker2d-v2 (left), Ant-v2 (middle) and Hopper-v2 (right).

Figure 6: Results (top) and TD-errors (bottom) for Walker2d-v2 (left), Ant-v2 (middle) and Hopper-v2 (right). The plots show median and interquartile ranges over 11 training runs, each representing mean evaluation performance over 100 initial states. The lower plots show TD-errors over time for the different horizons of the Truncated Q-function (denoted by Tr h for horizon h) as well as the TD-errors for the complete Q-estimate. Please note that TD-error here means the deviation from the associated target.

Figure 7: Results (top) and normalized area under the learning curve (bottom) for Composite TD3 in the Walker2d-v2 environment with different truncation horizons n (left) and different regularization weights β (right). The plots show median and interquartile ranges over 11 training runs, each representing mean evaluation performance over 100 initial states.

t r j + γ n Q π (s t+n , a t+n ) t r j + γ n Q π n (s t+n , a t+n ) + Q π n:∞ (s t+n , a t+n ) t-n r j + γ n Q π (s t+2n , a t+2n ) t r j + γ 2n Q π (s t+2n , a t+2n ) t r j + γ 2n Q π (s t+2n , a t+2n )   .

Figure8: Results for TD3 and TD3(∆) with the same number of parameters for the critic as Composite TD3, i.e. four layers with 500 neurons. The plots show median and interquartile ranges over 11 training runs, each representing mean evaluation performance over 100 initial states. We denote approaches using a critic with four layers by 4L.

[•|s t , a t ] by E t,π,M [•]. One popular representative of continuous model-free reinforcement learning is the Deep Deterministic Policy Gradient algorithm (DDPG)

Table content: <table/>

Normalized area under the median learning curve and IQRs over 11 training runs.

Table content: <table><tr><td>Samples</td><td>Method</td><td>Walker2d-v2</td><td>Ant-v2</td><td>Hopper-v2</td></tr><tr><td>2 • 10 5</td><td>TD3</td><td>82% (-19, +15)</td><td>88% (-20, +19)</td><td>84% (-29, +28)</td></tr><tr><td/><td colspan="4">Composite TD3 100% (-11, +15) 100% (-11, +8) 100% (-20, +50)</td></tr><tr><td/><td>MVE-TD3</td><td>50% (-15, +14)</td><td>82% (-5, +10)</td><td>86% (-17, +20)</td></tr><tr><td/><td>TD3(∆)</td><td>89% (-26, +34)</td><td>97% (-6, +8)</td><td>74% (-22, +24)</td></tr><tr><td>3 • 10 5</td><td>TD3</td><td>79% (-19, +14)</td><td>88% (-16, +13)</td><td>78% (-28, +21)</td></tr><tr><td/><td colspan="2">Composite TD3 100% (-10, +12)</td><td>100% (-9, +8)</td><td>100% (-19, +34)</td></tr><tr><td/><td>MVE-TD3</td><td>44% (-16, +12)</td><td>86% (-6, +8)</td><td>57% (-13, +18)</td></tr><tr><td/><td>TD3(∆)</td><td>87% (-21, +28)</td><td>94% (-6, +8)</td><td>72% (-26, +27)</td></tr><tr><td>4 • 10 5</td><td>TD3</td><td>81% (-20, +11)</td><td>89% (-14, +11)</td><td>81% (-25, +19)</td></tr><tr><td/><td colspan="2">Composite TD3 100% (-10, +10)</td><td>100% (-9, +7)</td><td>100% (-18, +27)</td></tr><tr><td/><td>MVE-TD3</td><td>44% (-16, +12)</td><td>88% (-8, +11)</td><td>44% (-11, +16)</td></tr><tr><td/><td>TD3(∆)</td><td>88% (-16, +22)</td><td>95% (-6, +7)</td><td>80% (-27, +22)</td></tr></table>

Maximum return of the median learning curve and IQRs over 11 training runs within the considered time frame of 4 • 10 5 samples.

Table content: <table><tr><td>Environment</td><td>TD3</td><td>Composite TD3</td><td>MVE-TD3</td><td>TD3(∆)</td></tr><tr><td colspan="4">Walker2d-v2 3962 (-887, +187) 4391 (-414, +239) 2050 (-703, +524)</td><td>4101 (-70, +304)</td></tr><tr><td>Ant-v2</td><td colspan="4">2933 (-229, +291) 3172 (-255, +250) 3019 (-322, +625) 3043 (-171, +199)</td></tr><tr><td>Hopper-v2</td><td colspan="4">2888 (-460, +169) 3044 (-459, +103) 1081 (-244, +234) 3047 (-474, +172)</td></tr></table>

Theorem 3. Let Q π n (s t , a t ) = E t,π,M [ Q π (s t , a t ) = Q π n (s t , a t ) + Q π n:∞ (s t , a t ) = E t,π,M

Table content: <table><tr><td>Proof.</td></tr><tr><td>t+n-1</td></tr><tr><td>j=t</td></tr></table>

Peer review (iclr2020):
Summary This paper introduces a new Q-learning formalism that helps reduce the bias of single step bootstrapping in Q-learning by learning multiple single step bootstrapping Q functions in parallel. This is accomplished by composing multiple n-step returns, showing that a recursive definition of n-step returns allows each return to be learned using only a single step of bootstrapping instead of at most n steps of bootstrapping. The paper solves the problem of the n-step fixed horizon by additionally composing a gamma discounted Q function that is shifted by n. In the end, the Q function used for behavior still predicts the same values as vanilla Q-learning, but with significantly less bias without a large increase in variance. Review I find this paper to be novel and insightful, the proposed algorithm is well supported theoretically and reasonably well supported empirically. I appreciated the careful demonstration on the smaller MDP with tabular features, showing the effects of multi-step Q-learning and clearly demonstrating the bias due to not truly using an off-policy formulation. I find that the demonstrations on the larger environments appear promising and suggest that composite multi-step Q-learning is a promising direction. The error bars in the larger demonstrations, Figure 4, make it difficult to distinguish any meaningful differences between the algorithms. I appreciate that results are averaged over 11 runs, fortunately far more than seems to be standard at the moment, but still the amount of variance makes it difficult to say anything statistically. Table 2, then shows a reduction of the results but without mention of variance. It would be useful to include error measurements (perhaps the standard error over runs) to Table 2 to see the statistical significance of those results. Based on Figure 4, my guess is that there is negligible difference statistically. The parameter sensitivity curves for the Walker2d domain also demonstrate that it is difficult to say anything meaningful about each parameter choice. Running a larger number of parameter settings would help to establish a clear pattern, or running each parameter setting for more independent runs could have allowed more significant results. The variance exhibited by one value in the regularization sensitivity curve is alone extremely interesting; perhaps using a different visualization that allowed more clear comparisons of the variance over independent runs would further motivate the utility of the regularization parameter. I think these results are interesting, but as presented do not sufficiently highlight the differences between the proposed algorithm and its competitors. For the experiment in Figure 2, why not include multi-step Q-learning with importance sampling corrections on the later steps? I believe this would have fixed the bias issue, though clearly would be a tradeoff for high variance. I think this would make for a more convincing argument. Additionally, the caption does not well explain what the four green lines at the top of the plot represent. It was difficult to interpret the plot on the first pass of the paper because of this omission. Regardless, I find the results in Figure 2 to be otherwise intriguing. Finally, the choice of meta-parameters in this paper could negatively impact results in favor of the competitor algorithms. By choosing to fix meta-parameters based on the defaults of a competitor, this could be harmfully biasing the proposed algorithm by preventing it from choosing a better stepsize. In fact, I would suspect that the proposed algorithm would exhibit lower variance updates than TD3, meaning it could potentially take advantage of higher stepsizes. This omission makes the claims of this paper weaker than they could possibly be, leaving a slight hole in the research. --------- Edit after discussion and rebuttal phase: I read the in-depth discussion between the authors and R3 and looked at the edits to the draft. I agree with the other reviewers on the basis of understanding the importance of meta-parameter selection. During the initial review, I found the ideas of the paper interesting enough to largely out-weigh the importance of a careful meta-parameter study. After R3*s demonstration that there were indeed flaws with the results under the current meta-parameter selections, I think the best course of action would be to reject the paper in its current form. I still strongly believe there is a place in the literature for this paper, so I hope to see this paper again at the next conference.