Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper deals with RL problems with the reward is either very sparse or delayed, in which case the Q-values would don't get updated. Honestly, I found the write-up to be really confusing, partly because of the structure of the paper and partly because of frequent carelessness in wording. Something that would really help is to take a difficult RL problem and just use it as a running example when discussing the different concepts in the paper. For instance, how does this notion of empirical sufficiency manifest itself in an image-based example and something like grid world?

As for the results, the authors conduct experiments on 6 Atari games, which I didn't find very convincing, in particular since games like Montezuma's Revenge, which are known to be difficult because of their reward sparsity are not included. Also, there has been a fair bit of recent work in this area, so using just A3C as a baseline is hard to justify. For instance, the authors can look at https://arxiv.org/abs/1606.01868 and the many papers that followed.

In short, I think there are some interesting ideas in the paper, but both the writing and the experimental results need significant improvement.
review_title: Interesting idea but poorly executed

final_score: rating: 4: Ok but not good enough - rejection
review_content: The work proposes 1) classifying states according to their observed reward roll-outs and 2) using the resulting classifier for reward shaping.

This reviewer finds the work difficult to read.  For example, the term "overfitting classifier" exhibits cognitive interference with standard usage without explanation.

The use of binary classification seems most appropriate for environments with sparse rewards (both positive and negative).  Otherwise the concept of "desired environmental signals" and "undesirable environmental signals" from section 3.2 is ill-specified.  (While the reviewer can imagine a policy improvement scenario where much-better-or-worse-than-the-baseline is related to desirable/undesirable, this is not discussed.)  The experimental section is not informative with respect to the issue of defining desirable or undesirable.

A better version of this paper would justify the technique analytically.  For instance, the optimal critic would provide the true Q-values as reward.  Under what conditions does a logistic binary classifier output a probability which is close to the true Q-value (e.g., with very sparse reward rollouts)?  Or alternatively under what conditions does the classifier induce a policy gradient [equation (1)] which is a descent direction?

The experiment section at the moment is structured as "it works on these 6 atari games", but this reviewer does not find this compelling (e.g., what about the other games?  do these 6 games have an obvious desirable/undesirable reward boundary?).  However, the claims about robustness to reward delay are interesting.  This reviewer encourages the authors to try their techniques on the RWRL challenge benchmark, specifically the challenges related to reward (and observation and action) delay.  
review_title: Potentially good idea, but poorly presented, and with insufficient experimental support

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Paper summary**
This paper proposes a method to tackle credit assignment for delay rewards. The method is based on building a classifier that can detect states that will lead to environmental rewards in the future and assigning an additional reward to these detected states. 

**Pros:**
- The overall idea is simple and intuitive.
- The visualizations in Fig 2 and 3 are clear and give good intuitions about the model.
- The results in Table 1 significantly improve over the baseline.

**Cons:**
1. The paper is not particularly easy to read. Here are some of the elements that caused me confusion and could be improved:

- Many terms introduced in the paper are not defined clearly enough (e.g. Empirical Sufficiency, Policy-based Empirical Sufficient Distribution,  Task-Specific Empirical Sufficient Distribution, Sensitive Sampling). I would suggest minimizing the introduction of new terms to the ones really required to explain the method.

- Other terms are slightly vague (e.g. pure distribution, dominant probability). 

- Some terms have names that are not very intuitive (e.g. rounds, overfitting mechanism). 

- Related to the previous point. In what sense is the word calibration used here? This term has a particular definition in the literature that should be refer to and justified.

In the section on Overfitting training:
- Equation (4) is not clear enough. Please define $L_E^one(\hat r_pos, r_pos) + (\hat r_neg, r_neg)$
- Are $N_{ident}$ and $N_{sufficient}$ number of rounds or a number of samples?
- What does it mean “we maximize Precision with complete $R_{negative}$ samples”?
- Is the phase 1 and 2 done in sequence or in parallel as Eq 6 suggests? In the latter case, is this the same as increasing the loss for the negative class?

