A Long $N$-step Surrogate Stage Reward for Deep Reinforcement Learning
Authors: Junmin Zhong
Ruofan Wu
Jennie Si
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep reinforcement learning
Reward Estimation

Abstract: We introduce a new stage reward estimator  named the long $N$-step surrogate stage (LNSS) reward for deep reinforcement learning (RL). It aims at mitigating the high variance problem, which has shown impeding successful convergence of learning, hurting task performance, and hindering applications of deep RL in continuous control problems. In this paper we show that LNSS, which utilizes a long reward trajectory of  rewards of future steps, provides consistent performance improvement measured by average reward, convergence speed, learning success rate,and variance reduction in $Q$ values and rewards.  Our evaluations are based on a variety of environments in DeepMind Control Suite and OpenAI Gym  by using  LNSS in baseline deep RL algorithms such as DDPG, D4PG, and TD3. We show  that LNSS reward has enabled good results that have been challenging to obtain by deep RL previously. Our analysis also shows that  LNSS exponentially reduces the upper bound on the variances of $Q$ values from respective single-step methods.

A Long N -tse Surrogate Stage Reward for Deep Reinforcement Learning
Junmin Zhong Arizona State University
Ruofan Wu Arizona State University
Jennie Si Arizona State University
Abstract
We introduce new stage reward estimator named the long N-step surrogate stage (LNSS) reward for deep reinforcement learning (RL). It aims at mitigating the high variance problem, which has shown impeding successful convergence of learning, hurting task performance, and hindering applications of deep RL in continuous control problems. In this paper we show that LNSS, which utilizes a long reward trajectory future steps, provides consistent performance improvement measured by average reward, convergence speed, learning success rate, and variance reduction in Q values and rewards. Our evaluations are based on a variety of environments DeepMind Control Suite and OpenAl Gym by using LNSS piggybacked on baseline deep RL algorithms such as DDPG, D4PG, and TD3. We show that LNSS reward has enabled good results that have been challenging to obtain by deep RL previously. Our analysis also shows that LNSS exponentially reduces the upper bound the variances of values from respective single-step methods.
1 Introduction
Reinforcement learning (RL) shows great promise as a theory of learning in complex dynamic tasks 21 For continuous control problems involving high-dimensional states and control spaces, several deep reinforcement learning (DRL) algorithms, such as deep deterministic policy gradient (DDPG) B. proximal policy optimization (PPO) [4], Soft actor critic (SAC) (5), D4PG [6] and twin delayed DDPG (TD3) 77, have demonstrated their great potential.
However, the high variance problem g 9 in DRL, still poses great challenges for it to be effective in solving complex contentious control problems. and error nature of reinforcement learning, which causes low data efficiency, slow learning, instability of learning and poor task performance [1O] [T] On the other hand, high variances are often caused by several factors, such as variances in value estimation 122, variances resulting from different random seeds [10), and variances due to noisy stochastic reward or corrupted sparse reward [3)..
one hand, this problem is intrinsic to the trial
Different approaches have been proposed to address the high variance problem, from the original
TD(A) algorithm to ((a) [14] as generalization of TD(A) [15. Rollout methods [16] 17
[8] have
enabled the success of some the most important milestone cases such as Backgammon 17 and
AlphaGoo [19] in machine learning history. Although these algorithms has been demonstrated in discrete state and control problems, variants of rollout are believed to be effective also in continuous control tasks. Modern DRL algorithms such Rainbow (20) integrate n-step learning top of DQN and results in speed-up in learning and an improvement of the final performance on Atari 2600 games. D4PG [6] uses the same n-step methods update target values, and have been shown effective in continuous control tasks. PPO [4] uses a truncated version of generalized advantage estimation (GAE) to update policy which reduces policy variance [1]. However these methods do
"Correspondng author: si @asuueeuu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

not explicitly account for noisy rewards where such uncertainties have been reported to degrade the model/controller performance [22]
In this paper, we propose a new algorithm, namely the long N-step surrogate stage (LNSS) reward estimator. LNSS aims at providing variance reduction for DRI. methods in continuous control problems, even under noisy reward signals or corrupted sparse reward. LNSS is simple, and can be easily piggybacked on DRL algorithms. is based on surrogate reward r' obtained from a trajectory of rewards of future "N-step"s. In turn, r' is used in Q value update where the target function is then of the same form as that in single-step TD methods. Using a long " "N-step"s of the reward sequence containing environment information, it is expected to be more advantageous to learning than using a short trajectory of n-step of the reward sequence.
We show theoretically that the LNSS method exponentially reduces the upper bound on the variance of Q value from respective single-step method. We then conduct extensive experiments in selected environments in DMC and GYM where most current DRL. algorithms such as DDPG, D4PG, and TD3 that typically struggle to obtain good results (23). We consider uniform random noises of different magnitudes to show how LNSS can benefit a variety of DRL algorithms while the performances of other methods degrade significantly. We further show how LNSS can still be effective in environments where only sparse rewards are available.
Contributions. 1) We introduce new, simple yet effective surrogate reward r that interpolates between the single-step TD methods and Monte-Carlo (MC) methods [15), to trade off the strengths from the extremes. 2) We theoretically show the proposed method helps reduce the upper bound on the variance of Q value with a long trajectory of rewards of future "Nsstpp"s. 3) Extensive experi- ments DMC and GYM benchmarks show that LNSS robustly benefits the learning performance of a variety of DRL algorithms even under reward noise or sparse reward. Mainly, the LNSS consistently reduces variances in the learned value function and achieves robust results from different random seeds in several different types of continuous control problems. Please check our code
2 Related Work
The "n-step" methods. Here, as in the literature, n-step methods refer to those involving a trajectory of rewards of multiple future steps in DRL algorithms for speeding up learning and reducing variance
24
25 6). They usually proceed as follows. First, collect n-step returns form discounted sum
of rewards (26
27). Then, perform n-step return backup to update the value function [5]. It was
empirically suggested that n-step methods perform better than single-step methods since n-step returns propagate rewards to relevant acte-nction pairs more efficiently (4]25).
Using longer trajectories with larger is expected to improve learning performance 28 However, to date, the st-tep DRL methods have only been demonstrated by using relatively small n. Rainbow 3 as the
20 uses 3, 5 to evaluate performance of 57 Atari 2600 games and reported best-performing reward trajectory length. D4PG 6 uses n = 1,5 to evaluate a variety of continuous control tasks in DMC and results show that 5 performs uniformly better than others. However, 3 and 5 are relative small for complex tasks which usually have a maximum of 1000 steps in an episode.
There are potentially two reasons that prevent n-step methods from using larger length n. One is that the longer the n-step return, the larger reward scale that can cause saturation and inefficiency in learning for most DRL algorithms
[10]. The second reason is that the longer the n--tep return, the smaller discount factor (7")) in n--tep backup [15. Based on previous studies 29), variations the scale of the discount factor directly causes uncertainty to the RL. performance. New algorithmic ideas are needed for DRL algorithms to benefit from longer reward bootstrapping.
Reward estimation. Reward estimation aims at reducing sample complexity and learning variance as reward variances may be introduced from using random seeds in training (9, from sensor noises in real-world applications [ and from corrupted sparse rewards (13). Several approaches have been proposed for reward estimation. Small backups [30], instead of directly using an actual reward, use multi-step imaginary rollouts as predicted reward. Model-basee policy search with Bayesian neural network (31) finds expected cost by averaging over multiple virtual rollout. The X-prediction (32 uses an extra network to predict reward and the training of which may introduce additional variance. Model-based value expansion [3 uses an imaginary reward from a model to estimate the values of state value functions. To reduce learning variance resulted from noisy rewards, regression reward

---

estimator [13 expects the estimated reward to reduce the variance propagated to the value function. Unbiased reward estimator [22] estimates surrogate reward by learning reward confusion matrix which estimates true reward from noisy reward. However, all these estimation methods require extra models (either in the form of neural networks, environment transitions, or reward noise model), which imposes overhead on learning and introduces estimation error. Additionally, how to effectively and efficiently integrate these reward estimates into DRL algorithms is not clear, or at least not straightforward.
LNSS. In contrast, our method does not introduce any new hyper parameters into learning as we still use the same form of reward signals but only to longer horizon of "N-step"s. s. The LNSS method can be piggybacked on any DRL algorithms directly. Comparing to n-step methods, by using our surrogate reward r' to perform single-step updates, we can benefit from n-step returns without changing the reward scale. This frees LNSS from a limited reward horizon to a much longer length N.
Selecting DRL algorithms. First, note that few existing n-step methods have been successfully applied to different DRL algorithms with consistent learning variance reduction. We selected DDPG, D4PG, and TD3 base DRL algorithms, with which our LNSS is be piggybacked on for the following considerations. Among all DMC based benchmark results [23]. distributional method D4PG (6] outperforms other DRL algorithms such as DDPG 33, and TD3
[5]. On the other hand, TD3, DDPG have relatively good performance in simple tasks such as walker but struggled to achieve good results in harder DMC tasks such as humanoid-ward chosen DRL. algorithms to systematically test the idea of LNSS piggybacked on promising DRL algorithms in complex tasks, even in noisy reward environments.
and fish-swim. We thus use the three
3 Background
Reinforcement Learning. We consider reinforcement learning agent interacts with its environment in discrete time. At each time step k. the agent observes a state 8₁. and select an action ag E A based on its policy S -> A. namely, dg x (sx), and receives a scalar reward r(sk, ax) E R (use тk as short hand notation).
Evaluation of policy π is performed using the expected return after taking an action ag based on state sg following the policy x:
Q" ax) = E ElR (ok, an.
where Rs
Krtt
(I)
t=k
Sk p 8k-1: ax-1).
0k = π (sx)
with 0 < < 1. The two common approaches (single-step and n-step) to update the Q value for policy æ are as follows.
Single-step RL. Algorithms. RL algorithms rely on using TD error or residual of the Bellman equation update the state-action value for policy æ, as described below,
QF (Sk, an) = + 7Q= (sK+1, 01++).
This equation provides the basis for single-step RL methods. is also known as a backup operation since it transfers information from one step ahead back to the current step.
"n-step" RL algorithms. Using n-step rewards for faster reward propagation RL has long been investigated [26] [4] 6 20). In n-step methods, the value function Q" (Sk, az)) update using an n-step return is based on the following.
kii-1
QF (sk, aR)
Σ g + 2== (sk+nn ak+n). t=
The n-step return is expected to help agents learn more efficiently by affecting multiple state action pairs within one update and gain information over the n-step horizon.
3

---

More details on specific modern DRL algorithms such as the single-step methods (DDPG and TD3) and the n-step methods (D4PG and PPO) can be found in Appendix D
4 Long N -tstep Surrogate Stage (LNSS) Reward
In this section, we introduce LNSS based on infinite horizon discounted reward formula- tion of reinforcement learning. Given a reward trajectory of N steps from time step k; let G(sk (kk---1) E R (use G₁ short hand notation) denote the discounted NN-sepp re- ward, i.c.
1+--11
GN
Σ
TT
where 7, is the ith stage reward and is from & to k N - 1. In LNSS, we introduce r/. surrogate stage reward place of r in Equation N N-step reward sequence, namely
To determine r/A. we treat it as weighted average of the
Lick 7 re
-+N-1 WN-1 ym
(5)
We then propose the surrogate stage reward r/ to be
Gb 7 7-1 r/ = 7.N -
(6)
This surrogate stage reward ry as formulated in Equation (6) relies on a discounted reward of an N-step horizon, from time step k to step (k + N 1)), from the stored experiences into temporary replay buffer ID' For a training episode of T steps [0, 1, 2..., T". the ID' is moving window of size N from the initial state so until the terminal state sr. As result, when there sufficient number (i.e., .N of reward samples, LNSS computes the surrogate reward rí from below,
k+N-1 Σ
Kk k= 7 N
rr-
Note that, when the reward is estimated at the beginning or toward the end of a long trial, less than N reward samples are available for estimating rk- A simple adjustment given in Appendix
Once r is obtained, r/ and state action pairs (sk, aks 9K41) will append as a new transition (sk; Ok. Th sk+1) stored into the memory buffer D.
Note that many DRL algorithms sample collection. We use the same technique to speed up sampling experiences. Then a DRL algorithm is ready to update the Q value and the respective policy based on mini-batch data from the memory buffer. In general form, we have
20 6 use distributed learning procedure to accelerate experience
Qiti ax) = r/e ((
(8)
(sk) arg max (3s,)aa)) az
where is iteration number. Putting the above two equations together, we have
Qi+ Qi+i ax) rkk + max Qi(5k+1; (141)
Remark 1. 1) Different from n-step methods, in our LNSS, N is the number of steps for accumulating rewards in Equation 0 We still perform a single-step update in Equation (8). This allows to prevent steep discounts of y in n-step backup when using longer n-step returns. As a result, LNSS can effectively use large N at scale of 100 while D4PG (Barth-Mant et al., 2018) uses n at scale of 5 steps, and the same for Rainbow (Hessel et al., 2018).
2) LNSS can also be effective in sparse reward environment. With longer reward trajectory of N future steps, LNSS continuously provides reward estimate as feedback to the agent by assigning credits progressively backward from the time of achieving the desired states. That is to say that LNSS

---

has turned sparse reward into a dense reward. Thus, this helps the agent effectively and efficiently learn the task. However, the single-step method does not have the ability provide any guidance or feedback to the learning agent until reaching goal.
3) The Q value for policy π due LNSS differ from that in Equation 1 The former aims to maximize the sum of sequence of surrogate rewards which are the weighted averages of the sequence of N-steps of the original rewards. As such, goal-related information can be progressively propagated back from the goal state to the current state. This prevents the agent from getting trapped from reaching its intended goal and thus being stuck in an undesirable set of states due a lack of feedback.
5 Variance Analysis
We now analyze the behavior of an actor-critic RL and our LNSS actor-critic RL. We consider the infinite horizon discounted reward formulation of RL (with 0 < 7 < 1). Specifically, we show that the upper bound on the variance in Q value due to LNSS differs by an exponential factor from that of single step actor-critic RL (AC). As this upper bound reduces exponentially as N increases, suggests significant variance reduction by using LNSS from using single step reward.
We first represent the Q values using single step reward F& in Equation 2 and using surrogate reward r/e from LNSS in Equation (8) respectively as follows,
Var [Q++1 ($k, a = Var [r*] + Var [7Q( ax+1)) + 2Cov [r QQ ak+1)].
(10)
Var [Q++1 (8k, a3)] = Var [rk] Var [>QQ [k+1)] + 2Cov [rk. Q
(11)
in Equation (8 be the i-th approximated return to solve Equation (T. We then have the following.
Lemma Assume {rx} is IID and drawn from the memory buffer D. Let Qi 4x-1)
Cov [Tk, Ty
(12)
Cov [rk, (sk++1 ak+1)] O.
(13)
Theorem Consider the variances of two Q value sequences, denoted as Qi and Qi. in Equation 100 and Equation (T.. which are obtained respectively from single step method and an LNSS method. Additionally, assume that Qo = Var [Qn] Qo Var [Qu] O. Let the IID reward {rx) and (r be drawn from the memory buffer D. Assume the variance of {rr} } is upper bounded by finite positive number B, i.c.,
0 and
0.06
1.M
0.6
0.04
Var [rx] S B. Further define a constant e as,
0.02
0.2
5- -= 7 (-
2N 7
0.0
20
40
LNSS 60
80
100
(14)
Figure 1: Variance discount factor & in Equation
Then the upper bounds of the variances of the two Q value sequences, Var [Q++]] and Var [Q++1], are respectively de- scribed below,
i+1
( Var [Qi+1 ax)] < Σ
1),
(15)
t=1
i+1
Var (Q141 ax)l S 3
( Σ
1)
(16)
1=1
Proof. Both proofs of Lemma I and Theorem I are given in Appendix A
Remark We now provide some insights based on the variance analysis above.
1) Given vb in Equation (14), i..., vb = (,3 ) )²(()_))) it follows that for large N, eb =
(7 - -)) 7
2) Furthermore, by the following identifies, 22-1 1 (7-1)(++1) and 7 22 -1 N2N 1)( () +1),
we have that = (1+ =1)) Therefore, vé decreases exponentially (refer to Figure 1
3) From inspecting Equations 15p and (16), we can see clear advantage of using long " N-step" in
LNSS over the typical reward Tk.
5

