Title: MULTI-STEP GREEDY POLICIES IN MODEL-FREE DEEP 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.

1. INTRODUCTION:

The field of Reinforcement learning (RL) span a wide variety of algorithms for solving decisionmaking 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 (e.g., Mnih et al. 2015; 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., Thrun & Schwartz 1993; Baird 1995; Van Hasselt et al. 2016; Lu et al. 2018 ). These problems are intensified in decision problems with long horizon, i.e., when the discount factor, γ, is large. Although using smaller values of γ addresses the γ-dependent issues and leads to more stable algorithms (Petrik & Scherrer, 2009; Jiang et al., 2015) , it comes with a cost, as the algorithm may return a biased solution, i.e., it may not converge to an optimal solution of the original decision problem (the one with large value of γ). Efroni et al. (2018a) recently proposed another approach to mitigate the γ-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 κ-greedy policy, and studied the convergence of the resulted PI and VI algorithms: κ-PI and κ-VI. These two algorithms iteratively solve γκ-discounted 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 γ, by iteratively solving decision problems with a smaller γκ horizon, the κ-PI and κ-VI algorithms could converge to an optimal policy of the original decision problem.

In this work, we derive and empirically validate model-free deep RL (DRL) implementations of κ-PI and κ-VI. In these implementations, we use DQN (Mnih et al., 2015) and TRPO (Schulman et al., 2015) for (approximately) solving γκ-discounted decision problems (with shaped reward), which is the main component of the κ-PI and κ-VI algorithms. The experiments illustrate the performance of model-free algorithms can be improved by using them as solvers of multi-step greedy PI and VI schemes, as well as emphasize important implementation details while doing so.

2. PRELIMINARIES:

In this paper, we assume that the agent's interaction with the environment is modeled as a discrete time γ-discounted Markov Decision Process (MDP), defined by M γ = (S, A, P, R, γ, µ), where S and A are the state and action spaces; P ≡ P (s |s, a) is the transition kernel; R ≡ r(s, a)

is the reward function with the maximum value of R max ; γ ∈ (0, 1) is the discount factor; and µ is the initial state distribution. Let π : S → P(A) be a stationary Markovian policy, where P(A) is a probability distribution on the set A. The value of π in any state s ∈ S is defined as V π (s) ≡ E[ t≥0 γ t r(s t , π(s t ))|s 0 = s, π], where the expectation is over all the randomness in policy, dynamics, and rewards. Similarly, the action-value function of π is defined as Q π (s, a) = E[ t≥0 γ t r(s t , π(s t ))|s 0 = s, a 0 = a, π]. Since the rewards have the maximum value of R max , both V and Q functions have the maximum value of V max = R max /(1 -γ). An optimal policy π * is the policy with maximum value at every state. We call the value of π * the optimal value, and define it as V * (s) = max π E[ t≥0 γ t r(s t , π(s t ))|s 0 = s, π], ∀s ∈ S. Furthermore, we denote the stateaction value of π * as Q * (s, a) and remind the following relation holds V * (s) = max a Q * (s, a) for all s. The algorithms by which an is be solved (obtain an optimal policy) are mainly based on two popular DP algorithms: Policy Iteration (PI) and Value Iteration (VI). While VI relies on iteratively computing the optimal Bellman operator T applied to the current value function V (Eq. 1), PI relies on (iteratively) calculating a 1-step greedy policy π 1-step w.r.t. to the value function of the current policy V (Eq. 2):

EQUATION

EQUATION

It is known that T is a γ-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 π * . In practice, the state space is often large, and thus, we can only approximately compute Eqs. 1 and 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; 2005; Farahmand et al., 2010) and after N steps, the algorithms approximately converge to a solution π N whose difference with the optimal value is bounded (see e.g., Scherrer 2014 for API):

η(π * ) -η(π N ) ≤ Cδ/(1 -γ) 2 + γ N V max .

(3) In Eq. 3, the scalar η(π) = E s∼µ [V π (s)] is the expected value function at the initial state,1 δ represents 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 (µ in Eq. 3), and depends 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 κ-GREEDY POLICY & κ-PI AND κ-VI ALGORITHMS Algorithm 1 κ-Policy Iteration 1: Initialize: κ ∈ [0, 1], π0, N (κ) 2: for i = 0, 1, . . . , N (κ) -1 do 3: V π i = E[ t≥0 γ t rt | πi] 4: πi+1 ← arg max π E[ ∞ t=0 (κγ) t rt(κ, V π i )|π] 5: end for 6: Return π N (κ) Algorithm 2 κ-Value Iteration 1: Initialize: κ ∈ [0, 1], V0 , N (κ) 2: for i = 0, 1, . . . , N (κ) -1 do 3: Vi+1 = maxπ E[ t≥0 (γκ) t rt(κ, Vi)|π] 4: end for 5: π N (κ) ← arg max π E[ t≥0 (κγ) t rt(κ, V N (κ) )|π] 6: Return π N (κ)

