Published as a conference paper at ICLR 2018 RESIDUAL LOSS PREDICTION: REINFORCEMENT LEARNING WITH NO INCREMENTAL FEEDBACK
We consider reinforcement learning and bandit structured prediction problems with very sparse loss feedback: only at the end of an episode. We introduce a novel algorithm, RESIDUAL LOSS PREDICTION (RESLOPE), that solves such problems by automatically learning an internal representation of a denser reward function. RESLOPE operates as a reduction to contextual bandits, using its learned loss representation to solve the credit assignment problem, and a contextual bandit oracle to trade-off exploration and exploitation. RESLOPE enjoys a no-regret reductionstyle theoretical guarantee and outperforms state of the art reinforcement learning algorithms in both MDP environments and bandit structured prediction settings.
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.