Multi-step Greedy Policies in Model-Free Deep Reinforcement Learning
Authors: Yonathan Efroni
Manan Tomar
Mohammad Ghavamzadeh
Venue:  (2020)
Keywords: Reinforcement Learning
Multi-step greedy policies
Model free Reinforcement Learning

Abstract: Multi-step greedy policies have been extensively used in model-based Reinforcement Learning (RL) and in the case when a model of the environment is available (e.g., in the game of Go). In this work, we explore the benefits of multi-step greedy policies in model-free RL when employed in the framework of multi-step Dynamic Programming (DP): multi-step Policy and Value Iteration. These algorithms iteratively solve short-horizon decision problems and converge to the optimal solution of the original one. By using model-free algorithms as solvers of the short-horizon problems we derive fully model-free algorithms which are instances of the multi-step DP framework. As model-free algorithms are prone to instabilities w.r.t. the decision problem horizon, this simple approach can help in mitigating these instabilities and results in an improved model-free algorithms. We test this approach and show results on both discrete and continuous control problems.

Under review as a conference paper at ICLR 2020
MULTI-STEP GREEDY POLICIES IN MODEL-FREE DEEP REINFORCEMENT LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Multi-step greedy policies have been extensively used in model-based Reinforee- ment Learning (RL) and in the case when a model of the environment is available (e.g., in the game of Go). In this work, we explore the benefits of multi-step greedy policies in model-free RL when employed in the framework of multi-step Dynamic Programming (DP): multi-step Policy and Value Iteration. These al- gorithms iteratively solve short-horizon decision problems and converge to the optimal solution of the original one. By using model-free algorithms as solvers of the thort-horizon problems instances of the multi-step DP framework. As model-free algorithms are prone instabilities w.r.t the decision problem horizon, this simple approach can help in mitigating these instabilities and results in an improved model-free algorithms. We test this approach and show results on both discrete and continuous control problems.
derive fully model-free algorithms which are
INTRODUCTION
The field of Reinforcement learning (RI.) span a wide variety of algorithms for solving decision- making problems through repeated interaction with the environment. By incorporating deep neural networks into RL algorithms, the field of RL has recently witnessed remarkable empirical success (eig..Mnih
Mnih et al. 2013: Lillicrap et al. 2015: Levine et al. 2016 Silver et al. 2017). Much of this success had been achieved by model- free RL algorithms, such as Q-learning and policy gradient. These algorithms are known to suffer from high variance in their estimations (Greensmith et al., 2004) and to have difficulties handling function approximation (e.g.. (hruun & Schwartz 1993 Baird 1995 Van Hasselt et al. 2016 Lu al. 2018). These problems intensified in decision problems with long horizon, i.e., when the discount factor, is large. Although using smaller values of Y. addresses the 7-ddeendennt issues and leads to more stable algorithms (Petrik & Scherrer 2009)
Jiang et al. 2015), it comes with a cost, as the algorithm may return biased solution, i.e., it may not converge to an optimal solution of the original decision problem (the one with large value of 7))
Efroni et al. (2018)) recently proposed another approach to mitigate the d-dependant instabilities in RL in which they study a multi-step greedy versions of the well-known dynamic programming (DP) algorithms policy iteration (PI) and value iteration (VI) (Bertsekas & Tsitsiklis 1996). Efroni et al. (2018a) also proposed an alternative formulation of the multi-step greedy policy, called r-greedy policy, and studied the convergence of the resulted PI and VI algorithms: k-PI and x- VI. These two algorithms iteratively solve -i-discoutted decision problems, whose reward has been shaped by the solution of the decision problem at the previous iteration. Unlike the biased solution obtained by solving the decision problem with a smaller value of 7, by iteratively solving decision problems with smaller ?x horizon, the x-PI and x-VI algorithms could converge an optimal policy of the original decision problem.
In this work, we derive and empirically validate model-free deep RL (DRL) implementations of x-PII and K- VL. In these implementations, we use DQN (Mnih et al. 2015) and TRPO (Schulman et al. 2015) for (approximately) solving 7y-ddiscounted decision problems (with shaped reward). which the main component of the k-PI and к- k-VI algorithms. The experiments illustrate the performance of model-free algorithms can improved by using them as solvers of multi-step greedy PI and VI schemes, as well as emphasize important implementation details while doing so.
PRELIMINARIES
In this paper, assume that the agent's interaction with the environment is modeled as discrete time discouutee Markov Decision Process (MDP), defined by M, = (S, P. R, 7. μ),, where S and A the state and action spaces; P P(s'|s, a) is the transition kernel; R r(s,a)

---

