Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper targets how to decompose delayed reward signals obtained at the end of a trajectory to a more immediate form of reward feedback. The authors introduce an algorithm, "Reward Distribution vis Randomized Return Decomposition" that serves as a proxy reward function for episodic reinforcement learning. The authors showcase extensive experiments showcasing improved performance over relevant baselines on common Mujoco benchmarks. The main contribution is to convert long horizon delayed reward problems to more short length sequences that can be trained upon with mini-batch gradient descent. 
main_review: Strengths:
- Paper is very well written and flows well. The theory is well presented and discussed and is relatively easy to understand.
- The paper is well situated in the context of related work. Baselines are thoroughly discussed and extreme care is taken explain the differences between RRD and other alternatives. 
- Experiments and ablations seem very thorough. 

Weaknesses:
- The related work (section 5) seems relatively small. The paper would benefit from more text here. 
- Experiments are constrained to Mujoco benchmark tasks. Would be interested in whether the authors have tried / intend to try the method on more such benchmarks.
- The graphs / figures might be more readable if some smoothing is introduced (and the smoothing factor is mentioned in the text). This is a matter of personal preference however so do not feel the need to do so. 
summary_of_the_review: The paper is well written and relatively easy to follow. It appears to introduce a novel algorithm for an important problem and should serve as an important alternative to training agents on long horizon delayed reward problems.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper addresses the delayed reward problem in reinforcement learning (RL). The authors propose an algorithm, randomized return decomposition (RRD), that learns a proxy reward function to provide immediate reward feedback to the RL agent. Theoretical analysis shows that RRD is an interpolation between two existing methods, namely deterministic return decomposition and uniform credit assignment. RRD can be interpreted as a regularized version of the deterministic return decomposition and is a generalization of uniform credit assignment. Empirical results in the Mujoco continuous control benchmark show that RRD performs better than algorithms that are based on deterministic return decomposition and uniform credit assignment, and two other methods that learn auxiliary rewards for facilitating policy learning.
main_review: **Originality & significance**:
This paper addresses the important delayed reward problem in RL. The proposed RRD method is simple but somewhat novel and the interpretation of RRD as an interpolation between deterministic return decomposition and uniform credit assignment is inspiring. The empirical results show visible improvement of RRD over baseline methods and demonstrate the effectiveness of RRD.

**Quality**:
Overall the paper quality is good. Section 3 presents a nice analysis of RRD and connects it to existing methods. The empirical comparison to existing methods is adequate. The ablation study sheds light on understanding the effect of the number of samples per episode. I have two comments below on how to further enhance the empirical section.
1. It will be nice to gain some understanding of what the learned proxy reward function looks like. In many of these continuous control tasks, the main factor of the reward is the forward progress of the creature. It will be interesting to see if the learned proxy rewards are aligned with the forward progress.
2. Related to the previous point, the return in these continuous control tasks is mostly the sum of the forward progress at every step. Thus the return decomposition is fairly easy to learn. It will be interesting to see more empirical results in domains that are more challenging from a return decomposition perspective. For example, in video games (modified to have trajectory feedback), it is hard to credit every single move properly but certain critical events are clearly rewarding/punishing. The long episodes with sparse events in video games may also be a challenge for RRD as a small batch of randomly sampled state-action pairs may mostly contain uninformative trivial transitions but not many interesting events. It will be interesting to see if RRD can still outperform its deterministic counterpart in that case.

**Clarity**:
This paper is well written and easy to follow.

**Minor issues**:
In the first paragraph of Section 1, it says "Most standard RL frameworks... require the reward function to provide instant feedback for every step of environment transitions." I'm not sure if this statement is accurate. In theory, most RL algorithms do not make assumptions on the density of the rewards, though they may not perform well in practice due to sparse rewards. This sentence feels a bit overstated to me.
summary_of_the_review: This paper addresses the important delayed reward problem in RL. The proposed method, RRD, is simple yet somewhat novel. The theoretical analysis builds connections to existing methods and the empirical study shows promises of RRD. Thus I think this paper is above the acceptance threshold.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper addresses the problem of credit assignment in delayed reward setting. It does this by providing a new mechanism for reward redistribution. The authors claim that the new mechanism makes reward redistribution more scalable. The authors predict the return of a trajectory by using only random sub-sequences in the trajectory. Then the prediction model is used for assigning reward for state-action pairs. 

main_review: - Experiments:

Experiments are well done and satisfactory. It seems all the environments have continuous action space. It would be interesting to know how the algorithm behaves for discrete action space. 

- Credit assignment and reward functions:

	Through the entire paper, credit assignment and reward functions have been used interchangeably. Constructing reward functions and assigning credit are two different problems. Also, RUDDER does not try to create a new dense reward function. It tries to assign credit to actions and it does this via decomposing the return of a trajectory. This has to be corrected in the paper. 

- RUDDER markov proxy reward function:

  RUDDER clearly states that the reward redistribution is second order markov (Theorem 2 in Arjona-Medina et.al). While in the paper it is mentioned that the resulting reward is a “Markovian proxy reward function”. Please provide clarification on why this is the case?

