Goal-Space Planning with Subgoal Models
Authors: Chunlok Lo
Gabor Mihucz
Farzane Aminmansour
Adam White
Martha White
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Model-Based Reinforcement Learning
Planning
Temporal Abstraction

Abstract: This paper investigates a new approach to model-based reinforcement learning using background planning: mixing (approximate) dynamic programming updates and model-free updates, similar to the Dyna architecture. Background planning with learned models is often worse than model-free alternatives, such as Double DQN, even though the former uses significantly more memory and computation. The fundamental problem is that learned models can be inaccurate and often generate invalid states, especially when iterated many steps. In this paper, we avoid this limitation by constraining background planning to a set of (abstract) subgoals and learning only local, subgoal-conditioned models. This goal-space planning (GSP) approach is more computationally efficient, naturally incorporates temporal abstraction for faster long-horizon planning and avoids learning the transition dynamics entirely. We show that our GSP algorithm can learn significantly faster than a Double DQN baseline in a variety of situations.

Under review as a conference paper at ICLR 2023
GOAL-SPACE PLANNING WITH SUBGOAL MODELS
Anonymous authors
Paper under double-blind review
ABSTRACT
This paper investigates a new approach to model-based reinforcement learning using background planning: mixing (approximate) dynamic programming updates and model-free updates, similar to the Dyna architecture. Background planning with learned models is often worse than model-free alternatives, such as Double DQN, even though the former uses significantly more memory and computation. The fundamental problem is that learned models can be inaccurate and often generate invalid states, especially when iterated many steps. In this paper, we avoid this limitation by constraining background planning set of (abstract) subgoals and learning only local,
models. This goal-space planning (GSP) approach is more computationally efficient, naturally incorporates temporal abstraction for faster long-horizon planning and avoids learning the transition dynamics entirely. We show that our GSP algorithm can learn significantly faster than a Double DQN baseline in a variety of situations.
INTRODUCTION
Planning with learned models in reinforcement learning (RL.) is important for sample efficiency. Planning provides mechanism for the agent simulate data, in the background during interaction, to improve value estimates. Dyna (Sutton, 1990) is classic example of background planning. On each step, the agent simulates several transitions according to its model, and updates with those transitions as if they were real experience. Learning and using such a model is worthwhile in vast or ever-changing environments, where the agent learns over a long time period and can benefit from re-using knowledge about the environment.
The promise of Dyna is that we can exploit the Markov structure in the RL formalism, to learn and adapt value estimates efficiently, but many open problems remain to make it more widely useful. These include that 1) one-step models learned in Dyna can be difficult to use for long-horizon planning. 2) learning probabilities over outcome states can be complex, especially for high-dimensional states and 3) planning itself can be computationally expensive for large state spaces.
A variety of strategies have been proposed to improve long moogooorizon planning. Incorporating options as additional (macro) actions in planning is one approach. An option is a policy coupled with a termination condition and initiation (Sutton et al., 1999). They provide temporally-extende ways of behaving, allowing the agent to reason about outcomes further into the future. Incorporating options into planning is central motivation of this paper, particularly how do so under function approximation. Options for planning has largely only been tested in tabular settings (Sutton et al., 1999; Singh et al., 2004; Wan al., 2021). Recent work has considered mechanism for identifying and learning option policies for planning under function approximation (Sutton et al., 2022), but as yet did not consider issues with learning the models.
A variety of other approaches have been developed to handle issues with learning and iterating one-step models. Several papers have shown that using forward model simulations can produce simulated states that result in catastrophically misleading values (Jafferjee et al., 2020; van Hasselt et al., 2019; Lambert et al., 2022). This problem has been tackled by using reverse models (Pan et al., 2018; Jafferjee et al., 2020; van Hasselt al., 2019); primarily using the model for decision-time planning (van Hasselt et al., 2019; Silver et al., 2008; Chelu et al., 2020); and improving training strategies to account for accumulated errors in rollouts (Talvitie, 2014; Venkatraman et al., 2015; Talvitie, 2017). An emerging trend is to avoid approximating the true transition dynamics, and instead learn dynamics tailored predicting values on the next step correctly (Farahmand et al., 2017;

---

Under review as a conference paper at ICLR 2023
Farahmand, 2018; Ayoub et al., 2020). This trend is also implicit in the variety of techniques that encode the planning procedure into neural network architectures that can then be trained end-to-end (Tamar et al., 2016; Silver et al., 2017; Oh et al., 2017: Weber et al., 2017; Farquhar et al., 2018; Schrittiessrr et al., 2020). We similarly attempt to avoid issues with iterating models, but do so by considering a different type of model.
Much less work has been done for the third problem in Dyna: the expense of planning. There is, the model given-that
however, large literature on approximate dynamic programming- is focused on efficient planning (see (Powell, 2009)). Particularly relevant to this work is restricting value iteration to a small subset of landmark states (Mann et al., 2015). The resulting policy is suboptimal, restricted to going between landmark states, but planning is provably more efficient.
The use of landmark states has also been explored in goal-conditioned RL, where the agent given a desired goal state or states. The first work to exploit the idea of landmark states was for learning and using universal value function approximators (UVFAs) (Huang et al., 2019). The UVFA conditions action-values on both state-action pairs as well as landmark states. The agent can reach new goals by searching on a learned graph between landmark states, to identify which landmark to moves towards. A flurry of work followed, still in the goal-conditioned setting (Nasiriany et al., 2019; Emmons et al., 2020; Zhang et al.. 2020; 2021; Aubret et al., 2021; Hoang et al., 2021; Gieselmann & Pokomy, 2021; Kim et al., 2021; Dubey al., 2021).
In this paper, we exploit the idea behind landmark states for efficient background planning in general online reinforcement learning problems. The key novelty is framework to sabboall-onditionen models: temporally-extendee simpler to learn, as they are only learned for states local subgoals and they avoid generating entire next state vectors. We use background planning on subgoals, to quickly propagate (suboptimal) value estimates for subgoals. We propose subgoal-value bootstrapping, that leverages these quickly computed subgoal values, but mitigates suboptimality by incorporating an update on real experience. We prove that dynamic programming with our subgoal models is sound (Proposition 2) and that our modified update converges, and in fact converges faster due to reducing the effective horizon (Proposition 3). We show in the PinBall environment that our Goal Goal-Space Planning (GSP) algorithm can learn significantly faster than Double DQN, and still reaches nearly the same level of performance.
models that condition on subgoals. The models are designed to be
2 PROBLEM FORMULATION
We consider the standard reinforcement learning setting, where agent learns make deci- sions through interaction with an environment, formulated as Markov Decision Process (MDP) (8, R. P). S is the state space and A the action space. R S A x S R and the transition probability P S x A x S > [0, oo) describes the expected reward and probability of transitioning state, for a given state and action. On each discrete timestep the agent selects an action A, in state S,, the environment transitions to a new state S.+1 and emits a scalar reward Re+1.
The agent's objective is to find a policy æ future discounted reward G. = Re+1 Gt+1 The state-based discount 7e+11 [0. 1] depends on S (Sutton et al., 1), which allows us to specify termination. If S,41 is a terminal state, then 7++1 = 0; else, 7/+1 = for some constant % E [0, 1]. The policy can be learned using algorithms like Q-learning (Sutton & Barto, 2018), which approximate the aetion-valuess the expected return from a given state and action.
A [0. 1] that maximizes expected return, the
We can incorporate models and planning to improve sample efficiency beyond these basic model-free algorithms. In this work, we focus on background planning algorithms: those that learn model during online interaction and asynchronously update value estimates use dynamic programming updates. The classic example of background planning is Dyna (Sutton, 1990), which performs planning steps by selecting previously observed states, generating transitions-outcomee outcome rewards and next states for every action and performing Q-learning update with those simulated transitions.
Planning with learned models, however, has several issues. First, even with perfect models, it can be computationally expensive. Running dynamic programming can require multiple sweeps, which is infeasible over a large number of states. A small number of updates, on the other hand, may be insufficient. Computation can be focused by carefully selecting which states sample transitions
2

---

Under review as a conference paper at ICLR 2023
Figure 1: Goal-Space Planning in the Pinball environment (see Section 4.1). The agent be- gins with a set of subgoals (denoted teal) and learns set of subgoal-conditiones models. (Abstraction) Using these models, the agent forms abstract goal-space MDP where the states are subgoals with options to reach each subgoal actions. (Planning) The agent plans in this abstract MDP to quickly learn the values of these subgoals. (Projection) Using learned subgoal values, the agent obtains approximate values of states based on nearby subgoals and their values. These quickly updated approxi- mate values are then used speed up learning.
Goal-Space MDP
Abstraction
Projection
Planning
Subgoals
Approximate Values
from-called search control-but how to do so effectively remains largely unanswered with only a handful of works (Moore & Atkeson, 1993; Wingate et al., 2005; Pan et al., 2019).
The second difficulty arises due to errors in the learned models. In reinforcement learning, the transition dynamics represented with an expectation model [[["|ss [s, a] or a probabilistic model P(s'|s, (s, a). If the state space or feature space is large, then the expected next state or distribution over it can be difficult to estimate, as has been repeatedly shown (Talvitie, 2017). Further, these errors can compound when iterating the model forward or backward (Jafferjee et al., 2020; van Hasselt the environment deterministic
al., 2019). is common to use an expectation model, but unless or are only learning the values rather than action- values, this model can result in invalid states and detrimental updates (Wan al., 2019).
In this work, we take steps towards the ambitious question: how can we leverage a separate com- putational procedure (planning with model) to improve learning in complex environments? More specifically, we consider background planning for value-based methods. We address the two difficul- ties with classic background planning strategies discussed above, by focusing planning on a set of subgoals (abstract states) and changing the form of the model.
3 GOAL-SPACE PLANNING WITH SUBGOAL-CONDITIONE MODELS
At high level, the Goal-Space Planning algorithm focuses planning over a set of given abstract subgoals to provide quickly updated approximate values to speed up learning. To do so, the agent first learns a set of subbool-conditionel models, minimal models focused around planning utility. These models then forms temporally abstract goal-space MDP, with subgoals as states, and options to achieve each subgoal as actions. Finally, the agent can update its policy based on these subgoal values speed up learning. Figure 1 provides visual overview of this process.
3.1 DEFINING SUBGOALS
Assume we have finite subset of subgoal vectors G. For example, could correspond to a situation where both the front and side distance sensors of robot report low readings-what person would call being in corner. This g could be represented using two- coo-dimensionall vector, even if the sensory space is co-dimenniooal. In general, subgoals need not be instances of states (i.e., G & S). As another example, in Figure 1, we simply encode the nine subgoals- wwhic correspond to regions with a small padius-using a tabular encoding of nine one-hot vectors. Essentially, our subgoals define new state space in abstract MDP, and these new abstract states (subgoals) can be encoded or represented in different ways, just like in regular MDPs.
To fully specify subgoal, we need membership function that indicates if a state is member of subgoal g: m(s 9) = 1, and zero otherwise. Many states can be mapped to the same subgoal For the above example, if the first two elements of the state vector consist of the front and side distance sensor, m(s g) = 1 for any states where $1, $2 are less than some threshold e. For a concrete example, we visualize subgoals for the environment in experiments in Figure 1.
3

---

Under review as a conference paper at ICLR 2023
Finally, we only reason about reaching subgoals from subset of states, called initiation sets for options (Sutton et al., 1999). This constraint is key for locality, to learn and reason about a subset of states for subgoal. We assume the existence of a (learned) initiation function d(s. that is if in the initiation set for (e.g., sufficiently close in terms of reachability) and zero otherwise. We discuss some approaches to learn this initiation function in Appendix C. But, here, assume it is part of the discovery procedure for the subgoals and first focus on how to use it.
For the rest of this paper, we presume we are given subgoals and initiation sets. We develop algorithms to learn and use models, given those subgoals. We expect a complete agent to discover these subgoals on its own, including how represent these subgoals facilitate generalization and planning. To separate concerns, we focus on how the agent can leverage reasonably well-specified subgoals.
3.2 DEFINING CURGGAL-CCONDITIONE MODELS
For planning and acting to operate in two different spaces, we define four models: two used in planning over subgoals saobgoal-to-suuooae and two used to project these subgoal values back into the underlying state space (state-to to-ssooal)) Figure 2 visualizes these two spaces.
The suub-ol models are ry SS x 9 + R and I': S x 9 - j0, 1], where 9 = G ( {Sterminal) if there is a terminal state (episodic problems) and otherwise G = G. An option policy Ti S x A [0, for subgoal 9 starts from any s in the initiation set, and terminates in g-in where m(5,g) The -owrrd-model (s, g) is the discounted rewards under option policy Tg: (5, Ex, [Re+1 + 7/9 (r, (S.+1, g)
where the discount zero upon reaching subgoal
if m((++11.)) namely subgoal is achieved by heing in St+1
To (St41)
7441
else
The discount-model I'(s,g) reflects the discounted number of steps until reaching subgoal starting from s, in expectation under option policy Tg
T(s, g) = R,, (n..mm((+1119)) (()))))))))++*((55()))(((((++) (S =
These tose-ol will only be queried for (s,g) where d(s. > 0: they are local models.
To define subgoal-to-subgon models, F,, G 9 - R and F state-to-subgoal models. For each subgoal E G, we aggregate r, (s. g') ) for all s where m(s, g) =
9 [0, 1], use the
(g. dat
Σ emm(s T1
and F(g.g') =(g)
[e [(s,g')
(1)
def Σ esm(s.g)=1 m(s.g) 9). This definition assumes uniform weighting over the We could allow a non-uniform weighting, potentially based on visitation frequency in the environment. For this work, however, we assume that m(s. g) = 1 for a smaller number states with relatively similar g'), making a uniform weighting reasonable.
for normalizer =(g)
states s where m(s,g) g)
These models are also local models, as we can similarly extract d(g. g') from d(s. and only reason about g' nearby or relevant to g. We set d(g, g') = maX.eS:m(ssgji> ((s,g') indicating that if there a state s that is in the initiation set for g' and has membership in g. then g' is also relevant to g.
Original MDP
Subgoal abstraction
Let consider example, in Figure 2. The red states are members of (m(A, g) = 1) and the blue members of (m(X, g²) 1.m(Y, gg)
1). For all in the diagram, d(s,g') > 0 (all are in the initiation set): the policy Fg can queried from any s to get to g'. The green path in the left indicates the trajectory under Ty from A, stochastically reaching either X Y, with accumulated reward r, (A,g") and discount I(A, g') (averaged over reaching X and Y). The subgoal-to-
Fylona)) i'o.s")
Figure 2: Original and Abstract Space. subgoal models, on the right, indicate g' can be reached from g, with F. (g. g') averaged over both (,, g') and r, (B.') g') and [(g. g') over [(A, g') and T(B, g'), described in Equation (1).
'The first input is any E G. the second is G. which includes Surminal-- We need to reason about reaching any subgoal Sueminal- But Steminal is real state: we do not reason about starting from it reach subgoals.
4

---

Under review as a conference paper at ICLR 2023
3.3 GOAL-SPACE PLANNING WITH CONDITIOOED MODELS
We can now consider how to plan with these models. Planning involves learning ūgg): the value for different subgoals. This can be achieved using an update similar to value iteration, for all g
(g)) = max "' 1=00 (g.gg") + [gg. ((g.g')(gg) 8 (Background Planning)
(2)
The value of reaching g' from g is the discounted rewards along the way. (g,99') (.).9"). plus the discounted value in g'. If ('g.gg') is very small, it is difficult to reach g' from g-or takes many steps andps-and so the value in g' is discounted by more. With a relatively small number of subgoals, we can sweep through them all to quickly compute ö(g). With larger set of subgoals, we can instead do as many updates possible, in the background on each step, by stochastically sampling g.
We can interpret this update as a standard value iteration update in new MDP, where 1) the set of states is G. 2) the actions from E G are state-dependent, corresponding to choosing which g' E G to go to in the set where d(g. g') > 0 and 3) the rewards are F.y and the discounted transition probabilities are I', Under this correspondence. it is straightforward to show that the above converges to the optimal values in this new Goal-Space MDP, shown in Proposition 2 in Appendix B.
This goal-space planning approach does not suffer from typical issues with model-based based RI.. First, the model is not iterated, but we still obtain temporal abstraction because the model itself incorporates it. Second, we do not need to predict entire state vectors distributions over brem-because we instead input the outcome g' into the function approximator. This may feel like a false success as it potentially requires restricting ourselves to smaller number of subgoals. If we want to use larger number of subgoals, then we may need a function to generate these subgoal vectors anyway- bringing us back to the problem of generating vectors. However, this is likely easier 1) the subgoals hes can be much smaller and more abstract, making it more feasibly to procedurally generate them and 2) it may be more feasible maintain a large set of subgoal vectors, or generate individual subgoal vectors, than producing relevant subgoal vectors from a given subgoal.
Now let us examine how use ū(g) update our main policy. The simplest way to decide how to behave from a state is to cycle through the subgoals, and pick the one with the highest value.
(3) and take action a that corresponds the action given by my for this maximizing g. However, this approach has two issues. First restricting to going through subgoals might result in suboptimal policies. From given state s, the set of relevant subgoals 9 may not be on the optimal path. Second, the learned models themselves may have inaccuracies, or planning may not have been completed in the background, resulting in ö(g) that are not yet fully accurate.
Uaub (s) def maxgeg:d(e.g))> r-y (s.g) g) + ((gg) (Projection Step)
We instead propose to use (sub(s) within the bootstrap target for the action-values for the main policy, For a given transition (Se, Ac, Ri+1, Se+1), either as the most recent experience or from a replay buffer, the proposed subgoal-vatle valuee bootstrapping update to parameterized q(S,, Ar; w) uses TD error
8 del Rot1 + 7++1 (11 3) max ((a42 a': w) +B Usub (SL+1) A(
(4)
Standard bootstrap Larget
Subgoal value
for some /3 E [0. 1]. For 3 = O, we get standard Q-learning update. For 3 1, we fully bootstrap off the value provided by Uaub (S++1). This may result in suboptimal values q(S,, Ar; w). but should learn faster because a reasonable estimate of value has been propagated back quickly using goal-space planning. On the other hand, , = 0 is not biased by a potentially suboptimal ((g). but does not take advantage of this fast propagation. An interim / can allow for fast propagation, but also help overcome suboptimality in the values.
15(8 (x) wo0()))))))))
( g:)) + r(S T (,19))
8
max
rs(8', .6) + D(S" ao)
Figure 3: Computing Venb((S") to update the policy at S. This result is intuitive:
We can show that the above update improves the convergence rate. -aauue bootstrapping changes the discount rate to 1 3). In the extreme case of 3 1, we are moving our estimate towards 1 for Uuub not based on q without any bootstrapping: it is effectively a regression problem. We prove this intuitive result in Proposition 3 in Appendix B. One other benefit of this approach is that the initiation sets need not cover the whole space: we can have a state d(s, g) = 0 for all g. If this occurs, we simply do not use Usub and bootstrap as usual.
5

---

Under review as a conference paper at ICLR 2023
3.4 PUTTING IT ALL TOGETHER: THE FULL GOAL-SPACE PLANNING ALGORITHM
The remaining piece is to learn the models and put it all to- gether. Learning the models is straightforward, leverage the large literature on general value functions (Sut- ton et al., 2011) 1) and UVFAs (Schaul al., 2015). There are nuances involved in 1) restricting updating to relevant states according to d(s, g). 2) learning option policies that reach subgoals, but also maximize rewards along the way and 3) con- sidering ways to jointly learn and r. For space we include these details in Appendix C.
Environment
can
updatee via Eq
sample action
A
S 7, R
Policy
S
The algorithm is visualized in Figure (pseudocode in appx. C.3). The steps of agent-environment interaction include:
Msub (5")
((g)
project via Eq 4
plan via 3q
update
r
I.r.f.F
1) take action A, in state S,, to get S1+1, Re+1 and Y4+1
2) query the model for r,y (
((g) for all
Model
where d(S 9) > 0;
3) compute projection (S using Eq. (3) and step 2;
4) update the main policy with the transition and Wauh (St..).
Figure Goal-Space Planning.
using Eq. (4).
All background computation is used for model learning using replay buffer and for planning to obtain so that they can be queried at any time on step 2.
EXPERIMENTS WITH GOAL-SPACE PLANNING
We investigate the utility of GSP, for 1) improving sample efficiency and 2) re-learning under non- stationarity. We compare to Double DQN (DDQN) (Van Hasselt et al., 2016), which uses replay and target networks. We layer GSP on top of this agent: the action-value update is modified to incorporate subgoal-value bootstrapping. By selecting 3 = O, we perfectly recover DDQN, allowing us to test different/ |3 values to investigate the impact of incorporating subgoal values computed using background planning.
4.1 EXPERIMENT SPECIFICATION
We test the agents in the PinBall environment (Konidaris & Barto, 2009), which allows for a variety of easy and harder instances test different aspects. The agent has to navigate small ball to destination in a maze-like environment with fully elastic and irregularly shaped obstacles. The state is described by 4 features: x E [0, 1) [0, 1), 1), [-1, The agent has discrete actions: increase/decrease i increase/decreass ÿ. and nothing. The agent receives reward of -5 per step and a reward of 10,000 upon termination the goal location. PinBall has continuous state space with complex and sharp dynamics that make learning and control difficult. We used harder version of PinBall in our first experiment, shown in Figure 5, and simpler one for the non stationary experiment, shown in Figure 9, to allow DDQN better chance to adapt under non non-stationarity.
The hyperparameters are chosen based on sweeping for DDQN performance. We then fixed these hyperparameters, and used them for GSP. This approach helps ensure they have similar settings, with the primary difference due to incorporating subgoal-vahl bootstrapping. We used neural networks with ReLU activations and 0.1; details about hyperparameters are in Appendix F.
The set subgoals for GSP are chosen to cover the environment in terms of (xx, y) locations. For each subgoal with location (I,,, ), we set m(s,
1 for (x, y, ., 1)) if the Euclidean distance between (x. y) and (zg: Vg) is below 0.035. Using a region, rather than requiring (x, y) (z Vg), is necessary for continuous state space. The agent's velocity is not taken into account for subgoal termination. The width of the region for the initiation function is 0.4. More details about the layout of the environment, positions of these subgoals and initiation functions shown in Figure 5.

---

Under review as a conference paper at ICLR 2023
GSP (3 0.10.)
50
Approximate LAVI
40
Reward Rate
30
DDQN
Averaged
20
over
30 Runs
10
0
0 500
1000
1500
2000 2500
Steps (x100)
Figure 5: (left) The harder PinBall environment used in our first experiment. The dark gray shapes are obstacles the ball bounces off of, the small blue circle the starting position of the ball (with no velocity), and the red dot the goal (termination). Solid circles indicate the location and radius of the subgoals (m)) with wider initiation set visualized for two subgoals (pink and teal). (right) Performance in this environment for GSP with = 0.1, DDQN, and approximate LAVI, with the standard error shown. Even just increasing to / 0.1 allows GSP to leverage the longer-horizon estimates given by the subgoal values, making it learn much faster than DDQN. Approximate LAVI is able to learn quickly, but levels off at suboptiomal performance, as expected.
4.2 EXPERIMENT 1: INVESTIGATING GSP WITH PRE-TRAINED MODELS
We first investigate the utility of the models after they have been learned in pre-training phase. The models use the same updates as they would when being learned online, and are not perfectly accurate. Pre-training the model allows to ask: if the GSP agent had previously learned model in the environment-or or had offline data to train its model-can can it leverage it to learn faster now? One of the primary goals of model-based RL is precisely this re-use, and so it is natural to start in setting mimicking this use-case. We assume the GSP agent can do many steps of background planning, so that ō is effectively computed in early learning; this is reasonable as we only need to do value iteration for 9 subgoals, which is fast. We compare GSP with 3 = 0.1 against two baselines: DDQN and approximate LAVI. DDQN is the model-free baseline which GSP builds on top of, and can also be viewed as a version of Dyna when the replay buffer is viewed as non-parametric model in the PinBall environment (van Hasselt et al., 2019; Pan et al., 2018), with planning updates sampled based on the agent's ' prior state-action visitation distribution. Approximate LAVI is modified version of LAVI (Mann et al., 2015) that uses learned subgoal models, and a version of GSP that fully relies on subgoal values when performing its updates with 3 = O. We selected 3 = 0.1 as it provided the best tradeoff of the beta values but we find that as small as le -8 was able to outperform DDQN. The performance of GSP with different 3 can be found in Appendix I.
We see in Figure that GSP learns much faster than DDQN, and reaches the same level of performance. This is the result we should expect GSP gets to leverage pre-trained model, after all but it is an important sanity check that using models in this new way is effective. Of particular note is that even just increasing / from 0 (which is DDQN) to 8 0.1 provides the learning speed boost without resulting in suboptimal performance. Likely, in early learning, the suboptimal subgoal values provide coarse direction to follow, more quickly update the action-values, which is then refined with more learning. When the approximate subgoal models are fully relied upon on as with approximate LAVI, we similarly get fast initial learning, but plateaus at more suboptimal point.
To further investigate the hypothesis that GSP more quickly changes its value function early in learning, we visualize the value functions for both GSP and DDQN over time in Figure After 2000 steps, they are not yet that different, because there are only four replay updates on each step and it takes time to visit the state-space and update values by bootstrapping off of subgoal values. By step 6000, though, GSP already has some of the structure of the problem, whereas DDQN has simply pushed down many its values (darker blue).
To see whether GSP is feasible apply to other problems, we also evaluated GSP in Lunar Lander (Brockman et al., 2016), an environment where subgoal specification is not as obvious and environ- ment dynamics cause the agent to frequently crash. We include those results in Appendix H. but note that similar conclusions about comparisons between GSP and DDQN hold. We also compared GSP to various Dyna-style planning algorithms, some of which also incorporates temporal abstraction, in Appendix G and find that GSP is able to outperform these alternatives.
7

