Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 a 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 et al., 2018), molecular design (Olivecrona et al., 2017) 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., 2019), 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 is a delayed reward which can only be obtained after the vehicles have passed the congestion (long after a single switch). In molecular design, only the molecule formed after the final operation can provide a meaningful evaluation for the whole process (Olivecrona et al., 2017). In locomotion control where the feedback is generated by the interaction with the large environment, it 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 non-Markovian rewards and perform unsatisfactorily 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 delayed 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 algorithmic 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 information. We also propose a 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 are delayed.

heading: 2 PROBLEM FORMULATION
text: 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 Past-Invariant (PI) condition, which is satisfied in many real-world settings with delayed rewards.

heading: 2.1 PAST-INVARIANT DELAYED REWARD MDPS
text: 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 a signal interval may depend on the state-action sequence and is observed only at the end of the interval. We formally define DRMDP as follows. Definition 1 (DRMDP). A Delayed Reward Markov Decision Process M = (S,A, p, qn, r, γ) is described by the following parameters. 1. The state and action spaces are S and A respectively. 2. The Markov transition function is p(s′|s, a) for each (s, a) ∈ S×A; the initial state distribution
is p(s0). 3. The signal interval length is distributed according to qn(·), i.e., for the i-th signal interval, its
length ni is independently drawn from qn(·).

heading: 4. The reward function r defines the expected reward generated for each signal interval; suppose
text: τi = τt:t+ni = (s, a)t:t+ni = ((st, at), . . . (st+n−1, at+ni−1)) is the state-action sequence during the i-th signal interval of length ni, then the expected reward for this interval is r(τi).
5. The reward discount factor is γ.
In this work, we focus on the infinite-horizon DRMDP. We use (τ, n) = (τi, ni)i∈{1,2,3,... } to denote a trajectory, where τi is the state-action sequence during the i-th signal interval and ni is the corresponding length. We also let ti be first time step of the i-th signal interval, i.e., ti =∑i−1 j=1 nj . Note that the reward r(τi) is revealed at time ti + ni − 1 = ti+1 − 1. We finally define
the discounted cumulative reward of the trajectory (τ, n) by R(τ, n) := ∑∞ i=1 γ
ti+1−1r(τi). The objective for DRMDP is to learn a policy π that maximized the expected discounted cumulative reward J (π) := E(τ,n)∼π[R(τ, n)].
Augmented Policy Class. In DRMDP, the Markov policy class {π = π(at|st)} might not achieve satisfactory performance because of the non-Markovian nature of the reward function. Theoretically speaking, we need a more general policy class Πτ = {π = π(at|τti:t ◦ st)} (i is the index of the signal interval that t belongs to). A formal statement is included in Appendix B. Unfortunately, policy optimization in such an exponentially large space Πτ is hard in practice, especially for highdimensional problems. Thus, as a trade-off, we consider the policy class Πs = {π = π(at|st, t − ti)}, 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. Definition 2 (PI-DRMDP). A Past-Invariant Delayed Reward Markov Decision Process is a DRMDP M = (S,A, p, qn, r, γ) whose reward function r satisfies the following Past-Invariant (PI) condition: for any two trajectory segments τ1 and τ2 of the same length, and for any two equallength trajectory segments τ ′1 and τ ′ 2 such that the concatenated trajectories τa ◦ τ ′b are feasible under the transition dynamics p for all a, b ∈ {1, 2}, it holds that
r(τ1 ◦ τ ′1) > r(τ1 ◦ τ ′2) ⇐⇒ r(τ2 ◦ τ ′1) > r(τ2 ◦ τ ′2).
Roughly speaking, in PI-DRMDP, the relative credit for different actions at each st only depends on the experience in 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 r with PI condition is r(τt:t+n) = ∑t+n−1 i=t r̂(si, ai), where r̂ is a 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 as the sum-form.
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 suboptimality issue, we will show that our algorithmic framework guarantees policy improvement in Πs, which is sufficient to support the design of actor-critic methods. Consequently, we are able to put forward a practical RL algorithm that can achieve the SOTA performance in delayed-reward tasks. The overall contribution of our work is summarized in Table 1 and we leave the optimality of the DRMDP problems as future works.
General Reward Function. In Definition 1, we 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, r(τti−c:ti+ni). 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 c = 0 in the main text for the simplicity of the exposition.

heading: 2.2 OFF-POLICY RL IN PI-DRMDP
text: Deep Reinforcement Learning has achieved great success in solving high-dimensional MDPs problems, among which the off-policy actor-critic algorithms SAC (Haarnoja et al., 2018a) and TD3 (Fujimoto et al., 2018) are the most widely used ones. However, since the rewards are delayed and non-Markovian in PI-DRMDP, 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-policy samples brings in off-policy bias. TD3 minimizes over φ w.r.t.
Lφ = ED [ (Rt + γQ̂φ(st+1, a ′ t+1)−Qφ(st, at))2 ] , (1)
where (st, at, Rt, st+1) is sampled from the replay bufferD,Rt = r(τi) if t = ti+1−1 and i = i(t) is the index of the reward interval that t belongs to, and Rt = 0 otherwise. Q̂φ represents the target value of the next state and a′t+1 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 β 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 a sequence of behavior policies β = {βk}Kk=1. In the delayed reward setting, since the reward r(τi) depends on the trajectory of the whole signal interval (i.e., τi) instead of a single step, the function Qφ(st, at) learned via Eq. (1) will also have to depend on the trajectory in the signal interval upto time t (i.e., τti:t) rather than the single stateaction pair at time t. Since the samples are collected under a sequence of behavior polices β, different behavior policy employed at state st may lead to different distribution over τti:t in Eq. (1). Consequently, Qφ(st, at) 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, Qφ(st, at) learned in Eq. (1) with on-policy samples in D may still be problematic. We formally state this problem via a simple sumform PI-DRMDP in Appendix B whose optimal policy is in Πs. In this example, the fix point of Eq. (1) 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. (1) would suffer a relative large variance. Since Rt varies between 0 and r(τi), minimization of TD-error (Lφ) with a mini-batch of data has large
variance. As a result, the approximated critic will be noisy and relative unstable. This will further effect the policy gradients in Eq. (2).
∇θJ(πθ) = ED [ ∇atQφ(st, at) ∣∣∣ πθ(st) ∇θπθ(st) ]
(2)
To sum up, directly applying SOTA off-policy algorithms in PI-DRMDP will suffer from multiple problems (off-policy bias, fixed point bias, large traning noise, etc). Indeed, these problems result in a severe decline in performance even in the simplest task when n = 5 (Gangwani et al., 2020).

