summaries: 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. This paper introduces a new Q-learning formalism that helps reduce the bias of single step bootstrapping in Q-learning by learning multiple single step bootstrapping Q functions in parallel. This is accomplished by composing multiple n-step returns, showing that a recursive definition of n-step returns allows each return to be learned using only a single step of bootstrapping instead of at most n steps of bootstrapping. The paper solves the problem of the n-step fixed horizon by additionally composing a gamma discounted Q function that is shifted by n. In the end, the Q function used for behavior still predicts the same values as vanilla Q-learning, but with significantly less bias without a large increase in variance.   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.
abstractText: 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 TemporalDifference 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 shortand 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.
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A. Rusu Joel Veness Marc G. Bellemare Alex Graves Martin A. Riedmiller Andreas Fidjeland Georg Ostrovski Stig Petersen Charles Beattie Amir Sadik Ioannis Antonoglou Helen King Dharshan Kumaran Daan Wierstra Shane Legg Demis Hassabis
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518(7540):529–533,
references.authors: David Silver Thomas Hubert Julian Schrittwieser Ioannis Antonoglou Matthew Lai Arthur Guez Marc Lanctot Laurent Sifre Dharshan Kumaran Thore Graepel
references.title: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play
references.authors: Timothy P. Lillicrap Jonathan J. Hunt Alexander Pritzel Nicolas Heess Tom Erez Yuval Tassa David Silver Daan Wierstra
references.title: Continuous control with deep reinforcement learning
references.venue: In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations,
references.authors: Martin Riedmiller Roland Hafner Thomas Lampe Michael Neunert Jonas Degrave Tom van de Wiele Vlad Mnih Nicolas Heess Jost Tobias Springenberg
references.title: Learning by playing solving sparse reward tasks from scratch
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: Tuomas Haarnoja Sehoon Ha Aurick Zhou Jie Tan George Tucker Sergey Levine
references.title: Learning to walk via deep reinforcement learning
references.venue: In Proceedings of Robotics: Science and Systems,
references.authors: Gabriel Barth-Maron Matthew W. Hoffman David Budden Will Dabney Dan Horgan Dhruva TB Alistair Muldal Nicolas Heess Timothy P. Lillicrap
references.title: Distributed distributional deterministic policy gradients
references.venue: In 6th International Conference on Learning Representations,
references.authors: Vladimir Feinberg Alvin Wan Ion Stoica Michael I. Jordan Joseph E. Gonzalez Sergey Levine
references.title: Model-based value expansion for efficient model-free reinforcement learning
references.venue: CoRR, abs/1803.00101,
references.authors: Joshua Romoff Peter Henderson Ahmed Touati Yann Ollivier Emma Brunskill Joelle Pineau
references.title: Separating value functions across time-scales
references.venue: CoRR, abs/1902.01883,
references.authors: Doina Precup Richard S. Sutton Satinder P. Singh
references.title: Eligibility traces for off-policy policy evaluation
references.venue: Proceedings of the 17th International Conference on Machine Learning ICML,
references.authors: Doina Precup Richard S. Sutton Sanjoy Dasgupta
references.title: Off-policy temporal difference learning with function approximation
references.venue: Proceedings of the 18th International Conference on Machine Learning ICML,
references.authors: Rémi Munos Tom Stepleton Anna Harutyunyan Marc G. Bellemare
references.title: Safe and efficient offpolicy reinforcement learning
references.venue: Advances in Neural Information Processing Systems
references.authors: Jacob Buckman Danijar Hafner George Tucker Eugene Brevdo Honglak Lee
references.title: Sampleefficient reinforcement learning with stochastic ensemble value expansion
references.venue: Advances in Neural Information Processing Systems 31, NeurIPS,
references.authors: Kristopher De Asis J. Fernando Hernandez-Garcia G. Zacharias Holland Richard S. Sutton
references.title: Multi-step reinforcement learning: A unifying algorithm
references.venue: Proceedings of the 32nd AAAI Conference on Artificial Intelligence,
references.authors: J. Fernando Hernandez-Garcia Richard S. Sutton
references.title: Understanding multi-step deep reinforcement learning: A systematic study of the DQN target
references.venue: Deep Reinforcement Learning Workshop (NeurIPS 2018),
references.authors: Harm van Seijen Mehdi Fatemi Romain Laroche Joshua Romoff Tavian Barnes Jeffrey Tsang
references.title: Hybrid reward architecture for reinforcement learning
references.venue: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems,
references.authors: Kristopher De Asis Alan Chan Silviu Pitis Richard S. Sutton Daniel Graves
references.title: Fixed-horizon temporal difference methods for stable reinforcement learning
references.venue: CoRR, abs/1909.03906,
references.authors: Richard S Sutton
references.title: Learning to predict by the methods of temporal differences
references.venue: Machine learning,
references.authors: David Silver Guy Lever Nicolas Heess Thomas Degris Daan Wierstra Martin A. Riedmiller
references.title: Deterministic policy gradient algorithms
references.venue: In Proceedings of the 31th International Conference on Machine Learning, ICML,
references.authors: Scott Fujimoto Herke van Hoof David Meger
references.title: Addressing function approximation error in actor-critic methods
references.venue: Proceedings of the 35th International Conference on Machine Learning, ICML,
references.authors: Hado van Hasselt Arthur Guez David Silver
references.title: Deep reinforcement learning with double qlearning
references.venue: Proceedings of the 30th AAAI Conference on Artificial Intelligence,
references.authors: Susan A. Murphy
references.title: A generalization error for q-learning
references.venue: J. Mach. Learn. Res.,
references.authors: Chi Jin Zeyuan Allen-Zhu Sébastien Bubeck Michael I. Jordan
references.title: Is q-learning provably efficient
references.venue: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems,
references.authors: Michael J. Kearns Satinder P. Singh
references.title: Near-optimal reinforcement learning in polynomial time
references.venue: Machine Learning,
references.authors: Greg Brockman Vicki Cheung Ludwig Pettersson Jonas Schneider John Schulman Jie Tang Wojciech Zaremba
references.title: URL http://arxiv.org/ abs/1606.01540
references.venue: Openai gym. CoRR,
references.authors: Emanuel Todorov Tom Erez Yuval Tassa
references.title: Mujoco: A physics engine for model-based control
references.venue: In IEEE/RSJ International Conference on Intelligent Robots and Systems,
sections.heading: 1 INTRODUCTION
sections.text: 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.
sections.heading: 2 RELATED WORK
sections.text: 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).
sections.heading: 3 BACKGROUND
sections.text: We consider tasks modelled as Markov decision processes (MDP), where an agent executes action at ∈ A in some state st ∈ S following its stochastic policy π. According to the dynamics model M of the environment, the agent transitions into some state st+1 ∈ S and receives scalar reward rt. The agent aims at maximizing the expected long-term return:
  Rπ(st) = Eaj≥t∼π,sj>t∼M T−1∑ j=t γj−trj ∣∣∣∣∣∣st  , (1)
  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:
  Qπ(st, at) = Eaj>t∼π,sj>t∼M T−1∑ j=t γj−trj ∣∣∣∣∣∣st, at  . (2)
  In the following, we abbreviate Eaj>t∼π,sj>t∼M[·|st, at] by Et,π,M[·]. One popular representative of continuous model-free reinforcement learning is the Deep Deterministic Policy Gradient algorithm (DDPG) (Lillicrap et al., 2016). In DDPG, actor µ is a deterministic mapping from states to actions, µ : S 7→ A, representing the actions that maximize the critic Qµ, i.e.
  µ(st) = arg maxaQ µ(st, 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(sj , aj |θQ) and targets yj = rj + γQ′(sj+1, µ′(sj+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):
  ∇θµ ← [ 1
  m ∑ j ∇aQ(s, a|θQ)|s=sj ,a=µ(sj |θµ)∇θµµ(s|θµ), (3)
  and the parameters of the target networks are updated according to:
  θQ ′ ← [ (1− τ)θQ′ + τθQ and θµ′ ← [ (1− τ)θµ′ + τθµ, (4)
  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.
sections.heading: 4 OFF-POLICY MULTI-STEP Q-LEARNING
sections.text: 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.
sections.heading: 4.1 COMPOSITE Q-LEARNING
sections.text: 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.
sections.heading: 4.1.1 TRUNCATED Q-FUNCTIONS
sections.text: In order to formalize the off-policy estimation of n-step returns, assume that n (T − 1) and that (T − 1− t) mod n = 0 for task horizon T . We make use of the following observation:
  Qπ(st, at) = Et,π,M [ rt + γrt+1 + γ 2rt+2 + γ 3rt+3 + · · ·+ γT−1rT−1 ] = Et,π,M
  [t+n−1∑ j=t γj−trj + γn t+2n−1∑ j=t+n γj−(t+n)rj  + · · ·+ γT−n
   T−1∑ j=T−n γj−(T−n)rj ]. (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(st, at) = Et,π,M[ ∑t+n−1 j=t γ
  j−trj ], which we plug into Equation (5):
  Qπ(st, at) = Et,π,M[Q π n(st, at) + γ nQπn(st+n, at+n) + · · ·+ γT−nQπn(sT−n, aT−n)]. (6) Theorem 1. Let Qπ1 (st, at) = rt be the one-step Truncated Q-function and Qπi>1(st, at) = rt + γEt,π,M[Q π i−1(st+1, at+1)] the i-step Truncated Q-function. Then Q π i (st, at) represents the
  truncated return Qπi (st, at) = Et,π,M[ ∑t+i−1 j=t γ j−trj ].
  Following Theorem 1 (the proof can be found in the supplementary), we approximate Qπn(st, at) off-policy via consecutive bootstrapping. Let QTr(·, ·|θQTr) denote a function approximator with parameters θQ
  Tr and n outputs, subsequently called heads, estimating Qπi . Each output Q Tr i boot-
  straps from the prediction of the preceding head, with the first approximating the immediate reward function. The targets are therefore given by:
  yTrj,1 = rj and y Tr j,i>1 = rj + γQ Tr′ i−1(sj+1, µ ′(sj+1|θµ ′ )|θQTr′i−1), (7)
  where µ′ corresponds to the actor maximizing the full Q-value as defined in Section 3. That is, QTr represents evaluations of µ at different stages of truncation and yTrj,i<n serve as intermediate predictions to get yTrj,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 st+c·n of a rollout starting in st. In the following, we describe an approach to achieve an estimation of Equation (6) model-free.
sections.heading: 4.1.2 SHIFTED Q-FUNCTIONS
sections.text: To get an estimation for the remainder of the rollout Qπn:∞ = Et,π,M[γ nQ(st+n, at+n)] after n steps, we use a consecutive bootstrapping formulation of the Q-prediction. Theorem 2. Let Qπ1:∞(st, at) = Et,π,M[γQπ(st+1, at+1)] be the one-step Shifted Q-function and Qπi>1:∞(st, at) = Et,π,M[γQ π i−1:∞(st+1, at+1)] the i-step Shifted Q-function. Then Q π i:∞(st, at) represents the shifted return Qπi:∞(st, at) = Et,π,M[γ iQπ(st+i, at+i)].
  Again, the proof of Theorem 2 can be found in the supplementary. Let QSh(·, ·|θQSh) denote the function approximator estimating the Shifted Q-function Qπn:∞, parameterized by θ
  QSh . 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 QShi therefore become:
  yShj,1 = γQ ′(sj+1, µ ′(sj+1|θµ ′ )|θQ′) and yShj,i>1 = γQSh′i−1(sj+1, µ′(sj+1|θµ ′ )|θQSh′i−1). (8)
  1https://github.com/sfujim/TD3
sections.heading: 4.1.3 COMPOSITION
sections.text: Following the definitions of Truncated and Shifted Q-functions, we can compose the full return. Theorem 3. Let Qπn(st, at) = Et,π,M[ ∑t+n−1 j=t γ
  j−trj ] be the truncated return and Qπn:∞(st, at) = Et,π,M[γ
  nQ(st+n, at+n)] the shifted return. Then Qπ(st, at) = Qπn(st, at) + Qπn:∞(st, at) represents the full return, i.e. Q π(st, at) = Et,π,M[ ∑∞ j=t γ j−trj ].
  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:
  yQj = rj + γ(Q Tr′ n (sj+1, µ ′(sj+1|θµ ′ )|θQTr′n ) +QSh′n (sj+1, µ′(sj+1|θµ ′ )|θQSh′n )), (9)
  approximated by Q(·, ·|θQ) with parameters θQ. Since we have true reward rj , 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 QTr, QSh and Q with function approximator QC(·, ·|θQC ). Let SEC denote the squared error between targets yCj and predictions QC(sj , aj |θQ C ). See Figure 1b for the detailed architecture of the Composite Q-network.
  Each pairQTri +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:
  L = 1 m m∑ j=1
  ( SEC + β 1
  n n∑ i=1 ( Q(sj , aj |θQ)− ( QTri (sj , aj |θQ Tr i ) +QShi (sj , aj |θQ Sh i ) ))2) , (10)
  for batch of size m and with β being the regularization weight. Actor µ is then updated on Q.
sections.heading: 4.2 TD3(∆) AND MVE-TD3
sections.text: 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 Wi as: W1 = Qγ1 and Wi>1 = Qγi −Qγi−1 . (11) 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:
  yγj,1 = rj + γ1Q ′ γ1(sj+1, µ ′(sj+1|θµ ′ )|θQ′γ1 ) and
  yγj,i>1 = (γi − γi−1)Q′γi−1(sj+1, µ′(sj+1|θµ ′ )|θQ ′ γi−1 ) + γiW ′ i (sj+1, µ ′(sj+1|θµ ′ )|θW ′i ),
  (12)
  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 MVETD3. 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.
sections.heading: 5 EXPERIMENTAL RESULTS
sections.text: We evaluate Composite Q-learning in both, the tabular setting and the actor-critic method TD3.
sections.heading: 5.1 TABULAR COMPOSITE Q-LEARNING
sections.text: To analyze the effect of incorporating short-term prediction QTrn 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 103 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.
sections.heading: 5.2 COMPOSITE Q-LEARNING WITH FUNCTION APPROXIMATION
sections.text: 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 · 105 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 · 105 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.
sections.heading: 6 CONCLUSION
sections.text: 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.
sections.heading: A ALGORITHM FOR COMPOSITE TD3
sections.text: A detailed description of Composite DDPG is given in Algorithm 1, where the adjustments of TD3 are omitted for simplicity. In order to transform Algorithm 1 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 critics for each target. Furthermore, actor and target networks have to be updated with delay.
  Algorithm 1: Composite DDPG 1 initialize critic QC , actor µ and targets QC ′, µ′ 2 initialize replay bufferR 3 for episode = 1..E do 4 get initial state s1 5 for t = 1..T do 6 apply action at = µ(st|θµ) + ξ, where ξ ∼ N (0, σ) 7 observe st+1 and rt and save transition (st, at, st+1, rt) inR 8 calculate targets:
  yTrj,1 = rj yTrj,i>1 = rj + γQ Tr′ i−1(sj+1, µ ′(sj+1|θµ ′ )|θQ Tr′ i−1) yShj,1 = γQ ′(sj+1, µ ′(sj+1|θµ ′ )|θQ ′ ) yShj,i>1 = γQ Sh′ i−1(sj+1, µ ′(sj+1|θµ ′ )|θQ Sh′ i−1) yQj = rj + γ(Q Tr′ n (sj+1, µ ′(sj+1|θµ ′ )|θQ Tr′ n ) +QSh′n (sj+1, µ ′(sj+1|θµ ′ )|θQ Sh′ n ))
  yCj = [ yQj , y Tr j,1, y Tr j,i>1, y Sh j,1, y Sh j,i>1 ] 9 update QC on minibatch b of size m fromR according to Equation (10)
  10 update µ on Q 11 adjust parameters of QC ′ and µ′
sections.heading: B ALGORITHM FOR TD3(∆)
sections.text: A detailed description of DDPG(∆) is given in Algorithm 2. The authors suggest the use of n-step samples which is not easily applicable in an off-policy setting. In our experiments, we therefore compare our approach to single-step TD3(∆). To transform DDPG(∆) to TD3(∆), the adjustments as described in Appendix A have to be applied analogously.
  Algorithm 2: DDPG(∆) 1 initialize critic Q∆, actor µ and targets Q∆′, µ′ 2 initialize replay bufferR 3 set discount values γ∆ = (γ0, γ1, . . . , γk)ᵀ 4 for episode = 1..E do 5 get initial state s1 6 for t = 1..T do 7 apply action at = µ(st|θµ) + ξ, where ξ ∼ N (0, σ) 8 observe st+1 and rt and save transition (st, at, st+1, rt) inR 9 calculate targets:
  yγj,1 = rj + γ1Q ′ γ1(sj+1, µ ′(sj+1|θµ ′ )|θQ ′ γ1 ) yγj,i>1 = (γi − γi−1)Q ′ γi−1(sj+1, µ ′(sj+1|θµ ′ )|θQ ′ γi−1 )
  +γiW ′ i (sj+1, µ ′(sj+1|θµ ′ )|θW ′ i )
  10 update Q∆ on minibatch b of size m fromR 11 update µ on Qγk 12 adjust parameters of Q∆′ and µ′
sections.heading: C TRUNCATED Q-FUNCTIONS
sections.text: Theorem 1. Let Qπ1 (st, at) = rt be the one-step Truncated Q-function and Qπi>1(st, at) = rt + γEt,π,M[Q π i−1(st+1, at+1)] the i-step Truncated Q-function. Then Q π i (st, at) represents the
  truncated return Qπi (st, at) = Et,π,M[ ∑t+i−1 j=t γ j−trj ].
  Proof. Proof by induction. Qπ1 (st, at) = rt by definition. The theorem follows from induction step:
  Qπi (st, at) = rt + γEt,π,M [ Qπi−1(st+1, at+1) ] = rt + γEt,π,M
  (t+1)+(i−1)−1∑ j=(t+1) γj−(t+1)rj  = rt + γEt,π,M
   t+i−1∑ j=(t+1) γj−(t+1)rj  = rt + Et,π,M
   t+i−1∑ j=(t+1) γj−trj  = Et,π,M
  t+i−1∑ j=t γj−trj  .
sections.heading: D SHIFTED Q-FUNCTIONS
sections.text: Theorem 2. Let Qπ1:∞(st, at) = Et,π,M[γQπ(st+1, at+1)] be the one-step Shifted Q-function and Qπi>1:∞(st, at) = Et,π,M[γQ π i−1:∞(st+1, at+1)] the i-step Shifted Q-function. Then Q π i:∞(st, at) represents the shifted return Qπi:∞(st, at) = Et,π,M[γ iQπ(st+i, at+i)].
  Proof. Proof by induction. Qπ1:∞(st, at) = Et,π,M[γQ π(st+1, at+1)] by definition. The theorem follows from induction step:
  Qπi:∞(st, at) = Et,π,M [ γQπi−1:∞(st+1, at+1) ] = Et,π,M [ γ(γi−1Qπ(st+1+i−1, at+1+i−1))
  ] = Et,π,M [ γ(γi−1Qπ(st+i, at+i))
  ] = Et,π,M [ γiQπ(st+i, at+i) ] .
sections.heading: E RESOLVING THE MUTUAL RECURSION
sections.text: Theorem 3. Let Qπn(st, at) = Et,π,M[ ∑t+n−1 j=t γ
  j−trj ] be the truncated return and Qπn:∞(st, at) = Et,π,M[γ
  nQ(st+n, at+n)] the shifted return. Then Qπ(st, at) = Qπn(st, at) + Qπn:∞(st, at) represents the full return, i.e. Q π(st, at) = Et,π,M[ ∑∞ j=t γ j−trj ].
  Proof.
  Qπ(st, at) = Q π n(st, at) +Q π n:∞(st, at)
  = Et,π,M t+n−1∑ j=t γj−trj + γ nQπ(st+n, at+n)  = Et,π,M
  t+n−1∑ j=t γj−trj + γ n ( Qπn(st+n, at+n) +Q π n:∞(st+n, at+n) ) = Et,π,M
  t+n−1∑ j=t γj−trj + γ n ( t+2n−1∑ j=t+n γj−t−nrj + γ nQπ(st+2n, at+2n) ) = Et,π,M
  t+n−1∑ j=t γj−trj + t+2n−1∑ j=t+n γj−trj + γ 2nQπ(st+2n, at+2n)  = Et,π,M
  t+2n−1∑ j=t γj−trj + γ 2nQπ(st+2n, at+2n)  . Repeating this process then gives Qπ(st, at) = Et,π,M[ ∑∞ j=t γ j−trj ].
  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.
sections.heading: F TD3 AND TD3(∆) WITH LARGER NETWORKS
sections.text: 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.
sections.heading: G SHALLOW ARCHITECTURE
sections.text: In order to analyze importance of the multi-layered structure reflecting the temporal dependencies between short- and long-term predictions, we compare the architecture used in our experiments to a shallow architecture which includes all predictions as outputs of the last hidden layer for the Walker2d-v2 environment in Figure 9. Based on the results in Appendix F, we reduced the amount of hidden layers to two.
  H INDIVIDUAL COMPARISONS
  For clarity, we provide individual comparisons between Composite TD3 and all baselines.