Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: After reading the other reviews and the authors' responses, I am satisfied that this paper is above the accept threshold.  I think there are many areas of further discussion that the authors can flesh out (as mentioned below and in other reviews), but overall the contribution seems solid.   I also appreciate the reviewers' efforts to run more experiments and flesh out the discussion in the revised version of the submission.

Final concluding thoughts:
-- Perhaps pi^ref was somehow better for the structured prediction problems than RL problems?
-- Can one show regret bound for multi-deviation if one doesn't have to learn x (i.e., we were given a good x a priori)?



---------------------------------------------
ORIGINAL REVIEW

First off, I think this paper is potentially above the accept threshold.  The ideas presented are interesting and the results are potentially interesting as well.   However, I have some reservations, a significant portion of which stem from not understanding aspects of the proposed approach and theoretical results, as outlined below.



The algorithm design and theoretical results in the appendix could be made substantially more rigorous. Specifically:

--  basic notations such as regret (in Theorem 1), the total reward (J), Q-value (Q), and value function (V) are not defined.  While these concepts are fairly standard, it would be highly beneficial to define them formally. 

-- I'm not convinced that the "terms in the parentheses" (Eq. 7) are "exactly the contextual bandit cost".  I would like to see a more rigorous derivation of the connection.  For instance, one could imagine that the policy disadvantage should be the difference between the residual costs of the bandit algorithm and the reference policy, rather than just the residual cost of the bandit algorithm. 

-- I'm a little unclear in the proof of Theorem 1 where Q(s,pi_n) from Eq 7 fits into Eq 8.

-- The residual cost used for CB.update depends on estimated costs at other time steps h!=h_dev.  Presumably, these estimated costs will change as learning progresses.  How does one reconcile that?  I imagine that it could somehow work out using a bandit algorithm with adversarial guarantees, but I can also imagine it not working out.  I would like to see a rigorous treatment of this issue.

-- It would be nice to see an end-to-end result that instantiates Theorem 1 (and/or Theorem 2) with a contextual bandit algorithm to see a fully instantiated guarantee.  



With regards to the algorithm design itself, I have some confusions:

-- How does one create x in practice? I believe this is described in Appendix H, but it's not obvious.  

-- What happens if we don't have a good way to generate x and it must be learned as well?  I'd imagine one would need larger RNNs in that case. 

-- If x is actually learned on-the-fly, how does that impact the theoretical results?

-- I find it curious that there's no notion of future reward learning in the learning algorithm.  For instance, in Q learning, one directly models the the long-term (discounted) rewards during learning.  In fact, the theoretical analysis talks about advantage functions as well.  It would be nice to comment on this aspect at an intuitive level.



With regards to the experiments:

-- I find it very curious that the results are so negative for using only 1-dev compared to multi-dev (Figure 9 in Appendix).  Given that much of the paper is devoted to 1-dev, it's a bit disappointing that this issue is not analyzed in more detail, and furthermore the results are mostly hidden in the appendix.

-- It's not clear if a reference policy was used in the experiments and what value of beta was used.

-- Can the authors speculate about the difference in performance between the RL and bandit structured prediction settings?  My personal conjecture is that the bandit structured prediction settings are more easily decomposable additively, which leads to a greater advantage of the proposed approach, but I would like to hear the authors' thoughts.



Finally, the overall presentation of this paper could be substantially improved.  In addition to the above uncertainties, some more points are described below.  I don't view these points as "deal breakers" for determining accept/reject.

-- This paper uses too many examples, from part-of-speech tagging to credit assignment in determining paths.  I recommend sticking to one running example, which substantially reduces context switching for the reader.  In every such example, there are extraneous details are not relevant to making the point, and the reader needs to spend considerable effort figuring that out for each example used.  

-- Inconsistent language. For instance, x is sometimes referred to as the "input example", "context" and "features".

-- At the end of page 4, "Internally, ReslopePolicy takes a standard learning to search step."  Two issues: 1) ReslopePolicy is not defined or referred to anywhere else.  2) is the remainder of that paragraph a description of a "standard learning to search step"?

-- As mentioned before, Regret is not defined in Theorem 1 & 2.

-- The discussion of the high-level algorithmic concepts is a bit diffuse or lacking.  For instance, one key idea in the algorithmic development is that it's sufficient to make a uniformly random deviation.  Is this idea from the learning to search literature?  If so, it would be nice to highlight this in Section 2.2.