heading: 3 METHOD
text: In this section, we first propose a novel definition of the Q-function (in contrast to the original Qfunction) and accordingly design a new off-policy RL algorithm for PI-DRMDP tasks. This method has better theoretical guarantees in both critic learning and policy update. We then introduce a HCdecomposition framework for the proposedQ-function, which leads to easier optimization and better learning stability in practice.
3.1 THE NEW Q-FUNCTION 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.
Qπ(τti:t+1) := E(τ,n)∼π  ∞∑ j=i γtj+1−t−1r(τj) ∣∣∣τti:t+1  , (3) The new Q-function is defined over the trajectory segments τti:t+1, including all previous steps in st’s signal interval. Besides, the expectation is taken over the distribution of the trajectory (τ, 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 as follows. The proofs are listed in Appendix B.
First, we consider the following objective function Lφ := ED [ (Rt + γQ̂φ(τtj :t+2)−Qφ(τti:t+1))2 ] , (4)
where τtj :t+2 = τti:t+1 ◦ (st+1, a′t+1) (so that j = i) if t is not the last step of τi, and τtj :t+2 = (sti+1 , a ′ ti+1) (so that j = i+1) otherwise. Similarly to Eq. (1), in Eq. (4), (τti:t+1, Rt, st+1) is also sampled from D and a′t+1 is sampled from π correspondently. We may view Eq. (4) as an extension of Eq. (1) for Qπ . However, with these new definitions, we are able to prove the following fact 1. Fact 1. For any distribution D with non-zero measure for any τti:t+1, Qπ(τti:t+1) is the unique fixed point of the MSE problem in Eq. (4). More specifically, when fixing Q̂φ 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 at any state st is invariant to the choice of τti:t, thanks to the PI condition. Fact 2. For any τti:t, τ ′ti:t and st, at, a ′ t which both τti:t ◦ st and τ ′ti:t ◦ st are feasible under the transition dynamics, ∀π ∈ Πs, we have that
Qπ(τti:t ◦ (st, at)) > Qπ(τti:t ◦ (st, a′t)) ⇐⇒ Qπ(τ ′ti:t ◦ (st, at)) > Q π(τ ′ti:t ◦ (st, a ′ t)).
Fact 2 ensures that the policy iteration on πk(at|st, t−ti) with an arbitraryQπ(τti:t◦(st, at)) results in the same πk+1 ∈ Πs. Consequently, we are able to prove the convergence theorem for the policy iteration with the Q-function.
1The definition ofQπ and Fact 1 also holds in DRMDP and for π ∈ Πτ .
Proposition 1. (Policy Improvement Theorem for PI-DRMDP) For any policy πk ∈ Πs, the policy iteration w.r.t. Qπk produces policy πk+1 ∈ Πs such that ∀τti:t+1, it holds that
Qπk+1(τti:t+1) ≥ Qπk(τti:t+1), which implies that J (πk+1) ≥ J (πk).
Thus, the off-policy value evaluation with Eq. (4) and the policy iteration in Proposition 1 guarantee that the objective function is properly optimized and the algorithm converges. Besides, for off-policy actor critic algorithms in the continuous environment, the policy gradient∇θJ (πθ) is changed to
∇θJ (πθ) = ED [ ∇atQπ(τti:t ◦ (st, at)) ∣∣∣ πθ(st,t−ti) ∇θπθ(st, t− ti) ] , (5)
where (τti:t, st) is sampled fromD. The full algorithm is summarized in Algorithm 1. As a straightforward implementation, we approximate Qπ(τti:t+1) with a GRU network (Cho et al., 2014) and test it on the continuous PI-DRMDP tasks. As shown in Figure 2(a), our prototype algorithm already outperforms the original counterparts (i.e., SAC) on many tasks.

heading: 3.2 THE HC-DECOMPOSITION FRAMEWORK
text: 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 (Goodfellow et al., 2016)) and computational inefficiency. Furthermore, the inaccurate estimation of Qπ(τti:t+1) 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-decomposition framework (abbreviation of History-Current) that decouples the approximation task for the current step from the historical trajectory. More specifically, we introduce Hφ and Cφ functions and require that
Qφ(τti:t+1) = Hφ(τti:t) + Cφ(st, at), (6)
Here, we use Cφ(st, at) to approximate the part of the contribution toQφ made by the current step, and useHφ(τti:t) to approximate the rest part that is due to the historical trajectory in the 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 on 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, we believe the architecture is easier to optimize, especially for Cφ whose input is a single state-action pair.
Moreover, we also find that the policy gradient will only depend on Cφ(st, at). Indeed, we calculate that the policy gradient ∇θJ HC(πθ) equals to
ED [ ∇atCφ(st, at) ∣∣∣ πθ(st,t−ti) ∇θπθ(st, t− ti) ] , (7)
Comparing Eq. (7) with Eq. (5), we note that the gradient on the policy π under HC-decomposition will not be effected by τti:t. Thus, for a mini-batch update, our policy gradient has less variance and the training becomes more efficient. In Figure 1, 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 Cφ functions, we minimize the following objective function
LHCφ =ED[(Rt + γ(Ĥφ(τti:t+1) + Ĉφ(st+1, a′t+1))− (Hφ(τti:t) + Cφ(st, at)))2] + λLreg(Hφ), (8)
where the first term is the TD error in Eq. (4) and the second term is a regularizer on Hφ. We use the regularization to stabilize the optimization process and prevent Hφ from taking away too much information of the credit on the choice of at. In Section 4.1, we will compare several simple choices of Hφ and Lreg. The search for other designs of Hφ and the regularization term in various settings is left as future work.

heading: 4 EXPERIMENT
text: In this section, we first test and illustrate our algorithmic framework and HC-decomposition on highdimensional PI-DRMDP tasks to 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 be the SOTA algorithm which is most sample-efficient and stable. Finally, we demonstrate our algorithm via an illustrative example.

