Highway Reinforcement Learning
Authors: Yuhui Wang
Haozhe Liu
Miroslav Strupl
Francesco Faccio
Qingyuan Wu
Xiaoyang Tan
Jürgen Schmidhuber
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
off-policy learning
credit assignment
Bellman Equation

Abstract: Traditional Dynamic Programming (DP) approaches suffer from slow backward credit-assignment (CA): only a one-step search is performed at each update. A popular solution for multi-step CA is to use multi-step Bellman operators. Unfortunately, in the control settings, existing methods typically suffer from the large variance of multi-step off-policy corrections or are biased, preventing convergence. To overcome these problems, we introduce a novel multi-step Bellman optimality equation with adaptive lookahead steps. We first derive a new multi-step Value Iteration (VI) method that converges to the optimal Value Function (VF) with an exponential contraction rate but linear computational complexity. Given some trial, our so-called Highway RL performs rapid CA, by picking a policy and a possible lookahead (up to the trial end) that maximize the near-term reward during lookahead plus a DP-based estimate of the cumulative reward for the remaining part of the trial. Highway RL does not require off-policy corrections. Under mild assumptions, it achieves better convergence rates than the traditional one-step Bellman Optimality Operator. We then derive Highway Q-Learning, a convergent multi-step off-policy variant of Q-learning. We show that our Highway algorithms significantly outperform DP approaches on toy tasks. Finally, we propose a deep function approximation variant called Highway DQN. We evaluate it on visual MinAtar Games, outperforming similar multi-step methods.

Under review as a conference paper at ICLR 2023
HIGHWAY REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Traditional Dynamic Programming (DP) approaches suffer from slow backward credit-assignment (CA); one time step per update. A popular solution for multi- step CA is to multi-step Bellman operators. Existing control methods, how- ever, typically suffer from large variance of multi-step off-policy corrections or are biased, preventing convergence. To overcome these problems, we introduce a novel multi-step Bellman Optimality operator, which quickly transports credit information from the future into the past through "hltippe"" induced by various behavioral policies. Our operator is unbiased with respect to the optimal value function and converges faster than the traditional Bellman Optimality oper- ator. Its computational complexity is linear in the number of behavioral policies and lookahead depth. Moreover, it yields a family of novel multi-step off- off-policy algorithms that do not need importance sampling, We derive convergent multi- step off- off-policy variant of Q-learning called Highway Q-Learning, and also a deep function approximation variant called Highway DQN. Experiments toy tasks and visual MinAtar Games (Young & Tian, 2019) illustrate that our algorithms outperform similar multi-step methods.
INTRODUCTION
Recent advances in multi-step reinforcement learning (RL) have achieved remarkable empirical suc- cess (Horgan al., 2018; Barth-Maron al., 2018). However, major challenge of multi-step RL is to balance the trade-off between traditional "safe" relying on knowledge stored in learned Value Function (VF), and large CA jumps across many time steps. A traditional way of addressing this issue is to impose fixed prior distribution over the possible numbers of CA steps, e.g., TD(A) (Sutton & Barto, 2018), GAE(A) (Schulman et al., 2016). This typically ignores the current spacefcp quality of the current VE, which dynamically improves during learning. Besides, the prior distribution usually has to be tuned case by case.
siin--ste--er-tree credit assignment (CA)
Multi-step RL should also work for off-policy learning, that is, learning from data obtained by other behavioral policies. Most previous research on this has focused on Policy Iteration(Pl- approaches (Sutton & Barto, 2018), which need to correct the discrepancy between target policy and behavior policy to evaluate the VF (Precup, 2000; Harutyunyan et al., 2016; Munos et al., 2016; Sutton & Barto, 2018; Schulman al., 2016). Classic importance sampling(IS)-aan -based methods is proven to be unbiased, but suffer from high variance due to the product of IS ratios (Cortes et al., 2010; Metelli et al., 2018). Recently, several variance reduction methods have been proposed and shown to be effective in practice such as Q(A) (Harutyunyan et al., 2016), Retrace (A) (Munos et al., 2016) and C-trace (Rowland al., 2020), and on (Espeholt et al., 2018: Horgan et al., 2018; Asis et al.. 2017). In contrast to PI, Value Iteration (VI) methods propagate the values of the most promising actions backward one step at a time (Sutton & Barto, 2018; Szepesvári, 2010). Such methods can safely use data from any behavioral policy. However, step-by-ster value propagation makes them somewhat ill-suited for general multi-step CA.
Here we provide new tool for multi-step off-policy learning by extending VI approaches to the multi-step setting. The foundation of our method is new Bellman operator, the Highway Operator, which connects current and future states through multiple "highways," and focuses on the most promising one. Highways are constructed through various policies looking ahead for multiple steps. Our operator has the following desirable properties: 1) It yields new Bellman Optimality Equation that reflects the latent structure of multi-step CA, providing a novel sufficient condition for the optimal VF; 2) It effectively assigns future credit to past states across multiple time steps and has

---

Under review as a conference paper at ICLR 2023
remarkable convergence properties; 3) It yields family of novel multi-step off- off-policy algorithms that do not need importance sampling. safely using arbitrary off policy data. Experiments on toy tasks and visual MinAtar Games (Young & Tian, 2019) illustrate that our Highway RL algorithms outperform existing multi-step methods.
2 PRELIMINARIES
A Markov Decision Processes (MDP) (Puterman, 2014) is described by the tuple .M = (S.A, T Mo, R), where S is the state space; A is the action space; 7 E [0, 1) is the discount
factor. We assume MDPs with countable S (discrete topology) and finite A. T S x A - A(S)
is the transition probability function; μ4 denotes the initial state distribution; R 8 x x A - ( denotes reward probability function. We use the following symbols to denote related conditional probabilities: T(''l8, a). R(-1s, a), 8, E S. E A. We also use r(s, a) ER-R(-Is..)) R for convenience. In order make the space of value functions complete (assumption of Banach fixed point theorem), we assume bounded rewards, which with discounting produce bounded value func- tions. We denote (x (X¹) the space of bounded sequences with supremum norm Il with support X' assuming X' is countable and has discrete topology. Completeness of our value spaces then follows from completeness of 120 (N)
The goal is to find a policy æ S ((A) that yield maximal return. The return is defined as the accumulated discounted reward from time step i... G, = Σn= ("*($t+ at+n). The state- value function (VF) of a policy is defined as the expected return of being in state s and following policy V (s) A E [Gt|s: s; x]. Let II denote the space of all policies. The optimal VF is V* max V It is also convenient to define the action-VF, Q (s. [Gass,
a;
and the optimal action- VF is denoted as Q" max Q The Bellman Expectation/Optiiaall
Equation and the corresponding operators are as follows:
V = V", where (B* (s) è Ea-a((s), (r(s, a) + vV (s')l
(1)
BV V", where (BV) max (r(s, + + t (s))]
(2)
3 HIGHWAY REINFORCEMENT LEARNING
Value Iteration (VT) looks ahead for one step to identify a promising value using only short-term information (see eq. 2). How can we quickly exploit long-term information through larger looka- heads? Our idea is to exploit the information conveyed by policies. We connect current and future states through multiple "highways" induced by policies, allowing for the unimpeded flow of credit across various lookaheads, and then focus on the most promising highway. Formally, we propose the novel Highway Bellman Optimulity Operator o (Highway Operator in short), defined by
(so) max max E.g wo =eñt neX
T'r + + max [r(sn, + 1E IV (11 (3)
where πT = (TTI.... 7m TM Rm E IT] is sei of behavioral policies, which are used to collect data; n is called the lookahead depth (also named bootstrapping step in RL literature), and A is the set of lookahead depths, which we assume always includes 0 (0 E A) unless explicitly stated otherwise; - (sg, ao, 81, a1, 82, a2, 02,...... s.)) and =h ~ π is the trajectory starting from so by executing policy π for n steps. Fig. 1 (Left) illustrates the backup diagram of this operator. Our operator can be rewritten using the Bellman Operators:
G V
max (B*)" BV.
(4)
xeil NEN
As implied by eq. (3) and eq. (4), given some trial, we pick a policy and a possible lookahead (up to the trial end if N is sufficiently large) that maximize the cumulative reward during the lookahead
'The space of all bounded sequences with supremum norm, which is known be complete metric space.
2

---

Under review as a conference paper at ICLR 2023
sialo
maax
(dancted) tondiio
1
Figure 1: (Left) Backup diagram of Highway Operator G. with N = {0, 1, 1. (Right) An illus- trative example of "highway" under simple N N-horizon MDP, where N the horizon between the start state and the end state sz. With the highway (dashed lines) induced by rolling-out behav- ioral policies, the start state 8 can directly access various deeper horizon information. By taking maximization over this information, the high credit information can be directly assigned to the pre- vious states through the highway.
interval plus a dynamic programming- estimate of future return. This provides a highway to quickly transport credit information from the future into the past. That's why our operator gen- erally converges faster than the classical Bellman Optimality Operator. See the detailed theoretical analysis in Section 5. Fig. 1 (Right) illustrates this highway through MDP problem and two policies. A highway connects the start state Sл to information derived from deeper lookaheads. In this example, our operator converges to the optimal VF within 2 iterations, while B needs N.
example: an N-horizon
The following result shows that our Highway operator is contraction the complete metric space loc and admits V as a unique fixed point.
Theorem (Properties of Highway Operator) For any î1 and N (s.t. 0 E N), we have
1) GN is a contraction on complete metric space (S),,,, i.e. for any V. V E (S))), we have? | V'l'l S |BV BVII S - V'll;
2) (Highway Bellman Optimality Equation, Highway Equation in short) V is the only fixed point R. that is, for all V (S) holds V =G if only if V*. Formally, we have
Give & max max (Br)") #eñl REN
"""""V'' BV =V*
V*,
(5)
3) For any Vo (S) and any sequence of policy sets (īg),,k: N, the sequence ( G tht [Vol.k N converges R-linearly V with convergence rate 7
All the proofs provided in Appendix A. Note that 0 E A is necessary for the guarantee of the fixed point property (Point 2), but not for the contraction property. This theorem implies that our Highway operator can provide powerful extension Bellman Optimality Equation, which can be potentially applied to various RI control methods. Table summarizes the comparison to classical Bellman Operators and some advanced operators. More details on the comparison are in Section
4 ALGORITHM
Here we illustrate three applications of our Highway theory for model-based and model-free RL algorithms. Although we listed only three instances in this paper, note that our theory can be poten- tially applied to various RL methods which involve value estimation, such as actor-critic methods.
We denote by ||- || the supremum throughout the paper.
3

---

Under review as a conference paper at ICLR 2023
NOT sullering explosion
Type
Opensoor
Fixed Point
Gunesnteed coevergence
Convergence Rate
Bellman Optimality Openator (oq.
Operators
Bellman Expectation Oyemtor 1 (og 1
V 10" sl.
Multi-Step Belmaan Optimality Openstr
E (8* y B
V* V²/
E
==x
(Hessel at al., 2018: Horgon et al., 2018)
Multi Step Offi Policy f Multi Multi-Step IS based Bellinan Expectation Operator
Openitor
Bxwpp (Sution
[8 }
v /0
Forany fi, N
7.
(Harutyuyyu al. 2016)
Q(A1 Operator
For st. f. is
7
Retracel A) Operator (Munus ol., 2016)
vT ///"
Forany fl
Highway Operator (oq.
V*/Q"
For any f
2 under some conditions!
Highway Ogentar and its Variants
N
c.t RCA
Softmax Highway Operutor
V//eg
Forany N.
G1L
" "mex" n'E ne (0.00
(8")"
relt
Expectation Highway Operator
V*/Q"
For any fi
Broup
mag (5"))"
Table Properties of the operators. II denote the set of behavioral policies; Pí a distribution over Il and Pn( (TT) is the probability of selecting क,; n' denotes the target policy of policy evaluation. and t: Please refer Appendix A.2 for details. $: B is the importance sampling-based (IS-based) Bellman Expectation Operator (see Appendix A.4).
4.1 MODEL-BASED REINFORCEMENT LEARNING
Highway Value Iteration. From the new operator, we can naturally derive new Value Iteration algorithm, (Algorithm B.1). Specifically, for finite S, the update using the Highway Operator G (eq. 3) can be written as
PART3
V&+1 max max eif BEA
max r + TT
(6)
PART2
PARTI
where V5 S column vector of VF; r and T" are |S| x 1 column vectors of rewards for action and policy æ respectively, where [r"], r(s,a), 1. Σ. x{als)r(s, a). Te and T are |S] x [S] matrices of transition probabilities for action a and policy π respectively, The computational complexity of
where [T]. s.s'
(s5lss, a), TT l.. - ((a)s)((s'|ss)
each iteration is O ((14)+ + π WI) [8|2) Two strategies can be adopted to accelerate the update
process. First, the matrix in PART and PART 2 in eq. (6) can be computed and reused for each π and n, as they fixed during the iteration process. Second, PART 3 can be computed in parallel for each policy II and n E N.
4.2 OFF-POLICY LEARNING IN MODEL-FRER REINFORCEMENT LEARNING
In model-free RL, is convenient use instead of V. The corresponding operator is defined
We use the same notation G denote the operator w.r.t. the the VF V and the action VF when there ambiguity. Similarly, for the Bellman operators, we will reuse the symbols.
4

---

Under review as a conference paper at ICLR 2023
Q ao) - max max E =en nEN
rT + ? n+ max Q 1.
a+1 ~ $00.00
ant1
(p
+++1 - (so. ao, To. $1, 01, Sn+1). This oper- where GQ (Trpttg) is the n + 1-step return; T 50.40 ator can also be represented by the Bellman Operators, i.e., Q - max, max, (8 BQ: and converges the optimal action VF Q" with any set of behavioral policies îi i.e. 9 (similar to Theorem I, see APPENDIX Theorem 6 for a formal statement). This means that it can utilize any off- aff-policy data collected by arbitrary policy, without additional corrections. We propose two methods for the tabular VF and VF approximation, named Highway Q-Learning and Highway DQN respectively.
Q"
Highway Q-Learning. Let D(m)) = (Tartd aagaa ~ mm) denote the trajectory data collected by the policy mm- The k-th VF Qu is updated in the following way:
DDim)) max max E foing [G (T )}:
Qx+1 (80, 00)
(8)
meM nEW
where Mon.oo
S
ml|
[
* 0f subset of indexes of the dataset that are not empty under sa.00l
(m))
(So: ao); E 20.00
((m)
[-]
Enn+1 n+1 Taging
EDim.
[ is the empirical averaged value. Note that all we
need to do is saving the trajectory data into the corresponding datasets D(m) Dooungs and then search over them, without having to know the form of nm or save the n. into the set of behavioral policies II. The algorithm, Highway Q-Learning, presented in Appendix Algorithm B.3.
Highway DQN. For large-scale space or continuous MDPs, the VF is usually approximated. Due to the estimation noise involved in function approximation (Van Hasselt al., 2016). our method may lead to overestimation by the two maximization operations (over policies and lookahead depths). However, as we show below, this issue can be easily solved through a minor modification.
We propose a new variant of eq. (7), named Softmax Highway Operator, as follows
Q (So, ao) - smar smar. max B
(G (F
xell n'EN nE(U,x) "0000
where the softmax operator smaz with the temperature parameter a is defined as
exp cxp (x))
smax #EX
(x) A
JEX Evex exp (af (x')) (x). fx).
Σ
(10)
smar reduces to max when 00. We have the following theorem.
Theorem For any a, any fi, and any N, we have GiQ' = Q" and (AQ E loo(S A)) | Q-1l < x|IQ Q*Il-
The operator in eq. (9) is derived in the following way. First, the Highway Q Operator G in eq. (7)
can be rewritten as equivalent form, c max, max,eeN maxne ( BQ. Then, we replace the first two max operators max, max,,' with the softmax operators smax smar
The above modification of Softmax Highway Operator G is necessary to a) remain unbiased w.r.t. Q' (as shown in APPENDIX Theorem 2) b) alleviate the overestimation issue and improve ex- ploration with the softmax operation, which has been shown effective recent RL literature (Fox et al., 2015; Haarnoja et al., 2017; Schulman et al., 2017; Song et al., 2019).
Note another variant smaz smar, (B*) BQ (without (D.w")) is generally biased w.r.t. Q- Please refer to Appendix A.3 for the detail of the reason.
5

---

Under review as a conference paper at ICLR 2023
Based on the above theoretically justified operator, propose the following objective function for updating the action VF Qo a) parametrized by the parameter #:
J]]
(0)
Σ
Qo (s0, an)
smax" smaz" max meMagin EE ne(D,n))
E
[G (Feg
(11)
(S0.00)ED
where Qa is the target network parametrized by 0', occasionally copied from 0: D = {(00, ao) }) is the sampled batch data of state-action (so; (o) pairs. The computational complexity of the method implied by the equation above is close to the one existing cligibility trace-based methods (Schul- man et al., 2016; Munos et al., 2016), which also need to compute n-step returns G for each n. The resulting algorithm is called Highway DQN, presented in APPENDIX Algorithm B.4.
In practice, our algorithm balances the trade-off between accuracy and sample efficiency by deciding the number of trials per policy, the size of the search space (of behavioral policies and lookahead depths), and the softmax temperature. While more trials per policy may improve the estimation accuracy, they may also cost more samples and reduce sample efficiency. On the other hand, while larger search space may increase efficiency, it might incur overestimation issues when the estimate is biased, leading to high variance.
In summary, our Highway Q-Learning and Highway DQN can recycle any trajectory data collected by some arbitrary policy, and utilize the multiple-step trajectory data that do not require Importance Sampling based corrections (as stated in Theorem and 2).
THEORETICAL ANALYSIS
In this section, we study the theoretical properties of Highway operator G and show its superiority over classical Bellman operators, e.g., B and 8" For convenience, our analysis is in the space of state VF, Le., the operators G B, F .... assumed to be mappings on Toc (8).
First, we compare our Highway Operator o to the Bellman Optimality Operator B.
Theorem (Comparison to Bellman Optimality Operator B) For all V, Vo E (S) holds: 1) 1 -v I ||BV - V=
2) Assume Vo S V For any s we have (o) - V (s) s BBV (s) - V* (s)), where the
strict inequality holds as long as there exists n' E such that arg max (Bx)) BV (s) > 0.
The first point of the theorem implies that our operator converges at the same rate as the Bellman Optimality Operator the worst case. The second point shows a state-wise convergence comparison under the case of Vo < V*. Our operator generally converges faster than the Bellman Optimality Operator as long as one behavioral policy finds a better path by looking forward for n steps (n >> 0). Note that the condition V/5 < V* can be easily satisfied by setting Vo min,' af r(s', a'). Moreover, as long as Vo < V*, we have (o < V* for any & (see Lemma 2 in Appendix).
V
Then, we show the relation of our Highway operator with the Multi-step Bellman Expectation op- erator By (B which is adopted in Generalized Policy Iteration (GPI) (see APPENDIX Algorithm B.2). GPI needs to balance the evaluation-improveneed parameter N in (B*)oN, Our Highway operator provides an optimal solution for deciding such hyperparameter N in terms of approaching the optimal VF.
trade-off by adapting hyper-
Theorem 4 (Comparison to Multi-Step Bellman Expectation Operator) Assume that the VF Vv S
By v denote the + 1-th VF of Highway Value Iteration with hyperparameter
V* Let V. '41 and
'Note that, unless otherwise stated, the results hold any set of behavioral policies îi and set lookahead depths N. For convenience, we analyze under fixed îT. However, these results can also be extended the case of dynamically changing IT (as shown Highway Value Iteration in Algorithm B. where îT₃ could change over different k-th iterations new policies added the set of hchavioral policies).

---

Under review as a conference paper at ICLR 2023
N and Generalized Policy Iteration with hyperparameter N. We have
Dg A+1
v*
-
min NEN
V*
(12)
k+1
Next, we show that by assuming that some of the behavioral policies act optimally within a few time steps, our Highway operator can achieve better convergence rates.
Assumption AiĪ.n) n) Given set of behavioral policies îi, lookahead depth Let S denote the set of all possible visited states by executing policy x' for n steps from state For each E S, there exists least one policy n' E II such that T' (s') = TT" (s') for any s' E S where x refers to an optimal policy. Note the quantification order: (4's E S, Ar² E M, As' E (n) T = =x=xx (s').
Theorem 5 (Belter Contraction Rate) Assume N 1 EN, f satisfies Assumption A A N - 1), and Vo E Loc (S) and Vo S V*, the convergence rate of IN is 7M,, i.e., lI V'll 7 MIV V*
This theorem implies that when the set of behavioral policies Il satisfies Assumption A(iI, 1), our operator G has a convergence rate of y Note that, in Assumption A .V- 1). fl is not required to include optimal policy л². Instead, it only requires that, for each state, there exists one policy that behaves well within a period (N - 1 consecutive steps), and the well-behaved policy could be varying towards different starting from each state. Note that this condition is much weaker than having some optimal or near-optimal policies included in the behavioral policy set. Specifically, Assumption A(ii' 1) can be satisfied by constructing II' = aT E A, (V' E S) Ta(als) = 1}, yielding convergence rate of 72.
Note that although the operator (B))N also leads to convergence rate of y our Highway operator f differs essentially from it. A major difference is that Highway operator G applies Multi-step Bellman Expectation Operator ) instead of applying Multi-step Bellman Optimality Operator (B)ON. In the model-free case, (B*) jo V can utilize the n-step trajectory data generated by i with minor cost (just by accumulating rewards within n-step, i.e., En 7" Tetn' + (sv(())) While (B)eN can only utilize the 1-step data and needs to update the VF N times (implying by eq. 2).
6 RELATED WORK
Multi-step RL methods has been studied in RL for a long history, including multi-step SARSA (Sut- ton Barto, 2018), Tree Backup (Precup, 2000), Q(a)) (Asis et al., 2017), and Monte Carlo methods (which can be regarded as co-step learning). X-return assign exponentially decaying weights de- pends on the decay factor (Sutton & Barto, 2018; Schulman et al., 2016; White White, 2016). Sahil et al. (2017) proposed more general form called weighted returns, which assigns weights to all n-step returns. Roughly, the lookahead depth, the decay factor, and the weights represent the prior knowledge or bias regarding appropriate CA intervals, usually tuned in case-by-case man- ner. Our method instead adaptively adjusts the lookahead depth in line with the quality of the data and the learned VF. Another similar work related to CA RUDDER (Arjona-Medina al., 2019), which trains an LSTM to re-assign credits to previous actions. Our methods derive a simple but sound principle for transporting the credit with minor cost.
Existing off-policy learning methods usually use additional corrections for off-policy data. Classical importance sampling (aSe-based methods suffer from high variance due to the products of IS ratios (Cortes et al., 2010: Metelli et al.. 2018). Several variance reduction techniques have been proposed. Munos et al. (2016)'s 's Retrace(A) reduces the variance by clipping the IS ratios, and has achieved great success in practice. Other work ignores IS: TB(A) (Precup, 2000) corrects the off-polic data by computing expectations w.r.t. data and estimated VF, using the probabilities of the target policy. Harutyunyan al. (2016)'s Q(A) corrects the off-policy data by adding off-policy correction term. Our method provides an alternative IS-free tool for off-policy learning. Similar to Retrace(A), it can safely use arbitrary off- off-po data. Moreover, it is very efficient, offering faster convergence rate under mild conditions. More research is needed, however, to understand how the variance of method compares to that of advanced IS-based variance reduction methods like Retrace(A).
7

---

Under review as a conference paper at ICLR 2023
Numbe offooms
(a) Multi-Room Environment
(b) Choice
(c) Trace Back
(a) shows results of model-based algorithms in Multi Polti-Room environments. The x-axis is the number of rooms. The y-axes for the three figures are total iteration, total samples, and total running time required by the algorithm, respectively. (b) and (c) in Choice and Trace Back environments: number of episodes required to solve the task, as function of the delay of reward. Average over 100 seeds, standard deviation.
Figure 2:
Searching over various policies and (or) lookahead depths to improve the convergence of RL systems an active field. Barreto et al. (2020) search over various policies while using only a fixed lookahead depth until the end of the trial. He et al. (2017) first propose to search over various lookahead depths along the trajectory data, but they do not search over various policies. Moreover, they employ the lookahead returns to construct additional inequality bounds on the VF. Our work instead contributes to a novel Bellman operator on updating the VF directly and provides a thorough theoretical analysis of the convergence properties. We also address that greedy operations (Barreto al., 2020; He et al., 2017) may cause overestimation, by proposing a novel softmax operation to alleviate this issue in an unbiased fashion. Compared to previous methods searching over the product of original policy space and action space (Efroni et al., 2018; 2019; 2020; Jiang et al., 2018; Tomar et al., 2020), ours has smaller search space (i.e., limited set of policies). In summary, this paper contributes theoretically-justtiee Bellman operator which searches both policies and lookahead depths, leading to more flexibility and scalability against different settings and applications.
Our method can also be viewed as combining the best of both worlds: (1) direct policy search based on policy gradients (Williams, 1992) or evolutionary computation (Rechenberg. 1971) (where looka- head equals trial length no runtime-based identification of useful subprograms and subgoals), and (2) dynamic programming-bast baasdd (Bellman, 1957) identification of useful subgoals during runtime. This naturally and safely combines best subgoals/sub-poliict (Schmidhuber, 1991) derived from data collected by arbitrary previously encountered policies. It can be viewed as a soft hierarchical chunking method (Schmidhuber, 1992) for rapid CA, with sound -based foundation.
7 EXPERIMENTS
We designed our experiments to evaluate the algorithms under different cases and investigate their properties. Please refer Appendix C for additional details of the experiment settings.
Model-based Toy Tasks. We first evaluate on model-based task: Multi-Room environments with different number of rooms. The agent needs to go through many rooms and reach the goal to get a reward. We compare our Highway Value Iteration to classical Value Iteration (VI) and Policy Iteration (PI). The algorithms are evaluated until convergence. As shown in the three plots of Fig. (a). our Highway Value Iteration outperforms VI and PI in terms of number of iterations required, total number of samples (total number of queries to the MDP model), and computation time.
Model-free Toy Tasks. To evaluate credit assignment efficiency, we evaluate the algorithms on two toy tasks involving delayed rewards (Arjona-Medl Medoina et al., 2019), in which a reward is only provided at the end of each trial. We compare our method to classical eligibility trace methods including Q(A), SARSA(A), Monte Carlo methods; and also the advanced credit assignment method RUDDER.
As shown in Fig. 2 (b) and (c), our method significantly outperforms all competitors on both tasks. For example, on Trace Back, our method requires only 20 episodes to solve the task, while the sec- ond best algorithm RUDDER requires more than 1000. Notably, the costs of Highway Q-Learning do not observably increase with the reward delays. In contrast, other methods such as Q(A) require exponentially increasing numbers of trials.
8

---

Under review as a conference paper at ICLR 2023
Highway DON
Mttt-Step DQN
Maxmin DQN
DON
Retrace
Breakeut
Seaqquest
Asturix
Freeway
Spare Invaders
390
meuti Crurs
Figure 3: Episode rewards during the training MinAtar Games (Young & Tian, 2019). Average over 5 seeds, standard deviation.
(a) Varying lookahead depths
(b) Varying replay buffer sizes
Figure 4: The performance of Highway DQN and Multi-Step DQN using (a) varying lookahead depth and (b) varying replay buffer sizes. Average over 5 seeds, 1 standard deviation.
MinAtar Games. We evaluate our algorithms benchmark tasks from MinAtar (Young & Tian, 2019). We compare to several advanced multi-step off-policy methods, including Multi-Step DQN (Horgan et al., 2018; Barth-Maron et al., 2018) and Retrace()) Munos et al. (2016). All multi-step methods are implemented on top of Maxmin DQN (Lan et al., 2020), which chooses the smallest Q- value among multiple target Q networks. All the compared methods adopt the same implementations to ensure that we measure differences between algorithms, not implementations.
Fig. 3 shows the performance of the algorithms. Highway DQN significantly outperforms all com- petitors in terms of both reward and sample efficiency on almost all the tasks. Compared to the advanced Retrace(A), our method performs significantly better on 3 of 5 tasks while performing on par with it on the remaining 2 tasks.
Ablation Study, We conducted the following ablation studies to investigate properties of Highway DQN. (1) Lookahead depth (N = (0. 1. ... N --1 11 for Highway DQN and N for Multi-step DQN). Multi step DQN, our Highway DQN shows strong robustness against variations of the lookahead depth. This is because Highway DQN can adaptively choose the lookahead depth. (2) Replay buffer size. As shown Fig. 4b, when the memory size increases to 8 10a (orange line), our Highway DQN shows a performance improvement, while Multi-Step DQN shows a degradation.
As shown in Fig. 4a, compared
(3) For the results with varying softmax Temperature a and number of target networks, please refer to APPENDIX Appendix C.4 for more details.
8 CONCLUSIONS
We introduced a novel multi-step Bellman Optimality Equation for efficient multi-step credit as- signment (CA) reinforcement learning (RL). We proved that its solution is the optimal value function and that the corresponding policy adjustments generally converge faster than the traditional Bellman Optimality operator. Our Highway RI. methods combine the best of direct policy search (where CA is performed without trying to identify useful environmental states or subgoals dur- ing runtime), and standard RL, which finds useful states/subgoals through dynamic programming. Highway RL quickly and safely extracts useful sub-policies derived from data obtained through previously tested policies. The derived algorithms have several advantages over existing off-policy algorithms. Their feasibility and effectiveness were experimentally illustrated on series of stan- dard benchmark datasets. Future work will theoretically analyze the algorithm's behavior in the model-free case.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
This paper provides a new operator for off-co learning-based methods. The authors do not find any particular concerns w.r.t the potential ethical or societal consequence.
REPRODUCIBILITY STATEMENT
The code is available at https: http://///nnooouuuuuou. 4open. science/ri
Hi giiggwyy-aa wonennoeeeeeeeeeerriinnn and implementation details can be found at Appendix and C.
REFERENCES
Jose A. Arjona-Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brand- stetter, and Sepp Hochreiter. Rudder: Return decomposition for delayed rewards. In H. Wallach, H. Larochelle, A. Beygelzimer, -'Aché-Bucc E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Kristopher De Asis, J. Fernando Bermandez-Garcin G. Zacharias Holland, and Richard S. Sutton. Multi-step reinforcement learning: A unifying algorithm. In AAAI, pp. 2902-2909, 2017.
André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117 (48):30079-3000 -00077 2020.
Gabriel Marth-Maron, Matthew W Hoffmaan, David Budden, Will Dabney, Dan Horgan, Dhruva Tb, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional deterministic policy gradients. arXiv preprint
2018.
Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1st
edition, 1957.
Maxime Chevalier-Boisee for openai gym. https: /ttthub..t.ttt/g com/ www.///wwwieee//aooooaaaaaaaaeae httpee//gmmmmiiiiii...... 2018.
Lucas Willems, and Suman Pal. Minimalistic gridworld environment
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances neural information processing systems, pp. 442-450, 2010.
Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Beyond the one-step greedy ap- proach reinforcement learning. In International Conference on Machine Learning, pp. 1387- 1396. PMLR, 2018.
Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. How to combine tree-search methods in reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 3494-3501, 2019.
Yonathan Efroni, Mohammad Ghavamzadeh, and Shie Mannor. Online planning with lookahead policies. Advances in Neural Information Processing Systems, 33:14024 1 2020.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with im- portance weighted actor-learner architectures. In International conference machine learning, pp. 1407-1416. PMLR, 2018.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint arXiv: 151008562 2015.
Tuomas Haarojj,, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. International Conference on Machine Learning (ICML), pp. 1352- 2017.
10

---

Under review as a conference paper at ICLR 2023
Anna Harutyunyan, Mare G Bellemare, Tom Stepleton, and Rémi Munos. (A) with off-cc corrections. In International Conference on Algorithmic Learning Theory, pp. 905-320. Springer, 2016.
Frank S. He, Yang Liu, Alexander G. Schwing, and Jian Peng. Learning to play in a day: Faster deep reinforcement learning by optimality tightening. In International Conference on Learning Representations, 2017. URL https: wpw./eeeerrr...eeeeeeee... net/ forum? d
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-second AAAI conference on artificial intelligence, 2018.
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Hasselt, and David Silver. Distributed prioritized experience replay. arXiv preprint arXiv: 1803, 1803,00933, 2018.
Daniel Jiang, Emmanuel Ekwedike, and Han Liu. Feedback- based tree search for reinforcement learning. In International conference machine learning, pp. 2284-28422202 2293. PMLR, 2018
Qingfeng Lan. A pytorch reinforcement learning framework for exploring new ideas. https: 2019.
//github. com/
Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin q-learning: Controlling the estimation bias of q-learning. In International Conference on Learning Representations, 2020.
URL https: /tttps://cpereeview net/ htt.rrrveeeeeeetttooureeeeeeaae forummiddBBguu33B
Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, pp. 5442 -454, 2018.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. Advances in Neural Information Processing Systems, pp. 1054-1062, 2016.
Doina Precup. Eligibility traces for off- off-policy policy evaluation. Computer Science Department Faculry Publication Series, pp. 80, 2000.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
I. Rechenberg. Evolutionsstrategic Optimierung technischer Systeme nach Prinzipien der biolo- gischen Evolution. Dissertation, 1971. Published 1973 by Fromman-Holzboog
Mark Rowland, Will Dabney, and Rémi Munos. Adaptive trade-off's in off-policy learning. In International Conference on Artificial Intelligence and Statistics, pp. 44. PMLR, 2020.
Sharma Sahil, Raguvir Girish, Ramesh Srivatsan, and Ravindran Balaraman. Learning to mix n-step returns: Generalizing lambda-return for deep reinforcement learning. CORR, abs/1705.07445, 2017.
URL http: http://xxvvv.r// org/ abs 0111//1555...55....
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arxiv::5111 05955,, 2015.
J. Schmidhuber. Learning to generate sub-goals for action sequences. In T. Kohonen, K. Mäkisara, O. Simula, and J. Kangas (eds.), Artificial Neural Networks, pp. 967-972, Elsevier Science Pub- lishers B. B. North-Holland, 1991.
Schmidhuber.
Learning complex, extended sequences using the principle of history compression. Neural Computation, 4(2):234-242, 1992.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. international conference learning representations, 2016.

---

Under review as a conference paper at ICLR 2023
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q- learning. arXiv preprint arXi::1004.06440) 2017.
Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International conference machine learning, pp. 5916-5925, PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelli- gence and machine learning, 4(1):1-103, 2010.
Manan Tomar, Yonathan Efroni, and Mohammad Ghavamzadeh. Multi-step greedy reinforcement learning algorithms. International Conference on Machine Learning, pp. 9504-9513 PMLR, 2020.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Thirtieth AAAI conference on Artificial Intelligence, 2016.
Martha White and Adam M. White. A greedy approach to adapting the trace parameter for temporal difference learning. CoRR, abs/1607 .0440004 2016. URL http: /ttp///axvvv////////////////.ava htrg/abs/1600 00446.
R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8:229-255 2222, 1992.
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for more efficient reinforcement learning experiments. 2019. URL /tt.tpp///erax...rr//////// 03176.
A THEOREM PROOFS
A.1 PROOF OF PROPERTIES OF HIGHWAY OPERATOR GN
Theorem (Properties of Highway Operator) For any Î1 and N (s.t. 0 N), we have
1) G is a contraction on complete metric space (S),), i.e. for any V, V E (So(S), we have - | V'lll S |BV BV'I S V>IVV-V' -VIl;
2) (Highway Bellman Optimality Equation, Highway Equation in short) V is the only fixed point Gh that for all V (S) holds V = =G&VV ifan only if = V*. Formally, we have
V V A max max (B*)" BV VV,
(13)
xeñ
3) For any Vo E lox(S) and any sequence of policy sets (fa),, E N, the sequence ( o NNN"
tth [Vo,, e N converges R-linearly to V with convergence rate 7
Proof: 1) The contraction property can be obtained:
1 - g/ = max max (BT)" BV max max (BT)" BV xeñ WEN
zeñ WEN
< max max (B") BV (B*)" BVII en nEN
< max max y |BV - BV' rell nEN
< || |BV BV
< 7 ||V v'Il
"We denote by ||
the supremum throughout the paper.
12

---

Under review as a conference paper at ICLR 2023
2) By application of the Banach fixed point theorem to point I., the operator 9 must have unique fixed point. Therefore, it suffices to verify that V is fixed point of g Our operator can be rewritten as
V max max (B*)* BV.
xeñ nEN
Using the fact that V < BV V and 8 monotony we obtain (B")" BV I V for any π and 2 0 (with the equality when = 0), which implies
"V* max max (B*) =V=== =V= V =iil nEN
|1 o - o... /
V 1-11= o of o.... .... NN [V[]
3) From 1) and 2) follows:
offy I*ll S >ll ..... /N [V6] -V By repeating the same argument we end up with ! NN "o...gN [Vo] V S x IV V*ll from which the statement follows.
Theorem For any a, any Il, and any N, we have NN Q" and (AQ loo A))
Q Q- S ~|Q Q*Il.
Proof:
Q (su, an) - smar smar. smar"smar"
max B xell n'EN nE(U,x)) 00 ~x
Go (T
(14)
This operator can be represented
G
A smar" " smax" max
(B")" (8")"BO, BQ.
well n'eN ne(o,n()
First, following the proof in Theorem I, have (B*)" BQ I Q" for any a and 2 0 (with equality when n = 0). Then, we have
smaz smar. max zeñ
n'EN (U,n))) (B*)" BQ Q"
Given action VF Q, let define distribution over ñi and N,, denoted by pasa and P such that
E Paippin nn upa
(B*)" BQ as, smar smar max (Br)" BQ (s.a) zeñ W'EN ne(u,e)
ne (0(0,)))
It follows
| 0-
smar smax" max TEll n'EN nE(O,n))
(B")" BQ -Q-
BamPhinn l ~PN
max (B*)" BQ IE Ex
max (B*)" BQ"
(0(nn)))
~NN
ne (0(0))
S max max [1(3))" BQ (B*)" BQ'1l =eñl neN
< - Q'11-
Corollary Assume Qo E (S x A) and 11,.k E N be sequence of sets of behavioral policies then the sequence W o zil-- o... [Qo,k e N converges R-linearly Q" with convergence rate %
Proof: The proof follows from just proved point Theorem 2 and proceeds analogically to proof of Theorem point 3).
m
13

---

Under review as a conference paper at ICLR 2023
Theorem (Comparison to Bellman Optimality Operator B) For all V, Vo (S) holds:
1) 1 V- I | II;
2) Assume Vo S VO. For any have (o) v (+) BBV6 (s) - V* (s)], where the
strict inequality holds as long as there exists T' II such that arg mNx (5+) " BVo (s) 0.
Proof: 1) has been proved in Theorem
2) Note that Vo 2 BV Further, Vo S V then V S V and BV 1 V* (as they are both monotonic). Putting all together obtain
0 0 /. Vo < <V* BVo
from which the desired inequality follows.
Theorem (Comparison to Multi-Step Bellman Expectation Operator) Assume that the VF Vi S
V*. Let & and V denote the + 1-th VF Highway Value Iteration with hyperparameter N and Generalized Policy Iteration with hyperparameter N. We have
6+1
V*
S
min
k+1
B V*
(15)
Proof: First, for any E EN, a' f, and any 8 E,
max (B")" BV (8) (Br) BV (8)
reñ TEA
According to Algorithm B.I, we know that The E i. Then, for any we have
V (s) v (s)
max max (BT)" BV2 (s) - V (s) refi nEN
(8)
max max (B*)² BVV (8)
=eñt nEN
min min (V* (s) - (B*)a BV, (5))
well ne.V
min min (BT)" BV2 (s) - V (s)
*eft neNV
< min ((**)* BV (8) V (s)
min NEN
(BTAA)
N+1 1/2 (8) - V (s)
V. B
min NEN
v (s)
from which the conclusion follows.
Assumption n) Given set of behavioral policies Î1 lookahead depth n. Let S denote the set of all possible visited states by executing policy n' for n. steps from state 8. For each E S, there exists at least one policy n' E fl such that at (s'))) ) = T" (s') ( for any s' E S where x" refers to an optimal policy. Note the quantification order: (Vs E S, 3n' I1 Vs' E SF')) : = = (s').
Theorem (Better Contraction Rate) Assume E N, fi satisfies Assumption A A N 1), and Vi loc(S) and Vo S V*, the convergence rate of ÿ is N,, iee. 1 V*Il s ~ M V*]l;
14

---

Under review as a conference paper at ICLR 2023
Proof: 1) First, if fi satisfies assumption Assumption A(i,, N 1), that is, starting from any s, there exists least one क II executing the optimal actions for N steps, then we have
V
max max (Br)) n BV
zi n'EN
(B*) N-1 BV
max tell
B N-1
BV.
Second, if & V*, then GVV V < V* (G is monotonic) and (B*)) ) Finally, with the results above, we have
N-1 BV V*.
| V - V2
N-1
BV - -va
5
137 N-1
BV (BT*) N-1
BV
S ~ | - V*Il-
To utilize the better convergence rates obtained theorem 5, we have to be a bit more careful than in theorem I point 3) and take care of the monotony requirements in theorem 5. This is done in the following lemma.
Lemma Assume a sequence of operators Tk, E N on (S), where all Tk satisfy (VV Loo (S), V S V*): I|T.V- - -V+ll S -V with common convergence rate o and common limit V* Further assume all Tg are monotonic and have fixed point V*. Then for any Vo E E N converges R-linearly to V with
oo (S): Vo I V* the sequence (Tg
convergence rate n
Proof: Assuming Vo 1 (8), Vo < V and monotony and fixed point of operators Ti Ti....; T implies: V == (Tx-1 0 o
[V]] I V* Now we can apply the inequality with y to get k- c...
[ o T o...Ti)[Vo
- [V] V*I. |. By repeating the same argument - VVII [ V*I from which the statement follows.
we end up with
Let us denote A (A: E N) the sequence of behavioral policies generated by Algorithm B.1. In Al- gorithm B.1 the set of behavioral policies Î1 changes by adding greedy policy every K iterations. Regardless of the sets IIg, the algorithm converges to the optimal value function form theorem point 3). This means that more and more close to optimal policies are added to II, set with growing iteration number k. When assumption Assumption A(,, n) gets satisfied for some n at iteration ku, then due to monotony of the sequence Ilg.k E N (i.e. the set IIg can just grow over time) Assump- tion A(, v2) is satisfied for the whole suffix A 2 ko. We then use lemma
corresponding suffix of operator sequence efl ,k 2 Kn with 7' n to claim better convergence rate (T*+1) of the corresponding suffix of value functions Vg. 2 kig- When S is finite this gives us monotonic im- provement of the convergence rate of the sequence Vg.k N as Assumption A(,, n) gets eventually satisfied for bigger and bigger n.
Theorem 6 (Highway Bellman Optimality Equation (Highway Equation) w.rl. action VF Q) For any Ii and N, we have
f is a contraction on complete metric space 100 x A), i.e. for any Q. E 12 x A), we have Q 2 < |BQQ- BQ'Il < >11 - Q'1l;
2. Q" is the only fixed point G.. That is,
2 Q'
(16)
15

---

Under review as a conference paper at ICLR 2023
for all Q (8 A) holds Q Q if and only i Q"
Proof: Note that G w.r.t action VF Q can also represented by the Bellman Operators w.r.t Q i.e.
@ Q - max max (B*)) BQ.
xell nEN
Except for the change of value spaces (S A) instead of (S)) the proof is the same for Theorem I).
Lemma 2 If Vo. S V*, then (o ofl-- o...o o Vo s V for any k and any sequence of policy sets I1, fl,......,.f. fIg.
Proof: As of is monotonic (for any set of behavioral policies ff), we have (G Wo & (V
V* Further, applying T again to the both sides we obtain (oW ل Vo & (G = V*. Repeting the argument further i times we get the result.
A.2 PROOF OF PROPERTIES MULTI-STEP BELLMAN OPTIMALITY OPERATOR
Recent works combined multi-step trajectory data and estimated the values of the most promising actions without any correction for the off- off-policy data (Horgan al., 2018; Barth-Maron al., 2018). The underlying operator is defined as
B (50; on) EENP (1**)~-IBQU an)]
(17)
-BAND n Ty
Σ 7'ra + 7 max Q (sN
a'y
where Pi is distribution over πl and Pit (Tr) is the probability of selecting л. Here use P and .V. Teg.og π to formulate the procedure of prioritized experience replay (Schaul et al., 2015: Horgan al., 2018), which samples the trajectory data collected by various behavioral policies according to a prior distribution. Although these methods have shown promising results in practice below will show that this operator is generally biased w.r.t. the optimal action VF Q', In other words, the corresponding fixed point O' j is different from the optimal VF Q", and unbiased learning only happens when all behavioral policies are optimal.
Theorem (Properties of the Multi-step Bellman Optimality Operator B For any N 2 2, 1) The operator BI, is a contruction on complete metric space (S x A), iee, for any two vectors
Q Q' E (S x A). 1 - 2 Q'll < < Q'll-
2) Let Q Bq denote the fixed point of BR iee., Q
BB = Qu gā. we have Q³ BB $ Q"
3) Q gg = Q" if and only if any x E î. P (T) > 0 satisfies (8) = (s) for any s E U == {s1 e
S sp, on, (( 1s0 0o) > 0} and n² an optimal policy.
Before giving the proof of the above theorem, we'd d like to mention variant of our Highway Oper- ator, named Expectation Highway Operator, defined as
JR Q(so. 0o) 2 ETNP NEN
max (Txx""""-1BB(6 ao)
(18)
Compared to the above Multi-Step Bellman Optimality Operator in eq. (17), our operator uses max- imization over lookahead depths instead fixed lookahead depth. It's interesting to note that this operator is unbiased w.r.t. Q" for any set of behavioral policies II. Formally, we have the following theorem.
16

---

Under review as a conference paper at ICLR 2023
Theorem 8 For any II, any Pir and any N.
1) In is a contraction on complete metric space 1o0 (S A), i.e. for any two vectors Q Q' E
(8 A), (VQ 18 A))= |9 Gū Q'Il 7|QQ Q']]; N
2) 9n Q" = Q
We now give the proofs of Theorem and respectively.
Proof of Theorem 7:
For simplicity, we will use P instead of PA
1)
| Q -
Q Q'll = ET-P | (BT)N-1BB BQ (BBr)
N-1 BQ¹)
>~ 11Q - Q''1
2) Applying Banach's 's fixed point theorem to B using the contraction result, we know that B has only one fixed point.
Following the proof in Theorem 1, we have (BM) S Q" for any x and N 2 2. This implies that
Q' 2 (B*) BQ¹ = =B
(19)
Using monotony of B (Q < Q' implies B S Q'),,, we get the monotonic sequence Q" 2 B" 2 (B 2 which converges the fixed point based the contraction property By
and Banach fixed point theorem:
Q' z Q 2 (B8) 2 ... (B > Sgg
(20)
3) For the implication we get
"-""i suffices to show for all π E f1, P(T) > 0 Q = Q- Since then
B Q² = Enpp ( N-1 = Em = =Q
and the implication is proved. Thus let us fix I1, P(x) 0 and so S.00 ag A the following holds Q² ($o. ag) = /a [r(8,, an) + 751" Since in the first expec- tation we just care about 8 for which (s|) (50, an) > O, we can assume 81 E U. As π on U can be replaced by the optimal policy x- from the assumption, get
1 Q" (So: 0n) = E,, -T (Ba (r (r(so, an) QQ"
Ex, T (1-so. ) (r [r(s, an) + (s), a1)] = (s).
The remaining implication " will be proved by contradiction. Assume that the conclusion does not hold, i.e. there exist E îī, P(r) 0 and 81 E U such that P(x)) and (-1ss)) is not optimal. Since $1 E U there exists so E SS000 ap A such that T(si ao) > 0. First we aim to prove inequality
BE Q= an) < Q" (s))ao). Since (-1s)) assigns positive probability to non-optimal action, it is easy to obtain (especially for finite A) that
Ear~z(-s)) Q" (S1, a1) Vs1)..
For other states different from 81 we can still have equality but the countable sum leaves the inequal- ity strict
(BT (50, an) r(so, an) + Egg~ (Ty-T(110000 E 1e) Q'(1. (s), r(sus an) + EE, ~ (T 1 (*( = Q' (su, ao).
Now since (BT)N-2 QQ S we get
N-1B0= (B*) N ( SBQQ
17

---

Under review as a conference paper at ICLR 2023
Using previous result obtain
au) - B"Q" (su. ao) < Q" au),
and applying expectation with finite set fî using P(T)) > 0 we get
B Q (so, an) < Q* (s0, ao);
which can be combined with eq. (20) show
Q B (80, an) < Q" (50, ao)
We now give proof of Theorem 8.
Proof of Theorem 8: 1) We first prove the contraction property,
g Q 9n Q'I s
BR-PH
max (B BQ mEN
Ex-Pn max (B*)) BQ')
$ Bm max (I(*B)) n BQ - (B*)" BQ'Il
$ 11 Q'Il
2) Similar to the proof in Theorem 1, (B*)" BQ" < Q* for any and 2 0 (and the equality holds when n O), we have
NN Q" 2 EaNPa
max TEN
(B*)" BQ"
Q"
A.3 DISCUSSION ABOUT SOFTMAX HIGHWAY OPERATOR
The Softmax Highway Operator is defined by
I e smax smar" max (B")"BQ, *eी n'EN nE(0,n))
If we remove the m) in the above operator, i.e.,
smar smax." (B*)" xeñ n'EN
then the above operator is biased w.r.t. Q¹. This operator can be regarded as an extension to the multi-step Bellman Optimality Operator B average over various n with weights smar." (.). There-
n'EN
fore, it has similar biased property to B However, simply adding max with minor compu- tational cost, our Softmax Highway operator is unbiased while alleviating the overestimation issue and improving the exploration.
A.4 MULTI-STEP IMPORTANCE SAMPLING-BAN BELLMAN EXPECTATION OPERATOR
In this section, describe the classical off- policy learning method based importance sampling (IS). IS-based off-policy methods evaluate the value function of a policy T' (called target policy) using the data collected by different policy (called behavior policy). The underlying opera- tor, called Importance Sampling- Bellman Expectation Operator (Sutton & Barto, 2018), is defined as follows.
('(a'ss') T(a's')) (r(s,a) + +)((s
8 ()) A
(21)
18