The optimal Bellman operator T (Eq. 1) and 1-step greedy policy π 1-step (Eq. 2) can be generalized to multi-step. The most straightforward form of this generalization is by replacing T and π 1-step with h-optimal Bellman operator and h-step greedy policy (i.e., a lookahead of horizon h) that are defined by substituting the 1-step return in Eqs. 1 and 2, r(s 0 , a) + γV (s 1 ), with h-step return, h-1 t=0 r(s t , a t ) + γ h V (s h ), and computing the maximum over actions a 0 , . . . , a h-1 , instead of just a 0 (Bertsekas & Tsitsiklis, 1996) . Efroni et al. (2018a) proposed an alternative form of multi-step optimal Bellman operator and multi-step greedy policy, called κ-optimal Bellman operator, T κ , and κ-greedy policy, π κ , for κ ∈ [0, 1], i.e.,

EQUATION

EQUATION

where the shaped reward r t (κ, V ) w.r.t. the value function V is defined as

EQUATION

It can be shown that the κ-greedy policy w.r.t. the value function V is the optimal policy w.r.t. a κweighted geometric average of all future h-step returns (from h = 0 to ∞). This can be interpreted as TD(λ) (Sutton & Barto, 2018) for policy improvement (see Efroni et al., 2018a, Sec. 6) . The important difference is that TD(λ) is used for policy evaluation and not for policy improvement.

From Eqs. 4 and 5, it is easy to see that solving these equations is equivalent to solving a surrogate γκ-discounted MDP with the shaped reward r t (κ, V ), which we denote by M γκ (V ) throughout the paper. The optimal value of M γκ (V ) (the surrogate MDP) is T κ V and its optimal policy is the κ-greedy policy, π κ . Using the notions of κ-optimal Bellman operator, T κ , and κ-greedy policy, π κ , Efroni et al. (2018a) derived κ-PI and κ-VI algorithms, whose pseudocode is shown in Algorithms 1 and 2. κ-PI iteratively (i) evaluates the value of the current policy π i , and (ii) set the new policy, π i+1 , to the κ-greedy policy w.r.t. the value of the current policy V πi , by solving Eq. 5. On the other hand, κ-VI repeatedly applies the T κ operator to the current value function V i (solves Eq. 4) to obtain the next value function, V i+1 , and returns the κ-greedy policy w.r.t. the final value V N (κ) . Note that for κ = 0, the κ-greedy policy and κ-optimal Bellman operator are equivalent to their 1-step counterparts, defined by Eqs. 1 and 2, which indicates that κ-PI and κ-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 γ, i.e., V * -V π N ∞ ≤ O(γ N ) (see e.g., Bertsekas & Tsitsiklis, 1996; Scherrer, 2013) . Analogously, Efroni et al. (2018a) showed that κ-PI and κ-VI converge with faster exponential rate of ξ(κ

) = γ(1-κ) 1-γκ ≤ γ, i.e., V * -V π N (κ) ∞ ≤ O(ξ(κ) N (κ)

), with the cost that each iteration of these algorithms is computationally more expensive than that of PI and VI. Finally, we state the following two properties of κ-PI and κ-greedy policies that we use in our RL implementations of κ-PI and κ-VI algorithms in Sections 4 and 5:

1) Asymptotic performance depends on κ. The following bound that is similar to the one reported in Eq. 3 was proved by Efroni et al. (2018b, Thm. 5) for the performance of κ-PI:

EQUATION

where δ(κ) and C(κ) are quantities similar to δ and C in Eq. 3. Note that the first term on the RHS of Eq. 7 is independent of N (κ), while the second one decays with N (κ).

2) Soft updates w.r.t. a κ-greedy policy does not necessarily improve the performance. Let π κ be the κ-greedy policy w.r.t. V π . Then, unlike for 1-step greedy policies, the performance of (1-α)π+απ κ (soft update) is not necessarily better than that of π (Efroni et al., 2018b, Thm. 1) . This hints that it would be advantages to use κ-greedy policies with 'hard' updates (using π κ as the new policy).

4. RL IMPLEMENTATIONS OF κ-PI AND κ-VI:

As described in Sec. 3, implementing κ-PI and κ-VI requires iteratively solving a γκ-discounted surrogate MDP with a shaped reward. If a model of the environment is given, the surrogate MDP can be solved using a DP algorithm (see Efroni 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 RL implementations of κ-PI and κ-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 κ-PI and κ-VI.

In this paper, we use DQN (Mnih et al., 2015) and TRPO (Schulman et al., 2015) as subroutines for estimating a κ-greedy policy (Line 4 in κ-PI, Alg. 1 and Line 5 in κ-VI, Alg. 2) or for estimating an optimal value of the surrogate MDP (Line 3 in κ-VI, Alg. 2). For estimating the value of the current policy (Line 3, in κ-PI, Alg. 1), we use standard policy evaluation deep RL (DRL) algorithms.

To implement κ-PI and κ-VI, we shall set the value of N (κ) ∈ N, i.e., the total number of iterations of these algorithms, and determine the number of samples for each iteration. Since N (κ) only appears in the second term of Eq. 7, an appropriate choice of

N (κ) is such that C(κ)δ(κ)/(1 - γ) 2 ξ(κ) N (κ) V max .

Note that setting N (κ) to a higher value would not dramatically improve the

Algorithm 3 κ-PI-DQN 1: Initialize replay buffer D, Q-networks Q θ , Q φ , and target networks Q θ , Q φ ; 2: for i = 0, . . . , N (κ) -1 do 3: # Policy Improvement 4:

for t = 1, . . . , T (κ) do 5:

Act by an -greedy policy w.r.t. Q θ (st, a), observe rt, st+1, and store (st, at, rt, st+1) in D; 6:

Sample a batch {(sj, aj, rj, sj+1)} N j=1 from D; 7:

Update θ by DQN rule with {(sj, aj, rj(κ, V φ ), sj+1)} N j=1 , where 8:

V φ (sj+1) = Q φ (sj+1, πi-1(sj+1)) and πi-1(s) ∈ arg maxa Q θ (s, a); 9:

Copy θ to θ occasionally (θ ← θ); 10:

end for 11:

# Policy Evaluation of πi(s) ∈ arg maxa Q θ (s, a) 12:

for t = 1, . . . , T (κ) do 13:

Sample a batch {(sj, aj, rj, sj+1)} N j=1 from D; 14:

Update φ by TD(0) off-policy rule with {(sj, aj, rj, sj+1)} N j=1 , and πi(s) ∈ arg maxa Q θ (s, a); 15:

Copy φ to φ occasionally (φ ← φ); 16:

end for 17: end for performance, because the asymptotic term in Eq. 7 is independent of N (κ). In practice, since δ(κ) and C(κ) are unknown, we set N (κ) to satisfy the following equality:

EQUATION

where C F A is a hyper-parameter that depends on the final-accuracy we are aiming for. For example, if we expect the final accuracy being 90%, we would set C F A = 0.1. Our results suggest that this approach leads to a reasonable choice for N (κ), e.g., N (κ = 0.99) 4 and N (κ = 0.5) 115, for C F A = 0.1 and γ = 0.99. As we increase κ, we expect less iterations are needed for κ-PI and κ-VI to converge to a good policy. Another important observation is that since the discount factor of the surrogate MDP that κ-PI and κ-VI solve at each iteration is γκ, the effective horizon (the effective horizon of a γκ-discounted MDP is 1/(1 -γκ)) of the surrogate MDP increases with κ.

Lastly, we need to determine the number of samples for each iteration of κ-PI and κ-VI. We allocate equal number of samples per iteration, denoted by T (κ). Since the total number of samples, T , is known beforehand, we set the number of samples per iteration to

EQUATION

5 DQN AND TRPO IMPLEMENTATIONS OF κ-PI AND κ-VI

In this section, we study the use of DQN (Mnih et al., 2015) and TRPO (Schulman et al., 2015) in κ-PI and κ-VI algorithms. We first derive our DQN and TRPO implementations of κ-PI and κ-VI in Sections 5.1 and 5.2. We refer to the resulting algorithms as κ-PI-DQN, κ-VI-DQN, κ-PI-TRPO, and κ-VI-TRPO. It is important to note that for κ = 1, κ-PI-DQN and κ-VI-DQN are reduced to DQN, and κ-PI-TRPO and κ-VI-TRPO are reduced to TRPO. We then conduct a set of experiments with these algorithms, in Sections 5.1.1 and 5.2.1, in which we carefully study the effect of κ and N (κ) (or equivalently the hyper-parameter C F A , defined by Eq. 8) on their performance. In these experiments, we specifically focus on answering the following questions:

1. Is the performance of DQN and TRPO improve when using them as κ-greedy solvers in κ-PI and κ-VI? Is there a performance tradeoff w.r.t. to κ?

2. Following κ-PI and κ-VI, our DQN and TRPO implementations of these algorithms devote a significant number of sample T (κ) to each iteration. Is this needed or a 'naive' choice of T (κ) = 1, or equivalently N (κ) = T , works just well, for all values of κ?

5.1. DQN IMPLEMENTATION OF κ-PI AND κ-VI:

Algorithm 3 contains the pseudo-code of κ-PI-DQN. Due to space constraints, we report its detailed pseudo-code in Appendix A.1 (Alg. 5). In the policy improvement stage of κ-PI-DQN, we use DQN to solve the γκ-discounted surrogate MDP with the shaped reward r t (κ, V φ V πi-1 ), i.e., at the end of this stage M γκ (V φ ). The output of the DQN is approximately the optimal Qfunction of M γκ (V φ ), and thus, the κ-greedy policy w.r.t. V φ is equal to arg max a Q θ (•, a). At the policy evaluation stage, we use off-policy TD(0) to evaluate the Q-function of the current policy

π i , i.e., Q φ Q πi .

Although what is needed on Line 8 is an estimate of the value function of the current policy, V φ V πi-1 , we chose to evaluate the Q-function of π i : the data in our disposal (the transitions stored in the replay buffer) is an off-policy data and the Q-function of a fixed policy can be easily evaluated with this type of a data using off-policy TD(0), unlike the value function.

Remark 1 In order for V φ to be an accurate estimate of the value function of π i-1 on Line 8, we should use an additional target network, Q θ , that remains unchanged during the policy improvement stage. This network should be used in π i-1 (•) = arg max a Q θ (•, a) on Line 8, and be only updated right after the improvement stage on Line 11. However, to reduce the space complexity of the algorithm, we do not use this additional target network and compute π i-1 on Line 8 as arg max Q θ , despite the fact that Q θ changes during the improvement stage.

We report the pseudo-code of κ-VI-DQN in Appendix A.1 (Alg. 6). Note that κ-VI simply repeats V ← T κ V and computes T κ V , which is the optimal value of the surrogate MDP M γκ (V ). In κ-VI-DQN, we repeatedly solve M γκ (V ) by DQN, and use its optimal Q-function to shape the reward of the next iteration. Let Q * γκ,V and V * γκ,V be the optimal Q and V functions of M γκ (V ). Then, we have

max a Q * γκ,V (s, a) = V * γκ,V (s) = (T κ V )(s),

where the first equality is by definition (Sec. 2) and the second one holds since T κ V is the optimal value of M γκ (V ) (Sec. 3). Therefore, in κ-VI-DQN, we shape the reward of each iteration by max a Q φ (s, a), where Q φ is the output of the DQN from the previous iteration, i.e., max a Q φ (s, a) T κ V i-1 .

5.1.1. κ-PI-DQN AND κ-VI-DQN EXPERIMENTS:

In this section, we empirically analyze the performance of the κ-PI-DQN and κ-VI-DQN algorithms on the Atari domains: Breakout, Seaquest, SpaceInvaders, and Enduro (Bellemare et al., 2013) . We start by performing an ablation test on three values of parameter C F A = {0.001, 0.05, 0.2} on the Breakout domain. The value of C F A sets the number of samples per iteration T (κ) (Eq. 8) and the total number of iterations N (κ) (Eq. 9). Aside from C F A , we set the total number of samples to T 10 6 . This value represents the number of samples after which our DQN-based algorithms approximately converge. For each value of C F A , we test κ-PI-DQN and κ-VI-DQN for several κ values. In both algorithms, the best performance was obtained with C F A = 0.05, thus, we set C F A = 0.05 in our experiments with other Atari domains.

Domain:

Alg. Figure 1 shows the training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) for the best value of C F A = 0.05, as well as for the 'naive' baseline T (κ) = 1, or equivalently N (κ) = T , on Breakout. The results on Breakout for the other values of C F A and the results on the other Atari domains for C F A = 0.05 have been reported in Appendix A.2. Table 1 shows the final training performance of κ-PI-DQN and κ-VI-DQN on the Atari domains with C F A = 0.05. Note that the scores reported in Table 1 are the actual returns of the Atari domains, while the vertical axis in the plots of Figure 1 corresponds to a scaled return. We plot the scaled return, since this way it would be easier to reproduce our results using the OpenAI Baselines codebase (Hill et al., 2018) .

κ best κ = 0 DQN, κ = 1 N (κ) = T ,

The results of Fig. 1 and Table 1 , as well as those in Appendix A.2, exhibit that both κ-PI-DQN and κ-VI-DQN improve the performance of DQN (κ = 1). Moreover, they show that setting N (κ) = T leads to a clear degradation of the final training performance on all of the domains expect Enduro, which attains better performance for N (κ) = T . Although the performance degrades, the results for N (κ) = T are still better than for DQN.

5.2. TRPO IMPLEMENTATION OF κ-PI AND κ-VI:

Algorithm 4 contains the pseudo-code of κ-PI-TRPO (detailed pseudo-code in Appendix A.1). TRPO iteratively updates the current policy using its return and an estimate of its value function. In our κ-PI-TRPO, at each iteration i: 1) we use the estimate of the current policy V φ V πi-1 (computed in the previous iteration) to calculate the return R(κ, V φ ) and an estimate of the value function V θ of the surrogate MDP M γκ (V φ ), 2) we use the return R(κ, V φ ) and V θ to compute the new policy π i , and 3) we estimate the value of the new policy V φ V πi on the original, γ discounted, MDP.

In Appendix B.1 we provide the pseudocode of κ-VI-TRPO derived by the κ-VI meta algorithm. As previously noted, κ-VI iteratively solves the γκ discounted surrogate MDP and uses its optimal value T κ V i-1 to shape the reward of the surrogated MDP in the i'th iteration. With that in mind, consider κ-PI-TRPO. Notice that as π θ converges to the optimal policy of the surrogate γκ discounted MDP, Vθ converges to the optimal value of the surrogate MDP, i.e., it converges to T κ V i-1 = T κ V i-1 . Thus, κ-PI-TRPO can be turn to κ-VI-TRPO by eliminating the policy evaluation stage, and simply copy φ ← θ, meaning, V φ ← Vθ = T κ V φ .

