Multi-Step Generalized Policy Improvement by Leveraging Approximate Models
Authors: Lucas Nunes Alegre
Ana L. C. Bazzan
Ann Nowe
Bruno Castro da Silva
Venue: NeurIPS 2023 poster (2023)
Keywords: generalized policy improvement
successor features
transfer learning
model-based reinforcement learning
TL;DR: We introduce $h$-GPI, a multi-step extension of generalized policy improvement that interpolates between standard model-free GPI and fully model-based planning as a function of a parameter, $h$, regulating the amount of time the agent has to reason.

Abstract: We introduce a principled method for performing zero-shot transfer in reinforcement learning (RL) by exploiting approximate models of the environment. Zero-shot transfer in RL has been investigated by leveraging methods rooted in generalized policy improvement (GPI) and successor features (SFs). Although computationally efficient, these methods are model-free: they analyze a library of policies---each solving a particular task---and identify which action the agent should take. We investigate the more general setting where, in addition to a library of policies, the agent has access to an approximate environment model. Even though model-based RL algorithms can identify near-optimal policies, they are typically computationally intensive. We introduce $h$-GPI, a multi-step extension of GPI that interpolates between these extremes---standard model-free GPI and fully model-based planning---as a function of a parameter, $h$, regulating the amount of time the agent has to reason. We prove that $h$-GPI's performance lower bound is strictly better than GPI's, and show that $h$-GPI generally outperforms GPI as $h$ increases. Furthermore, we prove that as $h$ increases, $h$-GPI's performance becomes arbitrarily less susceptible to sub-optimality in the agent's policy library. Finally, we introduce novel bounds characterizing the gains achievable by $h$-GPI as a function of approximation errors in both the agent's policy library and its (possibly learned) model. These bounds strictly generalize those known in the literature. We evaluate $h$-GPI on challenging tabular and continuous-state problems under value function approximation and show that it consistently outperforms GPI and state-of-the-art competing methods under various levels of approximation errors.

Multi-Step Generalized Policy Improvement by Leveraging Approximate Models
Lucas N. Alegre!:2 Ana C. Bazzan' Ann Nowe² Bruno C. da Silva
Institute of Informatics, Federal University of Rio Grande do Sul Artificial Intelligence Lab, Vrije Universiteit Brussel University of Massachusetts (Inalegre, bazzan) @inf .frgs.br ann nonenoubeubbbe bsilva umass edu
Abstract
We introduce a principled method for performing zero-shot transfer in reinforce- ment learning (RL.) by exploiting approximate models of the environment, Zero- shot transfer in RL has been investigated by leveraging methods rooted in gen- eralized policy improvement (GPI) and successor features (SFs). Although com- putationally efficient, these methods are model-free: they analyze library of policies- each solving a particular task-and identify which action the agent should take. We investigate the more general setting where, in addition to a library policies, the agent has access to an approximate environment model. Even though model-based RL algorithms can identify near-optimal policies, they are typically computationally intensive. We introduce h--PI, a multi-step extension of GPI that interpolates between these extremes model-based planning-as as a function of parameter, h, regulating the amount time the agent has reason. We prove that h-GPI's performance lower bound is strictly better than GPI's, and show that h-GPI generally outperforms GPI as h increases. Furthermore, we prove that as increases, h-GPI's performance becomes arbitrarily less susceptible to sub-optimality in the agent's policy library. Finally, we introduce novel bounds characterizing the gains achievable by h-GPI a function of approximation errors in both the agent's 's policy library and its (possi- bly learned) model. These bounds strictly generalize those known in the literature. We evaluate h-GPI on challenging tabular and continuous-state problems under value function approximation and show that it consistently outperforms GPI and titt-oofthh-att competing methods under various levels of approximation errors.
model-free GPI and fully
Introduction
Reinforcement learning (RL) (Sutton and Barto, 2018) algorithms have achieved remarkable per- formance in challenging tasks both in the model-free (Bellemare et al., 2020; Wurman al., 2022) and the model-based (Bryant et al., 2022; Wu et al., 2022) settings. In these problems, agents are typically trained optimize one particular reward function task). However, designing agents that can adapt their decision making policies to solve novel tasks in a zero-shot manner-i.e. -ie. without requiring any further learning-remains an important open problem.
Various principled and efficient policy transfer methods, which combine peviousll-acqquree policies solve new tasks zero-shot manner, have been proposed based on the combination of successor features (SFs) and generalized policy improvement (GPI) (Barreto et al., 2017: 7: Borsa et al., 2019; Barreto et al., 2020; Kim al., 2022). On the one hand, SF's allow agents efficiently evaluate the performance of given policies in arbitrary sets of tasks. On the other hand, GPI extends the classic policy improvement procedure (Sutton and Barto, 2018) by analyzing library of previously-Iemm leamnd
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