---

Under review as a conference paper at ICLR 2023
2000
6000
10000
22000
40000
100000
GSP
DDQN
Figure 6: (left) Visualizing the action- for DDQN and GSP (B 0.1) at various points in
training. (right) Usub obtained from using the learned subgoal-vad vaauues in the projection step.
4.3 ACCURACY OF THE LEARNED MODELS
g(s
One potential benefit of GSP is that the models themselves may be easier to learn, because we can leverage standard value function learning algorithms. We visualize the models learned for the previous experiment, as well as the resulting Usab; with details about model learning in Appendix E.
ry(s, g)
In Figure we see how learned state-to-sufe tuusala models accurately learn the structure. Each plot shows the learned state-to-subgoal for one subgoal, visualized only for the initiation set d(s, g) > O. We larger discount and reward values predicted based reachability. However, the models are not perfect. We measured model error and find it is reasonable but not very zero (see Appendix E). This result is actually encouraging: inaccuracies in the model do not prevent useful planning.
Figure 7: Learned state-to- subgoal models. White indicates d(s.g) 0.
is informative to visualize Usub We can see in Figure that the general structure correct, matching the optimal path, but that it indeed looks suboptimal compared the final values computed in Figure 6 by DDQN. This inaccuracy is likely due both to some inaccuracy in the models, as well as the fact that subgoal placement not optimal. This explains why GSP has lower values particularly in states near the bottom, likely skewed downwards by Usub-
Finally, we test the impact on learning using less accurate models. After all, the agent will want to start using its model as soon as possible, rather than waiting for to become more accurate. We ran GSP using models learned online, using only 50k, 75k and 100k time steps to learn the models. We then froze the models and allowed GSP to learn with them. We can see in Figure 8 that learning with too inaccurate of model-with 50k-fails, but already with 75k performance improves considerably and with 100k we already nearly at the same level of optimal performance as the pre-trained models. This result highlights it should be feasible learn and these models in GSP, all online.
160
100k
120
Reward
Rate
75k
Averaged
over
3D Runs
40
50k
0 500
1000
1500
2000
2500
Steps (x100)
Figure 8: The impact planning perfor- mance using frozen models with differing accuracy (shading shows standard error).
4.4 EXPERIMENT 2: ADAPTING IN NONSTATIONAR PINBALL
Now consider another typical use-case for model-based RL: quickly adapting to changes in the environment. We let the agent learn in PinBall for 50k steps, and then switch the goal to a new location for another 50k steps. Goal information is never given to the agent, so it has to visit the old goal, realize is no longer rewarding, and re-explore to find the new goal. This non-stationary setting harder for DDQN,
simpler configuration for PinBall, shown in Figure 9.
We can leverage the idea exploration bonuses, introduced in Dyna- (Sutton & Barto, 2018). Exploration bonuses are proportional to the last time that state-action the agent to revisit parts of the state-space that it has not seen recently, in case that part of the world has changed. For us, this corresponds to including reward bonus Thonus in the planning and projection steps: ö(g)
visited. This encourages
=0: (g (g.g') T(g. g¹) (ū(g') + Tbonus (g')) and (s)
8

---

Under review as a conference paper at ICLR 2023
200
GSP (B = 0.1)
150
LJ.7
Reward
100 Rate
DDQN
200
400
600
800
Steps (x1 (x100)
Figure 9: (left) The Non-stationary PinBall environment. For the first half of the experiment, the agent terminates at goal A while for the second half, the agent terminates at goal B. (right) The performance of GSP (3 = 0.1) and DDQN in the environment. The mean of all 30 runs is shown as the dashed line. The 25th and 75th percentile run for each algorithm are also highlighted. We see that GSP with exploration bonus was able adapt more quickly when the terminal goal switches compared to the baseline DDQN algorithm where goal values are not used.
max (s, +I (ā(g) + Toomus (o)) Because we have small, finite set of subgoals, it is straightforward to leverage this idea that was designed for the tabular setting. We use Fbomus (g) 1000 the count for g is zero, and 0 otherwise. When the world changes, the agent recognizes that has changed, and resets all counts. Similarly, both agents (GSP and DDQN) clear their replay buffers.
The GSP agent can recognize the world has changed, but not how has changed. It has to update its models with experience. The toue-oo- models and subgoal-to-subgoal models local to the previous terminal state location and the new one need to change, but the rest of the models are actually already accurate. The agent can leverage this existing accuracy.
In Figure 9, we can see both GSP and DDQN drop in performance when the environment changes, with GSP recovering much more quickly. is always possible that an inaccurate model might actually make re-learning slower, reinforcing incorrect values from the model. Here. though, updating these local models is fast, allowing the subgoal values also be updated quickly. Though
shown in the plot, GSP without exploration bonuses performs poorly. Its model causes it to avoid visiting the new goal region, so preventing the model from updating, because the value in that bottom corner low.
5 CONCLUSION
In this paper we introduced new planning framework, called Goal-Space Planning (GSP). GSP provides a new approach to use background planning to improve action-value estimates, with minimalist, local models and computationally efficient planning. We show in the PinBall environment that these subgoal- cabgoal-conditioned models can be accurately learned using standard value estimation algorithms and that GSP is robust to less accurate models (Section 4.3). We also find that GSP can significantly improve the speed of learning over DDQN in both the PinBall environment and outperforms several Dyna variants, including Dyna with options (Appendix G), and that GSP relearns more quickly under non-stationarity than DDQN (Section 4.4). Additionally, we compared GSP DDQN in another environment, called Lunar Lander (Appendix H), both highlight that the conclusions extend and to demonstrate that it is straightforward to apply GSP to other problems.
This work introduces a new formalism, and many new technical questions along with it. We have only tested GSP with pre-trained models and assumed a given set of subgoals. Our imitial experiments learning the models online, from scratch, indicate that GSP can get similar learning speed boosts. Using recency buffer, however, accumulates transitions only along the optimal trajectory, sometimes causing the models to become inaccurate part-way through learning. An important next step is to incorporate smarter model learning strategies. The other critical open question is in subgoal discovery. We somewhat randomly selected subgoals across the PinBall environment, with a successful outcome; such approach is unlikely to work in many environments. In general, option discovery and subgoal discovery remain open questions. One utility of this work is that it could help narrow the scope the discovery question, that of finding abstract subgoals that help the agent plan more efficiently.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Arthur Aubret, Lactitia matignon, and Salima Hassas, DisTop: Discovering Topological representa- tion to learn diverse and rewarding skills. arXiv:2106.0385 [cs]. 2021.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-Based Reinforeement Learning with Value- Targeted Regression. In International Conference on Machine Learning, 2020.
Andre Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygun, Philippe Hamel, Daniel Toyama, Jonathan hunt, Shibl Mourad, David Silver, and Doina Precup. The Option Keyboard: Combining Skills in Reinforcement Learning. In Advances in Neural Information Processing Systems, 2019.
André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117 (48), 2020.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv:1606.015.4 2016.
Veronica Chelu, Doina Precup, and Hado P van Hasselt. Forethought and hindsight in credit assignment. In Advances in Neural Information Processing Systems, 2020.
Rohit K. Dubey, Samuel S. Sohn, Jimmy Abualdenien, Tyler Thrash, Christoph Hoelscher, André Borrmann, and Mubbasir Kapadia. SNAP.Successor Entropy based Incremental Subgoal Discovery for Adaptive Navigation. In Motion, Interaction and Games, 2021.
Scott Emmons, Ajay Jain, Misha Laskin, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning. In Advances in Neural Information Processing Systems, 2020.
Amir-massoud Farahmand. Iterative Value-Aware Model Learning. In Advances in Neural Informa- tion Processing Systems 31, 2018.
Amir massoud Farahmand, Andre M S Barreto, and Daniel N Nikovski. Value- Loss Function for based Reinforcement Learning. In International Conference on Artificial Intelligence and Statistics, 2017.
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. TreeQN and ATreeC: Differentiable Tree- Strructurd Models for Deep Reinforcement Learning. In International Confer- on Learning Representations, 2018.
Robert Gieselmann and Florian T. Pokorny. Learning. IEEE Robotics and Automation Letters, 6(3), 2021.
Hierarchical Reinforcement
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Christopher Hoang, Sungryull Sohn, Jongwook Choi, Wilka Carvalho, and Honglak Lee, Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning. In Advances in Neural Information Processing Systems, 2021.
Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching. In Advances in Neural Information Processing Systems, 2019.
Taher Jafferjee, Ehsan Imani, Erin Talvitie, Martha White, and Micheal Bowling. Hallucinating Value: A Pitfall of Dyna-style Planning with Imperfect Environment Models. arXiv:2006. 04363 [cs, stat), 2020.
Khimya Khetarpal, Zafarali Ahmed, Gheorghe Comanici, David Abel, and Doina Precup. What can I do here? A Theory of Affordances in Reinforcement Learning. In International Conference on Machine Learning, 2020.
10

---

Under review as a conference paper at ICLR 2023
Junsu Kim, Younggyo Seo, and Jinwoo Shin. Landmark-Guide Subgoal Generation in Hierarchical Reinforcement Learning. In Advances in Neural Information Processing Systems, 2021.
G.D. Konidaris and A.G. Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. In Advances in Neural Information Processing Systems, 2009.
Nathan Lambert, Kristofer Pister, and Roberto Calandra. Investigating Compounding Prediction Errors in Learned Dynamics Models. arXiv:2203.00637 [es], 2022.
Timothy A. Mann, Shie Mannor, and Doina Precup. Approximate Value Iteration with Temporally Extended Actions. Journal of Artificial Intelligence Research, 53, 2015.
Amy McGovern and Andrew Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. In International Conference on Machine Learning, 2001.
Andrew W Moore and Christopher G Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning, 13(1), 1993.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with Goal-Conditioned Policies. In Advances in Neural Information Processing Systems, 2019.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. Advances in Neural Information Processing Systems, 2017.
Yangchen Pan, Muhammad Zaheer, Adam White, Andrew Patterson, and Martha White. Organizing Experience: A Deeper Look at Replay Mechanisms for Sample-Based Planning in Continuous State Domains. In International Joint Conference on Artificial Intelligence, 2018.
Yangchen Pan, Hengshuai Yao, Amir-Massoud Farahmand, and Martha White. Hill climbing on value estimates for search-control in Dyna. In International Joint Conference on Artificial Intelligence, 2019.
Warren B. Powell. What you should know about approximate dynamic programming. Wiley InterScience, 2009.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal Value Function Approxima- tors. In International Conference on Machine Learning, 2015.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588 (7839), 2020.
David Silver, Richard S Sutton, and Martin Müller. Sample-based learning and search with permanent and transient memories. In International Conference on Machine Learning, 2008
David Silver, Hado Hasselt, Mattco Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac- Amool, David Reichert, Neil Rabinowitz, Andre Barreto, and Thomas Degris. The Predictron: End-To-End Learning and Planning. In International Conference on Machine Learning, 2017.
Satinder Singh, Andrew Barto, and Nuttapong Chentanez. Intrinsically Motivated Reinforcement Learning. Advances in Neural Information Processing Systems, 2004.
Martin Stolle and Doina Precup. Learning Options Reinforcement Learning. Abstraction, Reformulation, and Approximation, 2002.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
Richard S Sutton, Doina Precup. and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2), 1999.
Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsuper- vised sensorimotor interaction. In International Conference on Autonomous Agents and Multiagent Systems, 2011.
11

---

Under review as a conference paper at ICLR 2023
Richard S Sutton, A R Mahmood, and Martha White. An emphatic approach to the problem of learning. The Journal of Machine Learning Research, 2016.
off-po
Richard S. Sutton, Marlos C. Machado, G. Zacharias Holland, David Szepesvari, Finbarr Timbers, Brian Tanner, and Adam White. Reward-Respecting Subtasks for Model-Based Reinforcement Learning. arXiv:2202. 03466 [cs], 2022.
R.S. Sutton. Integrated architectures for learning planning and reacting based on approximating dynamic programming. International Conference on Machine Learning, 1990.
Erik Talvitie. Model regularization for stable sample roll-outs. Uncertainty in Artificial Intelligence, 2014.
Erik Talvitie. Self-Correcting Models for Model-Based Reinforcement Learning. In AAAI Conference on Artificial Intelligence, 2017.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value Iteration Networks. In Advances in Neural Information Processing Systems, 2016.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In AAAI conference artificial intelligence, 2016.
Hado P van Hasselt, Matteo Hessel, and John Aslanides. When parametric models in reinforcement learning? In Advances in Neural Information Processing Systems, 2019.
A Venkatraman, M Hebert, and J. Andrew Bagnell. Improving Multi-Step Prediction of Learned Time Series Models. AAAI Conference on Artificial Intelligence, 2015.
Yi Wan, Muhammad Zaheer, Adam White, Martha White, and Richard S. Sutton. Planning with Expectation Models. In International Joint Conference on Artificial Intelligence, 2019.
Yi Wan, Abhishek Naik, and Richard S. Sutton. Everage-Reward Learning and Planning with Options. In Advances in Neural Information Processing Systems, 2021.
Theophane Weber, Sebastien Racanière, David P Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, Agents
Razvan Pascanu, Peter Battaglia, David Silver, and Daan Wierstra. Imagination-Augmeent for Deep Reinforcement Learning. Advances in Neural Information Processing Systems, 2017.
Martha White. Unifying task specification in reinforcement learning. In International Conference on Machine Learning, 2017.
David Wingate, Kevin D Seppi, Cs Byu Edu, and Cs Byu Edu. Prioritization Methods for Accelerating MDP Solvers. Journal of Machine Learning Research, 2005.
Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World Model as a Graph: Learning Latent Landmarks for Planning. In International Conference on Machine Learning, 2021.
Tianren Zhang, Shangqi Guo, Tian Tan, Xiaolin Hu, and Feng Chen. Generating adjacency- constrained subgoals in hierarchical reinforeement learning. In Advances in Neural Information Processing Systems, 2020.
12

---

Under review as a conference paper at ICLR 2023
A STARTING SIMPLER: GOAL-SPACE PLANNING FOR POLICY EVALUATION
To highlight the key idea for efficient planning, we provide an example of GSP in a simpler setting: policy evaluation for learning o" for fixed deterministic policy π in a deterministic environment, assuming access to the true models. The key idea is to propagate values quickly across the space by updating between subset of states that call subgoals, 9 (Later we extend G ş S to abstract subgoal vectors that need not correspond to any state.) To do so, we need temporally extended models between pairs g, g that may be further than one-transition apart. For policy evaluation, these models are the accumulated rewards Tn,y : S x S + I and discounted probabilitiess Pa,y x S + [0. 1] under x:
C S, visualized in Figure 10.
Tx. (g.gg def E,, [Be+1 + Yo' (5t
Pr. del (5 r1 79',++1 (a.t:i,,,,,tt,,,1/
where "g,,t++1 = 0 St+1 g' and otherwise equals 1t+1, the environment discount. If we cannot reach g from g under и,, then P=.)(g.)) (') will simply accumulate many zeros and be zero. We can treat 9 as our new state space and plan in this space, to get value estimates v for all g E E
v(g) = T (g: g') + (9. )o(g') where g' = erg
where 9 GUI {stemnina) { } if there is a terminal state (episodic problems) and otherwise G G. Is straightforward to show this converges, because Pn,y is a substochastic matrix (see Appendix A.
Once we have these values, can propagate these other states, locally, again using the closest to s. We can do so by noticing that the above definitions can be easily extended to "x.,(8,, g') and (s, g'), since for a pair (s.g) g) they are about starting in the state and reaching g under π.
v(s) (s. + (s,
where argmaxyeg (x.)
(5)
Because the rhs of this equation is fixed, we only cycle through these states once to get their values.
All of this might seem like a lot of work for policy evaluation; indeed, it will be more useful to have this formalism for control. But, even here goal-space planning can be beneficial. Let assume a chain $1, $2, ..... Sp, where requires sweeping over 10 states, rather than 1000. Further, we have taken a 1000 horizon problem and converted it into a 10 step one.? As result, changes in the environment also propagate faster. If the reward at s' changes, locally the reward model around s' can be updated quickly, to change Ta (g. g') for pairs g, where s' is along the way from g to g'. This local change quickly updates the values back to earlier ğ E G.
1000 and G = {$100, $200. .... $1000) ). Planning over g G only
A.1 PROOFS FOR THE DETERMINISTIC POLICY EVALUATION SETTING
We provide proof's here for the deterministic policy evaluation setting. We assume throughout that the environment discount N is constant %o E [0, 1) for every step in an episode, until termination when it is zero. The below results can be extended to the case where % 1, using the standard strategy for the stochastic shortest path problem setting.
we can guarantee that the update for the values for will converge. Recall that Ç U {Sternina] is the augmented goal space that includes the terminal state. This terminal state is not a subgoal-since it is not a real state-but is key for appropriate planning.
First, we want show that given F... and Pr.y.
Lemma 1. Assume that we have a deterministic MDP, deterministic policy v, 7e < 1, a discrete set of subgoals G C S,, and that we iteratively update Ut E 1R1 with the dynamic programming update v,(g) = (9. (') + Pa.:9999 (.""9.9"""--1(""" where g' argmax argmaxPr..99.93 (9.')
(6)
g'Eğ
for all E G, starting from an arbitrary (finite) initialization E [R(0, with (3 fixed at zero. Then then Ut converges a fixed point.
"nn this simplified example, we can plan efficiently by updating the value at the end S.. and then updating states backwards from the end. But, without knowing this structure, it is not general purpose strategy. For general MDPs, we would need smart ways to do search control: the approach to pick states from one-step updates. In fact, we can leverage search control strategies to improve the goal-space planning step. Then we get the benefit of these approaches, as well the benefit of planning over a much smaller state space.
13

---

Under review as a conference paper at ICLR 2023
Ste- Backup
s1
s2
s3
s4
s5
s7
s8
s9
$10
s11
s12
Terminal
Goal-Space Planning
$1
s3
s5
S7
S9
s10
s11
s12
Terminal
Figure 10: Comparing one-step backup with Goal-Space Planning when subgoals concrete states. GSP first focuses planning over smaller set of subgoals (in red), then updates the values of individual states.
Proof. To analyze this as a matrix update, we need to extend Px, (g.9) g') to include an additional row transitioning from Steminal- This row is all zeros, because the value in the terminal state is always fixed at zero, Note that there are ways to avoid introducing terminal states, using transition-bred based discounting (White, 2017), but for this work it is actually simpler to explicitly reason about them and reaching them from subgoals.
To show this we simply need to ensure that Pa,y a substochastic matrix. Recall that
Pr.y(g.g)) del [1(++ = g') + + (Sttt,, =
where 79'++1 0 if S = g' and otherwise equals 7 the environment discount. If it substochastic, then | < 1. Consequently, the Bellman operator
(Bv)(g) Tm, (g. 9 + l )o('')
where g' = argmax PaanaxxPx..l0 (9.9( g'Eg
a contraction, because [B Bu2 1|2 = 1
S || 1121111 22l1a < ||01 - 1222
Because To 1, then either g immediately terminates in g'. giving 1(S:+1 g) Pr.
= Y411 + < Te. Or, it does not immediatcly terminate, and 1(S = dh 7g Pa. (S++1, 0+ 7e S Te because (S,,(S)), 1. There- fore, if Yo < then | Pr,7 S S/c
Proposition 1. For deterministic MDP, deterministic policy n, and discrete of subgoals G C that are all reached by a in the MDP, given the ü(g) obtained from Equation 6, if we set
v(s) (s.g) + Pa g),g)(())
where g = argmax (s,g)
9Eg
for all states S then we get that Uy.
Proof. For a deterministic environment and deterministic policy this result is straightforward. The term (s, > 0 only if g is on the trajectory from s when the policy π is executed. The term (s, g) consists of deterministic (discounted) rewards and ū(g) is the true value from g. shown in Lemma 6 (namely ū(g) = ez (g)). The subgoal is the closest state on the trajectory from s, and P (8, is 7t where is the number of steps from g-
14

---

Under review as a conference paper at ICLR 2023
B PROOFS FOR THE GENERAL CONTROL SETTING
In this section we assume that "Ye < 1, to avoid some of the additional issues for handling proper policies. The same strategies apply to the stochastic shortest path setting with % with additional assumptions.
Proposition 2. /Convergence of Value Iteration in Goal-Spacel Assuming that I is substochastic matrix, with E Re191 initialized to an arbitrary value and fixing Un (Sterminat) iteratively sweeping through all g E 9 with update
0 for all I, then
Ve (g)
max g'E
(g(9,9) + [(g vv:
convergences to fixed-poins
Proof. We can use the same approach typically used for value iteration. For any E 1R1 we can define the operator
(g)
max
('.9g)) + ('g.g'' "0g'))
o' n'EG:d(a.a'' )>0
First we can show that 8 is conttraaci.... Assume we are given any two vectors v1, U2 Notice that I(g. Te. because for problem setting the discount is either equal % equal to at termination. Then we have that for any E G
((Bvr)(o) (B)
(r(9,9') "(g, g'EG:dlo.'')>0 Fg(gg') + F(g ((g.g')e22 ('22)'))
max g'ECrd(g.g'>a
< max
(g,))')) + "(g.g')) (f>(a.9') (o.
of g'EGrdlg.'')>>
[gg. ('g.g')(m (vi (2
max of d'E
7elwi v2(g')
max
o' d'EG:i(g.s')>0
I Sello1 U/ loc
Since this is true for any g, it is true for the max over g. giving
1B - B 32 I TellV1 - Velloo
Because the operator 3a is contraction, since %o 1, know by the Banach Fixed-Point Theorem that the fixed-point exists and is unique.
Now we analyze the update to the main policy, that incorporates the subgoal value estimates into the bootstrap target. We assume we have finite number of state-action pairs with parameterized action-values q(: w) E R" represented as a vector with one entry per state-action pair. Value iteration to find 9- corresponds to updating with the Bellman optimality operator
(B))(s, r(s, a) + Σ P(s'ss, (s'))) max a'EA
g(s',a')
On each step, for the current q(: wr), if we assume the parameterized function class can represent Bqt, then we can reason about the iterations of W1, W2... obtain when minimizing distance between g(:; W+41) and Bq,, with
(8, a; W(+1) = (Byl: (s,)
Under function approximation, we do not simple update table of values, but get this equality by minimizing until we have zero Bellman error. Note that g" = Bq", by definition.
In this realizability regime, can reason about the iterates produced by value iteration. The convergence rate is dictated by %es as is well known, because
Bq
Byzlloc rellan 42|1o0
15

---

Under review as a conference paper at ICLR 2023
Specifically, if we assume [r(s, a)] S 7 "max then use the fact that 1) the maximal return is no def
greater than Gmax return we have that 1100 9- xl I 2G Therefore, we get that
Time and 2) for any initialization go no larger in magnitude than this maximal I-%
B q" a ||8 Bq S vell90 901100
and so after / iterations we have
11a--91ll = B 1xx 1ellat-1-0"11 S ~e 2-122-222111 loo... S 1i:000001l>>> = Gmax We can use the exact same strategy to show convergence of value iteration, under our subgoal-value bootstrapping update. Let rsab a) del E. P(s'|s, a a))uusss') (s'), assuming Ueub S - [-Gmax, Gmax] is given, fixed function. Then the modified Bellman optimality operator is
(s, a) del r(s,a) + (r,ab(s,
B) Σ P(s')ss (oe(s,,)((s) max maxa(s'sse g(s',a')
(10)
Proposition 3 (Convergence rate of tabular value iteration under subgoal bootstrapping). The fixed
point g33 8 933 exists and is unique. Further, for and the corresponding wo, initialized such that (90(s, a; wo)l < Gmas the value iteration update with subgoal bootstrapping qe -- 1 for t t= 1,2,... satisfies
l1q. 119lo S S11 ~ Tmax + 3Gmax
(1 BYYY
Proof. First we can show that 8 is 76(1 conttraattn Assume we are given any two vectors ς1 Notice that (s) S Ye. because for our problem setting it is either equal to Yo or equal to zero termination. Then we have that for any (s, a)
((, a) ( as)
[[1 3)
Σ
s P(s'
P(s'
a))
max 9i (s',
maxq d')ll
d'EA
d'EA
(1 By%e Σ
P(s'l al)ax (s', d')
-max a')ll
a'EA
d'EA
$ (1 8)r, Σ
P(s (s, max (a a²) (2' d')l
I (1 B)% Σ P(s'|s,
lni(s d') ge(s', d')l
max s'ES
$ (1 5he Σ P(s'ls, a))l - 921lo0
= (1 B) 1q1 - 92
Since this is true for any (s, a). it is true for the max, giving
| 1
42 lo I r)lll1 92lloo
Because the operator is a contraction, since (1 B)7 1, we know by the Banach Fixed-Pon Point Theorem that the fixed-point exists and unique.
Now we can also use contraction property for the convergence rate. Notice first that we can consider F(s, a) der r(s, a) + Braab (s, a) as the new reward, with maximum value Tmax + BG Further, the new discount is (1 - B)Te. Consequently, the maximal return r 1-(1-D)Te
|/ 02 | 4t-1 13llo <1 3)relle--1 8" 1xx......... S (1 - -9)--o00000 101
< (1 - 3) Tmmx + 3.mmxx
This rate is dominated by ((1 - 3)mr)', and for near gives much faster convergence than 3 = O. We can determine after how many iteration this term overcomes the increase in the upper bound on the return. In other words, we want to know how big needs to be get
3G
(1 =/ Tmax (1 3)7c
< Gmu.. mux.
16

---

Under review as a conference paper at ICLR 2023
Rearranging terms, get that this is true for
mmxx + 3.G max
1
> log
/log 1-3)
mmax
(1
33%))
For example if mmax = 1, % = 0.99 and _ 0.5, then we have that > 1.56. we have that
mmax 10, Te 0.99 and 0.5, then get that 2 5. If we have that Tmax 1, Y 0.99 and
B = 0.1, then we get that 2 22.
C LEARNING THE SUBGOAL MODELS AND CORRESPONDING OPTION POLICIES
Now we need way to learn the models, (s, g) and g)s.g) These can both be represented as General Value Functions (GVFs) (Sutton al., 2011), and we leverage this form use standard algorithms in reinforcement learning to learn them. We start by assuming that we have Ty and discuss learning it after understanding learning these models.
C.I MODEL LEARNING
The data is generated applicy-according to some behavior rather than from Tg. We can either use importance sampling or we can learn the action-value variants of these models to avoid importance sampling. We describe both options here, but in our experiments using the action-value variant since it avoids importance sampling and the need have the distribution over actions under behavior b.
Model Update using Importance Sampling We can update (- with an importance-sanee sampled temporal difference (TD) learning update ptó, (r, where Pt
(o(a)S)) and
b(a S.)
8, R&+1 + 7g.
(S,(
The discount model [(s, g) can be learned similarly, because it is also GVF with cumulant mm(S+1::)7t.. and discount Tg.4+1- The TD update is P:O. where
6f m( 9441 + 1g,
I(S..9)
All of the above updates can be done using any off-policy GVF algorithm, including those using clipping of IS ratios and gradient-based methods, and include replay.
Model Update without Importance Sampling Overloading notation, let define the action-value variants ry (8, a, g) and [8,, (....g). We get similar updates to above, now redefining
8 = Re+1 + 79.441,((441, Ty (S++1). - r., (S, Ar.
and using update & Vr, (S,, A,, .). For I we have
of = m g) 7++1 Jast1 [( (S. r(S,, At.g)
We then define r., (s, dal r- (s, (s).)) and l'(s,) def r(s, (s),g) as deterministic functions of these learned functions.
Restricting the Model Update to Relevant States Recall, however, that we need only query these models where d(s,g) g) > We can focus our function approximation resources on those states. This idea has previously been introduced with an interest weighting for GVFs (Sutton et al., 2016), with connections made between interest and initiation sets (White, 2017). For large state space with many subgoals, using goal-space planning significantly expands the models that need to be learned, especially we learn one model per subgoal. Even if we learn a model that generalizes across subgoal vectors, likely such a models would be hard to learn, and constraining what we learn about with d(s,, g) is likely key for practical performance.
requiring that model to know lot: values from all states to all subgoals. It is
17

---

Under review as a conference paper at ICLR 2023
The modification to the update is simple: simply do not update rs, (s)g) in states where d(s, 9) = 0.3 For the action-value variant, we do not update for state-action pairs (8, a) where d(s, g) = 0 and (s) # a. The model will only ever be queried in (s, a) where d(s, g(s = 1 and
(5))) =
Learning the relevance model d We assume in this work that we simply have d(s.g). but we can at least consider ways that we could learn it. One approach is to attempt to learn T for each g, to determine which are pertinent. Those with I'(s.gg .) closer to zero can have d(ss, g) = O. In fact, such an approach was taken for discovering options (Khetarpal et al., 2020), where both options and such a relevance function are learned jointly. For us, they could also be learned jointly, where larger set of goals start with d(ss, g) = 1. then if (s. g) remains small, then these may be switched to d(s, g) = 0 and they will stop being learned in the model updates.
Learning the models F, I' from ry, r. The strategy involves updating towards the state-to-subgoal models, whenever a state corresponds to subgoal. In other words, for a given s, if m(s, g) = 1. then for a given g' (or iterating through all of them), we can update Fy using
models Finally, we need to extract the
(r,(5, -
and update I't using
(I(s, Vi(
Note that these updates are not guaranteed to uniformly weight the states where m(s,g) 1. Instead, the implicit weighting is based on sampling s, such as through which states are visited and in the replay buffer. We do not attempt to correct this skew, as mentioned in the main body, we presume that this bias is minimal. An important next step is to better understand if this lack of reweighting causes convergence issues, and how to modify the algorithm to account for a potentially changing state visitation.
C.2 A GENERAL ALGORITIM FOR LEARNING OPTION POLICIES
Finally, we need to learn the option policies Tg. In the simplest case, it is enough to learn Tg that makes ri (s. 9) maximal for every relevant 8 (i.e., d(s,g) > 0). We can learn the action-value variant (s, a, 9) using Q-learning update, and set T. (s)s) = argmax F'y (s. a. g). where we overloaded the definition of ry.. We can then extract r. (5.g) = max.E (s, a, g). to use in all the above updates and in planning. In own Pinball Experiment, this strategy is sufficient for learning Tg-
More generally, however, this approach may be ineffective because maximizing environment reward may be at odds with reaching the subgoal in reasonable number of steps (or all). For example, in environments where the reward is always positive, maximizing environment reward might encourage the option policy not terminate.* 4 However, return along the way to g. For example, if there is a lava pit along the way to goal, even if going through the lava pit is the shortest path, we want the learned option to get to the goal by going around the lava pit. We therefore want to be reward-respecting as introduced for reward rwsrr-respecctig subtasks (Sutton et al., 2022), but also ensure termination.
do want Ty to reach g. while also obtaining the best
We can consider spectrum of option policies that range from the policy that reaches the goal as fast as possible to one that focuses on environment reward. We can specify new reward for
MMore generally, we might consider using emphatic weightings (Sutton et al., 2016) that allow to incorporate such interest weightings d(s Ks,g). without suffering from bootstrapping off of inaccurate values in states where d(s,, g) = O. Incorporating this algorithm would likely benefit the whole system, but we keep things simpler for now and stick with a typical TD update.
'It is not always the case that positive rewards result in option policies that do not terminate. If there is large, positive reward at the subgoal in the environment, Even if all rewards are positive, if ye < and there larger positive reward at the subgoal than in other nearby states, then the return is higher when reaching this subgoal sooner, since that reward is not discounted as many steps. This outcome is less nuanced for negative reward. If the rewards are always negative, on the other hand, then the option policy will terminate, trying to find the path with the hest (but still negative) return.
18

---

Under review as a conference paper at ICLR 2023
learning the option: Ru+1 cR + (1 (1-c)(-11) When O, we have a cost-to-goal problem, where the learned option policy should find the shortest path to the goal, regardless of reward along the way. When in g. We can start by learning the option policy that takes the shortest path with e = 0, and the corresponding r- (8, g): ((s,g) 9). The constant can be increased until Fy stops going to the goal, or until the discounted probability [(ss, g) drops below a specified threshold.
1. the option policy focuses on environment reward, but may not terminate
Even without a well-specified c, the values under the option policy can still be informative. For example, it might indicate that it is difficult or dangerous to attempt to reach goal. For this work, we propose simple default, where we fix c 0.5. Adaptive approaches, such as the idea described above, are left to future work.
The resulting algorithm learn Fg involves learning a separate value function for these rewards. We can learn action- values (or a parameterized policy) using the above reward. For example, we can learn policy with the Q-learning update action-values
cRe+1 + gg.+1 maxq((S+:) ((xx,, ( (q(S).A4.9)
Then we can set n be the greedy policy, (s(s) argmax ((s.a.g).
C.3 PSEUDOCODE PUTTING IT ALL TOGETHER
We summarize the above updates in pseudocode, specifying explicit parameters and how they are updated. The algorithm is summarized in Algorithm I, with a diagram in Figure 4. An online update is used for the action-values for the main policy, without replay. All background computation is used for model learning using a replay buffer and for planning with those models. The pseudocode assumes small set of subgoals, and is for episodic problems. We provide extensions to other settings in Appendix C.4, including using a Double DQN update for the policy update. We also discuss in in-depth differences existing related ideas, including landmark states, UVFAs, and Goal-conditioned RL in Appendix D.
Note that overload the definitions of the subgoal models. We learn action-value variants (s, a, g; 8"), with parameters 8", to avoid importance sampling corrections. We learn the option-policy using action-values q(s, a; (7)) with parameters 0" and so query the policy using (s( 8%) = argmax Î(s, g; 8*). The policy Tg is not directly learned, but rather defined by q. Similarly, we do not directly learn rs,(s,g): instead, is defined by rs, a, g; 0*). Specif- (0",0", (*)), we set (s, 0) def (s,(s, To (s; 0T), ). gi 0r) and g; 0) I'(s, (s; (T), g; 0F) We query these derived functions in the pseudocode.
ically, for model parameters 0
Finally, we assume access to a given set subgoals. But there have been several natural ideas already proposed for option discovery, that nicely apply in our more constrained setting. One idea to use subgoals that are often visited by the agent (Stolle & Precup. 2002). Such a simple idea is likely reasonable starting point to make GSP algorithm that learns everything from scratch, including subgoals. Other approaches have used bottleneck states (McGovern & Barto, 2001).
Algorithm 1 Goal-Space Planning for Episodic Problems
Assume given subgoals G and relevance function
Initialize table e E IR (91, main policy w, model parameters 0 = (00,0F (0,0%),0 (ōr,0r) Sample initial state so from the environment for t E 0, 2, do
Take action o using g (c.g., e-greedy), observe se+1, 7441: ModelUppatee( at, S141,T441, 7+11) Planning()
MainPoli htwpllcccppppeeeeecco ar 8841, Te41, 7141)
19

---

Under review as a conference paper at ICLR 2023
Algorithm 2 2 Sborttmmhhhaanoooooooouoeesssaar
Usuh < (a ()s,):))))(((())))))))
4-1 r + +7 max q(s', d'; w) ((s,a;))
w f- w W
Algorithm 3 Pl Planning()
for iterations, for each E G do ü(g) & 7x. "(
Algorithm 4 Mode Mode (s
Add new transition (s, a, s',r, to buffer B
for g' E G. for multiple transitions (s, a, s', sampled from B do
Y - 7(1 mmss.g'))
// U Update option policy
5" 1 - Ti A q(s', d'
+
d': g(s, a, g':
8r + 8 + 8* Vg(s, a, g.;';")))
Update reward model and discount model
a' Ti (s';
8 t r + Tg "''.a''''"'" a,, 8 + m(s', ()) + Th
a', "s', -'
Or + Or + a 8 (s, g';','';00)
OF + or a (T(s,, V u';; 0²:
Update goal-to-goal models using state-to-goal models for each g such that mls.g) > 0 do
0" Or ā" (r, (';) :g (f (r) Ør - Qr + āt (T(s [g. VT)
C.4 EXTENDING GSP TO DEEP RL
It is simple to extend the above pseudocode for the main policy update and the option policy update to use Double DQN (Van Hasselt et al., 2016) updates with neural networks. The changes from the above pseudocode using polyak averaging to interpolate between the target network and the main network's 's weights, 3) changing the one-step bootstrap target the DDQN equivalent, 4) adding a replay buffer for learning the main policy, and 5) changing the update from using single sample to using batch update. Because the number of subgoals is discrete, the equations for learning 0" and ør does not change. We summarize these changes for learning the main policy in Algorithm 5 and for learning subgoal models in Algorithm 6.
1) the use of target network to stabilize learning with neural networks, 2)
Algorithm 5 StaimoollicyDDDapppatte.... 8',7))
Add experience (s, a, 8', ,,, r,,)) 7) to replay buffer Dmain for Mmain mini-batches do Sample batch Bmain = a, (s,,,, 5',)) from Dmain
(s) maxyeG
(8, + ((s,;;0)ū(0
Yrr s. + BBrbub 71 - (s' max, q(s', w)) Wtarget) (r. (', q(s.a;)))
L Bmain Eis.arre (ejer Bmain
w + aV Wtarget & pw + (1 P)Wtarge!
20

---

Under review as a conference paper at ICLR 2023
Algorithm 6 3 ass,,,,,,,
Add new transition (8, a, s', 7) to buffer Dmndde
for g' E G do for
Remodel mini-batches do
Sample batch Bmodel {(s, ,,',,, from model
Ng' + 711 m(s',g')
// Update option policy
a' + argmax q(s' ((8',c d',''00"))
6" (s, a, 8 1,,) + 2(( ( 1) + Yg ((6,, ,, g farr)) - g(8 a, g': 0*)
0" + 0 + a Vgn Bmodel Eisans' m) B Bmodee (8 (8, a, s 7))2
Biarg f Pmmodet + -Pmoded 0oarg
// Uppate reward model and discount model
(7 8" (s. S,a.ar a.r, s', 7) f- r -o' (7, s') Jr, (s', a' g': targ) -r a':
8 (s. a. s .?)) ) + mmmmssg))) + Y (7, s. s') a', g::'" targ) I(s, a. g':
or t or a'V a'Voo [Bmodet]
(s..,,, 7)) E)EBmadd (6
gT f oF - a a'V Vooor or [Bmodal
I
E ((s,a. () Bmoded (
O" targ & Pmodetl" + Pmodes 0 targ
OF targ < Ponodd + (1
Pmodel )0t targ
// Update goal-to-goal models using state-to-got models same as prior pseudocode.
C.5 OPTIMIZATIONS FOR GSP USING FIXED MODELS
is possible to reduce computation cost of GSP when learning with fixed model. When the subgoal models are fixed, Usub for experience sample does not change time all components that used to calculate Usub are fixed. This means that the agent can calculate Usub when it first receives the experience sample and save in the buffer, and use the same calculated Usah whenever this sample is used for updating the main policy. When doing so, Usub only needs to be calculated once per sample experienced, instead of with every update. This is beneficial when training neural networks, where each sample is often used multiple times to update network weights.
An additional optimization possible on top of caching of Usub in the replay buffer that we can batch the calculation of Usub for multiple samples together, which can be more efficient than calculating uuub for single sample every step. To do this, we create an intermediate buffer that stores up to some number of samples. When the agent experiences transition, it adds the sample to this intermediate buffer rather than the main buffer. When this buffer full, the agent calculates Usab for all samples in this buffer at once and adds the samples alongside uau to the main buffer. This intermediate buffer is then emptied and added to again every step. We set the maximum size for the intermediate buffer to 1024 in our experiments.
D CONNECTIONS TO UVFAS AND GOAL-CONDITIONED RL
There is large and growing literature on goal-conditioned RL (GCRL). This is problem setting where the aim learn policy π (Ta) s. g) that can be (zero-shot) conditioned on different possible goals. The agent learns for given set of goals, with the assumption that at the start of each episode the goal state explicitly given to the agent. After this training phase, the policy should generalize to previously unseen goals. Naturally, this idea has particularly been applied to navigation, having the agent learn to navigate to different states (goals) in the environment. Many GCRL approaches leverage UVFAs (Schaul et al., 2015).
This setting bears a strong resemblance to what we do in this work, but is notably different. Our models can be seen as goal-conditioned models part of the solution for planning in the general RL setting. GCRL, on the other hand, is a problem setting. Many approaches do not consider planning, but instead focus effectively learning the goal-conditioned value functions or policies.
21

---

Under review as a conference paper at ICLR 2023
There is more work, however, using landmark states and planning, for GCRL. In addition to the goal given for GCRL, the landmark states can be treated as interim subgoals and UVFA models learned for these well (Huang et al., 2019). Planning is done between landmarks, using graph-based search. The policy is set to reach the nearest goal (using action-values with cost-to-goal rewards of -1 per step) and learned distance functions between states and goals and between goals. These models like our reward and discount models, but tailored to navigation and distances.
The idea of learning models that immediately apply to new subtasks, using successor features, is like GCRL but goes beyond navigation. The option keyboard involves encoding options (or policies) as vectors that describe the corresponding (pseudo) reward (Barreto al., 2019). This work has been expanded more recently, using successor features (Barreto et al., 2020). New policies can then be easily obtained for new reward functions, by linearly combining the (basis) vectors for the already learned options. No planning is involved in this work, beyond one-step decision-time choice amongst options.
E ADDITIONAL DETAILS ON LEARNING SUBGOAL MODELS
This section describes implementation details for learning subgoal models in the PinBall environment and errors observed in the learned models.
To ensure that we provide sufficient variety of data to learn the model accurately, when learning the subgoal models, the agent is randomly initialized in the environment at a valid state, ran in the environment for 20 steps with random policy, then randomly reset again. To ensure that the agent gets sufficient experience near goal states, we initialize the agent, with a 0.01 probability, at states where m(s, g) = 1 for any g with added jitter sampled from U--0.01, 0.01) for each feature. The model is trained for 300k steps in this data gathering regime.
We restrict model update to relevant states in our experiments. Because the only relevant experience for learning r,y and are samples where d(s,, g) > O, we maintain a separate buffer for each subgoal g for learning T. (s, (s.9) and l(s,g) such that all experience within that buffer are relevant. We require 10k samples in the buffer of each subgoal before learning for the corresponding ryy and I begins, so that mini-batches
always drawn from sufficiently diverse set of samples.
Similarly, sample is only relevant for updating I and F., if ml.. g) 0 for some g, but this might not be true for samples stored in the buffers for learning T and ry. To be able to obtain a batch of samples where all samples are relevant for learning [ and i.,, the agent uses another buffer that exclusively stores samples where m(s, g) > 0 to learn I' and 87.
We mentioned in Appendix C. that we take the simple approach to restricting model updates to states where d(s.g) g) = 1. However, this means an update could bootstrap off inaccurate estimates when learning from a sample (s, a, r, 8') if d(ss, g) > 0 but d(s',g) g) = O. In PinBall, this occurs when the agent starts within the relevance area for subgoal but taking action moves the agent outside of it. We attempt to alleviate this issue in practice by changing the estimation target for those state-action pairs to be the minimum possible target in the environment. Because co-learn the option policy with r. (s, a, g), we set this minimum value to m-rrmin If the network can learn this target well, then the learned option policy will not leave the relevance area.
We also address the issue that for some fixed d, it is possible that not all states where d(s, g) 0 could reach the subgoal. This can negatively affect the quality of Usub as our algorithm assumes that goal g is reachable from state s via the option policy if d(s.g) g) > O. While this source of error did not seem to affect GSP in our experiments, it might be important in other environments, so we describe the modification to address this problem here. From these states, the agent should not consider these subgoals when doing background planning (g' is not reachable from g despite d(g. g') = 1) and projection (g' is not reachable from despite d(s,
1). We check for these states by seeing if the learned T(s. g) is near O, which indicates that it is either very difficult or impossible to reach from s. For states with I(s, g) very near O, we can set d(s,g) 0 for the purpose of background planning and projection, but not for learning (ss. g) as it might be initialized to a low value. In our experiments, we set this threshold to O.
22

---

Under review as a conference paper at ICLR 2023
Absolute Error
0.6
I(s,g)
0.4
0.0
200
150
(5,
100
Figure 11: A heatmap of the absolute error of I and r-y for two different subgoal models learned at various (Jr, y)- While the absolute error from states near subgoals can be quite low, they increase substantially as the state gets further away. White indicates that d(s, 0.
E. ERROR OF LEARNED SUBGOAL MODELS
To better understand the accuracy of our learned subgoal models, we performed roll-outs of the learned option policy different (x.y) locations (with 0 velocity) across the environment and compared true T4 and I with the estimated values. Figure 11 shows a heatmap of the absolute error of the model compared to the ground truth, with the mapping colors on the right. The models learned tend to be more accurate closer the goal, and less accurate further away. The absolute error of T can be as low as 0.01 close to the goal, but increase to 0.2 and higher further away. Similarly, the absolute error for r.y can be low below 10 near goals, but can increase While the magnitudes of errors are not unreasonable, they are also not very near zero. This results is encouraging that inaccuracies in the model do not prevent useful planning.
100 further away.
F ADDITIONAL EXPERIMENT DETAILS
This section provides additional details for the PinBall environment, the various hyperparameters used for DDQN and GSP, and the hyperparameters sweeps performed. The experiments described in the main body, along with the hyperparameter sweeps, used approximately 10.7 CPU days on an Apple MI chip.
The pinball configuration that we used is based on the "slightly harder configuration" found http: ///rrrrl.a./ cs brown. wwwpppinbaalii.eeeeee The Python implementation of PinBall was taken from https: //ggt/ggtttt////// cww/ htch/mmaraac wawaaak/pyyttoonaa.
which was released under the GPL- 3.0 license. We have modified the environment to support additional features such as changing terminations, visualizing subgoals, and various bug fixes.
Network Architecture We used neural networks for learning the main policy, H, and Ty- For experiment 1, we used a neural network with hidden layers [256, 256, 128, 128, 64, 64] for the main policy and [256, 256, 128, 128, 64, 64, 32, 32] for I' and Ty. For experiment 2, used neural network with hidden layers [128, 128, 64, 64] for the main policy and [128, 128, 128, 128, 64, 64) for I and r,,. We used ReLU activation function for each layer aside from the output layer. The network's bias weights are initialized to 0.001 and other weights were initialized using He uniform initialization (He al., 2015). Each network output vector of length 5, for each action.
23

---

Under review as a conference paper at ICLR 2023
F.1 EXPERIMENT HYPERPARAMETERS
For both experiments, we used the Adam optimizer for training both the main policy and the subgoal models. We used the default hyperparameters for Adam except the step-size (bj = 0.9, b2 0.999, c <= le 1e The main policy was trained with 4 mini-batches per step with batch size of 16, while the subgoal models were trained with mini-batch per step with the same batch size. We used e-greedy exploration strategy, with fixed to E = 0.1 in our experiments.
For experiment 1, 0.99, a-' = a² = af' 5e-1, and Pmodel = 0.4. For experiment 2, 7 0.95, a = a' = a" = 1e and Pmodel = 0.1. We selected the learning rate for Adam and the polyak averaging rate o for updating the main policy in each experiment using the methodology described in the section below.
F.2 HYPERPARAMETER SWEEP METHODOLOGY
For experiment 1, we swept the baseline DDQN algorithm for polyak averaging rate p E [0.0125, 0.025, 0.05, 0.1] and learning rate [le 5e 3,3e 3.-4 that p = 0.025 and learning rate of 5e -4 had the highest average reward rate in our sweep and used them when running both DDQN and GSP across seeds in the experiment.
across 4 seeds. We found 3,1-,,1-- f]
For experiment 2, we swept DDQN for polyak averaging rate p E [1.0, 0.8, and learning rate in [1e-2, 2e-2,,00 5e-3, 33 1e 11e5),e-1 1] for seeds. We find that p = 0.05 and learning rate of le-3 had the highest average reward rate out of all configurations swept and used these hyperparameters for all DDQN runs in the experiment. For GSP, we used p = 0.8 and learning rate of le
0.05, 0.025]
G COMPARING GSP TO OTHER DYNA ALTERNATIVES
In this section, we compare GSP against other basic background planning algorithms. Namely, we compare against DDQNx2, a DDQN agent that is given double the amount of computational budget per step compared to our baseline algorithm, and Dyna with options (Dyno), natural alternative to use option model for background planning.
As mentioned in Section 4, DDQN can be viewed as a background planning algorithm when the replay buffer is viewed as a non-parametric model. Providing DDQN with double the number of mini-batch updates attempts to answer the question of what if GSP's background planning resources was instead dedicated to additional one-step updates. Note that in this experiment, our DDQNx2 implementation took 50% additional wall-clock time run when compared to our GSP implementation.
Dyna with options (Dyno) is a basic algorithm that incorporates option models into Dyna such that the agent learns about both action values and option values Q : S x AU O. Dyno's 's behaviour policy then includes both actions and options. an option πy is selected when taking a greedy action according Q, then the first action given by my is executed. The model in Dyna needs include option models, which allows the agent to reason about accumulated rewards under an option, and outcome states after executing an option. Otherwise, the framework is identical Dyna. is simple, elegant extension on Dyna that allows for planning with temporal abstraction. However, this approach has several limitations. One limitation is that as we include new options-more abstraction-our value function needs to reason over more actions. Our proposed algorithm, GSP, allows the agent to obtain the benefits of abstraction, without modifying the form of the policy. Another limitation is that the model in Dyna is the standard state-to- tate-tt--tatte model. Though Dyna with options has not been extended to function approximation - somewhat surprisingly - the natural extension suffers from similar problems of model errors and the use of expectation models standard Dyna.
We compare DDQNX2, Dyno, and GSP in the simple PinBall environment. For Dyno, we use the same nubgoal-conditione models pre-trained for GSP as options models and set the predicted next state of each option to (Ig. By. 0, 0). We found Dyna with options difficult to get working. Instead, used modified version that only plans over options. This avoids learning and using primitive action models. We see in Figure 12 that this modified variant actually outperformed DDQN initially, but leveled off a suboptimal level of performance and overall learned slower than GSP. We also
24

---

Under review as a conference paper at ICLR 2023
GSP (6 = 0.1)
150
L
Reward Rate Averaged over 30 Runs
100
Dyna Options
DDQN
50
DDQNx2
500
1000
1500
2000
2500
Steps (x100)
Figure 12: (left) The simple PinBall environment. (right) The performance of Dyna with options (Dyno), DDQNx2, DDQN, and GSP (3 = 0.1) in the simple PinBall environment. Dyno learned slower than GSP and converged to lower performance point when compared to GSP. DDQNx2, despite requiring an additional 50% wall-clock time when compared to GSP, learned at a slower rate but converged the same optimal peformance.
find that DDQNx2 performed better than DDQN, but was unable to perform better than GSP despite requiring more wall-clock time, highlighting GSP's computational efficiency.
H EXPERIMENTS WITH LUNAR LANDER
To see how GSP can be applied to other problems, we ran GSP in the Lunar Lander environment (Brockman et al., 2016). The environment specification follow OpenAl Gym's Luna aaaner-v2 environment. We provide the agent with 9 subgoals, with one terminal subgoal when the agent lands safely on the landing pad and the rest of the subgoals laid throughout the environment at different (x.y) locations in an arrow-like fashionx. As the (x.y) coordinates are continuous, we take similar approach of defining small region around each coordinate and define a larger initiation area around each subgoal. We show the non-terminal subgoals in Figure 13. We compare GSP, DDQN, DDQNx4 (DDQN with 4x the amount of planning steps), and approximate LAVI. We evaluated GSP with 3 = 0.01 as we found it to be the best performing [0.001, 0.01, 0.05] in our experiments.
for subgoal termination,
We see in Figure 13 that GSP outperforms DDQN, DDQNx4, and approximate LAVI. Overall, we found that nubgoal-conditoone models are more difficult to learn in Lunar Lander, with the learned reward models and discount model having an average absolute error of around and 0.1 respectively from 200 monte-carlo rollouts of the policy the environment. This aligns with the poor performance of approximate LAVI and the lower value of B that was found to be good for GSP. Surprisingly, DDQNx4 performed worse than GSP and DDQN despite performing times the number of batch updates that DDQN performs per step. We hypothesize that this is because the increased number of updates causes the agent to fit to a suboptimal solution based on insufficient data, thus making the rate of improvement slower.
I INVESTIGATING GSP WITH DIFFERENT BETA
In subgoal-vaie value bootstrapping (Equation 4), the hyperparameter 3 represents the tradeoff between fully using the quickly updated but approximate subgoal values (s) and the standard bootstrap target. We investigate the impact of /3 in the harder pinball environment shown in Figure 5. We ran GSP with 3 E [0.0, 1e-3, 0.1, 0.5, 1.0]. Note that 3 = 0.0 is equivalent to DDQN, and 8 = 1.0 is equivalent to approximate LAVI. We similar fast initial learning, but converges to lower final performance. For 3 = 1e very close to 0, we see that performance more like DDQN. But even for such small / we get improvements.
in Figure 14 that with
0.5 and 3 1.0, GSP gets
25

---

Under review as a conference paper at ICLR 2023
GSP (B = 0.01)
200
DDQN
Average return (Past 100 episodes)
DDQNx4
100
Approximate LAVI
200
0.75
Steps (x1e6)
Figure 13: (left) The locations of non-terminal subgoals in Lunar Lander, shown with light green circles. (right) Mean return over 30 independent runs of the past 100 epsides of GSP, DDQN, DDQNx4, and approximate LAVI in Lunar Lander. GSP learned more quickly than DDQN and DDQNx4 and converged to the same level of performance. The performance of approximate LAVI quickly plateaued as was unable to overcome the suboptimality the learned subgoal models.
B
= 0.1
50
40
Reward
0.0
Rate
30
Averaged
20
β 1.0
over
30 Runs
10
B = 1e-3
0
0 500
1000
1500
2000 2500
Steps (x100)
Figure 14: Performance in the harder PinBall environment for GSP with variety of 3, with the standard error shown. Even just increasing to 3 from to 0.1 allows GSP makes learn much faster than DDQN by leveraging learned subgoal values. Once 3 is at 1, where it fully bootstraps off of potentially suboptimal subgoal values, GSP still learns quickly but arrives at a suboptimal policy.
26


Reviews:
[{"review_id": "sm8ykUOUSYl", "reviewer": "Reviewer_sJBg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper looks at how one could improve the performance of RL agents by leveraging planning at the level of subgoals. The authors argue that by restricting planning at a higher level of abstraction the method side-steps many of the problems associated with traditional model-based planning approaches, like inaccuracy of the learned model. Specifically they construct a goal-space MDP that reflects transitions in the terms of subgoals and use value functions for this abstract MDP to bootstrap the learning of the agent operating at the more concrete level.", "summary_of_the_review": "While I think the idea and the direction is interesting, the current version of the paper currently falls in the borderline region of acceptance for me. As mentioned, I have some concerns about the soundness of some of the assumptions and methods. I also feel the experiments could also be improved.", "strength_and_weaknesses": "First off, to the best of my knowledge the methods discussed in the paper are unique and touch upon many issues usually discussed in relation to planning with learned models. The closest related work I know of are in the realm of state-aggregation based abstraction scenarios where similar bi-level planning methods have been discussed(cf. Aggregation chapter in [1] or more generally check [2] for state abstraction). Connected ideas have also been studied in the context of temporal abstraction in relation to hierarchical planning (more generally or more specifically as in the context of task and motion planning), but their application in the context of RL I believe is novel. The results also seem to indicate that the method does provide some advantage over some of the current approaches.\n\nTo me the biggest issue with the proposed approach is the assumption that the subgoals are given. Currently the main paper simply includes a line that identification of the subgoals and initiation set are part of the subgoal discovery process. However, I didn’t see any discussion on what form the process takes. I am assuming the subgoal discovery process can’t be trivial. After all, in long horizon sparse reward problem settings, you have to discover enough subgoals that it could lead you to the eventual high reward states. Similarly, applying this in the context of non-stationarity, aren’t you assuming that the subgoals already cover state spaces relevant to the change. \n\nAnother point that was unclear to me was about the use of beta itself. If the purpose of not relying simply on the v_sub is to avoid following suboptimal policy, shouldn’t the value of beta be reduced over time. Because if your target value still includes a component that comes from v_sub, couldn’t that result in suboptimal policies?\n\nIn terms of evaluation, while the paper does present a few different experiments, I don’t believe there are any results that clearly shows that the current method provides a clear advantage over baseline when both systems are starting from scratch for standard setting. Experiment 1 is the result that comes closest to evaluating this, however the authors chose not to include the effort needed for model learning in that evaluation.  I understand that the experiment is framed in terms of a pre-learned model, but that has not been the focus of the paper. Throughout the paper, the primary focus was on a standard RL problem where the system starts without any knowledge of the environment and identifies a policy. Also given the fact that the methods were compared in terms of number of steps, this would have been an easy comparison to make.\n\n[1] Bertsekas, Dimitri. Reinforcement learning and optimal control. Athena Scientific, 2019.\n\n[2] Li, Lihong, Thomas J. Walsh, and Michael L. Littman. \"Towards a Unified Theory of State Abstraction for MDPs.\" AI&M. 2006.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_zVf8pLj9b", "reviewer": "Reviewer_bsyJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies fast background planning, based on an abstract model over subgoals. The subgoal space is predefined, and the authors then learn expected return and discount models between subgoals, which are used in a tabular dynamic programming procedure. The resulting value function is added to the bootstrapping of the lower-level RL agent to speed up learning. Empirical results on the Pinball environment show that learning is indeed faster. ", "summary_of_the_review": "This paper has its pros and cons. I think it is technically sound and well written, and the method works. However, my biggest issue is that the research question is a bit incremental, and the results therefore not too surprising (the method has much prior knowledge over the DDQN baseline). I am also a bit worried about the experimental evaluation on the PinBall environment only. I will therefore give a borderline vote. ", "strength_and_weaknesses": "Strenghts:\n\n* The paper is well written. \n* The topic (planning over landmarks) is relevant. \n* The paper is technically sound. \n\nWeaknesses: \n\n* The contribution is a bit incremental. The authors essentially 1) prespecify a set of subgoals, 2) prespecify the relation between subgoals and the underlying state space, and 3) pretrain a set of models to reach between these subgoals. The pretrained value function on the subgoals is then used as part of the bootstrap target in a downstream RL agent. This agent manages to outperform the DDQN baseline, but this is not too surprising given the extra amount of prior knowledge and pretraining given to the agent. I think the comparison would be more fair if the agent at least had to learn the value function to move between subgoals on the fly (during training). \n* Experimental evidence does not include many environments. The main paper only contains one task: PinBall, of which two instantiations are tested. The appendix does contain a second environment (LunarLandar), which I would definitely move to the main paper. \n\nSmaller weaknesses: \n* In your nonstationarity experiments, you indicate that “when the world changes, the agent recognizes that it has changed, and resets all counts”. I do not get how this works. Do you mean you hardcoded this? That does not seem to be fair, as the original Dyna+ implementation did not do that either? \n* You say you “somewhat randomly selected subgoals across the PinBall environment”. What does this mean? Looking at the pictures, they seem to be rather evenly distributed, which seems crucial for your method to work well. I think you handpicked them with a little added noise right, which is fine, but then describe the actual procedure you followed. \n* p4: I think you never introduce d(s,g)? I therefore have trouble understanding what a ‘local model’ really means.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VHNX1CWQIX", "reviewer": "Reviewer_1SkJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes \"goal-space planning\", an approach to training a model-free policy that uses user-specified subgoal states to perform approximate longer-horizon bellman updates and thus accelerate learning. The central novelty of the approach is the \"subgoal-value bootstrapping\" update that balances updating the Q-function via a standard TD error and a TD error borne of values associated with navigation to the nearest subgoal and then motion between those subgoals until the goal can be reached. Results are shown on two variations of the \"Pinball\" environment originally proposed for option/skill-learning and in both the authors show improvements in convergence rate and competitive long-term performance; additional results appear in the appendix, including some on the Lunar Lander domain.", "summary_of_the_review": "Overall, the proposed approach is interesting and shows some limited improvements in the scenarios in which a user can fairly easily specify some well-chosen subgoals. I believe that the paper's main weaknesses stem from a lack of clarity and somewhat poor organization. The language in the main body of the paper can be streamlined to communicate the same message in fewer words, which will improve clarity. This additional space can be used to incorporate some of the important experiments that should not have been relegated to the appendix (see above). The paper should aim to make those changes and ensure that the discussion of the relocated experiments addresses my concerns about the general utility and performance of the approach.", "strength_and_weaknesses": "- [strength] The approach is novel and delivers on the promised improvements to learning speed for the given experimental setup. The theoretical discussion is also self-contained and fairly comprehensive and the appendix contains considerable detail.\n- [weakness] The choice of beta is a critical piece of the proposed work, as it trades off between targeting the (potentially suboptimal) value from the subgoal model and the otherwise slow-to-converge q-value. In general, the main body of the paper is somewhat lacking on results that show how this value was chosen. Appendix I has some results that show (for an experiment not included in the main body of the paper) how changing the value of beta impacts the rate of learning and asymptotic performance. I believe that the two baselines shown (DDQN and approximate LAVI) correspond to extreme values of beta, yet clarifying this point and including a more detailed analysis in the main body of the paper (not the abstract) would be useful.\n- [weakness] The paper is missing a discussion of LAVI and the novelty of the proposed approach with respect to LAVI. Since the paper is contrasting to an \"approximate LAVI\" baseline and LAVI seems the work most similar to the proposed method, a statement summarizing its contributions and also the novelty of the proposed work with respect to LAVI is an important detail.\n- [weakness] Critically, the experiments shown in the main body of the paper are quite limited, and exist in only a single relatively-simple Pinball environment. While there is some discussion in the appendix of results in the popular Lunar Lander domain, the impact of the proposed approach is somewhat limited. Regardless, seeing results on a different domain (e.g., the Lunar Lander) in the *main body* of the text is helpful for understanding how this work can be used in other domains; I believe that this results should be moved to be in the main text. Relatedly, there are some questions about the additional results included in the appendix that could use further scrutiny. In particular the DDQNx# results are a bit odd. The explanation of the poor performing DDQNx4 results for the Lunar Lander domain is reasonable, though the improvements for the DDQNx2 results in the simple pinball domain point to lack of computational effort as a potential source of performance limitations of the DDQN approach and improvements to the amount of computation is not the claimed central advantage of the approach; further discussion of this point would be helpful and additional analysis or prose to clarify the trade off between performance, computation, and learning rate would be a welcome addition to the paper (even if it only appears in the appendix).\n- [weakness] There is little to no discussion about how the subgoals should be chosen. The authors acknowledge that *learning* these subgoals is beyond the scope of the paper, yet the omission of a clear procedure to obtain these subgoals or a discussion of what makes for a \"well-specified\" set of subgoals is a notable omission from the paper. The paper would benefit from at least some cursory evaluation of how the results would change if the subgoals were changed; this is an important practical consideration for someone who may wish to build upon this approach.\n- [unsure, but clarity would be helpful] Could the authors clarify on what happens if the subgoals are chosen poorly? The motivation for Eq. (4) from Eq. (3) suggests that beta exists primarily to compensate for not-yet-converged values of v_sub and also allow for optimal plans that do not follow the subgoals. For the latter problem, would a `max` operator not be more suitable, in which the optimization objective would select max( q(s_t+1, a), v_sub ). It could avoid the need to tune the value of beta and if the subgoals were poorly chosen, it would avoid entirely a reliance on those values during optimization.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2qvYuZM6DX", "reviewer": "Reviewer_XCiE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes using a state abstractions defined as subgoals to improve efficiency by doing planning on the background while learning action-value estimates.\nGiven a set of subgoals, which is a many-to-one mapping of states to abstract states, the proposed method runs dynamic programming to plan in the abstract space. The current estimate of the subgoal value function is then included in the standard Q-learning update used in the original state space.\nThe results compare the proposed method to DDQN and Approx Lavi on the classic PinBall environment.", "summary_of_the_review": "An interesting paper tackling the use of state abstractions to improve planning efficiency.\nUnfortunately, the paper falls short in standing out in novelty, and the improvements shown in the experiment do not appear to be very significant.\nI think there is potential for this line of work, but in its current state there's quite a bit of room for improvement. ", "strength_and_weaknesses": "Strengths:\n- The paper proposes  an interesting approach to incorporate subgoals value estimates into Q-learning updates.\n- The paper was clearly written and it is easy to follow.\n\n\n\nWeakness:\n- The idea is not very novel, the proposed approach seems to be very similar to HPA* ( https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf ), where the planning approach is to create an abstraction of the original state space to plan quickly at the abstract level. Granted, this was done in the context of classical planning and path finding, but the main concept is similar.\n\n- I understand the paper states that the focus is to plan when subgoals are given, so how to identify the subgoals is not covered, but this is a crucial step for abstract planning to work. Where do those abstractions come from? Not having explored that question, limits the contribution of the paper quite a bit.\n\n\n- The results do not appear to be significant. Figure 5 shows that GSP achieves an average reward of approx. 50 and DDQN of approx 40. Based on the description of the problem, the agent received a reward of 10,000 when reaching the goal, and -5 for every time-step. This means that a return of 50 takes (10,000 - 50) / 5 = 1,990 steps, while a return of 40 takes (10,000 - 40) / 5 = 1,992 steps.\nIn fact, every increase in reward of 5 points is a reduction of 1 step on average, so at training step 1000  where there seems to be a large difference between GSP and DDQN (40 vs. 10), the difference in the number of steps to reach the goal is 6.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject