Off-Policy Reinforcement Learning with Delayed Rewards
Authors: Beining Han
Zhizhou Ren
Zuofan Wu
Yuan Zhou
Jian Peng
Venue: ICLR 2022 Submitted (2022)
Keywords: Delayed Rewards
Off-Policy Reinforcement Learning

Abstract: We study deep reinforcement learning (RL) algorithms with delayed rewards. In many real-world tasks, instant rewards are often not readily accessible or even defined immediately after the agent performs actions. In this work, we first formally define the environment with delayed rewards and discuss the challenges raised due to the non-Markovian nature of such environments. Then, we introduce a general off-policy RL framework with a new $Q$-function formulation that can handle the delayed rewards with theoretical convergence guarantees. For practical tasks with high dimensional state spaces, we further introduce the HC-decomposition rule of the $Q$-function in our framework which naturally leads to an approximation scheme that helps boost the training efficiency and stability. We finally conduct extensive experiments to demonstrate the superior performance of our algorithms over the existing work and their variants.

Under review as a conference paper at ICLR 2022
OFF-POLICY REINFORCEMENT LEARNING WITH DELAYED REWARDS
Anonymous authors Paper under double-blind review
ABSTRACT
We study deep reinforcement learning (RL) algorithms with delayed rewards. In many real-world tasks, instant rewards are often not readily accessible or even de- fined immediately after the agent performs actions. In this work, we first formally define the environment with delayed rewards and discuss the challenges raised due to the non-Markovian nature of such environments. Then, we introduce a general off-policy RI. framework with a new Q-function formulation that can handle the delayed rewards with theoretical convergence guarantces. For practical tasks with high dimensional state spaces, we further introduce the HC-dccomposition rule of the Q-function in our framework which naturally leads to an approximation scheme that helps boost the training efficiency and stability. We finally conduct extensive experiments to demonstrate the superior performance of our algorithms over the existing work and their variants.
INTRODUCTION
Deep reinforcement learning (RL) aims at maximizing the cumulative reward of a MDP. To apply RL algorithms, the reward has to be given at every state-action pair in general (i.e., r(s, a)). With good and high quality reward function, RL can achieve remarkable performance, e.g. AlphaGo Zero for Go (Silver et al.) 2017). DQN(Mnih et al. 2015) for Atari, SAC (Haarnoja et al. 2018b) for robot control e.t.c. Recently, RL has been applied in many other real world settings beyond
games and locomotion control. This includes industrial process control (Hein et al.] 2017)) traffic
optimization (Gong et al., 2019 Lin al., 2018), molecular design (Olivecrona et al. [0017] and resource allocation (Xu et al. (2018). However, in many of these real-world scenarios, Markovian and instant per-step rewards are hard or impossible to obtain or even clearly defined. In practice, it becomes more reasonable to use a delayed reward of several consecutive steps as feedback. For example, in traffic congestion reduction (Gong et al.] (201)), the amount of decreased congestion for a single traffic light switch is hard to define in practice while it is more adequate to use the average routing time consumed for the vehicles as the feedback. The latter delayed reward which can only be obtained after the vehicles have passed the congestion (long after single switch). In molecular design, only the molecule formed after the final operation can provide a meaningful evaluation for the whole process (Olivecrona al.) 2017). In locomotion control where the feedback is generated by the interaction with the large environment, is usually the case that the frequency of the rewards generated from the environment's sensors is much lower than the frequency of the robot control, thus the rewards are given only every so often.
Despite the importance and prevalence of the delayed reward setting, very few previous research in RL has been focusing on problems with non-Markovian properties and delayed rewards. Besides, current RL algorithms lack theoretical guarantee under Mar-Mvikovian rewards and perform unsat- isfactorily in practice (Gangwani et al. 2020). Thus, in this paper, our goal is to better understand the properties of RL. with delayed rewards and introduce a new algorithm that can handle the de- layed reward both theoretically and practically. A key to our approach lies in the definition of the past-invariant delayed reward MDPs. Based on this definition, theoretical properties and algorith- mic implications are discussed to motivate the design of a new practical algorithm, which explicitly decompose the value function into components of both historical (H) and current (C) step infor- mation. We also propose number of ways to approximate such HC decomposition, which can be readily incorporated into existing off-policy learning algorithms. Experiments demonstrate that such approximation can improve training efficiency and robustness when rewards delayed.

---

