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):
This paper proposes the Composite Q-learning algorithm, which combines the algorithmic ideas of using compositional TD methods to truncate the horizon of the return, as well as shift a return in time. They claim that this approach will improve the method*s data efficiency relative to standard Q-learning. They demonstrate its performance relative to Q-learning in a tabular domain, as well as in deep RL domains which use the compositional idea as an off-policy critic. Overall, the paper has interesting algorithmic ideas, but there are critical issues in the evaluation and resulting claims being made. Based on this, I am recommending rejection of the paper. I do think there is value in the compositional idea, but for different reasons outlined in the suggestions. Issues: 1) The truncation of the horizon is not a novel TD formulation, as claimed in the paper. This algorithm is described in the original TD paper (Sutton, 1988) as *prediction by a fixed interval.* Sutton*s group further has a recent paper following up on the fixed-horizon TD (FHTD) idea (De Asis et al., 2019), introducing an off-policy control variant of it. 2) Based on Theorem 1 of the TD(Delta) paper (Romoff et al., 2019), as well as the sample-complexity arguments from the FHTD paper, this compositional algorithm is *exactly* equivalent to standard TD in the tabular setting (and function approximation if value functions don*t share parameters), update for update, assuming that: (1) each value function is initialized identically, and (2) the same step size is used for each value function. An intuition for why is because the accuracy of the shifted action-values depends on the accuracy of the standard TD estimate, and the TD errors can be shown to exactly decompose that of standard TD. Under this, there is no ready improvement in data efficiency due to the fixed-horizon value functions converging quicker. 3) The results in the tabular setting seem to contradict what I described in Issue 2, because compositional Q-learning as presented did converge quicker than standard Q-learning. However, this is misleading in that the other methods used a step size of 1e-3, but the step size of the shifted value functions used, without explanation, a larger step size of 1e-2. The reason for the improved performance is that these values had a step size an order of magnitude larger than the remaining ones, and if one were to use the same step size across all value functions, it would have matched Q-learning exactly. This exact decomposition is supported by how the fixed-horizon value estimates follow Q-learning*s curves exactly for the first h - 1 updates (and will converge to Q-learning*s curve if h approaches infinity), and can further be verified by running the provided code with a step size of 1e-3 for the shifted value functions. Without acknowledging the equivalence when using a consistent step size across value functions, as well as sweeping over step sizes for each method, the results don*t present a fair comparison and significantly misrepresent compositional TD methods. 4) On this observation that it is an exact decomposition of TD, it is particularly an exact decomposition of *one-step* TD, as one-step TD errors are used in the fixed-horizon and shifted value function estimates. This makes it equally biased to a one-step method, and is inconsistent with the use of *multi-step* learning in the literature where information across several time steps is included in the estimate of the return. Truncating and shifting things in time can be contextualized as a form of time-dependent discounting, and adjusting the discount rate isn*t generally viewed as performing multi-step TD. 5) Based on the above, the benefit in the deep RL setting is not convincingly due to what is claimed (as parameters are shared, and a consistent step size is used in the optimizer). Some possible reasons might include the architectural choices in how the network represented the decomposition, as well as the representation learning benefits of predicting many relevant outputs to a task. Suggestions: 1) The precise novelty of the work can be clarified, as the fixed-horizon TD formulation dates back to Sutton (1988), and has been extensively studied in De Asis et al. (2019). As far as I*m aware, there*s novelty in the idea of shifting value functions, reconstructing the full return from decomposed value functions, and introducing a penalty to the loss based on inconsistencies in the value estimates. 2) The motivation and claims of the paper should be revised, as the claimed data efficiency from fixed-horizon values converging quicker isn*t readily true. The resulting deep RL results may need more careful experiments to tease apart why the composition might be helping. For example, it might be useful to compare a different neural network architecture, like having all of the compositional components as outputs from the same, final hidden layer (in comparison with outputting them from intermediate hidden layers). 3) The tabular example needs to be re-worked to ensure a fair comparison between each algorithm. For example, the curves can be presented under the best step size (in terms of some metric, like area under the curve) for each algorithm. While there is an exact equivalence to standard one-step TD methods, a real benefit of the approach is that strictly more information is present to the agent, and the flexibility of being able to use separate step sizes for each value function can be favorable if it can be shown to be better after fairly tuning each algorithm. Shifting the focus toward showing that certain types of value functions are less sensitive to step sizes or work better operating at different time-scales from other components (because this seems to be what*s actually happening in the results) would be a huge plus for this. 4) Because it is using one-step TD errors to estimate each of these components, and is equally biased to one-step TD, it isn*t really a multi-step method. I think it would be better to emphasize the compositional aspect and its increased flexibility, than frame it as a multi-step off-policy method. ---------- Post-rebuttal: I think the additional results post-discussion are good, and are on the right track of the claimed goal of analyzing the algorithm. However, the new results might be contradictory to some of the claims made earlier in the paper, and so a more involved revision seems to be needed. I do believe the algorithm has promise for the reasons teased apart in our discussion, and encourage the authors to improve their paper with these results. To detail a few things: 1) The new results, which now empirically demonstrate the exact equivalence with one-step Q-learning, contradicts some claims about improved data efficiency due to truncated value-functions converging quicker. While meta-parameter selection isn*t the focus, if the choice of meta-parameter is what can make it differ from vanilla Q-learning, and is the key explanation for the improvements, then the analysis should focus on this. 2) Mention of the equivalence only comes up in the experimental results, when it*s a key property of the algorithm. If analysis of the composition is the paper*s focus, acknowledging this property is foundational to any analysis of the method. It could have been shown analytically following the algorithm*s derivation, and would have better justified some of the choices made in the experiments. 3) Being equivalent to running *one-step* Q-learning still makes the *multi-step* learning emphasis appear incorrect, especially when the algorithm can trivially be extended to use actual multi-step TD methods. The title seems to come from interpreting what the composite values represent, but the horizon isn*t what makes a method multi-step, and the compositional components add up to exactly one-step Q-learning*s update. Minor: 1) Arguably one of the most prevalent explanations in the deep RL literature for why one might expect improvements is the multi-task/auxiliary task hypothesis (Jaderberg et al., 2016).