Learning Long-Term Reward Redistribution via Randomized Return Decomposition
Authors: Zhizhou Ren
Ruihan Guo
Yuan Zhou
Jian Peng
Venue: ICLR 2022 Spotlight (2022)
Keywords: Reinforcement Learning
Long-Term Credit Assignment
Reward Redistribution
Return Decomposition

Abstract: Many practical applications of reinforcement learning require agents to learn from sparse and delayed rewards. It challenges the ability of agents to attribute their actions to future outcomes. In this paper, we consider the problem formulation of episodic reinforcement learning with trajectory feedback. It refers to an extreme delay of reward signals, in which the agent can only obtain one reward signal at the end of each trajectory. A popular paradigm for this problem setting is learning with a designed auxiliary dense reward function, namely proxy reward, instead of sparse environmental signals. Based on this framework, this paper proposes a novel reward redistribution algorithm, randomized return decomposition (RRD), to learn a proxy reward function for episodic reinforcement learning. We establish a surrogate problem by Monte-Carlo sampling that scales up least-squares-based reward redistribution to long-horizon problems. We analyze our surrogate loss function by connection with existing methods in the literature, which illustrates the algorithmic properties of our approach. In experiments, we extensively evaluate our proposed method on a variety of benchmark tasks with episodic rewards and demonstrate substantial improvement over baseline algorithms.

Published as a conference paper at ICLR 2022
LEARNING LONG-TERM REWARD REDISTRIBUTION VIA RANDOMIZED RETURN DECOMPOSITION
Zhizhou Ren', Ruihan Guo", Yuan
Peng145
1 University of Illinois at TirbanaChhappaig Shhnghai Jiao Tong University
*BMSS AIR, Tsinghua University "HeliXon Limited
iiliiii edu, guoruihan jtu. jtu.edu............... cn t imzhouyuan@gmail. com, jianpenge www.liiiiiee. edu
ABSTRACT
Many practical applications of reinforcement learning require agents learn from sparse and delayed rewards. It challenges the ability of agents to attribute their ac- tions future outcomes. In this paper, consider the problem formulation of episodic reinforcement learning with trajectory feedback. It refers to an extreme delay of reward signals, in which the agent can only obtain one reward signal at the end of each trajectory. A popular paradigm for this problem setting is learning with designed auxiliary dense reward function, namely proxy reward, instead of sparse environmental signals. Based on this framework, this paper proposes a novel reward redistribution algorithm, randomized return decomposition (RRD), to learn a proxy reward function for episodic reinforcement learning. We establish a surrogate problem by Monte-Carlo sampling that scales up least-squares based reward redistribution to long-horizon problems. We analyze surrogate loss function by connection with existing methods in the literature, which illustrates the algorithmic properties of our approach. In experiments, uate our proposed method on a variety of benchmark tasks with episodic rewards and demonstrate substantial improvement over baseline algorithms.
extensively eval-
INTRODUCTION
Scaling reinforcement learning (RL) algorithms to practical applications has become the focus of numerous recent studies, including resource management (Mao et al. 2016). industrial control (Hein
et al. 2017). drug discovery (Popova et al.) 2018), and recommendation systems (Chen et al.) 2018). One of the challenges in these real-world problems is the sparse and delayed environmental rewards. For example, in the molecular structure design problem, the target molecule property can only be evaluated after completing the whole sequence of modification operations (Zhou et al. 2019b). The sparsity of environmental feedback would complicate the attribution of rewards agent actions and therefore can hinder the efficiency of learning (Rahmandad et al.] 2009). In practice, it is a common choice to formulate the RL objective with meticulously designed reward function instead of the sparse environmental rewards. The design of such a reward function crucial to the performance of the learned policies. Most standard RL algorithms, such as temporal difference learning and policy gradient methods, prefer dense reward functions that can provide instant feedback for every step of environment transitions. Designing such dense reward functions is with domain knowledge and human supervision. It has been widely observed in prior works that handcrafted heuristic reward functions may lead to unexpected and undesired behaviors (Randløv) & Alstrøm 1998; Bottou et al. 2013 Andrychowicz et al., 2017). The agent may find shortcut solution that formally optimizes the given objective but deviates from the desired policies (Dewey) 2014 Amodei et al.) 2016). The reward designer can hardly anticipate all potential side effects of the designed reward function, which highlights the difficulty reward engineering.
simple problem even
To avoid the unintended behaviors induced by misspecified reward engineering, a common paradigm is considering the reward design as an online problem within the trial-and-erro loop of reinforce- ment learning (Sorg et al. 2010). This algorithmic framework contains two components, namely reward modeling and policy optimization. The agent first learns a proxy reward function from the experience data and then optimizes its policy based on the learned per-step rewards. By iterating this

---

Published as a conference paper at ICLR 2022
procedure and interacting with the environment, the agent is able continuously refine its reward model so that the learned proxy reward function can better approximate the actual objective given by the environmental feedback. More specifically, this paradigm aims to reshape the sparse and delayed environmental rewards to a dense Markovian reward function while trying to avoid misspecifying the goal of given tasks.
In this paper, we propose a novel reward redistribution algorithm based on a classical mechanism called return decomposition (Arjona-Medina et al., 2019). Our method is built upon the least- squares-based return decomposition (Efroni et al. (02T)) whose basic idea is training regression model that decomposes the trajectory return to the summation of per-step proxy rewards. This paradigm is promising approach to redistributing sparse environmental feedback. Our proposed algorithm, randomized return decomposition (RRD), establish surrogate optimization of return de- composition to improve the scalability in long-horizon tasks. In this surrogate problem, the reward model trained to predict the episodic return from a random subsequence of the agent trajectory, i.c. we conduct a structural constraint that the learned proxy rewards can approximately reconstruct environmental trajectory return from a small subset of state-action pairs. This design enables us to conduct return decomposition effectively by mini-batch training. Our analysis shows that sur- rogate loss function an upper bound of the original loss of deterministic return decomposition, which gives theoretical interpretation of this randomized implementation. We also present how the surrogate gap can be controlled and draw connections to another method called uniform reward redistribution. In experiments, we demonstrate substantial improvement of our proposed approach over baseline algorithms on suite of MuJoCo benchmark tasks with episodic rewards.
2 BACKGROUND
2.1 EPISODIC REINFORCEMENT LEARNING WITH TRAJECTORY FEEDBACK
In standard reinforcement learning settings, the environment model is usually formulated by Markov decision process (MDP: Bellman 1957), defined as a tuple M = (S,A, R, 14), where S and A denote the spaces of environment states and agent actions. P(s'ss, [s, a) and R(s, a) denote the unknown environment transition and reward functions. denotes the initial state distribution. The goal of reinforcement learning is to find policy क - A maximizing cumulative rewards. More specifically, a common objective is maximizing infinite- horizen discounted rewards based on a pre-defined discount factor y as follows:
8
(standard objective)
J(T) =E
Σ
r RRss (())) 80 ~ n. 8441 ~ P(. B6s T (+t))
(I)
In this paper, we consider the episodic reinforcement learning setting with trajectory feedback. in which the agent only obtain one reward feedback the end of each trajectory. Let 7 denote an agent trajectory that contains all experienced states and behaved actions within an episode. We assume all trajectories terminate in finite steps. The episodic reward function (T) is defined on the trajectory space, which represents the overall performance of trajectory т. The goal of episodic reinforcement learning is to maximize the expected trajectory return:
(episodic objective)
(T) = E RT)(T) 80 ~ μ1 a, = ( T = (so, do, 81,"" (T) (2)
In general, the episodic-reward setting is a particular form of partially observable Markov decision processes (POMDPs) where the reward function is Mon-Mvakvii.n. The worst case may require the agent to enumerate the entire exponential-size trajectory space for recovering the episodic reward function. In practical problems, the episodic environmental feedback usually has structured repre- sentations. A common structural assumption the existence of an underlying Markovian reward function A(s,a) a) that approximates the episodic reward (T)(T) by sum-form decomposition,
T-1
(sum-dccomposable episodic reward)
Rep(T) RTp(T) = A(st, ac).
(3)
This structure is commonly considered by both theoretical (Efroni et al. 2021) and empirical studies LLu et al. 2019 Raposo al. 2021) on long-horizon episodic rewards. It models the situations
2

---