Under review as a conference paper at ICLR 2020
(0, 1) is the discount factor; and a is the initial state distribution. Let т : S + P(A) be a stationary Markovian policy, where the set A. The value of π in any state s E S is defined as (*) = EIEizo>'r( 7'r(se, x (88))]80 = 8, T. where the expectation is over all the randomness in policy, dynamics, and rewards. Similarly, the action-value function of π is defined as Q (s. ElE.>0 7'r(st, [(ss)){s
is the reward function with the maximum value of Rmax Y
P(A) is a probability distribution
s, ag = a, q|. Since the rewards have the maximum value of Rmax. both V and Q functions have the maximum value of Vinax Rmax/ (1 - ?). An optimal policy x the policy with maximum value at every state. We call the value of x² the optimal value, and define it as (s) = max, E E|Er20 ("r(se, 2
T (sx)][=0 = 5, T], Vs E S. Furthermore, we denote the state- action value of 't" as (* a) and remind the following relation holds (*(s) = max, Q" (s, a) for all 8. The algorithms by which an is be solved (obtain optimal policy) mainly based on two popular DP algorithms: Policy Iteration (PI) and Value lteration (VI). While VI relies on iteratively computing the optimal Bellman operator T' applied to the current value function V (Eq. D). PI relies on (iteratively) calculating a 1-step greedy policy Ti-sup w.r.t. to the value function of the current policy V (Eq.2):
(s)) = max Bir(so, a) + (s1) aEA
s).
S,
(1)
stsp (s) arg max E[r(sp. a) (si) so s], ss E S.
(2)
acA
It is known that T is a y-contraction w.r.t. the max norm and its unique fixed point is V and the 1-step greedy policy w.r.t. V is an optimal policy n² In practice, the state space is often large, and thus, we can only approximately compute Eqs. 2 which results in approximate PI (API) and VI (AVI) algorithms. These approximation errors then propagate through the iterations of the API and AVI algorithms. However, it has been shown that this (propagated) error can be controlled (Munos) 2003 Farahmand et al.) (2100) and after N steps, the algorithms approximately converge to solution Ty whose difference with the optimal value is bounded (see e.g.. [Scherrer 2014 for API):
(T=") TT(TNN S C5/(1 - 7) + V
In Eq. 3 the scalar (7()) = Es~gl (V==a(V"(s))) [V*(s] is the expected value function at the initial state rep-
resents the per-iteration error, and C upper-bounds the mismatch between the sampling distribution and the distribution according to which the final value function is evaluated (1x in Eq. 3. and de-
pends heavily on the dynamics. Finally, the second term on the RHS of Eq. 3 is the error due to initial values of policy/value, and decays with the number of iterations N.
3 K- G-EERD POLICY & K-PP AND K- VI ALGORIHTM
Algorithm K-Policy Iteration
Algorithm 2 n- Value Iteration
1: Initialize: x E [0. 1). No. (R)) 2: for i 0, 1.....,, NN (k) 1 do
1: Initialize: K E [0, 1]. Vo (RR)
2: for 0, L. N N(x) 1 do
3: VTa E 120 T'T m.]
3: V4+1 max, E (22))
[]]]
4: m=+1 arg max E
[=]
4: end for
5: TN()) f- arg max BI BI (1s, VN(a)
5: end for
6: Return (N()))
Return TN(())
The optimal Bellman operator T (Eq. 1 and 1-step greedy policy step (Eq. can be generalized to multi-step. The most straightforward form of this generalization is by replacing T and T-ssp with h-optimal Bellman operator and h-step greedy policy (i.e., lookahead of horizon h) that are defined by substituting the 1-step return in Eqs. and ((S0,a) + >V1),, with h-step return, actions 0g,-.-. 44-1, instead of just
h-1 r(s,,a)) (.) + VV(,), ), and computing the maximum ao (Bertsekas & Tsitsiklis, 1996). Efroni et al. (2018a) proposed an alternative form of multi-step optimal Bellman operator and multi-step greedy policy, called x-optimal Bellman operator, Tx, and k-greedy policy, Nx. for & E [0, i.,.
Eizo
(T&V)(s) max E Σ>
(T V) so s),
E
(4)
(T(()) E arg max E
(a,,) V) 80 s, Vs S,
(5)
120
V*N) w.r.t. the initial state distribution j.. Note that the I.HS of Eq. is the f--nrrm of (V
2

---

Under review as a conference paper at ICLR 2020
where the shaped reward re (R. V) w.r.t. the value function V is defined
(e, V) = r8t,, 0+) + (1 (8)+1)))
(6)
can be shown that the k-greedy policy w.r.t. the value function V is the optimal policy w.r.t. a n- weighted geometric average of all future h-step returns (from h = 0 to 20). This can be interpreted as TD(A) (Suttonn Barto 2018) for policy improvement (see Efroni et al. 2018a| Sec. 6). The important difference is that TD(A) is used for policy evaluation and not for policy improvement.
From Eqs. andd [ it is easy to see that solving these equations equivalent to solving a surrogate yX-discounted MDP with the shaped reward (x V), which we denote by (V) throughout the paper. The optimal value of (V) (the surrogate MDP) is TvV and its optimal policy is the n-greedy policy, Te. Using the notions of k-optimal Bellman operator, Tx. and k-greedy policy, Te. Efroni et al.] (2018a) derived r-PI and Æ-VI algorithms, whose pseudocode is shown in Algo- rithms I andd 2 R-PI iteratively (i) evaluates the value of the current policy Ty and (ii) set the new policy, 1, to the n-greedy policy w.r.t. the value of the current policy V*, by solving Eq. 5 On the other hand, V- repeatedly applies the Tr operator to the current value function V; (solves Eq. 4 to obtain the next value function, Vi+1. and returns the K-greedy policy w.r.t. the final value VN(x))- Note that for = O, the k-greedy policy and k-optimal Bellman operator are equivalent to their 1ssee counterparts, defined by Eqs. [and which indicates that k-PI and k- VI are generalizations of the seminal PI and VI algorithms.
It has been shown that both PI and VI converge to the optimal value with an exponential rate that depends on the discount factor 7, i.e., | yay I O(7A) (see e.g., Bertsekas & Tsitsiklis,
1996 Scheerer 2013). Analogously, Efroni et al. (0188) showed that k-PI and K- converge with
faster exponential rate of {(x)
2(1-k) 2,i.e. |V' V 1l S (()), with the cost
I-76
that each iteration of these algorithms computationally more expensive than that of PI and VI. Finally, we state the following two properties of x-PI and k-greedy policies that we use in our RL implementations of s-Pl and K- VI algorithms in Sections [5
1) Asymptotic performance depends on k. The following bound that is similar to the one reported in Eq. B was proved by Efroni et al. (2018b) Thm. 5) for the performance of R-Pl:
n((T)) - (T(T(())) S ((x))())/(11)))) + E(Ks) Vimax
Asymptotic Term
Decaying Ter
3 Note that the first term on the RHS of Eq. iss independent of N (se), while the second one decays with (K)).
where 8(k) and C(x) are quantities similar to 8 and C' Eq.
2) Soft updates w.e.t a k-greedy policy does not necessarily improve the performance. Let my be the k- --grredy policy w.r.t. V*. Then, unlike for 1-step greedy policies, the performance of (1 -a)r+-amm (soft update) is not necessarily better than that of π (Efroni et al. [0188] Thm. 1). This hints that it would be advantages to use K-greedy policies with 'hard' updates (using n5 as the new policy),
4 RL IMPLEMENTATIONS OF K-PI AND K-VI
As described in Sec. B] implementing x-PI and K- V- requires iteratively solving a disduuucdd surrogate MDP with a shaped reward. If model of the environment is given, the surrogate MDP can be solved using a DP algorithm (see Effroni et al.) 2018a Sec. 7). When the model is not available, it can be approximately solved by any model-free RL algorithm. In this paper, we focus on the case that the model is not available and propose RI. implementations of k-PI and R-VI. The main question we investigate in this work is how model-free RL algorithms should be implemented to efficiently solve the surrogate MDP in K-Pl and K- KVV
In this paper, we use DQN (Mnih et al. 2015) and TRPO (Schulman et al. 2015) as subroutines for
estimating a K- k-greedy policy (Line 4 in RI. Alg. I and Line 5 in x- VI, Alg. 2 or for estimating an optimal value of the surrogate MDP (Line 3 in x- VI. Alg. 2) For estimating the value of the current policy (Line 3, in ksPI, Alg. D. we use standard policy evaluation deep RI. (DRL) algorithms.
To implement K-PI and VI, we shall set the value of ((s) E N, i.e., the total number of iterations of these algorithms, and determine the number of samples for each iteration. Since N(K) only appears in the second term of Eq. 7 an appropriate choice of N(s) is such that C(s)6(s)/(1 7) ~2 ((x) V Vmaax- Note that setting N (1s) to a higher value would not dramatically improve the
3

---

Under review as a conference paper at ICLR 2020
Algorithm 3 K-PIID
1: Initialize replay buffer D. Q- Q-networks Qe. Qs, and target networks Qo. Qg:
2: for i =0 ,,.., (x)) ((x))
-
do
3: # *Policy Improvement
4: for = 1,..., T(x) do
5: Act by e-greedy policy w.r.t. Qa(ss; a), observe rt, 9c+1, and store (st, de, Por 8t+1) D;
6: Sample a batch {[5,, a, 8541) ", from D;
7: Update by DQN rule with (5,, (1s, Vo), (541)) ))
where
8:
(o(5,a1)= = Q4(5441, (8)44)) and T=-1(5) arg max. (o(s,a);
9:
Copy to 8 occasionally (6' -- 8):
end for
Policy Evaluation (8) E arg max (6(
12:
for = 1, T(x) do
Sample a batch {(sy, ry, S5+1 S5t1 )) from D:
14:
Update & by TD(O) off policc rule with {(s,, an, (5)n)) and mT(s)) arg max. (s(s,));
15:
Copy & occasionally (d' + Ø);
16:
end for
17:
end for
performance, because the asymptotic term in Eq. iis independent of (R).. In practice, since 5())
and ((x) are unknown, we set (1s) to satisfy the following equality:
{(K))N(>> = CFA.
(8)
that depends on the final-accuracy we are aiming for. For example, if we expect the final accuracy being 90%, we would set CF 0.1. Our results suggest that this approach leads to reasonable choice for (KK), e.g., N(x = 0.99) = 4 and N(x 0.5) = 115, for CF = 0.1 and 7 0.99. As we increase K. we expect less iterations are needed for k-PI and K- VI to converge good policy. Another important observation is that since the discount factor of the surrogate MDP that к-PI and R-VT solve at each iteration is ryc, the effective horizon (the effective horizon of "x--discounted MDP is 1/(1 7x)) of the surrogate MDP increases with K.
where C'AA is
Lastly, we need to determine the number of samples for each iteration of k-PI and x-VL. We allocate equal number of samples per iteration, denoted by T(x). Since the total number of samples, T, is known beforehand, we set the number of samples per iteration to
= TTN(s).
DQN AND TRPO IMPLEMENTATIONS OF K- R-PI AND K- VI
In this section, we study the use DQN Mnii al. 2015) and TRPO (Schulman al. 2015 in k-PI and x- VI algorithms. We first derive our DQN and TRPO implementations of s-PI and k- VI in Sections 5.1 and 5.2 We refer the resulting algorithms as x-PI-DQN, K- VI-DQN, -RPI- and K- --RI-T It important to note that for = 1, K- R-PI-DON and ς- R-VI-DQN are reduced to DQN, and R-PI-TRPO and K- VI-PPO are reduced to TRPO. We then conduct set of experiments with these algorithms, in Sections 5.1.I and 5.2.1 in which we carefully study the effect of и and ((x) (or equivalently the hyper-parameter CFA, defined by Eq. 8) on their performance. these experiments, specifically focus on answering the following questions:
1. Is the performance of DQN and TRPO improve when using them as k-greedy solvers in K-PI and k- VT? Is there a performance tradeoff w.r.t. x??
2. Following k-PI and x- II, our DQN and TRPO implementations of these algorithms devote a significant number of sample T(k) to each iteration. Is this needed or a 'naive' choice of
T(x) = 1, or equivalently (w)) T, works just well, for all values of x?
5.1 DQN IMPLEMENTATION OF K-PI AND K- VI
Algorithm B contains the pseudo-code of P--PIDDN. Due space constraints, report its de- tailed pseudo-code in Appendix A.I (Alg. 5) the policy improvement stage k- w-PL--QN, we DON to solve the " surrogate MDP with the shaped reward re(K, V V*--t),
4

---

Under review as a conference paper at ICLR 2020
Breakout,
Ciay 9.05
100 seseee 10
045.9
03
3.6
68
08
10
6:2
2.4
6.
00
30
Ureakout,, M/. -
Breakout, Cra - 0.95
16
3.4
6.1
Time aiaos
Timm staps
Figure 1: Training performance of k- K-PI-DOON (Top) and K-VI-DON (Bottom) on Breakout, for the hyper-parameter CFA = 0.05 (right) and for the 'naive' baseline N()) = T (left).
i.., at the end of this stage Mv,) The output of the DQN is approximately the optimal Q- function of Myx MM))V,), and thus, the k-greedy policy w.r.t V, is equal arg max, Qa(:aa). At the policy evaluation stage, we use off-policy TD(0) to evaluate the Q-function of the current policy TT. i.e., Qs QT Although what is needed on Line 8 is an estimate of the value function of the current policy, V ~ V=--1, we chose to evaluate the Q-function of πद: the data in our disposal (the transitions stored in the replay buffer) is an off- off-policy data and the Q-function of fixed policy can be easily evaluated with this type of a data using off-policy TD(0), unlike the value function.
Remark In order for Ve to be an accurate estimate of the value function of T4-1 on Line we should use an additional target network, Q'. that remains unchanged during the policy improvement stage. This network should be used in (.-)(.) arg max Q'(-, a) on Line and be only updated right after the improvement stage on Line 77 However, to reduce the space complexity of the
algorithm, do not use this additional target network and compute πT-1 on Line 8 as arg max Q/ despite the fact that Q' changes during the improvement stage.
We report the pseudo-code of x- x-VI-DQN in Appendix A.1 (Alg. 6). Note that k-VI simply repeats V + Tr V and computes T, V, which is the optimal value of the surrogate MDP Myx(V.. In repeatedly solve M,x (V) by DQN, and use its optimal Q-function to shape the reward of the next iteration. Let 0 and V V be the optimal Q and V functions of (V).
k- R--VI-DO,,
T 7x, (s) = (T))) where the first equality is by definition (Sec. 2 and the second one holds since Tę V is the optimal value of (y)(V) (Sec. 3 Therefore, in k- VI-DON, we shape the reward of each iteration by max, Qs(s,) a), where Qo is the output of the DQN from the previous iteration, i.c., max, a)) ~ 1
Then, we have max, (s,,v((s, = V
5.1.1 K-PI-DQN AND K- VI-DQN EXPERIMENTS
In this section, we empirically analyze the performance of the R-PIIDQNN and k- VI-NN algorithms on the Atari domains: Breakout, Seaquest, Spacelnvaders, and Enduro (Bellemare et al. 2013). We start by performing an ablation test on three values of parameter Cra (0.001, 0.05, 0.2 on the Breakout domain. The value of CFA A sets the number of samples per iteration T(x) (Eq, 8) and the total number of iterations (()) (Eq. 9). Aside from CFA. we set the total number of samples to T ~ 10 This value represents the number of samples after which our DQN-based algorithms approximately converge. For each value of CFA, test x- R-PI-DON and µ- x-VII for several & values. In both algorithms, the best performance was obtained with Cra = 0.05, thus, we set CrA = 0.05 in our experiments with other Atari domains.
5

---

Under review as a conference paper at ICLR 2020
Domain
Alg.
Ribest
K
DON,
[(x) = 7, Abbet
224:15, K=0.68
160(1:)
Breakout
131
171 x=0.68
K- VI
180ct5) k=0.68
179
R-PI
747(:23), k=0.84
611(215)
SpaceInv.
685t=24)
695;=16, x=
R- VI
707:132) 6=0.36
669(1:16)
R-PI
5159;45mm k=0.84
(+281)
Seaquest
3207
437 I (=:40) k=0.84
R- VI
3394(136),
k=0.36
263 (11:996)
R-PI
544 0=0.84
37 (1:15))
Enduro
355(=52)
547(117,, x=0.68
V-VI
499, 0=0.84
492 (#228
R--I
3968, 178), 1=1.0
1654
BeamRider
3968(178))
3968 k=1.0
K-V
4077 (=30), x=0.8
4052 (=462)
R-PI
8276:1200,
0.36
6900
Qbert
7322(=280)
8042 x=0.92
V-
7924 (-267), K=0.68
7585 (4:587)
Table 1: The final training performance of K-PI-DON and K-VI-DQN on the Atari domains, for the hyper-parameter CFA 0.05. The values represent the empirical mean + empirical standard deviation.
Figure I shows the training performance of k-PI-DQN (Top) and k- s-VI-DQN (Bottom) for the best value of CF 0.05, as well for the 'naive' baseline T(k) 1, or equivalently N(x) = T, on Breakout, The results on Breakout for the other values of CFΛ and the results the other Atari domains for CF = 0.05 have been reported in Appendix A.2 Table shows the final training performance of K- x-PI-DQN and x- x-VI-DQN on the Atari domains with CPA 0.05. Note that the scores reported in Table D are the actual returns of the Atari domains, while the vertical axis in the plots of Figure corresponds to scaled return. We plot the scaled return, since this way it would be easier to reproduce our results using the OpenAl Baselines codebase (Hill et al. 2018).
The results of Fig. and Table I as well those in Appendix A.2, exhibit that both K- P--DIDONN and R- VI-IDN improve the performance of DQN (k = 1). Moreover, they show that setting N(x) = T leads to clear degradation of the final training performance on all of the domains expect Enduro, which attains better performance for N N(x) = T. Although the performance degrades, the results for (x:) T are still better than for DQN.
5.2 TRPO IMPLEMENTATION OF K- K-PI AND VI
Algorithm 4 contains the pscudo-code of R-PI-TRPO (detailed pscudo-code in Appendix A.1 TRPO iteratively updates the current policy using its return and an estimate of its value function. In x-PI-TRPO, each iteration i: 1) use the estimate of the current policy V/ V (com- puted in the previous iteration) calculate the return R(x, K, VV) and an estimate of the value function Ve of the surrogate MDP (M.. 2) we use the return R(s, Vy) and V9 to compute the new policy T, and 3) we estimate the value of the new policy Va V* on the original, 7 discounted, MDP.
In Appendix B.I we provide the pseudocode of K- VI-TPPO derived by the k-VI meta algorithm. As previously noted, V- iteratively solves the 7E discounted surrogate MDP and uses its optimal value T, Vi-1 to shape the reward of the surrogated MDP in the i'th iteration. With that in mind, consider x-PI-TRPO. Notice that as тh converges the optimal policy of the surrogate 7x discounted MDP, VÚ converges to the optimal value of the surrogate MDP, i.c., it converges to V = T2 V- Thus, k-PI--RRO can be turn to k- VI-TRP by eliminating the policy evaluation stage, and simply copy + 0. meaning, V + V/- = T.V..
5.2.1 K- PI--TO AND K- VI-TRPO EXPERIMENTS
In this section, we empirically analyze the performance of the K-PI-TRPO and K- K-VI-TRPO algo- rithms on the MuJoCo domains: Walker2d-v2, Ant-v2, HalfCheetah-v2 HumanoidStandup-v2 v2, and Swimmer-v2, (Todorov et al., 2012). As in Section 5.1.1 we start by performing an ablation test on the parameter CFA = (0.001, 0.05, 0.2} on the Walker domain. We set the total number of iterations to 2000, with each iteration consisting 1000 samples. Thus, the total number of samples is T 2 x 10 This is the number of samples after which our TRPO-based algorithms approximately converge. For each value of CFA. test k-PI x-PP-TRPO and R- VI-TPO for several values. In both algorithms, the best performance was obtained with CFA = 0.2, thus, we set CrA = 0.2 in our experiments with other MuloCo domains.

---

Under review as a conference paper at ICLR 2020
Algorithm 4 PP--PP
1: Initialize -ntworrss V4 and Va. policy network wg. and target network Vd:
2: for i= "=,
do
3: for t-= = I..... , [x) do
4: Simulate the current policy Ty for M steps and calculate the following two returns for all steps j:
5:
(K, V =
(vx)"")) (rx))" V2) and Pj = AM 2r;
6:
Update 0 by minimizing the batch loss function:
Lve N (V Rr Vo))
7:
Policy Improvement
8:
Update vi using TRPO by the batch (K Vi), Vo(ss))))
9:
Policy Evaluation
10: Update & by minimizing the batch loss function:
Lv2 N (y=((((()) - -p)33
11: end for
12: Copy @ & (0' r 3):
13:
end for
Walker,
Walker, Caa 0.2
Welker GAE
Vozi Elioos
Bernitons
Iteratione
Penaoooss
Walker,
Walker, Cra
Noa 130000
130
130
250
300
3000
1290
2500 3750 3000
254
500
15
X0X
2530 2350
3150
300
Figure 2: Training performance of k- T-PP-TRPO (Top) and k- x-VI-TRPO (Bottom) on Walker, for the hyper-parameter CFA 0.2 (right) and for the 'naive" baseline N(x) T (left).
Figure shows the training performance of PIP--TR (Top) and к- VI-PO (Bottom) for the best value of CFA = 0.2, as well as for the 'naive' baseline Txx) 1, or equivalently Nxx T, on Walker. The results on Walker for the other CFA values and the other MuJoCo domains for CPA = 0.2 have been reported in Appendix B.3 Table 2 shows the final training performance of
k-PI-TRPO and K- VI-TRPO on the MuloCo domains with CFA 0.2.
The results of Figure 2 and Table 2 as well as those in Appendix B.3 exhibit that both K-PI-TRPO and k-VI-TRPO yield better performance than TRPO (x 1). Furthermore, they show that the algorithms with CrA = 0.2 perform better than with ((R) = T. However, the improvement is less
significant relative to the DQN-based results Section 5.1.]
5.2.2 COMPARISON WITH THE GENERALIZED ADVANTAGE ESTIMATION ALGORITHM
There is an intimate relation between ssPPI and the GAE algorithm Schulman et al. (2016) which we elaborate on in this section. In GAE the policy is updated by the gradient:
VoEs~a(VV (s)] = Bxondara
V log (50) )o)) Σ (TA))
; 8(V) = +r - Ve, (10)
which can be interpreted as a gradient step in a y discounted MDP with rewards 5(V), which we refer here M As noted in Efroni et al. 2018a). Section 6, the optimal policy of the MDP M is the optimal policy of Myy((V) with i X, i.e., the s-greedy policy w.r.t. V: thus, the 7d

---

Under review as a conference paper at ICLR 2020
Domain
Alg.
Wbbest
0
TRPO, R
[(K)
Abest
GAE
K-PI
1352(4239), x=0.68
1205 (1:99)
Walker
560 (=:177)
1158(479, k=0.36
1664 A=0.36
K-VI
227 k=0.68
169))125)
K-P1
1359(1:36),
k=0.68
1083<4:208)
Ant
-18.47(
1225(+141) ==0.0
1152 A=0.0
K-VI
2916(14555, k=0.68
1809(1.44)
K-PI
1367 x=0.36
155
HalfCheetah
74
1450;+300) k=0.36
1453 A=0.36
K- V-
1735(1800), ==0.36
(078(1148)
R-PI
1974) k=0.99
13486(+1211)
HumanoidStand
(7545(11545)
72588:11929), ===0998
71420:11001, X=0.98
K-VI
74063+1179) k=0.99
11323
R-PI
108; 1=1.0
43c13)
Swimmer
108(+17)
108 k= 1.0
108:1100 À 1.0
K-VI
108:+17), k=1.0
46
R-PI
1872(4199, 6=0.68
805(4:291)
Hopper
1193(235)
1491(115), x=0.66
1745 À 0.68
R-V1
1043(495), k=0.92
590(1:246
Table 2: The final training performance of K-PI-TRPO and K- x-VI-TRPO on the MuJoCo domains, for the hyper-parameter CFA = 0.2. The values represent the empirical mean empirical standard deviation.
Breakout, Lowering y
Spacelreaders, Lowering
6.2
3.6
6.2
00
13
6:2
0.4
6.1
08
33
Welker Lowering Y
Ank-v2 Lowering
0.00
1808
Meam Ectodde
Perotions
Beratons
Figure 3: Lowering the discount factor
optimal policy of M is the k-greedy policy w.r.t V. GAE, instead of solving the r-greedy policy while keeping V fixed, changes the policy and updates V by the return concurrently. Thus, this approach is conceptually similar to x-PI-TRPO with ((x) = T. There, the value and policy concurrently updated as well, without clear separation between the update of the policy and the value.
In Figure and Table 2 the performance GAE is compared to the one of k-PI-TRPO and k- -- TRPO. The performance of the latter two is slightly better than the one of GAE.
Remark 2 (Implementation of GAE) We used the OpenAl baseline implementation of GAE with small modification. In the baseline code, the value network is updated w.r.l. the target E (r))r,
whereas in Schulman et al. (2016) the authors used the target Σ, Y (see Schulman et al 2016 28) We chose latter form in our implementation be accord with Schulman et al. 2016
5.3 DQN AND TRPO PERFORMANCE VERSUS THE DISCOUNT FACTOR
To supply with more complete view our experiments, we tested the performance of the "vanilla" DQN and TRPO when trained with different Y values than the previously used one (y = 0.99). As evident in Figure 3 only for the Ant domain this approach resulted in improved performance when for TRPO trained with y = 0.68. It interesting to observe that for the Ant domain the performance of x-PI-TRPO and especially of s-VI-TRPO (Table significantly surpassed the one of TRPO
8

---

Under review as a conference paper at ICLR 2020
trained with 7 0.68. The performance of DQN and TRPO on the Breakout, SpaceInvaders and Walker domains decreased or remained unchanged in the tested y values. Thus, on these domains, changing the discount factor does not improve the DQN and TRPO algorithms, using k-PI or R-VI with smaller &: value do.
It is interesting to observe that the performance on the Mujoco domains for small % e.g.. 7 0.68, achieved good performance, whereas for the Atari domains the performance degraded with lowering 7. This fits the nature of these domains: in the Mujoco domains the decision problem inherently has much shorter horizon than in the Atari domains.
Furthermore, it is important to stress that y and are two different parameters an algorithm designer may use. For example, one can perform scan of value, fix to the one with optimal performance, and then test the performance of different values.
DISCUSSION AND FUTURE WORK
In this work formulated and empirically tested simple generalizations of DQN and TRPO de- rived by the theory of multi-step DP and, specifically, of k-PI and x-VI algorithms. The empirical investigation reveals several points worth emphasizing.
K-PI is better than k- V-VI for the Atari domains.. most of the experiments on the Atari domains R-PI-DDN has better performance than k- x-VI-- This might be expected the former uses extra information not used by the latter: R-PI estimates the value of current policy whereas VI ignores this information.
2. For the Gym domains K- VI performs slightly better than k-PI. For the Gym domains λ-- VI-TRPO performs slightly better than K-PI-TRPO. We conjecture that the reason for the discrepancy relatively to the Atari domains lies in the inherent structure of the tasks of the Gym domains: they are inherently short horizon decision problems. For this reason, the problems can be solved with smaller discount factor (as empirically demonstrated in Section (.3) and information on the policy's 's value is not needed.
3. Non trivial value improves the performance. In the vast majority of our experiments both k-PI and k-VI improves over the performance of their vanilla counterparts (i.e., k = 1), except for the Swimmer and BeamRider domains from Mujoco and Atari suites. Impor- tantly, the performance of the algorithms was shown to be 'smooth' in the parameter k. This suggests careful hyperparameter tuning of is not of great necessity.
4. Using the 'naive' choice of N (k) T deteriorates the performance. Choosing the number of iteration by Eq. [ imppooees the performance on the tested domains.
An interesting future work would be test model-freer algorithms which other variants of greedy policies (Bertsckas & Tsitsiklis 1996; Bertsekas] 2018;) Efroni et al., 2200 8a] Sun et al.) 2018 Shani
eet al. 2019). Furthermore, and although in this work we focused model- free DRL, is arguably more natural to use multi- step DP in model-based DRL (e.g. Kumar et al.) 2016 Talvitie 2017 Luo al., 2018 Janner al., 2019). Taking this approach, the multi-step greedy policy would be solved with an approximate model. We conjecture that in this case one may set x or more generally, the planning horizon-
function of the approximate model's 'quality': as the approximate model gets closer to the real model larger д can be used. We leave investigating such relation in theory and practice future work. Lastly, an important next step in continuation to our work is to study algorithms with an adaptive parameter. This, we believe, would greatly improve the resulting methods, and possibly be done by studying the relation between the different approximation errors (i.e.. errors in gradient and value estimation, Ilyas et al. 2018), the performance and the value that should be used by the algorithm.
REFERENCES
L. Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning, pp. 30-37, 1995.
M. Bellemare, Y. Naddaf, Veness, and M. Bowling. The arcade learning environment: An evalu- ation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.