heading: 4.1 DESIGN EVALUATION
text: We implement the following architectures of Hφ in our experiment. Our algorithm is based on SAC (Haarnoja et al., 2018a).
Q-HC-RNN. Hφ(τti:t) is approximated with a GRU network.
Q-HC-Pairwise-K. Hφ(τti:t) is the sum of K+1 networks {ckφ}k=0,1,...K for different pairwise terms as follows2. K = 1, 3 are included in the experiment.
Hφ(τti:t) = ∑
k∈[0:K+1] ∑ j∈[ti:t−k] ckφ(τj:j+1 ◦ τj+k:j+k+1).
Q-HC-Singleton. Hφ(τti:t) is the sum of single step terms. Hφ(τti:t) = ∑
j∈[ti:t]
bφ(τj:j+1).
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 error. 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 Hφ is a 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.
Lreg(Hφ) = ED [ (Hφ(τi)− r(τi))2 ] , (9)
2Input for c0φ is thus a single state-action pair.
where τi is sampled from the D. As discussed in Section 3.2, the history part Hφ(τti:t) should only be used to infer the credit of τti:t within the signal interval τi. However, without the regularization, the approximated Hφ may deprive too much information from Qφ than we have expected. Thus, in a direct manner, we regularize Hφ(τi) to the same value of r(τi).
In Figure 2, we compare these algorithms on sum-form PI-DRMDP continuous control tasks based on OpenAI Gym. Rewards are given once every n steps which is uniformly distributed from 15 to 20. The reward is the sum of the standard per-step reward in these tasks. Our method is compared with vanilla SAC andQ-RNN whoseQπ 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 Qπ while vanilla SAC cannot handle non-Markovian rewards. 2. Qπ approximated with HC-decomposition architecture (i.e., with prefixQ-HC) is more sample-
efficient and more stable thanQ-RNN. Indeed, the HC architecture results in an easier optimization in critic learning.
3. Figure 2(b) shows the importance of regularization, especially when Hφ has complex form (i.e., Q-HC-RNN) and thus is more likely to result in ill-optimized C-part.
More Experiments. In Appendix C.1, 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 (qn). As shown in Table 2, our Q-HC methods are scalable to sum-form tasks with a signal interval length of 60 environmental 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-HCs still outperform Q-RNN and the vanilla SAC consistently in all environments (Figure 5). This suggests that the advantage of HCdecomposition also holds in other PI reward function tasks. Moreover, in Figure 6, we also test TD3-based Q-HC-Singleton and Q-HC-Pairwise-1. Comparing to TD3-based Q-RNN and vanilla TD3 (Fujimoto et al., 2018), 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 a remedy to the unstable optimization of direct Q approximation. As Q-HC is an implementation of the general algorithm in Section 3.1, it handles the non-Markovian rewards with theoretical support. In future work, we will explore the boundary of HC-decomposition, and analyze the effect of the projection error mathematically.

heading: 4.2 COMPARATIVE EVALUATION
text: 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). It 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, it 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., 2020). It utilizes off-policy data to provide a 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 our setting.
For clarity, we only include Q-HC-Pairwise-1 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-policy nature (i.e., based on PPO (Schulman et al., 2017)). SAC-IRCR performs well only on some easy tasks (e.g. Hopper-v2). Unfortunately, SAC-IRCR has a bad performance (e.g. Ant-v2, Walker2dv2, Reacher-v2) on other tasks. We suspect in these tasks, the smoothing technique results in a erroneous guidance reward which biases the agent. Thus, SAC-IRCR is not a safe algorithm in solving delay reward tasks. In contrast, ours (as well as other implementations shown in Appendix C.3) perform well on all tasks and surpass the baselines by a large margin. Most surprisingly, our algorithm 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 are given only every 20 steps.
We also conduct experiments on tasks with general reward functions, in which our algorithmic framework and the HC-decomposition can be naturally extended to (please refer to Appendix B and Appendix A). In the General Experiment of Figure 3, we plot the relative average performance w.r.t Oracle SAC on tasks whose general reward functions have different amount of overlapped steps (c = 5, 10). Clearly, our Q-HC is still the SOTA algorithm for every c. Thus, our method is applicable to environments with general reward functions. Please refer to Appendix D for experiment details.

heading: 4.3 HISTORICAL INFORMATION
text: 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 is a target-reaching task illustrated in Figure 4 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-Singleton outperforms the baselines by a large margin. For better illustration, we visualize bφ(st, at) in Q-HC-Singleton on the grid in Figure 4 Right. The pattern highlights the line from the start point to the target area (i.e., the optimal policy), suggesting that bφ 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 H-component may also possess direct impact on the policy learning instead of simply function as an approximator.

heading: 5 RELATED WORK
text: Off-Policy RL: Off-policy deep reinforcement learning algorithms TD3 (Fujimoto et al., 2018) and SAC (Haarnoja et al., 2018a) are the most widely accepted actor-critic algorithms on 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-learning (CDQ) technique to address overestimation in critic learning. Haarnoja et al. (2018a) also uses CDQ technique but instead optimizes the maximum entropy objective. These two methods lead to a more robust policy.
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 a popular research area recently. Some theoretical analysis have been conducted on delayed rewards in MAB and MDP Zhou et al. (2018; 2019); Héliou et al. (2020) These tasks are known to be difficult for long-horizon credit assignment (Sutton, 1984). To address this issue, Zheng et al. (2018) proposes to use intrinsic reward to boost the efficiency of policy gradients. The intrinsic reward is learnt via meta-learning (Finn et al., 2020). Gangwani et al. (2019) and Guo et al. (2018) use a discriminator to provide guidance reward for the policy. The discriminator is trained jointly with the policy with binary classification loss for self-imitating. In RUDDER (Arjona-Medina et al., 2019), it utilizes a recurrent network to predict a surrogate per-step reward for guidance. To ensure the same optimality, the guidance is then corrected with ground truth reward. Liu et al. (2019) extends the design and utilizes a Transformer (Vaswani et al., 2017) network for better credit assignment on episodic reward tasks. Recently, Klissarov & Precup (2020) proposes to use GCN (Kipf & Welling, 2016) network to learn a potential function for reward shaping (Ng et al., 1999). Noticing that all these algorithms are based on PPO (Schulman et al., 2017) and thus are on-policy algorithms while ours is an off-policy one.
Most recently, Gangwani et al. (2020) proposes to augment off-policy algorithms with a trajectoryspace smoothed reward in episodic reward setting. The design turns out to be effective in solving 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 in Section 4.2, in many cases, this method becomes extremely spurious. Our algorithm is derived from a theoretical perspective and performs well on all tasks.

heading: 6 CONCLUSION
text: In this paper, we 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 PIDRMDP, we put forward a novel and general algorithmic framework to solve the PI-DRMDP problems 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 to approximate the Q-value directly. To address this issue, we propose to use the HC-approximation framework for stable and efficient training in practice. In the experiment, we compare different implementations of the HC framework. They all perform well and robustly in continuous control PI-DRMDP locomotion tasks based on OpenAI Gym. Besides, our method outperforms previous baselines on delayed reward tasks remarkably, suggesting that our algorithm is a SOTA algorithm on these tasks so 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 1, possibly with offline data (Levine et al., 2020). The other direction is to design efficient and advanced algorithms with theoretical guarantees for the general DRMDP tasks.

