Venue: ICLR 2017 conference

Reviews:

final_score: rating: null
review_content: Hi,

Could you please clarify the following:
- What does this means precisely: "Gradients are also rescaled so that their magnitudes are comparable with or without penalty."
- In Table 1 why is the top right number in bold even if not the best result?

Thanks!
review_title: Small clarifications

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, a Q-Learning variant is proposed that aims at "propagating" rewards faster by adding extra costs corresponding to bounds on the Q function, that are based on both past and future rewards. This leads to faster convergence, as shown on the Atari Learning Environment benchmark.

The paper is well written and easy to follow. The core idea of using relaxed inequality bounds in the optimization problem is original to the best of my knowledge, and results seem promising.

This submission however has a number of important shortcomings that prevent me from recommending it for publication at ICLR:

1. The theoretical justification and analysis is very limited. As far as I can tell the bounds as defined require a deterministic reward to hold, which is rarely the case in practice. There is also the fact that the bounds are computed using the so-called "target network" with different parameters theta-, which is another source of discrepancy. And even before that, the bounds hold for Q* but are applied on Q for which they may not be valid until Q gets close enough to Q*. It also looks weird to take the max over k in (1, ..., K) when the definition of L_j,k makes it look like the max has to be L_j,1 (or even L_j,0, but I am not sure why that one is not considered), since L*_j,0 >= L*_j,1 >= ... >= L*_j,K. Neither of these issues are discussed in the paper, and there is no theoretical analysis of the convergence properties of the proposed method.

[Update: some of these concerns were addressed in OpenReview comments]

2. The empirical evaluation does not compensate, in my opinion, for the lack of theory. First, since there are two bounds introduced, I would have expected "ablative" experiments showing the improvement brought by each one independently. It is also unfortunate that the authors did not have time to let their algorithm run longer, since as shown in Fig. 1 there remain a significant amount of games where it performs worse compared to DQN. In addition, comparisons are limited to vanilla DQN and DDQN: I believe it would have been important to compare to other ways of incorporating longer-term rewards, like n-step Q-Learning or actor-critic. Finally, there is no experiment demonstrating that the proposed algorithm can indeed improve other existing DQN variants: I agree with the author when they say "We believe that our method can be readily combined with other techniques developed for DQN", however providing actual results showing this would have made the paper much stronger.

In conclusion, I do believe this line of research is worth pursuing, but also that additional work is required to really prove and understand its benefits.

Minor comments:
- Instead of citing the arxiv Wang et al (2015), it would be best to cite the 2016 ICML paper
- The description of Q-Learning in section 3 says "The estimated future reward is computed based on the current state s or a series of past states s_t if available." I am not sure what you mean by "a series of past states", since Q is defined as Q(s, a) and thus can only take the current state s as input, when defined this way.
- The introduction of R_j in Alg. 1 is confusing since its use is only explained later in the text (in section 5 "In addition, we also incorporate the discounted return R_j in the lower bound calculation to further stabilize the training")
- In Fig. S1 the legend should not say "10M" since the plot is from 1M to 10M
review_title: Intriguing idea, but lacking theoretical and empirical validation

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: In this paper, the authors proposed a extension to the DQN algorithm by introducing both an upper and lower bound to the optimal Q function. The authors show experimentally that this approach improves the data efficiency quite dramatically such that they can achieve or even supersede the performance of DQN that is trained in 8 days. 

The idea is novel to the best of my knowledge and the improvement over DQN seems very significant. 

Recently, Remi et al have introduced the Retrace algorithm which can make use of multi-step returns to estimate Q values. As I suspect, some of the improvements that comes from the bounds is due to the fact that multi-step returns is used effectively. Therefore, I was wondering whether the authors have tried any approach like Retrace or Tree backup by Precup et al. and if so how do these methods stack up against the proposed method.

The author have very impressive results and the paper proposes a very promising direction for future research and as a result I would like to make a few suggestions:

First, it would be great if the authors could include a discussion about deterministic vs stochastic MDPs. 

Second, it would be great if the authors could include some kind of theoretically analysis about the approach.

Finally, I would like to apologize for the late review.
review_title: Review

final_score: rating: null
review_content: Do you have any intuition or observations regarding which games benefit the most or the least from your proposed method?
review_title: Qualitative observations?

final_score: rating: null
review_content: I apologize for posting a question at this late juncture. But I was wondering about the meaning of the bounds in stochastic environments. For example, if either the reward function or the state transition is stochastic, then the bounds proposed in this paper would no longer be valid bounds. 

Empirically, this may not matter. But I was wondering whether the authors have any thoughts on this. Thanks!
review_title: Very late question.

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: This paper proposes an improvement to the q-learning/DQN algorithm using constraint bounds on the q-function, which are implemented using quadratic penalties in practice. The proposed change is simple to implement and remarkably effective, enabling both significantly faster learning and better performance on the suite of Atari games.

I have a few suggestions for improving the paper:
The paper could be improved by including qualitative observations of the learning process with and without the proposed penalties, to better understand the scenarios in which this method is most useful, and to develop a better understanding of its empirical performance.

It would also be nice to include zoomed-out versions of the learned curves in Figure 3, as the DQN has yet to converge. Error bars would also be helpful to judge stability over different random seeds.

As mentioned in the paper, this method could be combined with D-DQN. It would be interesting to see this combination, to see if the two are complementary. Do you plan to do this in the final version?

Also, a couple questions:
- Do you think the performance of this method would continue to improve after 10M frames?
- Could the ideas in this paper be extended to methods for continuous control like DDPG or NAF?
review_title: review

Meta-review: The authors have proposed an improvement to q-learning which imposes upper and lower constraint bounds on the q-function, which are implemented using quadratic penalties. This speeds up learning, at least for a limited set of Atari games. The reviewers are strongly divided on the merits of this paper. The authors have worked to be responsive to the reviewers' concerns, however, and the paper has been improved, so I side with the positives.
Decision: Accept (Poster)