---

Experiments and Results
In this section, we first show how LNSS can benefit learning by using simple Maze environment. To provide insight on the effect of using LNSS, we compare the performance of the original Q-learning with the one that the stage reward replaced by LNSS reward.
We then provide a comprehensive evaluation of our proposed LNSS piggybacked on three promising DRL algorithms (DDPG, D4PG, TD3) by measuring their performance several benchmarks in DMC and GYM (for results on GYM, please refer to Appendix E.5 Details of the implementation, training. and evaluation procedures are provided in Appendix reporting evaluation results below, we use the following short-form descriptions.
1) "Base": the original DRL algorithms (TD3, D4PG, DDPG).
2) "LNSS": LNSS piggybacked on the respective DRL algorithms where N=100 unless otherwise specified.
3) "n5": the DRL algorithms with "n-step" implementation in Equation 3 with 5.
Our evaluations aim to quantitatively address the following questions:
Q1. How is LNSS different from original reward? and How helps learning?
Q2. How does LNSS improve Base method?
Q3. How does LNSS compare with previous n-step method (n5)?
Q4. Is LNSS robust enough to compensate for stochastic reward?
Q5. Does LNSS improve Base methods under sparse reward setting?
Q6. How does LNSS reduce the variance of estimated Q values?
Q7. How different N in LNSS affects performance?
Q-learing Single Step
Q-leaming LNSS
With Penalty
WithOut Penalty
Epois Reward
Epois Reward
1.00
Maze Map
0.75
So
S₂
S2
0.50
200
400
600
0
200
400
600
Episode
Episode
Sg
Stage Reward
Stage Reward
1.0
0.5
0.5
Ss
S4
0
0
State
State
Figure 2: Evaluation of LNSS piggybacked on Q-learning in simple Maze (right panel). The evaluations are averaged over 10 seeds. The x-axis is the number of episodes (top-left panel) and the state number (bottom-left panel) in the plots for episode reward and stage reward, respectively. Note that the stage reward for LNSS is calculated based on Equation 6
6.1 The Simple Maze Problem
The right panel of Figure shows the Maze environment where So the initial state, S₁ is the goal state, and black blocks walls. The unique optimal policy is (right.igh.downndowwlleo consider two problem formulations:
We
1) Without Penalty: the agent only receives reward upon reaching goal state S5. For all other states, the agent receives O's.
2) With Penalty: the agent only receives reward upon reaching goal state Sy. For all other states, the agent receives -0.1 per stage penalty.
Q1 LNSS takes future rewards into formulating the surrogate stage reward guide RL agent in reaching the goal state. As Figure 2 lower-left panels show, the stage reward from LNSS is more