5.2.1. κ-PI-TRPO AND κ-VI-TRPO EXPERIMENTS:

In this section, we empirically analyze the performance of the κ-PI-TRPO and κ-VI-TRPO algorithms on the MuJoCo domains: Walker2d-v2, Ant-v2, HalfCheetah-v2, HumanoidStandup-v2, and Swimmer-v2, (Todorov et al., 2012) . As in Section 5.1.1, we start by performing an ablation test on the parameter C F A = {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 × 10 6 . This is the number of samples after which our TRPO-based algorithms approximately converge. For each value of C F A , we test κ-PI-TRPO and κ-VI-TRPO for several κ values. In both algorithms, the best performance was obtained with C F A = 0.2, thus, we set C F A = 0.2 in our experiments with other MuJoCo domains.

Algorithm 4 κ-PI-TRPO 1: Initialize V -networks V θ and V φ , policy network π ψ , and target network V φ ; 2: for i = 0, . . . , N (κ) -1 do 3:

for t = 1, . . . , T (κ) do 4:

Simulate the current policy π ψ for M steps and calculate the following two returns for all steps j: 5: Rj(κ, V φ ) = M t=j (γκ) t-j rt(κ, V φ ) and ρj = M t=j γ t-j rt; 6:

Update θ by minimizing the batch loss function:

LV θ = 1 N N j=1 (V θ (sj) -Rj(κ, V φ )) 2 ; 7:

# Policy Improvement 8:

Update ψ using TRPO by the batch {(Rj(κ, V φ ), V θ (sj))} N j=1 ; 9:

# Policy Evaluation 10:

Update φ by minimizing the batch loss function:

LV φ = 1 N N j=1 (V φ (sj) -ρj) 2 ; 11:

end for 12:

Copy φ to φ (φ ← φ); 13: end for The results of Figure 2 and Table 2 , as well as those in Appendix B.3, exhibit that both κ-PI-TRPO and κ-VI-TRPO yield better performance than TRPO (κ = 1). Furthermore, they show that the algorithms with C F A = 0.2 perform better than with N (κ) = T . However, the improvement is less significant relative to the DQN-based results in Section 5.1.1.

5.2.2. COMPARISON WITH THE GENERALIZED ADVANTAGE ESTIMATION ALGORITHM:

There is an intimate relation between κ-PI and the GAE algorithm Schulman et al. (2016) which we elaborate on in this section. In GAE the policy is updated by the gradient:

∇ θ E s∼µ [V π θ (s)] = E s0∼dµ,π ∇ θ log π θ (s 0 ) t (γλ) t δ(V ) ; δ(V ) = r t + γV t+1 -V t , (10)

which can be interpreted as a gradient step in a γλ discounted MDP with rewards δ(V ), which we refer here as M δ(V ) γλ . As noted in Efroni et al. (2018a) , Section 6, the optimal policy of the MDP M δ(V ) γλ is the optimal policy of M γκ (V ) with κ = λ, i.e., the κ-greedy policy w.r.t. V : thus, the is the κ-greedy policy w.r.t. V . GAE, instead of solving the κ-greedy policy while keeping V fixed, changes the policy and updates V by the return concurrently. Thus, this approach is conceptually similar to κ-PI-TRPO with N (κ) = T . There, the value and policy are concurrently updated as well, without clear separation between the update of the policy and the value.

In Figure 2 and Table 2 the performance of GAE is compared to the one of κ-PI-TRPO and κ-VI-TRPO. The performance of the latter two is slightly better than the one of GAE.

Remark 2 (Implementation of GAE) We used the OpenAI baseline implementation of GAE with a small modification. In the baseline code, the value network is updated w.r.t. to the target t (γλ) t r t , whereas in Schulman et al. (2016) the authors used the target t γ t r t (see Schulman et al. (2016) , Eq.28). We chose the latter form in our implementation to be in accord with Schulman et al. (2016) .

5.3. DQN AND TRPO PERFORMANCE VERSUS THE DISCOUNT FACTOR:

To supply with a more complete view on our experiments, we tested the performance of the "vanilla" DQN and TRPO when trained with different γ values than the previously used one (γ = 0.99). As evident in Figure 3 , only for the Ant domain this approach resulted in improved performance when for TRPO trained with γ = 0.68. It is interesting to observe that for the Ant domain the performance of κ-PI-TRPO and especially of κ-VI-TRPO (Table 2 ) significantly surpassed the one of TRPO trained with γ = 0.68. The performance of DQN and TRPO on the Breakout, SpaceInvaders and Walker domains decreased or remained unchanged in the tested γ values. Thus, on these domains, changing the discount factor does not improve the DQN and TRPO algorithms, as using κ-PI or κ-VI with smaller κ value do.

It is interesting to observe that the performance on the Mujoco domains for small γ, e.g., γ = 0.68, achieved good performance, whereas for the Atari domains the performance degraded with lowering γ. 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 γ and κ are two different parameters an algorithm designer may use. For example, one can perform a scan of γ value, fix γ to the one with optimal performance, and then test the performance of different κ values.

6. DISCUSSION AND FUTURE WORK:

In this work we formulated and empirically tested simple generalizations of DQN and TRPO derived by the theory of multi-step DP and, specifically, of κ-PI and κ-VI algorithms. The empirical investigation reveals several points worth emphasizing.

1. κ-PI is better than κ-VI for the Atari domains.. In most of the experiments on the Atari domains κ-PI-DQN has better performance than κ-VI-DQN. This might be expected as the former uses extra information not used by the latter: κ-PI estimates the value of current policy whereas κ-VI ignores this information. 2. For the Gym domains κ-VI performs slightly better than κ-PI. For the Gym domains κ-VI-TRPO performs slightly better than κ-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 5.3) and information on the policy's value is not needed. 3. Non trivial κ value improves the performance. In the vast majority of our experiments both κ-PI and κ-VI improves over the performance of their vanilla counterparts (i.e., κ = 1), except for the Swimmer and BeamRider domains from Mujoco and Atari suites. Importantly, the performance of the algorithms was shown to be 'smooth' in the parameter κ. This suggests careful hyperparameter tuning of κ is not of great necessity. 4. Using the 'naive' choice of N (κ) = T deteriorates the performance. Choosing the number of iteration by Eq. 8 improves the performance on the tested domains.

An interesting future work would be to test model-free algorithms which use other variants of greedy policies (Bertsekas & Tsitsiklis, 1996; Bertsekas, 2018; Efroni et al., 2018a; Sun et al., 2018; Shani et al., 2019) . Furthermore, and although in this work we focused on model-free DRL, it is arguably more natural to use multi-step DP in model-based DRL (e.g., Kumar et al., 2016; Talvitie, 2017; Luo et al., 2018; Janner et 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 κ -or more generally, the planning horizon -as a 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 to 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.

A DQN IMPLEMENTATION OF κ-PI AND κ-VI

A.1 PSEUDO-CODES

In this section, we report the detailed pseudo-codes of the κ-PI-DQN and κ-VI-DQN algorithms, described in Section 5.1, side-by-side. Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from D;

9:

Update θ by minimizing the following loss function:

10:

L Q θ = 1 N N j=1 Q θ (s j , a j ) -(r j (κ, V φ ) + γκ max a Q θ (s j+1 , a))

2 , where 11:

V φ (s j+1 ) = Q φ (s j+1 , π i-1 (s j+1 )) and π i-1 (s j+1 ) ∈ arg max a Q θ (s j+1 , a); 12:

Copy θ to θ occasionally (θ ← θ); Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from D;

18:

Update φ by minimizing the following loss function:

19:

L Q φ = 1 N N j=1 Q φ (s j , a j ) -(r j + γQ φ (s j+1 , π i (s j+1 ))) 2 ; 20:

Copy φ to φ occasionally (φ ← φ); Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from D;

9:

Update θ by minimizing the following loss function:

10:

L Q θ = 1 N N j=1 Q θ (s j , a j ) -(r j (κ, V φ ) + κγ max a Q θ (s j+1 , a))

2 , where 11:

V φ (s j+1 ) = Q φ (s j+1 , π(s j+1 )) and π(s j+1 ) ∈ arg max a Q θ (s j+1 , a); 12:

Copy θ to θ occasionally (θ ← θ); In this section, we report additional results of the application of κ-PI-DQN and κ-VI-DQN on the Atari domains. A summary of these results has been reported in Table 1 in the main paper. B TRPO IMPLEMENTATION OF κ-PI AND κ-VI

B.1 PSEUDO-CODES:

In this section, we report the detailed pseudo-codes of the κ-PI-TRPO and κ-VI-TRPO algorithms, described in Section 5.2, side-by-side.

Algorithm 7 κ-PI-TRPO 1: Initialize V -networks V θ and V φ , and policy network π ψ with random weights θ, φ, and ψ 2: Initialize target network V φ with weights φ ← φ 3: for i = 0, . . . , N (κ) -1 do 4:

for t = 1, . . . , T (κ) do 5:

Simulate the current policy π ψ for M time-steps;

6:

for j = 1, . . . , M do 7: Calculate R j (κ, V φ ) = M t=j (γκ) t-j r t (κ, V φ ) and ρ j = M t=j γ t-j r t ; 8:

end for 9:

Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from the simulated M time-steps; 10:

Update θ by minimizing the loss function:

L V θ = 1 N N j=1 (V θ (s j ) -R j (κ, V φ )) 2 ; 11: # Policy Improvement 12:

Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from the simulated M time-steps;

13:

Update ψ using TRPO with advantage function computed by {(R j (κ, V φ ), V θ (s j ))} N j=1 ;

14:

# Policy Evaluation 15:

Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from the simulated M time-steps;

16:

Update φ by minimizing the loss function:

L V φ = 1 N N j=1 (V φ (s j ) -ρ j ) 2 ; 17:

end for 18:

Copy φ to φ (φ ← φ); 19: end for Algorithm 8 κ-VI-TRPO 1: Initialize V -network V θ and policy network π ψ with random weights θ and ψ; 2: Initialize target network V φ with weights φ ; ← θ; 3: for i = 0, . . . , N (κ) -1 do 4:

# Evaluate T κ V φ and the κ-greedy policy w.r.t. V φ 5:

for t = 1, . . . , T (κ) do 6:

Simulate the current policy π ψ for M time-steps;

7:

for j = 1, . . . , M do 8: Calculate R j (κ, V φ ) = M t=j (γκ) t-j r t (κ, V φ ); 9:

end for 10:

Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from the simulated M time-steps 11:

Update θ by minimizing the loss function:

L V θ = 1 N N j=1 (V θ (s j ) -R j (κ, V φ )) 2 ; 12:

Sample a random mini-batch {(s j , a j , r j , s j+1 )} N j=1 from the simulated M time-steps 13:

Update ψ using TRPO with advantage function computed by {(R j (κ, V φ ), V θ (s j ))} N j=1 ;

14:

end for We see something interesting here. For the CartPole domain, the shaping term does not seem to have any effect on the performance (Figure 18 (b)), 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 is not true for other more complex problems. This is also why we see a similar result when lowering γ 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, we observe that performance deteriorates when κ is increased. We also plot a bar graph, with the cumulative score on the y axis and different κ values on the x axis. We use the continuous Mountain Car domain here, which has been shown to create exploration issues. Therefore, without receiving any positive reward, using a κ value of 0 in the case of discounting (solving the 1 step problem has the least negative reward) and of 1 in the case of shaping results in the best performance.

:

Note that the LHS of Eq. 3 is the 1-norm of (V π * -V π N ) w.r.t. the initial state distribution µ.

Figures and Tables:

Figure 1: Training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) on Breakout, for the hyper-parameter C F A = 0.05 (right) and for the 'naive' baseline N (κ) = T (left).