Published as a conference paper at ICLR 2022
where the agent objective is measured by some metric with additivity properties, e.g., the distance of robot rumning, the time cost of navigation, or the number of products produced in a time interval.
2.2 REWARD REDISTRIBUTION
The goal of reward redistribution constructing a proxy reward function R(s at) that transforms the apisodic-reward problem stated in Eq. (2) to a standard dense-reward setting. By replacing environmental rewards with such Markovian proxy reward function R(s,, az), the agent can be trained to optimize the discounted objective in Eq. ( using any standard RL algorithms, Formally, the proxy rewards M(s, 0e) form a sum-decomposable reward function RTp(T) = Σi= that is expected to have high correlation the environmental reward RTp(T). Here, introduce two branches of existing reward redistribution methods, return decomposition and uniform reward redistribution, which are the most related to our proposed approach. We defer the discussions of other related work to section 5
2 R(s,, ae)
Return Decomposition. The idea of return decomposition is training a reward model that pre- dicts the trajectory return with a given state-action sequenee (Arjona- Mendina et al. 2019). In this paper, without further specification, we focus on the least-squares baseeed---ddddeeee implementation of return decomposition (Efroni al.. 2021). The reward redistribution is given by the learned reward model, i.e,, decomposing the environmental episodic reward (T)(T) to a Markovian proxy reward function R(s, a). In practice, the reward modeling is formulated by optimizing the following loss function:
[ (Roa(t) - -E Ro ae)
T-1
)
2
(RD
T-D
where Rg denotes the parameterized proxy reward function, 9 denotes the parameters of the learned reward model, and D denotes the experience dataset collected by the agent. Assuming the sum- decomposable structure stated in Eq. 33. Rs a) is expected to asymptotically concentrate near the ground-truth underlying rewards R[s a) when Eq. is properly optimized (Efroni et al. 2021).
One limitation of the least-squares-basee. based return decomposition method specified by Eq. is its scalability in terms of the computation costs. Note that the trajectory-wise episodic reward is the only environmental supervision for reward modeling. Computing the loss function (+) with a single episodic reward label requires to enumerate all state-action pairs along the whole trajectory. This computation procedure can be expensive in numerous situations, e.g., when the task horizon T is quite long, or the state space S is high-dimensional. To address this practical barrier, recent works focus on designing reward redistribution mechanisms that can be easily integrated in complex tasks. We will discuss the implementation subtlety of existing methods section 4
Uniform Reward Redistribution. To pursue a simple but effective reward redistribution mech- anism, IRCR (Gangwani et al. 2020 considers uniform reward redistribution which assumes all state-action pairs equally contribute to the return value. It is designed to redistribute rewards in the absence of any prior structure information. More specifically, the proxy reward RIRCR( (s, a) is computed by averaging episodic return values over all experienced trajectories containing (8, a).
RIRCR (s, a)
E [Rpp(T) (s,a) E r..
T~D
In this paper, we will introduce novel reward redistribution mechanism that bridges between return decomposition and uniform reward redistribution.
3 REWARD REDISTRIBUTION VIA RANDOMIZED RETURN DECOMPOSITION
In this section, we introduce approach, randomized return decomposition (RRD), which sets up a surrogate optimization problem of the ceast-squares-bat based return decomposition. The proposed surrogate objective allows us to conduct return decomposition short subsequences of agent trajec- tories, which is scalable in long-horizon tasks. We provide analyses to characterize the algorithmic property of our surrogate objective function and discuss connections existing methods.
3

---

Published as a conference paper at ICLR 2022
3.1 RANDOMIZED RETURN DECOMPOSITION WITH MONTE- CARLO RETURN ESTIMATION
One practical barrier to apply least-squaresbbased return decomposition methods in long-horizon tasks is the computation costs of the regression loss in Eq. A. i.e., it requires enumerate all state- action pairs within the agent trajectory. To resolve this issue, we consider a randomized method that uses Monte-Carlo estimator to compute the predicted episodic return Re) as follows:
T
T
RTp,O(T) Σ (o) Impr(-)
Ro as)
Ro(
(6)
Z
IE
IEI
Deterministic Computation
Monte Carlo Estimation
where I denotes subset of indices. pr(+) denotes unbiased sampling distribution where each index t has the same probability to be included in I. In this paper, without further specification, pr() is constructed by uniformly sampling K distinct indices.
pr(+) Uniform (Şz C žr |Z| =k]),
where K' is a Hlyer-paramelte In this sampling distribution, each timestep has the same probability be covered by the sampled subsequence I ~ pr(() so that it gives an unbiased Monte-Carlo estimation of the episodic summation Rep.o(T).
Randomized Return Decomposition. Based on the idea of using Monte-Cart estimation shown in Eq. (6). we introduce our approach, randomized return decomposition (RRD), to improve the scal- ability of least-squares- sassses--rbeeddd reward redistribution methods. The objective function of approach formulated by the randomized return decomposition loss L (f) stated in Eq. (8) in which
the parameterized proxy reward function Rg is trained to predict the episodic return (T) given random subsequence the agent trajectory. In other words, we integrate the Monte-Carlo estimator (see Eq. (6)) into the return decomposition loss to obtain the following surrogate loss function:
Rand (D)
E
(
( (Rpl(T)
Σ Σ
RS (+)
Impr(-)
IET
In practice, the loss function (Rand-RD(() can be estimated by sampling mini-batch of trajectory subsequences instead of computing (o(st,,,) a,) for the whole agent trajectory, and thus the imple- mentation randomized return decomposition is adaptive and flexible long-horizon tasks.
3.2 ANALYSIS OF RANDOMIZED RETURN DECOMPOSITION
The main purpose of approach is establishing surrogate loss function improve the scala- bility of least-squares-basee based return decomposition in practice. Our proposed method, randomized return decomposition, is a trade-off between the computation complexity and the estimation error induced by the Monte-Carlo estimator. In this section, we show that our approach is an interpolation between between the return decomposition paradigm and uniform reward redistribution, which can be controlled by the syper-parameter K used in the sampling distribution (see Eq. (7)). We present Theorem as formal characterization of our proposed surrogate objective function.
Theorem (Loss Decomposition). The surrogate loss function LRand-RD (0) can be decomposed to two terms interpolating between return decomposition and uniform reward redistribution.
T I
RRand-RD (f) = (0) +
Var Impr(-)
Σ
Ro(st, oz)
(9)
TND
IEI
variance of the Monte-Carlo estimator
LRD return decomposition
E TDD
T2
Ro Ro((st (owT
Var
(10)
uniform reward redistribuaton
interpolation weight
where denotes the length of sampled subsequences defined Eq.
The proof of Theorem Tis based on the bias variance decomposition formula mean squared error (Kohavi & Wolpert 1996). The detailed proofs are deferred Appendix
4

---

Published as a conference paper at ICLR 2022
Interpretation Regularization. As presented in Theorem the randomized decomposition loss can be decomposed to two terms, the deterministic return decomposition loss LRD(O) and a variance penalty term (see the second term of Eq. (). The variance penalty term can be regarded as a regularization that is controlled by papee--prameter K. In practical problems, the objective of return decomposition is ill-posed, since the number of trajectory labels is dramatically less than the number of transition samples. There may exist solutions of reward redistribution that formally optimize the least-squares regression loss but serve little functionality to guide the policy learning. Regarding this issue, the variance penalty in randomized return decomposition is a regularizer for reward modeling. It searches for smooth proxy rewards that has low variance within the trajectory. This regularization effect is similar to the mechanism of uniform reward redistribution (Gangwani ett al. 2020), which achieves state-of-the-art performance in the previous literature. section 4 our experiments demonstrate that the variance penalty is crucial to the empirical performance of randomized return decomposition.
A Closer Look at Loss Decomposition. In addition to the intuitive interpretation of regulariza- tion, we will present a detailed characterization the loss decomposition shown in Theorem T We interpret this loss decomposition below:
Note that the Monte-Carde Carlo estimator used by randomized return decomposition is an unbi- ased estimation of the proxy episodic return (T) (see Eq. (6). This unbiased property gives the first component of the loss decomposition, i.e, the original return decomposition loss (0).
2. Although the Monte-Carlo estimator is unbiased, its variance would contribute to an addi- tional loss term induced by the mean-square operator, i.c., the second component of loss decomposition presented in Eq. (10). This additional term penalizes the variance of the learned proxy rewards under random sampling. This penalty expresses the same mecha- nism as uniform reward redistribution (Gangwani al., (0200) in which the episodic return is uniformly redistributed to the state-action pairs in the trajectory.
Based on the above discussions, we can analyze the algorithmic properties of randomized return decomposition by connecting with previous studies.
3.2.1 SURROGATE OPTIMIZATION OF RETURN DECOMPOSITION
Randomized return decomposition conducts a surrogate optimization of the actual return decompo- sition. Note that the variance penalty term in Eq. (10) is non-nen non-negative, our loss function LRand-RD serves an upper bound estimation of the original loss (f) as the following statement.
Proposition 1 (Surrogate Upper Bound). The randomized return decomposition loss R RD is an upper bound of the actual return decomposition loss function (RD(f), i.e., LRand-RD 2 LRD
Proposition I suggests that optimizing our surrogate loss LRand-RD (0) guarantees to optimize up- per bound of the actual return decomposition loss (RD( According to Theorem the gap between CRand-RD (0) and LRD (0) refers to the variance of subsequence sampling. The magnitude of this gap can be controlled by the apper-prrmmter K that refers to the length of sampled subsequences.
Proposition 2 (Objective Gap). Let (()) RRad denote the randomized return decomposition loss that samples subsequences with length K. The gap between c(K) Rond-RD
(0) and LRD( can be reduced
by using larger values of hyper-parameter K.
vB,
Rund--Ro (0) Z Rand--R RD (0) 2 ... -
(
L (0) LRD(A))
(11)
This gap can be eliminated by choosing T the sampling distribution (see Eq. 77) so that our approach degrades to the original deterministic implementation of return decomposition.
3.2.2 GENERALIZATION OF UNIFORM REWARD REDISTRIBUTION
The reward redistribution mechanism of randomized return decomposition is a generalization of uniform reward redistribution. To serve intuitions, start the discussions with the simplest case using K 1 in subsequence sampling, in which our approach degrades to the uniform reward redistribution the following statement.
5

---

Published as a conference paper at ICLR 2022
Proposition 3 (Uniform Reward Redistribution). Assume all trajectories have the same length and the parameterization space of 9 serves universal representation capacity. The optimal solution of minimizing C(L) Rand (0) is stated as follows:
Ro- (s,
E (Rp((t) (s, TND
(12)
where C(I) Rand-RDD
(0) denotes the randomized return decomposition loss with K
minor difference between Eq. (12 and the proxy reward designed by Gangwani et al. (2020) (see Eq. (5) is multiplier scalar 1/T. Gangwani et al. (2020) interprets such proxy reward mechanism as a trajectory-space smoothing process or a non-committal reward redistribution. Our analysis can give mathematical characterization to illustrate the objective of uniform reward redistribution. As characterized by Theorem ! uniform reward redistribution conducts an additional regularizer to penalize the variance of per-step proxy rewards. In the view of randomized return decomposition, the functionality of this regularizer is requiring the reward model to reconstruct episodic return from each single-step transition.
By using larger values of hyper-parameter K, randomized return decomposition is trained to recon- struct the episodic return from a subsequence of agent trajectory instead of the single-step transition used by uniform reward redistribution. This mechanism is a generalization of uniform reward re- distribution. in which we equally assign rewards to subsequences generated by uniformly random sampling. It relies on the concentratability of random sampling. i.e., the average of sequence can be estimated by a small random subset with sub-linear size. The individual contribution of each transition within the subsequence is further attributed by return decomposition.
3.3 PRACTICAL IMPLEMENTATION OF RANDOMIZED RETURN DECOMPOSITION
In Algorithm D
we integrate randomized return decomposition with policy optimization. It follows iterative paradigm that iterates between the rewarding modeling and policy optimization modules.
Algorithm Policy Optimization with Randomized Return Decomposition
1: Initialize D <-
2: for 1,,, do
3: Collect rollout trajectory using the current policy.
4: Store trajectory and feedback (Tp(T) into the replay buffer D < DU [(T, Rep(T)))
5: for 1,2, do
6:
M from the replay buffer. 7: Sample subsequences {Z, C Tr, }Md for these trajectories.
Sample M trajectories (Ty E DDMM
8:
Estimate randomized return decomposition loss CRand.RD)())
M Σ j=1
Σ Ro(s),, 2 TET,
E E BAund-RD(C (0) = M
Rup(T,)
T [z,
(13)
where T, denotes the length of trajectory = (85.1, 88,23). Perform gradient update the reward model R.g
9:
- a (A).
(14)
where a denotes the learning rate. Perform policy optimization using the learned proxy reward function Ro a).
10:
As presented in Eq. 13 and Eq. (4], the optimization of our loss function CRand-RD(O) can be easily conducted by mini-batch gradient descent. This surrogate loss function only requires computations on lhort-length subsequences. provides a scalable implementation for return decomposition that can be generalized to mor-horioon tasks with manageable computation costs. In section 4 will show that this simple implementation can also achieve ofate-of-the-e performance in comparison other existing methods.

---

Published as a conference paper at ICLR 2022
4 EXPERIMENTS
In this section, we investigate the empirical performance of our proposed methods by conducting ex- periments suite of MuJoCo benchmark tasks with episodic rewards. We compare approach with several baseline algorithms in the literature and conduct an ablation study on subsequence sampling that is the core component of our algorithm.
4.1 PERFORMANCE EVALUATION ON MUJoCo BENCHMARK WITH EPISODIC REWARDS
Experiment Setting. We adopt the same experiment setting as Gangwani et al. 2020) to compare the performance of our approach with baseline algorithms. The experiment environments based on the MuloCo locomotion benchmark tasks created by OpenAl Gym (Brockman et al. 2016). These tasks are long-horizon with maximum trajectory length T 1000, i.e., the task horizon is definitely longer than the batch size used by the standard implementation of mini-batch gradient estimation. We modify the reward function of these environments to set up an episodic-rewaie setting. Formally, on non- non-terminal states, the agent will receive zero signal instead of the per-step dense rewards. The agent can obtain the episodic feedback Rep(T) at the last step of the rollout trajectory, which (ep(T) is computed by the summation of per-step instant rewards given by the standard setting. We evaluate the performance of our proposed methods with the same configuration of perraaaetett in all environments. A detailed description of implementation details is included in Appendix B
We evaluate two implementations of randomized return decomposition (RRD):
RRD (ours) denotes the default implementation of our approach. We train a reward model using randomized return decomposition loss LDD in which we sample subsequences with length K = 64 in comparison to the task horizon T = 1000. The reward model Rg is parameterized by a two-layer fully connected network. The policy optimization module is implemented by soft actor-critic (SAC; Haarnoja et al. 2018a).
RRD-CRD (ours) is alternative implementation that optimizes LRD instead of LRana RD- Note that Theorem gives a closed-form characterization of the gap hetween LRand-RD (0) and (RD, which represented by the variance of the learned proxy rewards. By subtracting an unbiased variance estimation from loss function (()),, we can estimate loss function (+) by sampling short subsequences. It gives computationally efficient way to opti- mize (f). We include this alternative implementation to reveal the functionality of the regularization given by variance penalty. A detailed description is deferred to Appendix B.3
We compare with several existing methods for episodic or delayed reward settings:
IRCR (Gangwani et al. 2020 is implementation of uniform reward redistribution. The reward redistribution mechanism of IRCR is con-parametric, which the proxy reward of a transition is set to be the normalized value of corresponding trajectory return. It is equivalent to use a Monte-Care Carlo estimator of Eq. (5). Due to the ease of implementation, this method achieves state-of-the-ar performance in the literature.
RUDDER (Arjona-Medina et al. 2019) is based on the idea of return decomposition but does not directly optimize (f). Instead, trains return predictor based on trajectory, and the step-wise credit is assigned by the prediction difference between two consecutive states. By using the warm-up technique of LSTM, this transform prevents its training computation costs from depending on the task horizon T so that it is adaptive to long-horizon tasks.
GASIL (Guo et al., 2018), generative adversarial self-imitation learning, is generalization of GAIL (Ho & Ermon 2016). It formulates imitation learning framework by imitating best trajectories in the replay buffer. The proxy rewards are given by a discriminator that is trained classify the agent and expert trajectories.
LIRPG (Zheng et al. 2018) aims to learn an intrinsic reward function from sparse environ- ment feedback. Its policy trained to optimized the sum of the extrinsic and intrinsic rewards. The parametric intrinsic reward function is updated by meta-gradients to optimize the actual extrinsic rewards achieved by the policy
'The source code of our implementation is available https:///g httpeitthh.oooooeeeeeeeommme com/Sti 1wel G
Randomi zed- Rettuen- -etuurn--eecooosiitii
7

---

Published as a conference paper at ICLR 2022
RRD (ours)
RRD>-Cn (ours)
IRCR
RUDDER
GASIL
LIRPG
Ant-v2
HaliChectah-v2
Walker2d-v2
Humanoid-y2
18000
Average Kathodie
6000
3.00
0ST 8:5M E5S
3SE 0:33
TSE 13M 3M ZSM
031
IN 13M 2M 13M 3M
Timestepa
Timesteps
Timesteps
Timeotops
Reacher-v2
S Swimmer-v2
Hopper-v2
HumanoidStandpp-12
Avernge Eptondic
2508 TM L3M 2M 23M XM
1M 15M
INE LSM 2N 2,50 39C
BM E:5 153 13M 2M 25M 3N
391 1035 1M 13M 2M 2.M 353
853 0.5M
Timesteps
Timesteps
Timesteps
Timestopss
Figure 1: Learning curves suite of MuJoCo benchmark tasks with episodic rewards. All curves for MuJoCo benchmark are plotted from 30 runs with random initializations. The shaded region indicates the standard deviation. To make the comparison more clear, the curves are smoothed by averaging 10 most recent evaluation points. We set up an evaluation point every 104 timesteps.
Overall Performance Comparison. As presented in Figure randomized return decomposition generally outperforms bascline algorithms. Our approach can achieve higher sample efficiency and produce better policies after convergence. RUDDER an implementation of return decomposition that represents single-step rewards by the differences between the return predictions of two consecu- tive states. This implementation maintains high computation efficiency but long-term return predic- tion is a hard optimization problem and requires on-policy samples. In comparison, RRD more scalable and stable implementation which can better integrate with off- off-policy learning for improving sample efficiency. The uniform reward redistribution considered by IRCR simple implement but cannot extract the temporal structure of episodic rewards. Thus the final policy quality produced by RRD is usually better than that of IRCR. GASII, and LIRPG aim to construct auxiliary reward functions that have high correlation to the environmental return. These two methods cannot achieve high sample efficiency since their objectives require on on-policy training.
Variance Penalty as Regularization. Figure also compares two implementations of randomized return decomposition. In most testing environments, RRD optimizing LRand-RD outperforms the un- biased implementation RRD-LRD. We consider RRD using LRand-RD as our default implementation since it performs better and its objective function is simpler implement. As discussed in sec- tion 3.2 the variance penalty conducted by RRD aims to minimize the variance of the Monte-Carlo estimator presented in Eq. (6) It serves as regularization to restrict the solution space of return decomposition, which gives two potential effeett: (1) RRD prefers smooth proxy rewards when the expressiveness capacity of reward network over-parameteriza batch gradient estimation can also be reduced when the variance of Monte-Carde Carlo estimator is small. In practice, this regularization would benefit the training stability. As presented in Figure [] RRD achieves higher sample efficiency than RRD-LRD in most testing environments. The quality of the learned policy of RRD is also better than that of RRD-LRD. It suggests that the regularized reward redistribution can better approximate the actual environmental objective.
the dataset. (2) The variance of mini-
4.2 ABLATION STUDIES
We conduct an ablation study on the used by randomized return decomposition. As discussed in section 3.2 the hyper-parameter K controls the interpolation ratio between return decomposition and uniform reward redistribution. trades off the accuracy of return reconstruction and variance regularization. evaluate RRD with set of choices of hyper-parameter K E (1,8, 16, 12, 64, 128]. The experiment results show that, although the sensitivity this hyper-paramett depends on the environment, a relatively large value of K generally achieves better performance, since it can better approximate the environmental objective. In this experiment, we ensure all runs use the same input size for mini- batch training, i.e., using larger value of K leads to less number of subsequences in the mini-batch.
K that represent the length of subsequences
Figure 2 we
8

---

Published as a conference paper at ICLR 2022
K-128
K-64
K-32
K-16
K-8
Ant-v2
HaltChectah-v2
Walker2d-v2
Humanoid-v2
Average Lpicolic Recurn
480
2800
131 0.5M
1M
1.5M 2M
2550 352
291 03533
133 1,31 2M
2.33 Timestops
331
061 0,538
131
1.5 3M
2.51
3M
0,551
131 L3M 2M
253 3M
Timesdeps
Timestops
Timestops
Figure 2: Learning curves of RRD with different choices of hyper-parameter K. The curves with
K 64 correspond to the default implementation of RRD presented in Figure [
More specifically, in this ablation study, all algorithm instances estimate the loss function LRandRRD using a mini-batch containing 256 transitions. We consider K = 64 as our default configuration. As presented in Figure 2 larger values give marginal improvement in most environments. The benefits of larger values of can only be observed in HalfCheetab-v2. We note that HaliChectah-v2 does not have early termination and thus has the longest average horizon among these locomotion tasks. It highlights the trade-off between the weight of regularization and the bias of subsequence estimation.
RELATED WORK
The ability of RL agents highly depends on the designs of reward functions. is widely observed that reward shaping accelerate learning (Mataric 1994 Ng et al. 1999 Devlin et al. 2011 Wu & Tian 2017] Song et al. 2019). Many previous works study how to automatically design auxiliary reward functions for efficient reinforcement learning. A famous paradigm, inverse RL (Ng & Russell 2000 Fu al. 2018), considers to recover a reward function from expert demon- strations. Another branch of work is learning an intrinsic reward function that guides the agent to maximize extrinsic objective (Sorg et al. [210 Guo et al. 2016). Such an intrinsic reward function can be learned through meeaaggaddienss (Zheng al. 20188 2020 or self-imitation (Guo al., 2018) Gangwani et al. 2019). A recent work (Abel et al. (021) studies the expressivity of Markov rewards and proposes algorithms to design Markov rewards for three notions of abstract tasks.
Reward Design.
Temporal Credit Assignment. Another methodology for tackling long-horize sequential deci- sion problems is assigning credits to emphasize the contribution of each single step over the temporal structure. These methods directly consider the specification of the step values instead of manipu- lating the reward function. The simplest example is studying how the choice of discount factor
affects the policy learning (Petrik & Scherrer 2008 Jiang al. 2013 Fedus al. 2019). Several previous works consider to extend the X-return mechanism (Sutton 1988 to a more generalized credit assignment framework, such as adaptive (Xu et al. 2018) and pairwise weights (Zheng et al. 2021). RUDDER (ArjonaMeddis, et al., 2019) proposes a return return-equivalent formulation for the credit assignment problem and establish theoretical analyses (Holzleitner et al., [202T). Aligned- RUDDER (Patil et al. (020)) considers to use expert demonstrations for higher sample efficiency. Harutyunyan et al. (2019) opens up a new family of algorithms, called hindsight credit assignment, that attributes the credits from a backward view. In Appendix [F] we cover more topics of related work and discuss the connections to the problem focused by this paper.
CONCLUSION
In this paper, we propose randomized return decomposition (RRD), a novel reward redistribution algorithm, to tackle the episodic reinforcement learning problem with trajectory feedback. RRD uses a Monte- Carlo estimator to establish a surrogate optimization problem of return decomposi- tion. This surrogate objective implicitly conducts a variance reduction penalty as regularization. We analyze its algorithmic properties by connecting with previous studies in reward redistribution. Our experiments demonstrate that RRD outperforms previous methods in terms of both sample efficiency and policy quality. The basic idea of randomized return decomposition can potentially generalize to other related problems with sum -emoopoooooiiioon structure, such as preference- ing (Christiano et al.) 2017) and multi-agent value decomposition (Sunehag et al. 2018). It is also promising to consider non non-linear decomposition as what is explored in multi-agent value factoriza- tion (Rashid et al. 2018). We leave these investigations as future work.
reward model-

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like thank Kefan Dong for insightful discussions. This work supported by the National Science Foundation under Grant CCF-2006526.
REFERENCES
David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup. and Satinder Singh. On the expressivity of Markov reward. Advances in Neural Information Process- ing Systems, 34, 2021.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in Al safety, arXiv preprint arXiv:1606.06560 2016.
Saidhiraj Amuru and Michael Buehrer. Optimal jamming using delayed learning. In 2014 IEEE Military Communications Conference, pp. 1528-1533. IEFE, 2014.
Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. (048-5058, 2017.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89- 119,,,999129, 2008.
Jose A Arjona- Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brand- stetter, and Sepp Hochreiter. RUDDER: Return decomposition for delayed rewards. In Advances in Neural Information Processing Systems, volume 32, 2019.
Richard Bellman. Dynamic programming. Princeton University Press, 89:92, 1957.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991, PMLR, 2020.
Léon Bottou, Jonas Peters, Joaquin Quinenlro-Candela. Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14 (11),0113
Yann Bouteiller, Simon Ramstedt, Giovanni Beltrame, Christopher Pal, and Jonathan Binas. Re- inforcement learning with random delays. In International Conference on Learning Representa- tions, 2021.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl gym. arXiv preprint arXiv:1606.01540. 2016.
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Marc G Belle- mare. Dopamine: A research framework for deep reinforcement learning. arXiv preprint 10110:1812.06110, 2018.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforce- ment learning with once-per-e feedback. Advances in Neural Information Processing Sys- tems, 34, 2021.
Shi- Yong Chen, Yang Yu, Qing Da Jun Tan, Hai-Kuan Huang, and Hai-Hong Tang. Stabilizing reinforcement learning in dynamic environment with application to online recommendation. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1187-1196, 2018.
Xinshi Chen, Yu Li, Ramzan Umarov, Xin Gao, and Le Song. Rna secondary structure prediction by learning unrolled algorithms. In International Conference Learning Representations, 2020.
10

---

Published as a conference paper at ICLR 2022
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing sys- tems, 30, 2017.
Edward Clarke. Multipart pricing of public goods. Public choice, pp. 17-33, 1971.
Sam Devlin, Daniel Kudenko, and Marek Grzeš. An empirical study of potential-base reward shaping and advice in complex, multi-agent systems. Advances in Complex Systems, 14(02): 251-278, 2011.
Daniel Dewey. Reinforcement learning and the reward engineering principle. In 2014 AAAI Spring Symposium Series, 2014.
Yali Du, Lei Han, Meng Fang, Tianhong Dai, Liu, and Dacheng Tao. LIIR: learning individ- ual intrinsic reward multi-agent reinforcement learning. Advances in Neural Information Processing Systems, pp. 4403-4414, 2019.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7288-7295, 2021.
William Fedus, Carles Gelada, Yoshua Bengio, Mare G Bellemare, and Hugo Larochelle. Hyper- bolic discounting and learning over multiple horizons. arXiv preprint arXiv: (a0:::902000563 2019.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse rein- forcement learning. In International Conference on Learning Representations, 2018.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596, 2018
Tanmay Gangwani, Qiang Liu, and Jian Peng. Learning self- self-imitating diverse policies. In Interna- tional Conference on Learning Representations, 2019.
Tanmay Gangwani. Yuan Zhou, and Jian Peng. Learning guidance rewards with trajectory-space smoothing. In Advances in Neural Information Processing Systems, volume 33, pp. 822-832, 2020.
Theodore Groves. Incentives in teams. Econometrica:
Journal of the Econometric Society, pp-
617-631, 1973.
Xiaoxiao Guo, Satinder P Singh, Richard L Lewis, and Honglak Lee. Deep learning for reward design improve Monte Carlo tree search in ATARI games. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp. 1519-1525, 2016.
Yijie Guo, Junhyuk Oh, Satinder Singh, and Honglak Lee. Generative adversarial self-imitation learning. arXiv preprint arXiv: 1812.00950, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018a.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint arXiv:1812.00 1812.05955 2018b.
Beining Han, Zhizhou Ren, Zuofan Wu, Yuan Zhou, and Jian Peng. Off-policy reinforcement learn- ing with delayed rewards. arXiv preprint arXiv:2106.1188 11854, 2021.
Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nico- las Heess, Hado P van Hasselt, Gregory Wayne, Satinder Singh, Doina Precup. et al. Hindsight credit assignment. In Advances in neural information processing systems, volume 32, pp. 12488- 12497, 2019.
11

---

Published as a conference paper at ICLR 2022
Daniel Hein, Stefan Depeweg, Michel Tokic, Steffen Udluft, Alexander Hentschel, Thomas A Run- kler, and Volkmar Sterzing. A benchmark environment motivated by industrial control problems. In 2017 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1-8. IEEE, 2017.
Amélie Héliou, Panayotis Mertikopoulos, and Zhengyuan Zhou. Gradient-fres online learning in continuous games with delayed rewards. In International Conference Machine Learning, pp- 4172-4181. PMLR, 2020.
Todd Hester and Peter Stone. TEXPLORE: real-time sample-efficient reinforcement learning for robots. Machine learning, 90(3):385-429) 2013.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural information processing systems, volume 29, pp. 4565-45747 2016.
Markus Holzleitner, Lukas Gruber, José Arjona-Medinne Johannes Brandstetter, and Sepp Hochre- iter. Convergence proof for actor-critic methods applied to PPO and RUDDER. In Transactions on Large-Scale Data-and Knowledge-Centee Centered Systems XIVIII, pp. 105-130. Springer, 2021.
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 1181-1189, Citeseer, 2015.
Konstantinos Katsikopoulos and Sascha Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE transactions automatic control, 48(4):568-574, 2003.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International
Conference on Learning Representations, 2015.
Ron Kohavi and David Wolpert. Bias plus variance decomposition for zero-one loss functions. In Proceedings of the Thirteenth International Conference International Conference Machine Learning, pp. 275-283, 1996.
Kimin Lee, Laura Smith, and Pieter Abbeel. PEBBLE: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. In International Conference on Machine Learning, 2021.
Lei Lei, Yue Tan, Kan Zheng, Shiwen Liu, Kuan Zhang, and Xuemin Shen. Deep reinforcement learning for autonomous internet of things: Model, applications and challenges. IEEE Communi- cations Surveys & Tutorials, 2723):1722 2020.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Inter- national Conference on Learning Representations, 2016.
Yang Liu, Yunan Luo, Yuanyi Zhong, Xi Chen, Qiang Liu, and Jian Peng. Sequence modeling of temporal credit assignment for episodic reinforcement learning. arXiv preprint arXiv: 190:::99511..1111 13420, 2019.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides competitive approach reinforcement learning, arXiv preprint arXiv:1803.07055 2018.
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. In Proceedings of the 15th ACM workshop on hot topics in networks, pp. 50-56, 2016.
Maja Mataric. Reward functions for accelerated learning. Machine learning, pp. 181-189, 1994.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51 518(7540):5295533 2015.
Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
12

---

Published as a conference paper at ICLR 2022
Somjit Nath, Mayank Baranwal, and Harshad Khadilkar. Revisiting state augmentation methods for reinforcement learning with stochastic delays. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pp. 1346-1355, 2021.
Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning. Citeseer, 2000.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transforma- tions: Theory and application to reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning. pp. 278-287. Morgan Kaufmann Publishers Inc., 1999.
Duc Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Credit assignment for collective multia- gent RI with global rewards. In Advances in Neural Information P Processing Systems, volume 31, pp. 8102-8113 13, 2018.
Johan Nilsson, Bo Bernhardsson, and Bjöm Wittenmark. Stochastic analysis and control of real-time systems with random time delays. Automatica, 34(1):57-66 -4, 1998.
Vihang P Patil, Markus Hofmarcher, Marius-Constantin Dinu, Matthias Dorfer, Patrick M Blies, Johannes Brandstetter, Jose A Arjona-Medina, and Sepp Hochreiter. Align-RUDDER: Learning from few demonstrations by reward redistribution. arXiv preprint arXiv:2009. 14t.:00009.4108,, 2020.
Marek Petrik and Bruno Scherrer. Biasing approximate dynamic programming with a lower discount factor. Advances in neural information processing systems. 21:1265- 2008.
Mariya Popova, Olexandr Isayev, and Alexander Tropsha. Deep reinforcement learning for de novo drug design. Science advances, 4(7)xeaap7885, 2018.
Hazhir Rahmandad, Nelson Repenning, and John Sterman. Effects of feedback delay on learning.
System Dynamics Review, 25(4):309-338 2009.
Jette Randløv and Preben Alström. Learning to drive bicycle using reinforcement learning and shaping. In International Conference on Machine Learning, pp. 463-471. Citeseer, 1998.
David Raposo, Sam Ritter, Adam Santoro, Greg Wayne, Theophane Weber, Matt Botvinick, Hado van Hasselt, and Francis Song. Synthetic returns for long-term credit assignment. arXiv preprint 102.::2102.12425, 2021.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent rein- forcement learning. In International Conference on Machine Learning, pp. 4295 4304. PMLR, 2018.
Erik Schuitema, Lucian Buşoniu, Robert Babuška, and Pieter Jonker. Control delay in reinforcement learning for real-time dynamic systems: a memoryless approach. In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3226-3231. IEEE, 2010.
Sarjinder Singh. Advanced Sampling Theory With Applications: How Michael"" Selected"" Amy, volume 2. Springer Science Business Media, 2003.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 5887-5896. PMLR, 2019.
Shihong Song, Jiayi Weng, Hang Su, Dong Yan, Haosheng Zou, and Jun Zhu. Playing FPS games with environment-wwan hierarchical reinforcement learning. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pp. 3475-3482, 2019.
Jonathan Sorg, Richard I. Lewis, and Satinder Singh. Reward design via online gradient ascent. In Advances in Neural Information Processing Systems, volume 23, pp. 2190-2198, 2010.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. dcompsseoooooiition networks for cooperative aulti-agent learning based on team reward. Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, pp. 2085-2087 2018
13

---

Published as a conference paper at ICLR 2022
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9 (1):9444, 1988.
Wei Tang, Chien-Ju Ho, and Yang Liu. Bandit learning with delayed impact of actions. Advances in Neural Information Processing Systems, 34, 2021.
Arash Tavakoli, Mehdi Fatemi, and Petar Kormushev. Learning to represent action values as hypergraph on the action vertices. In International Conference on Learning Representations, 2021.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-33 38,3,, 1961.
Thomas Walsh, Ali Nouri, Lihong Li, and Michael L. Littman. Leamning and planning in envi- ronments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18(1):83-055 2009.
Jianhao Wang, Zhizhou Ren, Beining Han, Jianing Ye, and Chongjie Zhang. Towards understanding cooperative multi-agent q-learning with value factorization. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021a
Jianhao Wang. Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex dueling multi-agent q-learning. In International Conference on Learning Representations, 2021b.
Jianhong Wang, Yuan Zhang, Kae-Kyun Kim, and Yunjie Gu. Shapley Q-value: local reward approach to solve global reward games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 2295. 2020.
Christian Wirth, Johannes Fürnkranz, and Gerhard Neumann. Model-free preference-based rein- forcement learning. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
Yuxin Wu and Yuandong Tian. Training agent for first-person shooter game with actor-critic cur- riculum learning. In International Conference on Learning Representations, 2017.
Advances in Neural Information Processing Systems, volume 31, pp. 2396-2407, 2018. Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-gradien reinforcement learning. In
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. In Advances in Neural Information Processing Systems, volume 31, pp. 4644 4654, 2018.
Zeyu Zheng, Junhyuk Oh, Matteo Hessel, Zhongwen Xu, Manuel Kroiss, Hado Van Hasselt, David Silver, and Satinder Singh. What learned intrinsic rewards capture? In International Confer- ence on Machine Learning, pp. 11436-1 1446. PMLR, 2020.
Zeyu Zheng, Risto Vuorio, Richard Lewis, and Satinder Singh. Pairwise weights for temporal credit assignment. arXiv preprint arXiv:2102.04999 2021.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter Glynn, Yinyu Ye, Li-Jia Li, and Li Fei-Fei. Distributed asynchronous optimization with unbounded delays: How slow can you go? International Conference on Machine Learning, pp. 5970-5979. PMLR, 2018
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning generalized linear contextual bandits with stochastic delays. In Advances in Neural Information Processing Systems, volume 32, pp- 5197-5208, 2019a.
Zhenpeng Zhou, Steven Kearnes, Li Li. Richard N Zare, and Patrick Riley. Optimization of molecules via deep reinforcement learning. Scientific reports, 9(1):1-10, 2019b.
14

---

Published as a conference paper at ICLR 2022
A
OMITTED PROOFS
Theorem (Loss Decomposition). The surrogate loss function CRand-RD(O)) can be decomposed to two terms interpolating between return decomposition and uniform reward redistribution.
T I
Σ Ro(si, ai) SEI
RaD (0) = LRD(O) - E TND
Var Impr()
(9)
variance of the Monte-Cario estimator
K
(0)
E TND
T
Var (Se,
T
(10)
return decomposition
wniform reward redistribuaion
Interpolation weight
where denotes the length of sumpled subsequences defined Eq.
Proof. First, note that random sampling serves unbiased estimation. i.c.,
E
T
Ro( an)
T-1
Σ
Ro(se, ar) = (T).
I-pr(+)
7
EE
We can decompose loss function LRand-RD (0) as follows:
(Tp(T) T Σ
CRand RD (0)
E TDD
E Impp(())
Ro(se, ai)
1EI
Ro an) 27]
E TwD
E I-pp(())
Rep(T) RT) + Rop,o(T)
T
Σ FET
[
Rop(T) Rup,o(t)) 27
E
E T.pp(()
rnD
=Cx](A)
+ E TnD
((Hpp(T) Rop.o(T))
[ (Ranelt)
T
Σ Ro(Se: ar)
Impr(()
I
=0
(ep.o(T) T Σ Ro(str
+ E TND
Impr(t))
EET
=Var((T//ZZ)>> Ever Ro(o).)))
(R) + E T-D
Var (mpr(.)
Ro ar)
EE
Note sampling distribution defined in Eq. 7 refers to "sampling without replacement" Singh 2003 whose variance can be further decomposed as follows:
]
T
CRand-RD(()) = LRD(O)+ + E TND
Var Impr(()
Ro)
Ro ar)
I
PET
Lxv(( +
T2.
Var (St
(Ro(s))
1 (11 1- T-
K -
TND
K
15

---

Published as a conference paper at ICLR 2022
The proof of Theorem follows particular form of bias-variance decomposition formula (Kohavi & Wolpert 1996). Similar decomposition form can also be found in other works in the literature of reinforcement learning (Antos et al. 2008).
Proposition 1 (Surrogate Upper Bound). The randomized return decomposition loss RRand (0) is an upper bound of the actual return decomposition loss function LRD (0), i.e., Rand--D (0) 2 LRD (0).
Proof. Note that the second of Eq. (9) in Theorem expresses the variance of Monte-Carlo estimator which is clearly non-negative. It directly gives (Rn 2 (R)(O).
An alternative proof of Proposition Caan directly given by Jensen's 's inequality.
Proposition 2 (Objective Gap). Let Cland RD denote the randomized relurn decomposition loss
that samples subsequences with length K. The gap between L(K) (0) and LND(O) can be reduced Rand-RD
by using larger values of hyper-parameter K.
v0,
Rand RD (0) 2
((2) Rond RD (0) 2 ...
((T-1) Rand RD
(TT (0) Rand (0) LRD(O).
(11)
monotonically decreases the hyper- parameter K increases. When K = T, this coefficient is equal to zero. It derives Eq. in the
Proof. In Eq. (T) of Theorem the last term X
[-
given statement.
Proposition 3 (Uniform Reward Redistribution). Assume all trajectories have the same length and the parameterization space of f serves universal representation capacity. The optimal solution 6 of minimizing Cl Randd-RD (0) is stated as follows:
Ro- (s- E (Rp(t/ (s,a))
(12)
where C(I) Ro
(0) denotes the randomized return decomposition loss with K 1.
Proof. Note that we assume all trajectories have the same length. The optimal solution of this least- squares problem is given by
Re- (s, = min E. -
(s,a)
rER
1
r) (
min E
T2
rell TND
1
(Rp((t)/ -) (s.
-iin
E
T TND
min E rER AND
(s,a) (s,
E [R (s,a) 7]
TDD
which depends on the trajectory distribution in dataset D.
If we relax the assumption that all trajectories have the same length, the solution of the above least- squares problem would be weighted expectation as follows:
Ro. (s, a) min E rER TND
(Rap(T) T, .r)² (3,0)
-
min E. T3 (epl(T/TT--r)) (s,0)Er rER TND
ErED( Tr Rep(T)
ETED( T?
where T, denotes the length of trajectory r. This solution can still be interpreted as a uniform reward redistribution, in which the dataset distribution is prioritized by the trajectory length.
16

---

Published as a conference paper at ICLR 2022
B EXPERIMENT SETTINGS AND IMPLEMENTATION DETAILS
B.1 MuJoCo BENCHMARK WITH EPISODIC REWARDS
MuJoCo Benchmark with Episodic Rewards. We adopt the same experiment setting as Gang-
wani et al. (2020) and compare our approach with baselines in a suite of MuloCo locomotion bench-
mark tasks with episodic rewards. This experiment setting is commonly used in the literature (Mania
et al. 2018, Guo et al. 2018: Liu et al.) 2019] AArjona-eedini 2020 The environment simulator is based on OpenAl Gym (Brockman et al. 2016). These tasks are long-horizon with maximum trajectory length T 1000. We modity the reward function of these environments to set up an episodic-rewar setting. Formally, on non-terminal states, the agent will receive
et al. 2019 Gangwani et al., 2019]
signal instead of the per-step dense rewards. The agent obtain the episodic feedback (T) at the last step of the rollout trajectory, in which (ep(T) is computed by the sum- mation of per-step instant rewards given by the standard setting.
Slyper-Parameee Configuration For MuJoCo Experiments. In MuJoCo experiments, the pol- icy optimization module of RRD is implemented based on soft actor-critic (SAC; [Harnojj et al., 2018ap. We evaluate the performance of our proposed methods with the same configuration of hyper- parameters all environments. The hyper-parameters of the back-end SAC follow the official tech- nical report (Haarnoja et al., 2018b). We summarize our default conf configuration of hyper-parameters as the following table:
Default Configuration
discount factor y
0.99
# hidden layers (all networks)
neurons per layer activation
256 ReLU
optimizer (all losses)
Adam (Kingma & Ba 2015)
learning rate
3
initial temperature Q'nit
1.0
target entropy
dim(.4)
Polyak-averaging coefficient
0.005
# gradient steps per environment step gradient steps per target update
transitions in replay buffer transitions in mini-batch for training SAC
10
256
# transitions in mini-batch for training RS
256
# transitions per subsequence (K)
64
subsequences in mini-batch for training Rs
Table 1: The hyper-parameter configuration of RRD in MuloCo experiments.
In addition to SAC, we also provide the implementations upon DDPG (Lillicrap et al. 2016) and TD3 (Fujimoto et al., 2018) in our Github repository
B.2 ATARI BENCHMARK WITH EPISODIC REWARDS
Atari Benchmark with Episodic Rewards. In addition, we conduct experiments in suite of Atari games with episodic rewards. The environment simulator based OpenAl Gym (Brockman et al. 2016). Following the standard Atari pre- pre-processing proposed Mnih et al. (2015), we rescale each RGB frame to an x 84 luminance map, and the observation constructed as a stack recent luminance maps. We modify the reward function of these environments to set up episodic- reward setting. Formally, on non-terminal states, the agent will receive a zero signal instead of the per-step dense rewards. The agent can obtain the episodic feedback Rap(T) at the last step of the rollout trajectory. in which (ep(T) (r) is computed by the summation of per-step instant rewards given by the standard setting.
17

---

Published as a conference paper at ICLR 2022
Ptyper-Parameed Configuration For Atari Experiments. In Atari experiments, the policy op- timization module of RRD implemented based on deep Q-network (DQN; Mnih et al. 2015). We evaluate the performance of our proposed methods with the same configuration of hyper- areerpprraeetrs all environments. The aapeer-prramterr of the back-end DQN follow the technical report (Castro al. 2018). We summarize our default configuration of typer-parameters the following table:
Hapem-Parameter
Default Configuration
discount factor 7
0.99
stacked frames agent observation
# noop actions while starting new episode
30
network architecture
DQN (Mnih al.
2015
optimizer for Q-values learning rate for Q-values
Adam
Kingma & Ba
2015
6.25 10
optimizer for Ra learning rate for Ro
Adam
Kingma & Ba
2015
3 10
exploration strategy decaying range- start value decaying range end value # timesteps for decaying schedule
e-greedy
1.0
0.01
250000
# gradient steps per environment step gradient steps per target update
0.25
8000
transitions in replay buffer transitions in mini-batch for training DQN
10
32
# transitions in mini-batch for training Rs
32
# transitions per subsequence (K)
32
# subsequences in mini-batch for training Rg
Table 2: The
configuration of RRD in Atari experiments.
B.3 AN ALTERNATIVE IMPLEMENTATION OF RANDOMIZED RETURN DECOMPOSITION
Recall that the major practical barrier the least-squares-basee based return decomposition method spec- ified by (0) is its scalability in terms of the computation costs. The trajectory-wise episodic reward the only environmental supervision for reward modeling. Computing the loss function (RD(@) with single episodie reward label requires enumerate all state-action pairs along the whole trajectory.
Theorem I motivates unbiased implementation of randomized return decomposition that opti- mizes (RD(() (0) instead of LD By rearranging the terms of Eq. (10), we can obtain the difference between LR and (f) as follows:
T
Ro ae)
CRand-RD (RD( = Var
I-pr(-)
I
SEI.
Note our sampling distribution pr(:) defined in Eq. 7 refers "sampling without replacement" Singh 2003) whose variance can be estimated as follows:
T K EvEr [Ro(se, ar) Ro(
T T
Var I-)p(())
ao)s)
= 2
E I-pr(-)
T
K(K-1)
EET
where Ro( 1 EIEI Ro(se, Thus obtain an unbiased estimation of this variance
penalty by sampling subsequence I. By subtracting this estimation from P RD (0),
18

---

Published as a conference paper at ICLR 2022
obtain unbiased estimation of (R)( More specifically, we use the following sample-based loss function to substitute Eq. (13 in implementation:
(RD(O) = M
M
(Tp
T
Σ IET
I
f=1
M TT K)
Σ
(oo())
1 I
Σ
Ro(3))))31)
LEI
BEI,
The above loss function can be optimized through the same mini-batch training paradigm as what is presented in Algorithm
C EXPERIMENTS ON ATARI BENCHMARK WITH EPISODIC REWARDS
RRD (ours)
RRD-Cgo (ours)
IRCR
RUDDER
Assault
MsPacman
Pong
RoadRunner
Median Epiuodlic Return
190
C20
0.3
806
10M
Timmestops
Timesteps
Timestepo
Timestepa
Figure 3: Learning curves on a suite of Atari benchmark tasks with episodic rewards. These curves are plotted from 5 runs with random initializations. The shaded region indicates the standard devi- ation. To make the comparison more clear, the curves are smoothed by averaging 10 most recent evaluation points. We set up an evaluation point every 10 timesteps.
Note that our proposed method does not restricts its usage to continuous control problems. It can also be integrated in DQN-based algorithms to solve problems with discrete-action space. We eval- uate the performance of our method built upon DQN in several famous Atari games. The reward redistribution problem these tasks is more challenging than that MuJoCo locomotion bench- mark since the task horizon of Atari is much longer. For example, the maximum task horizon in Pong can exceed 20000 steps in a single trajectory. This setting highlights the scalability advantage of our method, i.e., the objective of RRD can be optimized by sampling short subsequences whose computation cost is manageable. The experiment results are presented in Figure 3 Our method outperforms all baselines in 3 out of 4 tasks. We note that IRCR outperforms RRD in RoadRunner. It may be because IRCR is non-parametric and thus does not suffer from the difficulty of processing visual observations.
D VISUALIZING THE PROXY REWARDS OF RRD
Ant-v2
HallCheetah-v2
Walker2d-v2
Humanoid-v2
Reward.Kefh.. Reti.a)
40
AIC
1.33
02
K00 MID:
(00
-201
420
Agent Forward Motion
Agoat Formard Mation
Agont Forward Mation
Agent Forward Motion
Figure 4: Visualization of the proxy rewards learned by RRD in MuJoCo locomotion tasks.
19

---

Published as a conference paper at ICLR 2022
In MuJoCo locomotion tasks, the goal of agents is running towards fixed direction. In Figure we visualize the correlation between per-step forward distance and the assigned proxy reward. We uniformly collected 10 samples during the first 10t training steps. "Agent Forward Motion" denotes the forward distance assigned at that step. It shows that the learned proxy reward has high correlation to the forward distance at that step.
single step. "Proxy Reward Ro a)" denotes the immediate proxy reward
E AN ABLATION STUDY ON THE
OF IRCR
We note that Gangwani et al. 2020 different hyyper-parameter configuration from the standard SAC implementation HHarnojj et al. 20185). The differences exist in two hyper-parameters:
Hyper- Parametrr
Default Configuration
Polyak-averaging coefficient # transitions in replay buffer # transitions in mini-batch for training SAC
0.001
3 10
512
Table 3: The hyper-parameter used by Gangwani et al. (2020) in MuJoCo experiments.
To establish rigorous comparison, we evaluate the performance of IRCR with the hyper- parammer configuration proposed by Haarnoja et al. 2018b). so that IRCR and RRD use the same hyper- parameters in their back-end SAC agents. The experiment results are presented in Figure
(ours)
(ablation)
Average Episuale Roturn
Ant-v2
HalfCheetah-v2
W aaakker2d-v2
H Humanoid-w2
1810
0331 1ST 13M IN 2.5 INT Timestps
0.5
135
2MT
133 AN
1.51 23S
Timostops
Timestops
Timesteps
Average Rpiandic Rerurn
Reacher-y2
Swimmer-v2
Hopper-v2
H HumanoidStandup-22
140
6ES IM LSM 2M 3:50 TM
1ST 0.5M T3 1351 2M EASE XNI
[M 3.5M
L.M 251 1:5M XSI Timesteps
1.5M 23M 3S
Timestops
Timestops
Timextps
Figure 5: An ablation study on the hyper-parameter configuration of IRCR. The curves of "IRCR" refer to the performance of IRCR using the hyper-parameter setting proposed by Gangwami et al. (2020) The curves of "IRCR (ablation)" refer the performance of IRCR using the hyper- parameters stated in Table [
All curves are plotted from 30 runs with random initializations.
As shown in Figure 5 the environments. Although using some cases, the overall performance cannot outperform RRD.
tuned by Gangwani et al. 2020 is more stable in most stated in Table can improve the performance in
F RELATED WORK
Delayed Feedback.
Tackling environmental delays is a long-lasting problem in reinforcement
learning and control theory (Nilsson et al., 1998 Walsh et al. 2009 Zhou et al. 2018 2019a Héliou al. 2020 Nath et al. [2021] [Tag et al. (021). In world applications, almost environmental signals have random delays (Schuitema et al. 2010 Hester & Stone 2013 Amuru & Buehrer 2014
Lei et al. 2020), which a fundamental challenge for the designs of RL algorithms. A classical method to handle delayed signals is stacking recent observations within small sliding window as
20

---

Published as a conference paper at ICLR 2022
the imput for decision-making making (Katsikopoulos & Engelbrecht 2003). This simple transformation can establish a Markovian environment formulation, which is widely used to deal with short-term environmental delays (Mnih et al. 2015). Many recent works focus establishing sample-efficient off-policy RI. algorithm that is adaptive to delayed environmental signals (Bouteiller et al. 2021] HHnn et al.) (02T). In this paper, consider extreme delay of reward signals, which is harder problem setting than short-term random delays.
Reward Design. The ability of reinforcement learning agents highly depends on the designs of reward functions. It is widely observed that reward shaping can accelerate learning (Mataric 1994. Ng al. 1999, Devlin et al.] 201T, Wu Tian, 2017; [Song et al. 2019). Many previous works study how automatically design auxiliary reward functions for efficient reinforcement learning. A famous paradigm, inverse reinforcement learning (Ng & Russell 2000; Fu et al., 2018), considers to recover a reward function from expert demonstrations. Several works consider to learn reward function from expert labels of preference comparisons (Wirth et al., (016)) Christiano et al.) 2017] Lee al., 2021), which is form of weak supervision. Another branch of work is learning an intrinsic reward function from experience that guides the agent to maximize extrinsic objective (Sorg al.,, 2010; Guo al., 2016). Such intrinsic reward function
be learned through meta-
gradients (Zheng et al.] 2018 2020) or self-imitation (Guo et al., [018)] Gangwani et al.] 2019). A
recent work (Abel et al. 2021) studies the expressivity of Markov rewards and proposes algorithms
to design Markov rewards for three notions of abstract tasks.
Temporal Credit Assignment. Another methodology for tackling long-horizen sequential deci- sion problems is assigning credits to emphasize the contribution of cach single step over the temporal structure. These methods directly consider the specification of the step values instead of manipu- lating the reward function. The simplest example is studying how the choice of discount factor ?
affects the policy learning (Petrik & Scherrer [0088] Diang et 2013 Fedus et al.] (019). Several previous works consider to extend the X-return mechanism (Sutton 1988) to a more generalized credit assignment framework, such as adaptive (Xu et al. 2018) and pairwise weights (Zheng formulation for
al., 2021). RUDDER (Arjona- Medina al., 2019) proposes a return-equivalen
the credit assignment problem and establish theoretical analyses (Holzleitner et al. (221). Aligned- RUDDER (Patil et al.) 2020) considers to use expert demonstrations for higher sample efficiency. Harutyunyan et al. (2019) opens up new family of algorithms, called hindsight credit assignment, that attributes the credits from a backward view.
Value Decomposition. This paper follows the paradigm of reward redistribution that aims to de- compose the return value to step-wise reward signals. The simplest mechanism in the literature is the uniform reward redistribution considered by Gangwani et al. (2020). It can be effectively integrated with off-policy reinforcement learning and thus achieves state-of-the-art performance in practice. Least-squares-basee reward redistribution is investigated by [Erroni al. (2021) from theoretical point of view. Chatterji et al. (202T) extends the theoretic results to the logistic reward model. game theory and multi-agent reinforcement learning, a related problem how to attribute global team reward to individual rewards (Nguyen et al.) (2018] Du et 2019 Wang et al.. 2020).
which provide agents incentives to optimize the global social welfare (Vickrey 1961 Clarke 1971
Groves] 1973: Myerson 1981). A promising paradigm for multi-agent credit assignment is using
structural value representation (Sunehag et al. 2018; Rashid et al. 2018; Son et al.) 2019 Böhmer
et al. 2020 Wang et al., 202 which supports end-to-end temporal difference learning. This paradigm transforms the value decomposition to the structured prediction problem. A future work integrating prior knowledge of the decomposition structure as many previous works for structured
prediction (Chen et al.) 2020 Tavakoli et al. (021).
21


Reviews:
[{"review_id": "xbiqAbYZ8Fu", "reviewer": "Reviewer_73tN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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).\n\nThe 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.\n\nMinor grammar issue: “Despite the Monte-Carlo estimator is unbiased,”\n\nQuestions:\n- 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.\n- “We evaluate the performance of our proposed methods with the same configuration of\nhyper-parameters in all environments.”  To clarify, all algorithms in the experiments (not just your two proposed methods) used these hyperparameters, correct?\n- Was any hyperparameter tuning performed?  How were the hyperparameters chosen?\n- 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.\n- 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?)\n\n**Update after the rebuttal and reading the other reviews:**\n\nMost 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.)\n\n**Update after final comments below:**\n\nI am updating my score to an 8; see below.", "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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gLQhT33DY3P", "reviewer": "Reviewer_UMu2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Experiments:\n\nExperiments 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. \n\n- Credit assignment and reward functions:\n\n\tThrough 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. \n\n- RUDDER markov proxy reward function:\n\n  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?\n\n- Return Equivalence\n \tOne 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.\n\n- Equation (4) \n\tThe 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.  \n\nMissing related work:\n\n[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.\n\n[1] Align-Rudder: Learning from few demonstrations by reward redistribution\n\n[2] Hindsight credit assignment\n", "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. \n", "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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "I1QG3e_P5C", "reviewer": "Reviewer_qFZu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Paper is very well written and flows well. The theory is well presented and discussed and is relatively easy to understand.\n- 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. \n- Experiments and ablations seem very thorough. \n\nWeaknesses:\n- The related work (section 5) seems relatively small. The paper would benefit from more text here. \n- 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.\n- 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_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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HDeWnkujV2T", "reviewer": "Reviewer_ySc8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality & significance**:\nThis 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.\n\n**Quality**:\nOverall 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.\n1. 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.\n2. 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.\n\n**Clarity**:\nThis paper is well written and easy to follow.\n\n**Minor issues**:\nIn 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)