---

No Penalty Case
Up
Down
Right
Left
State
Original Reward
LNSS Reward
Original Reward
LNSS Reward
Original Reward
ENSS Reward
Original Reward
LNSS Reward
1147
1.31
0
0
0.62
145
0
0.76
1.88
0
0
0
1.36
0
U
D
0
0.99
0.99
With Penaliy Case
Up
Down
Right
State
Original Roward
LNSS Reward
Original Roward
LNSS Reward
Original Rewiml
LNSS Reward
Original Reward
LNSS Reward
0
-0.09
40,09
1.1
-0099
40.0
1,36
-0.13
2
0.055
0.055
1.36
-0.54
0
-0.055
0.01
4003
0
0.04
1.3
4005
007
0.38
0.997
Table 1: Q tables of Q-learning using original reward and LNSS reward. The Q values reported are averages across 10 different random seeds.
informative as LNSS provides sequences of gradual and smoother rewards to be used in Q-learning. As result, from the upper-left panels, this informative guidance from LNSS significantly enhances the performance in terms of episode rewards. The effect is even more pronounced when dealing with penalties.
From Table with the original reward, the Q value is the sum of discounted expected rewards as in Equation The farther away the goal state, the smaller the Q values are as a result of discounts over the horizon. When learning under the environment of using penalty rewards, the Q values in States Sp, S1, S2 show that they are even farther away from the goal state value. The Q values can not be effectively updated due to a lack of informative feedback signal, and thus, causing the agent to get stuck and cease learning. In comparison, with the LNSS reward, goal-related information can be propagated back from the goal state to the initial state. This guidance plays a crucial role in assisting agents to overcome situations where they might otherwise get stuck.
Acrohon Up
Humanoid Wilk
Fish Swim
Pinger Turnffani
Algorithm
Nuovess X9
Arg. Kwdd
Jt 2n|
Kank [5]
SIspess [55
Avg: Rwdd
20
Kank [5]
Snceess 1%
Arg. Rwd
Ja 20
Rink
NIKDOSS [55
Avg. Rwd
ia 20r
Kunk 15
Noiser Level
DS0 (0.0)
DOPG-LINS
-25.1
100
645.1
-12.7
T00
Base
-53.8
272.9
DDPG-15
100
195.2
67.6
-51.9
2.2 1.5
.00-
100
150.5
33.7
-79.6
100
459.8
126.3
-51.3
TILLNNS
106
114.8
7 XUX
-71.8
100
307.9
16.9
-1923
100
676.8
+ 44.2
-8.4
100
940.1
+ 20.6
-0.3
1a--Baee
5.2.144. 4.1
-98.7
60
184.2 1. 178.8
-52.1
100
483.1
1 127.6
-34.6
90
251.8
1 101.4
-73.3
TD3-5
70
61.7
+ 45.7
.848
0
1.01 + 0.41
-99.6
100
731.7
+ 132.3
-1.1
90
394.2
+ 164.4
-58.2
IMPG-LNSS
406.3
100
383.9
37.1
738.7
59.8
100
$11.5
59.9
-14.0
277.7
-27.7
585.7
D4PG-05
310.1
100
360.3
683.5
90
413.7
-56.1
Nosse Level 155
(0.01)
DDPG-LNSS
100
243.5
62.3
-40.1
100
255.1 22,6
-33.6
100
700.4 1: 107.6
-5.3
100
934.3 1. 30,55
-0.1
DDPG-Rasc
100
188.2
58.7
-53.7
0
0.99
+ 0.25
-99.8
100
346.1 + 135.4
-53.9
100
300.5 + 130.
-67.9
DDPG-05
-60.7
0.45
.99.7
-99.8
100
416.9
109.3
-73.1
100
700.1
100
TD33-Rase
2.4 1.53
.09.4
1.43
-99.5
100
506.0
111.5
-31.4
601
193.4
142.2
-79.5
TD3-n5
69.6
016.1.20 23.5
-32.9
0
1,55
1 0.8
-99
100
688.7
132.3
-68
90
384.1
232
-59.3
ISPG-LLASS
160
330.3
1 60.6
-18.7
100
2479
42.3
-3..4
100
688.3
1 55.3
-6.6
100
501.
-150
DaPC-Rase
100
136.5
50.2
-66.4
100
210.5
44
-45.2
100
650.2
+ 89.3
-11.9
100
300.5
143.2
-68.1
D5
100
262.9
67.1
-35.3
0
10.9
2.3
-9.2
100
$78.7
78.9
-21.7
90
383.7
1 293.8
-59.3
DOPG-LASS
232.6
-418
135.4 25.7
699.3
95.3
-5.3
$10.1
DDPG Base
100
170.7
1 42.1
-58.0
0
0.76 J. 0.42
-99.8
100
330.42
144.2
-55.3
100
315.2
205.4
66.6
DDPG-N5
100
139.1
1.28.
-65.8
0
1.3 1 0.9
-99.7
100
116.5
16.8
-84.2
100
456.5
1 219.7
-51.6
TECEESSS
TA0
80.7
15.73
-90.1
100
200.2 + 117.6
-17.3
T00
696.
174.1
-5.7
100
888.54
1: V2
-33
Bas-Base
2.19 1 1.35
-99.5
0
1.5
-9..7
100
454.9
272.9
-38.4
60
190.
215.7
-79.9
TD3a5
24.9
22.7
.93.9
0.28
-99.7
654.7
190.2
-11.4
-4.2
DMPG-LNSS
331.3
681.4
212.6
-148
Base
1.0011
28.9
.67.9
1.42 0.7
-0077
100
645.1
245.2
-12.6
100
302.5
153.2
-679
D4PG-05
100
251.4
56.4
-38.1
0
0.89 + 0.6
-09.8
100
563.4
+ 214.7
-23.7
90
355.1
+ 285.5
.624
Table 2: Systematic evaluations of LNSS respectively augmented Base algorithms, and comparisons to the Base and r15-augmented Base algorithms. "Rank" (%) is the "percent of reward difference", the closer it is the better.
6.2 Main Results
Evaluation results in Table 2 are performed using default setup of Acrobot SwingUp. Humanoid Walk, Fish Swim, and Finger TurnHard DMC. In the Table "Success" is shorthand for success rate, "Avg. Rwd" stands for average reward, and "Rank" (%) the "percent of reward difference".
7

---

which is ( the average reward of the evaluated algorithm over that of the top performing algorithm 1), the closer it is the better. Note that, in computing the success rate, only those trials that have achieved reward of at least 50 are accounted for as successes.
The results are obtained different noise levels, based on the last 50 evaluations of 10 different random seeds (same for all compared algorithms). Best performances are boldfaced for average reward (Avg. Rwd).
Q2 LNSS improves Base methods. The learning curves for the four continuous dense reward benchmark environments are shown in Figure 3] Quantitative comparisons to the baselines are summarized in the first section of T (noise = 0). Overall, LNSS (solid lines) outperforms their respective base methods (dash lines) in terms of averaged reward (Awg. Rwd), learning speed, and success rate for all three DRL. algorithms. Among the measures, the success (learning) rate is to address the random initialization challenge caused by random seeds [TO]. LNSS method helps its Base method to achieve a 100% learning success rates whereas DDPG and TD3 Base method struggle with Humanoid Walk and Finger TurnHard. Besides, according to the "Rank" measure in Table 2 LNSS helps enhance the performances of almost all Base methods up to the top-performing algorithm in each category in all the tested environments, Detailed plots of pair-wise comparison for without noise condition are provided in appendix
.... TDS-BASE
TD3-LNSS
DAPG-BASE
DMPG-LNSS
DDPG-BASE
DDPG-LNSS
DMC Acrobot Up
DMC Humanoid Walk
DMC Fish Swim
500
1000
Epissdd Reward
400
250
200
500
250
DMC Finger Hard
DMC Cheetah Sporse
DMC Caripole Swingup Sparse
1000
1000
1000
Epicode Reward
750
750
750
500
500
500
250
200000
400000
600000
500000
200000
400000
600000
800000
200000
400000 600000
800000
Figure 3: Systematic evaluation of LNSS piggybacked on three DRL algorithms (DDPG, D4PG, TD3) in DMC environments without reward noise. The shaded regions represent the 95 % confidence range of the evaluations over 10 seeds. The x-axis is the number of steps. Detailed pair-wise comparison plots provided in appendix E.I
Q3 LNSS outperforms previous "n-step" methods (n5). The main improvement of LNSS over n5 are reflected in improved success rate, averaged reward, and "Rank". This improvement can be quantitatively viewed in the first section of Table 2 (noise = O). LNSS consistently enables the Base methods to achieve 100% learning success rate. However, the n5 method may even cause some learning to fail such as TD3 in Humanoid Walk and D4PG in Finger TurnHard. Additionally, according to "Rank" in Table 2 LNSS methods enable all cases to reach performances near those from the best algorithms. However, only TD3-n5 has resulted in slightly better "Rank" in Fish Swim only for without noise condition while all other n5 methods are below LNSS or even below its Base such as TD3-15 for humanoid walk and DDPG-15 for Fish swim. We also observe that LNSS has improved the average reward and lowered the standard deviation for all Base algorithms over those by the n5 method.
Q4 LNSS is robust under noisy rewards. We performed the same set of evaluations in Table 2 DMC experiments under random uniform reward noise settings with magnitudes at 1 1% and 10%
of the maximum DMC step reward (1). As results in the appendix E.2 (noise level 1%). Appendix
1% and 10%) show, at larger noise level, all algorithms have degraded performance with lower mean averaged reward, larger standard division, and more negative "Rank". However, LNSS consistently outperformed Base and n5 methods in terms of all measures for all three DRL algorithms. It is important to point out that we observe LNSS methods robustly improve the success rate with 100% for all environments. However, observe that both Base and n5 methods suffer greatly due to the increased noise level such as
E.3 (Noise level 10%), and the last two sections in (able
8

---

in Humanoid Walk and Finger Turn Harde environments. As Equation 3) shows the performance degradation for nā methods are due to accumulated noise when collecting the discounted sum of returns. This accumulated noise will induce a much larger approximation variance and result in degraded performance.
Q5 LNSS is effective in environments with sparse rewards. For setting up sparse rewards in Cheetah environments, refer to appendix B As Cheetah Sparse and Cartpole Sparse result in Figure One can observe that LNSS enables all DRL algorithms successfully learn all three sparse reward tasks with converged episode rewards greater than 800. However, due to the limited feedback from sparse rewards, all base methods struggle to learn and even fail to learn (e.g, Cheetah Run). Moreover, is important to point out that LNSS helps improve the learning speed over the base methods. This is expected as a long future reward trajectory of N-step is able to provide continuous reward feedback to the agent by assigning credits progressively backward from the time of achieving the desired states. In contrast, a single-step method does not provide any guidance or feedback to the learning agent until reaching the goal.
3
Q6 LNSS helps reduce the variance of Q value estimation. For this evaluation, we let coefficient of variation of Q value (in percentage) as co
Q %. In Figure 4 we show co(Q) every 2e5 steps where as example, we show TD3-LNSS outperforms TD3-Base and TD3-n5 under I 1% noise in rewards. Similar results are obtained for DDPG and D4PG classes of algorithms and shown in appendix E.4 Also shown in the same Appendix are respective results at different noise levels. Results (Figure 2 to Figure 20 in appendix E..) also show that for each LNSS augmented DRL algorithms, it has resulted in improved performance in cv(Q) to near the best performance among all DRL. algorithms. Figure -
std(Q)%
provides an empirical validation for our theoretical result on bounds of variances of the Q value, namely, with large LNSS parameter N at the late stage of learning, Q value variances become smaller as the upper bound of Q value variance decreases significantly according to Equation (14) in Theorem 1.
TD3-BBse
TD1-6
TD1-IN88
SwingLip
Humanoid Walk
DMC
Finger Tur
20
10
20
(V1Q)
10
10
0
200000 400000 600000 800000
200000 400000 600000 S00000
200000 400000 800000 800000
200000 400000 COCOCO 800000
Figure 4: The (Q) (coefficient of variaiton of Q value, the lower the better) of TD3 in DMC with 1% noise. Results are averaged over 10 seeds. The x-axis is the number of steps. Additional and respective results for DDPG and D4PG can be found appendix E.4
Q7. Effects of different length N in LNSS. In Figure 5 we show the effect of different choices of N (N = 5, 10, 20, 50, 100) in our proposed LNSS on top of TD3. (Similar results hold for D4PG and DDPG which can be found in appendix E.7) Comparisons are performed using the same set of hyperparameters except varying N. Figure 5 depicts performance curves for DMC tasks. The LNSS with = 50 and N 100 outperform LNSS with N 5, 10 in terms of final reward and learning speed. The results corroborate what we expect from our theoretical analysis (please refer to Figure
I in the paper). We can see a clear benefit of using large N (N 50, and 100) ) over small(NV= 5, and 10).
Additionally, in Figure 6 we show how cu(Q) (coefficient of variation of Q) varies with different N. Among the three N values, N = 100 outperforms others. Also, we observe that, in more complex environment, longer N is favorable. Notice that, for cartpole sparse environment, there is little difference among different N values. However, in Finger TurnHard and Humanoid Walk, the cu(Q) values of Base cases and N = cases increase dramatically. However, the co(() values for = 50 and N 100 change only slightly. Figure 6 provides an empirical validation for our theoretical analysis on variance discount factor t in Figure T that the longer the N, the more reduction in variance of Q value estimation.
9

---

N-5
N-
N-
N-
N-0
DMC Humanoid Walk
DMC Finger Tum Hard
DMC Carpplo SwingUp Spanse
1000
800
Epols rewand
6100
W
200
400
0
200000
600000
R00000
400000
500000
250000
575000
500000
Figure 5: Episode rewards for the 3 tasks in DMC by TD3-LNSS with different N (N 5, 10, 20, 50, 100) in Equation (6.. The results are averaged from 10 seeds. The x-axis is the number of steps. Respective results for DDPG and D4PG are provided in appendix E.7
DMC Humsmoid Walk
DMC Finger TumHfard
DMC Curpole Swingup Spurse
12
6.0
Vartnce (%g)
40
4.5
300
20
0.0
BASE
N5
N50
N100
BASE
N5
N50
N100
BASE
N5
N50
N100
Figure 6: cu(Q) (coefficient of variaiton of Q value, the lower the better) for the 3 tasks in DMC by LNSS with different N (N = 5, 50, 100) in Equation (6).
6.3 Limitation of This Study.
Here we introduce a new multi-step method, the LNSS, to effectively utilize longer reward trajectories of future steps than those used in existing methods to estimate the Q value with aim of reducing variances in learning. By piggybacking LNSS on top of TD3, DDPG, and D4PG, we demonstrate improved performance in terms of final reward, learning speed, and variance reduction in Q value. However, there exist two limitations. 1) The LNSS requires positive semi-definite reward values in long trajectory. Large negative reward may wash out the significance of good positive rewards. However, this limitation can be easily fixed by elevated reward stored in the temporary buffer TV by positive constant, and lower bounded it by 0. 2) Early termination is another limitation during implementation, which mostly affects LNSS in GYM environments (Hopper, Humanoid, Walker2d). Different from DMC tasks, GYM allows an environment to terminate before reaching the maximum time steps. As such, in early training stage, only 10 or 20 steps may be used to compute LNSS which diminishes the power of large N (such as 50 or 100). To resolve this limitation, re-programming task settings in the original GYM environments is required.
Discussion and Conclusion
1) In this work, we introduce a novel "N-step" method, the LNSS which utilize longer reward trajectories of future steps than those used in existing methods estimate the Q value with an aim of reducing variances in learning. It is easy to implement, as shown in the paper, and it can be easily piggybacked on policy gradient DRL algorithms. It has been shown consistently outperform respective Base and short n-step algorithms in solving benchmark tasks in terms of performance score, learning success rate, and convergence speed. 2) We provide a theoretical analysis to show that LNSS reduces the upper bound of variance in Q value exponentially from respective single step methods. 3) We empirically demonstrate the performance of LNSS piggybacked on TD3, DDPG, and D4PG in variety of benchmark environments that have been challenging for existing methods to obtain good results. 4) We show LNSS can provide consistent performance improvement under various reward noise settings, and for sparse rewards. Our results suggest that LNSS is promising tool for improving learning speed, learning performance score, and reducing learning variance. Further investigation on how to maximize the benefit of selecting optimal reward length N, and how to take advantage of different n in Q value update are exciting questions to be addressed in future work.
10