heading: A ALGORITHM
text: We summarize our algorithm for PI-DRMDP with General Reward Function as follows.
Algorithm 1 Algorithm with General Reward Function 1: Choose Qφ structure: Q-RNN, Q-HC-Pairwise-K, e.t.c 2: Initialize πθ,Qφ and target networks, D ← ∅ 3: for each env step do 4: at ∼ πθ(·|st, t− ti) 5: Take at and get st+1, Rt 6: Add (st, at, Rt, st+1) to D 7: for each gradient step do 8: Sample a batch of (τti−c:t+1, Rt, st+1) from D 9: Update Qφ via minimizing Eq. (8) (with τti−c:t) for Q-HC or Eq. (11) for Q-RNN 10: Update πθ via Eq. (7) for Q-HC or Eq. (12) for Q-RNN 11: Update the target networks 12: end for 13: end for

heading: B DISCUSSIONS AND FORMAL PROOFS
text: In this part, we provide the proofs for the statements in the main paper. In addition, we also add detailed discussions on 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, qn, rc, γ) is described by the following parameters. 1. The state and action spaces are S and A respectively. 2. The Markov transition function is p(s′|s, a) for each (s, a) ∈ S×A; the initial state distribution
is p(s0). 3. The signal interval length is distributed according to qn(·), i.e., for the i-th signal interval, its
length ni is independently drawn from qn(·).

heading: 4. The general reward function rc defines the expected reward generated for each signal interval with a overlap of maximal c steps with previous signal intervals; suppose τi = τt:t+ni =
text: (s, a)t:t+ni = ((st, at), . . . (st+n−1, at+ni−1)) is the state-action sequence during the i-th signal interval of length ni, then the expected reward for this interval is rc(τt−c:t+ni). 3
5. The reward discount factor is γ.
The PI-DRMDP is also extended naturally as follows.
Definition 4 (PI-DRMDP with General Reward Function, PI-DRMDP-c). A Past-Invariant DRMDP-c is a DRMDP-c Mc = (S,A, p, qn, rc, γ) whose reward function rc satisfies the following Past-Invariant (PI) condition: for any two trajectory segments τ1 and τ2 of the same length (no less than c), and for any two equal-length trajectory segments τ ′1 and τ ′ 2 such that the concatenated trajectories τa ◦ τ ′b are feasible under the transition dynamics p for all a, b ∈ {1, 2}, it holds that
r(τ1 ◦ τ ′1) > r(τ1 ◦ τ ′2) ⇐⇒ r(τ2 ◦ τ ′1) > r(τ2 ◦ τ ′2).
Remark 1. Definition 1 and Definition 2 are the special case (c = 0) of Definition 3 and Definition 4 respectively.
Clearly, we have the following Fact.
Fact 3. ∀c′ < c, DRMDPMc′ is also a DRMDPMc and PI-DRMDPMc′ is also a PI-DRMDPMc.
3If t < c, τt−c:0 refers to some zero token paddings which indicates the beginning of the trajectory.
Besides, under the general reward function, we extend the Q definition.
Qπ(τti−c:t+1) := E(τ,n)∼π  ∞∑ j=i γtj+1−t−1r(τtj−c:tj+1) ∣∣∣τti−c:t+1  . (10) Correspondingly, Qπ(τti−c:t+1) is optimized via
Lφ := ED [ (Rt + γQ̂φ(τtj−c:t+2)−Qφ(τti−c:t+1))2 ] , (11)
where τtj−c:t+2 = τti−c:t+1 ◦ (st+1, a′t+1) (so that j = i) if t is not the last step of τi, and τtj−c:t+2 = τti+1−c:ti+1 ◦ (sti+1 , a′ti+1) (so that j = i+ 1) otherwise.
The general policy update is also extended to ∇θJ (πθ) = ED [ ∇atQπ(τti−c:t ◦ (st, at)) ∣∣∣ πθ(st,t−ti) ∇θπθ(st, t− ti) ] . (12)
Without specification, the following proofs hold for ∀c.

heading: B.1 PROOF OF FACT 1
text: Fact 4 (Fact 1 with General Reward Function). For any distribution D with non-zero measure for any τti−c:t+1, Qπ(τti−c:t+1) is the unique fixed point of the MSE problem in Eq. (4). More specifically, when fixing Q̂φ as the corresponding Qπ , 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 π ∈ Πτ,c in DRMDPc setting. For brevity, we replace t+ 1 with t in the proof. By definition in Eq. (10), we have Qπ(τti−c:t) = qn(ni 6= t− ti|ni ≥ t− ti)(
γ ∑ st,at p(st|st−1, at−1)π(at|τti−c:t ◦ st)Qπ(τti−c:t ◦ (st, at)) ) + qn(ni = t− ti|ni ≥ t− ti)( r(τti−c:t) + γ
∑ st,at p(st|st−1, at−1)π(at|τt−c:t ◦ st)Qπ(τt−c:t ◦ (st, at))
) .
(13)
Clearly,Qπ(τti−c:t) is the solution of the following MSE problem. Noticing that we assumeQφ has tabular expression over τti−c:ts.
min φ ∑ Rt−1,st pD(τti−c:t, Rt−1, st)π(a ′ t|τtj−c:t ◦ st) ( Rt−1 + γQπ(τtj−c:t ◦ (st, a′t))−Qφ(τti−c:t) )2 Here, τtj−c:t is defined similarly as 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 Lφ(τti−c:t). As Lφ in Eq. (11) is the sum of all Lφ(τti−c:t), Qπ(τti−c:t) is a fixed point of the MSE problem.
The uniqueness is proved similar to the standard MDPs setting. For any Q̂φ, we denote the optimal solution of Eq. (4) as Qφ(τti−c:t). Since we assume tabular expression and non-zero probability of any pD(τti−c:t) Then, ∀τti−c:t, we have∣∣∣Qφ(τti−c:t)−Qπ(τti−c:t)∣∣∣ ≤ γqn(ni 6= t− ti|ni ≥ t− ti) ∑
st,at p(st|st−1, at−1)π(at|τti−c:t ◦ st)∣∣∣Q̂φ(τti−c:t+1)−Qπ(τti−c:t+1)∣∣∣+ γqn(ni = t− ti|ni ≥ t− ti)∑ st,at
p(st|st−1, at−1)π(at|τt−c:t ◦ st)∣∣∣Q̂φ(τt−c:t ◦ (st, at))−Qπ(τt−c:t ◦ (st, at))∣∣∣ ≤ γ ‖ Q̂φ −Qπ ‖∞
Last term denotes the infinite norm of the vector of residual value between Qπ and Q̂φ. Each entry corresponds to some τti−c:t feasible in the dynamic. Consequently, by the γ-concentration property, if Qφ = Q̂φ after the iteration (i.e., Qφ is a fixed point), then Qφ = Qπ . This completes the proof of uniqueness.
Remark 2. Fact 1 holds as the special case of Fact 4 when c = 0.