---

Under review as a conference paper at ICLR 2023
To utilize the sulti-step data collected by different behavior policies, the above operator be tended to a multi-step version with a set of behavioral policies (we call Multi-Step IS-based Bellman Expectation Operator) (Sutton & Barto, 2018), which is defined as
i1 (5% (50, on) - ETNP
(177)
M$(0 ao)
N-1
(22)
Σ
2 + ((oN,
7 7.0 mut
where N is the lookahead depth/bootstrappingg step; T (su, do 81, d1 82, d2 is the trajectory starting from so by executing policy for N steps; and çlit A II the product of IS ratios. The products of IS ratios could cause high variance.
SN): Teh
x (aplss)) is
[(ay(s))
B METHOD
B.1
ALGORITHMS
B.1.1
HIGHWAY VALUE ITERATION
The Highway Value Iteration algorithm is presented Algorithm B.1.
B.1.2
HIGHWAY Q-LEARNING
The Highway Q-Learning algorithm is presented as Algorithm B.3.
B.1.3
HIGHWAY DQN
The Highway DQN algorithm is presented as Algorithm B.4.
C EXPERIMENTAL RESULTS
The code of this paper is aublicly-available at https: /ttp://aoooooss.ppee.eciiiiiiii Hi Righwwy--eiiforceeee - Learning-4202.
C.I EXPERIMENTS WITH MODEL-BASED ALGORITHMM
C.1.1 DETAILS OF ENVIRONMENTS
Multi-Room is grid world environment with multiple rooms connected by doors. The agent's goal is to reach a goal square in the opposite comer and get a reward (r = 1000). addition, the agent will get small reward 0.001 when it finds the exit door of the room. We use the implementations based on the gym-minigrid Bnevvalir-Boiiverr et al., 2018).
Algorithm B.1 Highway Value Iteration
Input: Initial set of behavioral policies Nl the set of lookahead depths N; interval for adding new policy K
Initialize: Initial VF Vi RR. for =
do if (A: 1) mod K then (s) arg max, max,,r(sxaa) + yB. (V-
II f1,-1 U }
end if
V2 + G V
if [iV Vi-i 11 & then break end if
end for
19

---

Under review as a conference paper at ICLR 2023
Algorithm B.2 Generalized Policy Iteration (Sutton & Barto, 2018)
Input: the lookahead depth N. Initialize: Initial VF Vo IR [R|S).
for 1,2..... do
(*) arg mal.mras.a...e.aa. a) + yl (Vi-n(s')
V₂ f- (B**) Vk-1
if [ - V 11 I e then break end if
end for
Algorithm B.3 Highway Q-Learning
I: Input: Set of lookahead depths Nf Number of behavior policies M (for computing target value); Epochs running algorithm Lrunt Number behavior policies (for computing target Q value); Number of searched behavior policies M; Epochs of rolling-out policy Lottonts Epochs of updating value function Jupdate; Initial value function Qo E RISIXIA Exploration rate
Initialize: I 0; State-action replay buffer 0;
3: for m 1,... ,ran do
4: Set T.. to be e-greedy policy with Qx
5: D(m)) 4- 0, for all (s,a) E S A
6: for == 1,... rollout do
7: Collect trajectory
(s0, an, 70, 81, 01, ,8) with Fm-
for = 0,
do
9:
Add (st, Ct, Tt, Se+1, Oc+1, "rtl,"' ,8) to D( Add (se, ax)
10:
11:
end for
12:
end for
13:
for j= 1, Lupdate do
14:
Sample a (sa, ao) from D.
15:
Update the value function by the following rules
Qu+1 (So, un)
max max
B Paoin
[Got (7
m meMMapia
nEN
where poi
[1]
Σ
H
D
1eg.0g ED!
M Mao.00 = {mi, ... ,ma, m, ~ Uniform (fmm IDD +0})
16:
- 11
17: end for
18: end for
C.1.2 DETAILS OF ALGORITHMS
We compare Highway Value Iteration to Policy Iteration and Value Iteration. For Policy It- eration, the lookahead step is set by N = 10 (see Algorithm B.2). For our Highway Value Iteration method, the interval of adding policy is set by K 7: the of lookahead depths N (0, 1, ... 9): the size of behavioral policies is by [i] 5. The error bound ( Ve-illo I c) for all algorithms is set by c= 10
C.2 EXPERIMENTS OF MODEL-FREE ALGORITHMS TOy TASKS
Here we present the details of model-free-dae -ree---ro-lll in artificial tasks. We adopt the experimental setting of Arjona-Medina et al. (2019).
20

---

Under review as a conference paper at ICLR 2023
Algorithm B.4 Highway DQN
Input: Set of lookahead depths N; Number of behavior policies M (for computing target value); Epochs of running algorithm Tron Epochs of rolling-out policy Tollou:: Epachs of updating value function Fupdase Batch size updating value function b; Initial parameter of Q function; Exploration rate e: Temperature hyperparameter a for softmax function smax.
Initialize: State-action replay buffer D = 0: Initialize parameter 6' of target Q function, 0' +- 0. for m 1,-.. run do
Set T.. be e-greedy policy with Q
D 0. for all (s, a)
A
for -,..... drollout. do
Collect trajectory = (s0; ao, ro, $1, di,71,"! ,T) with n. for f = 0, 1,...
do
Add (St, 01, Ft, 1,,1, de+1s S141, Add (St, a.) to D
0.42, $14,,,125"""""" ST) to Dim)
end for end for for = 1, Juddate
Sample mini batch D = {s, a)} from D. Update by minimizing the following loss function:
I. (0)
Σ
(s,
smar smar max ?D (1 meMa,e n N'EN mE(0m))
(23)
(.,))
where
E
b
Σ
D
1+1 E (mn) "20.00 20.00
Mag.a0 {mi.... mM., mi Uniform (f (m'llpio''s + 0))
end for + every C' timesteps
end for
0
1
2
3
Door
4
5
6
7
Goal
Door
8
9
each -0.01
achieving goal: 1000
10
achieving the exit
11
door: 0.001
Start
12
achieving the entry door:
Figure 5: The illustration of the Minimalistic Gridworld Environment
21

---

Under review as a conference paper at ICLR 2023
C.2.1 DETAILS OF ENVIRONMENTS
We evaluate the model-free algorithms on two toy tasks involving delayed rewards (Arjona-Medina al., 2019), where reward is only provided at the end of each trial and is associated with the previous actions. For example, in task "Trace Back," the final reward depends on the first two actions. Each task run with 100 random seeds. task "Choice." the stochastic reward depends on the first action at the beginning; the final reward depends on the first two actions. Please refer to Arjona- Arjona-Medina Medina et al. (2019) for more details.
C.2.2 ALGORITHMIC DETAILS
The following methods are compared:
RUDDER with reward redistribution for Q-value estimation, and RUDDER applied on top Q-learning.
Q-learning with eligibility traces according to Watkins (Q(A)).
SARSA with eligibility traces (SARSA())).
Monte Carlo.
For RUDDER, we use the default setting of Arjona-Medina et al. (2019). For Q(A) and SARSA(A). the hyperparameter of eligibility traces is À = 0.9. For Q(A), we use Watkins' implementation.
The algorithms evaluated until the task is solved. For MC, Q-values the exponential moving average of the episode return. In all experiments, an e-greedy policy with e = 0.2 is adopted.
For our Highway Q-Learning, the set of lookahead depths N is set by {0, 2, , .N -1,, where is set to be the length until the end (7" is the length of trajectory and the timestep of current state). Epochs of rolling-on out policy is set by Irollout 1. Epochs of updating value function is set by /update = T.
N = T
C.3 EXPERIMENTS OF MODEL-FREE ALGORITTMM IN MINATAR TASKS
C.3.1 ENVIRONMENTAL DETAILS
This paper uses 5 games in MinAtar (Young & Tian, 2019), including Asterix, Breakout, Free- way, Seaquest, and Space Invaders. The details of the environments be found https: //github. www/ken/////eeeeeeco jyengggug/Maaa /MinAtar..
C.3.2 DETAILS OF ALGORITTM
We implement and competing methods by extending the implementation of Maxmin DQN Lan (2019). The hyperparameters of training deep neural network are provided in Table 2.
We reuse the syper-parameters and settings of neural networks in the Maxmin DQN paper (Lan et al., 2020). For Maxmin DQN, the best number of target networks (a hyperparameter) was chosen from [2, 3, 4, 6, 7, 8, 9] and the best learning rates were chosen from [3x 10 10-3, 10- The set of lookahead depths of our Highway DQN is set by {0, 1, -.. N - 1}. and the lookahead depth/bootstrapping step of Multi-Step DQN and Retrace()) is set by N. For our Highway DQN, Multi-Step DQN and Multi-Step SARSA, the best hyperparameter N was chosen from [4. 8. 12): the best learning rate from [3 x 10-30- 3, 3 10-1), and the best number of target networks was chosen from [2, 4, 6). For Retrace(A), A), À is set by according to the suggestion of Retrace(A) paper (Munos et al., 2016). For our Highway DQN, the best hyperparameter of softmax temperature a was chosen from 0.5). Epochs of rolling-out policy is set by Trollout 1.
10-$).
In practice, we adopt several measures to accelerate the computation of Highway DQN. We cache the values generated by the target network for data (s. a) such that they can be reused when the data is sampled again for training until the target network updated. With the cached Q values, all need is softmax over [W] [K] numbers, which is typically fast on GPUs.
22

---

Under review as a conference paper at ICLR 2023
Hyperparameter
Value
Optimizer
RMSprop
Batch size
32
Gym:5
Gradient Clipping
MinAtari:
Gym:200
Target network update frequency
MinAtari:1000
Gym: Fully-connected layer (64.64)
MinAtari:
Hidden units of Q network
Conv. layer(out channels=16, kernel size=3, stride=1) Conv. layer(out channels=16, kernel size=3, stride=1)
Activation function
ReLU
Gym: 10
Buffer size
MinAtari:100
Discount factor Y
0.99
Exploration rate
statr: 1.0; end: 0.1; decay type: linear
Table 2: Hyperparameters of the implemented algorithms. We reused hyperparameters and settings of neural networks the Maxmin DQN paper (Lan et al., 2020).
2=03
2-05
2=30
10.0
Num-
Spaciieacers
Space
tetof
(a) Varying softmax temperatures.
(b) Varying number target net-
work.
Figure (a) Performance (left) and Q values (right) of Highway DQN using varying softmax temperatures (b) Corresponding results using varying numbers of target networks. Average over seeds, standard deviation.
C.4 ADDITIOANL RESULTS ON ABLATION STUDY
We evaluate our Highway DQN with varying softmax temperature a and number of target networks. As shown in Fig. 6a and Fig. 6b, appropriate softmax temperature a and number target networks can reduce the overestimation of Q values and benefit the performance of the algorithm.
23


Reviews:
[{"review_id": "tICCvur0Wcc", "reviewer": "Reviewer_ftfH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper suggests a new way of doing multi-step RL using a Bellman operator that first performs a few steps of rollout via behavioral policies, and then doing one step of the optimal Bellman operator. The authors term this new method Highway RL. The paper first shows theoretical results (in an exact DP setting) and then shows how the new operator can be used in VI, Q learning, and DQN. Lastly, they show empirical results.", "summary_of_the_review": "It would be nice to see if the authors could take their idea and do a deeper analysis of how the operator behaves as a function of the quality of the behavioral policies. ", "strength_and_weaknesses": "Strengths: \n- The idea of using suboptimal policies that might need to better credit assignment is an interesting one.\n- The numerical results seem to be promising on a set of difficult problems.\n\nWeaknesses:\n- [Theorem 1] The fact that the new operator is a contraction eventually relies on the single step of B. I feel that it is misleading to state the ||GV - GV'|| <= ||BV - BV'||. In the proof of theorem 1, the fact that 0 \\in N is explicitly used (which, in effect, ignores all of the behavioral policies) to show the \\gamma-contraction property and the fixed point property. \n- [Theorem 5] This result was also underwhelming in that it is basically doing multi-step optimal Bellman operators. The assumption is stated in a way that makes it slightly weaker in that it requires one of the behavioral policies to be equivalent to the optimal policy at a subset of states.\n- A few other papers that use multi-step operators are: \n\"Online Planning with Lookahead Policies\"\n\"Feedback-Based Tree Search for Reinforcement Learning\"\n\"Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "h0dEmFly5R3", "reviewer": "Reviewer_7nDd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper is concerned with solving general reinforcement learning problems under the MDP formulation. The author(s) introduced a highway Bellman operator that enjoys nice theoretical properties when compared to standard one-step or multi-step Bellman operators. Built upon this Bellman operator, three RL algorithms are developed. Numerical studies were conducted to support the claims. ", "summary_of_the_review": "The paper develops a class of highway reinforcement learning algorithms based on a highway Bellman operator. The methods are novel in my opinion. The proposal is justified via theoretical results and numerical experiments. ", "strength_and_weaknesses": "As far as I can see, the advances of the proposal include:\n\n1. the introduction of the highway Bellman-operator;\n2. the development of the associated RL algorithms built upon the Bellman operator;\n3. the established theoretical results accompanying the Bellman operator;\n4. empirical verifications of the highway algorithm. \n\nBelow are some of the points to discuss:\n\n1. The proposed Bellman operator has very nice theoretical properties. Nonetheless, it seems to involve several hyper-parameters, including the set of the policies as well as the choice of the maximal lookahead steps. It remains unclear to me whether the operator and the associated algorithms are sensitive to the set of policies. How would recommend to set these hyper-parameters in practice?\n2. The theories are mainly concerned with the contraction properties of the Bellman operator. Could you please derive some theoretical results for certain highway algorithms?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XyaHUsfofd", "reviewer": "Reviewer_NWV2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes highway RL, which adaptively selects the policy and look-ahead steps for the Bellman operator. The proposed algorithm doesn't need off-policy corrections and hence doesn't suffer from the large variance. In addition, it can also achieve an improved convergence rate than the conventional one-step Bellman operator. The authors also present the application of Q-learning for both continuous and discrete domains. Empirically, the proposed variant can attain better results than the baseline methods, including Multi-step DQN, Maxmin DQN, and Multi-step SARSA on a series of RL benchmarks.\n", "summary_of_the_review": "Overall, I think the authors propose an interesting and theoretically justified idea for improving the convergence rate of the Bellman operator. The idea itself is novel. However, the new operator seems doesn't improve the convergence rate, and the per-step computational cost $O((|A|+|\\Pi||\\mathcal{N}|)|S|^2)$ is pretty large. So, I am not convinced about the improvement of the proposed operator over the standard Bellman operator or  $B^{\\circ N}$. I am happy to increase the rating if the authors can address my concerns raised in the strength and weakness section well. At the current stage, I recommend for rejection.", "strength_and_weaknesses": "Strength:\n- The entire paper is clearly written and easy to follow. \n\n-  The idea of highway RL is quite natural. The authors also provide theories for justification of the algorithm, though the derivations seem mostly to follow from the prior works on the one-step Bellman operator. \n\nWeakness:\n-  The computation of the proposed algorithm is very expensive for each step, though it can achieve an improved convergence rate. It needs to search over the product space of possible policies $\\hat{\\Pi}$ and possible lookahead steps $\\mathcal{N}$, which can be very large. Moreover, the algorithm is also much more complicated than the standard Bellman operator.. \n\n-  Theorem 5 shows that the proposed operator can achieve a convergence rate of $\\gamma^N$. However, if we apply the original Bellman operator for $N$ times for each time step, i.e., $B^{\\circ N}$, we should also achieve a convergence rate of $\\gamma^N$, right? If this is true, I am not sure what's the advantage of your operator over the $B^{\\circ N}$ operator. Let alone the per-step computational cost for your operator is $O((|A|+|\\Pi||\\mathcal{N}|)|S|^2)$ , and  $O(N|A||S|^2)$ for $(B)^{\\circ N}$.\n\n\n-  Can you provide a comparison with the method from He et al., 2017? This work is quite relevant, as they also proposed an algorithm for improving the convergence of Q-learning by looking ahead. The high-level idea is that they build the lower and upper bound of the Q function, and make them two constraints. So, when doing the Bellman update, it needs to solve a constrained optimization problem, which can be efficiently solved using the Lagrange multiplier trick. \n\n\n\n-  Abstract: \"We first derive a new multistep Value Iteration (VI) method that converges to the optimal Value Function (VF) with an exponential contraction rate but linear computational complexity\".\nLinear computational complexity in what? It would be better to state it more explicitly in the abstract, though it can be inferred from the later sections.\n\n- As you mentioned in the introduction (page 2), \n> \"It effectively assigns credit over multiple time steps\", \n\n  I feel the term \"credit assignment\" is a bit vague. What do you mean by assigning credit over multiple time steps? Can you provide a more formal explanation of this?\n\n- Can you explain more formally why your operator doesn't suffer from high variance? \n\n- For equations (9) & (11), why do you need to take a max over {0, n'}? \n\n- Do you have any results on Atari games? The MinAtar Games is not a very commonly adopted benchmark. It would be much more accessible for the readers if you have comparisons on more commonly used benchmarks.\n\n- Page 7: I don't understand why $(B)^{\\circ N}$ will incur a greater computational cost. For your algorithm, each step will suffer from a computational cost of $O((|A|+|\\Pi||\\mathcal{N}|)|S|^2)$ cost, while for $(B)^{\\circ N}$, the cost should only be $O(N|A||S|^2)$, which is smaller than yours. \n\n- Won't $|M_{s_0, a_0}|$ become very large for RL tasks, as the policy will be updated frequently in online learning? This will also increase the computational cost for each update step.\n\n - Figure 4 (a): it seems that increasing the number of steps doesn't improve the performance, and it even makes the performance worse. Can you explain why? \n\n\n======\nPost-rebuttal:\nThanks for the authors for answering my questions. I increase the rating to 5.\n\n[1] He, Frank S., Yang Liu, Alexander G. Schwing, and Jian Peng. \"Learning to play in a day: Faster deep reinforcement learning by optimality tightening.\"  ICLR 2017.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "F2sjv0O03t5", "reviewer": "Reviewer_dbJn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents highway RL, a novel dynamic programming-based strategy for off-policy RL that incorporates multistep information without requiring importance weights. Highway RL replaces the traditional Bellman backup by the maximum over both $n$ and $\\pi$ of the $n$-step return of $\\pi$ followed by the maximum over the learned value function (where $\\pi$ is taken from some candidate set of policies $\\hat \\Pi$). The algorithm is proved to converge in the model-based setting and it is shown that the rate can be better than standard VI under an assumption that the candidate policy set covers the optimal policy. The algorithm is then extended heuristically to the model-free setting. Experiments using the model-based algorithm in some toy problems and the model-free algorithm on MinAtar demonstrate performance better than the chosen baselines.", "summary_of_the_review": "Overall, I liked this paper and think it presents an interesting and novel algorithm. There are still a few issues regarding baselines and discussions of tradeoffs, but these do not seem like fatal flaws, so I rate it as a weak accept.", "strength_and_weaknesses": "### Strengths:\n\n1. The paper presents an interesting and novel idea that is potentially impactful in the off-policy RL community. It is a longstanding goal to be able to learn off-policy in a theoretically well-motivated way without needing high-variance importance weights. Hopefully the paper could spur follow-up work that tightens up the main ideas in the model-free case.\n2. The proofs seem to be correct, while limited to the model-based setting where the model of the environment is known to allow for exact computation of the relevant expectations.\n3. While the experiments are somewhat small-scale, they present consistent evidence of improvement, especially in the model-based case where the theory actually holds.\n\n\n### Weaknesses:\n\n1. Important baselines are missing from the experiments. First, there is no comparison to any importance-weighted off-policy algorithm like retrace. Such a baseline is important to actually substantiate the claims made in the paper about the benefit of avoiding importance sampling. Second, it seems from my reading that the Highway DQN algorithm uses maxmin DQN but the multi-step DQN baseline does not. The number of Q functions is important, see fig. 5b, so this seems to be an important issue. If this is the case, then a missing baseline is the multi-step DQN with maxmin learning on top to reduce overestimation and make a fair comparison to the implementation of highway DQN (if I have misunderstood how the implementation works, let me know).\n2. There is little to no discussion of the tradeoffs and potential weaknesses of the algorithm. In particular, I am somewhat concerned about what happens to the algorithm in the model-free case when rather than taking expectations of n-step returns under each of the candidate policies, we instead only see the one trajectory that already exists in the replay buffer. Especially in stochastic environments, maximizing over these single-sample returns seems like it may cause worse than usual overestimation problems and high variance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject