Off-policy Multi-step Q-learning
Authors: Gabriel Kalweit
Maria Huegle
Joschka Boedecker
Venue:  (2020)
Keywords: Multi-step Learning
Off-policy Learning
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 real-world 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 policy rollout 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(Delta), which we introduce as an off-policy variant of TD(Delta). 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.

Under review as a conference paper at ICLR 2020
OFF-POLICY MULTI-STEP Q-LEARNING
Anonymous authors
Paper under double-bling blind review
ABSTRACT
In the past few years, off-policy reinforcement learning methods have shown promising results in their application for robot control. Deep Q-learning, how- ever, still suffers from poor data-efficiency which is limiting with regard to real- world 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 steps of target-policy rollout w.r.. 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 dunction-approximatio setting with TD3, Model-based Value Expansion and TD3(A). which we introduce as an off-policy variant of TD(A). We show on three simulated robot tasks that Composite TD3 outperforms TD3 as well as sate-of-the-ard off-policy multi-step approaches in terms of data-efficiency.
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 al. 2015: Silver et al., 2018 Lillierap et al., (016), including environments of higher complexity (Riedmiller et al. (0188) and even in first real world applications (Haamojj et al. (211)). Due to its off-policy update, Q-Jearning can leverage transitions collected by any policy which makes it more data-efficient compared to on- policy methods. Deep Q-learning, however, still has very high demand for data samples which limiting with regard to robot applications.
One reason for the low data-efficiency is the long temporal horizon the reward signal has to propa- gate through. Data-efficiency of on-policy Temporal-Differene 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 re-tep 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 has to be set to small value to keep the samples close to the target-policy (Barth-Maron et al. a [0188] Hessel et al.) (2018). To avoid these problems, a dynamics model can used for imaginary roll- outs, 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(A)
(Romoff et al. 2019). In this work, we define model-free Temporal-Difference Difff-reeeeeeee formulation which tollows the idea of multi-step learning while remaining off- tiflppolcy.
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 re- cursive definition of the Q-function for the final algorithm. Second, we evaluate MVE within TD3, leading to MVE-TD3. And third, we introduce (A),, an extension TD(A) to deep Qelarnnig. We discuss related work in Section 2 describe the theoretical background in Section 3 and define Composite Q-learning MVE-TD3 and TD3(A) in Section 4 By breaking down the long-tern tingttrrm re- turn into composition of several short-term predictions, our method increases data-efficency which

---

Under review as a conference paper at ICLR 2020
show in the tabular case and for three simulated robot tasks in Section We then conclude in Section
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; MMnos et al.) 2016). Approaches based on Importance Sampling. however, can come with a vast increase in variance or can be of high cost and not easily applicable to deterministic policies.
One way to remain off ooflpy in multi-step Q-learning is to get the Monte Carlo rollout on the basis of the current target-policy applied to learned dynamics model (Feinberg al. 2018 Buckman et al. 2018). Due to accumulating errors of single-step models, this can lead to severe stability issues the Q-update, which is also the conclusion of Feinberg 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 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 multi- step dynamics model implicitly via consecutive bootstrapping.
Most related to our approach is TD(A) (Romoff et al., 2019). Romoff et al. formalize a Bellman- operator over the differences between value functions of increasing discount values. Their approach on-policy and can therefore benefit directly from n-step returns. We extend TD(A) to the off- policy case below. Q-learning can also be extended to a SARSA-like tree-backup called ((r) (Asis) cet al. 2018 Hernandez
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
the reward and the estimation of value functions for each part of this decomposition which then combined as approximation of the full return. HRA addresses the problem of complex rewards and is thus complementary to our work focusing long time scales. Concurrently to our work, AAsis al. (2019) introduced Fixed Horizon TD-learning, formalizing action-value functions for different horizons in time. In contrast to our work. however, AAsi 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 restrict predictions 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, A in some state 8, S following its stochastic policy æ. According to the dynamics model M of the environment, the agent transitions into some state $141 E S and receives scalar reward ri- The agent aims at maximizing the expected long-term return:
RdT (st) Eagger
rj
where T' is the (possibly infinite) temporal horizon of the MDP and E [0, 1] the discount factor. therefore tries to find n²,, s.t. R=" > RD 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:
(T az) = Ea Eapprrae
rj
St, ar
(2)
In the following, we abbreviate Ee ar] by Er,..MI.). One popular represen- tative of continuous model-free reinforcement learning is the Deep Deterministic Policy Gradi- ent algorithm (DDPG) (Lillicrap et al.] (016). In DDPG, actor μ is a deterministic mapping from states to actions, μ A. representing the actions that maximize the critic Q". i.e.
2

---

Under review as a conference paper at ICLR 2020
Composite
Internediatt Predictions
fully connected layers (500) leaky ReLU)
Q
Q
Q
fully connected
@rer
(500,
Q%
T
(500, lasky Rel.t)
fully
Qu ....4
(a)
(b)
Figure 1: (a) Structure of Composite Q-learning. Target networks are omitted for visibility. Q; denotes the Truncated and Shifted Q-functions at step i and Q the Composite Q-function. In- coming edges yield the targets for the corresponding heads. Edges denoted by y are discounted. (b) Architecture of the Composite Q-network used in our experiments in Section 5.2
((s:) arg max, (se, a). Q and μ are estimated by function approximators Q(:,100) and (1-10)), parameterized by 02 and 0r, The critic is optimized on the mean squared error between predictions Q(sj, ay ay)00) and targets y,, rr + 15 target networks, parameterized by 0² and 0= The parameters of μ are optimized following the deterministic policy gradient theorem (Silver et al. 2014):
))0"), where Q' and jí' are
1 VaQ(s,al
gu ( m
==)) V ((()0)))
(3)
and the parameters of the target networks are updated according to:
8 + (1 (1 - -)) + + and 6" (1 - (1-T)0" + TB",
(4)
with r E 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 be- longing 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-lcarning algorithm, an off-policy multi-step reinforce- ment learning method to enhance data-efficiency, along with MVE-TD3 and TD3(A) baselines.
4.1 COMPOSITE Q- 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 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 e-greedy exploration (Kearns and Singh| 2002). We thus argue that truncated horizons for 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 then combine to the full return with model-free Shifted Q-functions, ap- proach we call Composite Q-learning. while remaining purely off off-policy. Since these quantities cannot be estimated directly from single-step transitions, introduce consecutive bootstrapping
3

---

Under review as a conference paper at ICLR 2020
scheme based on intermediate predictions. For overview, see Figure la The full algorithm is in the appendix. Code based on the implementation of TD: can found in the supplementary.
4.1.1 TRUNCATED Q-FUNCTIONS
In order to formalize the off off-policy estimation of n-step returns, assume that n & (7 1) and that (T - 1 t) mod n 0 for task horizon T. We make use of the following observation:
(81, ax) = Eg,x,. [ra Ti++ + 7rr4t2 + r2+3 +
rr-1
ht--1
2+2n-1
M
Σ
7 (3-133 +
Σ
(-((-n))
j=t+z
(5)
T
s=T-n
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 (T, a.) = M. 1 " which we plug into Equation 5
Q (se: at) = Ei, | + + + (st- attn) +
"Q" (8T OT -n- (6)
Theorem 1. Let Q7 (81, (15s,,0, at) Tt. be the one-step Truncated Q-function and (is1 az) = rt + EE 1 (8241, (441) the i-step Truncated Q-function. Then Qi (st, 0z) represents the truncated return QT (5t, = Ee, -ttiii1 -5-(r]]
Following Theorem 1 (the proof can be found in the supplementary), approximate (T aq) off-policy via consecutive bootstrapping. Let QT ("-""")0 denote function approximator with parameters 0 and n outputs, subsequently called heads, estimating Q.- Each output O boot- straps from the prediction of the preceding head, with the first approximating the immediate reward function. The targets are therefore given by:
v Tj and y =y QQTT (5)+1100 (10001))))1)0")))))
where μ² corresponds the actor maximizing the full Q-value as defined in Section 3 That is, Q"r represents evaluations of μ at different stages of truncation and yaicen serve as intermediate predictions to get y We then only use Q. which implements the full n-step return, 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 8t+en of rollout starting in 8t- In the following, describe an approach to achieve an estimation of Equation ( model-free.
4.1.2 SHIFTED Q-FUNCTIONS
To get an estimation for the remainder of the rollout Q E.....M Q($+4 Q( ac+n)] after n steps, consecutive bootstrapping formulation of the Q-prediction.
Theorem 2. Let Q7. (s),0t) at) MI, (t (8t+1, 0t+1)] ) be the one-step Shifted Q-function and 1 (St, a+) fh..M/1Q. (8t+1, (++1)] the i-step Shifted Q-function. Then Q (st, 0t) represents the shifted return Q (8t, at) = Er,.,Ml*** (8e4s, dz4;)].
Again, the proof of Theorem can be found in the supplementary. Let (s"(,,-100 denote the function approximator estimating the Shifted Q-function Q parameterized by 0인th We can shift the Q Q-prediction by bootstrapping without taking the immediate reward into account, to skip the first n rewards of a target-policy rollout. The Shifted Q-targets for heads Q2ah therefore become:
5 (15 109) and Wi T (1541,16 (5)+110"') 0000"")) (00+))0"))000")))
(8)
http:://giithubb.com//////
4

---