---

Under review as a conference paper at ICLR 2020
D. Bertsekas and J. Tsitsiklis. Neuro-dynamic programminng, volume 5. 1996.
Dimitri P Bertsekas. Feature-based aggregation and deep reinforcement learning: A survey and some new implementations. IEEE/CAA Journal of Automatica Sinica, 6(1):1-31, 2018.
Y. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Beyond the one step greedy approach in rein- forcement learning. In Proceedings of the 35th International Conference on Machine Learning. 2018a.
Y. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Multiple-step greedy policies in approximate and online reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5238- 5247, 2018b.
A. Farahmand, C. Szepesvári, and R. Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, pp. 568-576, 2010.
E. Greensmith, P. Bartlett, and J. Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5(Nov):1471-153)) 2004.
A. Hill, A. Raffin, M. Ernestus, A. Gleave, A. Kamervisto, R. Traore, P. Dhariwal, C. Hesse, O. Klimov, A. Nichol, M. Plappert, A. Radford, J. Schulman, S. Sidor, and Y. Wu. Stable base- lines. https: / com/hill hill- meailllasstein a/stab basaableebsselleeee lines] 2018.
Andrew Ilyas, Logan Engstrom, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Are deep policy gradient algorithms truly policy gradient algo- rithms? arXiv preprinl arXiv: 181 1.02553, 2018.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. arXiv preprint arXiv:1906.082. 2019.
N. Jiang, A. Kulesza, S. Singh, and R. Lewis. The dependence of effective planning horizon on model accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 1 1181-1189 189, 2015.
Vikash Kumar, Emanuel Todorov, and Sergey Levine. Optimal control with learned local models: Application to dexterous manipulation. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 378 -333.. IEEE, 2016.
S. Levine, C. Finn, T. Darrell, and P. Abbeel. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, 17(): 2016.
2016.
T. Lillicrap, J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 559.00997, 2015.
Lu, D. Schuurmans, and C. Boutilier. Non-delusional q-learning and value iteration. In Pro- ceedings of the 32nd International Conference Neural Information Processing Systems, pp- 9971-9981, 2018.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorith- mie framework for model-based deep reinforcement learning with theoretical guarantees. arXiv preprint arXiv:1807.03885, 2018
V. Mnih, K. Kavukcuoglu, D. Silver, A. A Rusu, J. Veness, M. Bellemare, A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
R. Munos. Error bounds for approximate policy iteration. In Proceedings of the 20th International Conference on Machine Learning, pp. 560-567, 2003.
R. Munos. Error bounds for approximate value iteration. In Proceedings of the 20th National Conference on Artificial Intelligence, pp. 1006-1011, 2005.
M. Petrik and B. Scherrer. Biasing approximate dynamic programming with a lower discount factor. In Advances in neural information processing systems, pp. 1265-1272, 2009.
10