heading: B.2 PROOF OF FACT 2
text: Fact 5 (Fact 2 with General Reward Function). For any τti−c:t, τ ′ti−c:t and st, at, a ′ t which both τti−c:t ◦ st and τ ′ti−c:t ◦ st are feasible under the transition dynamics, ∀π ∈ Πs, we have that
Qπ(τti−c:t ◦ (st, at)) > Qπ(τti−c:t ◦ (st, a′t)) ⇐⇒ Qπ(τ ′ti−c:t ◦ (st, at)) > Q π(τ ′ti−c:t ◦ (st, a ′ t))
Proof. Since π(at|st, t − ti) ∈ Πs, for any st, at, the distribution of the remaining trajectories ρπ(τt:T , nt:T |st, at, ti) is irrelevant with τti−c:t . Thus, we have Qπ(τti−c:t ◦ (st, at)) = ∑
τt:∞,nt:∞
ρπ(τt:∞, nt:∞|st, at, ti)  ∞∑ j=i γtj+1−t−1r(τtj−c:tj+1)  = ∑ ti+1 γti+1−t−1qn(ni = ti+1 − ti|ni ≥ t− ti) ∑ τt:ti+1 ρπ(τt:ti+1 ◦ sti+1 |st, at, ti)
· r(τti−c:ti+1) + γ ∑ ati+1 π(ati+1 |sti+1 , 0)Qπ(τti+1−c:ti+1 ◦ (sti+1 , ati+1))  ∝
∑ ti+1,τt:ti+1 qn(ni = ti+1 − ti|ni ≥ t− ti)ρπ(τt:ti+1 |st, at, ti)r(τti−c:ti+1)
+K(st, at, ti)
The last term denotes the residual part which is irrelevant with τti:t. Besides, under the PI condition, the order of r(τti−c:ti+1) is invariant over τti−c:t. As a result, the order of Qπ(τti−c:t ◦ (st, a)) among a is also invariant of τti−c:t. This completes the proof.
Remark 3. Fact 2 holds as then special case of Fact 5 when c = 0.

heading: B.3 PROOF OF PROPOSITION 1
text: Proposition 2 (Proposition 1 with General Reward Function). For any policy πk ∈ Πs, the policy iteration w.r.t. Qπk (Eq. (10)) produces policy πk+1 ∈ Πs such that ∀τti−c:t+1, it holds that
Qπk+1(τti−c:t+1) ≥ Qπk(τti−c:t+1),
which implies that J (πk+1) ≥ J (πk).
Proof. Under Fact 5, the new policy iteration is defined formally as following
πk+1(at|st, t− ti) = arg max at Qπk(τt−c:t ◦ (st, at))
where τt−c:t is any trajectory segments feasible for st under the dynamics. If there are multiple maximums, we can assign arbitrary probability among these ats. Following Eq. (13), we have
∀τti−c:t Qπk(τti−c:t) = qn(ni 6= t− ti|ni ≥ t− ti)(
γ ∑ st,at p(st|st−1, at−1)πk(at|st, t− ti)Qπk(τti−c:t ◦ (st, at)) ) qn(ni = t− ti|ni ≥ t− ti)(
r(τti−c:t) + γ ∑ st,at p(st|st−1, at−1)πk(at|st, 0)Qπk(τt−c:t ◦ (st, at)) ) ≤ qn(ni 6= t− ti|ni ≥ t− ti)(
γ ∑ st,at p(st|st−1, at−1)πk+1(at|st, t− ti)Qπk(τti−c:t ◦ (st, at))
) +
qn(ni = t− ti|ni ≥ t− ti)( r(τti−c:t) + γ ∑ st,at p(st|st−1, at−1)πk+1(at|st, 0)Qπk(τt−c:t ◦ (st, at)) ) (14)
Then, we can iteratively extend each Qπk term in Eq. (14) and get ∀τti−c:t Qπk(τti−c:t) ≤ Qπk+1(τti−c:t)
Noticing that the inequality is strict if any step of the inequality in the iterations is strict. Furthermore, by definition, J (π) = ∑ s0,a0 p(s0)π(a0|s0, 0)Qπ(s0, a0)4, we have
J (πk) ≤ ∑ s0,a0 p(s0)πk+1(a0|s0, 0)Qπk(s0, a0)
≤ ∑ s0,a0 p(s0)πk+1(a0|s0, 0)Qπk+1(s0, a0)
≤ J (πk+1)
This completes the proof.
Remark 4. Proposition 1 holds as the special case of Proposition 2 when c = 0.

heading: B.4 DISCUSSION OF OPTIMAL POLICIES
text: To begin with, we consider the general DRMDP-c. Similarly, we denote Πτ,c = {π(at|τti−c:t ◦st)} as the extension of Πτ (c = 0). Then, we prove the following Fact.
Fact 6. For any DRMDP-c, there exists an optimal policy π∗ ∈ Πτ,c. However, there exists some DRMDP-0 (so as DRMDP-c ∀c) such that all of its optimal policies π∗ /∈ Πs.
In general, any policy belongs to the class Πall = {π(at|τ0:t ◦ st, n0:t)}. Namely, the agent’s policy can only base on all the information it has experienced till step t. Besides, in DRMDP-c, the expected discounted cumulative reward is
J (π) = ∑ τ,n ρπ(τ, n)R(τ, n).
where ρπ(τ, n) denotes the probability that trajectory (τ, n) is generated under policy π ∈ Πall. To begin with, we first prove the following Lemma.
Lemma 1. For any policy π ∈ Πall which is the optimal, i.e, maximize J (π), we consider two segments of trajectories (τa0:ta , n a 0:ta) and (τ b 0:tb , n b 0:tb) which satisfies that τ a tai−c:ta = τ b tbi−c:tb and tb ≥ ta. Besides, we also consider ∀t ≥ tb, t′ = t−tb+ta and τ b0:t = τ b0:tb ◦τtb:t, n b 0:t = n b 0:tb ◦ntb:t
4Here, we omit specifying the c-step padding.
and state s( ′) t feasible in the dynamic, we switch the policy π to π
′ w.r.t these two trajectories as following
π′(·|τ b0:t ◦ st, nb0:t) = π(·|τa0:ta ◦ τtb:t ◦ st′ , na0:ta ◦ ntb:t). Then, π′ ∈ Πall and J (π′) = J (π).
Proof. Obviously, π′ is well-defined and π′ ∈ Πall as the transition is Markovian. Noticing that J (π′) = ∑ τ,n ρπ ′ (τ, n)R(τ, n)
= ∑
(τ,n):(τb 0:tb ,nb 0:tb )6⊂(τ,n)
ρπ ′ (τ, n)R(τ, n)
︸ ︷︷ ︸ denoted by Jπ′ (τb
0:tb ,nb 0:tb )
+ρπ ′ (τ b0:tb , n b 0:tb)
∑ (τ,n):(τb
0:tb ,nb 0:tb )⊂(τ,n)
ρπ ′ (τ, n|τ b0:tb , n b 0:tb)R(τ, n)
= Jπ ′ (τ b0:tb , n b 0:tb) + ρ π′(τ b0:tb , n b 0:tb) ∑ (τ,n):(τb
0:tb ,nb 0:tb )⊂(τ,n)
ρπ ′ (τ, n|τ b0:tb , n b 0:tb)  ∞∑ j=1 γtj+1−1r(τtj−c:tj+1)  = Jπ
′ (τ b0:tb , n b 0:tb) + ρ π′(τ b0:tb , n b 0:tb) i(tb)−1∑ j=1 γtj+1−1r(τtj−c:tj+1)  + ρπ
′ (τ b0:tb , n b 0:tb)
( γt b−1Qπ
′ (τ btbi−c:tb
) ) .
We denote (τ0:t, n0:t) ⊂ (τ, n) if the former is the trajectory prefix of the latter. Qπ ′
is defined in Eq. (3) except that π′ ∈ Πall in this case. By the definition of π′ and the condition that π is optimal, we have Qπ′(τ b
tbi−c:tb ) = Qπ(τatai−c:ta) = Q π(τ b tbi−c:tb
) and Jπ ′ (τ b0:tb , n b 0:tb) = J π(τ b0:tb , n b 0:tb).
Thus, we have
J (π′) = Jπ ′ (τ b0:tb , n b 0:tb) + ρ π′(τ b0:tb , n b 0:tb) i(tb)−1∑ j=1 γtj+1−1r(τtj−c:tj+1)  + ρπ
′ (τ b0:tb , n b 0:tb) ( γt b−1Qπ(τ btbi−c:tb) ) = Jπ(τ b0:tb , n b 0:tb) + ρ π(τ b0:tb , n b 0:tb)
∑ (τ,n):(τb
0:tb ,nb 0:tb )⊂(τ,n)
ρπ(τ, n|τ b0:tb , n b 0:tb)
 ∞∑ j=1 γtj+1−1r(τtj−c:tj+1)  = J (π).