Under review as a conference paper at ICLR 2020
4.1.3 COMPOSITION
Following the definitions of Truncated and Shifted Q-functions, we can compose the full return.
Theorem 3. Let ac) = Ei. 1E " be the truncated return and ae) = M,,... (u the shifted return. Then
= (T ar) +
(St 0e) represents the full return, i.e. Q" (8x, 01) = E,, ?.)
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 in the supplementary. We can thus define the Composite Q-target as:
v r + "(
100%) + QT Sh ( 1100)))
(9)
approximated by Q(: -19) with parameters 09 Since have true reward rj, include it in the target. Please note, that shifting the action-value in time imposes a bottleneck, since relies on the estimation of the full action-value. We therefore jointly estimate Q", Q and Q with function approximator (=,--109" Let SEc denote the squared error between targets of and predictions (s), a,100") See Figure lb for the detailed architecture of the Composite Q-network.
Each pair Q, 2 is 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 the loss penalizing the deviation between the prediction of Q and the 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:
Σ j=1
m
SEc +
Σ i=1
((((s))0)09) - (s), ((F (00)) 2 ag (e1s),a,0007) 100 () (10)
for batch of size and with 3 being the regularization weight. Actor is then updated on Q.
4.2 TD3(A) AND MVE-TD3
Most related to Composite Q-learning are TD(A) (Romotf et al. 2019) and MVE-DDPG (Feinberg al. 2018). In this section, we describe how to extend IT(A) off-policy setting and how to combine MVE and TD3.
TD3(A) Another way to divide the value function into multiple time scales is TD(A) (Romoff et al. 2019). To this point, it has only been applied in on-policy setting. In favor of comparability, we extend TD(A) to Q-learning, yielding TD3(A). The main idea of TD(A) is the combination of
different value functions corresponding to increasing discount values. Let denote a fixed ordered sequence increasing discount values, i.c. delta functions W, as:
(71, 12,-.2... ......, 7,.) h=s22-1- "
We can then define
W1 = Qn and W Qr - -Q
(11)
Let (A. denote the function approximator estimating Qugige Based on the derivations in (Romoff et al. 2019), the targets for Q-learning can be formalized
v = ry + 7i Di (8541, (054100" 100% and 17.00 (1x 7- 7- (#)+1, / (l(8; (8j+ 10 10 + 74 Te (0)" 100))
(12)
which then be used in any Q-learning algorithm. The authors suggest the use of n-step targets within TD(A) which is not easily applicable in an off-policy setting. In our experiments, we there- fore compare our approach single-step TD3(A). 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 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

---

Under review as a conference paper at ICLR 2020
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 in the Q-update, we apply Com- posite Q-learning in the tabular case to the MDP of horizon K given in Figure 2a We compare vanilla Q-learning well as multi-step Q-learning based subtrajectories of the exploratory policy and imaginary rollouts of the target-policy with the true model of the MDP.
Composite Queearning
Sit
sulti-step Q Qlleariing True Model
Trs
Shy
Ongolliy Multi-stop Qutarring
Trs.
Slu
So
Qliearning
S1u
91
-5-
Tranaated and Saiited Q-raiues Sor Esc.
Quwile for (vu.6)
10
-20
sk-
-25
8K-1
Updates
x10#
Updates
x10
(b)
Figure 2: (a) In this MDP of horizon K, the agent ought to arrive at terminal state 8K-1 using actions {a, b, c}. The initial state is so 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 so and action a as estimated by the different approaches over time. Dashed lines indicate convergence the optimal policy. The predicted Truncated Q-values for state so and action with horizons to 4, denoted by Tr,..., Tr,, and predicted Shifted Q-values for state so and action a, denoted by Sh Shi...., Sh4,
the right. Dotted lines indicate the true optimal respective Q-values.
Results for K 20 are depicted in Figure(2] All approaches update the Q-function with learning rate of 10-3 on the same fixed batch of 10 episodes with percentage of 10% non-optimal transi- tions. 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 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 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 learning rate of 10 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 larger learning rate for the Truncated O-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-tern term- predictions yields the most benefit the learning rate for the Shifted Q D-functions can be set to higher value. We believe this to be due to two possible reasons. The higher learning rates for the Truncated Q f-fuctiions might lead to overfitting to the shorter horizons (given that represents easier learning problem compared to the full return), whereas the Shifted Q-functions allow for

---

Under review as a conference paper at ICLR 2020
Compusite Quaaning 9
Composii Quassmins (197)
Shilldd Qukaming
Composite Q larning (10 ?
Shitted Q Jearning (Lo-))
Statted Q louninn (10")
Composite Quauinng (Io-1)
Stalted Q daaarning (10-1)
Quiorzinn
0-
-5
Qualte (ec.))
Quain for (Rc
-00-
-15
15-
-20
-2-
0
2
3
4
5 11
Updates
1100
Updates
01
Queca for (Sxo)
-0-
-20
2
5 -10"
Updais
X100
Uptatts
Figure 3: Results of four individual runs on the MDP with a horizon of = 20 for Composite and Shifted Q-learning, with different learning rates for the Shifted D-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 in all experiments.
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 convergence to wrong action-value which is underlining the importance of truly off- 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 according to a (-test) and grows with increasing horizon, as shown Table[] This in line with the findings of [in al.] (2018) who establish connection between the horizon of MDP and the sample complexity of value estimation.
Table 1: Comparison of convergence speed between tabular Q-learning and tabular Composite Q- learning for exemplary runs on the MDP given in Figure with n
Horizon K
10
20
50
100
Speed up Q-learning
11%
44%
57%
66%
5.2 COMPOSITE Q-LEARNING WITH FUNCTION APPROXIMATION
We evaluate TD3, Composite TD3, MVE-TD3 and TD3(A) on three robot simulation tasks of OpenAl Gym (Brockman et al., 2016) based on MuloCo (Toooroy et al. 2012): Walker2d-v2, Ant-v2 and v2 A visualization of the environments depicted in Figure
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 (10-3), target update (5 10-3) and actor setting (two hidden layers with 400 and 300 neurons and ReLU activation) are the same in the default setting of TD3. We use Gaussian exploration noise with a = 0.15. The critic in Composite Q-learning consists of four layers with 500 neurons and leaky ReL.U activation, the critic in all other
7

---

Under review as a conference paper at ICLR 2020
Compusite Quaaningg "
Compoiit Quoaninn
Composite Q loanning (10
Compostte Q Jeaznizg (1IP)
-G
Groden for (Ac.)
for
-10
-10
Updates
X10
Updetes
X11
Qualte for (tuva)
Queaaa ber (hur)
-00
-00
Updates
X31'
Figure 4: Results of four individual runs on the MDP with horizon of = 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).
approaches and the model in MVE-TD3, with learning rate of 10 has two layers. However, also evaluate TD3 and TD3(A) with the same critic setting as Composite TD3, see Figure g in the supplementary. This corresponds the most stable setting
could find for TD3 with the given subset of MuloCo tasks. For Composite TD3, we set n = 50 and 3 10-1 for Walker2d-v2 and Hopper-v2 and 8 5- 10-5 for Ant-v2. For TD3(A), we use the 7-schedule suggested by the authors, i.e. ?1 and Y>s1 %-1+1 with an upper limit 0.99 RRomoff al. 2019). For
MVE-TD3, we use rollout length of 3, as described in Feinberg et al. 2018).
Data Efficiency We choose the under the learning curve 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 small number of runs, we compare median and interquartile ranges (IQR). As listed in Table 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 transitions, Composite TD3 has 19%, 11 % and 19% larger area under the median learning curve, comparison to vanilla TD3. As depicted in Figure MVE-TD3 is highly sensitive w.r.t. accumulating emrrrs 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 be very effective, the results show for Ant-v2. Based 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 transitions can be seen in Table
experiments, TD3(A)
8