---

Under review as a conference paper at ICLR 2020
B. Scherrer. Improved and generalized upper bounds the complexity of policy iteration. In Advances in Neural Information Processing Systems, pp. 386-394, 2013.
B. Scherrer. Approximate policy iteration schemes: a comparison. In International Conference on Machine Learning, pp. 1314-1322, 2014.
Schulman, Levine, Abbeel, M. Jordan, and P. Moritz. Trust-region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Picter Abbeel. High- dimensional continuous control using generalized advantage estimation. Proceedings of the International Conference Learning Representations (ICLR), 2016.
Lior Shani, Yonathan Efroni, and Shie Mannor. Exploration conscious reinforcement learning visited. In International Conference on Machine Learning, 5680-5689, 2019.
D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, Lai, A. Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550 (7676):354, 2017.
Wen Sun, Geoffrey J Gordon, Byron Boots, and J Bagnell. Dual policy iteration. In Advances in Neural Information Processing Systems, pp. 7059-7069, 2018.
R. Sutton and A. Barto. Reinforcement learning: An introduction. 2018.
Erik Talvitie. Self-correcting models for modellbased reinforcement learning. In Thirty-Firss AAAI Conference on Artificial Intelligence, 2017.
Thrun and A. Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the Connectioniss Models Summer School, pp. 255-263, 1993.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In IEEE/RSI International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
H. Van Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double Q-learning. In Thirtieth AAAI conference on artificial intelligence, 2016.

