Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: This paper proposes the Composite Q-learning algorithm, which combines the algorithmic ideas of using compositional TD methods to truncate the horizon of the return, as well as shift a return in time. They claim that this approach will improve the method's data efficiency relative to standard Q-learning. They demonstrate its performance relative to Q-learning in a tabular domain, as well as in deep RL domains which use the compositional idea as an off-policy critic.

Overall, the paper has interesting algorithmic ideas, but there are critical issues in the evaluation and resulting claims being made. Based on this, I am recommending rejection of the paper. I do think there is value in the compositional idea, but for different reasons outlined in the suggestions.

Issues:

1) The truncation of the horizon is not a novel TD formulation, as claimed in the paper. This algorithm is described in the original TD paper (Sutton, 1988) as "prediction by a fixed interval." Sutton's group further has a recent paper following up on the fixed-horizon TD (FHTD) idea (De Asis et al., 2019), introducing an off-policy control variant of it.

2) Based on Theorem 1 of the TD(\Delta) paper (Romoff et al., 2019), as well as the sample-complexity arguments from the FHTD paper, this compositional algorithm is *exactly* equivalent to standard TD in the tabular setting (and function approximation if value functions don't share parameters), update for update, assuming that: (1) each value function is initialized identically, and (2) the same step size is used for each value function. An intuition for why is because the accuracy of the shifted action-values depends on the accuracy of the standard TD estimate, and the TD errors can be shown to exactly decompose that of standard TD. Under this, there is no ready improvement in data efficiency due to the fixed-horizon value functions converging quicker.

3) The results in the tabular setting seem to contradict what I described in Issue 2, because compositional Q-learning as presented did converge quicker than standard Q-learning. However, this is misleading in that the other methods used a step size of 1e-3, but the step size of the shifted value functions used, without explanation, a larger step size of 1e-2. The reason for the improved performance is that these values had a step size an order of magnitude larger than the remaining ones, and if one were to use the same step size across all value functions, it would have matched Q-learning exactly. This exact decomposition is supported by how the fixed-horizon value estimates follow Q-learning's curves exactly for the first h - 1 updates (and will converge to Q-learning's curve if h approaches infinity), and can further be verified by running the provided code with a step size of 1e-3 for the shifted value functions. Without acknowledging the equivalence when using a consistent step size across value functions, as well as sweeping over step sizes for each method, the results don't present a fair comparison and significantly misrepresent compositional TD methods.

4) On this observation that it is an exact decomposition of TD, it is particularly an exact decomposition of *one-step* TD, as one-step TD errors are used in the fixed-horizon and shifted value function estimates. This makes it equally biased to a one-step method, and is inconsistent with the use of "multi-step" learning in the literature where information across several time steps is included in the estimate of the return. Truncating and shifting things in time can be contextualized as a form of time-dependent discounting, and adjusting the discount rate isn't generally viewed as performing multi-step TD.

5) Based on the above, the benefit in the deep RL setting is not convincingly due to what is claimed (as parameters are shared, and a consistent step size is used in the optimizer). Some possible reasons might include the architectural choices in how the network represented the decomposition, as well as the representation learning benefits of predicting many relevant outputs to a task.

Suggestions:

1) The precise novelty of the work can be clarified, as the fixed-horizon TD formulation dates back to Sutton (1988), and has been extensively studied in De Asis et al. (2019). As far as I'm aware, there's novelty in the idea of shifting value functions, reconstructing the full return from decomposed value functions, and introducing a penalty to the loss based on inconsistencies in the value estimates.

2) The motivation and claims of the paper should be revised, as the claimed data efficiency from fixed-horizon values converging quicker isn't readily true. The resulting deep RL results may need more careful experiments to tease apart why the composition might be helping. For example, it might be useful to compare a different neural network architecture, like having all of the compositional components as outputs from the same, final hidden layer (in comparison with outputting them from intermediate hidden layers).

3) The tabular example needs to be re-worked to ensure a fair comparison between each algorithm. For example, the curves can be presented under the best step size (in terms of some metric, like area under the curve) for each algorithm. While there is an exact equivalence to standard one-step TD methods, a real benefit of the approach is that strictly more information is present to the agent, and the flexibility of being able to use separate step sizes for each value function can be favorable if it can be shown to be better after fairly tuning each algorithm. Shifting the focus toward showing that certain types of value functions are less sensitive to step sizes or work better operating at different time-scales from other components (because this seems to be what's actually happening in the results) would be a huge plus for this.

4) Because it is using one-step TD errors to estimate each of these components, and is equally biased to one-step TD, it isn't really a multi-step method. I think it would be better to emphasize the compositional aspect and its increased flexibility, than frame it as a multi-step off-policy method.

----------

Post-rebuttal:

I think the additional results post-discussion are good, and are on the right track of the claimed goal of analyzing the algorithm. However, the new results might be contradictory to some of the claims made earlier in the paper, and so a more involved revision seems to be needed. I do believe the algorithm has promise for the reasons teased apart in our discussion, and encourage the authors to improve their paper with these results.

To detail a few things:

1) The new results, which now empirically demonstrate the exact equivalence with one-step Q-learning, contradicts some claims about improved data efficiency due to truncated value-functions converging quicker. While meta-parameter selection isn't the focus, if the choice of meta-parameter is what can make it differ from vanilla Q-learning, and is the key explanation for the improvements, then the analysis should focus on this.

2) Mention of the equivalence only comes up in the experimental results, when it's a key property of the algorithm. If analysis of the composition is the paper's focus, acknowledging this property is foundational to any analysis of the method. It could have been shown analytically following the algorithm's derivation, and would have better justified some of the choices made in the experiments.

3) Being equivalent to running *one-step* Q-learning still makes the "multi-step" learning emphasis appear incorrect, especially when the algorithm can trivially be extended to use actual multi-step TD methods. The title seems to come from interpreting what the composite values represent, but the horizon isn't what makes a method multi-step, and the compositional components add up to exactly one-step Q-learning's update.

Minor:

1) Arguably one of the most prevalent explanations in the deep RL literature for why one might expect improvements is the multi-task/auxiliary task hypothesis (Jaderberg et al., 2016).
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content:   *Synopsis*:
  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.

  Main Contributions:
  - An algorithm, Composite Q-learning, which decomposes the value function into a short-term truncated portion and a long-term shifted portion.
  - Derivation of prior art for off-policy.

  *Review*
  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).


  [Q]uestions/[C]larifications/[S]uggestions:

  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.

  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.

  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).

  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.

  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)

  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. 

  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.


  *Other comments not taken into consideration in the review*

  - 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.

-----------
Post discussion/rebuttal:

After 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. 

Thanks again for your hard work, and I look forward to seeing this in a future conference.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: Summary

This paper introduces a new Q-learning formalism that helps reduce the bias of single step bootstrapping in Q-learning by learning multiple single step bootstrapping Q functions in parallel. This is accomplished by composing multiple n-step returns, showing that a recursive definition of n-step returns allows each return to be learned using only a single step of bootstrapping instead of at most n steps of bootstrapping. The paper solves the problem of the n-step fixed horizon by additionally composing a gamma discounted Q function that is shifted by n. In the end, the Q function used for behavior still predicts the same values as vanilla Q-learning, but with significantly less bias without a large increase in variance.

Review

I find this paper to be novel and insightful, the proposed algorithm is well supported theoretically and reasonably well supported empirically. I appreciated the careful demonstration on the smaller MDP with tabular features, showing the effects of multi-step Q-learning and clearly demonstrating the bias due to not truly using an off-policy formulation. I find that the demonstrations on the larger environments appear promising and suggest that composite multi-step Q-learning is a promising direction.

The error bars in the larger demonstrations, Figure 4, make it difficult to distinguish any meaningful differences between the algorithms. I appreciate that results are averaged over 11 runs, fortunately far more than seems to be standard at the moment, but still the amount of variance makes it difficult to say anything statistically. Table 2, then shows a reduction of the results but without mention of variance. It would be useful to include error measurements (perhaps the standard error over runs) to Table 2 to see the statistical significance of those results. Based on Figure 4, my guess is that there is negligible difference statistically.

The parameter sensitivity curves for the Walker2d domain also demonstrate that it is difficult to say anything meaningful about each parameter choice. Running a larger number of parameter settings would help to establish a clear pattern, or running each parameter setting for more independent runs could have allowed more significant results. The variance exhibited by one value in the regularization sensitivity curve is alone extremely interesting; perhaps using a different visualization that allowed more clear comparisons of the variance over independent runs would further motivate the utility of the regularization parameter. I think these results are interesting, but as presented do not sufficiently highlight the differences between the proposed algorithm and its competitors.

For the experiment in Figure 2, why not include multi-step Q-learning with importance sampling corrections on the later steps? I believe this would have fixed the bias issue, though clearly would be a tradeoff for high variance. I think this would make for a more convincing argument. Additionally, the caption does not well explain what the four green lines at the top of the plot represent. It was difficult to interpret the plot on the first pass of the paper because of this omission. Regardless, I find the results in Figure 2 to be otherwise intriguing.

Finally, the choice of meta-parameters in this paper could negatively impact results in favor of the competitor algorithms. By choosing to fix meta-parameters based on the defaults of a competitor, this could be harmfully biasing the proposed algorithm by preventing it from choosing a better stepsize. In fact, I would suspect that the proposed algorithm would exhibit lower variance updates than TD3, meaning it could potentially take advantage of higher stepsizes. This omission makes the claims of this paper weaker than they could possibly be, leaving a slight hole in the research.

---------
Edit after discussion and rebuttal phase:

I read the in-depth discussion between the authors and R3 and looked at the edits to the draft. I agree with the other reviewers on the basis of understanding the importance of meta-parameter selection. During the initial review, I found the ideas of the paper interesting enough to largely out-weigh the importance of a careful meta-parameter study. After R3's demonstration that there were indeed flaws with the results under the current meta-parameter selections, I think the best course of action would be to reject the paper in its current form.

I still strongly believe there is a place in the literature for this paper, so I hope to see this paper again at the next conference.
review_title: Official Blind Review #1

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