---

8 Acknowledgment
This research was supported in part under NSF grants #1 #1808752 and #2211740.
References
[1] Wentao Liu, Junmin Zhong, Ruofan Wu, Bretta I. Fylstra, Jennie Si, and He Helen Huang. Inferring human-robot performance objectives during locomotion using inverse reinforcement learning and inverse optimal control. IEEE Robotics and Automation Letters, 72):2549-2556, 2022.
[2] Ruofan Wu, Junmin Zhong, Brent Wallace, Xiang Gao, He Huang, and Jennie Si. Human- prosthesis as collaborating agents for symmetrical walking. Advances in Neural Information Processing Systems, 35:27306- 2022.
[3] Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: M.XXvv15090029977 2015.
[4] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. 2017.
[5] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[6] Gabriel Barth-Maron, Matthew W Hoffmann David Budden, Will Dabney, Dan Horgan, Dhruva Tb, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional determin- istic policy gradients. arXiv preprint 100.v:v80040861111 2018.
[7] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. International conference on machine learning, pages 1587-1596.
PMLR, 2018.
[8] Gabriel Dulac-Amold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 1 1100))2419-244 -268 2021.
[9] Johan Bjorek, Carla Gomes, and Kilian Q Weinberger. Is High Variance Unavoidable in RL.? Case Study in Continuous Control. arXiv preprint arXiv:21 10. 1222, 2021.
[10] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup. and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[11] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pages 1329-1338. PMLR, 2016.
[12] Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5(9), 2004.
[13] Joshua Romoff, Peter Henderson, Alexandre Piché, Vincent Francois-Lavet, and Joelle Pineau. Reward estimation for variance reduction in deep reinforcement learning. arXiv preprint arXiv:1805.03359, 2018.
[14] Kristopher De Asis, J Hernandez-Garee Garcia, G Holland, and Richard Sutton. Multi-step reinforee- ment learning: A unifying algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[15] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.