---

Under review as a conference paper at ICLR 2020
Walker2d-v2
Ant-v2
Hopper-v2
Composiite
Composite
MVE:TD3 TD3/A)
Composite
MVE-TDD
TDXA)
TD3
TD3A
3000
1000
Retur
2000
2000
1000
1000
1000
Tr.p
T8
11;
Tho
Teao
Ti;
TTap
Trgo
Trg
Tryp
Tr
Try
TTro
Trao
Tho
Tr
Trro
Trap
Tryo
3.0
2.5
2.5
2.0
2.0
TD-Earr
2.0-
1.-
1.5
1.5
1.0
1.0
1.0
0.5
0.5
0.0
Transit tons
x10
Transitions
110
Transitions
x10
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 rep- resenting 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, for horizon h) as well the TD-error for the complete Q-estimate. Please note that TD-error here means the deviation from the associated target.
Table 2: Normalized area under the median learning curve and IQRs over 11 training runs.
Samples
Method
Walker2d-v2
Ant-v2
Hopper-v2
2 10
TD3
82% (-19, +15)
88% (-20, +19)
84% (-29, +28)
Composite TD3
100% (-11, +15)
100% (-11, +8)
100% (-20, +50)
MVE-TD3
50% (-15, +14)
82% (-5, +10)
86% (-17, +20)
TD3(A)
89% (-26, +34)
97% (-6, +8)
74% (-22, +24)
3 10
TD3
79% (-19, +14)
88% (-16, +13)
78% (-28, +21)
Composite TD3 MVE-TD3 TD3(A)
100% (-10, +12)
100% (-9, +8)
100% (-19, +34)
44% (-16, +12) 87% (-21, +28)
86% (-6, +8)
57% (-13, +18)
94% (-6, +8)
72% (-26, +27)
4 10
TD3 Composite TD3 MVE-TD3 TD3(A)
81% (-20, +11)
89% (-14.
81% (-25, +19)
100% (-10, +10)
100% (-9,
100% (-18, +27)
44% (-16, +12)
88% (-8, +11)
44% (-11, +16)
88% (-16, +22)
95% (-6,+7)
80% (-27, +22)
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, well the TD-errors for the complete -esstimate. 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

---

Under review as a conference paper at ICLR 2020
Table 3: Maximum return of the median learning curve and IQRs over 11 training runs within the considered time frame of 4 10 samples.
Environment
TD3
Composite TD3
MVE-TD3
TD3(A)
Walker2d-v2
3962 (-887, +187)
4391 (-414, +239)
2050 (-703, +524)
4101 (-70, +304)
Ant-v2 2933 (-229, +291)
3172 (-255, +250)
3019 (-322, +625)
3043 (-171, +199)
Hopper-v2
2888 (-460, +169)
3044 (-459, +103)
1081 (-244, +234)
3047 (-474, +172)
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.
32 50
150
10
0000
Reom
2100
1040
1003
Transstict
x100
Transtioon
X10
1.2
SEVRE Losering Chow
1.0
Saendian
10-
0.8
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 regulariza- tion weights & (right). The plots show median and interquartile ranges over 11 training runs, each representing mean evaluation performance over 100 initial states.
Sensitivity to Hyperparameters Lastly, we evaluate influence and 3, exemplary for 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 rather large, however, can slow learning down. The same holds if the regularization weight is set to high value. On the other hand, regularization is needed to keep the predictions in narrow range, since it can lead to stability issues, otherwise.
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 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(A), an off-policy variant of (D))). We showed on three simulated robot tasks that Composite TD3 outperforms vanilla TD3 by 19%. 11% and 19% 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- off-pollcy multi-step learning.
Going forward, the uncertainty estimate based the variance of the Composite Q-network could be of benefit both, update calculation and exploration. We further leave the application of the truncated formulation of other quantities such state change auxiliary costs future work.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-29)) 1992.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, 2015.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre. Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through play. Science, 362(6419):1140- 1144, 2018.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR, 2016.
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom van de Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4344 4353. PMLR, 10-15 Jul 2018.
Tuomas Haarnoja, Sehoon Ha, Aurick Zhou, Jie Tan, George Tucker, and Sergey Levine. Learning to walk via deep reinforcement learning. In Proceedings of Robotics: Science and Systems, 2019.
Gabriel Barth-Maron, Matthew W. Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva TB, Alistair Muldal, Nicolas Heess, and Timothy P. Lillicrap. Distributed distributional deterministic policy gradients. In 6th International Conference Learning Representations, ICLR, 2018.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors. Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), pages 3215-3222. AAAI Press, 2018.
Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael I. Jordan, Joseph Gonzalez, and Sergey Levine. Model-based value expansion for efficient model-free reinforcement learning. CoRR, a03/1803.00011, 2018. /ttt:::/taaiii/e.//////////
www.a.twwi......aaaaoooooo abs/ 00101
Joshua Romoff, Peter Henderson, Ahmed Touati, Yann Ollivier, Emma Brunskill, and Joelle Pineau. Separating value functions across time-scales. CoRR, abs/1902.01883, 2019. URL http://
arxiv. wwwiiv.org/bbe abs 0902 01883
Doina Precup, Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off-policy policy evaluation. In Pat Langley, editor, Proceedings of the 17th International Conference on Machine Learning /CML, pages 759-766. Morgan Kaufmann, 2000.
Doina Precup, Richard S. Sutton, and Sanjoy Dasgupta. Off-policy temporal difference learning with function approximation. In Carla E. Brodley and Andrea Pohoreckyj Danyluk, editors, Proceed- ings of the 18th International Conference on Machine Learning ICML, pages 417-424 Morgan Kaufmann, 2001.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare G. Bellemare. Safe and efficient off- policy reinforcement learning. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29, pages 1046-1054, 2016.
11