We refer it as a policy switch on π w.r.t (τ b0:tb , n b 0:tb) and (τ a 0:ta , n a 0:ta) to π′. Then, we prove Fact 6 as follows.
Proof of Fact 6. For simplicity, we denote Πtτ,c ⊂ Πall as the policy space that if π ∈ Πtτ,c and ∀ta, tb ≤ t then ∀(τa0:ta , na0:ta), (τ b0:tb , n b 0:tb) which τ a tai−c:ta = τ b tbi−c:tb
, π(·|τa0:ta ◦ sta , na0:ta) = π(·|τ b0:tb ◦ stb , n b 0:tb) for all s feasible. Clearly, Π 0 τ,c = Πall and Π ∞ τ,c = Πτ,c. Then, starting from some optimal policy π0 ∈ Π0τ,c, we utilize the policy switch operation to shift it into Πτ .
Suppose that πt−1 ∈ Πt−1τ,c , we consider the following two steps of operations. 1. Step 1. ∀(τ0:t, n0:t) that ∃(τ ′0:t′ , n′t′i:t′) which t ′ < t and τti−c:t = τ ′ t′i−c:t′
(randomly choose one if multiple segments exist), we conduct a policy switch on πt w.r.t (τ0:t, n0:t) and (τ0:t′ , n0:t′). We denote the policy after all these policy switches as π′t−1. 2. Step 2. We denote Sπt−1(τ̃ti−c:t) = {(τ0:t, n0:t)|τti−c:t = τ̃ti−c:t and @(τ ′0:t′ , n′0:t′), t′ < t which τ ′t′i−c:t′ = τ̃ti−c:t}. For each Sπt−1(τ̃ti−c:t), we randomly choose some (τ 0 0:t, n 0 0:t) ∈
Sπt−1(τ̃ti−c:t) and conduct policy switch on π ′ t−1 w.r.t all (τ, n) ∈ Sπt−1(τ̃ti−c:t) and (τ00:t, n 0 0:t). Finally, we get πt.
Since πt−1 ∈ Πt−1τ,c , it is straightforward to check that πt ∈ Πtτ,c. Besides, as all operations are policy switches, πt is optimal if πt−1 is optimal. Consequently, by induction from the optimal policy π0, we can prove that ∃π∞ ∈ Πτ,c which is optimal. For the second statement, we consider the following DRMDP-0.
A0
A1
B C
a0
a1
b0, b1
whose n = 2. a0, a1 denote two actions from A0, A1 to B respectively and b0, b1 are two actions from B to C. The reward is defined as r(ai, bj) = i⊕j,∀(i, j) ∈ {0, 1}. The initial state distribution is p(A0) = p(A1) = 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 B to C. This illustrates that π∗ may not be in Πs.
Consequently, learning optimal policies is relatively hard in DRMDP due to the large policy class to search. In our work on PI-DRMDP, we only focus on the optimization in Πs. However, in some bizarre cases, the optimal policy π∗ 6∈ Πs. For example, consider the following PI-DRMDP-0 where n if fixed as 2.
Al
B
C+
C− T
Ab
a10
a0.1
b+1
b−1 τ
The initial state is uniformly chosen from {Ab, Al} and C+, T are terminal states. The reward function for the first interval is r(ai, bj) = i× j (Past-Invariant) and r(τ) = 5. The optimal policy at B should be π(·|Ab/l, B) = b+1/−1 which is not in Πs. 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 or even DRMDP-c as future work. As mentioned above, most real world reward functions still satisfy that the optimal policy belongs to Πs. This makes our discussion in Πs still practically meaningful. Additionally, we put forward a sub-class of PI-DRMDP-c which guarantees that there exists some optimal policy π∗ ∈ Πs. Definition 5 (Strong PI-DRMDP-c). A Strong Past-Invariant DRMDP-c is a PI-DRMDP-c whose reward r satisfies a stronger condition than the Past-Invariant (PI) condition: ∀ trajectory segments τ1 and τ2 of the same length (no less than c), and for any two equal-length trajectory segments τ ′1 and τ ′ 2 such that the concatenated trajectories τa ◦ τ ′b are feasible under the transition dynamics p for all a, b ∈ {1, 2}, it holds that
r(τ1 ◦ τ ′1)− r(τ1 ◦ τ ′2) = r(τ2 ◦ τ ′1)− r(τ2 ◦ τ ′2).
Namely, the discrepancies are invariant of the past history τ1,2 in addition to only the order. A straightforward example is the weighted linear sum of per-step rewards
r(τt−c:t+n) = t+n−1∑ i=t−c wi−tr(si, ai), 0 ≤ wi−t ≤ 1
The weight mimics the scenario that the per-step reward for the i-tth step in the reward interval will be lost with some probability wi−t. Furthermore, Strong PI-DRMDP-c satisfies
Fact 7. For any Strong PI-DRMDP-c, there exists some optimal policy π∗ ∈ Πs. Remark 5. Table 1 summarizes the case when c = 0.