1: The final training performance of κ-PI-DQN and κ-VI-DQN on the Atari domains, for the hyper-parameter C F A = 0.05. The values represent the empirical mean ± empirical standard deviation.

Figure 2: Training performance of κ-PI-TRPO (Top) and κ-VI-TRPO (Bottom) on Walker, for the hyper-parameter C F A = 0.2 (right) and for the 'naive' baseline N (κ) = T (left).

Figure 2 shows the training performance of κ-PI-TRPO (Top) and κ-VI-TRPO (Bottom) for the best value of C F A = 0.2, as well as for the 'naive' baseline T (κ) = 1, or equivalently N (κ) = T , on Walker. The results on Walker for the other C F A values and the other MuJoCo domains for C F A = 0.2 have been reported in Appendix B.3. Table 2 shows the final training performance of κ-PI-TRPO and κ-VI-TRPO on the MuJoCo domains with C F A = 0.2.

The final training performance of κ-PI-TRPO and κ-VI-TRPO on the MuJoCo domains, for the hyper-parameter C F A = 0.2. The values represent the empirical mean ± empirical standard deviation.

Figure 3: Lowering the discount factor

π i (s) ∈ arg max a Q θ (s, a); 16:for t = 1, . . . , T (κ) do 17:

Figure 4: Performance of κ-PI-DQN and κ-VI-DQN on Breakout for different values of C F A .

Figure 5: Training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) on SpaceInvaders, for the hyper-parameter C F A = 0.05 (right) and for the 'naive' baseline N (κ) = T (left).

Figure 6: Training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) on Seaquest, for the hyper-parameter C F A = 0.05 (right) and for the 'naive' baseline N (κ) = T (left).

Figure 7: Training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) on Enduro, for the hyper-parameter C F A = 0.05 (right) and for the 'naive' baseline N (κ) = T (left).

Figure 8: Training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) on BeamRider, for the hyper-parameter C F A = 0.05 (right) and for the 'naive' baseline N (κ) = T (left).

Figure 9: Training performance of κ-PI-DQN (Top) and κ-VI-DQN (Bottom) on Qbert, for the hyper-parameter C F A = 0.05 (right) and for the 'naive' baseline N (κ) = T (left).

Figure 10: Performance of κ-PI-TRPO and κ-VI-TRPO on Walker2d-v2 for different values of C F A .

Figure 11: Performance of GAE and 'Naive' baseline (Top row) and κ-PI-TRPO (Bottom left) and κ-VI-TRPO (Bottom right) on Ant-v2.

Figure 12: Performance of GAE and 'Naive' baseline (Top row) and κ-PI-TRPO (Bottom left) and κ-VI-TRPO (Bottom right) on HalfCheetah-v2.

Figure 13: Performance of GAE and 'Naive' baseline (Top row) and κ-PI-TRPO (Bottom left) and κ-VI-TRPO (Bottom right) on HumanoidStandup-v2.