---

Under review as a conference paper at ICLR 2020
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bian-Bianci, and Roman Gar- nett, editors, Advances in Neural Information Processing Systems 31, NeurlPSS pages 8234-8244, 2018.
Kristopher De Asis, Fernando Hernandez- Garcia. Zacharias Holland. and Richard S. Sutton. Multi-step reinforcement learning: A unifying algorithm. In Sheila A. Mcllraith and Kilian Q. Weinherger, editors, Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 2902-2909, AAAI Press, 2018.
J. Fermando Hiemandez--Gariaa and Richard S. Sutton. Understanding multi-step deep rein- forcement learning: A systematic study of the DQN target. Deep Reinforcement Learn- ing Workshop (NeurIPS 2018), 2018. URL https: / http:ssttssooooo. www.gooool....oooooooooo cct/view// 20180-22211101111
m/7_mmUU_00 Jm5DxN
Нanm van Seijen, Mehdi Fatemi, Romain Laroche, Joshua Romoff, Tavian Barnes, and Jeffrey Tsang. Hybrid reward architecture for reinforcement learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pages 33322-5402, 2017.
Kristopher De Asis, Alan Chan, Silviu Pitis, Richard S. Sutton, and Daniel Graves. Fixed-horizon temporal difference methods for stable reinforcement learning. CoRR, abs/1909.03906, 2019. URL http:httta/iiiii org/ abs 1909.9..0000 03906)
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin A. Riedmiller. Deterministic policy gradient algorithms. In Proceedings of the 31th International Conference on Machine Learning, ICML, volume 32 of JMLR Workshop and Conference Proceedings, pages 387-395, 2014.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML, volume 80 of Proceedings of Machine Learning Research, pages 1582-1591. PMLR, 2018.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the 30th AAAI Conference on Artificial Intelligence, pages 2094-2100. AAAI Press, 2016.
Susan A. Murphy. A generalization error for q-learning. J. Mach. Learn Res., 6:1073-1097, 2005.
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably effi- cient? In Samy Bengio, Hamna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, pages 4868 4878, 2018
Michael J. Kearns and Satinder P. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49(2-3):209-2333 2002.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. CoRR, abs/1600.01 5400, 2016. URL wtRl/http://axxvv.oom
abs/1606. 01540
Emanuel Todorov. Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In JEEE/RS/ International Conference on Intelligent Robots and Systems, IROS, pages 5026- 5033. IEEE, 2012.
12