heading: B.5 DISCUSSION OF OFF-POLICY BIAS
text: This following example illustrates the off-policy bias concretely. We consider the case for a sumform PI-DRMDP-0.
The signal interval length is fixed as n + 1 and any trajectory ends after one interval. The reward function is in sum-form over r(s, a). When learning the critic (tabular expression) via Eq. (1), the Q-values at the last step n are 5
Qφ(sn, an) = ∑ τ0:n ρβ(τ0:n|sn, an)r(τ1)
= ∑ τ0:n ρβ(τ0:n|sn, an) ( n−1∑ t=0 r(τt:t+1) ) ︸ ︷︷ ︸
Q̃β(sn,an)
+r(sn, an) (15)
In Eq. (15), ρβ(τ0:n|sn, an) denotes the probability distribution of τ0:n collected under the policy sequence β conditioning on that τn:n+1 = (sn, an). Besides, we denote ρβk(τ0:n|sn) as the distribution under policy βk conditioning on sn at the last step. Obviously, ρβk is independent of last step’s action an as π ∈ Πs. By Bayes rule, we have the following relation
ρβ(τ0:n|sn, an) = ∑K k=1 ρ
βk(τ0:n|sn)βk(an|sn)∑K k=1 βk(an|sn)
(16)
In other word, ρβ(·|sn, an) is a weighted sum of {ρβk(·|sn)}. The weights are different between ans since the behavior policies {βk} are different. Consequently, Q̃β(sn, an) will also vary between ans and it is hard to be quantified in practice. Unfortunately, we may want Qφ(sn, an) ∝ r(sn, an) for unbiased credit assignment the actions at the last step. Thus, updating the policy with approximated Qφ(sn, an) will suffer from the off-policy bias term Q̃β(sn, an).

heading: B.6 DISCUSSION OF FIXED POINT BIAS
text: Even with on-policy samples in D, critic learning via Eq. (1) can still be erroneous. We formally state the observation via a toy sum-form PI-DRMDP-0.
A
B
C C0
D D0
a0
a1
c
d b
5Without loss of generality, the discussion is simplified by assuming sn will only appear at the end of a reward interval.
where for state B,C,D, there is only one action. The agent only needs to decide among a0, a1 at state A. n is fixed as 2 and the initial state distribution p0(A) = p0(B) = 0.5. The reward has sum-form over the following per-step reward
r(C, c) = r(D, d) = 0
r(A, a0) = 0.01, r(A, a1) = 1
r(B, b) = −1
Fact 8. For the above PI-DRMDP-0 and any initialization of the policy, value evaluation (Qφ(st, at) in tabular form) via Eq. (1) with on-policy data and policy iteration w.r.t Qφ(st, at) will converge to a sub-optimal policy with J (π) = −0.495γ. In contrast, our algorithm can achieve the optimal policy with J (π) = 0.
Proof. For any policy π, we denote p = π(a1|A). Then, if we minimize Eq. (1) with on-policy samples, we will have Qφ(C, c) = 0.01, Qφ(A, a0) = 0.01γ. Besides, as initial state distribution are uniform, we have
Qφ(D, d) = 1
2 (p− 1), Qφ(A, a1) =
1 2 γ(p− 1)
Since Qφ(A, a1) < Qφ(A, a0) for any p, policy iteration will converges to a sub-optimal policy that π(a0|A) = 1.The sub-optimal policy has J (π) = −0.495γ. Noticing that this holds even if the initial policy is already the optimal.
For our algorithm, we have
Qφ(A, a1) = γQφ(A, a0, D, d) = γ
For any γ > 0 and any p, a single policy iteration will have the optimal policy with but the optimal has J (π∗) = 0.