Figure 14: Performance of GAE and 'Naive' baseline (Top row) and κ-PI-TRPO (Bottom left) and κ-VI-TRPO (Bottom right) on Swimmer-v2.

Figure 15: Performance of GAE and 'Naive' baseline (Top row) and κ-PI-TRPO (Bottom left) and κ-VI-TRPO (Bottom right) on Hopper-v2.

Figure 19: Training performance of κ-PI-TRPO (Top Left: training curves, Top Right: cumulative return) and the 'naive' baseline N (κ) = T (Bottom) on the Mountain Car environment.

κ best

Table content: <table><tr><td>Breakout</td><td>κ-PI κ-VI</td><td>224(±5), κ=0.68 180(±5), κ=0.68</td><td>160(±3) 179(±6)</td><td>131(±3)</td><td>171(±1), κ=0.68</td></tr><tr><td>SpaceInv.</td><td>κ-PI κ-VI</td><td>747(±23), κ=0.84 707(±32), κ=0.36</td><td>611(±15) 669(±16)</td><td>685(±24)</td><td>695(±16), κ=0.92</td></tr><tr><td>Seaquest</td><td>κ-PI κ-VI</td><td>5159(±509), κ=0.84 3394(±86), κ=0.36</td><td>2732(±281) 2631(±496)</td><td>3207(±248)</td><td>4371(±466), κ=0.84</td></tr><tr><td>Enduro</td><td>κ-PI κ-VI</td><td>544(±29), κ=0.84 499(±18), κ=0.84</td><td>371(±215) 492 (±28)</td><td>355(±52)</td><td>547(±17), κ=0.68</td></tr><tr><td>BeamRider</td><td colspan="3">κ-PI κ-VI 4077 (±303), κ=0.68 4052 (±462) 3968(±78), κ=1.0 3654(±778)</td><td>3968(±78)</td><td>3968(±78), κ=1.0</td></tr><tr><td>Qbert</td><td colspan="3">κ-PI κ-VI 7924 (±267), κ=0.68 7585 (±587) 8276(±202), κ=0.36 6900(±149)</td><td>7322(±280)</td><td>8042(±442), κ=0.92</td></tr></table>



Table content: <table/>

Initialize replay buffer D, and Q-networks Q θ and Q φ with random weights θ and φ; 2: Initialize target networks Q θ and Q φ with weights θ ← θ and φ ← φ; 3: for i = 0, . . . , N (κ) -1 do Execute a t , observe r t and s t+1 , and store the tuple (s t , a t , r t , s t+1 ) in D;

Table content: <table><tr><td colspan="2">Algorithm 5 κ-PI-DQN</td></tr><tr><td>1: 4:</td><td># Policy Improvement</td></tr><tr><td>5:</td><td>for t = 1, . . . , T (κ) do</td></tr><tr><td>6:</td><td>Select a t as an -greedy action w.r.t. Q θ (s t , a);</td></tr><tr><td>7:</td><td/></tr><tr><td>8:</td><td/></tr></table>

Initialize replay buffer D, and Q-networks Q θ and Q φ with random weights θ and φ; 2: Initialize target network Q θ with weights θ ← θ; 3: for i = 0, . . . , N (κ) -1 do Execute a t , observe r t and s t+1 , and store the tuple (s t , a t , r t , s t+1 ) in D;

Table content: <table><tr><td>21:</td><td>end for</td></tr><tr><td colspan="2">22: end for</td></tr><tr><td colspan="2">Algorithm 6 κ-VI-DQN</td></tr><tr><td>1: 4:</td><td># Evaluate T κ V φ and the κ-greedy policy w.r.t. V φ</td></tr><tr><td>5:</td><td>for t = 1, . . . , T (κ) do</td></tr><tr><td>6:</td><td>Select a t as an -greedy action w.r.t. Q θ (s t , a);</td></tr><tr><td>7:</td><td/></tr><tr><td>8:</td><td/></tr></table>

Peer review (iclr2020):
===== Summary ===== The 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. Contributions: 1. The paper proposes a non-trivial extension for k-PI and k-VI to use function approximation via the DQN algorithm. 2. 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. 3. 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. ===== Decision ===== The 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. ===== Detailed Comments about Decision ===== All of these are comments for which I would consider increasing my score if they were addressed. === Empirical Evaluations === First, 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. My 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. Additionally, 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. Finally, I have some questions about some of the choices made in the experiments and results sections: 1. 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. 2. In remark one, it is pointed out that another target network 	ilde 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 	ilde Q instead of using an alternative that further deviates from the original k-PI algorithm? 3. 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). === Contradictory Claims in the Results === There are a few claims that contradict with what is shown in Table 1 and 2. In 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.” Similarly, 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. ===== Minor Comments ===== 1. I believe there is a typo in the last column of Table 1, it should be a kappa instead of a ??. 2. 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. ===== References ===== Precup, 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 R. Sutton and A. Barto. Reinforcement learning: An introduction. 2018. Y. 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. 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.