---

Under review as a conference paper at ICLR 2020
A ALGORITHM FOR COMPOSITE TD3
A detailed description of Composite DDPG is given in Algorithm D where the adjustments of TD3 are omitted for simplicity. In order to transform Algorithm to its TD3-equivalent, Gaussian policy smoothing has to be added to all targets in Line 8 as well as taking the minimum prediction of two distinct crities for each target. Furthermore, actor and target networks have to be updated with delay.
Algorithm 1: Composite DDPG
initialize critic Q actor and targets Q initialize replay buffer R
episode 1..E do
get initial state $1
for t- 1..f' do
apply action ((s (0*) &. where ~ (0)
observe s++1 and r, and transition (8t; Ots 8t+1, in R.
calculate targets:
Vj.1 Tj
M, = + +70 (1)=::05111 (S551110 (00")10"))1000 (oR!")))
Sh QQ'(s (8541 1 )109)
1 -Q (5s+1 10 1100%-1)
Q ry + 7(( (#5+1, (8541 0" "100%") + Q (f 0r 11000))
5j Mj M..1 M5 15,1 13,0>1
update Q on minibatch b of size m from according to Equation (0
10
update μ on Q adjust parameters of QC and
B ALGORITHM FOR TD3(A)
A detailed description of DDPG(A) is given in Algorithm 2 samples which is not easily applicable in an off-policy setting. our experiments, we therefore compare approach to single-step TD3(A). To transform DDPG(A) to TD3(A), the adjustments as described in Appendix A
The authors suggest the use of n-step
have to applied analogously.
Algorithm 2: (DPG(A)
initialize critic Q actor μ and targets Q initialize replay buffer R
set discount values م (10, .
for episode 1. do
get initial state $1 for f. 1..7 do
apply action (ss (0") E, where o)
observe 8 and r. and transition (8t, ax, 8141, F2) in R. calculate targets:
v7,1 r, + 12 (1441, (1)
f7.111 (m--7-1) 1' (s o (s5+1l0") 1108%
+ / (8 nd 11*))
update Q on minibatch of size from R update μ Q adjust parameters of a and
10
13

---

Under review as a conference paper at ICLR 2020
C TRUNCATED Q-FUNCTIONS
Theorem 1. Let QT ar) Te be the one-step Truncated Q-function and T = Pt + F. (amM(Qi11 1Q%-1 (8141, 01+1)] the i-step Truncated Q-function. Then Q (st, 0+) represents the truncated return (8,, = M., 1 (3)
Proof. Proof by induction. (1 0z) = rı by definition. The theorem follows from induction step:
Q7 ar) = r2. + 7,E,,.MMM
(1-1,001,,0++11
(1+1)((-1)-1
=1 + 77
Σ j=(++1)
70
b+i-1
= =t + E.
Σ gp
(
j=
Hi--
= =t; + E.a.M
Σ ر5
j-+++)
bti-1
E
D SHIFTED Q-FUNCTIONS
Theorem 2. Let (8)00
az) = Et, M (1441100441 be the one-step Shifted Q-function and Pis1000 (8r, az) E, M 1:00 (8++1, ax41)] the i-step Shifted Q-function. Then Q7: (81, ae)
represents the shifted return Q (81, = ("t.ul""""(
Proof. Proof by induction. Q7:0 (st, = (s411 by definition. The theorem follows from induction step:
Q (St: a.) = EIT.. (8411,
ES,T.M ( (14444--1
E (1("==1=0((0 (844::4441) (16
E [ Q²T ((((s:::444)))
E RESOLVING THE MUTUAL RECURSION
Theorem 3. Let (s()) M ( - be the truncated return and Th Ut) Br..MMl""(Sssa axtn]] the shifted return. Then Q (Tt, az) QT ac) + Q (St, (+) represents the full return, i.e. Q# (st, at) (L, 33-br
14

---

Under review as a conference paper at ICLR 2020
Proof.
(St, az) + (8t, ut)
hn=11
-
) + 1² (sttn; attn)
(n at-n) + Q ( (rta)) )
Σ
x rg + nm
14=-1
1+2n-1
-E,x,
Σ
x " +
Σ
p + 7 as+2n)
1=1
j=ton
14n-1
r+2n-1
13 + Σ
" + 7 2t (sc+2m as+2n)
1=
j=t+
f42n-1
Σ
7 + + (s1+2n, ac+2n)
Repeating this process then gives (',,,,,;)) = Er, MM, 25 'rl
Due to the composite structure, the Shifted Q-function represents the long-term sum of partial turns provided by the Truncated Q-function, as opposed to single reward values.
F TD3 AND TD3(A) WITH LARGER NETWORKS
To further analyze the impact of the Composite Q-learning structure, we evaluate TD3 and TD3(A) with the same number of parameters for the critic, as depicted in Figure g The approaches do not seem to make use of the additional capacity and reveal a worse performance in the given time frame.
Walker2d-v2
Ant-v2
Hopper-v2
TD3
TD3(A)
TD3
TD3(A) TD3(A)
TD3
TD3(A)
TD3 4L
TD3(A)
TD3 4L
TD3 4L
TD3(A)
1000
3000
3000
3000
Return
2000
2000
2000
1000
1000
1000
0-
0-
0-
0
0
0
Transitions
x10
Transitions
x10
Transitions
x10
Figure 8: Results for TD3 and TD3(A) with the same number of parameters for the critic as Com- posite TD3, i.c. 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 critic with four layers by 4L.
15

---

Under review as a conference paper at ICLR 2020
G SHALLOW ARCHITECTURE
In order to analyze importance of the multi-layered structure reflecting the temporal dependencies between short- and long-term predictions, compare the architecture used in our experiments to shallow architecture which includes all predictions as outputs of the last hidden layer for the Walker2d-v2 v2 environment in Figure Based on the results in Appendix F. we reduced the amount of hidden layers to two.
Composite TD3
Shallow Composite TD3
fully connected (500, leaky ReI.U)
3000
Return
2000
fully connected (500, leaky ReLU)
1000
0-
Qr Q.
@ ...... -th
2
4 x10
Transitions
(a)
(b)
Figure 9: (a) Results for shallow architecture of the Composite Q-network for the Walker2d-v2 environment. The plots show median and interquartile ranges over 11 training runs, each represent- ing mean evaluation performance over 100 initial states. (b) Architecture of the shallow Composite Q-network.
H INDIVIDUAL COMPARISONS
For clarity, provide individual comparisons between Composite TD3 and all baselines.
Walker20-v2
Ant-v2
Hopper-v2
Compoeite TD3
Composite TD3
Composite TD3
TD3
TD3
TD3
3000
4000
3000
3000
2000
Rotura
2000
1500
2000
1000
500
0
Transisions
10
Transit
Transition
Figure 10: Results for Composite TD3 and TD3 as in Figure
16

---

Under review as a conference paper at ICLR 2020
Walser3d-v2
Ant-v2
Hopper-v2
Composite TD3
Composite MVE-TD3
Composite MVE-TD8
MVE-TD3
3500
4000
2500
Retura
2500
2000
2000
2000
1500
1000
1000
1000
300
500
Transisions
1100
Trunsitions
x10
Transitions
x10*
Figure 11: Results for Composite TD33 and MVE-TD3 as in Figure
Walker2d-v2
Ant-v2
Hopper-v2
Composite TD3
Composite TD3 TD3(A)
Composite TD3
TD3(A)
TDS()
3500
3000
4000
3000
2500
Recura
2000
2000
1000
500
Transisions
10
Transitions
x10
Transitions
x10F
Figure 12: Results for Composite TD3 and TD3(A) as in Figure 6
17


Reviews:
[{"review_id": "HyxxejAhtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "  *Synopsis*:\n  This paper proposes to split the value function into two separately learned components (a short-term truncated value function, and a long-term shifted value function) suggesting the short term truncated returns should learn faster as compared to the tail of the returns. They provide temporal difference formulations for a truncated value function and shifted value function, enabling efficient learning of the two components. They also provide derivations of other similar approaches to the off-policy case. Finally, they compare their algorithm to several approaches on a subset of the MuJoCo tasks, and a novel tabular domain.\n\n  Main Contributions:\n  - An algorithm, Composite Q-learning, which decomposes the value function into a short-term truncated portion and a long-term shifted portion.\n  - Derivation of prior art for off-policy.\n\n  *Review*\n  The paper is generally well written (some suggestions for improved readability can be found below), and provides some nice algorithms for the community. I especially appreciate the author's willingness to derive off-policy variants of related algorithms to compared, as opposed to relegating this to future work which is the typical case. The theory for the truncated and shifted value functions also seems correct at a light check. Overall, I am recommending this paper for a weak accept as I have some concerns over the experimental results that I would like clarified. (specifically C1, Q4, and Q6).\n\n\n  [Q]uestions/[C]larifications/[S]uggestions:\n\n  C1: For the tabular domain, are the reported results over multiple runs? If not, I think it would be worthwhile to do some more runs and provide a significance test.\n\n  C2: It would be beneficial to add some indication what the true value for state s_0 is in the plot (either with a horizontal dotted) for each of the methods (i.e. I would expect Tr0 to converge to a different value compared with composite Q-learning). Also, I'm unsure if you appropriately specified what Tr_0, Tr_1, ... are in the text. I might be missing this, but I think it should be more clear.\n\n  S3: It might be interesting to look at the value of the shifted Q-function for this domain. Also, in the appendix I think it would be worthwhile to include the results for all of the states in the MDP (or a representative subset).\n\n  Q4: What are the default settings for TD3 and how were they set? This is an important detail to include, even if you believe they are well accepted in the field. This will make it easier to reproduce your experiments for future work. I think it seriously harms the paper by not tuning the algorithms appropriately.\n\n  S5: It seems as if you are using an open source implementation of TD3, if this is the case you should state this and give a link to the implementation (if you implemented yourself disregard this)\n\n  Q6: How significant are the results in figure 4, say for Walker2d? From what I understand about IQR, significance is measured based on overlap of the medians with the competing IQRs. For example, if we look at Walker2d much of the Composite TD3 median learning curve is within the IQR of TD3(\\Delta) and there are many points where TD3(\\Delta) is also in the IQR of the Composite TD3. I think portions are significant, but it is hard to appreciate from this plot. What might be useful to get a better sense of the data is to include error bars for the results presented in table 2 and table 3. I think table 3 could also benefit with box plots for each of the domains, just to make the comparison easier. \n\n  C7: I think the claim \"We also showed that composite TD3 is able to achieve state-of-the-art data-efficiency compared...\" is a bit strong, especially given the needed clarifications on the significance of the results and how you set hyperparameters. I would urge the authors to soften this claim, and instead say you provide evidence of composite q-learning's data efficiency as compared to other methods.\n\n\n  *Other comments not taken into consideration in the review*\n\n  - It was quite difficult to read sections 2 and 3 given how dense they are. I would recommend splitting these sections into multiple paragraphs to make the sections more readable.\n\n-----------\nPost discussion/rebuttal:\n\nAfter reviewing the comments from other reviewers and the discussion with R3, I'm inclined to think this paper could use a bit more work. I think the idea is still interesting and worth pursuing, but given some of the new observations and experiments run the paper needs to make more changes than I would find reasonable for acceptance. \n\nThanks again for your hard work, and I look forward to seeing this in a future conference.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgVopXatr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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.\n\nIssues:\n\n1) 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.\n\n2) 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.\n\n3) 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.\n\n4) 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.\n\n5) 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.\n\nSuggestions:\n\n1) 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.\n\n2) 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).\n\n3) 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.\n\n4) 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.\n\n----------\n\nPost-rebuttal:\n\nI 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.\n\nTo detail a few things:\n\n1) 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.\n\n2) 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.\n\n3) 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.\n\nMinor:\n\n1) 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).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlkunYoKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis 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.\n\nReview\n\nI 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.\n\nThe 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.\n\nThe 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.\n\nFor 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.\n\nFinally, 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.\n\n---------\nEdit after discussion and rebuttal phase:\n\nI 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.\n\nI 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose TD updates for Truncated Q-functions and Shifted Q-functions, reflecting short- and long-term predictions, respectively. They show that they can be combined to form an estimate of the full-return, leading to a Composite Q-learning algorithm. They claim to demonstrated improved data-efficiency in the tabular setting and on three simulated robot tasks.

All of the reviewers found the ideas in the paper interesting, however, based on the issues raised by Reviewer 3, everyone agreed that substantial revisions to the paper are necessary to properly incorporate the new results. As a result, I am recommending rejection for this submission at this time. I encourage the authors to incorporate the feedback from the reviewers, and believe that after that is done, the paper will be a strong submission. 
Decision: Reject