---

Under review as a conference paper at ICLR 2020
A DQN IMPLEMENTATION OF K-PI AND K- X-VI
A. PSEUDO-CODES
In this section, we report the detailed pseudo-codes of the k-PI-DQN and k-VI-DQN algorithms, described in Section 5.1 side-by-side.
Algorithm P--IDO
1: Initialize replay buffer DD and Q- Q-networks Qo and Qa with random weights @ and Ø;
2: Initialize target networks Q/ and Q' with weights 8 + and + o;
3: for i= 0,..,, ((s) - do
4: # Policy Improvement
5: for , ((() do
6: Select d, c-greedy action w.r.t. Qo(st, a);
7:
Execute a, observe r and 8t-1, and store the tuple (st. az, rz. 8141) in D;
8:
Sample random mini-batch ((8j, 0j. ry 8841 }3 from D;
9:
Update 0 by minimizing the following loss function:
10:
= N (Qo(s), az) (ry(K, Vg) 7o maxaaQ((j+11
where
Vo($)41) = Qo(s,-1, (1,1())+1))
and TT-1(85+1) E arg max, (/(5)-1.00) o);
12:
Copy 0 to l' occasionally (0' - 0);
end for
14: # Policc Evaluation
Set (s) E arg max, (s,
16:
for t' = 1,..... (xx) do
17:
Sample random mini-batch {(8), 0g ry ()+1)}}= from D; Update by minimizing the following loss function:
18:
19:
Le. = + Σ (Qo(s),a,) - (r, +
20: Copy & to ø' occasionally (0' + 6):
21: end for
22:
end for
Algorithm 6 k- VI-DQN
Initialize replay buffer D, and Q-networks Qo and Qs with random weights 0 and Ø:
2: Initialize target network Q' with weights 0' <- 0;
3: for i= 0, O..... N(s)
do
4: # Evaluate T, Vo and the x-greedy policy w.r.t. Va
5: for 1,. (K) do
6: Select a, c-greedy action w.r.t. Qo(se, a);
7:
Execute a,, observe r2 and 8t-1, and store the tuple (st, az, rı, $141) in D;
8:
Sample random mini-batch {(s), Ty. 8541 (.1)) ) from D;
9:
Update 0 by minimizing the following loss function:
10:
= I (Qo(s),ay) (ry(k, Vo) my max, (6(()+1, where Vo(o)41) Q6(1)-1, ((8+1)) and m(8441) arg max, (b(8++1:a):
11:
12:
Copy 0 to 0' occasionally (0' -);
end for
14: Copy 0 to Φ (ø 0)
end for
12

---

Under review as a conference paper at ICLR 2020
Hyperparameter
Value
Horizon (T)
1000
Adam stepsize
x 10
Target network update frequency
1000
Replay memory size
100000
Discount factor
0.99
Total training time steps
10000000
Minibatch size
32
Initial exploration
Final exploration
Final exploration frame
1000000
#Runs used for plot averages Confidence interval for plot runs
4
70%
Table Hyperparameters for k-PI-DQN and <--I-....
A.2
ABLATION TEST FOR CFA
Breakout, CFΛ 0.05
Breakout, CyΛ 0.2
Mean epicode scaled reward
Mean episode scaled reward
12
10
19
k=0.0
--0.68
k-0.68
k-0.64
k-0.84
k-0.96
k-0,30
k-0.99
k-0.90
k=0.30
0.6
Time steps
Time steps
Breakout, CFa = 0.001
34
Mean episode scaled reward
12
20
A-0.0
A-0.36
^=0.68
4:0 84
6-0.92
A-0.96
a-0.66
0-9.9
Time steps
Figure 4: Performance of k-PI-DQN and x-VI-DQQ on Breakout for different values of CFA
A.3 K-PI-DQN AND K- VI-DQN PLOTS
In this section, report additional results of the application of s-PI-DQN and >-VII the Atari domains. A summary of these results has been reported in Table I in the main paper.
13

---

Under review as a conference paper at ICLR 2020
Spacelnvaders, M₂
Spacelnvaders, CFA 0.05
20.0
20.0
Mean episode scaled reward
130
15.0
100
k-0.36
10.0
=:0.08
x=0.60
x:0
x:0 Rd
5.
k-0.95
5.0
k-0.96
x=0.98
k=0.08
k=1.8
0.0
0.0
0.0
0.6
0.8
1.0
0.0
0.4
0.8
0.8
Time steps
le/
Time steps
le/
Spacelnvaders, Cra 0.05
20.0
Mean episode scaled reward
15.0
12.5
4-0.6
10.0
--0.6
^-0.84
^m0.02
A-0.56
4-0.90
A=0.09
Time steps
Figure 5: Training performance of R-PI-DQN (Top) and k- VI--ON (Bottom) on SpaceInvaders, for the hyper-parameter CrA = 0.05 (right) and for the 'naive' baseline N(s) T (left).
14

---

Under review as a conference paper at ICLR 2020
Seaquest,
Seaquest, CFA 0.05
k-0.0
K-0.0
Mean episade oraled roward
Meon episade scaled reward
20
k-0.8
50
X=0.8
x=0.84
K=0.84
80
x=0,92
40
0.092
k-0.90
k-0.98
5
.-0.00
30
k-0.00
20
20
30
0.0
0.6
0.8
1.0
0.8
0.8
Time steps
Time steps
le/
Seaquest, Cfa 0.05
60
8=0.0
Mean episode scaled reward
50
x-0.54
40
A-0.92
30
k=0.99
6-10
20
30
Time steps
Figure 6: Training performance of R-PI-DQN (Top) and k- VI-DON (Bottom) on Seaquest, for the hyper-parameter CrA = 0.05 (right) and for the 'naive" baseline N(s) = T (left).
15

---

Under review as a conference paper at ICLR 2020
Enduro, N₂ T
Enduro, CFa 0.05
620
600
K-0.0
Meen apisode scaled raward
Mean episode scaled reward
300
300
K=0.80
K=0.84
429
6-00
400
36
K-0.58
300
300
k=0.00
<=0 8
<
X00
200
100
100
0
0.2
0.4
0
0.8
10
0.0
0.2
0.8
1.0
Time steps
Time steps
le/
Enduro, CFA 0.05
600
8=0.0
Mean episode scaled reward
500
6-0.54
400
A-0.92
A-0 59
4-10
100
Time steps
Figure 7: Training performance of k-PI-DONN (Top) and Æ- VI-DON (Bottom) on Enduro, for the hyper-parameter CrA = 0.05 (right) and for the 'naive" baseline N(s) = T (left).
16

---

Under review as a conference paper at ICLR 2020
BeamRider, Nr
BeamRider, Cp4 0.05
Mean episade ozaled rowar
Meon episode scaled reward
k-0.36
=:0.88
==0.00
x:0
x:0 Rd
k-0.95
k-0.06
x=0.98
k=0.08
0.0
0.4
0.8
1.0
0.4
0.6
0.8
Time steps
Time steps
le/
BeamRider, CFA 0.05
25
Mean episode scaled reward
20
400
^-0.84
0m0002
A-0.66
4-0.90
A=0.09
Time steps
Figure 8: Training performance k-PI-DQN (Top) and K- VI-DNN (Bottom) on BeamRider, for the hyper-parameter CrA 0.05 (right) and for the 'naive' baseline N(s) 7 (left).
17

---

Under review as a conference paper at ICLR 2020
Qbert, N, T
Qbert, CFa 0.05
35
Mean episade ocaled moward
50
Meon episode scaled reward
-30
=:0.88
==0.00
x:0
x:0 Rd
k-0.95
k-0.06
ke0.98
k=0.08
5
5
0
0.0
0.2
0.4
0.8
1.0
02
0.4
0.8
0.8
10
Time steps
Time steps
Obert, CFA
0.05
35
Mean episode scaled reward
10
25
400
15
^-0.84
0m0002
A-0.66
4-0.90
A=0.09
Time steps
Figure 9: Training performance R-PI-DQN (Top) and K- <-VI-D (Bottom) on Qbert, for the hyper-parameter CrA = 0.05 (right) and for the 'naive' baseline N(s) = T (left).
18

---

Under review as a conference paper at ICLR 2020
B TRPO IMPLEMENTATION OF x-PI AND K- VI
B.1 PSEUDO-CODES
In this section, we report the detailed pseudo-codes of the x-PI-TRPO and x-VI-TRPO algorithms, described in Section 5.2 side-by-side.
Algorithm 7 k- PI-PORRPO
1: Initialize V-networks Vo and Vg. and policy network TΦ with random weights 8, ø, and &b
2: Initialize target network Vi with weights o'
3: for i= 0, ((s) - do
4: for = 1, ..... (+) do
5: Simulate the current policy TΦ for M time-steps;
6: for 1,..., MM do
7: Calculate (N, V2) E (76) Vi) and Pj = Di=EEs M 7'
8: end for
9:
Sample random mini-batch {(8j, Oj. rj 8 1) from the simulated M time-steps;
Update by minimizing the loss function:
Lv, = N Eソ= (Vo(s;) - R, V(D)
# Policy Improvement
12:
Sample random mini-batch {(s), (6. "y. 8 13== from the simulated M time-steps;
13:
Update using TRPO with advantage function computed by ((R Vg), V8 )
14:
# Policy Evaluation
15:
Sample random mini-batchh {(sj, Oj. Fj. 15+1))+111111 1)55 from the simulated M time-steps;
Update by minimizing the loss function: end for
Dv. Ej - p,)²
18: Copy & to o' (Ø' +);;
end for
Algorithm 8 k- VI-TRPP
1: Initialize V-network Vo and policy network TΦ with random weights 0 and 3/;
2: Initialize target network V/ with weights Φ': 0:
3: for i= 0,..... ((x) - do
4: # Evaluate T, and the x-greedy policy w.r.t. V%
5: fort ., T(x) do
6: Simulate the current policy ue for M time-steps;
7: for 1,..., M do
8: Calculate (N, Vi) = EM (TK)* (r Vo):
9:
end for Sample random mini-batch {(5), Oj. T3. 8 1) ) from the simulated A time-steps
10:
11:
Update 0 by minimizing the loss function: Lv. I - (s,,, Vg)) Sample random mini-batch ((8j, 0g Ty 85+ )) from the simulated M time-steps Update &i using TRPO with advantage function computed by (Ry((, V2), ()(s end for
12:
13:
15:
Copy 0 to ø' (0' < 0);
end for
19

---

Under review as a conference paper at ICLR 2020
Hyperparameter
Value
Horizon (T)
1000
Adam stepsize
10
Number of samples per Iteration
1024
Entropy coefficient
0.01
Discount factor
0.99
Number of Iterations
2000
Minibatch size
128
#Runs used for plot averages
5
Confidence interval for plot runs
70%
Table 4: Hyper-parameters of s-PI-TRPO and K-VI-TRPO on the MuJoCo domains.
B.2 ABLATION TEST FOR CFA
Walker, Cra
Walker, Cra 0.05
17:0
1750
k-0.36
Mean Episode Reward
1-0.b0
Mean Episode Reward
>=0.68
1-0.84
K=0.84
1250
x-0.06
1250
K-0.96
x-0.90
K-0.98
10C0
=+0.00
1030
720
k-0
750
k-1.0
966
500
239
250
0
250
300
750
1000
1250
1500
1750
2000
250
300
750
2000
1230
1500
1750
2000
Iterations
Iterations
Walker, CfΛ 0.001
2000
4-0.0
Episode Reward
X-0.88
1500
A-0.54
>-0.95
1000
K-0.59
aw1.0
500
250
500
750
1000
1250
1500
1750
2000
Iterations
Figure 10: Performance of x-PI-TRPO and =-VI-TRPO on Walker2d-v2 for different values of CFA-
B.3 K-PI-TRPO AND A- VI-TRPO PLOTS
In this section, we report additional results of the application of k--PI-TRPO and к- x-VI-TRPO on the MuloCo domains. A summary of these results has been reported in Table the main paper.
20

---

Under review as a conference paper at ICLR 2020
Ant-v2 GAE
Ant-v2, N, TT
3520
3530
7-000
K-0.0
30.0
1.0.36
20:00
Mean Episode Reward
1-068
Mean Episode Reward
K=0.68
2500
0=0.4
K=0.84
1.0.92
J-0.96
2-0.90
K-0.98
2=0.09
k-0.00
7-10
k-1.0
500
500
0
0
0
500
750
1000
1250
1500
1750
2000
250
300
1000
1250
1500
1750
2000
Iterations
Iterations
Ant-v2, CFΛ
0.05
Ant-v2, CFA
0.05
3500
35000
k-0.0
k=0.0
3000
x-00.5
3030
Mean Episode Reward
X-0.68
Mean Eolsode Reward
K-0.68
X-0.84
K-0.84
k-0.02
K-0.02
v=0.99
ru0.99
995
1000
1000
309
300
0
Iterations
Iterations
Figure 11: Performance of GAE and 'Naive" baseline (Top row) and k-PI-TRPO (Bottom left) and k- x-VI-TRPP (Bottom right) on Ant-v2.
21

---

Under review as a conference paper at ICLR 2020
HalfCheetah-vZ GAE
HalfCheetah-v2, M(k)
2520
2530
7-00
K-0.0
1=0.36
Mean Episode Reward
2000
2-0.8
2000
K=0.60
0.0.4
K=0.84
15C0
0.9.
1500
2-100
K-0.98
1000
1000
k-0.00
906
500
-500
-500
0
300
750
1000
1250
1500
1750
2000
250
500
1000
1250
1500
1750
2000
Iterations
Iterations
HallCheetah-v2. CFA 0.2
HallCheetah-v2, CFA
0.2
2500
2500
0-0.0
k=0.0
x-0035
Mean Episode Reward
2000
X-0.68
2000
X-0.84
K-0.84
1500
x-0.02
1500
K-0.02
1000
v-0.99
1000
r=0
500
500
-500
-300
Iterations
Iterations
Figure 12: Performance of GAE and 'Naive' baseline (Top row) and k-PI-TRPO (Bottom left) and k- x-VI-TRPP (Bottom right) on HalfCheetah-v2.
22

---

Under review as a conference paper at ICLR 2020
HumanoidStandup--2 GAE
HumanoidStanddp v2, N(x)
75000
0.0.0
75000
K-0.0
1.3.36
Kw0.36
2-0.88
-V3VVUE INCHOIL
K=0.68
0-0.4
K=0.84
000CO
9.9.92
05030
K=0.92
0.9.90
K-0.58
600C0
2.0.0
60000
k=0.89
55000
55930
43000
45000
40000
40000
300
750
100C
1250
1500
1750
2000
250
300
1000
1250
1500
1750
2000
Iterations
Iterations
HumanoidStanduup-v) CFA 0.2
HumanoidStanduup-22 Cfa 0.2
75000
k-0.0
75030
k=0.0
x-0.35
70000
X-0.84
X-0.68
IICOI LUNSUNE NC PaRU
70030
K-0.84
650C0
0-0.0
65000
K-0.92
+0.08
60000
K9
60000
F40.99
x-1.0
K-1.0
50300
50030
45000
43000
40000
40000
Iterations
Iterations
Figure 13: Performance of GAE and 'Naive' baseline (Top row) and s-PI-TRPO (Bottom left) and A- x-VI-TRPO (Bottom right) on HumanoidStandup-v2.
23

---

Under review as a conference paper at ICLR 2020
Swimmer GAE
Swimmer,
120
2- 0-00
120
K-0.0
1.3.6
Mean Episode Reward
100
2-068
0.884
Mean Episode Reward
100
==0.84
X=0.8
0.9.
80
0.9.9
K-0.98
2.09
K-0
0
0
300
750
1000
1250
1500
1750
2000
250
300
1000
1250
1500
1750
2000
Iterations
Iterations
Swimmer, CFA
0.2
Swimmer, CFA
0.2
0-0.0
k=0.0
Mean Episode Reward
100
X- 0.8.84
X-0.69
Mean Episode Neward
100
K-0.84
0.02
K-0.92
v-0.99
K=0 94
Iterations
Iterations
Figure 14: Performance of GAE and 'Naive' baseline (Top row) and k-PI-TRPO (Bottom left) and k- x-VI-TRPP (Bottom right) on Swimmer-v2.
24

---

Under review as a conference paper at ICLR 2020
Hopper GAE
Hopper, N(x)
v-0.0
K-0.0
y=0.30
Mean Episode Reward
1720
Mean Episode Reward
3750
K=0.60
15C0
y=0.84
K=0.84
0-0.92
y-0,06
K-0.58
1900
0-0.08
1000
K-0 09
750
V-1.0
750
500
250
0
0
250
500
750
1000
1230
1500
1750
2000
250
300
1000
1250
1500
1750
2000
Iterations
Iterations
Hopper, CFA 0.2
Hopper, Cea 0.2
k-0.0
k=0.0
Mean Episode Reward
1750
X-0.68
Mean Eoisode Reward
3750
15C0
X-0.84
0-0.02
1500
K-0.84
K-0.02
1250
v-0.99
ru0
09
720
750
Iterations
Iterations
Figure 15: Performance of GAE and 'Naive' baseline (Top row) and k-PI-TRPO (Bottom left) and A- x-VI-TRPO (Bottom right) on Hopper-v2.
25

---

Under review as a conference paper at ICLR 2020
C REBUTTAL RESULTS
C.I CARTPOLE
In this section, we analyze the role plays in the proposed methods by reporting results on the simple CartPole environment for к-PI TRPO. For all experiments, we use single layered value function network and linear policy network. Each hyperparameter configuration is run for 10 different random seeds and plots are shown for 50% confidence interval.
CartPole, Cra 0.2
CartPole, N(x)
230
Mean Eoisode Reward
Mean basode Reward
150
150
135
125
k=0.0
k-0.36
<-0.68
180
k-0.68
78
k-0.66
75
k=0.84
k-0.96
k-0.9G
k-0.99
k-0.90
23
Iterations
Iterations
Figure 16: Training performance k-PI-TRPO (Left) and the 'naive" baseline N(s) T (Right) on the CartPole environment.
Note that since the CartPole is extremely simple, do not clear difference between the values that are closer to 1.0 (see Figure T6p. Below, we observe the performance when the discount factor is lowered (see Figure 17). Since, there is ceiling of 200 on the maximum achievable return, it makes intuitive sense that observing the effect for lower gamma value such as 0.36 will allow us see clearer trade-off between x values. this end, we also plot the results for when the discount factor is set to 0.36.
CartPole Lowering
CartPole, CFA 0.2, V=0.36
200
175
175
Mean Episode Reward
Mean Loisode Reward
150
150
v=0.0
125
125
k-0.0
100
v-0.6
100
k=0.68
y=0.32
75
k-0.84
50
0=0.8
50
k-0.90
k-0.96
y=0.99
Iterations
Iterations
Figure 17: Training performance when lowering the discount factor (Left) and of -P--TRPPO (Left) when discount factor is set to 0.36 (Right) on the CartPole environment.
The intuitive idea behind s-PI, and к- VI similarly, is that every time step, we wish to solve simpler sub-problem, i.e. the 7K discounted MDP. Although, we are solving an easier/shorter horizon problem, in doing so, the bias induced is taken care of by the modified reward this new MDP. Therefore, it becomes interesting to look at how к affects its two contributions, one being the discounting, the other being the weighting of the shaped reward (see eq. IT]. Below we look at what at time, while varying for the
happens when each of these terms made independent, other term. To make this clear, we introduce different notations for both such x instances, one being Ka (responsible for discounting) and the other being K,, (responsible for shaping).
26

---

Under review as a conference paper at ICLR 2020
The (s) arg max E
Σ (yRR)) [r(s), + +1 (5)77
80 80= = s,
VsE (I))
220 discounting
shaping
CartPole. CFA 0.2,
CartPole, CFA = =02, Kg
200
200
175
Mean Episode Reward
Mean Episode Reward
129
150
6-0
k-0.0
100
6-0.96
k-0.00
<-0
k-0 84
k-0.96
6-10
k-0.00
28
Iterations
Iterations
Figure 18: Training performance when contribution of x is fixed for a) the shaped reward (Left) and b) the discount factor (Right) on the CartPole environment.
We see something interesting here. For the CartPole domain, the shaping term does not seem to have any effect on the performance (Figure I8()), while the discounting term does. This implies that the problem does not suffer from any bias issues. Thus, the correction provided by the shaped term is not needed. However, this true for other more complex problems. This also why see a similar result when lowering y in this case, but not for more complex problems.
C.2 MOUNTAIN CAR
In this section, we report results for the Mountain Car environment. Contrary to the CartPole results, where lowering the values degraded the performance, observe that performance deteriorates when k is increased. We also plot bar graph, with the cumulative score on the y axis and different values the axis.
MountainCar, CFA 0.2
MountainCar, N(k) =
Moan Episode Reward
-10
Mean Episode Reward
-10
k=0.0
-30
x-0.36
-30
6-
-30
K-0
<-0
A-0 86
6-0.9
X-0.99
6-0 995
X-O 995
-50
-50
175
100
175
Iterations
Iterations
Figure 19: Training performance of k-PI-TRPO (Top Left: training curves, Top Right: cumulative return) and the 'naive" baseline N(k) = T (Bottom) on the Mountain Car environment.
We use the continuous Mountain Car domain here, which has been shown to create exploration issues. Therefore, without receiving any positive reward, using value of 0 in the case of dis- counting (solving the step problem has the least negative reward) and in the case of shaping results in the best performance.
27

---

Under review as a conference paper at ICLR 2020
MounlainCar Lowering Y
MountainCar, CA 0.2, 0.995
Mcan Episode Reward
y=h 0
Mean Episode Reward
-10
-20
y-0.0
km0
7-0
X-0
K
-40
7-0 983
-30
-50
y=0 908
K-0 96
-60
K-0 0999
-30
-50
k=1.0
100
173
Iterations
Iterations
Figure 20: Training performance when lowering the discount factor (Left) and of K- k-PI-TRPO (Left) when discount factor is set to 0.995 (Right) on the MountainCar environment.
MountainCar, Cfa = 0.2, Kg
MountainCar, Cra 0.2, Kg =
Mcan Episode Reward
-10
K=0 0
-20
6-0.36
Mean Episode
K-0
<-0
-30
-40
K-0 98
<=0 96
-50
K-0 99
2-0 995
-10
1-1.0
-10
100
100 Iterations
Iterations
Figure 21: Training performance when contribution of к is fixed for a) the shaped reward (Left) and b) the discount factor (Right) on the MountainCar environment.
C.3 PENDULUM
In this section, we move to the Pendulum environment, domain where we see non-trivial best value. This is due to there not being cciling on the maximum possible return, which is the case in CartPole.
Pendulum, Cęa
Pendulum, N(K)
-400
k=0 0
-400
<-0.36 36
K-0 36
-800
6-
-800
K-0 92
-100
-1000
-229
6=3 905
<-0 99
-200
A-0 995
K-0 99
-1600
-1600
0
120
200
300
000
500
800
100
200
300
400
300
600
Iterations
Iterations
Figure 22: Training performance of x-PIITRPO (Top Left: training curves, Top Right: cumulative return) and the 'naive' baseline N(x) T (Bottom) on the Pendulum environment.
28