- Return Equivalence
 	One of the ways RUDDER ensures that the optimal policy stays the same is by being return equivalent. It is not clear how RRD ensures return equivalence or ensures that the optimal policy stays the same.

- Equation (4) 
	The section where equation (4) is introduced seems to imply that all methods use such a loss function. For example, RUDDER does not use this loss and should be clarified.  

Missing related work:

[1] also does reward redistribution for credit assignment for the complex task of Minecraft. [2] also looks at the problem of credit assignment and is relevant to your work.

[1] Align-Rudder: Learning from few demonstrations by reward redistribution

[2] Hindsight credit assignment

summary_of_the_review: Overall, the paper provides a new mechanism to reduce the delay in the reward and make learning faster in delayed settings. But the work is not too novel and the writing is not satisfactory. It is not clear why the optimal policy does not change after such randomized reward redistribution.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a method of constructing a proxy reward function (and the loss function for learning that reward function), which generalizes two prior methods, allowing it to trade off the advantages and disadvantages of those methods.  They create an RL algorithm based on this, analyze it theoretically and relative to prior work, and show that it performs well empirically.

main_review: Minor nitpick: The theta used in (4) should be formally defined.  One potential confusion that could result from not defining it: theta could parameterize the policy that generates the trajectory tau, or it could parameterize \hat R (I know it’s the latter, but I think this is a potential point of confusion that can be avoided by defining things more formally).

The notation around (6) is a little confusing, \mathcal I is not defined formally (it is a subset of \mathcal Z_T, but that’s not defined) or intuitively in English, except to say that it is sampled from rho_T.  rho_T “denotes an unbiased sampling distribution”, but of what?  I can infer that it is of the timesteps in the trajectory, (and thus I can infer the meaning \mathcal I) but all of this should be made clearer; it’s best not to make the reader have to guess and infer definitions.

Minor grammar issue: “Despite the Monte-Carlo estimator is unbiased,”

Questions:
- The RRD-L_RD is claimed as the authors’ algorithm, but that loss function is discussed as prior work when it is given in (4).  What is the contribution that makes it algorithm authors’ (and not prior work)?  The answer to this question might be a nice addition to supplementary material section B.2.
- “We evaluate the performance of our proposed methods with the same configuration of
hyper-parameters in all environments.”  To clarify, all algorithms in the experiments (not just your two proposed methods) used these hyperparameters, correct?
- Was any hyperparameter tuning performed?  How were the hyperparameters chosen?
- How many runs were used in each experiment? (I know at least 10, but more specifics would be good.)  What criteria were used for choosing to use different numbers of runs for different experiments?  I am concerned there could be bias here: 10 runs is not a large number for RL, where variance between runs is often enormous, and if some plots or curves were given additional runs after the authors viewed the results for 10 runs, that could add significant bias to the results in favor of their methods.
- Why the unusual choice for the error bars?  I suspect the standard choice (standard deviation) did not tell the desired story as convincingly…  (Or is this a common choice that I have simply not encountered much?)

**Update after the rebuttal and reading the other reviews:**

Most of my concerns have been addressed.  However, the fact that most of the plots used 10 runs raises a new concern: statistical significance.  (I did not raise this point before, "at least 10" could have meant 30+ for most plots.)  RL experiments are known to have large variance between runs, often with rare but extreme "outlier runs", so the common practice of including only 1-10 runs is not good, as has been pointed out in many papers, talks, etc. in recent years.  30+ runs (and ideally some statistical significance testing) would make this paper much stronger.  For this reason, I am only raising my score to weak accept (6) instead of accept (8).  (I would maintain my score of 5, but the paper is strong in other areas, and 10 runs is not quite as bad as many papers which include only 1-5 runs, and the trends that the authors assert seem somewhat clear across environments.)

**Update after final comments below:**

I am updating my score to an 8; see below.
summary_of_the_review: The overall contribution is a little light, but this is nonetheless a solid well-executed paper as a whole.  However, due to the questions above about experiments, I cannot accept the paper in its current form.  Pending the answers to those questions (and the reviewer discussion), I may raise my score significantly.
review_title: null

Meta-review: Description of paper content:

The paper addresses the problem of credit assignment for delayed reward problems. Their method, Randomized Return Decomposition, learns a reward function that provides immediate reward. The algorithm works by randomly subsampling trajectories and predicting the empirical return by regression using a sum of rewards on the included states. The method is compared to a variety of existing methods on Mujoco problems in “episodic reward” settings, where the reward is zero except for the final step of the episode, where it is the sum of rewards from the original task. Theoretical argument suggests the method is an interpolation of return decomposition (regress based on all states, not a subsample) and uniform reward distribution (send episodic reward to all states equally). By regressing with a subset of states, the method reduces compute for longer problems and is suggested to be more scalable.

Summary of paper discussion:

The reviewers largely commended the simplicity of the method, the simplicity of the presentation, the novelty of the algorithm, and the quality of the empirical results. The negative reviewer maintained their initial review’s score on account of a bias introduced by the algorithm.
Decision: Accept (Spotlight)