---

[16] Dimitri P Bertsekas. Rollout algorithms for discrete optimization: A survey. Handbook of Combinatorial Optimization, D. Zu and Pardalos, Eds. Springer, 2010.
[17] Gerald Tesauro. TD-Gammon, self-teaching backgammon program, achieves master-level play. Neural computation, 6(2):215-219, 1994.
[18] David Silver, Thomas Hubert. Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel. et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140) 140-119991111111110 1144, 2018.
[19] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587)4844-88 2016.
[20] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dab- ney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. Thirty-second AAAI conference on artificial intelligence, 2018.
[21] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXin:1506.02438, 2015.
[22] Jingkang Wang, Yang Liu, and Bo Li. Reinforcement learning with perturbed rewards. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages 2202-6209, 2020.
[23] Fabio Pardo. Tonic: A deep reinforcement learning library for fast prototyping and benchmark- ing. arXiv preprint arX1v:2011.07537, 2020.
[24] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International conference machine learning, pages 1928-1937. PMLR, 2016.
[25] Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Beyond the one-step greedy approach in reinforcement learning. In International Conference on Machine Learning, pages 1387-1396. PMLR, 2018.
[26] Christopher John Comish Hellaby Watkins. Learning from delayed rewards. 1989.
[27] Jing Peng and Ronald J Williams. Incremental multi-step q-learning. In Machine Learning Proceedings 1994, pages 226-232. Elsevier, 1994.
[28] J Fernando Hernandez- and Richard S Sutton. Understanding multi-step deep rein- forcement learning: systematic study of the dqn target. arXiv preprint arXiv: 1XX1v:9001.00 007510, 2019.
[29] Harm Van Seijen, Mehdi Fatemi, and Arash Tavakoli. Using logarithmic mapping to enable lower discount factors in reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[30] Harm Van Seijen and Richard S Sutton. Efficient planning in MDPs by small backups. In Proc. 30th Int. Conf. Mach. Learn, volume 28. Citeseer, 2013.
[31] Stefan Depeweg, José Miguel Hernández-Lobato, Finale Doshi-Velez, and Steffen Udluft. Learning and policy search in stochastic dynamical systems with bayesian neural networks. arXiv preprint arXiv: 2016.
[32] David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Arnoid, David Reichert, Neil Rabinowitz, Andre Barreto, et al. The predictron: End-to- end learning and planning. In International Conference on Machine Learning, pages 3191-3199.
PMLR, 2017.
12

---

[33] Vladimir Feinberg, Alvin Wan, lon Stoica, Michael I Jordan, Joseph E Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-free reinforeement learning. arXiv preprint arXiv: 803.00001,, 2018.
[34] Alfredo V Clemente, Humberto N Castejón, and Arjun Chandra. Efficient parallel methods for deep reinforcement learning. arXiv preprint
2017.
[35] Yinlong Yuan, Zhu Liang Yu, Zhenghui Gu, Yao Yeboah, Wu Wei, Xiaoyan Deng, Jingcong Li, and Yuanqing Li. A novel multi-step Q-learning method to improve data efficiency for deep reinforcement learning. Knowledge- Bassed Systems, 175:107-117, 2019.
13