---

Under review as a conference paper at ICLR 2020
Choosing the best y value and running k-PI it results in an improved performance for all values (see Figure 23
Pendulum Lowering
Pendulum, CιΛ 0.2, y=0.96
-200
-400
-400
y-
620
X-0 0
X-0
ywo
K-0
-1000
96
K-0
-1200
K-0
y-0 39
-1200
K-0 99
y-0 995
-1400
-1600
Iterations
Iterations
Figure 23: Training performance when lowering the discount factor (Left) and of k-PI-TRPO (Left) when discount factor is set to 0.96 (Right) on the Pendulum environment.
Pendulum, CFa 0.2, K==1
Pendulum, CFa 0.2, Kz=1
-2.9
420
K=0.36
K=0.68
K=0.84
820
K-0.96
8300
K=0.90
-1000
<
-1000
x=1.0
-1200
6-0
-1200
005
A-1.0
-1400
0
100
200
300
400
300
800
100
200
300
400
300
600
Iterations
Iterations
Figure 24: Training performance when contribution of x is fixed for a) the shaped reward (Left) and b) the discount factor (Right) on the Pendulum environment.
To summarize, we believe that in inherently short horizon domains (dense, per time step reward), such the Mujoco continuous control tasks, the discounting produced by s-PI and VI is shown cause major improvement in performance over the TRPO basclines. This is reinforced by the results of lowering the discount factor experiments. On the other hand, in inherently long horizon domains (sparse, end of trajectory reward), such as in Atari, the shaping produced by x-PI and VI is supposed cause the major improvement over the DQN baselines. Again, this is supported by the fact that lowering the discount factor experiments actually result in deterioration in performance.
29