heading: B.7 DISCUSSION OF DRMDP DEFINITION
text: In this section, we compare DRMDPs with other related definitions about MDP delays. To be specific, we provide brief discussions on 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 are non-Marvian. Simply solving DRMDPs (or PI-DRMDPs) as 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 set. Contrarily, in DRMDP, the length of the signal interval (comparing to 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 a low-level option policy over actions and a high-level control policy over options. However, DRMDPs are formulated for general sequential decision making problems.
Delay MDP: Delay MDPs (Walsh et al., 2009; Derman et al., 2021) are used to characterize observation delay and action delay. For example, the observation inputs to the controller (e.g., a 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 coupled with the corresponding state-action pair, i.e., when the delay is a constant m, the transition (st, at, rt, st+1)a observed at the remote agent, is also the transition the controller received at step t+m, i.e., (st+m, at+m, rt+m, st+m+1)c.
In DRMDP, there is no observation-delay or action-delay and there is no per-step rewards coupled with each state-action pair.

heading: C ADDITIONAL RESULTS

heading: C.1 DESIGN EVALUATION
text: Here, we show more experiments omitted in Section 4.1. To begin with, we compare different HC-decomposition algorithms (Q-HC) with Q-RNN and vanilla SAC on several sum-form PIDRMDP tasks with different signal interval length distributions (qn). The results are consistent with our discussions in Section 4.1, despite of the lengths and the distributions.
Then, we test the HC-decomposition on non sum-form PI-DRMDP taks based on OpenAI Gym. Two non sum-form tasks are included: Max and Square. For Max,
r(τt:t+n) = 10× max i∈[t:t+n] {r(si, ai)}
Here, r(si, ai) is the standard per-step reward in each task. For Square, we denote ravg(τt:t+n) = 1 n ∑ i∈[t:t+n] r(si, ai) and the reward is defined as follows.
r(τt:t+n) = 4× { ravg(τt:t+n) |ravg(τt:t+n)| < 1. sign(ravg(τt:t+n))× r2avg(τt:t+n) |ravg(τt:t+n)| ≥ 1.
Noticing that these two tasks are still PI-DRMDP. The results are shown in Figure 5. Clearly,Q-HC algorithms outperform Q-RNN and vanilla SAC on all tasks.
Moreover, we also implement TD3-based Q-HC-Singleton, Q-HC-Pairwise-1 and compare them with the vanilla TD3 and TD3-based Q-RNN. The results still match our analysis of HCdecomposition in Section 3.2. However, we find that SAC-based variants consistently outperform
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.

heading: C.2 ABLATION STUDY
text: In Figure 7, we show the ablation study on the regulation term Lreg on all 4 tasks. We observe that in HalfCheetah-v2 and Ant-v2, the regulation plays an important role for the final performance while the regulation is 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 Q-HC-Singleton, regulation is less helpful. We suspect that the simple structure itself imposes implicit regulation during the learning.
Furthermore, we ablate the HC-decomposition in Q-HC-Singleton and Q-HC-Pairwise-1. Namely, we implement Q-Singleton and Q-Pairwise-1 with the similar architecture but not with HCdecomposition. For Q-Singleton, we have
Q(τti:t+1) = ∑
j∈[ti:t+1]
bφ(τj:j+1)
and for Q-Pairwise-1, we have Q(τti:t+1) = ∑
j∈[ti:t]
c1φ(τj:j+1 ◦ τj+1:j+2) + ∑
j∈[ti:t+1]
bφ(τj:j+1)
In Figure 8, we observe that these two ablations perform sluggishly and even worse than Q-RNN (without any decomposition). This suggests the necessity of HC-decomposition for PI-DRMDP, i.e., the separated history part (H) and the current part (C), as the transition of the environment is still Markovian. Without the separation, a simple decomposition fails to assign the adequate credit to the last step action in τti:t+1, thus results in errorneous policy update.

heading: C.3 COMPARATIVE EVALUATION
text: We show detailed results of our algorithms Q-HC and previous baselines on sum-form PIDRMDP tasks with general reward function. Please refer to Appendix B and Appendix A for
detailed discussions. For environments with maximal c overlapping steps, the reward function is formally defined as follows.
rc(τti−c:ti+ni) = ∑
i∈[ti−c:ti+ni−c]
r(si, ai)
where r(si, ai) is the standard per-step reward. If i < 0, then r(si, ai) = 0. In this definition, the reward is delayed by c steps and thus the signal intervals are overlapped. In Figure 9, we show the relative average performance (over Reach-v2, Hopper-v2, HalfCheetah-v2, Walker2d-v2, and Ant-v2) of each algorithm w.r.t the 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 c in Figure 10.

heading: D EXPERIMENT DETAILS
text: D.1 IMPLEMENTATION DETAILS OF OUR ALGORITHM
We re-implement SAC based on OpenAI baselines (Dhariwal et al., 2017). The corresponding hyperparameters are shown in Table 3. We use a smaller batch size due to limited computation power.
To convince that the superiority of our algorithms (Q-HC-RNN, Q-HC-Pairwise-K, Q-HCSingleton) results from the efficient approximation framework (Section 3.2) and the consistency
with the theoretical analysis (Section 3.1), rather than from a better choice of hyper-parameters, we did not tune any hyper-parameter shared with SAC (i.e., in Table 3).
The architecture of different Hφs are shown as follows. For the regularization coefficient λ, we search λ in {0.0, 0.05, 0.5, 5.0} for each implementation of Q-HC. λ is fixed for all tasks including the toy example.
- Q-HC-RNN. Each step’s input τt:t+1 is first passed through a fully connected network with 48 hidden units and then fed into the GRU with a 48-unit hidden state. Hφ(τti:t) is the output of the GRU at the corresponding step. We use λ = 5.0.
- Q-HC-Pairwise-1. Both c0φ and c1φ are two-layer MLPs with 64 hidden units each. λ = 0.5. - Q-HC-Pairwise-3. All ciφ, i = 0, 1, 2, 3 are two-layer MLP with 48 hidden units each. λ = 5.0. - Q-HC-Singleton. bφ is a two-layer MLPs with 64 hidden units each. λ = 0.05.
As suggested by the theoretical analysis, we augment the normalized t− ti to the state input.
All high dimensional experiments are based on OpenAI 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 hyper-parameters as in Table 3. The only exception is the architecture of the GRU critic. Similar to Q-HC-RNN, each state-action pair is first passed through a fully connected layer with 128 hidden units and ReLU activation. Then it is fed into the GRU network with 128-unit hidden state. The Qφ(τti:t+1) is the output of the GRU network at the corresponding 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 is still 3 × 10−4 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.

heading: D.3 DETAILS FOR TOY EXAMPLE
text: Point Reach. As illustrated in Figure 4, the Point Reach PI-DRMDP task consists of a 100x100 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 (x, y) coordinate only. The action space is its moving speed (vx, vy) ∈ [−1, 1]2 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 to the agent as follows.
The grid is divided into 10 sub-areas of 10x100 along the x-axis. We denote the sub-areas (highlighted by one color each in Figure 4) as Si, i = [0 : 10] form left to right. In each sub-area Si, it provides an extra reward and the reward ri indicates how far is the sub-area to the target (i.e., ri = i). Clearly, the bigger the reward is, the closer the sub-area is to the target area. Besides, reward interval length is fixed as 20 and the point agent is rewarded with the maximal ri it has visited in the interval together with a bonus after reaching the target and a punishment for not reaching. Namely,
r(τt:t+n) = max j∈[t:t+n] 9∑ i=0 ri · 1(sj:j+1 ∈ Si) + 10 · (1(reach target)− 1)
The task ends once the agent reach the target area 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 4 show the mean and half of a standard deviation of 10 seeds. All curves are smoothed equally for clarity.
Heatmap. In Figure 4 right, the heatmap visualizes the value of bφ(st, at) on the whole grid. We select the bφs after the training has converged to the optimal policy. To be specific of the visualization, for each of the 10x10 cells on the grid, st in bφ(st, at) is selected as the center of the cell and at is sampled from π(·|st, 0). Additionally, in Figure 11, we visualize bφ(st, at) similarly of Q-HC-Singleton without Lreg. Clearly, Figure 11 shows the similar pattern as Figure 4 right.

heading: D.4 DETAILS FOR VARIANCE ESTIMATION
text: The experiment in Figure 1 is conducted in the following manner. First, we train a policy πθ with Q-HC-Singleton 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 the GRU architecture (i.e.,Q-RNN) and the other usesQ-HC-Singleton structure. Most importantly, since these two critics are not used for policy updates, there is no overestimation bias (Fujimoto et al., 2018). Thus, instead of using the CDQ method Fujimoto et al. (2018), these two critics are trained via the method in DDPG (Silver et al., 2014). With a mini-batch from D, we compute the gradients on the policy’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.
Then, we compute the sample variance of the gradient on each parameter θi in the policy network. The statistics (y-axis in Figure 1) 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.

heading: D.5 DETAILS FOR RELATIVE AVERAGE PERFORMANCE
text: Here, we formally introduce the Relative Average Performance (RAP) metric in Table 2, Figure 9, 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 1M steps (trained on dense reward environment). The only exception is Reach-v2, in which the episodic returns are added by 50 to before the normalization.

Review summaries:
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. 

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.

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.