policies-eate solving particular task and identifying a novel policy that simultaneously improves upon all policies in the agent's library.
We introduce h-GPI, multi-step extension of GPI that interpolates between these extremes- -standard model-free GPI and fully model- based planning-as
function of a parame- ter, h, regulating the amount of time the agent has to reason. An h-GPI policy is computed by performing online planning for h steps, us- ing an approximate model, and then employing GPI on all states reachable in h steps to iden- tify (in zero-shot manner) which actions the agent should take thereafter. See Figure 1 for an example.
h planning steps with approximate model
Sue
zero-shot GPI in states reachable h steps
bookstapping
bootstrapping
boobstrapiig
Our work is partially motivated by the observa- tion that state-of-the-art model-based RL algo- rithms (Hafner et al., 2019, 2021) often adapt poorly local changes in the environment (Wan al., 2022). Furthermore, environment models may have been learned and thus might be inaccurate. These observations underscore the risks involved in relying solely on approximate models for long-horizon planning scenarios, as model errors compound and may lead to catastrophic outcomes. Unlike techniques for dealing with approximate models, our method additionally exploits GPI's capabilities of efficiently performing zero-shot transfer in model-free manner. Other approaches- similar in nature to h-GPI- make use of models and GPI-based techniques. Thakoor et al. (2022), for example, introduced GGPI, method that learns state visitation models induced by particular policies rapidly evaluate policies under a given, known reward function. The authors show that performing GPI over a particular type of non-stationary policy produces behaviors that outperform those in the agent's 's library policy. h-GPI, by contrast, learns a different type of model: an environment model, which is used to perform planning faaning-i.e.,, action selection- rather than policy evaluation. Moreover, h-GPI exploits GPI to perform bootstrapping from all states reachable in steps. Section 5, we contrast our method with other related techniques, highlighting the unique aspects of our approach.
Figure 1:
h-GPI combines online planning with GPI leveraging learned model.
In this paper, we introduce the first principled method capable of exploiting approximate models and producing multi-step extension of GPI with formal guarantees. We prove that /-GPI's performance lower bound is strictly better than GPI's, and show that h-GPI generally outperforms GPI as prove that as / increases, /t-GPI's performance becomes arbitrarily
increases. Furthermore, less susceptible to value function approximation errors the agent's policy library. Finally, we introduce novel bounds characterizing the gains achievable by h-GPI function of approximation errors in both the agent's ' policy library and its (possibly learned) model. We empirically evaluate h-GPI in challenging tabular and continuous-stad problems with value function approximation. Our findings show that it consistently outperforms both GPI and other state-of tf-the-art methods under various levels of approximation errors. These results, combined with our method's 's formal guarantees, indicate that h-GPI is an important first step towards bridging the gap between model-free GPI-based methods and fully model-based planning algorithms-whir being robust approximate models of the environment and value function estimation errors.
2 Background
Before introducing our contributions, we review key concepts and definitions related to model-free and model-based RL, SFs, and GPI.
2.1 Reinforcement learning
RL problems (Sutton and Barto, 2018) are typically modeled Markov decision processes (MDPs).
An MDP a tuple M A (S, A. (,,.,,,,), 7), where S is state space, A an action space, pb (1||s, a) denotes the distribution over next states conditioned on state and action, r S x A x S + IR is a reward function, 4 an initial state distribution, and 7 E [0, 1) a discount factor. Let S,, A,, and R2 r(S,, Ar, S(+1) be random variables corresponding to the state, action, and reward, respectively,

---

at time step 2 O. The goal of an RL agent is to learn a policy S + A that maximizes the expected discounted sum of rewards (return) D:= Y R,. The action-value function of a policy is qº (s(s a) - E |=== MRR++ = s, A, = a), where [+1-]] denotes the expectation over trajectories induced by π and p. Given q", a greedy policy can be defined as x'(s) E arg max, 9" (s,a). It guaranteed that qa (s.a) 2 q" (s,a)). for all (s,a) E S x A. Computing q" and ' is done by processes known, respectively. as policy evaluation and policy improvement. Repeatedly alternating between policy evaluation and policy improvement steps known to lead to an optimal policy, x (*)), which maximizes the expected return from all states s E S (Puterman, 2014).
2.2 Successor features and GPI
The successor features (SFs) framework (Barreto et al., 2017) allows agents to efficiently evaluate the performance of a given policy when deployed under any represetatee reward functions, Tw (s, a, 5') (0s,, a, s') w. where ( a, s') R are reward features and w R are weights. controlled Markov process (S, A. P. ,1 y), i.e., an MDP without a reward function, when combined with reward features Φ x A x S + IRd induces a family of MDPs:
M _ {M- = (S, M.. (s, = Φ(s, a,s'). ..
Notice that the family of MDPs M represents all possible tasks (each defined by a reward function) that can be defined the environment associated with the corresponding controlled Markov process. Given policy its corresponding SFs, 20" (s, Rd, for state-action pair (s, a) are defined
(s, E
Σ 044 S = s,
(2)
where Φ, _ ((S Ar, 1(+1). Importantly, notice that given the SFs rb" (s, a) of a policy x, it is possible to directly compute the action-value function Iw (s, a) of n, under any linearly-eppressbble reward functions, Tw. as follows:!
Bw (s, a)
E Σ Dete W St = A, = = 16"
(8, a) W.
(3)
The equation described above whhch uses SFs to evaluate a given policy under different reward functions represents a process known as generalized policy evaluation (GPE) (Barreto et al., 2020). Notice that this process can be extended to the case where an agent has access to a set of previously- learned policies, IT { and their corresponding SFs, V { In N==1- Then, given any Ty E IT, GPE can be used to efficiently evaluate n; under any arbitrary reward function of interest,
Tw. via Equation (3): q (s, a) 2b² (s, a) w.
Generalized policy improvement. GPI generalizes the standard policy improvement process (discussed in Section 2. It assumes access to a set of policies (and corresponding action-value functions) and uses it to directly identify a novel policy optimizing a particular reward function, rw- Importantly, the novel policy is guaranteed to outperform all original policies the agent had access to. Definition 1. (Barreto et al., 2020) Given a set of policies 11 and a reward function policy improvement (GPI) is the process by which a policy, x', is identified such that
function Tw. generalized
Ow (s, a) Z max Iw (s, a) for all (s, a) E ESXX A.A A.
(4)
well
Based on Equation (4) and the reward decomposition (s, ((s,,,,5)) w. generalized policy, क : S x W + A, can then defined as follows:
π -GP s: w) E arg max max 2 (s,a). aEA #ell
(5)
Let (s. a) be the action-value function of policy x GPI w). The GPI theorem (Barreto et al., 2017) shows that x² GG w) satisfies Definition 1, and so Equation (5) can be used to identify a policy guaranteed to perform at least as well any other policies π; E II, when tackling new task, w. This theorem can be extended to cases where the agent only has access to an approximation of the action-value function, q of policy क, (Barreto et al., 2018).
Notice that the definition of SFs satisfies a form of the Bellman equation, where the features &, play the role of rewards. Thus, SFs can be learned through standard temporal-difie differenee learning algorithms.
3

---

2.3 Model-based RL
In model-free RL, agents do not have access to the environment state transition and reward functions, p and and must, instead, learn a policy solely based on samples obtained while interacting with the environment. Given an MDP, we denote m _ (p, r) as its model. In model-based RL, an agent given (or has to learn) an approximate model, m m. Agents may exploit models in different ways; for example, (i) to perform background planning (i.e., generating simulated experiences to more rapidly learn a policy or value function, as Dyna-style algorithms (Van Seijen and Sutton, 2013; Janner et al., 2019; Pan et al., 2019)); and (ii) to perform online planning (Barto et al., 1995; Chua et al., 2018; Efroni et al., 2020; Hansen et al., 2022).
In online planning methods, agents use a model to estimate the value of states by simulating the outcomes of particular sequence of actions. This is also known "unrolling the model forwards", from the current state, for a given number of time steps. Typically, online planning procedures are performed from every state the agent encounters, (MPC) algorithms (Camacho and Alba, 2013; Chua et al., 2018), Importantly, recent work-such as that of Wan et al. (2022) has shown that state-of-the-arr model- RL. algorithms (Hafner et al., 2019, 2021) often fail catastrophically when deployed in settings where the environment (e.g.. the MDP's reward function) may change. This observation underscores the risks involved in relying solely approximate models for long-horizon planning scenarios, since it is well-known that model errors compound.
in model-predictive control
We address these limitations by introducing a zero-shot transfer technique based on online planning. Our technique interpolates between standard model-free GPI and fully model-based planning accord- ing to parameter, h, regulating the amount of time the agent has to reason using an approximate model. Unlike previous methods that require re-learning or adapting models tackle novel tasks, our technique exploits approximate models and SFs to solve any tasks (defined as theeary-expressiteee reward functions) without requiring any further learning. Importantly, it has strong theoretical guarantees regarding its performance lower bound under various types of approximation errors.
3 Multi-step generalized policy improvement
We now introduce our main contribution, h--PI. This is a multi-step extension of GPI that combines online planning with approximate environment models to efficiently perform zero-shot transfer.
We start by defining the Bellman optimality operator T (and its multi-step variant) applied to action- value functions E Q, where Q is the space of action-value functions. To simplify notation, given a model m - (p,r). we denote Em as the expectation operator with respect to S.+1 ~ p(I|S,,AA and R2 _ r(St, Ar, S1+1). Similarly, we write r(s, a.) [s (r(s a, St+1)] for brevity. Definition 2. (Single- and multi-step Bellman optimality operators). Given a model m = (p,r), the single-step Bellman optimality operator, T Q + Q is defined as:
T'q(s, a) A Em ((s.a) + y max ((S s a'EA
(6)
T The repeated application T* for h steps gives rise to the h-step Bellman operator, denoted
(T*)")(s,a) a) 2 T Tgls g(s,a) Efroni al. (2018) showed that (T+ can be written as follows: T
h-tines
+ max h-1 ((S (T*)*a(s,a) a) Em ( = =, =
max
Em
Σ (r + 7 max g ((Senn, = =s,
a'EA
(8)
where μr is any policy (in an arbitrary policy space) the agent could choose to deploy at time i.
It is well known that T is a contraction mapping and its fixed-point (for any initial q E (Q) is q" (s,a) (Puterman, 2014).
lim (7*)"
We now introduce our first contribution: h-step generalized policy improvement, or h-GPI:

---

Definition 3. Ler 11 (a. be of policies and (p,r) be model. Then, given
horizon 2 O, the h-GPI policy on state & is defined as
π
E arg (T*)
max (s, xell
(9)
aEA
h-1
arg max aEAA
mI8X A1 Ph-1
Em
Σ
( ue (S++a))) +7
max max o' (Seth, IMo(S.) =
a' d'EA sell
K=O
online plasningg
GPI
(10)
where μ4 is any policy (in an arbitrary policy space) the agent could choose to deploy at time
Intuitively, h-GPI identifies a policy that returns the best possible action, a, by first planning with model m for h steps and then using GPI to estimate the future returns achievable from all states reachable in steps. This is in contrast with standard GPI policies, which can only reason about the future returns achievable from the current state, Sr if following given policy in II. /-GPI, by contrast, uses a model to reason over the decisions made at states within h steps from 8, as well as states, St+A- reachable after h steps. This makes it possible for h-GPI to produce policies that exploit the model-free, zero-shot return estimates produced by GPI when evaluating states beyond given horizon h; in particular, states that would otherwise not be considered by the standard GPI procedure when determining return-maximizing actions. Notice, furthermore, that h-GPI by construction interpolates between model-free GPI and fully model-based planning:
h-GPI induces policies that interpolate between (i) standard model-free GPI (when h 0) and (ii) fully model-based planning (when > oo).
In practice, agents seldom have access to the true model, m, an MDP, and instead rely on approximate models, m. The application of the Bellman operator under an approximate model, m. rather than the true MDP model, m, can be represented mathematically by replacing m with rn in Equation (6). This gives rise to medee-deepndent Bellman optimality operator, which we call T In what follows, we introduce Theorem 1, which extends the original GPI theorem (Barreto et al., 2017) and allows us to characterize the gains achievable by 4-GPI as function of approximation errors in both the agent's s policy library (II) and its (possibly learned) model m.. Notice that Theorem generalizes the original GPI theorem, which is recovered when h 0.
Theorem 1. Let II { be set of policies, { { be approximations of their respective action-value functions, and in (f,P) be an approximate model such that, for all π. E III and all (8,a) S A.
qThh (s. a) (s, se, Σ pl((s'ss, a) -(s''s, & Eps and (r(s, f(8, a(s,a))5G, S (11)
Recall once again the definition of h-GPI (Definition 3):
π (s) arg max max(T))
max q" (s, Tell
(12)
aeA
Then,
2 pP 2 (T*)* max (s.a)
1-9 (r c(cricp,h)) e(en
(13)
fell
max q" (s,
- (s + cleer li),
(14)
#Ell
where c(Er, Ep, (i) Lagh I- - (Er + " and v max., a (s,
Theorem characterizes the performance lower bound of h-GPI as a function of the number of planning steps, h, and the approximation emrors in the agent's 's model and action-value functions (i.e., errors e, Ep, and e,
5

---

Note that since (T*)* max (s. 2 max (", as, h-GPI's performance lower bound strictly better than GPT's (h- = 0) assuming no model approximation errors (c, = Ep 0). Furthermore, notice that as + co, (T*)* max=ell q" (s, a) converges to q" and the approximation error term (7*²) in Equation (13) disappears. In other words, as h increases, /-GPI's performance becomes arbitrarily less susceptible to sub-optimality in the agent's policy library. This implies that the planning horizon h trades off between two conflicting objectives. On the one hand, increasing the planning horizon h improves the performance of the h-GPI policy because the error term (e) associated with value function approximations errors becomes irrelevant. On the other hand, longer horizons worsen h-GPI's performance lower bound since they increase its dependency on errors arising from approximate models. Intuitively, for small values of h, the agent relies more heavily on the assumption that its estimates { } are correct, given that these estimates are discounted by y.. For large values of h, by contrast, the approximate model error term, c(er, Ep, h1,, increases, and the agent relies more heavily on the assumption that its (learee) model approximately correct.
Next, we introduce a novel upper-bound on the discrepancy between the value, on J-GPI of the h-GPI policy under a particular reward function, and the optimal action-value function, lw- Notice that, as in Theorem 1, we can recover the standard GPI bound when setting h = 0.2
Theorem 2. Let II {mi be a set of optimal policies with respect to reward weights (wa) and w be arbitrury reward weights. Let mn ()) be upproximate model and 1i Ji=1 be approximations to the action-value functions of policies in II, under the reward function Tw. such that for all E II and all (s, a) E S x A.
la (8,0) Tw (s, S.
Ele(slosa) - (()'18, s fps and [r (5, a) i (8, S 6r
(15)
We now extend the definition of h-GPI (Definition 3) to the case where this policy is defined under the assumption of an MPD with reward function Tw:
T. (s; ())
arg max(TT))) max 9w (s, a).
(16)
oEA
sEll
Let Dmax maxs, (16((8, a) |l. Then, it follows that
2
Rels, a) - ow G. (s. S I-7 @amor min w
w,ll + + + cp,r,,
(17)
where c(er, Epr h)
1 I (Er 7mpumax)-
Theorem 2 precisely characterizes the optimality gap (i.e., the maximum difference) between the action-value function induced by h-GPI (g a)) and the optimal action-value function (9th (s, a)), as function of (i) the reward weights (w,);,, 1 for which the policies in the agent's 's library, 11, are optimal; (ii) approximation errors in action-value functions #f In Jazi and (iii) approximation errors in the model m = (f, fw).
3.1 h-GPI under (learned) approximate models for zero-shot transfer
Recall that our goal is to perform zero-shot policy transfer to solve any tasks M E M (Equation (1)). In order to employ h-GPI on any given reward function of the form rw. (S,, A,, Sz+1) = Φ, w, we propose learning a model, m (p. Φ). that approximates both the state transition function, and reward features, Φb. The key insight is that this model implicitly induces the space of all MDP models m (p,, r,), based on (arbitrary) reward weights w E IRd. This allows employing RL model-based methods to multi-task settings without the need to re-train the model when solving new tasks defined by different reward functions. In Algorithm I, we present high-level description of how the h-GPI
policy G.. w) can be computed given model m (p, Φ). SFs (6) "i > and horizon h 2 0.
Tabular setting. In the tabular case, models can be learned via maximum likelihood estimates: vi(ss, $18 a) 2 N(s.a.0.s') where N(s, a, s') is the number of times the agent experienced the N(s.a)
'The proofs of Theorem I and Theorem 2 can be found in Appendix A.

---

Algorithm 1: /-GGI with Successor Features
Input:
Model ri (), SFs &&b "K= planning horizon h 0, state 8, reward weights w.
for action a E A do
Let St = =8, 10 (0(())
Compute (Tm) max (w (8,
max Eug
Σh- 7th Dit (Setks (E (S+(5))))) w + 7"h max max ib d'EA sell
(S) w
A1...Ah-11
Return: n 71-GPP((s ()) arg max A (Ta) max,, Ow (s,a)
transition (s, a, 8') and N(s, a) is the number of times the agent selected action in state 8. To efficiently compute the action given by the policy > (s, w) (line 3 of Algorithm 1), we extend the Forward-BB -Bakwad Dynamic Programming (FB-DP) algorithm (Efroni et al., 2020) to the discounted- SFs setting, in order to compute h-lookahead policies in real-time. The corresponding pseudocode can be found in Appendix B. Notably, given a state s, FB-DP time complexity is O (S) I), where N is the maximal number of accessible states in one step (maximal "nearest neighbors" from any state), and S is total reachable states in / time steps from state 8. Note that while we chose to extend FB-DP due to its efficiency and closed-form formulation, other planning techniques could have been used (e.g., Monte Carlo tree search (Tesauro and Galperin, 1996; Silver et al., 2017)).
Continuous-states setting. In the continuous-state setting, extend the class of models composed of ensembles of probabilistic neural networks (Chua et al., 2018) to the SFs setting. These models used in state-of- mate-of-the-aa art single-task model-based RL algorithms (Janner et al., 2019; Yu et al., 2021). The learned model (s' Φbs, 2.8,00 a). parameterized by şo, is composed of an ensemble of n neural networks, 1 each of which outputs the mean and diagonal covariance matrix of multivariate Gaussian distribution: myp, (S++1, Φb St, A.) = N ((o,, (St, Ad), Exp, (St, At)). Each model in the ensemble is trained in parallel to minimize the following negative log- likelhhoodd loss function, using different bootstraps of experiences in a buffer B = {(S,, At, Φ.. St+1) 2 0}: [(p)) A.s..A..d, ... S.-))=B( log (S(+1, Φ2 Se At]]- In practice, experiences the agent collected while training the SFs for the training tasks. In order to compute the h-GPI policy in this setting, we approximate the expectation over next states by averaging over the predictions of the components of the ensemble (Chua et al., 2018).
as B the buffer with
We employ universal successor features approximators (USFAs) (Borsa al., 2019) to learn SFs in the function approximation setting. Given sufficiently expressive USFAs, we can evaluate the value function of any policy Tx (optimal for task z) in any task
F by simply computing Aw (s)a) (ss,, a, z) w. Furthermore, when using a USFA to generalize to new task w', GPI (Equation 5) becomes: n GP w) E arg max a maxwEM (0(8,, a, w) w', where M is typically a set of weight vectors used when training the USFA. Notably, we only require a single USFA &b and a single model m to perform h-GPI given any M E &Ma. in contrast other approaches that require learning complex model for each policy in the library (Thakoor et al., 2022).
Notice that although we assume that during training the agent can observe and add its buffer B the features Φb at each time step I, our method could also be applied to the setting where the features are learned beforehand in pre-training phase (Hansen al., 2020; Carvalho et al., 2023). Learning appropriate reward features & is an important but orthogonal problem to the one tackled in this paper.
4 Experiments
We conduct tabular and deep RL experiments in three different domains to evaluate the effectiveness of h-GPI as a method for zero-shot policy transfer.
First, we consider the tabular FourRoom domain (Barreto et al., 2017). To make this domain more challenging, we made its transition function stochastic by including 10% chance of the agent moving to a random direction after taking any action. In FourRoom, the reward features Φ E 3 correspond to binary vectors indicating whether the agent collected each of the three types of objects in the map. The second domain is Reacher (Alegre et al., 2022a), which consists of a robotic arm that can apply torque to each of its two joints. The features o, F2 are proportional
Environments.
7

---

Median
IQM
10-GPI
8-GPT
6-GPI
4-GPI
2-GPI
1-GPT
MPMP
MP
B0MPC
GPI
0.64
0.72
0.50
0.64
0.72
0.80
0.06
0.04
0.72
0.80
Normalized Return
Figure 2: Median, IQM, and mean normalized returns over a set of test tasks in the stochastic FourRoom domain. h-GPI performance significantly improves as h increases.
to the distance of the tip of the arm to four different targets. Finally, extend the FetchPush domain (Plappert et al., 2018), which consists of fetch robotic arm that must move a block to a target position top of a table by pushing the block with its gripper. The reward features O R are the negative distances of the block to each of the four target locations. The action space was discretized in the same way usually done in Reacher. Importantly, the state space of this domain is high-dimensional (S C R 19) and its dynamics are significantly more complex than Reacher's. s. A more detailed description of the domains can be found in Appendix B.
Baselines. We compare h-GPI with standard GPI (Barreto et al., 2017), which is equivalent to h-GPI when h O. To showcase the importance of combining model-based planning with model-free action-value estimates, we in-
Moan Nornalized [eetuz
0.30
0653
clude an SF-based MPC approach, which is equivalent to h-GPI but without GPI bootstrapping That is, given a task w, it selects the first action from a se-
0.90
time step h.
0.75
R-CPE
CPI V10,000
quence of actions that maximizes E, A-11 o 7 2ith w].
A-GPI V10.0.1)
(-CPI - N10,000
and re-plans at every time step. In the function approxima- tion case with USFAs, we also compare with Constrained GPI (CGPI) (Kim al., 2022). CGPI is state-of-ther method that computes lower and upper bounds for the op- timal value on new tasks and uses them to constrain value approximation errors when following the GPI policy.
SF SF-3IPC
0.53
Figure 3: h-GPI, under various levels of errors in the SFs, function of h.
Based on the theoretical properties introduced in Section 3, we expect the following hypotheses to hold. HI: h-GPI performance better generalizes to unseen test tasks than standard GPI and, in general, improves as we increase h. H2: h-GPI more robust approximation errors in the learned SFs than GPI, and such errors have a decreasing impact as h increases. Additionally, we investigate whether H3: h-GPI can be scaled up to solve problems with high-dimensional state spaces. In each experiment, we report the median, interquartile mean (IQM), and mean normalized returns with their 95% stratified bootstrap confidence intervals (Agarwal et al., 2021), which are obtained by evaluating agents trained with 20 different random seeds on set of test tasks. For faimeess of comparison, we used the same agents for evaluating each method. We follow previous works (Borsa et al., 2019; Kim et al., 2022) and use training tasks the weight vectors that form the standard basis of Rd in all three domains. In FourRoom, we use 32 weights vectors equally spaced from the weight simplex
{w) Dd i= w7 1, wi 2 0} as test tasks. For Reacher and FetchPush, we follow Kim et al. (2022) and use weight vectors defined by 11 as test tasks. Notice that this results in many tasks with negative weights, which are significantly different than the training tasks.
In Figure 2, we can observe that 4-GPI is able to outperform GPI even with small planning horizons (see, e.g., 1-GPI). As h increases, the performance the test tasks consistently increases. This is in accordance with Theorem and H1. Notice that even with a small planning horizon of h = 2, h-GPI is capable of matching the performance of SP-MPC even when SF-MPC is allowed to plan for ten times longer (i.e., 20).
Next, to investigate H2, we evaluate h-GPI after artificially adding Gaussian noise with different standard deviations to the learned SFs of each of the agent's policies for every state and action. We can notice (in Figure 3) that standard GPI (h- 0) catastrophically fails under all levels of
8

---

Median
IQM
5-GPI
4-GPI
3-CPI
2-GPI
I-GPI
SMP
GPI
CGP]
0.72 0.80
0.88
0.96
0.50
0.55
0.56
0.72
0.80
0.86
Normalized Resurn
Figure 4: Median, IQM, and mean normalized returns over test tasks in the Reacher domain.
Mediam
5-GPT 4-GPI
3-GPT
2.GPI
I-GPI
15
1MPC
5-PPC
OCPI
GPI-ST
0.22 0.78
0..44
0.90
0.84
0.58
0.72
0.79
0.84
0.50
Normaliood Return
Figure 5: Median, IQM, and mean normalized returns over test tasks in the FetchPush domain.
approximation error. In all cases, h-GPI can closely approximate the same performance levels as those resulting from settings with no added noise. To do so, suffices to use sufficiently large In other words, h-GPI successfully and effectively identifies policies that are robust to noise due to its ability to combine model-free GPI generalization and planning under approximatefimpertie for h steps. This is consistent with theoretical results that show that value function approximation emros impact the performance's lower bound by a factor of na
models
In Figures 4 and 5, we show the results in the Reacher and FetchPush domains, respectively. Given a test task w', Iet GPI-ST be the policy that uses both the source/training (S) and target (T) tasks, MU U [w'}, as input to the USFA when performing GPI. Similarly, we refer to GPI as the policy that performs GPI only over the training tasks M. The CGPI policy was unable to significantly improve performance
GPI-ST, which hypothesize may be due to USFA errors in the training tasks, or due to overly small minimum rewards used in its upper- upper-bound. Both are known limitations of CGPI (Kim et al., 2022). In both domains with function approximation using USFAs, h-GPI outperforms the competing methods, which supports H1 and H3. the FetchPush domain, in particular, SF-MPC is allowed plan for up to h=15 steps; that is, three times longer than the maximum horizon we allow h-GPI to plan. Again, h-GPI consistently outperforms it (and other baselines) when allowed plan for significantly fewer steps. Interestingly, in the FetchPush domain, 4-GPI's performance slightly decreases for intermediate values of h. which suggests that its policy is being affected by model approximation errors. Even so, the mean returns achieved, for all values of h are higher than the ones achieved by GPI. This demonstrates the robustness of l-GPI to approximate models of the environment and function approximation errors.
5 Discussion and related work
We now discuss the works most closely related to h-GPI. Further discussions can be found in Appendix C.
GPI and SFs. Previous works have extended GPI to safe RL (Gimelfarb et al., 2021; Feng et al., 2023),
maximum-entropy RL (Hunt et al., 2019), unsupervised RL (Hansen al., 2020), and hierarchical RL (e.g., via the options framework) (Barreto et al., 2019; Machado et al., 2023). Recently, Thakoor (2022) introduced Geometric GPI (GGPI). GGPI uses geometric horizon models (GHMs) to learn the discounted future state-visine visitvisittiion distribution induced by particular policies to rapidly

---

evaluate policies under given, known reward function. The authors show that performing GPI over particular type of non-stationary policy produces behaviors that outperform those in the agent's library policy. h- by contrast, learns different type of model: an environment model, which is used to perform planning-i.e. action selection-ratiie learning separate GHMs for each policy in the library, whereas h-GPI can operate with a single model that predicts the next reward features, alongside a single USFA. Secondly, GGPI assumes that the reward function is known a priori, while we exploit SFs to generalize over all línear rewards given reward features. Bagot et al. (2023) introduced GPI-Tree Search (GPI-TS), which is closely related to h-GPI. GPI-TS uses GPI bootstrapping backup value estimates at the leaf nodes of Monte Carlo tree search. However, GPI-TS does not employ SFs and was only designed to tackle single-task settings. Moreover, it assumee oracle model of the environment. We, by contrast, exploit learned models to perform zero-shot transfer over multiple tasks and show how approximation errors in the model affect the performance of the h-GPI policy (see Theorems 1 and 2). Kim et al. (2022) introduced Constrained GPI (CGPI), which uses lower and upper bounds of the value of a new task to constrain the vation-value estimates used when selecting the GPI policy's s action. Although CGPI is able to deal with generalization errors in the values given by USFAs for target tasks, it is sensitive to errors in the value estimates for the training tasks. h-GPI, by contrast, can deal with approximation errors in the value functions of the source/base policies. Other works have studied methods for constructing a policy library for use with GPI (Zahavy et al., 2021; Nemecek and Parr, 2021: Alver and Precup, 2022: Alegre et al., 2022a) and for learning different SF-based representations (Lehnert and Littman, 2020; Touati and Ollivier. 2021). These methods solve important orthogonal problems and could potentially be combined with h-GPI.
than policy evaluation. Additionally, GGPI requires
Multi-step RL algorithms. Multi-step RL methods were extensively studied for policy evaluation, both in the model-free (Hessel et al., 2018; 8; van Hasselt et al., 2018) and the model-based settings (Yao al., 2009; Janner et al., 2019). Model value expansion algorithms (Feinberg al., 2018; Buckman et al., 2018; Abbas et al., 2020) are a significant example of the latter. In this work, by contrast, we introduce a multi-step method for policy improvement in transfer learning settings. GX-Chen et al. (2022) introduced the 77-return mixture, a new backup target for better credit assignment, which combines bootstrapping with standard value estimates and SFs, as a function of a parameter 1). Efroni et al. (2018) studied multi-step greedy versions of the well-known dynamic programming (DP) policy iteration and value iteration algorithms (Bertsekas and Tsitsiklis, 1996), and Efroni et al. (2020)
proposed a multi- step greedy real-time DP algorithm that replaces 1-step greedy policies with a h-step lookahead policy. Our work also related to the techniques introduced by Sikchi et al. (2022) and Hansen et al. (2022), which combine planning and bootstrapping with learned value estimates. However, unlike h-GPI, these methods do not address the multi-pole multi-policy and zero-shot transfer settings. We also note that there exists neuroscientific evidence that multi-step planning occurs in the brains of humans and other animals (Miller and Venditto, 2021). Finally, we believe that our work also shares similarities with the investigation performed by Tomov et al. (2021) on how model-free and model- based mechanisms are combined in human behavior.
Conclusions
We introduced h-GPI, multi-step extension of GPI that interpolates between standard model-free GPI and fully model-based planning. Through novel theoretical and empirical results, we showed that h-GPI effectively exploits approximate models to solve novel tasks in a zero-shot manner. Notably, in our experiments, and consistent with the introduced theorems, we showed that 4-GPI is less susceptible to value approximation errors and that it outperforms standard GPI and state-of-the-an competing baselines. Our findings hold even in high-dimensional problems where imperfect learned models are used. These results, combined with our method's strong formal guarantees, indicate that h-GPI is an important first step towards bridging the gap between model-free GPI-basee methods and model-based planning algorithms- whhle also being robust to approximation errors.
Limitations and future work. The main limitation of h-GPI is that it can introduce computational overhead for large values of h. In future work, this can be tackled by designing heuristics for use when performing online planning, or via principled methods to dynamically select the best value of h. Another interesting direction is integrate uncertainty estimation techniques (e.g.. implicit value ensemble (Filos et al.. 2022)) into the h-GP! policy to further reduce the impact of high model or value function approximation errors. Finally, regarding potential direct negative societal impacts of this work, we do not anticipate any.
10

---

Acknowledgments and disclosure of funding
This study was financed in part by the Coordenação de Aperfeigoamento de Pessoal de Nível Superior Brasil (CAPES)- Finance Code 001; CNPq (Grants 140500/2021-9, 304932/2021-3); FAPESP/MCTI/GI (Grant 2020/05165. 1); the Research Foundation Flanders (FWO) [G062819N]] the AI Research Program from the Flemish Government (Belgium); and the Francqui Foundation.
References
Abbas, Z., Sokota, S.. Talvitic, E., and White, M. (2020). Selective dyna-style planning under limited model capacity. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pages 1-10. PMLR. C.C
Agarwal, R., Sehwarzer, M., Castro, S., Courville, A., and Bellemare, M. G. (2021). Deep reinforcement learning at the edge of the statistical precipice. Beygelzimer, A.. Dauphin. Y., Liang, P., and Vaughan. J. W., editors, Advances in Neural Information Processing Systems 34 (NeurIPS 2021). 4
Alegre, L. N., Bazzan, A. C., and da Silva, B. C. (2022a). Optimistic linear support and successor features as basis for optimal policy transfer. In Chaudhuri, K., Jegelka, S., Song. L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 394 413, PMLR. 4, 5, B.3, C
Alegre, L. N., Felten, F., Talbi, E.-G., Danoy, G., Nowé, A., Bazzan, A. L. C., and da Silva, B. C. (2022b). MO-Gym: A library of multi-objective reinforcement learning environments. In Proceedings of the 34th Benelux Conference on Artificial Intelligence BNAIC/Beneleam 2022. B.2, B.2
Alver, S. and Precup, D. (2022). Constructing good behavior basis for transfer using generalized policy updates. In Proceedings of the Tenth International Conference Learning Representations.
Bagot, L., D'eer, L.,, Latré, S., Schepper, T. D., and Mets, K. (2023). GPI-Tree Search: Algorithms for decision- time planning with the general policy improvement theorem. In Proceedings of the Adaptive and Learning Agents Workshop (ALA 2023). 5,
Barreto, A., Borsa, D... Hou, S., Comanici, G., Aygün, E., Hamel, P., Toyama, D., Hunt, J., Mourad, S., Silver, D., and Precup. (2019). The option keyboard combining skills reinforcement learning, In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA. Curran Associates Inc. C
Barreto, A., Borsa, D., Quan, J., Schaul, T., Silver, D... Hessel, M., Mankowitz, D., Zidek, A., and Munos, R. (2018). Transfer in deep reinforcement learning using successor features and generalised policy improvement. In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 501-510, Stockholm, Sweden. 2.2
Barreto, A., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., van Hasselt, H. P., and Silver, D. (2017). Successor features for transfer in reinforcement learning. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processigg Systems, volume 30. Curran Associates, Inc. 1, 2.2, 2.2, 3, 4, A, A, A, B.2, B.2
Barreto, A., Hou, S., Borsa, D., Silver, D., and Precup, D. (2020). Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 1 117449)30079--3087. 1, 2.2,
Barto, A. G., Bradtke, J., and Singh. S. P. (1995). Learning to act using real-time dynamic programming. Artificial Intelligence, 72(1):81-138. 2.3
Bellemare, M. G., Candido, S., Castro, P. S., Gong, J., Machado, M. C., Moitra, S., Ponda, S., and Wang, (2020). Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77- 82. 1
Bertsekas, D. and Tsitsiklis, J. (1996). Neur-dynamic programming. Athena Scientific, Belmont, MA. 5, C
Borsa, D., Barreto, A., Quan. J., Mankowitz, D. J., Munos, R., Hasselt, H. V., Silver. D., and Schaul, (2019).
Universal successor features approximators. In Proceedings of the 7th International Conference on Learning Representations (ICLR). 1,4, 4. B.3
Bradbury, J.. Frostig. R. Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., Vander- Plas, J.. Wanderman-MMi Milne, S., and Zhang, Q. (2018). JAX: composable transformation of Python+NumPy programs. B.3

---

Bryant, P., Pozzati, G., Zhu, W., Shenoy, A., Kundrotas, P., and Elofsson, A. (2022). Predicting the structure of large protein complexes using alphafold and monte carlo tree search. Nature Communications, 13(1):1-14. 1
Buckman, J., Hafner, D., Tucker, G., Brevdo, E., and Lee, H. (2018). Sample-efficient reinforcement learning with stochastic ensemble value expansion. In Bengio, S... Wallach, H., Larochelle, H., Grauman, K., Cesa- Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc. C
Camacho, F. and Alha, C. (2013). Model Predictive Control. Advanced Texthooks in Control and Signal Processing. Springer. 2.3
Carvalho, W. T., Filos, A., Lewis, R., Lee, H., and Singh, (2023). Composing task knowledge with modular successor feature approximators. In Proceedings of The Eleventh International Conference on Learning Representations.
Chua, K., Calandra, R., McAllister, R., and Levine, S. (2018). Deep reinforcement learning in handful of trials using probabilistic dynamics models. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pages 4759 4770, Red Hook, NY, USA. Curran Associates Inc. 2.3, 4, B.3
Dayan, P. (1993). Improving generalization for temporal difference lcarning: The successor representation. Neural Computation, 5(4):613 624. C
de Lazeano, R., Andreas, K., Tai, Lec, R., and Terry, J. (2023). Gymnasium robotics. B.2
Efroni, Y., Dalal, G., Scherrer. B., and Mannor, S. (2018). Beyond the one-step greedy approach in reinforcement learning. In Dy, J. G. and Krause, A., editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1386-1395. PMLR. A, C
Efroni, Y., Ghavamzadeh, M., and Mannor, S. (2020). Online planning with lookahead policies. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems 33. 2.3, 4,5, 5, B.I, C
Feinberg, V., Wan, A., Stoica, I., Jordan, M. I,, Gonzalez, J. E., and Levine, S. (2018). Model-hased value estimation for efficient model-free reinforcement learning. CoRR, 0tss/803.00100 C
Feng, Z.. Zhang, B., Bi, J., and Soh, H. (2023). Safety-constrained policy transfer with successor features. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 2219-7225. 5, C
Filos, A., Vértes, E.,. Marinho, Z., Farquhar, G., Borsa, D., Friesen, A., Behbahani, F,, Schaul, T., Barreto, A.. and Osindero, S. (2022). Model-valuu inconsistency as a signal for epistemic uncertainty. Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 6474- 6498. PMLR. 6, C
Fujimoto, S., Meger, D., and Precup, D. (2020), An equivalence between loss functions and non-uniform sampling in experience replay. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F,, and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 14219-14230. Curran Associates, Inc. B.3
Gimelfarb, M., Barreto, A.. Sanner. S., and Lee, C.-G. (2021). Risk-aware transfer in reinforcement learning using successor features. In Proceedings of the 35th Annual Conference on Advances in Neural Information Processing Systems, Online. 5, B.2, B.2,
GX-Chen A., Chelu, V., Richards, A., and Pineau, J. (2022). A generalized bootstrap target for value-learning. efficiently combining value and feature predictions. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, pages 6829-6833 AAAI Press. 5, C
Hafner, D., Lillicrap, T. P., Fischer, I., Villegas, R., Ha, D., Lee, H., and Davidson, J. (2019). Learning latent dynamics for planning from pixels. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2555-2565. PMLR. 1.3.
Hafner, D., Lillicrap, T. P., Norouzi, M., and Ba, J. (2021). Mastering atari with discrete world models. In Proceedings of The 9th International Conference on Learning Reprexentations. OpenReview.net. 1, 2.3
Hansen, N. A., Su, H., and Wang, X. (2022). Temporal difference learning for model predictive control. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3887-8406. PMLR. 2.3, 5.
12

---

Hansen, S., Dabney, W., Barreto, A., Warde-Farley, D., de Wiele, T. V. and Mnih, V. (2020), Fast task inference with variational intrinsic successor features. In Proceedings of the 8th International Conference Learning Representations. 4, C.
Hasselt, H. v., Guez, A., and Silver, D. (2016). Deep reinforcement learning with double q-learning- In Proceedings the Thirtieth AAAI Conference on Artificial Intelligence, AAAI' 16, pages 2094 2100. AAAI Press. B.3
Hessel, M., Modayil, J., van Hasselt, H., Schaul, T., Ostrovski. G. Dabney, W., Horgan, D., Piot, B., Azar, M.. and Silver, D. (2018). Rainbow: Combining improvements in deep reinforcement learning. In Proceedings the Thirty-Second Second AAAI Conference on Artificial Intelligence, AAAI' 18. AAAI Press. C.
Hunt. J., Barreto, A., Lillicrap, T.. and Heess, N. (2019). Composing entropic policies using divergence correction. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 2911-2920. PMLR.
5, C.
Janner, M., J., Zhang. M., and Levine, S. (2019). When to trust your model: Model-based policy optimization. In Wallach, H., Larochelle, H.. Beygelzimer, A., Alché-Buc, Buc, F., Fox, E., Garnett, R., editors, Advances in Neural Information Processing Systems (NIPS) 32, pages 12519-12530. Curran Associates, Inc. 2.3, 4, 5, B.3, C.
Kim, J., Park, S., and Kim, (2022). Constrained GPI for zero-shot transfer reinforcement learning. Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems 35. 1, C,
Kingma, D. P. and Ba, (2015). Adam: A method for stochastic optimization. In Bengio, Y. and LcCun, Y., editors, Proceeding of the 3rd International Conference on Learning Representations (ICLR), San Diego, CA. B.3
Lehnert, L. and Littman, M. L.. (2020). Successor features combine elements of model-free and model-based reinforeement learning. Journal of Machine Learning Research, (1(19))1-53, 5, C
Machado, M. C., Barreto, A., and Precup. D. (2023). Temporal ahstraction in reinforcement learning with the
successor representation. Journal of Machine Learning Research (JML.R), 24(80):1-69. C.
Miller, K. J. and Venditto, S. J. C. (2021). Multi-step planning in the brain. Current Opinion in Behavioral Sciences, 38:29-39 39. 5, C
Momennejad, I., Russek, E., Cheong, J. H., Botvinick, M., Daw, N., and Gershman, S. (2017). The successor representation in human reinforcement learning. Nature Human Behaviour, 1:680-699 692. C
Nemecek, M. and Parr, R. (2021). Policy caches with successor features. Proceedings of the 38th International Conference on Machine Learning. 5, B.2, C
Pan, Y., Yao, H., Farahmand, A.. and White, M. (2019). Hill climbing on value estimates for search-control in dyna. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3209-3215, Macao, China. ojcai.org. 2.3
Plappert, M., Andrychowicz. M., Ray, A., McGrew, B., Baker, B.,, Powell, G., Schneider, J., Tobin, J., Chociej, M.. Welinder, P., Kumar, V., and Zaremba, W. (2018), Multi-goal reinforcement learning: Challenging robotics environments and request for research. CoRR, thh//1802.099 4, B.2
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. 2.1, 3, A
Russek, E. M., Momennejad, I., Botvinick, M. M., Gershman, S. J., and Daw. N. D. (2017). Predictive representations can link badel- reinforcement leamiing model-free mechanisms, PLOS Computational Biology, 13(9):1-35.
Schaul, T.. Quan, J., Antonoglou, I., and Silver, D. (2016). Prioritized experience replay. In Proceedings of the 33rd International Conference on Learning Representations, Puerto Rico. B.3
Sikehi, H.. Zhou, W., and Held, D. (2022). Learning off policy with online planning. In Faust, A., Hsu, D., and Neumann, G., editors, Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pages 1622-1633. PMLR. 5, C
Silver. D., Schrittweserr, J.. Simonyan, K., Antonoglou, 1., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M.. Bolton, A., Chen, Y. Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D. (2017). Mastering the game of go without human knowledge. Nature, 550(7676)354 359, 4, B.1
13

---

Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. The MIT Press, second edition. 2.1
Tesauro, G. and Galperin, G. R. (1996). On-line policy improvement using monte-carlo search. In Mozer, M.. Jordan, M. L, and Petsche T., editors, Advances in Neural Information Processing Systems pages 1068-1074 MIT Press. 4, B.1
Thakoor, S., Rowland, M., Borsa, D., Dabney, W. Munos, R., and Barreto, A. (2022). Generalised policy improvement with geometrie policy composition. In Chaudhuri, K., Jegelka, S., Song, L., szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 21272 21272-21307. PMLR. 1, C.C
Todorov, E.,. Erez. T., and Tassa, Y. (2012). Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, Vilamoura, Portugal. B.2
Tomov, M., Schulz, E., and Gershman, S. (2021). Multi task reinforcement leamiing in humans. Nature Human Behaviour, pages 1-10. 5, C
Touati, A. and Ollivier, Y. (2021). Learning one representation to optimize all rewards. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 13 23. Curran Associates, Inc. 5, C
van Hasselt, H.. Doron, Y., Strub, F., Hessel, M., Sonnerat, N., and Modayil, J. (2018). Deep reinforcement learning and the deadly triad. In Deep Reinforcement Learning Workshop, NeurlPS, 5, C
Van Seijen, H. and Sutton, R. S. (2013). Efficient planning in MDPs by small backups. In Proceedings of the 30th International Conference International Conference Machine Learning, ICML' 13, pages 111-361- 111-369. JML..org. 2.3
Wan, Y., Kalihii-uaa A., Rajendran, J., Momennejad, I., Chandar, S., and Van Seijen, H. H. (2022). Towards evaluating adaptivity of model- reinforcement learning methods. In Chaudhuri, K., Jegelka, S., Song. L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22536-22561. PMLR. 2.3
Wu, P., Escontrela, A., Hafner, D., Abbeel, P., and Goldberg, K. (2022). Daydreamer: World models for physical robot leamning In Liu, K., Kulic, D., and Ichnowski, J., editors, Proceedings of The 6th Conference Robot Learning, volume 205 of Proceedings Machine Learning Research, pages 2226-2240. PMLR.
Wurman, P. R., Barrett, S., Kawamoto, K., MacGlashan, J., Subramanian, K., Walsh, T. J., Capobianco, R., Devlic, A., Eckert, F., Fuchs, F., Gilpin, I.,, Khandelwal, P., Kompella, V., Lin, H., MacAlpine, P., Oller, D., Seno, T.. Sherstan, C., Thomure. M. D.. Aghabozorgi. H., Barrett, L.. Douglas, R.. Whitehead, D., Dürr, P., Stone, P., Spranger, M., and Kitano, H. (2022). Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 602(7896):223-228.
Yao, H., Bhatnagar, S., Diao, D., Sutton, R. S., and Szepesvári, C. (2009). Multi-step dyna planning for policy evaluation and control. In Bengio. Y., Schuurmans, D.., Lafferty. J., Williams, C., and Culotta, A., editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates. Inc. 5, C
Yu, T., Kumar, A., Rafailov, R., Rajeswaran, A., Levine, S., and Finn, C. (2021). Combo:
Conservative oflline model- based policy optimization. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, W., editors, Advances in Neural Information Processing Systems, volume 34, pages 28954 28967. Curran Associates, Inc. 4
Zahavy, T.. Barreto, A.. Mankowitz, J., Hou, S., O'Donoghue, B., Kemaev, I., and Singh, S. (2021). Discovering a set of policies for the worst case reward. In Proceedings of the 9th International Conference on Learning Representations. 5, C
14

---

Appendix
A Proofs of theoretical results
We start by defining the Bellman optimality operator, T", and its multi-step variant, when applied to action-value functions q E 2, where 2 is the space of action-value functions. To simplify notation, given the (true) model, m - (p,r), of the underlying MDP, we denote Em[] as the expectation operator with respect S411 p(-|S A1) and R2 r(S,, S441). Similarly, write r(s, a) & (s)))) a, S1+1)] for brevity.
Definition (2), (Single- and multi-step Bellman optimality operators). Given an MDP's model m = (p,r). r), the single-step Bellman optimality operator, T : + Q is defined as:
[')(s,0) & Em(r(s,a) + (Sxx s, a).
(18)
T The repeated application T for steps gives rise to the h-step Bellman operator, denoted as (T*)"q(s,)) a) & T'... g(s,a) a). Efroni et al. (2018) showed that (T*)² can be written as follows:
((s)) a) Bm a(s,a) + max((")) h-1 "(Se+1, = A, =
(19)
d'EA
max
Em
r( (4((++4sHH((444)))) (S(+x))) 7" max g mo(s)
P1...Rt-11
a'EA
0==
(20)
where μ4 is any policy (in an arbitrary policy space) the agent could choose to deploy at time i. Definition 4. (Bellman evaluation operator). Given an MDP's model m = (p, r) and a policy n, the single-step Bellman evaluation operator, T Q Q, is defined as:
T Ts(s, a) A Em [r(s, a) + (9(S ((411)))) =, A a].
(21)
It is well known that T and T are contraction mappings and their fixed- (for any initial q E Q) are lima- ( a) q² (s,a) a) and lim; ((s, a) = q" (s, respectively (Puterman, 2014).
Notice that the definitions above, since m the (true) model of given MDP, we chose to omit m when writing the corresponding Bellman operators to make the notation more succinct. Formally, though, one could alternatively denote these operators as T and T respectively. In what follows, we always omit m whenever the corresponding operators are defined with respect to the true model of an MDP.
The Bellman optimality operator induced by an approximate model, m = (ø, F), of the true underlying transition and reward functions, p and r, of given MDP, is defined as:
Thg a) & EAa [fs a) + + maa (1)+ s. A₁ = a) a'EA
(22)
= a() + Σ p(s'ls, a) max g(s,,a))
(23)
a'EA
15

---

Now, recall our definition of h-step generalized policy improvement, or h-GPI:
Definition (3), Let IT {m:)== be a set of policies and m = (p, r) be a model. Then, given a horizon h 2 0, the h-GPI policy on state s is defined as
()) E arg max
(s)
max q" (8,a) a) sell
(24)
aEA
arg max aEAA
max P1
Em
Ar Ma (S++a)) +7"h
max max q" (St-h, a') Imo(St) =
a'EA nell
A=
online planning
GPI
(25)
where is any policy (in an arbitrary policy space) the agent could choose to deploy at time i.
Intuitively, an h-GPI policy identifies the best possible action, A., when in state St, by first planning with model m for h steps and then using GPI to estimate the future returns achievable from all states reachable in steps. This is in contrast with standard GPI policies, which can only reason about the future returns achievable from the current state, S,, if following given policy in II. h-GPI, by contrast, uses a model to reason over the decisions made at states within steps from S,, as well states Si+h reachable after h steps. This makes it possible for h-GPI to produce policies that exploit the model-free, zero-shot return estimates produced by GPI when evaluating states beyond given horizon h; in particular, states that would otherwise not be considered by the standard GPI procedure when determining maximmzixii actions. Notice, furthermore, that h- construction-iinerpollaee between model-free GPI and fully model-based planning:
h-GPI induces policies that interpolate between (i) standard model-free GPI (when h 0) and (ii) fully model-based planning (when h + oo).
Next, we introduce a few lemmas that will subsequently allow us to (i) precisely characterize the performance lower bound of an h-GPI policy; (ii) show that it is strictly better than GPI's performance lower bound; (iii) prove that as h increases, h-GPI's performance becomes arbitrarily less susceptible to sub-optimality in the agent's 'ss policy library.
The following lemma characterizes the loss introduced by applying the multi-step Bellman optimality operator, (T*)², // to an approximate action-valus function, q" (8,a).
Lemma 1. Let = { be a set of policies, and ( } be approximations to their respective action-value functions such that, for all n. E II and all (s,a) S x A.
l a) (s) S.
(26)
Then,
(T*h max o (8, a) 2 (T*)* max q" (8, a) - M/e.. nell
(27)
nell
Proof.
(T*)* max qº (s,a)=
max E
(4 + +2"h max max o (Stth, (00th,a))5 a')[St= =8,14(5))
nell
d'EA nell
(28)
max
E
(r(S + + max max (SthiStt,, a')aaaa))))33 -c]Ss = s, s.Ho(()
M Ah-1
a'EA sell
(29)
max E
Σ y M (a(ekk)) + +1 max max (Seth, a')SS = s, (o(s) (s) = a - -he
M1 Ah-1
Fell
(30)
-T*)* max a= (s, -
(31)
HEll
Above, (28) and (31) are due to the definition of (T*)^ introduced in Equation (20).
16

---

The next lemma characterizes the loss incurred by applying the Bellman optimality operator induced by an approximate model m, (Th),, to an action-value function, q". of policy x.
Lemma 2. Let m (p. be approximate model such that, for all (s, a) S A.
[lo(d'(s,a) - (()'|s,a) S cp and (r(s,a) - f(s, a)l S cr.
(32)
Let mmax A maxx, a (= ()) Then, for any policy πT and h 2 0.
(TT (Tm))* q" (s,a)l Epr
(33)
where
1 1-1h h (er + mapd)
Epr 11)
(34)
1
Proof.
- (Ta))))
r(s,a) +7 Σ p() max () 1 a(s,a)- - E p(s (s,a max (ax((T))=11 ('s('aa')
(35)
Σ p( [p( 56
max (ax Σ ((l'lss,a) (ax))sa))axx(Tne (aa)(TT)) (s
(36)
a'EA
Ep(sl|s, () max T ( 1" (s', + (( (aaaa)max(T)) 9" (s',a') a'EA
er 7
a'EA Σ 0(8' ()) maam))aa(())))
9- as', ) (5'
max
(37)
a'EA
a'EA
E, + Σ p(s' a)
(T) 9" (s',''
max -ax
d'EA
d'EA
- ((s'|s,
mT (
(38)
a'EA
< E, + max
(T h- 1 ("(,'' (Th) 9 (s'
+ ? Σ p(s' (. a) - p(s')s s,a) a)
((
max (s',aa²)
(39)
a'EA
S + max max s'
9" (s',a) a) (T (5' a')l + T
(40)
In the proof above, all terms shown in blue refer to approximate quantities-succ proximate model of the environment or an approximate transition function. In the proof above, (35) follows from the recursive definition of (T*)h showed in Equation (19). In (37), we add and subtract E. ((s"((s. (T))) "s' a'). (39) is obtained due to the property that E. Ess(s' (() as') I max,' f(s'). for any function f. Finally, (40) is due to (T+)h-1 1='("""'" (s', a') z max-
ap-
We now show how to rewrite the inequality (40) recursively. Let (n 2 I(T')) (Ta)"a (s. a)), for all (s,a) E S A. Then, by replacing the definition of A (40), we obtain: An(s, a) S e, + max A.-10_15555 (s', a') + "mp
(41)
Because inequality (41) holds for any (s, a). it also holds for the maximizer. Thus, we can omit (s, a). and define A. e maxx, (8, a). The inequality (41) then becomes:
A s + -
YC, y mmax.
(42)
17

---

Now we use the fact that, by definition, Au(s, = (s. as) = 0. to recursively expand inequality (42):
Ah
((r + maxx)
(43)
k=0
1 7h
1 (cr (mxx)mx)
(44)
Finally, by using (44) and recalling the definition of An (i.e., An maxx,a a)), we can directly prove that
- (c + mop))ar)
max (s, & max (T*) q 8,8
- 1-7
(45)
8,0
The result above bounds the difference between the action-value functions resulting from applying the Bellman optimality operator (defined with respect to the true model of the MDP) h times, and the action-value function resulting from applying the Bellman optimality operator (defined with respect an approximate model, ri)) h times. This allows us to precisely characterize- when repeatedly using the Bellman optimality operator over an initial action-value function-the maximum error incurred by using an approximate model of the environment.
The next two lemmas provide intermediate results that will be used in the proofs of Theorem I and Theorem 2.
Lemma 3. LT { be a set of policies, Hi be approximations to their respective action-value functions, and in f) be an approximate model such that, for all n; E II and for all (8,a) EES x A, the following holds:
11"h (8. (s, Se, Elo(6'00 0(8'1s,a) Sep, and (r(8,a) f(8,a)) s (46)
Recall the definition of h-GPI (Definition 3):
h GPI (8) arg (Tax((T)) max (s. acA
(47)
sell
Then, it follows that:
T (Ta) max q" (8, 2 (T* ( 708// + c((r::p:l)) h)).
(48)
well
well
Proof.
T M-R
(T max q" (s,a) = E r(s,a) + > max q" (S x h-GPl (Sc+1)][{:= =
#ell
nell
(49)
max g (St+1, = 8, A₁ = a (50)
E
r(s, + max
d'EA
fell
2 E
r(s, a) + max d'Ed
(T%)*
max o (S - -xxe) (/}1ss, 1s: = 8, At = a
sell
(51)
2 E r(s, a) + max
(T*)*
h max qd (S141, -'(ern,, - /h Sy s, A,A,=d =
REd
well
(52)
E
r(s a) + max max maxq (Sx, = A.
1(7 c + c(cr:cp.
d'EA
#ell
(53)
= (T+
max q- (s, a) - 700" cler
(54)
#ell
18

---

Above, (49) is due to the definition of the Bellman evaluation operator (21). and (50) is due to the definition of the h-GPI policy (47). Finally, (51) is due Lemma and (52) follows from the use of Lemma 2.
I
Lemma 4. Let 11 { be set of policies, { be approximations to their respective action-value functiios, and m (p. f) be an approximate model such that, for all n; E 11, and all (8,a) E x A:
(() Se, Elo(o'ss,) - ((8'1s,))) S Eps and (r(s,a) f(8,a)) er. (55)
Recall the definition of h-GPI (Definition 3):
Th A. (s) arg max (Tx)(Tm)) h max (s,
(56)
aeA
well
Then,
T N.
(Th)) max (0, (s,a) 2 (Tr)** max (" - - +n) c(er, (o(p))(110
(57)
sell
well
Proof.
T A.
(Tm)
max (s, #Ell
2 (T M+1 max pax (s, - +
(58)
well
M max 8 (s, a) c(tn)
(59)
TEll
M max q" (s, a) - c(e hi - cper::pp
(60)
Hell
max n" (5,a) a) ~/- - - Ep. h) 7 Ep. h))
#ell
(61)
(Ta)) max q (s,a) - >-c(1 + 7) c(er: Ep, + h))
(62)
Above, (58) is by Lemma 3, (59) is due to the monotonicity of T (i.e. T (s, 2 9" (s, a)), and (60) by Lemma 2.
We now use Lemmas 1, 2, and 4 to introduce Theorem 1, which extends the original GPI theo- rem (Barreto et al., 2017) and allows us to characterize the gains achievable by l--PI as a function of approximation errors in both the agent's 's policy library, II, and its (possibly learned) model, m. Notice that Theorem generalizes the original GPI theorem, which is recovered when h 0.
Theorem (1), Let Il = { } be a set of policies, ( be appreximations of their respective action-value functions, and m (f, be an approximate model such that (as previously-assumen in Lemmas and 3), for all n. E 11 and all (s,a) ESX A.
(s, e, Ele(s'ls
p(s')s, a)l S Eps and |r(s, a) f(s, c (63)
Recall once again the definition of h-GPI (Definition 3):
G.P (8)
arg max
" max q (s, well
(64)
aeA
Then,
GPP (s. 2 (T')² max (s,a) xell
2
(n c(cr. h))
(65)
1 1-9
2
(
( cler, h)),
(66)
#ell
1
where c(Er, Ep. hi)
1- I-7 (er + 7)
19

---

Proof.
gioGPl(s,)) lim
(T
(Tm
(max
g" (s)
(67)
k00
sell
(Th)
(max q" (s, a))
lim
+cG + +7))
(68)
nell
i=0
rde(1 +7)
Ep,
(T (max q" (8, a))
(69)
HEll
1-7
1-7
(max q (s, a)) - -/' (d(1+
Epr, h) (c)rep.h)((++))
(Tr)
(70)
HEll
1-7
1-7
7ne(1
cle,, Ep: hp
(max q" (s, a)) c(er, Eps h)) - -7" sell
1-7
1-7
(71)
= (T)) (max qa (s, (max
(T + clers (p:
(72)
Tell
Above, (67) is due to the fixed-point of limg- (T q" a) being G a) for any q. (68)
due to the repeated application of Lemma 4. Finally, (70) due Lemma and (71) is due to Lemma 2.
Theorem I characterizes the performance lower bound of h-GPI as a function of the number of planning steps, h, and the approximation errors in the agent's 's model and action-value functions (i.e., errors e, Ep, and c,).
Note that since (T*)* max+en ( (s. 2 max 9d (s, a), h-GPI's performance lower bound strictly better than GPI's (h = 0) assuming no model approximation errors (c,- = Cp O). Furthermore, notice that as + co, (T*)* max,en q" (s, a) converges to q" and the approximation error term (7 in Equation (13) disappears. In other words, as h increases. h-GPI's performance becomes arbitrarily less susceptible to sub-optimality in the agent's policy library. This implies that the planning horizon h trades off between two conflicting objectives. On the one hand, increasing the planning horizon h improves the performance of the h-GPI policy because the error term (c) associated with value function approximations errors becomes irrelevant. On the other hand, longer horizons worsen h-GPI's performance lower bound since they increase its dependency on errors arising from approximate models. Intuitively, for small values of h. the agent relies more heavily on the assumption that its estimates { ) are correct, given that these estimates are discounted by yh. For large values of h, by contrast, the approximate model error term, c(Er, Ep, h), increases, and the agent relies more heavily on the assumption that its (learned) model approximately correct.
Theorem (2). Let l1 = {mī be set of optimal policies with respect to reward weights {w, )
and w be arbitrary reward weights. Let ii = (f, fw) be an approximate model and (áw Yizı be approximations to the action-value functions of policies in II, under the reward function Two such that for all n, E II and all (8, a) E x A.
Σ Elp(s'ss,a) -(('(s,,)) Epp and (rw(s: a) pw (s, S er- lowi (s, a) qwi (s,a)) S,
mh
(73)
We now extend the definition of h--PI (Definition 3) to the case where this policy is defined under the assumption of an MPD with reward function Tw:
G. (s; w) E arg wammmaxTT.t. max T (s. a).
(74)
aEA
well
Let &max= maxx, (l) Then, it follows that
2
(8, - Aw G-GPI (s. 1- (mmax min ||w
will + nhe cpe
(75)
I-gA where c(Er, Ep. fi) I- (Er Vmpu)aa)
20

---

Proof. The proof is an extension of Theorem 2 of Barreto et al. (2017) to the case where we use our Theorem 1 (i.e., we apply the bound introduced earlier characterize the relation between the performance of h-GPI and the model and action-value function approximation errors), rather than using the GPI theorem, as defined by Barreto al. (2017):
2 (7 1- - + cper;)p:li))
Iw (8, a)
Iw
N.GPI (8, S Iw (8, a) - (T*)a max Iw (8, a) + Tell
(76)
S Aw (s, a) - max Iy (s, a) +
1 1-9 c + cp.
(77)
S 2
2
min max |T (8, rw. Tw: (8, + 1 3,
(7 + c(err hi)
y
(78)
2
2
min max (0(8,)) ((5 a) wil + 8,
1- ( cpcr. h1)
1
1-7
(79)
2
min max (0(s, (w - (w)) +
(7 Cp: hi) (80)
=
y-y
8,0
1 1
2
2
5
min max [|0(s, a)ll | will
(7 + (81)
7
1
2
2
Φ max min | -wll will+
1- (3 (p. hi)
(82)
2
(Ø max min |w - will + + + cler, Epp hi))
(83)
Above, (76) is due to Theorem 1 and (77) is due to the monotonicity of T Finally, (78) is due to the application of Lemma 1 of Barreto al. (2017), and (81) due the Cauchy-Schware inequality.
Theorem 2, above, allows to characterize h- L-GPI's performance (under approximation errors) with respect to the optimum action-value function, given an arbitrary reward function, rw:
Theorem 2 precisely characterizes the optimality gap (i.e., the maximum difference) between the action-value function induced by h-GPI (g (0 (s, a)) and the optimal action-value function (4t (s, a)), as function of (i) the reward weights {wi]== for which the policies in the agent's 's library, II, are optimal; (ii) approximation errors in action-value functions {Φw }a Ve=i and (iii) approximation errors in the model m fw).
B Experimental details
In this section. we provide detailed description of the practical implementation of h-GPI, as well as details of the domains used in our experiments. The code necessary reproduce our results is available in the Supplemental Material.
B.1 Computing h-GPI policies with SFs and Farward- Dynamic Programming
In this section, we show how extend the Forward-Backward Dynamic Programming (FB-DP) algorithm (Efroni et al., 2020) to the discounted-So setting, in order to compute h-GPI policies efficiently. The algorithm is described in Algorithm 3.
The algorithm works by first computing the sets of states achievable from the current state, s, after t t= O...., h time steps (line 1 of Algorithm 3). The complete procedure is described in the Forward- Pass algorithm (Algorithm 2). Next, the algorithm for computing 4-GPI policies (Algorithm 3) assigns the value of states reachable in h steps using GPI bootstrapping with the SFs estimates (line time steps are then computed via dynamic
3). The values of states reachable in = I.., programming (lines 4-5). Finally, the h-GPI action is identified in lines 6-8.
21

---

Regarding Algorithm 3, we first note that, given state s, the algorithm's 's time complexity is [( where N is the maximal number of accessible states in one step (i.e., maximal "nearest neighbors" from any state), and [Sh is the total number of reachable states in h time steps from state
Note that while we chose to extend the original FB-DP algorithm to design practical procedure for computing h-GPI policies, due its efficiency and closed-form formulation, other planning techniques could have been used (e.g., Monte Carlo Tree Search (Tesauro and Galperin, 1996; Silver al., 2017)).
Algorithm 3: /-GPI with SFs and FB-DP
Input: Model m (ý) Φ). SFs { RE= planning horizon 0, state 8, reward vector w.
Algorithm 2: Forward Pass
Input: Model m (Ø, Φ), planning
{S J + ForwardPPass(f.. h)
2 for s S₁. do
horizon 2 0, state 8.
So {s}, S, f 0 Vt E {I,...,hh)
3 (s) t E max &b (s.
for f = I,..., h do
for 1-1,.... do
for 8:-1 E S do
5
for 8 E St do
S t S
vt(s) + max ( a w
| s.t. p(s ((=,))) 0}
E a(
Return: Lh
for A do
(Tm) max 1w (8, (8,00 a)
(Ø(s,a) w + EE p(s as)
Return: arg max, (Tr: ( )a max L (s,
B.2
Environments
Below, we describe the three domains used in our experiments all of which are depicted in Figure 6.
Figure 6: The FourRoom, Reacher, and FetchPush domains.
The Four Room domain (Barreto al., 2017: Gimelfarb al., 2021) is a gridworld with dimensions of 13 x 13, consisting of four rooms separated by walls. At each time step the agent occupies cell and can move in of four directions, denoted by the action set A = {up, down, left, right). Differently from related works, we introduced a 10% chance of the agent moving to random direction, rather than the direction given by the selected action. This makes the state transition function, p. stochastic. If the destination cell happens to be a wall, the agent remains in its current cell. The grid contains three different types of objects, as illustrated in the lefumost figure in Figure 6. There are four instances of each object type distributed throughout the grid. The state space is defined as the concatenation of the agent's current x-y coordinates and set of binary variables indicating whether each object has been picked up or not: S = {0. 1, 12}² x {0, 1) 12 The features (,,, a, 8') E {0, 1 are one-hot encoded vectors that indicate the type of object present in the current cell. If there are objects in the current cell, the corresponding features are set to zero. The goal cell which the agent has to reach located at the upper-right of the map. It contains one instance of each object, and entering this cell results in the termination of the episode. In this domain,
FourRoom.
22

---

a discount factor o = 0.95 was used. In our experiments, we used the implementation available on D0-Gyymaaiimm (Alegre et al., 2022b).
Reacher. The Reacher domain is a classic domain in the SFs literature (Barreto et al., 2017; Gimelfarb et al., 2021; Nemecek and Parr, 2021; Alegre et al., 2022a). It consists of a two-joint robot arm that must reach different target locations with the tip of its arm (see the middle figure in Figure 6). The agent's 's state space S IR consists of the sine and cosine of the angles of the central and elbow joints, as well as their angular velocities. The agent's 's initial state is the one shown angionn
in the middle figure in Figure 6. The action space, originally continuous, is discretized using bins per dimension corresponding to maximum positive torque (+1), negative torque (-1), and zero torque for each actuator. This results
total of 9 possible actions: A (-1,0, +1)2. Each feature (1s, 0, s') E TR' is defined as (s, 8') = 44 (target,), = 1...4, where A (target,, is the Euclidean distance between the tip of the robot's arm and the i-th target's ' location. We used a discount factor of y 0.9 in this domain. We used the implementation of this domain available on MO-Gymnasium (Alegre et al., 2022b), which is based on the MuJoco robotics simulator (Todorov et al., 2012).
FetchPush. Finally, we extended the FetchPush domain (Plappert et al., 2018), which consists of a Fetch robotic arm that must move block to given target position on top of a table by pushing the block with its gripper (see the rightmost figure in Figure 6). Importantly, the state space of this domain, S C "R is high-dimensional, and its dynamics are significantly more complex than that of Reacher's. s. In our experiments, we removed from the states all information related to the position of targets, as these are irrelevant since targets have fixed locations. We discretized the action space similarly to how this was done when defining the Reacher domain. The reward features Φ(s.a, a, s') F correspond to the negative distances between the block and each of the four target locations on the table. Our implementation of this domain is an adaptation of the one available in Syymnasium-Roootie (de Lazcano al., 2023).
B.3 Parameters
In the FourRoom experiments, the SFs of each policy were learned similarly as in Alegre et al. (2022a), using Q-learning and 5 Dyna updates per time step. Each policy was trained for 10 time steps using a learning rate of 0.1 and epsilon-greedy exploration with a probability of selecting a random action linearly decayed from to 0.05 during half of the training period.
In the Reacher and FetchPush domains, we used multi-layer perception (MLP) neural networks to learn universal successor feature approximators (USFAs) (Borsa et al., 2019). The USFAs, db(s, a, w). were modeled using MLPs with 4 layers of 256 neurons and ReLU nin-linear activations. We used the Adam optimizer (Kingma and Ba, 2015) with a learning rate of 10 and mini-batches of size 256. Recall that (as discussed in the main paper), we used vectors that form the standard basis of Rdd as training reward weights, M, where is the dimension of the reward features vector Φ. In our implementation, we also adopted popular DQN extensions to speed up and stabilize learning, such as prioritized experience replay (Schaul et al., 2016; Fujimoto et al., 2020) and Double Qllearning (Hasselt al., 2016) with target neural network updated after every 200 time steps. In both domains (Reacher and FetchPush), we trained the USFAS for a total 2 100 time steps. In Reacher, the epsilon-gu -reeddyyggyyyygeeeee exploration rate was kept fixed at 0.05, while in FetchPush, it was linearly decayed from 1 to 0.05.
We used an ensemble of n=7 probabilistic neural networks in both the Reacher and FetchPush environments to learn the model (S++1 & IS,, A.). In the Reacher domain, each network was an MIP with 3 layers with 200 neurons each. In the FetchPush domain, we used an MLP with 4 layers with 400 neurons each. The probabilistic neural networks used to approximate the model were trained with early stopping based on holdout validation subset with instances drawn from the experience buffer B-as as commonly done when training such networks (Chua et al., 2018; Janner et al., 2019), In Figure 7, we depict the mean validation loss of the learned models both in the Reacher and FetchPush domains. As can be seen, the learned model rapidly becomes fairly accurate.
Compute. For the tabular experiments, we used an Intel 17-8700 CPU @ 3.20GHz computer with 32GB of RAM. For the experiments involving the function approximation setting, we used computers with NVIDIA A100-PCIE-40GB GPUs. For each random seed, the training period used for training
23

---

(10.0)
11.0
2.1773
E.030
2.110
Meon Model Valigiion
Meon Model Validatinn
E20220
2.200
2000
1086
1940
13401 Traning Time Step
11000
30000 (1000) 2004
2500
1000
70630
19400
20000
(00M0) 119R0
29003
Traning Time Step
Figure 7: Mean validation loss of the learned environment model, m dls, a), throughout the training phase during which II is constructed (Left: Reacher domain; Right: FetchPush domain).
USFAs was of approximately 6.5 hours. We used the JAX library (Bradbury et al., 2018) for the implementation of neural networks.
C
Related work
In this section, we discuss in more detail works that are related to /t-GP.
GPI and SFs. Previous works have extended GPI to safe RL (Gimelfarb et al., 2021; Feng et. 2023), maximum-entrop RL (Hunt et al., 2019), unsupervised RL (Hansen et al., 2020). and hierarchical RL (e.g., via the options framework) (Barreto et al., 2019; Machado et al., 2023). Recently, Thakoor et al. (2022) introduced Geometric GPI (GGPI). GGPI uses geometric horizon models (GHMs) to learn the discounted future state-visitation distribution induced by particular policies to rapidly evaluate policies under given, known reward function. The authors show that performing GPI over a particular type of non-stationary policy produces behaviors that outperform those in the agent's s library policy. h-GPI, by contrast, learns different type of model: environment model, which is used to perform planning- i..., action selection-ratiee than policy evaluation. Additionally, GGPI requires learning separate GHMs for each policy in the library, whereas h-GPI operate with a single model that predicts the next reward features, alongside a single USFA. Secondly, GGPI assumes that the reward function is known priori, while we exploit SFs generalize over all linear rewards given reward features. Bagot et al. (2023) introduced GPI-Tree Search (GPI-TS), which closely related to h-GPI. GPI-TS uses GPI bootstrapping the leaf nodes of a Monte Carlo tree search. However, GPI-TS does not employ SFs and was only employed single-task settings. Moreover, assumes an oracle model of the environment. We. by contrast, employ learned models to perform zero-shot transfer over multiple tasks, and we show how approximation errors in the model affect the performance of the h-GPI policy (see Theorems I and 2). Kim et al. (2022) introduced Constrained GPI (CGPI), which uses lower and upper bounds of the expected return of the optimal policy for new task to constrain the action-vas -valuss used when selecting the GPI policy's 's actions. Although CGPI is robust with respect to generalization errors in the values predicted by USFAs for new target tasks, sensitive to approximation errors in the values of the training tasks. h-GPI, by contrast, can inherently deal with approximation errors in the values of source/base policies. Other works have studied methods for constructing policy library for use with GPI (Zahavy et al., 2021; Nemecek and Parr, 2021; Alver and Precup, 2022; Alegre et al., 2022a). These methods solve important orthogonal problems, and could potentially be combined with h-GPI.
backup value estimates at
Madel-based RL and SFs. Russek al. (2017) proposed a Dyna-style algorithm that performs background planning to update tabular successor representations (SRs) (Dayan, 1993). Momennejad al. (2017) argued that this algorithm could better model human behavior on tasks with changing rewards when compared to pure model-free or model-based approaches. In this paper, by contrast, we employed online planning and leveraged GPI and SFs-botth of which generalize SRs to continuous- state problems. Other works have studied methods for learning SF-based representations (I (Lehnert and Littman, 2020; Touati and Ollivier, 2021). Studying the behavior of k-GPI under different types of reward feature representations is interesting dircction for future research. We believe that our work
24

---

also shares similarities with the investigation performed by Tomov et al. (2021) on how model-free and model-based mechanisms are combined in human behavior.
Multi-step RL algorithms. Multi-step RI. methods were extensively studied in the context of policy evaluation, both in the model-free (Hessel et al., 2018; van Hasselt et al., 2018) and the model-basee settings (Yao et al., 2009; Janner et al., 2019). Model value expansion algorithms (Feinberg et al., 2018; Buckman al., 2018; Abbas et al., 2020) are representative example of the latter type of approach. In this paper, by contrast, we introduced a multi-step method for policy improvement, designed specifically
tackle transfer-learning settings. GX-Chen et (2022) introduced the 7-return mixture, new backup target for better credit assignment, which combines bootstrapping with standard value estimates and SFs, as a function of a parameter 77. Efroni al. (2018) studied multi-step greedy versions of the classic policy iteration and value iteration (Bertsekas and Tsitsiklis, 1996) dynamic programming (DP) algorithms. Efroni et (2020) proposed multi-step greedy real-time DP algorithm that replaces 1 -step greedy policies (used in policy improvement) with an h-step lookahead policy. The technique introduced in our paper is also related the works of Sikchi al. (2022) and Hansen et al. (2022), which combine planning and bootstrapping with learned value estimate. However, unlike h-GPI, the abovementioned approaches did not address the multi-policy and zero-shot transfer settings. Another interesting use of multi-step prediction models is the work of Filos et al. (2022). In that work, the authors defined measure of epistemic uncertainty based on the disagreement between the values resulting from applying the model-induces induced Bellman evaluation operator for different numbers of steps. Finally, we also emphasize to the interested reader that there exists neuroscientific evidence that multi-step planning occurs in the brains of humans and other animals (Miller and Venditto, 2021).
25


Reviews:
[{"review_id": "cmHJ1GyAo7", "reviewer": "Reviewer_MMCf", "summary": "This paper proposes a new hybrid solution of model-free and fully model-based reinforcement learning solutions for planning. It introduces a multi-step extension of generalized policy improvement by having certain planning steps to approximate model behavior, increasing the efficiency of the model. It is followed by zero-shot policy transfer.", "questions": "1. Why h-GPI should be useful and advancing from earlier model-free/model-based methods and why this is necessary?\n2. From high-level perspective, the proposed method looks like a fine-tuning of an approximators. So do you think this can be applied to \"conventional\" deep model-based planning methods? If so, do you think hGPI can still outperform?\n3. Do you think the method itself will be heavily rely on the generalization power of the universal SF feature approximator, rather than the model itself? It gives me this kind of instinct when reading the experimental sections.", "limitations": "The authors listed some limitations of their methods at the very last section. Potential negative societal impact may not be applicable.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Although the originality of the problem itself is not new, it does address the problem of working efficiency of current methods.\n2. The algorithm itself is very well-written, starting from basics of RL, MDPs and extended to the contribution itself.", "weaknesses": "1. The method itself lacks subjective comparison with other fully model-based or model-free solutions under same learning environment.\n2. Although the method addresses the problem of efficiency, it is not fully motivated and justified (why it should be useful and advancing from earlier model-free/model-based methods and why this is necessary?)\n3. The method is applied to two main setups - statistical one and deep learning based one. However, the setup looks a bit hand-crafted and lacks earlier reference. I do not think they comes from no-where - authors may address earlier works and add some general descriptions of those two settings, before getting into details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our work. Below, we address their remaining questions:\n### On $h$-GPI's underlying motivations and advantages\nThank you for your feedback that further intuitive discussion on the motivation and advantages of $h$-GPI may be provided. The goal of $h$-GPI is to perform zero-shot transfer in RL—in a principled way—by exploiting possibly imperfect models of the environment. $h$-GPI advances upon existing model-free and model-based methods, in the zero-shot transfer setting, in various ways.\n* Existing *model-free* zero-shot transfer methods often rely on techniques rooted in GPI and SFs. These techniques analyze a library of policies—each solving a particular task—and identify which action the agent should take. Although computationally efficient, they cannot exploit models of the environment that the agent may have access to, thus rendering them less sample efficient.\n* Fully *model-based* algorithms can—if given perfect knowledge about the environment—identify optimal policies. However, they are typically computationally intensive, and the assumption that exact models are available is seldom true. In reality, these techniques may fail catastrophically since modeling errors are known to compound with the number of actions taken by the agent.\n* $h$-GPI simultaneously improves upon these extremes. It implements a multi-step extension of GPI that interpolates between these extremes and exploits the best of both worlds. The interpolation is controlled by $h$, which regulates the amount of time the agent has to reason.\n* As $h$ increases, $h$-GPI exploits the agent's model and becomes arbitrarily less susceptible to sub-optimality in the agent's prior knowledge for solving previously-experienced tasks—see Theorem 1.\n* Finally, *(i)* $h$-GPI is more computationally efficient than fully model-based approaches, since it does not have to construct complete, possibly long-horizon plans; *(ii)* it is less susceptible to model errors, since it avoids compounding modeling errors by exploiting GPI to directly predict the agent's performance in future states; and *(iii)* it is more efficient than purely model-free methods, since it identifies promising actions by looking ahead into the future.\n\nThe discussion about the points above is currently presented in the Introduction and Section 3. We will follow the reviewer's suggestion and further emphasize these points.\n### Information about domains used in experiments\nWe thank the reviewer for this suggestion. We agree that this change will benefit readers who may be unfamiliar with the field.\n* We will emphasize more strongly that a complete and detailed description of our experimental setup—both for the tabular/statistical case, and for the deep RL case—is already available in Appendix B2.\n* We will update the paper to include further references, as requested by the reviewer, to emphasize that all settings investigated in this paper are consolidated in the literature of SFs\\&GPI. Appendix B2 discusses this and provides a complete and thorough set of references for each experiment. The FourRoom and Reacher domains have been investigated by many other works (Barreto et al. (2017); Gimelfarb et al. (2021); Nemecek and Parr (2021); Alegre et al. (2022)). Both of them are well-known experimental setups used to evaluate GPI-based algorithms both in the tabular setting (discrete state spaces) and in the deep RL setting (continuous states and function approximation with NNs).\n* We will move parts of the description of the domains from Appendix B2 to the main body, for the benefit of readers unfamiliar with particular details.\n* We will clarify that multi-task version of the FetchPush domain was introduced by us to showcase the capabilities of our method in a setting with more complex state dynamics.\n### Combining $h$-GPI with \"conventional\" deep model-based planning algorithms\n* The reviewer is correct that $h$-GPI can be instantiated in settings that combine various types of model-based RL algorithms—including those using deep model-based techniques. In our experiments with the Reacher and FetchPush domains, we do combine planning steps (inherent to the way $h$-GPI works) and deep learning algorithms—necessary as these domains have continuous states.\n* Regarding the possibility of combining $h$-GPI with other deep model-based algorithms, it suffices to compute the first term of Eq. 10 (responsible for the online planning step) using any other techniques of interest.\n* There are many benefits to doing so compared to deploying these methods directly. If the agent only has access to imperfect environment models, $h$-GPI empowers the agent to identify the best possible action by first planning with the approximate model for $h$ steps, and then exploiting the transfer and generalization properties of GPI to *directly* estimate the return from future states. This capability is something that standard deep model-based planning algorithms currently do not possess.\n* We appreciate the reviewer's insight and will update the paper to discuss this promising strategy for extending existing algorithms with $h$-GPI.\n### Does performance rely primarily on the generalization power of USFAs?\n* $h$-GPI's performance does not primarily rely on universal successor feature approximators (USFAs). This observation is supported by our empirical results. In the FourRoom domain, for example, $h$-GPI significantly improves both upon standard GPI and MPC (for numerous values of $h$) *even though USFAs are not used*. In the other domains, we allow *both* $h$-GPI and GPI to use USFAs. In this case, even though all methods can exploit the generalization power of USFAs, $h$-GPI still outperforms them. Therefore, the benefits of $h$-GPI are not primarily due to USFAs; by contrast, they arise from its strong formal guarantees regarding the performances that are achievable when interpolating between GPI and model-based approaches."}, {"review_id": "N5LYnMCcSC", "reviewer": "Reviewer_Y3y3", "summary": "This paper studies the combination of model-based planning/rl and model free generalized policy improvement and proposes h-GPI. The authors provide both theoretical and experimental results to support the method.", "questions": "See the weakness above.", "limitations": "See the weakness above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is clearly written and easy to follow. \n2. The motivation to study the intersection between model-based planning and GPI is also straightforward and clear.\n3. The theoretical results are thorough, and are correct in my perspective.", "weaknesses": "1. For readers who are not familiar with GPI, Definition 1 is a bit confusing. What is $\\pi'$ used for? In equation 5, $\\pi'$ does not appear. Does that mean $\\pi^{GPI}$ satisfies equation 4?\n2. Can the authors explain how the policy set $\\Pi$ is obtained?\n3. Can the results generalize to the algorithm that replaces GPI to standard policy iteration/TD? It seems that h-GPI is a generalization of h-step model value expansion [1]. If so, I am interested in the comparison of h-GPI to MVE in both theory and experiments. Otherwise, the novelty compared to previous model-based value expansion works can be limited.\n4. The current theoretical results only cover the bias of the proposed algorithm, which meets our expectation as model-free and model-based combinations require the trade-off of h. It would be more comprehensive if more analysis on the sample/computational complexity can be added.\n\n[1] Vladimir Feinberg et al. Model-Based Value Estimation for Efficient Model-Free Reinforcement Learning\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging that the paper is clearly written, that the theoretical results are thorough and correct, and that both theoretical and experimental results support the method. Below, we carefully answer all concerns raised in your review:\n\n### On the definition of GPI\nThank you for the feedback on our discussion about GPI. We will include extra discussion on the intuition underlying this definition. This will be done by reminding the reader that GPI is the process by which an agent can combine policies in a given set, $\\Pi$, to obtain a new policy, $\\pi'$, such that its performance is at least as good as the performance of any policy in the original set, $\\Pi$ (lines 116-117). This property is formalized in Eq. 4. One way to identify a policy $\\pi'$ satisfying such property is via the GPI procedure, which computes a policy $\\pi^\\text{GPI}$ according to Eq. 5. This is described in lines 123-124.\n### How can $\\Pi$ be constructed?\nThis is a great question, and one of the open problems in the field. In theory, any arbitrary set of policies, $\\Pi$, may be used when performing GPI. In the Related Work, we discuss four recently-proposed methods introducing different heuristics for constructing $\\Pi$ (lines 342--344). In our experiments, as discussed in lines 299-300, we constructed $\\Pi$ via a commonly-used approach described in Borsa et al. (2019) and Kim et al. (2022). In the FourRoom domain, this approach identifies the base policies in $\\Pi$ by solving tasks whose reward functions are defined by weight vectors $\\mathbf{w} \\in \\\\{ [1,0,0], [0,1,0], [0,0,1] \\\\}$. We will emphasize that $h$-GPI is agnostic to the set $\\Pi$ used.\n\n### Can GPI be replaced with standard TD techniques?\nOur method uses GPI to directly determine the performance of a policy when optimizing a given reward function. Determining the performance of a policy can be done via any standard policy evaluation technique. We use GPI due to its strong generalization and transfer properties, which allow us to *directly* determine a novel policy's performance—unlike TD methods, which demand the agent to interact with the environment and would thus be more sample inefficient.\n### Sample/computational complexity\n* Regarding the computational complexity of $h$-GPI, it primarily depends on the underlying planning technique used. In this paper, e.g., we extended the FB-DP algorithm (Efroni et al., 2020), allowing $h$-lookahead policies to be computed in real-time (see pseudocode in Appendix B.1.). Concretely, given an initial state $s$, the time complexity of this algorithm is $O(N|A||S_{h}^{\\text{tot}}|)$, where $N$ is the maximal number of accessible states in one step, and $S_{h}^{\\text{tot}}$ is the number of reachable states in $h$ time steps from state $s$. It is worth noting that the complexity of performing the other significant step of $h$-GPI—GPI bootstrapping—is negligible compared to planning, as it only requires querying the learned $q$-value policies in the library $\\Pi$.\n* Regarding the sample complexity of *deploying* $h$-GPI, we recall that our paper addresses a zero-shot transfer setting. In this context, agents *cannot* collect any further samples from the environment when tackling a new task. Instead, they must rely solely on previously-acquired information—regardless of how it was obtained—to identify potential solutions. Since no samples can be collected at deployment time, defining or quantifying sample complexity becomes non-trivial. A more meaningful way to characterize how the method scales might be to analyze how quickly it reduces errors in its solutions as a function of the properties of the knowledge available to the agent (e.g., value function approx. errors). This is explored in Section 3. We appreciate you bringing up this point, and we believe that adding a corresponding discussion will enhance the clarity of the paper.\n\n### Can $h$-GPI be compared with MVE?\nThis is a good question. Although $h$-GPI and MVE are, on a high level, based on a similar motivation (i.e., exploiting possibly imperfect models of the environment), they solve qualitatively different problems.\n- As discussed in the Related Work, MVE algorithms (Feinberg et al., 2018) are model-based algorithms for *policy evaluation* in the single-task setting. We, by contrast, introduce a model-based algorithm for *policy improvement* in the multi-task setting. Since they are solving qualitatively different problems, and under different assumptions, a comparison is not possible.\n- We will, in our Future Work section, discuss potential ways in which $h$-GPI may be used to extend MVE's capabilities. In particular, it may be used to extend MVE so that MVE becomes applicable not only in single-task settings, but also in multi-task problems. \nFurthermore, $h$-GPI might potentially be employed to incorporate a novel policy improvement procedure to MVE so it can learn (rather than merely evaluate) effective policies.\n\n### Final comments\nWe sincerely thank the reviewer for their constructive insights! In your review:\n* You asked for clarification regarding two minor points.\n* You pointed out a relevant high-level similarity between $h$-GPI and MVE and proposed a direct comparison. We hope our discussion on how these methods solve distinct problems addresses your question and clarify why an empirical comparison, in the setting we address in this paper, would not be possible even in principle.\n\nWe trust that our responses have addressed your concerns and provided the necessary clarification on the questions you had and on your primary concern. \n- *Based on this additional information, and in line with the positive strengths you noted (regarding our setting, motivation, and theoretical results), we kindly request that you reconsider your evaluation.*\n- *We would be glad to address any other questions you may have. Otherwise, we hope that this enhanced understanding of our work may align with an Acceptance decision for this paper.*"}, {"review_id": "L9D4wbtDdw", "reviewer": "Reviewer_CAn3", "summary": "The paper presents a hybrid model-free and model-based policy improvement method for zero-shot policy generalization with successor features. The generalized value function is calculated using a generalized version of the multi-step Bellman operator, where a learned model is used in the rollout to predict future states and reward features.", "questions": "- (See also above): What would happen if you increased the horizon for SF-MPC further?\n- How good is the dynamics model in the experiments for Figs 2,3, 4, and 5? Maybe it would be beneficial to report prediction errors (although not absolutely necessary if results for SF-MPC for long horizons are shown)\n- If the model quality is not perfect, is there a sweet-spot h at which the performance of h-GPI starts to decrease again with increasing h?\n", "limitations": "Limitations are discussed relatively briefly, it might be worth broadening this section a little.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The idea to use multistep updates for generalized policy evaluation and improvement is novel to my knowledge. The paper is well written and relatively easy to understand. The authors carefully report detailed statistics for their experiments. I think that generally, the approach is a good idea and can be impactful if supported by the right set of experiments.", "weaknesses": "I am not sure about the meaning of the experimental results in section 4. As I understand it, the h-GPI approach amounts to planning ahead for h steps, and then obtaining the \"rest\" of the estimated future value for times after h using model-free successor features. If the learned model is relatively accurate, and the successor features are, compared to that, less accurate, then naturally the results improve as h increases and the decision-making relies more on the model over the successor features (as the authors also state after theorem 1). Likewise, it is unsurprising that simply ignoring the remaining value after h steps (as the SF-MPC baseline does iiuc, see footnote on page 8) performs worse than h-GPI. I think that a fair baseline would be SF-MPC for horizons much longer than h (the authors state themselves that SF-MPC underperforms since it \"requires long-term reasoning to collect items which are far from the agent\").\n\nAlternatively, one could make the argument that the \"cut-off\" done by h-GPI after h steps is a performance advantage over SF-MPC with much longer horizons, since rollouts can be shorter. However, I don't think that the authors are currently trying to make that argument; runtimes are barely mentioned (except for a brief discussion in the limitations section, but only in comparison to vanilla GPI).\n\nI would therefore suggest comparing to SF-MPC with much longer horizons, and if this should outperform h-GPI, maybe consider arguing from the perspective of run-time performance, supported by additional experiments on that.\n\nMinor issues: Should the reference in line 311 really be to figure 4, or should it be to figure 3? Also, it would probably help to quickly mention in the caption of figure 3 in what environment these experiments were run.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and for the suggestion of new experiments. Below we discuss how our newly added experiments clarify your raised concern.\n\n### Comparing $h$-GPI with SF-MPC with longer horizons\nThe reviewer asked about the meaning of the experimental results presented in Section 4. As described in lines 263--264, the objective of the experiments is \"to evaluate the effectiveness of $h$-GPI as a method for zero-shot policy transfer\".\n\nThe reviewer, subsequently, argued that $h$-GPI might outperform SF-MPC primarily because they think SF-MPC may have been allowed to plan for an insufficient number of timesteps. **This is not the case** for the following reasons:\n1. In our experiments, we *always* allow SF-MPC to plan for a number of steps that is higher than or equal to the number of steps that we allow $h$-GPI to plan (see the footnote on page 8). In other words, *SF-MPC is always given strictly more planning resources than $h$-GPI*, in all experiments. Therefore, even when SF-MPC is allowed to reason for significantly longer horizons than $h$-GPI, $h$-GPI still consistently outperforms it. \n2. To make this point clearer, we performed additional experiments and added novel results showing that even if we allow SF-MPC to plan for *twice as many steps* as $h$-GPI, $h$-GPI still outperforms it. Please see Figures A and B in the attached one-page PDF.\n3. As an example, in Figure A (FourRoom) one can see that even with a small planning horizon of $h=2$, $h$-GPI is capable of matching the performance of SF-MPC even when SF-MPC is allowed to plan for **ten times** longer (ie., $h=20$).\n4. Similarly, the experiment depicted in Figure B (FetchPush) compares both methods when SF-MPC is allowed to plan for up to $h=15$ steps—that is, **three times** longer than the maximum horizon we allow $h$-GPI to plan. Again, $h$-GPI consistently outperforms it (and other baselines) even when allowed to plan for significantly fewer steps.\n\nWe hope these results better clarify and emphasize the advantages of $h$-GPI over fully model-based planning methods as well as over various state-of-the-art GPI baselines.\n### How accurate is the learned model in your experiments?\nTo provide the reviewer with concrete data on this, we have included a new figure (Figure C) in the additional one-page PDF. This figure depicts the mean validation loss of the learned models both in the Reacher and FetchPush domains. As can be seen, the learned model rapidly becomes fairly accurate. Importantly, therefore, even with a well-trained model, SF-MPC (*even when given more than twice the amount of planning resources than $h$-GPI*) cannot outperform the technique we introduced in this paper.\n### Impact of the value of $h$ and model errors on $h$-GPI's performance\nThank you for bringing up this question. The reviewer is correct that when models are imperfect, $h$-GPI's performance may decrease under long horizons (large values of $h$). This effect can be observed in the FetchPush experiments (Figure 5). Here, $h$-GPI's mean performance decreases slightly due to model errors for some intermediate values of $h$. Importantly, however, further increasing $h$ past those values causes $h$-GPI to once again outperform competitors since, intuitively, the benefits of being able to perform transfer and generalization in future steps outweigh the downsides of short-term model predictions.\n### Feedback on presentation\nWe thank the reviewer for their attention to detail and for the feedback regarding two minor suggestions to improve presentation and clarity. The first point brought up by the reviewer was, indeed, a minor typo; regarding the second suggestion given by the reviewer, we will update the figure's caption to clarify it relates to the FourRoom domain. We will address both of these suggestions in the updated version of the paper.\n### Are \"unsurprising\" experimental results a weakness of the paper?\nThe reviewer argues that, in retrospect, combining planning steps and the generalization and transfer power of successor features is bound to result in a powerful method that performs well (they say that some experimental results are \"unsurprising\"). They argue that this is a weakness of the paper. We strongly disagree that experimental results being (from a given reviewer's perspective) \"unsurprising\" is a *weakness* of a paper.\n- The goal of our experiments was to provide strong empirical supporting the formal properties of $h$-GPI—which they did. \n- We have presented strong additional results addressing the reviewer's primary concern regarding the reasons why $h$-GPI outperformed SF-MPC. \n- Besides the strong empirical evidence of our method's performance, our contribution lies in that we introduced a method that is novel, principled, with various non-trivial formal performance guarantees, and that outperforms many strong, state-of-the-art competitors.\n- Up to this point, the problem of designing a principled method capable of combining imperfect models and the generalization power of GPI had remained an open problem in the field.\n### Final comments\nWe would like to once again thank the reviewer for their constructive feedback and clarification questions. The main—and only—concern brought up by the reviewer was related to whether $h$-GPI outperforms other methods due to unfair advantages related to planning horizons. We performed additional experiments to tackle this concern and provided further and strong support to our claim that $h$-GPI outperforms all competitors. \n* We trust the strong results discussed above fully address the reviewer's sole concern.\n* *Considering this resolution, and also in light of the positive feedback expressed, e.g., by obSw and MMCf, we would be thankful if the reviewer could revisit their evaluation of this paper.*\n* *We hope that our detailed response and the strengths identified may lead you to align your evaluation with an Acceptance decision.*"}, {"review_id": "zevFDybolQ", "reviewer": "Reviewer_obSw", "summary": "The authors present an to the Generalized Policy Improvement (GPI) framework, where the agent is able to leverage approximate models to derive a policy in a zero-shot fashion that adapts to unseen tasks related to others it has previously solved.\nThe paper derives an h-step planning horizon style action selection where the agent is able to trade-off long-term planning horizons for potentially compounding approximation errors in its update.\n\nThe authors provide theoretical results on the bound of improvement on their proposed method as it relates to model approximation error, and show that their approach is a consistent improvement over GPI in several standard RL benchmarks. ", "questions": "- See weaknesses\n\n- Line 197-198, it states the \"increasing\" the planning horizon improves performance because the error term becomes irrelevant. Did you mean to say decreasing? Why would increasing horizon make error terms irrelevant? Wouldn't the error compound and therefore become more relevant to the performance?\n\n\nNitpick:\n\n- Notation in Eq. 7, and subsequent uses of max_{a' \\in A}(T).....max_{a \\in A} is not a function applied to the operator T itself, but rather to the result of the operator applied to q.\nThis should probably be max_{a' \\in A}( T*^h q(St+1, a;))....notice the parenthesis.\n\n\n- Eq 10, why the sudden change from pi to mu to refer to a policy? Is there any special meaning to it? If so, please clarify, if not, please pick a notation a be consistent with it.\n\n- line 116 reads a bit awkward, I think there are some typos there.\n- line 151 that's not the correct use of e.g.", "limitations": "- The authors that in practicality it would also be needed a way to assess the discrepancy between the model approximation and the true model to determine what the value of h should be.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper extends the GPI framework to leverage approximate models of the problem at hand. This provides a natural extension of the model-free approach of GPI, to a model based approach that allows an agent to take advantage of long-horizon planning when selecting actions.\n\n- The authors provide a theoretical bound on the improvement of their approach as it relates to the model approximation error.\n\n- The authors also presented a thorough experimental section with several standard benchmarks in the tabular and continuous state cases. These results show a consistent improvement over standard GPI.", "weaknesses": "- The main weakness I see is not of the method itself, but perhaps on how to apply it in practice. The theoretical results bounds the improvement of GPI based on the model approximation error, and in the limit one could set the h-step to 0 and recover GPI. \nHowever, since one of the main benefits is the potential of zero-shot adaptation to novel tasks, it is difficult to see how one would estimate the model error in practice when trying to solve a new task.\nHow would you know what h would be right when solving a new problem? According to Fig 3, the right h value seems to be quite important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our work, and for highlighting the theoretical and experimental contributions of the paper.\n\n### How to identify the best possible value for $h$ ?\nThis is a great question relating to our formal bounds and the information needed to deploy our method. The formal bounds we introduced serve to mathematically quantify, e.g., how errors in the model and in the agent's value function approximators impact its performance, as a function of the planning horizon $h$. The goal of proving these bounds is to mathematically guarantee (for instance) that as $h$ increases, our method becomes arbitrarily less susceptible to sub-optimality in the agent's prior knowledge for solving previously-experienced tasks.\n\nFormally proving such bounds allows us to provide formal guarantees about the behavior and optimality properties of $h$-GPI as a function of the amount of planning resources that are given to the agent, thereby demonstrating *(i)* that ours is not a heuristic method for zero-shot transfer; and that *(ii)* its performance degrades gracefully as a function of imperfections in the agent's model and approximators.\n\nBelow we comment on the process of selecting effective values for $h$.\n\n* The reviewer is correct that if one wished to estimate the *optimal* value of $h$, they would need access to the true value of all error terms. In practice (as is the case with many other machine learning techniques) *deploying* our method does not require knowledge about such quantities. Instead, $h$ is seen as an adjustable hyperparameter of $h$-GPI. \n* Since $h$ regulates how the algorithm interpolates between purely model-free approaches (like GPI) and fully model-based RL (like Dynamic Programming), it we it as similar in nature to the $\\lambda$ parameter of TD($\\lambda)$. This latter hyper-parameter also regulates the amount of interpolation—in this case, between purely model-free Monte Carlo approaches and fully model-based Dynamic Programming techniques. \n* In practice, even though formal bounds relating approximation errors, performance, and $h$ (in our case) or bias, variance, and $\\lambda$ (in the case of TD($\\lambda$), both algorithms are deployed with the understanding that, in practice, their hyper-parameters $h$ and $\\lambda$ are domain-dependent hyper-parameters. These are in practice adjusted empirically or given domain knowledge, rather than computed based on the formal equations describing the formal properties of each method.\n* Having said that, the reviewer is absolutely right that it is important to determine if, in practice, our method's performance is not overly sensitive to $h$. In our experimental section, we show that $h$-GPI outperforms competing methods essentially for *all* the values of $h$ that we tested (concretely, in all experiments and comparisons we performed, competing methods outperformed $h$-GPI in only 2\\% of the cases even when considering possibly adversarial values of $h$). This shows that the algorithm is robust to the choice of its (only) hyperparameter. Extending the method to adaptively identify the best value of $h$ is an interesting direction for future work, and we will discuss it in our Future Work section.\n\n### On the impact of model errors and planning horizon on $h$-GPI's performance\n* In the sentence mentioned by the reviewer (lines 197--198), we are referring to errors, $\\epsilon$, in the agent's approximations of successor features. In this case, the longer the horizon, the more the agent relies on the model and the smaller the effect of possible successor feature approximation errors when performing GPI after $h$ steps. In particular, any performance estimation errors due to imperfect SFs will be discounted by $\\gamma^h$, thereby having a vanishing impact on the agent's performance as $h$ increases.\n* The reviewer is correct that increasing the horizon $h$ makes model errors compound—$h$ trade-offs between these two possible sources of error (model errors or errors in the agent's approximators). The impact of increasing $h$ in the agent's performance, as a function of increasingly imperfect models, is characterized in Theorem 1 and lines 189--191.\n* Regarding the latter point (compounding modeling errors), this effect can be observed in the FetchPush experiments (Figure B). Here, $h$-GPI's mean performance decreases slightly due to model errors for some intermediate values of $h$. However, further increasing $h$ past those values causes $h$-GPI to once again outperform competitors since, intuitively, the benefits of being able to perform transfer and generalization in future steps outweigh the downsides of short-term model predictions.\n\n### Feedback on presentation\n* We thank the reviewer for their attention to detail and for the feedback regarding a few minor suggestions to improve presentation and clarity. We will address all of them in the updated version of the paper.\n"}]

Author rebuttal:
We would like to thank the reviewers for their positive feedback and for the constructive suggestions for improving the paper.

In summary, one of the main concerns raised by reviewers was the need to compare GPI with SF-MPC under longer horizons. To address this concern, we have performed additional experiments to support our claims and the properties of our method. The corresponding results are shown in the additional attached one-page PDF file. Importantly:
1. Our novel results show that even if we allow SF-MPC to plan for *twice as many steps* as $h$-GPI, $h$-GPI still outperforms it. Please see Figures A and B in the attached one-page PDF.
3. As an example, in Figure A (FourRoom) one can see that even with a small planning horizon of $h=2$, $h$-GPI is capable of matching the performance of SF-MPC even when SF-MPC is allowed to plan for **ten times** longer (ie., $h=20$). 
4. Similarly, the experiment depicted in Figure B (FetchPush) compares both methods when SF-MPC is allowed to plan for up to $h=15$ steps—that is, **three times** longer than the maximum horizon we allow $h$-GPI to plan. Again, $h$-GPI consistently outperforms it (and other baselines) even when allowed to plan for significantly fewer steps.

In addition, we have carefully answered *all* other questions regarding our method properties—as well as minor clarifications regarding related works—in the answers provided as rebuttal to each of the reviewers.

We hope our detailed comments, as well as the additional strong empirical results discussed above, fully address the reviewers' main concerns.

Meta-review: The paper considers improving accuracy compared to generalized policy improvement in zero-shot transfer learning setting, as a function of the horizon. The contribution seems to be both interesting and significant, both from a theoretical perspective as well as in terms of applications. There are few-limitations, however, such as how to properly determine the most effective horizon length to use.
Decision: Accept (poster)