---

Under review as a conference paper at ICLR 2020
C.4
SMOOTHNESS IN
HaltChestah, Gja 0.2
Ant, 0.2
19000
800000
490009
-00235
Figure 25: Cumulative training performance of K-PI-TRPO on HalfCheetah (Left, corresponds to Figure 12) and Ant (Right, corresponds to Figure 11) environments.
30


Reviews:
[{"review_id": "H1geTaI6KS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "===== Summary =====\nThe paper proposes an extension of multi-step dynamic programming algorithms from Efroni, Dalal, Scherrer, and Mannor (2018a, 2018b) to the reinforcement learning setting with function approximation. The multi-step dynamic programming algorithms proposed by Efroni et. al. (2018a)  find the solution of the h-step optimal Bellman operator, which applies the maximum over the next h sequence of actions. Moreover, Efroni et. al. (2018a) also showed an equivalence between h-step optimal Bellman operators and k-Policy Iteration (k-PI) and k-Value Iteration (k-VI) algorithms, which, similar to TD( 𝜆 ) but for policy improvement, take a geometric average of all future h-step returns weighted by k. The paper extends the work from Efroni et. al. (2018a, 2018b) to the deep reinforcement learning setting by proposing an approximate k-PI and k-VI algorithm based on DQN and TRPO. Finally, the paper provides empirical evaluations of k-PI and k-VI with DQN in several Atari games and of k-PI and k-VI with TRPO in several MuJoCo environments with continuous actions paces. \n\nContributions:\n1. The paper proposes a non-trivial extension for k-PI and k-VI to use function approximation via the DQN algorithm. \n2. Similarly, the paper proposes a non-trivial extension for k-PI and k-VI to use function approximation with continuous action spaces via the TRPO algorithm. \n3. The paper provides empirical evaluations of the four proposed algorithms and, at least for the k-PI algorithm with DQN and TRPO, demonstrates an improvement over the baselines. \n\n===== Decision =====\nThe paper represents a natural next step to the work of Efroni et. al. (2018a, 2018b). The paper extends the applicability of multi-step greedy policies to more complex environments and shows a statistically significant improvement in performance compared to the methods that it builds upon. Additionally, the ideas are presented clearly and incrementally throughout the paper, which makes it flow nicely until the part where k-PI and k-VI DQN and TRPO are introduced. This is my main complaint about the paper, the lack of simple and intuitive understanding about k-PI and k-VI with function approximation due to the complicated architectures associated with DQN and TRPO. For this reason, my rating of the paper is weak accept.\n\n===== Detailed Comments about Decision =====\nAll of these are comments for which I would consider increasing my score if they were addressed. \n\n=== Empirical Evaluations ===\nFirst, my main complaint is the complicated architectures and complex domains used to gain insights about k-PI and k-VI with function approximation. Big demonstrations in Atari and MuJoCo are important, but in the case of very new algorithms such as these ones, I consider it to be more important to gain insight through small domains that allow us to dig deep into the algorithms. Any small domain that would allow for big sample sizes for ablation and parameter studies would be more insightful than big demonstrations with very small sample sizes. I do not mean to be dismissive about what has been done in the paper, but it would be a great source of insight and a big improvement to what has already been done if a simple demonstration was presented in the paper. \n\nMy suggestion would be to use a simple approximation method, such as Tile Coding with linear function approximation, in small a domain such as mountain car. This would allow for a bigger sample size and a parameter study that could provide more insight about the role of the parameters k and C_{FA} on the performance of k-PI and k-VI. \n\nAdditionally, one of the claims in the conclusions was never emphasized in the results: “importantly, the performance of the algorithms was shown to be ‘smooth’  in the parameter k.” This was not completely obvious until I spent some time looking closely at the graph. It eventually became clear, but I think a simpler way to emphasize this is to show a plot of the cumulative reward over the whole training period with the values of k on the x-axis. Based on the top right pane of FIgure 1, this type of plot would show a smooth increase from k=0.99 to k=0.68 followed by a smooth decrease from k=0.68 to k=0. \n\nFinally, I have some questions about some of the choices made in the experiments and results sections:\n\n1. Why choose 50% confidence intervals? 50% confidence intervals with a sample size of 4 in the case of DQN and 5 in the case of TRPO is equivalent to multiplying the standard error by a factor of approximately 0.7, which is narrower than using the standard error on its own. Thus, it seems that some of the conclusions would change based on using a 95% confidence interval compared to a 50% confidence interval in Tables 1 and 2. I insist in showing the performance in a small domain with a simple form of function approximation. This would complement the Atari and MuJoCo experiments by showing improvements in performance with a higher confidence. \n\n2. In remark one, it is pointed out that another target network \\tilde Q should be used to obtain \\pi_{t-1}, but this was not done to reduce the space complexity of the algorithm. How big were the networks that you used for k-PI DQN? If the network was not prohibitively big, why not implement \\tilde Q instead of using an alternative that further deviates from the original k-PI algorithm? \n\n3. Line 19 of Algorithm 5 in Appendix A.1 is supposed to be the off-policy TD(0) update. However, it is not clear how this update is off-policy TD(0) since it based on Q and it does not have any importance sampling to correct for the difference in policies. Am I missing something? It seems that it should be off-policy Sarsa(0), but even then it would still be missing an importance sampling term (see Sutton & Barto, 2018, Equation 7.11, or Algorithm 1 of Precup, Sutton, and Singh, 2000, for more information).\n\n=== Contradictory Claims in the Results ===\nThere are a few claims that contradict with what is shown in Table 1 and 2.\n\nIn the last paragraph of Section 5.1.1 it says that “[the table 1] show[s] that setting N(k) = T leads to a clear degradation of the final training performance on all the domains except Enduro.” This is only true in two out of four games presented in Table 1. In Seaquest the lower confidence bound of the performance of k-PI with k=0.68 is 4643, whereas the upper confidence bound of the performance of k-PI with N(k) = T is 4837; the intervals clearly overlap. Similarly, in the game of Enduro, where k-PI with N(k) = T is said to have better performance, the lower confidence bound of k-PI with N(k) =T is 530, whereas for k-PI with k=0.84 the upper confidence bound is 575; again, the confidence intervals overlap. Hence, neither of these two claims are fully justified, and it is certainly not a “clear degradation of the final training performance.”\n\nSimilarly, in Section 5.2.2, k-PI is said to have a better performance than N(k) = T based on the results of Table 2. However, similar calculations show that this is only true for the Ant domain.\n\n===== Minor Comments =====\n1. I believe there is a typo in the last column of Table 1, it should be a \\kappa instead of a 𝜆.\n\n2. In the second paragraph above Equation 7, the convergence of PI and VI are said to converge to the optimal value with linear rate, but the rate of convergence is O( \\gamma^N ), i.e., exponential. Similarly, for the k-PI and k-VI their rate of convergence is O( \\ksi ( \\kappa )^{N( \\kappa )} ), which is also exponential. \n\n===== References =====\nPrecup, Doina; Sutton, Richard S.; and Singh, Satinder, \"Eligibility Traces for Off-Policy Policy Evaluation\" (2000).ICML '00 Proceedings of the Seventeenth International Conference on Machine Learning. 80.Retrieved fromhttps://scholarworks.umass.edu/cs_faculty_pubs/80\n\nR. Sutton and A. Barto. Reinforcement learning: An introduction. 2018.\n\nY. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Beyond the one step greedy approach in reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, 2018a.\n\nY. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Multiple-step greedy policies in approximate and online reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5238–5247, 2018b.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BklUIEo6_r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on the implementation and some empirical evaluations of a class of algorithms designed to find optimal strategies/values of large MDP.\n\nThe basic idea of these algorithm (called \\kappa-PI or \\kappa-VI) is to combine two type of classical approaches:\n- policy/value iteration \n- k-step ahead computation (instead of just 1-ahead, and actually, k should be quite big or even infinite with an auxiliary appropriate discount rate).\n\nThe theoretical formulation of \\kappa-PI and \\kappa-VI involves solving, at each iteration, another auxiliary MDP problem (where the discount rate is of order \\kappa\\gamma). This is basically what this paper suggests to do, and implements. \n\nThe experiments are a bit difficult for me to read, as the baselines (\\kappa=0 and =1, say) are compared with \"the best \\kappa\" which seems to be problem dependent, so I do not know if there is a clear message.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJeblVM6tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main contributions of this paper are k-PI-DQN and k-VI-DQN, which are model-free versions of dynamic programming (DP) methods k-PI and k-VI from another paper (Efroni et al., 2018).  The deep architecture of the two algorithms follows that of DQN.  Efroni et al. (2018b) already gave a stochastic online (model-free) version of k-PI in the tabular setting.  Although this paper is going one step further extending from tabular to function approximation, I feel that the paper just combined known results, the shaped reward from Efroni et al (2018a) and DQN.  The extension seems straightforward.  Mentioning previous results from Efroni et al (2018a) and (2018b) does not justify the extension would possess the same property or behaviour.   The experiments were only comparing their methods with different hyperparameters, with only a brief comparison to DQN.  ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends recent multi-step dynamic programming algorithms to reinforcement learning with function approximation.  In particular, the paper extends h-step optimal Bellman operators (and associated k-PI and k-VI algorithms) to deep reinforcement learning.  The paper describes new extensions to DQN and TRPO algorithms.  This approach is claimed to reduce the instability of model-free algorithms, and the approach is tested on Atari and Mujoco domains. 

The reviewers noticed several limitations of the work.  The reviewers found little theoretical contribution in this work and they were unsatisfied with the empirical contributions.  The reviewers were unconvinced of the strength and clarity of the empirical results with the Atari and Mujoco domains along with the deep learning network architectures.  The reviewers suggested that simpler domains with a simpler function approximation scheme could enable more through experiments and more conclusive results.  The claim in the abstract of addressing the instabilities was also not adequately studied in the paper.

This paper is not ready for publication.  The primary contribution of this work is the empirical evaluation, and the evaluation is not sufficiently clear for the reviewers.
Decision: Reject