In the Results section:
- Result order: The modified environment result is presented before the regular one, although in the first paragraph of the results the order is swapped.  

- In Table 2, what is the difference between the red trace in top and bottom row?

2. I’m not sure the Atari levels selected for the experiments have a particularly delayed reward. With the possible exception of Bowling, the other levels usually have a short period between action and reward. Some levels that could be more interesting for testing credit assignment could be Skiing, Seaquest, Solaris or Venture (justified in e.g. Arjona-Medina et al. 2019 or Puigdomènech Badia 2020). It would be interesting to include the justification for this particular selection of levels in the paper.

3. The results are not particularly strong. From Table 2, it seems that the only significant improvement is made on FishingDerby. Is this because of the choice of levels? I would have expected a positive result in Bowling. Could the authors include a comment on why this is not the case? The results are positice in Table 1, in the modified environments, but I would like to see results in an original level with more delayed rewards (which already exist in Atari). 

4. How does this method cope with intermediate (distracting) rewards in between the key action and the ultimate reward? (as in Hung et al., 2018). Is the way of selective states for the positive pools a problem to learn this type of credit assignment?

Minor: 
- Tables 1 and 2 should be Figures.
- Fig3. caption “ The calibrated rewards and environmental rewards are encoded in red and yellow“  should be blue?
- “resonate with human cognition” seems a bit over-claimed to me. I would say that the visual inspections make intuitive sense. 

review_title: Official review

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper presents an experimental approach to tackle the problem of appropriate credit assignment under the delayed reward scenario and proposes an empirically sufficient condition to calibrate the reward policy in a Deep Reinforcement Learning framework.

**Pros**
    - The problem is interesting.

**Cons**
    - The paper does not explain the pre-processing in sufficient depth. In the experiments (neither in section 4 nor in A.1 or A.2) the state representation is not clear. 
    - The approach presented in this paper seems to be ad-hoc, and it lacks rigorous experimentation to validate the contribution of building blocks of the architecture. In particular, **ablation tests** are very much necessary to clarify the contribution of different components in the proposed architecture, but no such study has been provided in the paper. Further, there is little theoretical backup and intuition behind the proposed idea. 
    - The authors define Empirical Sufficiency (Definition 3.1) but do not specify the structure of the space. Specifically, it is not clear what is the underlying set, and if there is a metric associated with it? Now, depending on the structure of the space, it could give rise to many topological properties. Hence, the definition is not complete. Further, the intuitive explanation presented in the paper is not sufficient.
    - The proposed method is not rigorously compared against the existing well-known DRL techniques. The authors indeed present some experiments to highlight the improvement accomplished by their architecture w.r.t. to some hind-sight results (Table 1). However, the end-goal of solving a task (e.g. playing games) is to maximise the total reward. Hence, it is essential to compare the total reward obtained by the proposed method with that obtained by the latest DRL based algorithms, and it is missing in this paper.

**Overall impression**
The paper attacks an exciting problem but lacks rigorous experimentation and theory to validate the proposed method.
review_title: The proposed method seems to be ad-hoc, and neither has a good theoretical explanation, nor there is any rigorous experiment to validate and compare against the existing methods.

Meta-review: This work tackles sparse or delayed reward problem in reinforcement learning. The key idea is to build a classifier to detect states that will lead to high rewards in the future and provide a bonus to those states. All the reviewers liked the idea but had issues with the execution of empirical results. The approach is evaluated only in a few Atari games skipping many sparse reward games and missing comparison to many exploration baselines. Furthermore, many reviewers found the writing confusing and hard to follow. The authors provided the rebuttal and addressed some of the concerns. However, upon discussion post rebuttal, the reviewers decided to maintain their score. Reviewers believe that the paper will immensely benefit with improved writing, evaluation on all atari games, and comparison to exploration baselines. Please refer to the reviews for final feedback and suggestions to strengthen the future submission.
Decision: Reject