Under review as a conference paper at ICLR 2022
2 PROBLEM FORMULATION
In order to characterize the delayed and non-Markovian reward signals, we introduce the Delayed Reward Markov Decision Process (DRMDP). In this work, we focus on DRMDP that satisfies the (PI) condition, which is satisfied in many real-world settings with delayed rewards.
2.1 PAST-INVARIANT DELAYED REWARD MDPs
In DRMDP, the transition of the environment is still Markovian and the agent can observe and interact with the environment instantly. However, rewards may be non-Markovian and delayed and are observed only once every few steps. More specifically, the time steps are divided into consecutive signal intervals of random lengths, and the reward signal generated during signal interval may depend on the vate-action sequence and observed only at the end of the interval. We formally define DRMDP follows.
Definition 1 (DRMDP). A Delayed Reward Markov Decision Process M (S, A. P,,, is described by the following parameters.
1. The state and action spaces are S and A respectively,
2. The Markov transition fransition.uuncionn is (( a) for each (s,a) E S x A; the initial state distribution is p(so).
3. The signal interval length is distributed according to qn(()), ie., for the i-th signal interval, its length n, is independently drawn from 9n(-).
4. The reward function r defines the expected reward generated for each signal interval: suppose Ti Testi, (s, ()t.tn during the i-th signal interval of length n4, then the expected reward for this interval is r(T:).
((5,, at),... (St+n-1, (t+n,11)) - is the state-action sequence
5. The reward discount factor is "..
In this work, we focus on the infinite-horizon DRMDP. We use (T, = (T,, (1.2, to denote a trajectory, where т; the state-action sequence during the i-th signal interval and n; the corresponding length. We also let l; be first time step of the i-th signal interval, i.e. 4
Σj=1 ny. Note that the reward r(T;) is revealed at time t; + n; 1 f,+1 - 1. We finally define the discounted cumulative reward of the trajectory (r,n) by R(T, n) := Σi= ((T)) The objective for DRMDP is to learn a policy π that maximized the expected discounted cumulative reward J (T) = (f(..))>[[B(( n)].
Augmented Policy Class, In DRMDP, the Markov policy class {x = [s)) might not achieve satisfactory performance because of the non- Mar-ooaoo nature of the reward function. Theoretically speaking. we need a more general policy class IT, = {T = x(a Te.s 8t)) is the index of the signal interval that & belongs to). A formal statement is included in Appendix B Unfortunately, policy optimization such an exponentially large space 11, is hard in practice, especially for high- dimensional problems. Thus, as trade-off, we consider the policy class 11, {iT π (arls,, t;)), which resembles the traditional Markov policy class, but is augmented with an extra parameter indicting the relative index of the current time step in the signal interval. Moreover, we focus on the PI-DRMDP problems, in which our algorithmic framework has theoretical guarantees.
Past-Invariant Delayed Reward Markov Decision Process is a DR- MDP M (S, A. qn 7, whose reward function satisfies the following Past-Invariant (PI) condition: for any two trajectory segments T₁ and T2 of the same length, and for any two equal- length trajectory segments oI and T2 such that the concatenated trajectories To Tf are feasible under the transition dynamics for all a, b {1,2}. it holds that
Definition 2 (PI-DRMDP).
r(T Tff o1))
r(72 o R)) r(z
Roughly speaking, in PI-DRMDP, the relative credit for different actions at each only depends on the experience the future and is invariant of the past. This property may relieve the agent from considering the past experience for decision making. A simple example of with PI condition is r(Teatn) Ditr - f(s,, a(),,a)), where f is per-step reward function. This kind of tasks is studied in many previous work (Zheng et al.) 2018 Oh et al. 2018; Klissarov & Precup 2020). We refer this kind of reward functions the sum-form.
2

---

Under review as a conference paper at ICLR 2022
In the worst case, there exists some bizarre reward design in PI-DRMDPs that still requires the optimal policy to take history information into consideration (see Appendix B). Despite the sub- optimality issue, we will show that our algorithmic framework guarantees policy improvement in HT. which is sufficient to support the design of actor-critic methods. Consequently, we are able to put forward practical RI. algorithm that achieve the SOTA performance in delayed-reward tasks. The overall contribution of our work is summarized in Table | and we leave the optimality of the DRMDP problems as future works.
Table 1: Contribution of our algorithm in different problem settings. Notice that MDP is degraded case of DRMDP, which has signal interval length fixed as 1.
Policy Improvement Policy Optimaiiyy
MDP PI-DRMDP DRMDP
Yes
Yes No
Yes
No
No
General Reward Function. In Definition | define the reward as a function of the state-action sequence of its signal interval. In general, we may allow reward functions with longer inputs which overlap with the previous signal intervals, e.g., maximal overlapping of c steps, rTT: ). The theoretical analysis in Section 3.1 and the empirical method in Section 3.2 can be directly extended to this general reward function. We provide detailed discussions in Appendix [B] for the general definition while we only consider e = 0 in the main text for the simplicity of the exposition.
2.2 OFF-POLICY RL IN PI-DRMDP
Deep Reinforcement Learning has achieved great success in solving sigh-dimensional MDPs prob- lems, among which the off-policy actor-critic algorithms SAC (Haarnoja et al.] 201 8a) and TD3 (Fujimoto et al., 2018) are the most widely used ones. However, since the rewards are delayed and non-Markovian in PI-DRDDP, directly applying these SOTA off-policy RL algorithms faces many challenges that degrade the learning performance. In this subsection, we briefly discuss the problems that arise in critic learning based on TD3 and similar problems also exist for SAC.
First, in PI-DRMDP, value evaluation with off- pff-policy samples brings off-policy bias. TD3 mini- mizes over 6 w.r.t.
L = ED (Re 2Q0 -Qo(
where (st, de: Re, S1+11) is sampled from the replay buffer D, R, 4++1 (++) and i = i(() is the index of the reward interval that t belongs to, and R. 0 otherwise. Qo represents the target value of the next state and d'41 is sampled from the smoothed version of the policy æ. Furthermore, in practical implementation, samples in the replay buffer D are not sampled from a single behavior policy /3 as in traditional off-policy RL (Sutton & Barto 2018). Instead, the behavior policy changes as the policy gets updated. Thus, we assume that samples are collected from sequence of behavior policies B = [Bx]
In the delayed reward setting, since the reward r(T,) depends on the trajectory of the whole signal interval (i.e., T;) instead of a single step, the function (2 a)) learned via Eq. [ will also have to depend on the trajectory in the signal interval upto time (i.e., Te:tt) rather than the single state- action pair at time t. Since the samples are collected under sequence of behavior polices B, different behavior policy employed at state 8; may lead to different distribution over a in Eq, (T. Consequently, Q (8t, ax) will be affected by this discrepancy and may fail to assign the accurate expected reward for the current policy. Please refer to Appendix B for detailed discussions.
Second, in addition to the issue resulted from off-policy samples, (s at) learned in Eq. { with on-policy samples in D may still be problematic. We formally state this problem via a simple sum- form PI-DRMDP in Appendix B whose optimal policy is in II, In this example, the fix point of Eq. (T) fails to assign the actual credit and thus misleads policy iteration even when the pre-update policy is already the optimal. We refer this problem as the fixed point bias.
Last but not least, the critic learning via Eq. I would suffer a relative large variance. Since R, varies between 0 and r(T;), minimization of TD-error (Taz) with mini-batch of data has large
3

---

Under review as a conference paper at ICLR 2022
variance. As result, the approximated critic will be noisy and relative unstable. This will further effect the policy gradients in Eq. (2).
VoJ(To)) ED (o(e,
Voro (5t)
(s))
To up, directly applying SOTA off- off-policy algorithms in PI-DRMDP will suffer from multiple problems (off-polic) bias, fixed point bias, large traning noise, etc). Indeed, these problems result in severe decline in performance even in the simplest task when (Gangwani al. 2020
METHOD
In this section, first propose novel definition of the Q-function (in contrast to the original Q- function) and accordingly design a new off-policy RL RL algorithm for PI-DRMDP tasks. This method has better theoretical guarantees in both critic learning and policy update. We then introduce a HC- decomposition fratoonrrmeeen framework for the proposed Q-function, which leads to easier optimization and better learning stability in practice.
3.1 THE NEW F-FUCCTION AND ITS THEORETICAL GUARANTEES
Since the non-Markov rewards make the original definition of Q-function ambiguous, we instead define the following new Q-function for PI-DRMDP tasks.
oC
2 (Traee+))= == B(r,n)
Σ 7 (((s))
Teat41
The new Q-function is defined over the trajectory segments T1,:++1, including all previous steps in sy 's signal interval. Besides, the expectation taken over the distribution of the trajectory (r, n) that is due to the randomness of the policy, the randomness of signal interval length and the transition dynamics. Despite the seemingly complex definition of Q, we provide a few of its nice properties that are useful for PI-DRMDP tasks follows. The proof' are listed in Appendix B
First, we consider the following objective function
C ED (R. + (6((T))422) 2Φ (T
(4)
where Te,442 Tr,2411 (81+1, ((411) (so that j i) if t not the last step of T₁, and Tr,
(S111) (44)) (so that = i+ 1) otherwise. Similarly to Eq. ( in Eq. (4). (Te,241, Rg, 8(41) is also sampled from D and d'+1 is sampled from æ correspondently. We may view Eq. (4p as an extension of Eq. I for Q However, with these new definitions, we are able to prove the following fact |
Fact 1. For any distribution D with non-zero measure for any Te Q (Te, is the unique fixed point of the MSE problem in Eq. (4). More specifically, when fixing 2p as the corresponding Q", the solution of the MSE problem is still Q".
Consequently. Q" can be found precisely via the minimization for tabular expressions. This helps to solve the problems in critic learning for PI-DRMDP. We next introduce Fact 2 which states that the order of Q" w.r.t. the actions any state st invariant the choice of Trat thanks to the PI condition.
Fact 2. For any Th,ss, That and 8t, at, d, which both Taa o 8t and That o st are feasible under the transition dynamics, Vn E II, we have that
Qº (Teat o (st, az)) Q (TEL o (st, = ( o (s,, a.)) @T(,r o (st. df)).
Fact 2 ensures that the policy iteration on Fa (a St, t- t.) with an arbitrary Q" (Teest a (St, at)) results in the same T E II. Consequently, we are able to prove the convergence theorem for the policy iteration with the Q-function.
The definition of Q" and Fact also holds in DRMDP and for TT,
4

---

Under review as a conference paper at ICLR 2022
Proposition 1. (Policy Improvement Theorem for PI-DRMDP) For any policy my E II, the policy iteration w.r.t. e** produces policy Tk+1 E II such that VT,,,+1, it holds that
1 (Tene++) 2 2 (Teae+1),
which implies that J (TT+1)) 2 (TA).
Thus, the off ooflccy value evaluation with Eq. and the policy iteration in Proposition guarantee that the objective function is properly optimized and the algorithm converges. Besides, for off ooflcoolcy actor critic al algorithms in the continuous environment, the policy gradient VoT(mo) is changed to
(oo( ED Va Q (Te,a o (s)) =o(s),t-6)) VOTTOSs +x) -4)
(5)
where (Tr,a, st) sampled from D. The full algorithm is summarized in Algorithm | As a straight- forward implementation, test it on the continuous PI-DRMDP tasks. As shown in Figure ((a) our prototype algorithm already outperforms the original counterparts (i.e., SAC) on many tasks.
approximate Q" (Tt,s+1) with a GRU network (Cho al. 2014) and
3.2 THE HC-DECOMPOSITION FRAMEWORK
One challenge raised by the Q-function is that it takes a relatively long sequence of states and actions as input. Directly approximating the Q-function via complex neural networks would suffer from lower learning speed (e.g., recurrent network may suffer from vanishing or exploding gradients Goodffllow et al. 2016)) and computational inefficiency. Furthermore, the inaccurate estimation of
Q" (Tr,+4)) will result in inaccurate gradients in Eq. (5) which degrades the learning performance.
To improve the practical performance of our algorithm for high dimensional tasks, we propose the HC- deCompoomooiiionn framework (abbreviation of History-Current) that decouples the approximation task for the current step from the historical trajectory. More specifically, we introduce He and Co functions and require that
@ Ho((east) + Co(se,
Here, we use Co(st, 0z) to approximate the part of the contribu- tion to 2₂ made by the current step, and use H (T(T,,)) to approx- imate the rest part that is due to the historical trajectory signal interval. The key motivation is that, thanks to the Markov transition dynamics, the current step (st, at) has more influence than the past steps the value of the future trajectories under the given policy æ. Therefore, in Eq. (6). we use C to highlight this part of the influence. In this way, believe the architecture is easier to optimize, especially for Cs whose input is single state-action pair.
the
Moreover, we also find that the policy gradient will only de- pend on Colst, az). Indeed, we calculate that the policy gradient V HH (T²) equals
HelDhedaadd M4ve Hoppord
Policy gradient vari- ance averaged over the training process. All bars show the mean and one standard deviation of 4 seeds.
Figure 1:
ED Va, Coloe, ar) ( (o(er))-1)) V - 42)
(7)
Comparing Eq. (7) with Eq. (5). we note that the gradient on the policy under HCC-dcoomooittion will not be effected by Te.rt- Thus, for a mini-batch update, our policy gradient has less variance and the training becomes more efficient. In Figure [ we visualize and compare the scale of the gradient variance of our HC-decomposition framework and the straightforward recurrent network approximation of the Q function, w.r.t. the same policy and the same batch of samples. Clearly, the result supports our claim that HC-decomposition results in less gradient variance.
Finally, to learn the H& and Co functions, minimize the following objective function
CHC [E + (HH (T,,41) Co(se41, d(y1)) (Ho(Tr.) + Colsi, a)))) + AL (Ho).
5

---

Under review as a conference paper at ICLR 2022
+00
53he54 7atum
2230
Painise
0-HC
Gii sion
GMM Auemeco
02/00 1005
(a) Performance on High- DigghnDDmnnninnall Tasks
(b) Ablation on Regulation
Figure 2: (a): Performance of different implementations of HC-decomposition framework (Q-HO), Q-RNN and vanilla SAC. The task is the continuous sum-form PI-DRMDP task and is uniform distribution between 15 and 20, The results show the mean and standard deviation of 7 seeds each. (b) Ablation the Lee-- Each dashed line is the no-regularization version of the corresponding Q-HC of the same color.
where the first term is the TD error Eq. and the second term is a regularizer on Hg. We use the regularization to stabilize the optimization process and prevent He from taking away too much information of the credit on the choice of az In Section 4. we will compare several simple choices of H& and Legg- The search for other designs of He and the regularization term in various settings is left as future work.
4 EXPERIMENT
In this section, we first test and illustrate our algorithmic framework and HC-decoopositionn on high- dimensional PI-DRMDP tasks validate our claims in previous sections. Then, we compare our algorithm with several previous baselines on sum-form delayed reward tasks. Our algorithm turns out to the SOTA algorithm which most sample-efficiet and stable. Finally, we demonstrate our algorithm via an illustrative example.
4.1 DESIGN EVALUATION
We implement the following architectures of Hş in our experiment. Our algorithm is based on SAC Haarnoja al. 2018a).
Q-HC-RNN. (T(Ta)) is approximated with a GRU network.
Q-HC-Pairwise-K. (T.,)) is the sum of K+1 networks fcb.k=u,1,...K for different pairwise terms follows K = 1, are included in the experiment.
(T(Te))) = Σ
Σ
( o Ty41)++411)
kE(O:K +1 (E(
Q-HC-Singleton. (T is the sum of single step terms.
(T( = Σ bo(T)s41).
jE(t,d]
In terms of the representation power of these structures, (-RNN) is larger than (-Pairwise) larger than (-Singleton). With a small representation power, critic's learning will suffer from large projection enror. In terms of optimization, (-Singleton) is easier than (-Pairwise) and easier than (-RNN). As discussed in Section 3.2 non-optimized critic will result in inaccurate and unstable policy gradients. The practical design of He trade-off' between the efficiency of optimization and the scale of projection error. For the regularizer in Eq. (8). we choose the following for all implementations.
(Hg) = ED ((T))))-(Tr))}]]
(9)
Input for Oe is thus single state-action pair.

---

Under review as a conference paper at ICLR 2022
where T; is sampled from the D. As discussed in Section 3.2 the history part (T(Taa)) should only be used to infer the credit of Th within the signal interval T,. However, without the regularization, the approximated Ha may deprive too much information from 2. than we have expected. Thus, in a direct manner, we regularize Ho(T) to the same value of r(T:).
In Figure? 2. compare these algorithms sum-form PI-DRMDP continuous control tasks based on OpenAl Gym. Rewards are given once every n steps which is uniformly distributed from 15 to 20. The reward the sum of the standard per-step reward in these tasks. Our method is compared with vanilla SAC and Q-RNN whose º" is approximated by a GRU network. The results verify our claims made in Section 3 and the necessity of the design of our method.
1. Algorithms under the algorithmic framework (i.e., with prefix Q) outperform vanilla SAC. Our framework approximates @" while vanilla SAC cannot handle non-Markovian rewards.
2. 2 approximated with HC-deconposition architecture (i.e., with prefix Q-HC) is more sample- efficient and more stable than Q-RNN. Indeed, the HC architecture results in easier optimiza- tion in critic learning.
3. Figure 2() shows the importance of regularization. especially when Hg has complex form (i.e., Q-HC- RNN) and thus is more likely result in ill-optimized C-part.
More Experiments. In Appendix C.I we show that the empirical results are consistent in a variety of PI-DRMDP tasks and under different implementations. First, we test in sum-form tasks with different interval length distributions (g,). As shown in Table 2 our Q-HC methods are scalable to sum-form tasks with a signal interval length of 60 envirommental steps, which is quite a long period in the Gym benchmark, and perform well in various random length tasks. Then, in non-sum-form tasks with Max and Square reward functions, we find that Q-HCss still outperform Q-RNN and the vanilla SAC consistently in all environments (Figure 5p This suggests that the advantage of HC- decomposition also holds in other PI reward function tasks. Moreover, in Figure 6 we also test TD3-based
and O-HC-Pairwiser 1. Comparing to TD3-based Q-RNN and vanilla TD3 (Fujimoto et al., 20188,, these two variants outperform the baselines uniformly.
To sum up. based on the empirical evidence, we conclude that our Q-HC is widely applicable in PI-DRMDPs as remedy to the unstable optimization of direct Q approximation. As Q-HC is an implementation of the general algorithm in Section[.1]] it handles the non- Markovako rewards with theoretical support. In future work, we will explore the boundary of HC-decomposition, and analyze the effect of the projection error mathematically.
4.2 COMPARATIVE EVALUATION
Here, we compare our algorithm with previous algorithms in sum-form high-dimensional delayed reward tasks. The following baselines are included in the comparison.
LIRPG (Zheng et al. 2018). utilizes intrinsic rewards to make policy gradients more efficient.
The intrinsic reward is learnt by meta-gradient from the same objective function. We use the same code provided by the paper.
RUDDER (Arjona-Medina et al. 2019). It decomposes the delayed and sparse reward to a surrogate per-step reward via regression. Additionally, utilizes on-policy correction to ensure the same optimality w.r.t the original problem. We alter the code for the locomotion tasks.
SAC-IRCR (Gangwani et al.) (020). It utilizes off-policy data to provide smoothed guidance rewards for SAC. As mentioned in the paper, the performance heavily relies on the smoothing policy. We implement a delayed reward version of IRCR in setting.
For clarity, we only include Q-HC- HHHC-Parwiie-11 and Q-HC-RNN in the comparison. As shown in Figure 3 we find that LIRPG and RUDDER perform sluggishly in all tasks, due to their on on-policy nature (i.e., based on PPO (Schulman et al. 2017)). SAC-IRCR performs well only on some easy tasks (e.g. -2)) Unfortunately, SAC-IRCH has a bad performance (e-g. Ant-v2, Walker2d- v2, Reacher-v2) on other tasks. We suspect in these tasks, the smoothing technique results in erroneous guidance reward which biases the agent. Thus, SAC-IRCR is not a safe algorithm in solv- ing delay reward tasks. In contrast, ours (as well as other implementations shown in Appendix CC.) perform well on all tasks and surpass the baselines by a large margin. Most surprisingly, our algo- rithm can achieve the near optimal performance, i.e., comparing with Oracle SAC which is trained on dense reward environment for 1M steps. Noticing that we use an environment in which rewards given only every 20 steps.
7

---

Under review as a conference paper at ICLR 2022
Reacher-22
HarCChetthh-12
Happeru2
3000
4000
Teecdtyshh
Tracstoes
360
Steeting
15-
RaManee Rop Pertommanc
stopo
URPO
RUDDER
SAC
SAC RCR
Oradee SAC
Figure 3: Comparisons of 1-ri--airwise-1, Q-HC-RNN and baselines on 5 sum-form PI-DRMDP tasks. The dashed line is the value of Oracle SAC. yn fixed 20 (Zheng et al.) 2018 Oh al., 2018). The results show the mean and the standard deviation of 7 runs. All curves are further smoothed equally for clarity. The last picture shows the relative performance w.r.t the Oracle SAC on sum-form Pl DRMDP tasks with general reward function (Appendix [B. Each data point shows the average of tasks of each algorithm. X-axis refers the overlapping steps of the reward function.
We also conduct experiments tasks with general reward functions, in which our algorithmic framework and the HCCdecomposition can be naturally extended to (please refer to Appendix BBaddixBaann and Appendix A). In the General Experiment of Figure Oracle SAC on tasks whose general reward functions have different amount overlapped steps (c = 5, 10). Clearly, Q-HC is still the SOTA algorithm for every Thus, method is applicable to environments with general reward functions. Please refer to Appendix [ for experiment details.
plot the relative average performance w.r.t
4.3 HISTORICAL INFORMATION
In addition, with a toy example, we explore what kind of information the H-component learns so that the C-component makes suitable decisions. The toy example a target-reaching task illustrated in Figure Left. The point agent is given delayed reward which roughly indicates its distance to the target area. This mimics the low frequency feedback from the environment. Noticing that the reward function is not in sum-form. Please refer to Appendix D for more details.
The learning curves are shown in Figure 4 Middle. Clearly, Q-HC-Singlcton outperforms the base- lines by large margin. For better illustration, we visualize bø(St, 0e) in Q-HC-Singleton grid in [ The pattern highlights the line from the start point to the target area (i.e., the optimal policy), suggesting that by has captured some meaningful patterns to boost training. We also observe a similar pattern for HC-Singleton without regression (Appendix D). This is an interesting discovery which shows that the //-component may also possess direct impact on the policy learning instead of simply function as an approximator.
the
RELATED WORK
Off-policy deep reinforcement learning algorithms TD3 (Fujimoto et al. 2018 and SAC (Haarnoja et al.) 20 2a) the most widely accepted actor-critic algorithms the robot locomotion benchmark (Duan et al. 2016) so far. Based on previous work (Degris et al. 2012 Silver et al. 2014), Fujimoto et al. 2018 puts forward the clipped double Q-learnig (CDQ) technique to address overestimation in critic learning. HHarnoja et al. (2018a) also uses CDQ technique but instead optimizes the maximum entropy objective. These two methods lead more robust policy.
Off-Policy RL:
8

---

Under review as a conference paper at ICLR 2022
agart
Figure 4: Left: 100 x 100 Point-Reach task with additional positional reward (indicated by area color). Reward is given every 20 steps. Middle: Learning curves of Q-HC-Singleton and several baselines. Dashed line represents Q-HC-Singleton without regularization. Y-axis shows the number of steps needed for the point agent to reach the target area (cut after 500 steps). All curves represent the mean of 10 seeds and are smoothed equally for clarity. Right: Heatmap visualization be in Q-HC-Singleton.
In our setting, we observe that SAC-based algorithms slightly outperforms TD3-based algorithms suggesting the benefit of maximum entropy in delayed reward tasks.
Delayed or Episodic Reward RL: Developing RL algorithms for delayed reward or episodic reward (at the end of the trajectory) has become popular research area recently. Some theoretical analysis have been conducted on delayed rewards in MAB and MDP Zhou et al. (2018) 2019); Héliou et al.) (2020) These tasks are known be difficult for long-horizon credit assignment (Sutton 1984). To address this issue, Zheng et al. (2188) proposes to use intrinsic reward to boost the efficiency of policy gradients. The intrinsic reward learnt via meta-learning (Finn al. 2020). Gangwani al. 2019) and Guo et al.] (2018) use a discriminator to provide guidance reward for the policy. The discriminator trained jointly with the policy with binary classification loss for self-imitating. In RUDDER (Arjona-Medina et al. 2019), it utilizes recurrent network to predict a surrogate per-step reward for guidance. ensure the same optimality, the guidance then corrected with ground truth reward. Liu et al. (2019) extends the design and utilizes Transformer (Vaswani al. 2017) network for better credit assignment on episodic reward tasks. Recently, Klissarov & Precup (0200) proposes use GCN (Kipf & Welling 2016) network to learn potential function for reward shaping (Ng jet al. 1999). Noticing that all these algorithms are based on PPO (Schulman et al. 2017) and thus are on-policy algorithms while ours is off-policy one.
Most recently, Gangwani et al. (2020) proposes to augment off-policy algorithms with trajectory- space smoothed reward in episodic reward setting. The design the problem. However, as mentioned by the paper itself, this technique lacks theoretical guarantee and heavily relies the choice of the smoothing policy. As shown Section 4.2) in many cases, this method becomes extremely spurious. Our algorithm is derived from theoretical perspective and performs well on all tasks.
out to be effective in solving
CONCLUSION
In this paper, model the sequential decision problem with delayed rewards as Past-Invariant Delayed Reward MDPs. As previous off-policy RL algorithms suffer from multiple problems in PI- DRMDP, we put forward novel and general algorithmic framework to solve the PI-DRMDP prob- lems that has theoretical guarantees in the tabular case. The framework relies on a novelly defined Q-value. However, in high dimensional tasks, it is hard approximate the Q-value directly. To ad- dress this issue, we propose to use the HC-approximation framework for stable and efficient training in practice. the experiment, we compare different implementations of the HC framework. They all perform well and robustly in continuous control PI-DRMDP locomotion tasks based OpenAI Gym. Besides, our method outperforms previous baselines on delayed reward tasks remarkably, suggesting that our algorithm is SOTA algorithm these tasks far.
In terms of future work, two research directions are worth exploring. One is to develop our algorithm and the HC-approximation scheme to various real world settings mentioned in Section I possibly with offline data (Levine et al.) 2020). The other direction is to design efficient and advanced algo- rithms with theoretical guarantees for the general DRMDP tasks.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Mostafa Al-Emran. Hicrarchical reinforcement learning: a survey. International journal of comput- ing and digital systems, 4(02), 2015.
Jose A. Mjjona-Medina, 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, pp. 13566-13577. Curran Associates, Inc., 2019.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), ). pp. 1724-1734, Doha, Qatar, October 2014. Associ- ation for Computational Linguisties. doi: 10.3115/v I/D4--119.
Thomas Degris, Martha White, and Richard Sutton, Off-policy actor-critic. In Proceedings of the 29th International Coference on International Conference Machine Learning, pp. 179-186, 2012.
Esther Derman, Gal Dalal, and Shie Mannor. Acting in delayed environments with non-stationary markov policies. arXiv preprint arXiv:2101. 2021.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https: 2017.
7/github ccw./pppnaa///baeeenneeee
Yan Duan, Chen, Rein Houthooft, John Schulman, and Pieter Abbeal. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning. 2016.
Chelsea Finn, Pieter Abbeal, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In 34th Conference Neural Information Processing Systems, 2020.
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-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 34th Conference Neural Information Processing Systems, 2020.
Yaobang Gong, Mohamed Abdel-Aty, Qing Cai, and Md Sharikur Rahman. Decentralized network level adaptive signal control by multi-agent deep reinforcement learning. Transportation Research Interdisciplinary Perspectives. 1:100020, 2019.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Brockman Greg, Cheung Vicki, Pettersson Ludwig, Schneider Jonas, Schulman John, Tang Jie, and Zaremba Wojciech. Openai gym, 2016.
Yijie Guo, Junhyuk Oh, Satinder Singh, and Honglak Lee. Generative adversarial self-imitation learning, arXiv preprint arXiv:1812.00952 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 1861-1870, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 201 8a. PMLR.
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: ae 2018b.
10

---

Under review as a conference paper at ICLR 2022
D. Hein, S. Depeweg, M. Tokic, S. Udluft, A. Hentschel, T. A. Runkler, and V. Sterzing. A bench- mark environment motivated by industrial control problems. In 2017 JEEE Symposium Series on Computational Intelligence (SSCI), pp. 1-8, 2017. doi: 10.1 00.1099SSCL2201.82889922
Amélie Héliou, Panayotis Mertikopoulos, and Zhengyuan Zhou. Gradient- online learning in continuous games with delayed rewards. In International Conference Machine Learning, pp- 4172-4181. PMLR, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Computer Science, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. CoRR, abs/1609, 00900,7 2016.
Martin Klissarov and Doina Precup. Reward propagation using graph convolutional networks mar- tin. In 34th Conference on Neural Information Processing Systems, 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
Kaixiang Lin, Renyu Zhao, Zhe Xu, and Jiayu Zhou. Efficient large-scale fleet management via multi-agent deep reinforcement learning. In the 24th ACM SIGKDD International Conference, 2018.
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 2019.
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, 518 518(7540):529, 2015.
A. Ng. D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference on Machine Learning, 1999.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3878-3887, Stock- holmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Mareus Olivecrona, Thomas Blaschke, Ola Engkvist, and Hongming Chen. Molecular de-novo design through deep reinforcement learning. Journal of cheminformaties, 9(1::1114, 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Proceedings of the 31 International Conference International Conference on Machine Learning- Volume 32, pp. 1-387, 2014.
David Silver, Julian Schrittwieser, Karen Simonyan, Aj Antonoglou, Ioannis abd Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lill- icrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550, 2017.
Richard S Sutton. Between mdps and semi-mdps: Learning, planning, and representing knowledge at multiple temporal scales. 1998.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Stuart Sutton. Temporal credit assignment in reinforcement learning. PhD thesis, Depart- ment of Computer Science, University of Massachusetts at Amherst, 1984.

---

Under review as a conference paper at ICLR 2022
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, N, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In 31th Conference on Neural Information Processing Systems, pp. 5998-6008, 2017.
Thomas Walsh, Ali Nouri, Lihong Li, and Michael Littman. Leamingg and planning in envi- ronments with delayed feedback. Autonomous Agents and Mulli-Agent Systems, 18(1):83-105, 2009.
Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, and Jieping Ye. Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In the 24th ACM SIGKDD International Conference, 2018.
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. Curran Associates, Inc., 2018.
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? In International Conference on Machine Learning, pp. 9979. PMLR, 2018.
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32:5197-5208, 2019.
12

---

end for Under review as a conference paper at ICLR 2022
A ALGORITHM
We summarize algorithm for PI-DRMDP with General Reward Function follows.
Algorithm Algorithm with General Reward Function
1: Choose 2 structure: Q-RNN, Q-HC-Pairwise-K, e.t.c
2: Initialize Te. 2g and target networks, D <
3: for each env step do
4: 0e ~ (-)s,,,, -4)
5: Take and get S1+1. Rs
6: Add (s,, ce. R2, St+1) D
7:
for each gradient step do
8:
Sample batch of (Tr,- R4 8141) from D
9:
Update 2s via minimizing Eq. ( (with Tr, Tr,-::) for Q-HC Eq. I1] for Q-RNN
10: Update Ty via Eq. 7 for Q-HC or Eq. (12) for Q-RNN
11: Update the target networks
12: end for
B DISCUSSIONS AND FORMAL PROOFS
In this part, we provide the proofs for the statements in the main paper. In addition, we also add detailed discussions the issues mentioned above. To begin with, we restate the definitions with general reward functions.
Definition 3 (DRMDP with General Reward Function, DRMDP-c). A DRMDP-C Mc
(S, A, P. Yn.re.?) 7) is described by the following parameters.
1. The state and action spaces are S and A respectively.
[ss a) for each (s,a) S A; the initial state distribution 2. The Markov transition function is p(s'|s,
is p(0o).
3. The signal interval length is distributed according to qu (:), ie., for the i-th signal interval, its length n, is independently drawn from qn(.).
4. The general reward function To defines the expected reward generated for each signal inter- val with overlap of maximal steps with previous signal intervals; suppose Thating (s, a)t.,n, = ((st, de).... ($14n-1, dc+n,-1)) is the state acatinaction sequence during the i-th sig- nal interval of length n,, then the expected reward for this interval is r re(Tr-aittn.)
5. The reward discount factor is ry.
The PI-DRMDP also extended naturally as follows.
Definition 4 (PI-DRMDP with General Reward Function, P1-DRMDP-c). A Past-Invarians DRMDP-c DRMDP-c Me = (S, A.P, p. Te,Te. 7) whose reward function re satisfies the fol- lowing Past-Invarian (PI) condition: for any two trajectory segments and of the same length (no less than c), and for any two equal-length trajectory segments 7i and T such that the concate- nated trajectories Ti are feasible under the transition dynamics p for all a, b E (1,2), it holds that
r(m o T|) r(T1 o =
r(12 r(T2 Tg)-
Remark 1. Definition Iaciioonnanee and Definition the special case (c of Definition 3 Definition respectively.
Clearly, we have the following Fact.
Fact 3. Vél < DRMDP Me is also DRMDP M. and PI-DRMDP M is also PI-DRMDP M
'If G, Tt-co refers
token paddings which indicates the heginning of the trajectory.
13

---

Under review as a conference paper at ICLR 2022
Besides, under the general reward function, we extend the Q definition.
@a (T = (F,n)~
((Te,-cct_))) -cd, Th, Tet
(10)
Correspondingly, 2" (Tr, (ft,-ca+1) is optimized via L == ED RR + 1 1Qp(T)
@ (6(
(11)
where -t,-0 = -0t+1 o ($1+1, 4(+1) (so that j = i) if not the last step of Tú and Tty-cu+2 Pt41--iti1 o (Stz11> ( (so that i + 1) otherwise.
The general policy update is also extended to
VOTolont -6)) 6s)
VoJ(me)) = ED Va. e" (Ti-eet (sp, a))
(12)
Without specification, the following proofs hold for Ve.
B. PROOF OF FACT
Fact (Fact 1 with General Reward Function). For any distribution with non-zero measure for any ctt-c Q (T,,,-ott+)) is the unique fixed point of the MSE problem in Eq. (4) More specifically, when fixing 2g the corresponding 2 the solution of the MSE problem is still Q
Proof. Though we state the fact for PI-DRMDP-c, we will prove it for general π E 1ll in DRMDP- setting, For brevity, replace & with t in the proof. By definition in Eq. (T)) have @ (Ti, = gn (n4 # t ts/m 2 t -ttt,) t.)
Σ p(sel az ) (T; o 2t) (Tr,-eat a (st, (st, ai)) RLal
+ ga(ni = 1. lilie 2(-4))
((Tr)-at) + Σ a(st/sc-11 ar- (0 8t) (T (on,
$t.0t
(13)
Clearly, Q² (T, is the solution of the following MSE problem. Noticing that we assume Qs has tabular expression over Tr.-c:t..
min Σ pD(Te,-att Re-1, (t) o st) (Rt-1 + 7Q" (Tr t Re-1.
o (st, a()) - 2s (T.,
Here, Tiy-oit is defined similarly in the main text and PD refers to the probability of the fragment of trajectory is sampled from the buffer D. We denote the objective function as LT. As Es in Eq. II is the sum of all CT)T (T,, is fixed point of the MSE problem.
The uniqueness proved similar to the standard MDPs setting. For any 2e, we denote the optimal solution of Eq. 44 as Qs (T.--a)) Since we assume tabular expression and non-zero probability of any (=( Then, VTe,-e:t: we have
Q (s( Q" (TT,-ee)) I 2gn # #t -t-ttlng ti/m: 2 - t2) Σ ((
0.8))
(s(T,-ott11) 2a (Tr,-00++) (mg = t- --4// 2 1.)
Σ (1 0t
(T (st, (()) 2 (Tr-ait (st,
7 Q, 2T 11
14

---

Under review as a conference paper at ICLR 2022
Last term denotes the infinite norm of the vector of residual value between Q and 2s- Each entry corresponds to some -t, feasible in the dynamic. Consequently, by the concenttaaiio property, 2 = 2g after the iteration (i.e., 2s is a fixed point), then 2s 2". This completes the proof of uniqueness.
Remark 2. holds as the special case of Fact when O.
B.2 PROOF OF FACT 2
Fact 5 (Fact) with General Reward Function). For any Tr, Tr,-e:t T and St, a, de which both The -ot 8, and To cet are feasible under the transition dynamics, Vx TT we have that
2" (Tr, -e ae)) 2" (Tr-ee (sts (s)) = (Ti (e)) 2
2" (Tu-cas o (8t, d))
Proof. Since T --1s,tttt f.) E 1I. for any St, the distribution of the remaining trajectories p" (TeT, nuT (e, ae. (r;ti) is irrelevant with Tr,-est Thus, have
8
(T( o (t))
Σ
p" (Troce Tece 01,,
Σ
7 b+ -/----11
To:o0 Ni:00
- gn =4+1 - ti/m 2t Σ
p (Teises 16,1181,
611
Th:444
r(T r(Tu-et41)) +9 Σ
1 (8t at.4:))
04441
az an(n = t+t1 - -tilns - (te (t (Tr
+ K(8,, 4))
The last term denotes the residual part which irrelevant with Tı. Besides, under the PI condition, the order of r(7t,-ctt+1) is invariant over Tt,-at- As result, the order of Q" (Teeect o (8), among a is also invariant of Tt,-oit- This completes the proof.
Remark 3. Fact 2 holds then special case of Fact 5 when 0.
B.3 PROOF OF PROPOSITION
Proposition 2 (Proposition with General Reward Function). For any policy Ti E H. the policy iteration w.r.t. T (Eq. 10 produces policy T8+1 E 1I, such that VTr,-ett-1 it holds that
T+++1 (Te, (Tu-ca++1) 2 T (Tt--o:41);
which implies that ((T441) 2 [(TK)-
Proof. Under Fact 5 the new policy iteration defined formally as following
(a+1(a fx) = arg max Q (Tt-oat (st, az))
where Te-est is any trajectory segments feasible for s, under the dynamics. If there are multiple maximums, assign arbitrary probability among these a,s. Following Eq. (3). have
15

---

Under review as a conference paper at ICLR 2022
(P = qn(ni # t- 4/m4 2 t 14)))
Σ Dis:ls--1144--aaaallls tt) (T o (st, ai)) tr,0r
qn (n: t t: 21-22-t8 t4)
r(Th-c:)) + Σ p(si st-1, (0) (Te-al (st,
51,01
$ an (1, t- 11//1 2 6-b,) bz)
7 1,5)55--1,0-11600 (ar 1z) ((r))*((r,-a))) (Tr (s),
Seidc
On (n, = - t4 2 2t-)
r(Tr--ct) +7 E p(s s1-1, a 0) (Te-ct (st, ail) (14)
$1,4,
Then, we can iteratively extend each T term in Eq. [4 and get VTC-ca
Q (Tt, S " (Tt,-ca)
Noticing that the inequality strict if any step of the inequality in the iterations is striet. Further- more, by definition, (TT) = eo, p( (so: Q) do we have
J(Tx)) S Σ ((50)=++1(a0)) 80 0) (So, ap)
$0.90
< Σ p(su)=++1(a0ls)) 0) an)
80.00
< I (TT+1)
This completes the proof.
Remark Proposition holds as the special case of Proposition when
B.4 DISCUSSION OF OPTIMAL POLICIES
To begin with, we consider the general DRMDP-c. Similarly, we denote II,cc -e 0s:) as the extension of II, (c 0). Then, we prove the following Fact.
Fact For any DRMDP-c, there exists an optimal policy x" E TT However, there exists some DRMDP-0 (so DRMDP-c Vc) such that all of its optimal policies x¹ o II,
In general, any policy belongs to the class Ill = {o Toa o 8t, noa)). Namely, the agent's policy only base on all the information it has experienced till step t. Besides, in DRMDP-c, the expected discounted cumulative reward is
J(m) - (T,
T.R
where p² (T, begin with, we first prove the following Lemma.
n)) denotes the probability that trajectory (T, is generated under policy ा E Han- To
Lemma 1. For any policy
Han which is the optimal, i.e, maximize J(T), consider two segments of trajectories (To.a, no.ra) and (5ore mo which satisfies that Th -et-
Th -ot and
tb > ta. Besides, we also consider 2 th,t== t-t + and The = To. o oT n = ni otgpe
*Here, omit specifying the e-step padding.
16

---

Under review as a conference paper at ICLR 2022
and state ? feasible in the dynamic, we switch the policy πT x' wet these two trajectories as following
x (-1oia o 8t, mox)) = a (.. Toa Tp o Se, Doaz nzbg). Then, x' E Tall and [(r') = [(T)..
Proof. Obviously, x' well-defined and x' Hall the transition Markovian. Noticing that J(T') Σ9d (T,
Σ
O ((T)) +p" 1 (Toee mb:e))
(T,n)e( Dight Oreh (((m)
demoted by J (+t
0 0100)
Σ
p² (T, no.eh )((,
(5,))(( me ((.m))
= J=
+ p²
Σ
(Fin)i(T one an o (C(.m))
DC
p² (r,mlTonnn mgx0)
Σ
-0 (TTes
i(th)-1
Jd (Ti mbaa) ) + p= (rhernnre
Σ
- - (F(t
p² (For moxe)) 11 (192
We denote (Toit; Ro:t) C (T, if the former the trajectory prefix of the latter. QT' is defined in Eq. ①3 except that n' E Man in this case. By the definition of x and the condition that क is optimal,
we have QT' (T)) (ea)) = QT (Tp-att) = Q (T) -aa)) and J (To ngre) = J (To. n no
Thus, we have
)(1-11
J(z)= = J (Tore m + p² (To m
Σ
g/41 1 1:1--r(z2 (eetr--(Tecct-)))
(Tises mbau) ( (T (Toe-ca))
J (T n( ) + p² (To
Σ (Trn)((h ond Bee with C(T.n))
1" (T (l mixe)
y 1/41 1/111 (44e--((Te-cttt))
j=1
= -(T).
We refer it as a policy switch on π want (Ti no) and (To ngza)) to x'. Then, we prove Fact as follows.
Proof of Fact 6 For simplicity, we denote ITC T.e C Tal as the policy space that if ग E T and Vta, to < t then "r00=nnn0 (Th mbge) which T - = Th - T-- Sts, ng,r)) (-IT 8,o, nh.)) for all feasible. Clearly, 1I Hnn and I1 = Ir.. Then, starting from some optimal policy mo 170 7 we utilize the policy switch operation shift it into II
17

---

Under review as a conference paper at ICLR 2022
Suppose that xe-1 E I consider the following two steps of operations.
1. Step 1. V(Tor, no.:) that 3(Tors "içar) which t' I and Tt,-est -6--0a (randomly choose one multiple segments exist), we conduct a policy switch on Te w.n. (Toit, no:r) and (Tows, n.ve). We denote the policy after all these policy switches T/-1-
2. Step 2. We denote (ft = {(T0:2, no.a) = tt, and A( no (o < which T6:-::1' = - For each Sa.-1 (Fe.-or), we randomly choose some (To m(a)) E (Fr,-cit) and conduct policy switch on 7/-1 w.r. all (T, E (ft.-e) and (To: m0:.). Finally, we get :T.
Since TT-1 E _
straightforward to check that n. E Ief Besides, as all operations are policy switches, πi is optimal if πT-1 is optimal. Consequently, by induction from the optimal policy no. we can prove that 3m E II, which is optimal.
For the second statement, consider the following DRMDP-0.
Ao
ag
bo: b
B
C
A1
a
whose = 2. 40: denote two actions from Ao. A1 to B respectively and bo, b1 are two actions from C. The reward defined as r(a,, bj) = i. v(i,j) {0, 1}. The initial state distribution is (o) p(1 = 0.5. Clearly, for any optimal policy, the agent has to query for its action from the initial state to B before deciding the action from to This illustrates that " may not be in llg.
Consequently, learning optimal policies is relatively hard in DRMDP due to the large policy class search. In our work PI-DRMDP, we only focus the optimization in [,. However, in some bizarre cases, the optimal policy π² & 1l.. For example, consider the following PI-DRMDP-0 where if fixed 2.
Ap
C₁
Q10
b+1
d0.1
b
A
C-
T
The initial state is uniformly chosen from (Ab, Ar} and C+, T are terminal states. The reward function for the first interval is r(as, by) = i x j (Past-Invariant) and r(T) = 5. The optimal policy B should be (-IAAbtt, B) 641/-1 which not in ll..
We have not covered the potential non-optimal issue in this work and leave developing general algorithms for acquiring optimal policy for any PI-DRMDP-c even DRMDP-cat as future work. As mentioned above, most real world reward functions still satisfy that the optimal policy belongs to I1. This makes our discussion in II, still practically meaningful. Additionally, we put forward sub-class of PI-DRMDP-c which guarantees that there exists some optimal policy T² E II,
Definition (Strong P1-DRMDP-e). A Strong Past- Invariava DRMDP-c a PI-DRMDP-C whose reward r satisfies stronger condition than the Past-Invariant (PI) condition:
y trajectory segments Ti and 72 of the same length (no less than c), and for any two equal-lenger trajectory segments 7i and The such that the concatenated trajectories Ta Th are feasible under the transition dynamics p for all a, {1, 2}, holds that
r(n + r(n 7/)) = - r(T2 72).
18

---

Under review as a conference paper at ICLR 2022
Namely, the discrepancies are invariant of the past history 71,2 in addition to only the order. A straightforward example is the weighted linear sum of per-step rewards
H+n-1
r(t--ct+))=
Σ (.rr(s;;aa)) 0 W1-
The weight mimics the scenario that the per-step reward for the i-t step in the reward interval will be lost with some probability Wi-t- Furthermore, Strong PI-DRMDP- satisfies
Fact 7. For any Strong PI-DRMDP-C, there exists some optimal policy x² E (T
Remark 5. Table 7 summarizes the case when
B.5 DISCUSSION OFF-POLICY BIAS
This following example illustrates the off- off-pooiicy bias concretely. We consider the case for sum- form PI-DRMDP-0.
The signal interval length is fixed as n + 1 and any trajectory ends after one interval. The reward function is sum-form over r(s, a). When learning the critic (tabular expression) via Eq. (1) the Q-values at the last step are
Qo(en)an)
D an (T())
Σ (Teenlsm:
70
n-
Σ
0 (Toen Sn, an)
Σ E((Fect))
+r(sn, an)
(15)
Tomn
Q (sn:
In Eq. 15 0² an) denotes the probability distribution of Tomn collected under the policy sequence 3 conditioning on that Twm++1 = (Sn: an). Besides, we denote p (Tu:n|s,) as the dis- tribution under policy 3& conditioning sn the last step. Obviously, - is independent of last step's action on as π E II, By Bayes rule, we have the following relation
K K== po (Toen (a,
1 (TomlS5n an)
(16)
ΣK
(anla)))
In other word, (-Isn, an) is a weighted sum of to (-1sx)}. }. The weights are different between a, since the behavior policies (3c) are different. Consequently, ( an) will also vary between a, and it is hard to be quantified in practice. Unfortunately. we may want Qo(sn, a,) x r(8n. an) for unbiased credit assignment the actions at the last step. Thus, updating the policy with approximated Q0(5n (x) will suffer from the off-policy bias term Q8 (8n: (n))
B.6 DISCUSSION OF FIXED POINT BIAS
Even with on- on-policy samples in D, critic learning via Eq. TT) can still erroneous. We formally state the observation via toy sum-form PI-DRMDP-0.
C
Co
40
A
D
Do
B
'Without loss of generality, the discussion is simplified by assuming 8n will only appear at the end of reward interval.
19

---

Under review as a conference paper at ICLR 2022
where for state B, C, D, there is only action. The agent only needs to decide among du. d1 at state A. n fixed as 2 and the initial state distribution (u( = Pb( = 0.5. The reward has
sum-form over the following per-step reward
r(C,c) = r(D,d) =0 r(A, 00) - 0.01, r(A. =1
r(B, b) =-1
Fact 8. For the above PI-DRMDP-O and any initialization of policy, value evaluation (Qo(se, ae) in tabular form) via Eq. (7) with on-policy data and policy iteration w.r. Qø(st, at) will converge sub-optimal policy with [(] 0.449%.. In contrast, our algorithm can achieve the optimal policy with I (x)==0)
Proof. For any policy म, we denote = T(a Then, if we minimize Eq. T with on-policy samples, will have co( 0.01, (A(A, 0n) 0.01y. Besides, as initial state distribution
are uniform, we have
1 (0- Qo(A,a)) Qo(D,d)
1 -
Since (s a1) < Qo(A, an) for any p. policy iteration will converges sub-optimal policy that (ap) A) = 1.The sub-optimal policy has (TT) = -0.495% Noticing that this holds even if the initial policy already the optimal.
For our algorithm, we have
((o444))=0(((4,00) oo. D,d)= =y
For any 7 > and any p. a single policy iteration will have the optimal policy with but the optimal has J(x') O.
B.7 DISCUSSION OF DRMDP DEFINITION
In this section, we compare DRMDPs with other related definitions about MDP delays. To be specific, we provide brief discussions the differences between DRMDP (delayed reward MDP) with Delay MDP and Semi-MDP.
Semi-MDP and Option Framework: In Semi-MDP, actions are allowed to execute variable length of time. In DRMDP, actions are executed and re-planned at each time step while rewards are delayed for random length and non-Marvian. Simply solving DRMDPs (or P1-DRMDPs) Semi-MDPs will result in serious sub-optimal problems.
The middle ground between Semi-MDP and MDP is the Option Framework (Sutton 1998), in which options are temporally extended action sequences and cen be learned, i.e., option policy, initial state set, termination state Contrarily, in DRMDP, the length of the signal interval (comparing the length of the option execution time) is random and is determined by the environment. Furthermore, in option framework, rewards are still provided once very step (Markovian).
Option framework is often used on problems with hierarchical structures (Al-Emran 2015), in which the whole policy is composed of low-level option policy over actions and high-level control policy over options. However, DRMDPs are formulated for general sequential decision making problems.
Delay MDPs (Walsh et al., 2009 Derman et al., 2021) are used to characterize ob- servation delay and action delay. For example, the observation inputs to the controller (e.g., computer) is the observation of the remote agent (e-g., a drone) several milliseconds ago and the action executed at the remote agent is the output of the control policy several steps ahead. We have to emphasize that, in delay MDP, the rewards are still defined as per-step rewards and are cou- pled with the corresponding state-action pair, i..., when the delay is constant m, the transition (St, de, Tt, S141)a observed at the remote agent, is also the transition the controller received at step + m, i... (5++ 0r Ft+m $14m+1)
Delay MDP:
In DRMDP, there is no observation-delay or action-delay and there is no per-step rewards coupled with each state-action pair.
20

---

Under review as a conference paper at ICLR 2022
C ADDITIONAL RESULTS
C.I DESIGN EVALUATION
Here, show more experiments omitted in Section 4.1 To begin with, compare different HC-decomposition algorithms (Q-HC) with Q-RNN and vanilla SAC on several sum-form PI- DRMDP tasks with different signal interval length distributions (g,). The results consistent with our discussions in Section 4.1, despite of the lengths and the distributions.
Table 2: Relative average performance in tasks with different signal interval length distribution Zr over 4 environments: Hopper-v2, HalfCheetah-v2, Walker2d-v2, Ant-v2. 8(r) refers to a fixed interval length æ and U (a, b) refers uniform distribution in range [a, b]. All results show the mean of 6-7 seeds and N.A. refers to no result due to limited computation resources.
On
SAC
Q-RNN
Q-HC-
Q-HC-
Q-HC-
Q-HC-RNN
Singleton
Pairwise-1
Pairwise-3
8(10)
0.62
0.61
0.91
0.89
0.92
0.98
U110, 20)
0.48
0.52
0.95
0.84
0.95
0.96
U(15,20) 20)
0.48
0.61
0.89
0.99
0.95
0.93
8(20)
0.51
0.53
0,91
0.93
0.98
0.99
8(40)
0.30
0.38
0,90
0.94
0,85
0.87
8(60)
0.17
N.A.
0.87
0.81
0.88
N.A.
Then, we test the HC-decomposition on non sum-form PI-DRMDP taks based on OpenAl Gym. Two non sum-form tasks are included: Max and Square. For Max,
r(Teatn) 10 x max {r(ss,a;)
sE[t:t+n]
Here, r(s;, az) is the standard per-step reward each task. For Square, we denote Tavg (Tretn) E [e(eeei]] 788, 0z) and the reward is defined as follows.
Tavg (Tet4))
Tavg (Tog(Te))))))) ) <
(Tree=n) = x
sign(r (ereeee(Teeee (Tue4a)) x rang (Tra4n) |aag (Trst)))))) ) 2
Noticing that these two tasks are still PI-DRMDP. The results are shown in Figure Clearly, Q-HC algorithms outperform Q-RNN and vanilla SAC on all tasks.
Met McCeieet
33
Kagp
KITWOITT
200
200
Figure 5: Experiments of non sum-form PI-DRMDP tasks. The first line shows the result of Max form and the second line shows the result Square form. The learning curves are mean and one standard deviation of 6-7 seeds.
Moreover, also implement TD3-based Q-HC-Singleton, Q-HC-Pairwised and compare them with the vanilla TD3 and TD3-based Q-RNN. The results still match our analysís of HC- decomposition in Section 3.2 However, find that SAC-based variants consistently outperform
21

---

Under review as a conference paper at ICLR 2022
TD3-based variants. We think that the entropy maximization regularization is useful in the delayed reward environment, which prevents the policy getting trapped in local maximal points.
Poppers2
1ellCreetat-22
Ber2642
fetiv2
1500
155
0.0
68
20
100400 Smapics
Figure 6: Learning curves of TD3-based Q-HC-Singleton, Q Q-HC- HHC-Pairwis--, Q-RNN and vanilla TD3. All curves show the mean and one standard deviation of seeds. The result is consistent with that of SAC-based methods.
C.2 ABLATION STUDY
In Figure we show the ablation study on the regulation term Leg on all tasks. We observe that in HallCheetah-v2 and Ant-v2, the regulation plays important role for the final performance while the regulation less necessary for the others. Besides, for Q-HC algorithms with complex H-component architectures (i.e., Q-HC-RNN, Q-HC-Pairwise-3), the regulation is necessary while for simple structure like Singletnn,,,n, regulation less helpful. We suspect that the simple structure itself imposes implicit regulation during the learning.
Figure 7: More ablations on Log term. The task a sum-form PI-DRMDP with n uniformly drawn from 15 to 20. Dashed lines are the no regularization version of the algorithm Q-HC with the same color. All curves show the mean and a standard deviation of 6-7 seeds.
Furthermore, we ablate the HC-decomposition Q-HC-Singleton and Q-HC-Pairwise-L. Namely, implement Q-Singleton and Q-Pairwise-1 with the similar architecture but not with HC- decomposition. For Q-Singleton, we have
Q Σ
bo(T)(41)
jE(eat-1]
and for O-Pairwise-l, we have
Q(Te =
Σ SE(NAT
+
E bo(T)S+1)
jE(Nat+]]
In Figure 8 we observe that these two ablations perform sluggishly and even worse than Q-RNN (without any decomposition). This suggests the necessity HC-decomposiiton for PI-DRMDP, i.e. the separated history part (H) and the current part (C), the transition of the environment is still Markovian. Without separation, simple decomposition fails assign the adequate credit the last step action in Te,0+11, thus results in errorneous policy update.
C.3 COMPARATIVE EVALUATION
We show detailed results of our algorithms Q-HC and previous baselines on sum-form PI- DRMDP tasks with general reward function. Please refer Appendix B and Appendix A for
22

---

Under review as a conference paper at ICLR 2022
4000
000
200
Figure 8: Ablation of HC-decomposition in Q-HC-Singleton and Q-HC- Q-HC-Pairwise-l. The task is sum-form PI-DRMDP with n fixed 20. Dashed lines are two ablations Q-Singleton and Q- Pairwise-1. All curves show the mean and standard deviation of 6 seeds.
detailed discussions. For environments with maximal e overlapping steps, the reward function is formally defined as follows.
Fe(Tt,-ctttn.)
Σ r(si,a)) a:)
ie(t, +m.-
where r(s;, (4) is the standard per-step reward. If < O, then r(s;, a,) 0. In this definition, the reward is delayed by e steps and thus the signal intervals are overlapped. In Figure [ we show the relative average performance (over Reach-v2, Hopper-v2, HalfCheetah-v2, Walker2d-v2, and Ant-v2) of each algorithm w.r.t Oracle SAC trained on the dense reward setting. Please refer to Appendix D for the exact definition of this metric. The results demonstrate the superiority of our algorithms over the baselines in the General Reward Function experiments. This supports our claim that our algorithmic framework and the approximation method (HC) can be extended naturally to the general definition, i.e., PI-DRMDP-c. Furthermore, we show the detailed learning curves of all algorithms in tasks with different overlapping steps in Figure 10
Duntardem 01
Figure 9: Relative Average Performance of our algorithms and the basclines on PI-DRMDP-c tasks with general reward functions. Each dot represents the relative performance of the algorithm over the P1-DRMDP-c task (average over Reach-v2, Hopper-v2, HalfCheetah-v2, Walker2d-v2, Ant-v2).
D EXPERIMENT DETAILS
D.I IMPLEMENTATION DETAILS OF OUR ALGORITII
We re-implement SAC based OpenAI baselines (Dhariwal al. 2017). The corresponding hyperparameters are shown in Table We use a smaller batch size due to limited computation power.
To convince that the superiority our algorithms (Q-HC-RNN, Q-HC-Pairwise-K. Q-HC- Singleton) results from the efficient approximation framework (Section 3.2 and the consistency
23

---

Under review as a conference paper at ICLR 2022
30/d
Waber
Figure 10: Learning curves of our algorithms Q-HC and several previous baselines. The first line refers to the task with c = O. The second line refers to the task with = 5. The third line refers to the task with = All curves show the mean and one standard deviation of 6-7 seeds.
Table 3: Shared Hyperparameters with SAC
Hyperparameter
SAC
2s, me architecture
2 hidden-layer ML.s with 256 units each
non-lincarity
ReLU
batch size discount factor 7 optimizer
128
0.99
Adam Kingma & Ba 2014)
learning rate
entropy target
-|A] 0.005
target smoothing
replay buffer
large enough for 1M samples
target update interval gradient steps
with the theoretical analysis (Section 3.1 rather than from a better choice Syyper-paaamttrs. we did not tune any aperr-paraeete shared with SAC (i.c., in Table
The architecture of different H&s are shown follows. For the regularization coefficient X, search À in {0.0, 0.05, 0.5, 3.0) for each implementation of Q-HC. is fixed for all tasks including the toy example.
Q-HC-RNN. Each step's 's input Te:++1 is first passed through fully connected network with 48 hidden units and then fed into the GRU with 48-unit hidden state. Ho (Teat)) is the output of the GRU at the corresponding step. We use X = 5.0.
Q-HCCPairwise-1 1. Both eg and c/, are two-layer MLPs with 64 hidden units each. À = 0.5.
O-HC-Pairwise--. All ci, i 0, 1, 2, are two-layer MLP with 48 hidden units each. À = 5.0.
Q-HC-Singleton. by is a two-layer MLPs with 64 hidden units each. = 0.05.
As suggested by the theoretical analysis, augment the normalized l, the state input.
24

---

Under review as a conference paper at ICLR 2022
All high dimensional experiments are based OpenAl Gym (Greg et al. 2016) with MuJoCo200. All experiments are trained on GeForce GTX 1080 Ti and Intel(R) Xeon R) CPU E5-2630 v4 @ 2.20GHz. Each single run can be completed within 36 hours.
D.2 IMPLEMENTATION DETAILS OF OTHER BASELINES
Q-RNN. We use the same shared pppee-parameters as in T The only exception is the architec- ture of the GRU critic. Similar Q-HC-RNN, each state-action pair is first passed through fully connected layer with 128 hidden units and ReLU activation. Then it is fed into the GRU network with 128-unit hidden state. The (T(,,,++1) is the output of the GRU network at the correspond- ing step. We choose the above architecture to ensure that the number of parameters is roughly the same with our algorithm for fair comparison. The learning rate for the critic still 3 x 10 after fine-tuning.
SAC-IRCR. Iterative Relative Credit Refinement (Gangwani et al. 2020 is implemented on episodic reward tasks. In the delayed reward setting, we replace the smoothing value (i.e., episode return) with the reward of the reward interval. We find this performs better than using the episode return.
D.3 DETAILS FOR TOY EXAMPLE
Point Reach. As illustrated in Figure the Point Reach PI-DRMDP task consists of 100x grid, the initial position at the bottom left corner, a 10x10 target area adjacent to the middle of the right edge and a point agent. The observation for the point agent is its (æ, y) coordinate only. The action space is its moving speed (y), E [_1, along the two directions. Since the agent can not observe the goal directly, it has to infer it from the reward signal. To relieve the agent from heavy exploration (not our focus), the delayed rewards provide some additional information the agent as follows.
The grid is divided into 10 sub-areat of 100 along the x-axis. We denote the sub-areat (high- lighted by one color each in Figure 4 as S,, = [0 10) form left to right. In each sub-area S. provides extra reward and the reward r indicates how far the sub-area the target (i.e., r i). Clearly, the bigger the reward is, the closer the sub-area is to the target area. Besides, reward interval length is fixed 20 and the point agent is rewarded with the maximal r¹ has visited in the interval together with a bonus after reaching the target and punishment for not reaching. Namely,
9
r(Feat)) = max
Σ r' 1(5):+11 E S.) + 10 (1reach target) - 1)
jElEt+n]
i=0
The task ends once the agent reach the target and also terminates after 500 steps. Clearly. the optimal policy is to go straightly from the initial point to the target area without hesitation. The shortest path takes roughly 95 steps. The learning curves in Figure show the mean and half of standard deviation of 10 seeds. All curves are smoothed equally for clarity.
Heatmap. In Figure 4 right, the heatmap visualizes the value of ba(st, ae) the whole grid. We select the bys after the training has converged to the optimal policy. To be specific of the visual- ization, for each of the 10x10 cells on the grid, s; in by ag selected as the center of the cell and is sampled from T(-[s,,0) Additionally, in Figure 11 we visualize (s(s o:) similarly of HC--Singleton without Ireg- Clearly, Figure 11 shows the similar pattern as Figure right.
D.4 DETAILS FOR VARIANCE ESTIMATION
The experiment in Figure is conducted in the following manner. First, we train a policy To with Q-HC-Singletor and collect all the samples along the training to the replay buffer D. Second, two additional critics are trained concurrently with samples uniformly sampled from D. One critic uses structure. Most importantly,
the GRU architecture (i.c., Q-RNN) and the other uses since these two critics are not used for policy updates, there is no overestimation bias (Fujimoto et al. 2018). Thus, instead using the CDQ method Fujimoto et al. 2018)), these two critics are trained via the method in DDPG Siiverr et al. 2014). With mini-bated from D, compute the gradients on the policy's 's parameters # in Eq. (5) and Eq. (7) from the two extra critics respectively. Noticing that these gradients are not used in the policy training.
25

---

Under review as a conference paper at ICLR 2022
Figure 11: Visualization of (s, ax) of Q-HC-Singleton without regulation term.
Then, we compute the sample variance of the gradient each parameter 0g in the policy network. The statistics (y-axis in Figure T is the sum of variance over all parameters in the final layer (i.e., the layer that outputs the actions). The statistics is further averaged over the whole training and scaled uniformly for clarity.
D.5 DETAILS FOR RELATIVE AVERAGE PERFORMANCE
Here, we formally introduce the Relative Average Performance (RAP) metric in Table 2 Figure and Figure 3 The relative average performance (RAP) of algorithm A on task set E is defined as the average of RAP over tasks in E. RAP of each task is the episodic return after 1M steps training normalized by the episodic return of Oracle SAC at IM steps (trained dense reward environment.. The only exception is Reach-v2, in which the episodic returns are added by 50 to before the normalization.
26


Reviews:
[{"review_id": "gzhRQ7gPt30", "reviewer": "Reviewer_mJkz", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\n- What is the relation between $t_i$ and $t+1$? The definition of $t_i$ only says that it is the first step of the interval $i$, but does not have any dependency on $t$ itself. Throughout the paper, the range of $t_i:t+1$ is used but I do not know if I understand this range properly.\n\n- It felt that under dynamics being Markovian and only rewards being Markovian, then additionally enforcing past invariance condition will result in even the standard Q-learning to not having the fixed point bias. But authors provide an interesting example later on confirming the fixed point bias, if the non-Markovian structure is not accounted for. Perhaps this result can be alluded to earlier on in the paper.\n\n- It is also worth mentioning that policy gradient, with full Monte-Carlo roll-outs can deal with any form of non-Markovian structure to provide exact policy evaluation and policy improvement (it can be seen from slide 9 here: http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_4_policy_gradient.pdf). Further, using importance sampling it can be made to work in the off-policy setting. Of course, it may not find the optimal policy if it is not within the policy class. The problem occurs when using Q-learning (or actor-critic methods) that rely on the Markov structure through the Bellman equation to estimate the Q-values.\n\n- However, I am not sure what the novelty of the proposed method is, both theoretically and practically. How is the proposed method different from just naively concatenating the history of the last n steps in the state? (This might also clarify my confusion about $t_i$ and $t+1$), given that the reward only depends on the signal interval $n$. One can now consider a new MDP that has state = concatenation of the past $n$ steps, and therefore Markovian in this new state space. Using this state-space, all the existing policy improvement results will hold directly. Of course, one problem here is about knowing what is the value of $n$, but I am not sure how is the proposed method handling that either? Is it assumed that the value of $n$ for any interval is provided to the agent?  (Yes, for the proposed method, the policy does not concatenate recent history, but Q still does)\n\n- Another question worth addressing is which step fails in the final algorithm if even the states are Markovian (but past invariance still holds) ?\n\n- Policy gradient equations are wrong everywhere in the paper (Eq 2, 5, and 7). It needs (a) distribution correction terms to account for the off-policy sampling under $D$ instead of $\\pi$, and (b) is also missing the $\\gamma$ terms in the gradient (Thomas, Philip. \"Bias in natural actor-critic algorithms.\" International conference on machine learning. PMLR, 2014). \n\n- For experiments, the paper mentions \"To convince that the superiority of our algorithms..... we did not tune any hyper-parameter shared with SAC\". This statement is very weak and makes the empirical results less meaningful. The empirical results only show that _for this given choice of hyper-parameters_ the proposed method is better. Further, there are additional parameters for the proposed method which are indeed tuned :(\n\n- It is worth calling out before each Fact/Proposition that a tabular setting is being considered for that given result. Further, the proofs in the appendix have lots of writing errors and should be presented better.\n", "summary_of_the_paper": "Authors look at a problem where the rewards are non-Markovian (but dynamics are Markovian). They show how naively using existing methods on this setup may result in sub-optimal policies and then provide a method based on considering recent history as the augmented state.\n\n", "summary_of_the_review": "Paper falls a little short on both theoretical/methodological novelty and rigorous experimentation.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YKtxXTjrRka", "reviewer": "Reviewer_6XaH", "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": "1. This paper proposes a new setting of delayed reward, namely DRMDP. It seems unclear what real problem can be exactly modeled by this setting. Moreover, Past-Invariant Delayed Reward Markov Decision Process seems to impose an additional assumption that the past does not affect the future. What application can be modeled by this model? What does path-invariance mean for the distribution of signal interval length? What $q_n (\\cdot)$ meet the assumption?\n\n2. This paper proposes to focus on a restricted policy class $\\Pi_s$. How good is it? Even if we achieve the globally optimal policy, it does not mean we find a \"good\" policy because the policy can be very small such that all policies in this class are bad. \n\n3. For $Q^{\\pi}$ to be the solution to the least-squares loss in (1), what's the assumption on the behavior policy? Does it also belong to $\\Pi_s$? How to choose $\\hat Q$? Is it possible to show that $Q^\\pi$ is the fixed point of a Bellman operator for the policy evaluation problem?\n\n4. How to conduct policy improvement step for $\\Pi_s$? \n\n5. What is the reasoning behind HC-decomposition? Why use an additive model instead of using a big GRU that takes everything as the input? \n\n6. This work is related to bandit and RL with stochastic delays: \n\n- Learning in Generalized Linear Contextual Bandits with Stochastic Delays\n- Gradient-free Online Learning in Continuous Games with Delayed Rewards\n- Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?", "summary_of_the_paper": "This work considers a modified MDP model where the rewards are subject to random delays. Specifically, the timesteps are divided into random batches and the agent observes the cumulative rewards of the batch when it ends. For such a model, Markov property does not hold and classical methods do not apply. The authors propose a policy iteration method for learning the optimal policy within a restricted policy class. In particular, the authors consider a more restricted model, named Past-Invariant Delayed Reward Markov Decision Process, and a policy class with an augmented parameter that indicates the current time step in the signal batch. In such a setting, the authors show that, under the tabular case, the true value function minimizes the mean-squared error of the policy evaluation problem, and the policy iteration step yields an improved policy. Furthermore, to enhance computational efficiency, the HC-decomposition is utilized in the Q-function. ", "summary_of_the_review": "This work proposes a new setting of MDP models with stochastic delays. But the assumption of the MDP model is not well-justified -- it is unclear what signal interval distribution justifies the assumption. Also, the policy class might be restricted and it is unclear how to conduct policy improvement within the policy class. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DAWiQanVS7U", "reviewer": "Reviewer_oufu", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths\\\n         The idea is pretty new and interesting.\n         It seems from the empirical results that the proposed algorithm performed well in the tested domains.\n\nThe main weakness of the paper is that it is very difficult to understand. There are just so many parts that are confusing to me.\\\n         a) Generally speaking, it seems to me that this paper tries to present so many different things in one paper without making each of them clear to the readers. For example, the main theoretical contribution of the paper, the newly proposed decision process, once defined, is only briefly discussed in section 3.1. It is hard to tell the commonalities and differences between the new decision process and classic MDP. And I would also suggest the authors compare the proposed decision process with Semi-MDP because they seem to be closely related. The other example I can give is that the paper derives a policy improvement theorem and then directly jumps to a deterministic policy gradient (equation 5), which uses continuous actions while all the definitions and results derived up to that point are for discrete actions. Then the paper starts to talk about neural network implementation of the policy gradient. It is like algorithms, theories, and implementations are all mixed together without a clear explanation of each of them. \\\n         b) Each policy in \\Pi_s is a function of s_t, a_t, and t - t_i. But the action-value function takes the entire trajectory segment as input, which entails more information than s_t, a_t, and t - t_i. Do we really need to let the action-value function take the entire trajectory segment as input in order to get the best policy in \\Pi_s?\\\n         c) Given that the authors want to find the optimal policy within \\Pi_s, why not just combine s_t and t - t_i and treat them as a state? You would convert the problem to the normal MDP problem in this way.\\\n         d) Some sentences are confusing: e.g., page 4 \"Consequently, Q can be found precisely via the minimization for tabular expressions\". Why is this important? This is true when you know \\hat Q, but from the paper, it seems that you don't know it right?\\\n         e) Frankly speaking, the notations are not easy to follow. You might want to consider other ways to make it easier for readers to understand.\n\n", "summary_of_the_paper": "This paper proposed a decision process that is Markov in state transitions but non-Markov in reward. The paper argued that this new decision process is a suitable model for applications where rewards are delayed. For this decision process, the paper proposed analogues of action-value function and policy improvement theorem. It further proposed to decompose the action-value into two parts, one of which only depends on the current state-action pair while the other one depends on the history. It then proposed an algorithm that extends SAC and estimates the two parts separately. Empirical results showed improved performance over SAC on delayed reward versions of several continuous control problems.", "summary_of_the_review": "I suggest rejecting the paper because of the weaknesses listed in my main review. I like the idea of the paper and would encourage the authors to keep working on it. But the paper in its current form is not ready to be published from my point of view.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "D4L0gL7Hvii", "reviewer": "Reviewer_fukM", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper opens with statements on how delay in MDPs is an unexplored territory. However, the authors seem to ignore both mature and recent works that address it thoroughly and reach conclusions that may affect the findings in this paper. Two examples are [1] and [2]. I find [2] even more relevant, since like in this reviewed paper, it also proposes a new Q-function definition and discusses the related non-stationarity.\n\nNext, even though the grammar is fine, I find the paper hard to follow. Specifically, the past-invariance introduced in Def. 2 that constitutes the basis for the consecutive results is not clear to me. Does it really assume the reward is independent of past decisions but only the current one? How is that realistic in a delayed reward setup, where the history is exactly what yields the sequence of present reward? Under such a strong assumption, I believe the result in Fact 2 is almost trivial. \n\nIn similar fashion, the H-C decomposition in Sec. 3.2 seems extremely artificial. If I understand correctly, it assumes the Q-function decomposes to two additive parts of past and present. From an engineering POV, I can see how it is useful. But how does this make sense in a delayed reward setup where everything depends on past decisions? I would expect more formal and informal (intuitive) justifications for such a strong assumption. Note also that making this assumption on the Q-function is stronger than making it on the reward.\n\nAdditional comments/questions:\n1. First sentence in p.3 -- why is it bizarre that the proposed PI-DRMDP requires the optimal policy to consider history? Can the authors provide an example of such a case? If not, can they show the opposite and provide a proof that there is always an optimal history that is history independent? This is expected especially as the authors are those who propose this model and later rely on this assumption. Also, what information exactly is required for the policy to be optimal? I general, the usage of the word \"bizarre\" without any justification is bothering. \n2. I find the explanations below Sec 2.2 to be confusing, especially the paragraph below the display equation and the multiple behavior policies that \"come out of nowhere\". \n\n\n[1] Walsh, Thomas J., et al. \"Learning and planning in environments with delayed feedback.\" Autonomous Agents and Multi-Agent Systems 18.1 (2009): 83-105.\n\n[2] Derman, Esther, Gal Dalal, and Shie Mannor. \"Acting in Delayed Environments with Non-Stationary Markov Policies.\" International Conference on Learning Representations (2021).", "summary_of_the_paper": "The paper studies the problem of delayed reward, which imposes non-Markov behavior that hinders performance of \"standard\" RL algorithms. It then proposes a new Q-function definition based on segments of reward, together with a decomposition to historical-current parts. Lastly, the authors add experimental comparisons to several recently published methods.", "summary_of_the_review": "The paper makes strong assumptions on MDPs with delayed reward that do not align well with knowledge from previous works. Instead of trying to compare and articulate the exact differences and conclusions of their work and previous literature, the authors briefly list some existing works at the end of the paper in an independent section without such warranted explanations. While I appreciate the vast experimental part of the paper with comparison to several other methods, the rest of the paper is not well justifying many of its statements and does not convince that the overall approach makes sense.", "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": {}}]

Author rebuttal:

Meta-review: The paper introduces an interesting new model for MDPs, where the time is divided into random segments, and at the end of each segment the cumulative reward for the given segment is communicated to the agent. Some theoretical results with a policy improvement algorithm, as well as a more practical algorithm are presented. While the reviewers valued these contributions, they all had issues with the presentation of the paper.

These presentation issues make the paper extremely hard to follow -- this was a problem for all reviewers, and I also verified it myself. The reviewers also raised issues regarding the experiments, where the algorithms should be tuned properly to be able to draw valid conclusions.

While unfortunately the above issues prevent me from recommending acceptance of the paper, the authors are strongly encouraged to revise their paper and resubmit to the next venue, with a special emphasis on making the presentation proper. There are several problems/recommendations mentioned in the reviews which will certainly help in this regard (I would also add that special care should be made that everything is defined properly, e.g., the equation for your policy iteration should appear in the main text not in a proof in the appendix, or $\hat{Q}_\phi$ should be defined, etc.).
Decision: Reject