review_title: Solid paper, many confusions in the original paper have been answered

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors present a new RL algorithm for sparse reward tasks. The work is fairly novel in its approach, combining a learned reward estimator with a contextual bandit algorithm for exploration/exploitation. The paper was mostly clear in its exposition, however some additional information of the motivation for why the said reduction is better than simpler alternatives would help.  

Pros
1. The results on bandit structured prediction problems are pretty good
2. The idea of a learnt credit assignment function, and using that to separate credit assignment from the exploration/exploitation tradeoff is good. 

Cons: 
1. The method seems fairly more complicated than PPO / A2C, yet those methods seem to perform equally well on the RL problems (Figure 2.). It also seems to be designed only for discrete action spaces.
2. Reslope Boltzmann performs much worse than Reslope Bootstrap, thus having a bag of policies helps. However, in the comparison in Figures 2 and 3, the policy gradient methods dont have the advantage of using a bag of policies. A fairer comparison would be to compare with methods that use ensembles of Q-functions. (like this https://arxiv.org/abs/1706.01502 by Chen et al.). The Q learning methods in general would also have better sample efficiency than the policy gradient methods.
3. The method claims to learn an internal representation of a denser reward function for the sparse reward problem, however the experimental analysis of this is pretty limited (Section 5.3). It would be useful to do a more thorough investigation of whether it learnt a good credit assignment function in the games. One way to do this would be to check the qualitative aspects of the function in a well understood game, like Blackjack.

Suggestions:
1. What is the advantage of the method over a simple RL method that predicts a reward at every step (such that the dense rewards add up to match the sparse reward for the episode), and uses this predicted dense reward to perform RL? This, and also a bigger discussion on prior bandit learning methods like LOLS will help under the context for why we’re performing the reduction stated in the paper.  

Significance: While the method is novel and interesting, the experimental analysis and the explanations in the paper leave it unclear as to whether its significant compared to prior work.

Revision: I thank the authors for addressing some of my concerns. The comparison with relative gain of bootstrap wrt ensemble of policies still needs more thorough experimentation, but the approach is novel and as the authors point out, does improve continually with better Contextual Bandit algorithms. I update my review to 6. 
review_title: Fairly novel approach for solving credit assignment in sparse reward RL, however comparison with other algorithms and explanations arent thorough enough to know if its a significant advance

final_score: rating: 7: Good paper, accept
review_content: The authors propose a new episodic reinforcement learning algorithm based on contextual bandit oracles.
The key specificity of this algorithm is its ability to deal with the credit assignment problem by learning automatically a progressive "reward shaping" (the residual losses) from a feedback that is only provided at the end of the epochs.

The paper is dense but well written. 

The theoretical grounding is a bit thin or hard to follow.
The authors provide a few regret theoretical results (that I did not check deeply) obtained by reduction to "value-aware" contextual bandits.

The experimental section is solid. The method is evaluated on several RL environments against state of the art RL algorithms. It is also evaluated on bandit structured prediction tasks.
An interesting synthetic experiment (Figure 4) is also proposed to study the ability of the algorithm to work on both decomposable and non-decomposable structured prediction tasks.


Question 1: The credit assignment approach you propose seems way more sophisticated than eligibility traces in TD learning. But sometimes old and simple methods are not that bad. Could you develop a bit on the relation between RESLOPE and eligibility traces ?

Question 2: RESLOPE is built upon contextual bandits which require a stationary environment. Does RESLOPE inherit from this assumption?


Typos:
page 1 
"scalar loss that output." -> "scalar loss."
", effectively a representation" -> ". By effective we mean effective in term of credit assignment."
page 5
"and MTR" -> "and DR"
page 6
"in simultaneously." -> ???
".In greedy" -> ". In greedy"

review_title: RESIDUAL LOSS PREDICTION: episodic RL and learning to search without incremental feedback

Meta-review: The reviewers agree that the problem of learning learning credit assignment from terminal rewards is interesting, and that the presented approach is promising. There are some concerns regarding the rigor and correctness of the theoretical results, and I ask the authors to improve those aspects of the paper. I also ask the authors to the result figures easier to read. The chosen colors are not ideal and the use of log-scale x-axis is not standard. Finally, including DAgger in the same plot is confusing assuming that DAgger user more information.
Decision: Accept (Poster)