Reviews:
[{"review_id": "fh8aFHc3RQ", "reviewer": "Reviewer_dTq6", "summary": "This paper proposes a simple but effective surrogate reward, which uses the future n-step cumulative rewards (with some coefficient). \nThe theoretical results show that the proposed method has a smaller variance than the classical one-step method.\nThe experimental results show the effectiveness of the proposed method.", "questions": "For my major concern, please see the weakness above.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 1, "presentation": 4, "contribution": 3, "strengths": "Generally, this paper writes well.\nThis paper proposes an interesting surrogate reward, which is very simple but has shown to be very effective.\nThe paper also provides a theoretical analysis of the variance compared to that of existing one-step method.\nThe experimental results are complete and sufficient to show the effectiveness of the proposed method.", "weaknesses": "I agree that this paper tries to solve an important problem and proposes a very simple but empirically effective method. \n\nHowever, the proposed method does not make sense to me. I give my reason below.\n\n- My major concern is whether the proposed method with the surrogate reward learns exactly the same solution as the one using the original reward. The paper didn't provide any discussion or proof of this critical problem.\n\n- In my view, my answer to this problem will be negative. Based on eq.7, the surrogate loss is, in fact, a multi-step cumulative reward times a coefficient. Compared to the existing n-step method (eq. 3), the difference is the coefficient and the next state (the proposed method use $s_t$, and the n-step method use $s_{t+N}$). The solution of the proposed method should be different from the original $Q^\\pi$.\n\n- I believe that eq. 5 is very suspicious. I don't understand why the $G'_k$ should be in that form (and $r_k'$ is a constant). In addition, in this way, the final computed $r'_k$ will be different over different k.\n- (I spent a lot of hours on this paper, trying to understand, but I failed to convince myself. I'm happy to increase my score if the author can prove I'm wrong)\n\nThe paper didn't make a comparison of the variance with n-step methods.\n\nIn addition,  how does the paper fit into the off-policy setting? It is no problem for the one-step method because there is no bias. However,   when utilizing multi-step data, this could be one problem for the proposed method (DDPG and several baseline methods used in the paper are off-policy methods).\n\nMinor Issues:\n- Line 115: It's not very general to assume the policy to be deterministic.\n- eq. 1: It is better to use $s_{k'+1} \\sim p( | s_{k'}, a_{k'} )$. Just differentiate $k'$ and $k$\n- eq. 2: missing an expectation over $s_{k+1}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reviewing our paper and for the penetrating questions. We also thank the reviewer for recognizing that our paper addresses an important problem, and our LNSS is simple and potentially very effective.\n\n>Q1 Learns exactly the same solution as the one using the original reward?\n\nPlease refer to our General Response (GR), points 5) and 6).\nThe sequence ${r_k’}$ differs from ${r_k}$. Thus, the respective returns $\\mathbb{Q}_i$  and $Q_i$ differ. Refer to Fig R1, the right column. Inspect estimation bias between the solid lines with the respective dashed lines. Learning with the two different reward sequences {$r_k'$} and {$r_k$} leads to different solutions in general. It is noted that LNSS resulted in significantly improved learning performance (Fig. 2 and Table 1).\n\nNote however, ${r_k’}$ approaches $r_k$ upon learning convergence, and $G_k’$ (N-step discounted sum of ${r_k’}$) becomes an unbiased estimate of $G_k$. Since the update laws are the same for both cases, and thus, at this time, the two sums necessarily converge to the same solution. But this is not true for early stage.\n\n>Q2 Eq. 5, why $G'$ is in that format and $r_k'$ is constant?\n\nThank you for pointing this out. Please first review GR point 4). We'd like to emphasize that $r_k'$ is constructed from $G_k$ (Eqn (6)-(7)) without any assumption or additional requirement. \n\nAbout Eqn (5), $G_k'$ in (5) is an imaginary variable in our mind, a short-hand notation. It is probably easy to see that it inspired us to reach Eqn (6) by simply moving the sum of discounted factor $\\gamma$ away from $r_k'$, and thus we arrive at Eqn (6), for the construction of $r_k'$.  \n\nOur use of $G_k'$ may have caused this confusion to the reviewer. We should have used a different notation so that $G_k'$ is as in RL convention that it is the sum of discounted rewards {$r_k'$}.\n\n>Q3 comparison of the variance with n-step methods\n\nFirst, please note that our systematic evaluations include comparisons on variance for n-step method (n5) and LNSS, please refer to Table 1 where in all cases, the std values of LNSS are less than those of n5.\n\nMany previous works including [1-3] reported that off-policy n-step methods such as TD$(\\lambda)$ and $Q(\\sigma)$ are shown to decrease the estimation bias at the cost of increasing the variance. \nAs LNSS aims to, and is shown to, reduce variance without sacrificing bias (General Response Point 7), to see how n-step methods may increase variance, please refer to Eqn (25), the n-step return variance can be written as $ Var[\\sum_{t=k}^{k+N-1}\\gamma^{t-k} r_t ] \\leq (\\frac{\\gamma^{2N} - 1}{\\gamma^2 - 1}) \\mathbb{B} $ and $\\frac{\\gamma^{2N} - 1}{\\gamma^2 - 1}) > 1$ which will result in the upper bound on the variance of n-step to be greater than that of single step. Combine with Theorem 1 we will have the following relations hold $Var[$LNSS$] < Var[$single step$] < Var[$n step$]$.\n\n>Q4 About estimation bias and off-policy issue\n\nPlease refer to our General Response, points 7)-9).\n\n> Minor Issues\n\nWe thank the reviewer for pointing out these detailed discrepancies. We will make the edits if the paper is accepted.\n\n[1] Watkins,C.J.C.H.(1989).Learning from delayed rewards.PhD Thesis,University of Cambridge, England.\n\n[2] Jaakkola, T.; Jordan, M. I.; and Singh, S. P. 1994. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation 6(6):1185–1201.\n\n[3] De Asis, Kristopher, J. Hernandez-Garcia, G. Holland, and Richard Sutton. \"Multi-step reinforcement learning: A unifying algorithm.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1. 2018."}, {"review_id": "BaA9jsj7lY", "reviewer": "Reviewer_PJwS", "summary": "Authors proposed a long N-step surrogate stage (LNSS) reward for DRL which mitigates the high variance problem in continuous control problems. It is shown that the proposed LNSS can provide consistent performance improvement measured by average reward, convergence speed, learning success rate, and variance reduction in Q values and rewards.", "questions": "One question is that for baseline comparison, the authors chose original algorithms and a simple n-step variation of loss function with n=5. LNSS reported in the table is using N=100. I'm wondering can this be considered as a fair comparison? From ablation studies, smaller N such as N=5, and N=10 does not perform as good as N=100 in training and variance reduction. Can authors justify this? Would it be possible to also include LNSS N=5 in the main results table for comparison. \n\nI noticed that in some environments, a simple n-step variation with n=5 is even much worse than the baseline algorithm, while LNSS with N=100 provide promising improvements. This is very interesting. Any explanations for this phenomenon? Will LNSS with N=5 have the same improvements? \n\nToo many colors in figure 2 and 3, maybe use the same color for one baseline algorithm, for example, TD3-base TD3-LNSS both use red but one solid line and one dash line as you already use in the figures for an easy comparison. \n\nA final question out of curiosity, to my knowledge, TD3 itself would fail in some complex environments , and it is nice to see how LNSS helped to improve the situation, however, some algorithms such as max-entropy algorithm SAC would succeed. Will LNSS be combined with max-entropy algorithm also provide similar improvements in performance and variance reduction?", "limitations": "I think for me some phenomenon in experimental results may need some further explanation. A large N is required for powerful performance. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Well written and well organised.\nProposed a novel and easy-to-implement n-step method LNSS which reduces variance in training. The method can be easily applied on existing algorithms such as DDPG, TD3 for enhanced performance. \nPromising experimental results with large N-steps and theoretical analysis provided to support the conclusions. Nice ablation studies provided.\nMain experimental results are presented in a clean table which is easy to interpret. ", "weaknesses": "I think some interesting experimental results lacks explanation. Some figures can be improved for better readability. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank the reviewer for reading our paper and for the favorable comments. Your questions have helped us further improve the paper. \n\n>Q1 How to justify smaller N not working as well as larger N? Also how to show this in baseline comparisons (using n=5 and N=5) and ablation studies (N=5, 10, 100)?\n\nFrom Theorem 1 and Figure 1, we can see that for N = 5, 10, and 100, the respective $\\psi$ factor is 0.2, 0.1, 0.011. Clearly, the upper bound of variance for N = 100 is much smaller than N=5 and 10. Additionally, our experiment results strongly support this theoretical result. Please refer to our discussions in Results section (Q6. Effects of different length N in LNSS) and Fig. 5. Specifically, in lines 286-289, we discussed respective learning performances for different N.\n \nAs theoretical and experimental results show that the larger the N the better the learning performance. For n-step methods, as n = 5 is the best-performing choice as reported in RAINBOW, D4PG [1,2], we therefore consider it to be fair to compare with our best-performing and also realistic choice of N=100. Also since the strength of LNSS relies on using larger N, we theretofore focused on reporting large N results. The reviewer has raised an important point. If the paper is accepted, we will include N=5 in Table 1 if space permits or we will include an expanded Table 1 in the Appendix.  \n\n>Q2 In some environments, a simple n-step variation with n=5 is even much worse than the baseline algorithm, while LNSS with N=100 provide promising improvements. This is very interesting. Any explanations for this phenomenon? Will LNSS with N=5 have the same improvements?\n\nPlease refer to lines 256 to 259 where we explain why the performance degraded for n5 method even below the baseline. To gain some insight, from Eqn (3), about n-step methods, we can intuitively see that errors in reward signal may degrade learning performance, the longer the reward sequence, and more uncertainties due to accumulated errors from longer steps. As such, it may introduce a much larger approximation variance.\n\nFor our LNSS, we do not expect LNSS with N = 5 to provide exceptionally good performance as large N values do.  Please refer to our reported results (Table 1) where N=100 improves learning performance significantly. Please also refer to our discussion for Q1 above.\n\n> Q3 Too many colors in Figures 2 and 3, maybe use the same color for one baseline algorithm, for example, TD3-base TD3-LNSS both use red but one solid line and one dash line as you already use in the figures for easy comparison.\n\nVery good point, thank you! We'll make the update if the paper is accepted. \n\n> Q4 Can LNSS work on SAC?\n\nSince our LNSS only changes the stage reward and we did not change anything else in the learning framework of baseline algorithms, theoretically LNSS can be used in SAC with no problem. \n\nAlso, from DMC benchmark results [3], it is reported that SAC and TD3 have very similar performance. This is the reason we only used TD3 baseline in the paper. To provide more specifics, during the rebuttal period, we applied LNSS on SAC for two environments  (cartpole swing-up sparse and finger turn hard) to provide preliminary results. As expected, the performance of SAC+LNSS has improved over SAC baseline. Please refer to Fig R2, the preliminary results under the general response pdf file.\n\n\n[1] Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., ... & Silver, D. (2018, April). Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence (Vol. 32, No. 1).\n\n[2] Barth-Maron, G., Hoffman, M. W., Budden, D., Dabney, W., Horgan, D., Tb, D., ... & Lillicrap, T. (2018). Distributed distributional deterministic policy gradients. arXiv preprint arXiv:1804.08617.\n\n[3] Pardo, F. (2020). Tonic: A deep reinforcement learning library for fast prototyping and benchmarking. arXiv preprint arXiv:2011.07537."}, {"review_id": "hmIUwR7rK3", "reviewer": "Reviewer_TX4g", "summary": "The paper propose a new reward estimator for off-policy RL to reduce the variance of the Q-value target estimate in bellman backup. Specifically, the method works by computing the discounted return of a trajectory segment and then augment such reward along with the original transition (state, action, next state) in the replay buffer. On a range of simulated environments, the proposed method is able to enhance existing off-policy RL algorithm such as DDPG, D4PG and TD3 on a range of environments in DeepMind Control Suite and OpenAI Gym. The authors also provide variance analysis of the Q-value target estimate and demonstrate an improved variance upper-bound.", "questions": "- Have you experimented with using the full trajectory to compute the LNSS reward? I imagine that this could actually help the sparse reward tasks even more (e.g., Cartpole SwingUp Sparse).\n- It would be also very interesting to study the interaction of LNSS with more gradient steps per environment step (UTD ratio). Intuitively, having more gradient updates per data collection step could also greatly help with propagating the signal back in time fast (in terms of the number of environment steps).", "limitations": "The author has adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to follow. The proposed method is very simple and can be directly added on top of any TD-style RL algorithms. In addition, the paper contains a set of thorough empirical evaluations that demonstrate that the effectiveness and the robustness of the proposed method (LNSS) under a range of reward functions (e.g., noisy, sparse), different hyperparameters as well as insights on the variance reduction effect that LNSS has on the Q value estimation. ", "weaknesses": "If I understand correctly, the proposed method can lead to a biased value estimate, which conceptually could hurt performance. The bias comes from the fact that the LNSS reward estimate assumes the trajectory is filled with a constant reward. For example, for sparse reward task where the reward is only non-zero, positive in the end of the trajectory, the Q-value would get overestimated. It would be great if the authors could discuss more the implication of the bias and whether there are any pathological examples that could break the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank the reviewer for reading our paper and for the favorable comments. Your questions have helped us further improve the paper. \n\n> Q1 About estimation bias and learning performance and the LNSS reward estimate assumes the trajectory is filled with a constant reward\n\nPlease refer to our General Response, points 7) 5) 6) 9)\n\nAbout $r_k'$ being a constant reward signal, this may be caused by our inappropriate choice of short hand notation of $G_k'$ in Eqn (5), and thus caused confusion. Actually $G_k'$ in (5) is an imaginary variable in our mind.  It is probably easy to see that it inspired us to reach Eqn (6) by simply moving the sum of discounted factor $\\gamma$ away from $r_k'$, and thus we arrive at Eqn (6), for the construction of $r_k'$. We should have used a different notation so that $G_k'$ is as in RL convention that it is the sum of discounted rewards {$r_k'$}.\n\nAs for a pathological example that may break LNSS, please refer to our Limitations section where we discussed that if there is a lack of a sufficiently long reward sequence to work with, then LNSS will not be effective.  \n\n>Q2 Have you experimented with using the full trajectory to compute the LNSS reward? I imagine that this could actually help the sparse reward tasks even more (e.g., Cartpole SwingUp Sparse).\n\nIn principle, we can use a full trajectory, but that may not further improve performance. Recall that in infinite horizon discounted reward formulation, the discount will be so severe in further steps so that the respective stage reward plays little importance in the sum. To see that, for $\\gamma = 0.99$, at N = 1000 (typical full length of an episode), $\\gamma^{999} = 4e−5$. Thus, its effect is minimal. We thus consider $N = 100$ in LNSS to be effective and practical.\n\n> Q3 It would be also very interesting to study the interaction of LNSS with more gradient steps per environment step (UTD ratio) Intuitively, having more gradient updates per data collection step could also greatly help with propagating the signal back in time fast (in terms of the number of environment steps).\n\nWe thank the reviewer for the suggestion. This is indeed a very interesting idea. We did not implement the UTD ratio, but implemented the original baselines approaches, i.e., one update per environment step. We did so as we thought this would be fair to all baseline algorithms by using their original implementation. But we agree with the reviewer that having more gradient updates per data collection step could help improve training time. We'd be happy to explore this idea in our future work."}, {"review_id": "ttb0lfliws", "reviewer": "Reviewer_ektB", "summary": "This paper introduces a new stage reward estimator called the long N-step surrogate stage (LNSS) reward for deep reinforcement learning (RL). The LNSS aims to mitigate the high variance problem in deep RL, which has been shown to impede successful convergence of learning, hinder task performance, and limit the application of deep RL in continuous control problems. The paper shows that LNSS, which uses a long reward trajectory of future steps, consistently improves performance in terms of average reward, convergence speed, learning success rate, and variance reduction in Q-values and rewards. The evaluations are based on various environments in DeepMind Control Suite and OpenAI Gym using LNSS in baseline deep RL algorithms such as DDPG, D4PG, and TD3. The paper also demonstrates that LNSS significantly reduces the upper bound on the variances of Q-values compared to single-step methods.", "questions": "1. It is obvious that increasing the length of bootstrap can reduce variance, but how do you handle bias (off policy issue)?", "limitations": "The paper seems to lack originality.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper proposes a new stage reward estimator, LNSS, which addresses the high-variance problem in RL. This can be useful in improving performance in continuous control tasks.", "weaknesses": "1. Compared with the common n-step bootstrap method, it seems that the difference is only the larger n?\n2. The paper uses off-policy RL baselines like TD3 and such a large N in LNSS reward, but didn't pay any attention to the off-policy issue.\n3. The paper is not well written, making it difficult to identify the originality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's critical input, which has helped us to think about LNSS from a general perspective in order to make it more clear and highlight its novelty.\n\n>Q1 compare with common $n$-step method, the difference is only the larger $n$? lack originality\n\nThank you for the question. We have carefully explained this issue in the General Response, points 1) - 5).\n\n>Q2 How to address the off-policy issue? How do you handle bias (off policy issue)?\n\nThank you for this important question. Please refer to our General Response, points 7), 5), 6) and 9) where we explained that LNSS does not raise additional estimation bias to the Baseline algorithms\n\n>Q3 The paper is not well written, making it difficult to identify the originality.\n\nWe sincerely thank the reviewer for the feedback. Hopefully, with the point to point explanation in our general response, the significance and the novelty of LNSS are now clear so that the entire paper is easy to read now, as other reviewers said in their reviews."}, {"review_id": "DSbbDQnPqh", "reviewer": "Reviewer_r58G", "summary": "The article considers a new way to formulate the n-step rewards in deep reinforcement learning. Specifically, while the normal n-step reward discount the Q-value by \\gamma^n, the authors propose to only discount the Q-value by \\gamma while using the normal n-step reward (times a constant) for r. For a simplified model, the authors mathematically prove that this decreases an upper bound of the variance of Q-values. Empirically, the authors add the proposed method to three standard RL algorithms (DDPG, TD3, D4PG) and evaluate them on DMC and GYM. For four tasks in DMC, the proposed method improves the performance of the baseline algorithms. For GYM, the proposed methods improve TD3 on a task.\n\nEDIT: I have read the rebuttal and will keep my score but decrease my certainty.", "questions": "Are the experiments all state-based? If so, could you add experiments when learning from pixels?  \n\nHow were the environments selected?\n\nWill the upper bound in Theorem 1 be tight?\n\nCan you clarify the assumptions in Theorem 1?\n\nAre the implementations SOTA? If not, can you try adding your method to a SOTA implementation?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper proposes a natural and simple method. It should be simple to implement and could conceivably improve performance.\n\nThe authors show strong empirical performance for the proposed method.", "weaknesses": "The authors show improvements on a few tasks for a few algorithms. It is unclear how the environments are selected, and there is some risk of cherry-picking. Furthermore, it is not clear if the baseline algorithms and their implementations are SOTA. So it’s not really clear if the proposed methods would improve SOTA RL, they might just improve some mediocre baselines.\n\nThe assumptions of theorem 1 are not clear. Furthermore, I think the interpretation of the results is misleading. The authors show that an upper bound on the variance of the Q-values decreases with the proposed method. However, a difference in an upper bound does NOT imply that the actual variance decreases. That is only true if the upper bound is reasonably tight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's comments and suggestions. We'll properly address the questions in our revision if the paper is accepted. \n\n>Q1. The author selected a few tasks for a few algorithms\n\nThank you for this important comment. We believe that the number of tasks and the baseline algorithms we selected in our paper is in line with the most recent, SOTA results published in top-tier conferences such as NeuIPS 2022 and ICML 2022. For example, for evaluations in [1-5], the authors used from 2 to 5 benchmark environments. They used three baseline algorithms. Together with their 6 variant algorithms. they evaluated between 3 to 9 algorithms.\n\nIn comparison, our evaluations involved 7 different DMC benchmark environments for all base algorithms in our main paper, and additional 3 different GYM benchmark environments for TD3. For algorithm selection, as in those papers [1-5], we used 3 baseline algorithms. For each algorithm, we have 2 different variants (n-step and LNSS). This makes our total compared algorithms to be 9.\n\nIn sum, we believe our selection of benchmark environments and baseline algorithms was on par with the most recent comparable papers in top venues.\n\n>Q2. How were the environments selected?\n\nWe kept a general idea in mind that is to diversify our benchmark environments. We not only select dense reward environments, but also sparse reward environments. Additionally, We considered reward noise in each dense reward environment to make the  environments more realistic (more often than not, previous works do not consider reward noise). \n\nAmong all DMC benchmark environments, the four types of environments are classical control dense, classical control sparse, robot locomotion dense, and robot locomotion sparse. For classical control types, many recent papers choose carpole swingup [1,6,7,8] which is much easier to learn than acrobot-swingup as discussed in [9,12]. We thus chose acrobot-swingup. For robot locomotion, the complexity of the environment increases as the dimension of the state and action space increases. Many recent papers use walker-walk [1,6,8,10,13] with  state space dimension of 18 and action space 6, and cheetah-run [4,9,11,13,16] with state space 18 and action space 6. These two environments are much easier to learn than our selection of humanoid-walk [1,8,9] with state space dimension of 54 and action space 21. Additionally, fish-swim [10,12] and finger-turn hard [10,11,12] are also commonly selected locomotion benchmark environments. For classic control sparse type, we use carpole swingup sparse [8,13], a commonly selected sparse benchmark. For locomotion sparse type, as other papers [14,15], we used cheetah and walker to sparsify the dense reward, a common practice in literature [14,15]. We therefore have a locomotion sparse benchmark. For GYM environments, Hopper, walker2d and humanoid are the common selection for evaluations in the literature [12,16,17]. We therefore did the same.\n\n>Q3. Are baseline and its implementation SOTA?\n\nBased on comprehensive benchmark results on Deepmind Control Suite [9,18,19], our choice of off-policy baselines are SOTA. Specifically, it is well accepted that D4PG provides SOTA results in continuous control problems. This can also be seen from the highest rewards achieved by D4PG with scores over 900 over 1000. As such D4PG has been used in most of the recent and impactful papers [1,20,23,24]. Although DDPG and TD3 do not perform as well as D4PG, they still are considered SOTA in RL as they are widely used as baseline algorithms in recent impactful papers [2,3,21,22,23].\n\nAdditionally, notice from Table 1 that, LNSS has enabled DDPG and TD3 to achieve comparable performance as SOTA D4PG. This also demonstrates the significance and impact of LNSS and why it is a novel and practical idea. \n\n>Q4. Clarify the assumptions in Theorem 1? and will the upper bound in Theorem 1 be tight?\n\nWe assume state-action value function $Q$ and $\\mathbb{Q}$ are initialized to 0 ($Q_0 = 0$ and $\\mathbb{Q}_0 = 0$) which is a common assumption and practically used in reinforcement learning [25,26]. Accordingly,  the variance of initial $Q$ values are 0, i.e., $Var[Q_0]=0$ and $Var[\\mathbb{Q}_0]=0$\n\nWe assume the reward samples follow IID process which is a common and widely used assumption in reinforcement learning [27,28]\n\nWe Assume the variance of $\\{r_k\\}$ is upper bounded by a finite positive number $\\mathbb{B}$, i.e., $Var[r_k] \\leq \\mathbb{B}$. This is widely used and practical. Consider a reward bounded by $[minR,maxR]$, the maximum variance can be calculated using Popoviciu's inequality: $Var[r] \\leq \\frac{1}{4}(maxR-minR)^2$. Hence our  $\\mathbb{B} = \\frac{1}{4}(maxR-minR)^2 $. For DMC environments, the rewards are within [0,1]. Other environments such as Atari domain clips reward to be within [0,1]. Therefore in many cases,  $\\mathbb{B} = \\frac{1}{4}$.\n\nLNSS theoretically reduces the upper bound of variance according to Theorem 1. Furthermore, this bound exponentially decreases as N increases. For example, for N=100, Refer to Remark 2 and Figure 1, we can see that $\\psi=0.011$. Therefore, in this case, LNSS has reduced the upper bound of variance by about 100 times from single-step methods. Our extensive evaluation results also show significantly reduced variance due to LNSS. (Table 1 and Fig 4, 6 and all figures in Appendix)\n\n>Q5. Are the experiments all state-based? If so, could you add experiments when learning from pixels?\n\nYes, this paper is about solving state-based problems. Probably for similar reasons, most works [1-8,10-17,19,21-29] also mainly focus state-based problems. Actually, the literature covers either state-based or directly pixel-based problems, not both. In principle, we expected LNSS to be effective for pixel-based problems, in which case, we will need to use deep NN/ CNN in place of our fully connected networks. We are more than happy to quantitively evaluate LNSS on pixel-based problems in our future work."}]

Author rebuttal:
# General Response: Insights on LNSS, its essence, and novelty
We first thank all reviewers full-heartedly for their insightful comments. We will integrate some key points below into the revision if our paper is accepted.
1) LNSS is about a new, surrogate reward $r_k’$, which relies on multiple (long N) steps of the reward sequence {$r_k$}. This new surrogate reward sequence {$r_k’$} is then used in a 1-step framework (Eqn 2). 
2) LNSS is new as it is fundamentally different from 1) the traditional 1-step methods (Eqn 2) due to difference in stage reward, and 2) the traditional multi-step or n-step methods (Eqn 3) due to using a single stage surrogate reward $r_k’$ (Eqn 8). Both traditional approaches have a long history of development [1-4]
3) LNSS is simple, and effective as it results in reduced variance and improved performance (average reward, convergence speed, learning success rate). 
4) The surrogate $r_k’$ is a weighted average (or simply the center of mass) of the long N-step reward sequence as 
$ r_k' =  \dfrac{ \sum_{t=k}^{k+N-1} \gamma^{t-k} r_t}{\sum_{n=0}^{N-1} \gamma^{n}} = \dfrac{G_k}{ \dfrac{\gamma^N - 1}{\gamma -1}}=  \dfrac{\gamma -1}{\gamma^N - 1}G_k$
5) The sequence {$r_k’$} differs from {$r_k$}. Thus, their respective $\mathbb{Q}_i$ and $Q_i$ differ. Refer to Figure R1, the right column. Inspect estimation bias between the solid lines with the respective dashed lines. Notice that, the two estimation biases differ during learning. However, as will be discussed below, $r_k’$ approaches $r_k$ upon learning convergence, at which point $G_k’$ as the N-step discounted sum of $r_k’$ (not the $G_k'$ in Eqn (5), where we should have used a different shorthand notation) become an unbiased estimate of $G_k$. 
6) To see the above point, notice that, for successful learning using either {$r_k’$} or {$r_k$} (namely reaching convergence with sufficiently large $i$ and sample pairs being used sufficient number of times in learning), it is necessary that $r_k$ approaches a constant reward $c$ (see DMC examples after the below equations). From the derivations below, if we compute $r_k’$ as constructed above or Eqn (6), it is necessary that $r_k’$ also approaches $c$. Since $r_k’$ approaches $r_k$ (constant $c$) upon learning convergence, and the update laws are the same for both cases, then, toward late stage of learning, $G_k$ and $G_k'$ necessarily converge to the same solution, but this is not true for early stage.
 
    Derivation: For successful learning, $r_t = c$, $G_k = \sum_{t=k}^{k+N-1} \gamma^{t-k} r_t =  \dfrac{1 - \gamma^N}{1 - \gamma}c$, thus For Eqn (6), $r_k' = \dfrac{\gamma -1}{\gamma^N - 1}G_k = c$ and $G_k' = \sum_{t=k}^{k+N-1} \gamma^{t-k} r'_t =  \dfrac{1 - \gamma^N}{1 - \gamma}c$

    For illustration, consider a DMC example: a two-link planar reacher where the stage reward approaches 1 as end point approaches target. Thus, the reward sequence {$r_k$} will be all 1’s once learning converges. As another example from DMC, consider the “acrobot swingup” which involves an underactuated double pendulum environment. Once the double pendulum is balanced, and then to the end of this episode, the reward sequence {$r_k$} will be all 1’s. 
 
7) From the above discussion, upon learning convergence, $G_k’$ is an unbiased estimate of $G_k$. Also, from Fig R1 in attached PDF, we see that LNSS does not introduce additional estimation bias to the base algorithms (inspect the right column, late stage of learning). 
8) We speculate that the initial difference between $G_k’$ and $G_k$ may actually be helpful to learning performance with reduced variance, improved average reward, learning success rate, and learning speed (Refer to Fig 2, and Table 1). Or in other words, using knowledge of the ultimate expected return ($G_k$) early on may have helped steer certain transitions and hence shape the behavior of the agent.
9)	$r_k’$ is constructed from a segment of N-steps of the reward sequence given policy (Eqn 7). It is then placed into off-policy baseline algorithms (e.g., DDPG,D4PG, TD3, SAC) in a single step framework (Eqn 2). Also notice that, as discussed in the above point 7), using $r_k’$ does not introduce additional estimation bias. Thus together (LNSS on top of baseline), the procedure still is an off-policy TD algorithm and the learned action-value function still aims at approximating $Q^*$, independent of the policy being followed, so long as the policy has an effect in that it determines which state–action pairs are visited and updated, and all state-action pairs continue to be updated. This a minimal requirement for any method guaranteed to find optimal behavior in the general case [Sutton 2018 book].
10)	LNSS theoretically reduces the upper bound of variance according to Theorem 1. Furthermore, this bound exponentially decreases as N increases. For example, for N=100, Refer to Remark 2 and Fig 1, we can see that $\psi=0.011$. Therefore, in this case, LNSS has reduced the upper bound of variance by about 100 times from single-step methods. Our extensive evaluation results also show significantly reduced variance due to LNSS. (Table 1 and Fig 4, Fig 6 and all figures in Appendix)

[1] Watkins,C.J.C.H.(1989).Learning from delayed rewards.PhD Thesis,University of Cambridge, England.

[2] Jaakkola, T.; Jordan, M. I.; and Singh, S. P. 1994. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation 6(6):1185–1201.

[3] De Asis, Kristopher, J. Hernandez-Garcia, G. Holland, and Richard Sutton. "Multi-step reinforcement learning: A unifying algorithm." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1. 2018.

[4] Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., ... \& Kavukcuoglu, K. (2016, June). Asynchronous methods for deep reinforcement learning. In International conference on machine learning (pp. 1928-1937). PMLR.
 

Meta-review: This paper has initially received mixed reviews. Some reviewers have appreciated the paper, while others have expressed doubts about the soundness of the method. In particular, one reviewer seems really concerned about whether the proposed method introduces bias or not, as claimed. Unfortunately, even if the authors provided an extensive rebuttal to address the concerns of reviewers in terms of the contribution and soundness of the method, the reviewers with negative scores did not participate in the discussion till the end. Given the positive reviews and the effort of the authors in providing theoretical guarantees for their method, even for multiple cases trying to interpret the doubts of the reviewer, I argue for accepting this paper.

I encourage the authors to address all the comments and to incorporate the recommended improvements in the final version.
Decision: Accept (poster)