# Option Transfer and SMDP Abstraction with Successor Features

Dongge Han1 Sebastian Tschiatschek2
1University of Oxford
2University of Vienna, Faculty of Computer Science, Vienna, Austria
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Abstraction plays an important role in the generalisation of knowledge and
skills and is key to sample efficient learning. In this work, we study joint
temporal and state abstraction in reinforcement learning, where temporally-
extended actions in the form of options induce temporal abstractions, while
aggregation of similar states with respect to abstract options induces state
abstractions. Many existing abstraction schemes ignore the interplay of state
and temporal abstraction. Consequently, the considered option policies often
cannot be directly transferred to new environments due to changes in the state
space and transition dynamics. To address this issue, we propose a novel
abstraction scheme building on successor features. This includes an algorithm
for transferring abstract options across different environments and a state
abstraction mechanism that allows us to perform efficient planning with the
transferred options. 00footnotetext: The appendix to this paper is available
at https://hdg94.github.io/assets/img/abstractions_appendix.pdf.

##  1 Introduction

Reinforcement learning (RL) has recently shown many remarkable successes Mnih
et al. (2015); Silver et al. (2017). For efficient planning and learning in
complex, long-horizon RL problems, it is often useful to allow RL agents to
form different types and levels of abstraction Sutton et al. (1999); Li et al.
(2006). On the one hand, temporal abstraction allows the efficient
decomposition of complex problems into sub-problems. For example, the options
framework Sutton et al. (1999) enables agents to execute options, i.e.,
temporally-extended actions (e.g., _pick up the key_), representing a sequence
of primitive actions (e.g., _move forward_). On the other hand, state
abstraction Li et al. (2006); Abel et al. (2016) is a common approach for
forming abstract environment representations through aggregating similar
states into abstract states allowing for efficient planning.

In this paper we aim to combine the benefits of temporal and state
abstractions for enabling transfer and reuse of options across environments.
We build on the insight that environments with different dynamics and state
representations may share a similar abstract representation and address the
following question: How can we transfer learned options to new environments
and reuse them for efficient planning and exploration? This is a challenging
question because options are typically described by policies that are not
transferable across different environments due to different state
representations and transition dynamics. This issue is underlined by the fact
that abstract options (e.g., _open a door_) can often correspond to different
policies in different environments. To enable option transfer and reuse, we
propose an abstract option representation that can be shared across
environments. We then present algorithms that ground abstract options in new
environments. Finally, we define a state abstraction mechanism that reuses the
transferred options for efficient planning.

Concretely, to find a transferable abstract option representation, we propose
abstract successor options, which represent options through their successor
features (SF) Dayan (1993); Barreto et al. (2017). An SF of an option is the
vector of cumulative feature expectations of executing the option and thus can
act as an abstract sketch of the goals the option should achieve. By defining
shared features among the environments, the abstract successor options can be
transferred across environments. Abstract options then need to be grounded in
the unseen environments. One way, therefore, is to find a ground option policy
that maximises a reward defined as a weighted sum over the SF Barreto et al.
(2019). However, careful hand-crafting on the reward weights is needed to
produce an intended option’s behaviour due to interference between the
different feature components. Alternatively, we formulate option grounding as
a feature-matching problem where the feature expectations of the learned
option should match the abstract option. Under this formulation, we present
two algorithms (IRL-naive and IRL-batch) which perform option grounding
through inverse reinforcement learning (IRL). Our algorithms allow option
transfer and can be used for exploration in environments with unknown
dynamics. Finally, to enable efficient planning and reuse of the abstract
options, we propose successor homomorphism, a state abstraction mechanism that
produces abstract environment models by incorporating temporal and state
abstraction via abstract successor options. We demonstrate that the abstract
models enable efficient planning and yield near-optimal performance in unseen
environments.

##  2 Background

##### Markov Decision Processes (MDP).

We model an agent’s decision making process as an MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,r,\gamma\rangle$, where
$\mathcal{S}$ is a set of states the environment the agent is interacting with
can be in, $\mathcal{A}$ is a set of actions the agent can take,
$P\colon\mathcal{S}\times\mathcal{A}\rightarrow[0,1]^{|\mathcal{S}|}$ is a
transition kernel describing transitions between states of the MDP upon taking
actions, $r\colon\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is a
reward function, and $\gamma$ is a discount factor. An agent’s behavior can be
characterized by a policy
$\pi\colon\mathcal{S}\rightarrow[0,1]^{|\mathcal{A}|}$, i.e., $\pi(a|s)$ is
the probability of taking action $a$ in state $s$.111We only consider
stationary policies in this paper.

##### Successor Features (SF).

Barreto et al. (2017) Given features
$\bm{\theta}\colon\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$
associated with each state-action pair. The SF $\bm{\psi}^{\pi}_{s_{0}}$ is
the expected discounted sum of features of state-action pairs encountered when
following policy $\pi$ starting from $s_{0}$, i.e.,

$\bm{\psi}^{\pi}_{s_{0}}=\mathbb{E}_{\mathcal{M},\pi}[\sum_{t=0}^{\infty}\gamma^{t}\bm{\theta}(S_{t},A_{t})\mid
S_{0}=s_{0}].$ (1)

##### Options and Semi-Markov Decision Processes (SMDPs).

Temporally extended actions, i.e., sequences of actions over multiple time
steps, are often represented as options $o=\langle
I^{o},\pi^{o},\beta^{o}\rangle$, where $I^{o}\subseteq\mathcal{S}$ is a set of
states that an option can be initiated at (initiation set),
$\pi^{o}\colon\mathcal{S}\rightarrow[0,1]^{|\mathcal{A}|}$ is the option
policy, and $\beta^{o}\colon\mathcal{S}\rightarrow[0,1]$ is the termination
condition, i.e., the probability that $o$ terminates in state
$s\in\mathcal{S}$. The transition dynamics and rewards induced by an option
$o$ are

$\displaystyle P_{s,s^{\prime}}^{o}$
$\displaystyle=\sum_{k=1}^{\infty}P(s,o,s^{\prime},k)\gamma^{k},$
$\displaystyle r_{s}^{o}$
$\displaystyle=\mathbb{E}[r_{t+1}+\ldots+\gamma^{k}r_{t+k}\mid\mathcal{E}(o,s,t)],$

where $P(s,o,s^{\prime},k)$ is the probability of transiting from $s$ to
$s^{\prime}$ in $k$ steps when following option policy $\pi^{o}$ and
terminating in $s^{\prime}$, $\mathcal{E}(o,s,t)$ is the event that option $o$
is initiated at time $t$ in state $s$, and $t+k$ is the random time at which
$o$ terminates.

An SMDP Sutton et al. (1999) is an MDP with a set of options, i.e.,
$\mathcal{M}=\langle\mathcal{S},\mathcal{O},P,r,\gamma\rangle$, where
$P\colon\mathcal{S}\times\mathcal{O}\rightarrow[0,1]^{|S|}$ are the options’
transition dynamics, and
$r\colon\mathcal{S}\times\mathcal{O}\rightarrow\mathbb{R}$ is the options’
rewards. A family of variable-reward SMDPs Mehta et al. (2008) (denoted as
$\bm{\psi}$-SMDP) is defined as
$\mathcal{M}=\langle\mathcal{S},\mathcal{O},P,\bm{\psi},\gamma\rangle$, where
$\bm{\psi}_{s}^{o}$ is the SF of option $o$ starting at state $s$. A
$\bm{\psi}$-SMDP induces an SMDP if the reward is linear in the features,
i.e., $r_{s}^{o}=w_{r}^{T}\bm{\psi}_{s}^{o}$.

##### Inverse Reinforcement Learning (IRL).

IRL is an approach to learning from demonstrations Abbeel and Ng (2004) with
unknown rewards. A common assumption is that the rewards are linear in some
features, i.e., $r_{s}^{a}=w_{r}^{T}\bm{\theta}(s,a)$, where
$w_{r}\in\mathbb{R}^{d}$ is a real-valued weight vector specifying the reward
of observing the different features. Based on this assumption, Abbeel and Ng
(2004) observed that for a learner policy to perform as well as the expert’s,
it suffices that their feature expectations match. Therefore, IRL has been
widely posed as a feature-matching problem Abbeel and Ng (2004); Syed et al.
(2008); Ho and Ermon (2016), where the learner tries to match the expert’s
feature expectation.

##  3 Options as Successor Features

In this section, we first present abstract successor options, an abstract
representation of options through successor features that can be shared across
multiple MDPs $\\{\mathcal{M}_{i}\\}_{i=1}^{k}$. Therefore, we assume a
feature function which maps state-action pairs for each MDP to a shared
feature space, i.e.,
$\bm{\theta}_{\mathcal{M}_{i}}\colon\mathcal{S}_{i}\times\mathcal{A}_{i}\rightarrow\mathbb{R}^{d}$.
Such features are commonly adopted by prior works Barreto et al. (2017); Syed
et al. (2008); Abbeel and Ng (2004), and can be often obtained through feature
extractors such as an object detector Girshick (2015). We then present two
algorithms that enable us to transfer abstract successor options to new
environments with and without known dynamics by grounding the abstract
options.

###  3.1 Abstract Successor Options

_Abstract successor options_ are vectors in $\mathbb{R}^{d}$, representing
cumulative feature expectations that the corresponding ground options should
realise.

######  Definition 3.1 (Abstract Successor Options, Ground Options).

Let $\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,r,\gamma\rangle$ be an MDP
and
$\bm{\theta}_{\mathcal{M}}\colon\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$
be the feature function. An _abstract successor option_ is a vector
$\bm{\psi}^{{\bar{o}}}\in\mathbb{R}^{d}$. For brevity, we will often denote
$\bm{\psi}^{{\bar{o}}}\in\mathbb{R}^{d}$ as ${\bar{o}}$. Let
$g_{s}\colon\mathcal{O}\rightarrow\mathbb{R}^{d}$ denote a state-dependent
mapping such that
$o\mapsto\bm{\psi}_{s}^{o}=\mathbb{E}[\sum_{\kappa=0}^{k}\gamma^{\kappa}\bm{\theta}_{\mathcal{M}}(S_{t+\kappa},A_{t+\kappa})|\mathcal{E}(o,s,t)]$.
The options $o\in g_{s}^{-1}({\bar{o}})$ are referred to as _ground options_
of ${\bar{o}}$ in state $s$.

The initiation set of an abstract successor option ${\bar{o}}$ can now be
naturally defined as $I^{{\bar{o}}}\coloneqq\\{s\in\mathcal{S}\mid\exists
o\colon g_{s}(o)=\bm{\psi}^{{\bar{o}}}\\}$. In the following section, we
present an algorithm for grounding abstract successor options in an MDP
$\mathcal{M}$ using IRL.

###  3.2 Grounding Abstract Successor Options

The challenge of grounding abstract successor options, i.e., finding ground
policies which realize an abstract successor option’s feature vector,
corresponds to a feature-matching problem. This problem, although with a
different aim, has been extensively studied in IRL, where a learner aims to
match the expected discounted cumulative feature expectations of an expert
Syed et al. (2008); Abbeel and Ng (2004). Inspired by IRL, we present two
algorithms for option grounding: IRL-naive and IRL-batch, where the latter
algorithm enjoys better runtime performance while achieving similar action
grounding performance (cf. experiments).

Algorithm 1 Option Grounding (IRL-naive)

1:Input:
$\\!\mathcal{M}\\!\\!=\\!\\!\langle\mathcal{S},\mathcal{A},P,r,\gamma\rangle$,
abstract option ${\bar{o}}$, $\epsilon_{\textnormal{thresh.}}$

2:Output: initiation set $I^{\bar{o}}$, dict. of ground option policies
$\Pi^{\bar{o}}$, dict. of termination probabilities $\Xi^{\bar{o}}$

3:// Construct augmented MDP

4:$\mathcal{S}^{\prime}\leftarrow\mathcal{S}\cup\\{s_{\textnormal{null}}\\},\mathcal{A}^{\prime}\leftarrow\mathcal{A}\cup\\{a_{\textnormal{T}}\\},P^{\prime}\leftarrow
P$

5:$\forall s\in\mathcal{S}^{\prime}\colon
P^{\prime}(s_{\textnormal{null}}|s,a_{\textnormal{T}})=1$

6:$\forall a\in\mathcal{A}^{\prime}\colon P^{\prime}(s_{\textnormal{null}}\mid
s_{\textnormal{null}},a)=1$

7:// Find ground options (for IRL see Algorithm 2, Appendix A.1)

8:for all $s_{\textnormal{start}}\in\mathcal{S}$, do

9: $\epsilon,\pi^{o}_{s_{\textnormal{start}}}\leftarrow$
IRL($\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},\gamma,s_{\textnormal{start}},\bm{\psi}^{\bar{o}}$)

10: if $\epsilon\leq\epsilon_{\textnormal{thresh.}}$ then

11: $I^{\bar{o}}\leftarrow I^{\bar{o}}\cup\\{s_{\textnormal{start}}\\}$

12: $\Pi^{\bar{o}}(s_{\textnormal{start}})=\pi^{o}_{s_{\textnormal{start}}}$

13: $\Xi^{\bar{o}}(s_{\textnormal{start}})=\beta^{o}$, where
$\beta^{o}(s)=\pi^{o}_{s_{\textnormal{start}}}(a_{\textnormal{T}}|s)$

14: end if

15:end for

16:return $I^{\bar{o}},\Pi^{\bar{o}},\Xi^{\bar{o}}$

#####  IRL-naive (Algorithm 1)

is a naive algorithm for grounding an abstract option ${\bar{o}}$. The
algorithm uses feature matching based IRL to find for each possible starting
state $s_{\textnormal{start}}$ an option realizing the feature vector
$\bm{\psi}^{{\bar{o}}}$. First, we create an augmented MDP which enables
termination of options. To do this, we augment the action space with a
terminate action $a_{\textnormal{T}}$ and append a null state
$s_{\textnormal{null}}$ to the state space. Specifically, $a_{\textnormal{T}}$
will take the agent from any “regular” state to the null state. Taking any
action in the null state will lead to itself, and yield a zero feature, i.e.,
$\bm{\theta}(s_{\textnormal{null}},\cdot)=\mathbf{0}$. With the augmented MDP,
we can compute an option policy via IRL. There exists several IRL
formulations, and we adopt the linear programming (LP) approach by Syed et al.
(2008) (Algorithm 2 in Appendix A.1). Specifically, the algorithm finds the
discounted visitation frequencies for all state-action pairs that together
match the abstract successor option, then the option policy $\pi^{o}$
(including option termination) can be deduced from the state-action visitation
frequencies. Finally, if the discrepancy $\epsilon$ of the successor feature
of the learned option and the abstract option is below a specified threshold
$\epsilon_{\textnormal{thresh.}}$, the start state $s_{\textnormal{start}}$
will be added to the initiation set.

#####  IRL-batch (Algorithm 3, Appendix A.1).

IRL-naive needs to solve an IRL problem for each state in $\mathcal{S}$ which
is computationally demanding. To improve the efficiency of abstract option
grounding, we propose IRL-batch, a learning algorithm that performs IRL for
starting states in batches. The main challenge is that the state-action
visitation frequencies found by the LP for matching the abstract option’s
feature vector may be a mixture of different option policies from different
starting states. To approach this issue, IRL-batch uses a recursive procedure
with a batched IRL component (cf. Algorithm 4 in Appendix A.1) which
effectively regularises the learned option policy. This algorithm can
significantly reduce the number of IRL problems that need to be solved while
preserving near-optimal performance, cf. Table 1.

(a) Object-Rooms (b) Abstract $\bm{\psi}$-SMDP

(c) Successor Homomorphism

(d) $Q$ (all)-Abstraction

Figure 1: MDP abstraction in the Object-Rooms domain. (b) Abstract
$\bm{\psi}$-SMDP induced by our successor homomorphism from the ground MDP as
shown in (c), the abstract states in (b) correspond to aggregated ground
states of the same colour in (c). (d) Abstraction induced by approximate
$Q^{*}$-irrelevance abstraction (cf. Sec. A.4) for _find key_ ; the
abstraction does not carry temporal semantics, and is not reusable for other
tasks e.g., _find star._. Another example can be found in Figure 10 in
Appendix A.6.1 and more details are in the experiments section.

###  3.3 Transfer Via Abstract Successor Options

Since features are assumed to be shared across MDPs, an existing option from a
source environment can be transferred to a target environment through first
finding the abstract successor option ${\bar{o}}=g_{s}(o)$ by computing the
ground option’s successor feature, then grounding ${\bar{o}}$ in the target
environment $o^{\prime}\in g_{s}^{-1}({\bar{o}})$ using the IRL-naive or IRL-
batch algorithm. When the transition dynamics of the target environment are
unknown, exploration is needed before option grounding to construct the
(approximate) MDP transition graph, e.g., through a random walk. However,
random walks can often get trapped in local communities Pons and Latapy (2005)
and thus can be inefficient for exploration. On the other hand, unlike solving
a long-horizon task with sparse rewards, options are often relatively
localised, and hence can be readily found with partially constructed
transition graphs. This enables simultaneous exploration and option grounding:
given a set of abstract options $\bar{\mathcal{O}}$, we start with an
iteration of a random walk which constructs an approximate MDP
$\tilde{\mathcal{M}}_{0}$. In each subsequent iteration $k$, we ground the
abstract options using $\tilde{\mathcal{M}}_{k-1}$, and update the MDP
$\tilde{\mathcal{M}}_{k}$ by exploring with a random walk using both primitive
actions and the computed ground options. We show empirically that, using our
approach, ground options can be learned quickly and significantly improve the
exploration efficiency, cf. Section 5.1.2.

##  4 Abstraction with Successor Homomorphism

Parallel to temporal abstraction, state abstraction Dean and Givan (1997); Li
et al. (2006); Abel et al. (2016) aims to form abstract MDPs in order to
reduce the complexity of planning while ensuring close-to-optimal performance
compared with using the original MDP. Typically, an abstract MDP is formed by
aggregating similar states into an abstract state. However, most prior methods
do not take into account temporal abstraction thus often requiring strict
symmetry relations among the aggregated states. To overcome this limitation,
we propose a state abstraction mechanism based on our abstract successor
options and $\psi$-SMDPs (cf. Sec. 2), which naturally models the decision
process with the abstract options. In particular, we propose _successor
homomorphisms_ , which define criteria for state aggregation and induced
_abstract $\psi$-SMDPs_. We show that planning with these abstract
$\psi$-SMDPs yields near-optimal performance. Moreover, the abstract
$\psi$-SMDPs can inherit meaningful semantics from the options, c.f., Fig. 1.

Specifically, an abstract $\psi$-SMDP is a tuple
$\bar{\mathcal{M}}=\langle\bar{\mathcal{S}},\bar{\mathcal{O}},\bar{P},\bar{\bm{\psi}},\gamma\rangle$,
where $\bar{\mathcal{S}}$ is a set of abstract states, $\bar{\mathcal{O}}$ are
the abstract options, whose transition dynamics between the abstract states
are described by $\bar{P}_{{\bar{s}},{\bar{s}}^{\prime}}^{{\bar{o}}}$, and
$\bar{\bm{\psi}}_{{\bar{s}}}^{\bar{o}}$ is the SF of executing $\bar{o}$ from
$\bar{s}$. A successor homomorphism $h=(f(s),g_{s}(o),w_{s})$ maps a (ground)
$\psi$-SMDP to an abstract $\psi$-SMDP, where $f(s)$ aggregates ground states
with approximately equal option transition dynamics into abstract states,
$g_{s}(o)$ is our state-dependent mapping between ground and abstract options,
and $w_{s}$ is a weight function which weighs the aggregated ground states
towards each abstract state.

######  Definition 4.1 ($\epsilon$-Approximate Successor Homomorphism).

Let $h=(f(s),g_{s}(o),w_{s})$ be a mapping from a ground $\bm{\psi}$-SMDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{O},P,\bm{\psi},\gamma\rangle$ to an
abstract $\bm{\psi}$-SMDP
$\bar{\mathcal{M}}=\langle\bar{\mathcal{S}},\bar{\mathcal{O}},\bar{P},\bar{\bm{\psi}},\gamma\rangle$,
where $f\colon\mathcal{S}\rightarrow\bar{\mathcal{S}}$,
$g_{s}\colon\mathcal{O}\rightarrow\bar{\mathcal{O}}$ and
$w\colon\mathcal{S}\rightarrow[0,1]$ s.t.
$\forall{\bar{s}}\in\bar{\mathcal{S}},\sum_{s\in f^{-1}({\bar{s}})}w_{s}=1$.
$h$ is an _$(\epsilon_{P},\epsilon_{\psi})$ -approximate successor
homomorphism_ if for $\epsilon_{P},\epsilon_{\psi}>0$, $\forall
s_{1},s_{2}\in\mathcal{S},o_{1},o_{2}\in\mathcal{O}$,

$\displaystyle h(s_{1},o_{1})=h(s_{2},o_{2})\implies\\!\\!\\!$
$\displaystyle\quad\forall
s^{\prime}\in\mathcal{S}\;|\sum_{s^{\prime\prime}\in
f^{-1}(f(s^{\prime}))}P^{o_{1}}_{s_{1},s^{\prime\prime}}\\!\\!-\\!P^{o_{2}}_{s_{2},s^{\prime\prime}}|\leq\epsilon_{P},$
$\displaystyle\quad\textnormal{and
}\|\bm{\psi}_{s_{1}}^{o_{1}}-\bm{\psi}_{s_{2}}^{o_{2}}\|_{1}\leq\epsilon_{\psi}.$

Having defined the abstract states, the transition dynamics and features of
the abstract $\psi$-SMDP $\bar{\mathcal{M}}$ can be computed by:
$\bar{P}_{{\bar{s}},{\bar{s}}^{\prime}}^{{\bar{o}}}=\\!\\!\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}\\!\\!\sum\limits_{s^{\prime}\in
f^{-1}{({\bar{s}}^{\prime})}}\\!\\!\\!\\!\\!P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}})}\textnormal{
, and
}\bar{\bm{\psi}}_{{\bar{s}}}^{{\bar{o}}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}\bm{\psi}_{s}^{g^{-1}_{s}({\bar{o}})},$

where $\sum_{s^{\prime\prime}\in
f^{-1}(f(s^{\prime}))}P^{o}_{s,s^{\prime\prime}}$ refers to the transition
probability from ground state $s$ to an abstract state
${\bar{s}}^{\prime}=f(s^{\prime})$ following option $o$. Intuitively, two
states mapping to the same abstract state have approximately equal option
transition dynamics towards all abstract states, and the corresponding ground
options induce similar successor features. For efficient computation of the
abstract model, the transition dynamics condition can be alternatively defined
on the ground states s.t. $h(s_{1},o_{1})=h(s_{2},o_{2})\implies\forall
s^{\prime}\in S$,

$\displaystyle\vspace{-1mm}|P^{o_{1}}_{s_{1},s^{\prime}}-P^{o_{2}}_{s_{2},s^{\prime}}|\leq\epsilon_{P},\textnormal{
and
}\quad\|\bm{\psi}_{s_{1}}^{o_{1}}-\bm{\psi}_{s_{2}}^{o_{2}}\|_{1}\leq\epsilon_{\psi},\vspace{-1mm}$
(2)

which states that two states mapping to the same abstract state have
approximately equal option transition dynamics towards all _ground_ states,
and the corresponding ground options induce similar SF. In general, Def 4.1
and Eq. (2) can result in different abstractions, but similar performance
bounds could be derived. In cases in which multiple ground options map to the
same abstract option, $g^{-1}_{s}({\bar{o}})$ picks one of the ground options.
An example abstract $\bm{\psi}$-SMDP induced by our approximate successor
homomorphism is shown in Fig. 1.

Our successor homomorphism combines state and temporal abstraction, by
aggregating states with similar multi-step transition dynamics and feature
expectations, in contrast to one-step transition dynamics and rewards. This
formulation not only relaxes the strong symmetry requirements among the
aggregated states but also provides the induced abstract $\psi$-SMDP with
semantic meanings obtained from the options. Furthermore, each abstract
$\bm{\psi}$-SMDP instantiates a family of abstract SMDPs (cf. Def. A.3,
Appendix A.3) by specifying a task, i.e., reward weight $w_{r}$ on the
features. Extending results from Abel et al. (2016, 2020) to our setting, we
can guarantee performance of planning with the abstract $\psi$-SMDP across
different tasks.

######  Theorem 4.1.

Let $w_{r}\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a linear reward vector
such that $r_{s}^{a}=w_{r}^{T}\bm{\theta}(s,a)$. Under this reward function,
the value of an optimal abstract policy obtained through the
$(\epsilon_{P},\epsilon_{\psi})$-approximate successor homomorphism is close
to the optimal ground SMDP policy, where the difference is bounded by
$\frac{2\kappa}{(1-\gamma)^{2}}$, where
$\kappa=|w_{r}|(2\epsilon_{\psi}+\frac{\epsilon_{P}|\bar{\mathcal{S}}|\max_{s,a}|\bm{\theta}(s,a)|}{1-\gamma})$.
(c.f. appendix for the proof)

##  5 Experiments

(a) State visitation frequencies

(b) Setting

(c) States explored (d) Baked potato obtained

(e) Coal obtained (f) Potato obtained

(g) Doors opened

Figure 2: Exploring and grounding options in unknown environments in the
Minecraft setting.

In this section, we empirically evaluate our proposed abstraction scheme for
option transfer to new environments with known and unknown transition
dynamics, and planning with abstract SMDPs. Additional details for all
experiments are available in Appendix A.6.

###  5.1 Option Transfer

We evaluate the performance and efficiency of our option grounding algorithm
for transferring options given by expert demonstrations to new environments.

####  5.1.1 Transfer to environments with known dynamics

|  | 2 Rooms | 3 Rooms | 4 Rooms
---|---|---|---|---
Goal | Algorithm | success | LP | success | LP | success | LP
Find Key | IRL-naive | 1.0 | 157 | 1.0 | 487 | 1.0 | 1463
IRL-batch | 1.0 | 2 | 1.0 | 2 | 1.0 | 2
OK | 1.0 | - | 1.0 | - | 1.0 | -
Find Star | IRL-naive | 1.0 | 157 | 1.0 | 487 | 1.0 | 1463
IRL-batch | 1.0 | 2 | 1.0 | 2 | 1.0 | 2
OK | 1.0 | - | 1.0 | - | 1.0 | -
Find Key, Open Door | IRL-naive | 1.0 | 157 | 1.0 | 487 | 1.0 | 1463
IRL-batch | 1.0 | 3 | 1.0 | 15 | 0.95 | 29
OK | 0.08 | - | 0.56 | - | 0.71 | -
Find Key, Open Door, Find Star | IRL-naive | 1.0 | 157 | 1.0 | 487 | 1.0 | 1463
IRL-batch | 1.0 | 4 | 1.0 | 16 | 1.0 | 7
OK | 0.0 | - | 0.51 | - | 0.66 | -

Table 1: Performance and efficiency of option grounding in the Object Rooms.
We show the success rate (success) of the learned options for achieving all
specified goals across all starting states in the initiation set, and the
number of LPs used to find the option policy.

We compare our option grounding algorithms with the baseline algorithm Option
Keyboard (OK) Barreto et al. (2019) on the Object-Rooms Setting.

_s $\mathbin{\vbox{\hbox{\scalebox{0.8}{$\bullet$}}}}$ IRL-naive (Algorithm 1)
and IRL-batch (Appendix; Algorithm 3)_. Our both algorithms _transfer_ an
expert’s demonstration from a 2-Room source environment to a target
environment of 2-4 Rooms, by first encoding the expert’s demonstration as an
abstract option, then grounding the abstract option in the target environment.
_s $\mathbin{\vbox{\hbox{\scalebox{0.8}{$\bullet$}}}}$ Option Keyboard (OK)_
Barreto et al. (2019): OK first trains primitive options (find-key, open-door,
find-star) to maximise a cumulant (pseudo-reward on the history). The
cumulants are hand-crafted in the target environment, where the agent is
rewarded when terminating the option after achieving the goal. Then the
composite options are synthesized via generalized policy improvement (GPI).

_Object-Rooms Setting._ $N$ rooms are connected by doors with keys and stars
inside. There are 6 actions: $\mathcal{A}=\\{$Up, Down, Left, Right, Pick up,
Open$\\}$. The agent can pick up the keys and stars, and use the keys to open
doors. See Figure 4 in Appendix A.6 for an illustration.

_Results._ Table 1 shows the success rate of the computed options for
achieving the required goals across all starting states in the initiation
sets. Both IRL-naive and IRL-batch successfully transfer the options,
moreover, IRL-batch significantly reduces the number of LPs solved. The OK
composed options have a low success rate for achieving the required goals,
e.g., for grounding ”find key, open door, find star” in the 3-Room setting,
the learned options often terminate after achieving 1-2 subgoals.

(a) dense reward

(b) sparse reward

(c) transfer (w. overlap)

(d) transfer (w.o. overlap)

Figure 3: Performance of planning with the abstract MDPs. The upper row shows
the total rewards (normalized by the maximum possible total rewards) obtained,
and the lower row shows the corresponding number of abstract states of the
abstract MDPs. The $x$-axes are the distance thresholds $\epsilon$. _transfer_
refers to task transfer (i.e., different reward function). Further details are
available in Appendix A.6.

####  5.1.2 Transfer to environments with unknown dynamics

To perform grounding with unknown transition dynamics, the agent
simultaneously explores and computes ground options.

_Bake-Rooms Setting (Minecraft)_. The considered environment is based on
Malmo, a standard AI research platform using Minecraft Johnson et al. (2016),
as shown in Figure 2: 4 rooms (R1-R4 from bottom to top) are connected by
doors, and the agent starts in R1. To obtain a baked potato, the agent needs
to open doors, collect coal from a coal dropper in R2, collect potato from a
dropper in R3, and issue a _craft_ command to bake the potato. Agents observe
their current location, objects in nearby $3\times 3$ grids, and the items in
inventory.

_Baselines and learning._ We compare our IRL-batch with the baselines: (i)
_random walk_ and (ii) _eigenoptions_ Machado et al. (2018). Each agent runs
for 20 iterations, each consisting of 200 steps. In the first iteration, all
agents execute random actions. After each iteration, the agents construct an
MDP graph based on collected transitions from all prior iterations. The
eigenoption agent computes $3$ eigenoptions of smallest eigenvalues using the
normalized graph Laplacian, while IRL-batch grounds the $3$ abstract options:
1. open and go to door, 2. collect coal, 3. collect potato. In the next
iteration, agents perform a random walk with both primitive actions and the
acquired options, update the MDP graph, compute new options, and so on.

_Results._ Figure 2 (a) shows the state visitation frequency of our algorithm
in the $14^{\textnormal{th}}$ iteration and a constructed transition graph
(more details in Figure 7, Appendix A.6). The trajectory shows that from R1
(bottom), the agent learns to open door, collect coal in R2, open door,
collect potato in R3, and navigate around the rooms. (c) shows that our
algorithm explores on average more than 50 percent more states than both
baselines in 20 iterations. (d) - (g) shows the objects collected by the
agents (max count is 1) and the number of doors opened. The agent using our
algorithm learns to open door and collect coal within 2 iterations, and it
learns to bake a potato 50 percent of the time within 5 iterations. In all
cases, our algorithm outperforms the baselines. The results are averaged over
10 seeds, shaded regions show standard deviations.

###  5.2 Planning with Abstract SMDP

We compare the performance of planning using our abstract $\psi$-SMDPs found
by successor homomorphism, with two baseline abstraction methods Li et al.
(2006); Abel et al. (2016) on the _Object-Rooms_ environment.

_1\. Q (all)_ : ($Q^{*}$-irrelevance abstraction), if $f(s_{1})=f(s_{2})$,
then $\forall a,|Q^{*}(s_{1},a)-Q^{*}(s_{2},a)|\leq\epsilon$, where
$Q^{*}(s,a)$ is the optimal Q-function for the considered MDP.

_2\. Q (optimal)_ : ($a^{*}$-irrelevant abstraction), if $f(s_{1})=f(s_{2})$
then $s_{1}$ and $s_{2}$ share the same optimal action $a^{*}$ and
$|Q^{*}(s_{1},a^{*})-Q^{*}(s_{2},a^{*})|\leq\epsilon$.

_Training and results._ 3 abstract options are given: 1. open door, 2. find
key, and 3. find star. To find the abstract model induced by our successor
homomorphism, we first ground each abstract option. Then we form the abstract
state by clustering the ground states $s$ according to the pairwise distance
of their option termination state distributions
$\max_{s^{\prime},{\bar{o}}}{|P_{s_{1},s^{\prime}}^{g_{s_{1}}^{-1}({\bar{o}})}-P_{s_{2},s^{\prime}}^{g_{s_{2}}^{-1}({\bar{o}})}|}$
through agglomerative clustering. Finally we compute the abstract transition
dynamics and feature function. For Q (all) and Q (optimal), we first perform
Q-value iteration on a source task to obtain the optimal Q-values, then
cluster the states by their pairwise differences, e.g.,
$|Q^{*}(s_{1},\cdot)-Q^{*}(s_{2},\cdot)|_{\infty}$ for the Q (all) approach,
then compute the abstract transition dynamics.

Figure 3 shows the results of using the induced abstract model for planning.
Our performs well across all tested settings with few abstract states. Since
abstract $\psi$-SMDP does not depend on rewards, the abstract model is robust
across tasks (with varying reward functions) and sparse rewards settings.
Whereas abstraction schemes based on the reward function perform worse when
the source task for performing abstraction is different from the target task
for planning.

##  6 Related Work

Agent-space options Konidaris and Barto (2007) are one of our conceptual
inspirations. In our work, we tie the agent-space to the problem-space through
features, and our option grounding algorithms allow the agents to transfer
agent-space options across different problem spaces.

Successor features (SF). Successor representations (SR) were first introduced
by Dayan (1993). Barreto et al. (2017) proposed SF which generalised SR.
Machado et al. (2018) discovered eigenoptions from SF and showed their
equivalence to options derived from the graph Laplacian. Ramesh et al. (2019)
discovered successor options via clustering over the SR. The Option Keyboard
Barreto et al. (2019) is a pioneering work for option combinations: primitive
options are first trained to maximise cumulants (i.e., pseudo-rewards on
histories), then by putting preference weights over the cumulants, new options
are synthesized to maximise the weighted sum of cumulants. For the purpose of
option transfer and grounding, however, this may yield imprecise option
behaviours due to the interference between cumulants. In contrast, our
successor feature-matching formulation generates precise option behaviours as
demonstrated in Table 1.

MDP Abstraction. MDP abstraction through bisimulation was first considered by
Dean and Givan (1997). Ravindran and Barto (2002) introduced MDP
homomorphisms, which account for action equivalence with a state-dependent
action mapping. Li et al. (2006) proposed a unified theory of abstraction, and
approximate abstraction mechanisms were studied by Ferns et al. (2004) and
Abel et al. (2016). Most relevant to our work are SMDP homomorphisms Ravindran
and Barto (2003) and theoretical formulations for reward-based abstractions in
SMDPs in Abel et al. (2020). Different from prior abstraction formulations
which are reward-based, our feature-based successor homomorphism produces
abstract models which are reusable across tasks.

##  7 Conclusion

We studied temporal and state abstraction in RL using SF. Specifically, we
developed an abstract option representation with SF and presented algorithms
that transfer existing ground options to new environments. Based on the
abstract options, we developed successor homomorphism, which produces abstract
$\psi$-SMDPs that can be used to perform efficient planning with near-optimal
performance guarantees. We demonstrated empirically that our algorithms
transfer the options effectively and efficiently, and showed that our abstract
$\psi$-SMDP models exhibit meaningful temporal semantics, with near-optimal
planning performance across tasks.

## References

  * Abbeel and Ng (2004) Pieter Abbeel and Andrew Y Ng.  Apprenticeship learning via inverse reinforcement learning.  In International Conference on Machine learning, 2004.
  * Abel et al. (2016) David Abel, David Hershkowitz, and Michael Littman.  Near optimal behavior via approximate state abstraction.  In International Conference on Machine Learning, pages 2915–2923. PMLR, 2016.
  * Abel et al. (2020) David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman.  Value preserving state-action abstractions.  In International Conference on Artificial Intelligence and Statistics, pages 1639–1650. PMLR, 2020.
  * Barreto et al. (2017) André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver.  Successor features for transfer in reinforcement learning.  In Advances in Neural Information Processing Systems, pages 4058–4068, 2017.
  * Barreto et al. (2019) André Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygün, Philippe Hamel, Daniel K Toyama, Jonathan J Hunt, Shibl Mourad, David Silver, et al.  The option keyboard: Combining skills in reinforcement learning.  Advances in Neural Information Processing Systems, 2019.
  * Dayan (1993) Peter Dayan.  Improving generalization for temporal difference learning: The successor representation.  Neural Computation, 5(4):613–624, 1993.
  * Dean and Givan (1997) Thomas Dean and Robert Givan.  Model minimization in markov decision processes.  In AAAI Conference on Artificial Intelligence, 1997.
  * Ferns et al. (2004) Norm Ferns, Prakash Panangaden, and Doina Precup.  Metrics for finite markov decision processes.  In Uncertainty in Artifical Intelligence, 2004.
  * Girshick (2015) Ross Girshick.  Fast r-cnn.  In International Conference on Computer Vision, pages 1440–1448, 2015.
  * Ho and Ermon (2016) Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  Advances in Neural Information Processing Systems, 2016.
  * Johnson et al. (2016) Matthew Johnson, Katja Hofmann, Tim Hutton, and David Bignell.  The malmo platform for artificial intelligence experimentation.  In International Joint Conference on Artificial Intelligence, 2016\.
  * Konidaris and Barto (2007) George Dimitri Konidaris and Andrew G Barto.  Building portable options: Skill transfer in reinforcement learning.  In International Joint Conference on Artificial Intelligence, pages 895–900, 2007.
  * Li et al. (2006) Lihong Li, Thomas J Walsh, and Michael L Littman.  Towards a unified theory of state abstraction for mdps.  In International Symposium on Artificial Intelligence and Mathematics, 2006.
  * Machado et al. (2018) Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell.  Eigenoption discovery through the deep successor representation.  In International Conference on Learning Representations, 2018.
  * Malek et al. (2014) Alan Malek, Yasin Abbasi-Yadkori, and Peter Bartlett.  Linear programming for large-scale markov decision problems.  In International Conference on Machine Learning, pages 496–504. PMLR, 2014.
  * Manne (1960) Alan S Manne.  Linear programming and sequential decisions.  Management Science, 6(3):259–267, 1960.
  * Mehta et al. (2008) Neville Mehta, Sriraam Natarajan, Prasad Tadepalli, and Alan Fern.  Transfer in variable-reward hierarchical reinforcement learning.  Machine Learning, 73(3):289, 2008.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  nature, 518(7540):529–533, 2015.
  * Pons and Latapy (2005) Pascal Pons and Matthieu Latapy.  Computing communities in large networks using random walks.  In International Symposium on Computer and Information Sciences, pages 284–293. Springer, 2005.
  * Ramesh et al. (2019) Rahul Ramesh, Manan Tomar, and Balaraman Ravindran.  Successor options: An option discovery framework for reinforcement learning.  In International Joint Conference on Artificial Intelligence, 2019\.
  * Ravindran and Barto (2002) Balaraman Ravindran and Andrew G Barto.  Model minimization in hierarchical reinforcement learning.  In International Symposium on Abstraction, Reformulation, and Approximation, pages 196–211. Springer, 2002.
  * Ravindran and Barto (2003) Balaraman Ravindran and Andrew G Barto.  Smdp homomorphisms: an algebraic approach to abstraction in semi-markov decision processes.  In International Joint Conference on Artificial Intelligence, pages 1011–1016, 2003.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  nature, 550(7676):354–359, 2017.
  * Sutton et al. (1999) 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):181–211, 1999.
  * Syed et al. (2008) Umar Syed, Michael Bowling, and Robert E Schapire.  Apprenticeship learning using linear programming.  In International Conference on Machine Learning, pages 1032–1039, 2008.

##  Appendix A Appendix

###  A.1 Algorithm

In the main text, we have discussed a naive option grounding algorithm:

  * •

Algorithm 1 (IRL-naive): naive option grounding algorithm which performs IRL
over all starting states independently.

In this section, we present additional algorithms useful for option grounding:

  * •

Algorithm 2 (IRL module for IRL-naive): the IRL algorithm adapted from Syed et
al. [2008], and used by the IRL-naive option grounding algorithm (Algorithm 1)
to find the option policies starting from each starting state.

  * •

Algorithm 3 (IRL-batch): an efficient option grounding algorithm which
improves IRL-naive and performs batched learning using IRL.

  * •

Algorithm 4: (IRL module for IRL-batch) the IRL module used by the IRL-batch
option grounding algorithm (Algorithm 3) to find option policies starting from
a batch of starting states.

####  A.1.1 IRL algorithm for the naive option grounding (Algorithm 2)

First, we introduce the IRL module adapted from Syed et al. [2008] and used by
the IRL-naive option grounding algorithm:

Algorithm 2 IRL (used by Algorithm 1 IRL-naive)

1:Input: Augmented MDP
$\mathcal{M}=\langle\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},r,\gamma\rangle,$
starting state $s_{\textnormal{start}}$, state-action features
$\bm{\theta}\colon\mathcal{S}^{\prime}\times\mathcal{A}^{\prime}\rightarrow\mathbbm{R}^{d}$,
abstract option $\bm{\psi}^{{\bar{o}}}\in\mathbbm{R}^{d}$.

2:Output: ground and abstract option feature difference
$\epsilon=\sum_{k=1}^{d}\epsilon_{k}$, option policy
$\pi^{o}_{s_{\textnormal{start}}}$

—Solve LP for visitation frequencies $\mu_{s,a}$ and feature matching errors
$\epsilon_{k}$

$\displaystyle\min_{\mu,\epsilon_{k}}\quad$
$\displaystyle\sum_{k}\epsilon_{k}-\lambda_{1}\sum_{a}\mu_{s_{\textnormal{null}},a}+\lambda_{2}\sum_{s}\mathbbm{1}_{\mu_{s,a_{\textnormal{T}}}>0}$
(3) s.t.
$\displaystyle\sum_{a}\mu_{s,a}=\mathbbm{1}_{s=s_{\textnormal{start}}}+\gamma\sum_{s^{\prime},a}P^{\prime}(s|s^{\prime},a)\mu_{s^{\prime},a}\qquad\forall
s\in\mathcal{S}^{\prime}$ (4)
$\displaystyle\sum_{s,a}\mu_{s,a}\bm{\theta}_{k}(s,a)-\bm{\psi}^{{\bar{o}}}_{k}\leq\epsilon_{k}\qquad\phantom{-}\forall
k\in 1,\ldots,d$ (5)
$\displaystyle\sum_{s,a}\mu_{s,a}\bm{\theta}_{k}(s,a)-\bm{\psi}^{{\bar{o}}}_{k}\geq-\epsilon_{k}\qquad\forall
k\in 1,\ldots,d$ (6) $\displaystyle\mu_{s,a}\geq 0\quad\forall
s\in\mathcal{S}^{\prime},a\in\mathcal{A}^{\prime}$ (7)

—Compute option policy
$\pi^{o}_{s_{\textnormal{start}}}(a|s)=\frac{\mu_{s,a}}{\sum_{a}\mu_{s,a}}$

The algorithm finds the policy and termination condition of the option
${\bar{o}}$ in the following two steps:

  1. 1.

Compute the state-action visitation frequencies $\mu_{s,a}$ such that the
corresponding expected feature vector (approximately) matches the abstract
option feature $\bm{\psi}^{\bar{o}}$.

  2. 2.

Compute the option policy (which includes the termination condition) from
$\mu_{s,a}$.

##### Linear program.

Adapting from prior work which uses linear programming approaches for solving
MDPs and IRL Syed et al. [2008]; Malek et al. [2014]; Manne [1960], our LP
aims to find the state-action visitation frequencies $\mu_{s,a}$ for all
states and actions, which together (approximately) match the abstract option
feature, i.e.,
$\bm{\psi}^{o}_{\textnormal{start}}=\sum_{s,a}\mu_{s,a}\bm{\theta}(s,a)\approx\bm{\psi}^{\bar{o}}$.
In particular,
$\|\bm{\psi}^{o}_{\textnormal{start}}-\bm{\psi}^{\bar{o}}\|_{1}\leq\sum_{k=1}^{d}\epsilon_{k}$.

_Inputs: _ Recall that to enable the modelling of options and their
termination conditions, the input augmented MDP
$\mathcal{M}=\langle\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},r,\gamma\rangle$
was constructed in Algorithm 1 by adding a null state $s_{\textnormal{null}}$
and termination action $a_{\textnormal{T}}$ such that $a_{\textnormal{T}}$
leads from any regular state to $s_{\textnormal{null}}$.

_Variables:_ 1\. $\epsilon_{k}$: Upper bounds for the absolute difference
between the (learner) learned ground option successor feature and the abstract
option (expert) feature in the $k$-th dimension.

2\. $\mu_{s,a}$: Expected cumulative state-action visitation of state-action
pair $s,a$. Additionally, denote $\mu_{s}$ as the expected cumulative state
visitation of $s$, i.e., $\forall s\in\mathcal{S},a\in\mathcal{A}$,

$\displaystyle\mu_{s,a}=\mathbb{E}_{\mathcal{M},\pi}[\sum_{t=0}^{\infty}\gamma^{t}\mathbbm{1}_{S_{t}=s,A_{t}=a}|s_{0}\sim
P_{\textnormal{start}}],\quad\textnormal{and}\quad\mu_{s}=\mathbb{E}_{\mathcal{M},\pi}[\sum_{t=0}^{\infty}\gamma^{t}\mathbbm{1}_{S_{t}=s}|s_{0}\sim
P_{\textnormal{start}}]$ (8)

where $P_{\textnormal{start}}$ is the distribution over starting states. In
this naive option grounding algorithm the start state is a single state
$s_{\textnormal{start}}$. Observe that $\mu_{s}$ and $\mu_{s,a}$ are related
by the policy $\pi\colon\mathcal{S}\rightarrow\mathcal{A}$ as

$\displaystyle\mu_{s,a}=\pi(a|s)\mu_{s},\quad\textnormal{and}\quad\mu_{s}=\sum_{a}\pi(a|s)\mu_{s}=\sum_{a}\mu_{s,a}.$
(9)

And the Bellman flow constraint is given by either $\mu_{s}$ or $\mu_{s,a}$:

$\displaystyle\mu_{s}=\mathbbm{1}_{s=s_{\textnormal{start}}}+\gamma\sum_{s^{\prime},a}P(s|s^{\prime},a)\pi(a|s^{\prime})\mu_{s^{\prime}}\iff\sum_{a}\mu_{s,a}=\mathbbm{1}_{s=s_{\textnormal{start}}}+\gamma\sum_{s^{\prime},a}P(s|s^{\prime},a)\mu_{s^{\prime},a}$
(10)

By Equation (9), the policy $\pi$ corresponding to the state-action visitation
frequencies is computed as

$\displaystyle\pi_{s_{\textnormal{start}}}^{o}=\frac{\mu_{s,a}}{\mu_{s}}=\frac{\mu_{s,a}}{\sum_{a}\mu_{s,a}}.$
(11)

_Objective function:
$\sum_{k}\epsilon_{k}-\lambda_{1}\sum_{a}\mu_{s_{\textnormal{null,
a}}}+\lambda_{2}\sum_{s}\mathbbm{1}_{\mu_{s,a_{\textnormal{T}}}>0}$_

1\. $\sum_{k}\epsilon_{k}$: the first term is the feature difference
$\epsilon$ between the abstract and computed ground option.

2\. $-\lambda_{1}\sum_{a}\mu_{s_{\textnormal{null, a}}}$: The second term is a
small penalty on the option length to encourage short options. This is
achieved by putting a small bonus (e.g., $\lambda_{1}=0.01$) on the expected
cumulative visitation of the null state $s_{\textnormal{null}}$, which the
agent reaches after using the terminate action.

3\. $\lambda_{2}\sum_{s}\mathbbm{1}_{\mu_{s,a_{\textnormal{T}}}>0}$: The last
term is a regularisation on the number of terminating states. This helps guide
the LP to avoid finding mixtures of option policies which together match the
feature expectation.

In this way, the linear program can find an option policy which terminates
automatically.

_Constraints:_ Equation (4) is the Bellman flow constraint Syed et al. [2008];
Malek et al. [2014] which specifies how the state-action visitation
frequencies are related by the transition dynamics, see Equation (10).
Equations (5) and (6) define the feature difference $\epsilon$ of the ground
option
$\bm{\psi}^{o}_{s_{\textnormal{start}}}=\sum_{s,a}\mu_{s,a}\bm{\theta}(s,a)$
and abstract option $\bm{\psi}^{\bar{o}}$ for the $k$-th dimension.

_Step 2_ derives the policy from the state-action visitation frequencies
$\mu_{s,a}$, see Equation (11).

####  A.1.2 Grounding Abstract Options for Starting States in Batches
(Algorithm 3)

Algorithm 3 Grounding Abstract Options (IRL-Batch)

1:Input: MDP $\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,r,\gamma\rangle$,
abstract option $\bm{\psi}^{{\bar{o}}}$, $\epsilon_{\textnormal{threshold}}$

2:Output: initiation set $I^{\bar{o}}$, dictionary of ground option policies
$\Pi^{\bar{o}}$, termination probabilities $\Xi^{\bar{o}}$

3:// Construct augmented MDP

4:$\mathcal{S}^{\prime}\leftarrow\mathcal{S}\cup\\{s_{\textnormal{null}}\\},\mathcal{A}^{\prime}\leftarrow\mathcal{A}\cup\\{a_{\textnormal{T}}\\},P^{\prime}\leftarrow
P$

5:$\forall s\in\mathcal{S}^{\prime}\colon P^{\prime}(s_{\textnormal{null}}\mid
s,a_{\textnormal{T}})=1$; $\forall a\in\mathcal{A}^{\prime}\colon
P^{\prime}(s_{\textnormal{null}}\mid s_{\textnormal{null}},a)=1$

6:

7:// Find ground options for all starting states

8:$I^{\bar{o}},\Pi^{\bar{o}},\Xi^{\bar{o}}$ = Match-and-
divide($\mathcal{S}^{\prime}\setminus\\{s_{\textnormal{null}}\\}$)

9:

10:// Recursive Function

11:function Match-and-divide($c_{\textnormal{start}}$)

12:
$\epsilon_{c_{\textnormal{start}}},\Pi^{o}_{c_{\textnormal{start}}}\leftarrow$
IRL($\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},\gamma,c_{\textnormal{start}},\bm{\psi}^{\bar{o}}$),
$\triangleright$ for IRL see Algorithm 4

13: $c_{\textnormal{match}}$, $c_{\textnormal{no-match}}$,
$C_{\textnormal{ambiguous}}$ = Classify($c_{\textnormal{start}}$,
$\Pi^{o}_{c_{\textnormal{start}}}$, $\epsilon_{c_{\textnormal{start}}}$,
$\epsilon_{\textnormal{threshold}}$)

14: for all $s_{\textnormal{start}}\in c_{\textnormal{match}}$ do

15:
$\pi^{o}_{s_{\textnormal{start}}}\leftarrow\Pi^{o}_{c_{\textnormal{start}}}(s_{\textnormal{start}})$

16: $I^{\bar{o}}\leftarrow I^{\bar{o}}\cup\\{s_{\textnormal{start}}\\}$,
$\Pi^{\bar{o}}(s_{\textnormal{start}})=\pi^{o}_{s_{\textnormal{start}}}$,
$\Xi^{\bar{o}}(s_{\textnormal{start}})=\beta^{o},\textnormal{ where
}\beta^{o}(s)=\pi^{o}_{s_{\textnormal{start}}}$

17: end for

18: if $C_{\textnormal{ambiguous}}\neq\emptyset$ then

19: for all $c_{i}\in C_{\textnormal{ambiguous}}$ do

20: match-and-divide($c_{i}$) $\triangleright$ Note:
$C_{\textnormal{ambiguous}}$ is a set of clusters

21: end for

22: end if

23: return $I^{\bar{o}},\Pi^{\bar{o}},\Xi^{\bar{o}}$

24:end function

25:

26:// Classify start states according to the policy found by IRL

27:function
Classify($c_{\textnormal{start}},\Pi^{o}_{c_{\textnormal{start}}}$,
$\epsilon_{c_{\textnormal{start}}}$,$\epsilon_{\textnormal{threshold}}$)

28: $c_{\textnormal{match}},c_{\textnormal{no-
match}},c_{\textnormal{ambiguous}}\leftarrow\emptyset$

29: for all $s_{\textnormal{start}}\in c_{\textnormal{start}}$ do

30: Execute $o$ from $s_{\textnormal{start}}$ to get successor feature
$\bm{\psi}^{o}_{s_{\textnormal{start}}}$ and terminating distribution
$P^{o}_{s_{\textnormal{start}},s^{\prime}}$

31: Compute feature difference
$\epsilon^{o}_{s_{\textnormal{start}}}=|\bm{\psi}^{\bar{o}}-\bm{\psi}^{o}_{s_{\textnormal{start}}}|$

32: end for

33: $c_{\textnormal{no-match}}\leftarrow c_{\textnormal{start}}$ if
$\min_{s_{\textnormal{start}}\in
c_{\textnormal{start}}}\epsilon^{o}_{s_{\textnormal{start}}}>\epsilon_{\textnormal{threshold}}$
and $\epsilon_{c_{\textnormal{start}}}>\epsilon_{\textnormal{threshold}}$

34: $c_{\textnormal{match}}\leftarrow\\{s_{\textnormal{start}}\in
c_{\textnormal{start}}|\epsilon^{o}_{s_{\textnormal{start}}}\leq\epsilon_{\textnormal{threshold}}\\}$

35: $c_{\textnormal{ambiguous}}\leftarrow c_{\textnormal{start}}\setminus
c_{\textnormal{match}},c_{\textnormal{no-match}}$

36: if $c_{\textnormal{ambiguous}}\neq\emptyset$ then $\triangleright$ Cluster
by termination distributions or successor features(1)

37:
$C_{\textnormal{ambiguous}}\leftarrow\textsc{Cluster}(c_{\textnormal{ambiguous}},P^{o}_{s_{\textnormal{start}},s^{\prime}})$

38: end if

39: return $c_{\textnormal{match}}$, $c_{\textnormal{no-match}}$,
$C_{\textnormal{ambiguous}}$

40:end function

(1) In practice both approaches work well and address the challenge that the
solution found could be a mixture of different option policies which
individually yield different SF but together approximate the target SF.
Clustering by SF approaches this issue by enforcing the SF of option policies
from all $s_{\textnormal{start}}$ in a cluster to be similar and match the
target. Clustering by termination distribution is an effective heuristic which
groups together nearby $s_{\textnormal{start}}$, also resulting in options
with similar SF.

Based on the naive option grounding algorithm (Algorithm 1), we now introduce
an efficient algorithm for grounding abstract options, which performs IRL over
the start states in batches (Algorithm 3).

##### Challenges.

The main challenges regarding performing batched IRL for grounding the options
are: 1. By naively putting a uniform distribution over all possible starting
states, the IRL LP cannot typically find the ground options which match the
abstract option. Moreover, a closely related problem as well as one of the
reasons for the first problem is 2. Since there are many different starting
states, the state-action visitation frequencies found by the LP for matching
the option feature may be a mixture of different option policies from the
different starting states, and the induced ground option policies individually
cannot achieve the successor feature of the abstract option.

##### Solutions.

For the first challenge, we introduce the batched IRL module (Algorithm 4) to
be used by IRL-batch. It flexibly learns a starting state distribution with
entropy regularisation.

For the second challenge, Algorithm 3 is a recursive approach where each
recursion performs batched-IRL on a set of starting states. Then, by executing
the options from each starting state using the transition dynamics, we prune
the starting states which successfully match the abstract successor option’s
feature, and those where matching the abstract option is impossible. And
cluster the remaining ambiguous states based on their option termination
distribution (or their achieved successor features) and go to the next
recursion. Intuitively, we form clusters of similar states (e.g., which are
nearby and belong to a same community according to the option termination
distribution). And running batched-IRL over a cluster of similar starting
states typically returns a single ground option policy which applies to all
these starting states.

##### Algorithm 3 (IRL-batch: Grounding Abstract Options in Batches).

The algorithm first constructs the augmented MDP with the null states and
terminate actions in the same way as the naive algorithm. Then it uses a
recursive function _Match-And-Divide( $c_{\textnormal{start}}$)_, which first
computes the ground option policies corresponding to the set of starting
states $c_{\textnormal{start}}$ through batched IRL (Algorithm 4) over
$c_{\textnormal{start}}$, then _Classify_ the starting states by their
corresponding ground options’ termination distributions or successor feature,
into the following 3 categories: 1. $c_{\textnormal{match}}$: the start states
where an abstract option can be initiated (i.e., there exists a ground option
whose successor feature matches the abstract option); 2. $c_{\textnormal{no-
match}}$: the start states where the abstract option cannot be initiated; and
3. $C_{\textnormal{ambiguous}}$: a set of clusters dividing the remaining
ambiguous states. If $C_{\textnormal{ambiguous}}$ is not empty, then each
cluster goes through the next recursion of _Match-And-Divide_. Otherwise the
algorithm terminates and outputs the initiation set, option policy and
termination conditions.

Algorithm 4 IRL (used by Algorithm 3 IRL-Batch)

1:Input: Augmented MDP
$\mathcal{M}=\langle\mathcal{S}^{\prime},\mathcal{A}^{\prime},P^{\prime},r,\gamma\rangle,$,
state-action features
$\bm{\theta}\colon\mathcal{S}^{\prime}\times\mathcal{A}^{\prime}\rightarrow\mathbbm{R}^{d}$,
abstract option $\bm{\psi}^{{\bar{o}}}\in\mathbbm{R}^{d}$, a set of starting
states
$c_{\textnormal{start}}\subseteq\mathcal{S}^{\prime}\setminus\\{s_{\textnormal{null}}\\}$.

2:Output: (joint over $c_{\textnormal{start}}$) ground and abstract option
feature difference $\epsilon=\sum_{k=1}^{d}\epsilon_{k}$, dictionary of ground
option policy $\Pi^{o}(s_{\textnormal{start}})$ for all start states in
$c_{\textnormal{start}}$

——-_// Step 1: Solve LP for state-action visitation frequencies $\mu_{s,a}$_

$\displaystyle\min_{\mu,\epsilon_{k},p^{\textnormal{start}}}\quad$
$\displaystyle\sum_{k}\epsilon_{k}-\lambda_{1}\sum_{a}\mu_{s_{\textnormal{null}},a}+\lambda_{2}\sum_{s}p_{s}^{\textnormal{start}}\log
p_{s}^{\textnormal{start}}+\lambda_{3}\sum_{s}\mathbbm{1}_{\mu_{s,a_{\textnormal{T}}}>0}$
s.t.
$\displaystyle\sum_{a}\mu_{s,a}=p_{s}^{\textnormal{start}}+\gamma\sum_{s^{\prime},a}P^{\prime}(s|s^{\prime},a)\mu_{s^{\prime},a}$
$\displaystyle\qquad\forall s\in\mathcal{S}^{\prime}$
$\displaystyle\sum_{s,a}\mu_{s,a}\bm{\theta}_{k}(s,a)-\bm{\psi}^{{\bar{o}}}_{k}\leq\epsilon_{k}$
$\displaystyle\forall k\in 1,\ldots,d$
$\displaystyle\sum_{s,a}\mu_{s,a}\bm{\theta}_{k}(s,a)-\bm{\psi}^{{\bar{o}}}_{k}\geq-\epsilon_{k}$
$\displaystyle\forall k\in 1,\ldots,d$ $\displaystyle\mu_{s,a}\geq 0$
$\displaystyle\forall s\in P^{\prime},a\in\mathcal{A}^{\prime}$
$\displaystyle\sum_{s\in c_{\textnormal{start}}}p_{s}^{\textnormal{start}}=1$
$\displaystyle p_{s}^{\textnormal{start}}\geq 0$ $\displaystyle\forall s\in
c_{\textnormal{start}}$ $\displaystyle p_{s}^{\textnormal{start}}=0$
$\displaystyle\forall s\notin c_{\textnormal{start}}$

——-_// Step 2: Compute dictionary of option policies $\Pi^{o}$, $\forall
s_{\textnormal{start}}\in c_{\textnormal{start}}$:_

$\displaystyle\forall
s\in\mathcal{S},a\in\mathcal{A}^{\prime},\pi^{o}_{s_{\textnormal{start}}}(a|s)=\frac{\mu_{s,a}}{\sum_{a}\mu_{s,a}},\quad\textnormal{
then add to
dictionary}\quad\Pi^{o}(s_{\textnormal{start}})\leftarrow\pi^{o}_{s_{\textnormal{start}}}$

##### Algorithm 4 (IRL module for IRL-batch).

Compared with the IRL algorithm presented in Algorithm 1, this batched
algorithm performs IRL over a batch of starting states. As we discussed in the
above challenges, naively putting a uniform distribution over all possible
starting states would typically fail. Therefore, we enable the LP to _learn a
starting state distribution $p^{\textnormal{start}}_{s}$_ which best matches
the abstract option feature. However, the LP would again reduce to a single
starting state which best matches the abstract option. To counteract this
effect, we add a small entropy regularisation to the objective to increase the
entropy of the starting state distribution, i.e., we add
$\lambda_{2}\sum_{s}p_{s}^{\textnormal{start}}\log
p_{s}^{\textnormal{start}}$. Clearly, entropy is not a linear function. In
practise, the objective is implemented using a piecewise-linear approximation
method provided by the Gurobi optimisation package.333https://www.gurobi.com/

###  A.2 Feature-based (Variable-reward) SMDP Abstraction

In this section, we provide a general framework for feature-based abstraction
using the variable-reward SMDPs. The state mapping and action mapping
functions $f(s),g_{s}(o)$ can be defined to instantiate a new abstraction
method.

######  Definition A.1 (Abstract $\bm{\psi}$-SMDP).

Let $\mathcal{M}=\langle\mathcal{S},\mathcal{O},P,\bm{\psi},\gamma\rangle$ be
a ground $\bm{\psi}$-SMDP. We say that
$\bar{\mathcal{M}}=\langle\bar{\mathcal{S}},\bar{\mathcal{O}},\bar{P},\bar{\bm{\psi}},\gamma\rangle$
is an _abstract $\bm{\psi}$-SMDP of $\mathcal{M}$_ if there exists (1) a state
abstraction mapping $f\colon\mathcal{S}\rightarrow\bar{\mathcal{S}}$ which
maps each ground state to an abstract state, (2) a weight function
$w\colon\mathcal{S}\rightarrow[0,1]$ over the ground states such that
$\forall{\bar{s}}\in\bar{\mathcal{S}},\sum_{s\in f^{-1}({\bar{s}})}w_{s}=1$,
(3) a state-dependent option abstraction mapping
$g_{s}\colon\mathcal{O}\rightarrow\bar{\mathcal{O}}$, and (4) the abstract
transition dynamics and features are

$\bar{P}_{{\bar{s}},{\bar{s}}^{\prime}}^{{\bar{o}}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}\sum\limits_{s^{\prime}\in
f^{-1}{({\bar{s}}^{\prime})}}\\!\\!\\!\\!\\!P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}})}\textnormal{
, and
}\quad\bar{\bm{\psi}}_{{\bar{s}}}^{{\bar{o}}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}\bm{\psi}_{s}^{g^{-1}_{s}({\bar{o}})}.$

###  A.3 Reward-based MDP and SMDP abstraction

In the following we define the abstract MDP and abstract SMDPs, following the
conventional notations of Li et al. [2006]; Abel et al. [2016]; Ravindran and
Barto [2003].

######  Definition A.2 (Abstract MDP).

Let $\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,r,\gamma\rangle$ be a ground
MDP. We say that
$\bar{\mathcal{M}}=\langle\bar{\mathcal{S}},\mathcal{A},\bar{P},\bar{r},\gamma\rangle$
is an _abstract MDP of $\mathcal{M}$_ if there exists (1) a state abstraction
mapping $f\colon\mathcal{S}\rightarrow\bar{\mathcal{S}}$, which maps each
ground state to an abstract state, (2) a weight function
$w\colon\mathcal{S}\rightarrow[0,1]$ for the ground states such that
$\forall{\bar{s}}\in\bar{\mathcal{S}}$, $\sum_{s\in
f^{-1}({\bar{s}})}w_{s}=1$, and (3) a state-dependent action mapping
$g_{s}\colon\mathcal{A}\rightarrow\bar{\mathcal{A}}$, the abstract transition
dynamics and rewards are defined as

$\bar{P}_{{\bar{s}},{\bar{s}}^{\prime}}^{\bar{a}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}\sum\limits_{s^{\prime}\in
f^{-1}({\bar{s}}^{\prime})}\\!\\!\\!\\!\\!P_{s,s^{\prime}}^{g_{s}^{-1}({\bar{a}})}\textnormal{
, and}\quad\bar{r}_{{\bar{s}}}^{\bar{a}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}r_{s}^{g^{-1}_{s}({\bar{a}})}.$

In cases in which multiple ground actions map to the same abstract action,
$g^{-1}_{s}({\bar{a}})$ picks one of the ground actions. $g_{s}$ is commonly
defined as the identity mapping Li et al. [2006]; Abel et al. [2016]. We now
generalize this definition to abstract SMDPs:

######  Definition A.3 (Abstract SMDP).

Let $\mathcal{M}=\langle\mathcal{S},\mathcal{O},P,r,\gamma\rangle$ be a ground
SMDP. We say that
$\bar{\mathcal{M}}=\langle\bar{\mathcal{S}},\bar{\mathcal{O}},\bar{P},\bar{r},\gamma\rangle$
is an _abstract SMDP of $\mathcal{M}$_ if there exists (1) a state abstraction
mapping $f\colon\mathcal{S}\rightarrow\bar{\mathcal{S}}$ which maps each
ground state to an abstract state, (2) a weight function
$w\colon\mathcal{S}\rightarrow[0,1]$ over the ground states such that
$\forall{\bar{s}}\in\bar{\mathcal{S}},\sum_{s\in f^{-1}({\bar{s}})}w_{s}=1$,
(3) a state-dependent option abstraction mapping
$g_{s}\colon\times\mathcal{O}\rightarrow\bar{\mathcal{O}}$, and (4) the
abstract transition dynamics and rewards are

$\bar{P}_{{\bar{s}},{\bar{s}}^{\prime}}^{{\bar{o}}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}\sum\limits_{s^{\prime}\in
f^{-1}{({\bar{s}}^{\prime})}}\\!\\!\\!\\!\\!P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}})}\textnormal{
, and }\quad\bar{r}_{{\bar{s}}}^{{\bar{o}}}=\\!\\!\\!\\!\\!\sum\limits_{s\in
f^{-1}({\bar{s}})}\\!\\!\\!\\!\\!w_{s}r_{s}^{g^{-1}_{s}({\bar{o}})}.$

In cases in which multiple ground options map to the same abstract option,
$g^{-1}_{s}({\bar{o}})$ picks one of the ground options, e.g., the option of
shortest duration, maximum entropy, etc.

###  A.4 Relation to Other MDP Abstraction Methods

The framework of MDP abstraction was first introduced by Dean and Givan [1997]
through stochastic bisimulation, and Ravindran and Barto [2002] extended it to
MDP homomorphisms. Later, Li et al. [2006] classified exact MDP abstraction
into 5 categories and Abel et al. [2016] formulated their approximate
counterparts: model-irrelevance, $Q^{\pi}$-irrelevance, $Q^{*}$-irrelevance,
$a^{*}$-irrelevance and $\pi^{*}$-irrelevance abstractions. Our successor
homomorphism follows the formulation of MDP homomorphism Ravindran and Barto
[2003], which broadly fall into the category of model-irrelevance abstraction,
where states are aggregated according to their one-step/multi-step transition
dynamics and rewards. On the other hand, abstraction schemes which aggregate
states according to their Q-values are $Q^{*}$-irrelevance abstraction and
$a^{*}$ abstraction, where $Q^{*}$ aggregate states according to all actions,
while $a^{*}$ aggregate states with the same optimal action and Q-value, cf.
Figure 1 for an illustration of the induced abstract MDPs. Different from
prior abstraction formulations (Definition A.2) which are reward-based, our
feature-based successor homomorphism produces abstract models with meaningful
temporal semantics, and is robust under task changes. Furthermore, we include
a generic formulation of feature-based (variable-reward) abstraction
(Definition A.1), which provides a basis for potential feature-based
abstractions other than successor homomorphism.

###  A.5 Proof for Theorem 4.1

See 4.1

###### Proof.

Given $\epsilon$-Approximate Successor Homomorphism: $h=(f(s),g_{s}(o),w_{s})$
from ground $\bm{\psi}$-SMDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{O},P,\bm{\psi},\gamma\rangle$ to
abstract $\bm{\psi}$-SMDP
$\bar{\mathcal{M}}=\langle\bar{\mathcal{S}},\bar{\mathcal{O}},\bar{P},\bm{\psi},\gamma\rangle$,
such that $\forall s_{1},s_{2}\in\mathcal{S},o_{1},o_{2}\in\mathcal{O}$,
$h(s_{1},o_{1})=h(s_{2},o_{2})\implies$

$\displaystyle|\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}P_{s_{1},s_{j}}^{o_{1}}-\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}P_{s_{2},s_{j}}^{o_{2}}|$
$\displaystyle\leq\epsilon_{P}$ (12)
$\displaystyle|\bm{\psi}_{s_{1}}^{o_{1}}-\bm{\psi}_{s_{2}}^{o_{2}}|$
$\displaystyle\leq\epsilon_{\bm{\psi}}$ (13)

The abstract transition dynamics and features are

$\displaystyle P_{{\bar{s}},{\bar{s}}^{\prime}}^{{\bar{o}}}=\sum_{s\in
f^{-1}({\bar{s}})}w_{s}\sum_{s^{\prime}\in
f^{-1}({\bar{s}}^{\prime})}P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}})},\textnormal{
and }\bm{\psi}_{{\bar{s}}}^{{\bar{o}}}=\sum_{s\in
f^{-1}({\bar{s}})}w_{s}\bm{\psi}_{s}^{g^{-1}_{s}({\bar{o}})}.$ (14)

We show that given features
$\bm{\theta}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$ in the
underlying (feature-based) MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,\bm{\theta},\gamma\rangle$, and
linear reward function on the features $w_{r}\in\mathbb{R}^{d}$, the
difference in value of the optimal policy in the induced abstract SMDP and the
ground SMDP is bounded by $\frac{2\kappa}{(1-\gamma)^{2}}$, where
$\kappa=|w_{r}|(2\epsilon_{\bm{\psi}}+\frac{\epsilon_{P}|\bar{\mathcal{S}}|\max_{s,a}|\bm{\theta}(s,a)|}{1-\gamma}).$

To show the above error bound, we extend the proof of Abel et al. [2016] for
the error bound induced by approximate MDP abstraction, which follows the
following three steps:

_Step 1: Show that $\forall
s_{1}\in\mathcal{S},o_{1}\in\mathcal{O},{\bar{s}}=f(s_{1}),{\bar{o}}=g(o_{1})\implies|Q({\bar{s}},{\bar{o}})-Q(s_{1},o_{1})|\leq\frac{\epsilon}{1-\gamma}.$_

$\displaystyle
r_{{\bar{s}}}^{{\bar{o}}}=w_{r}^{T}\bm{\psi}_{{\bar{s}}}^{{\bar{o}}}=\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}w_{r}^{T}\bm{\psi}_{s_{i}}^{g^{-1}_{s_{i}}({\bar{o}})}=\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}r_{s_{i}}^{g^{-1}_{s_{i}}({\bar{o}})}\textnormal{
denote }r_{s_{i}}^{g^{-1}_{s_{i}}({\bar{o}})}\textnormal{ as
}w_{s_{i}}r_{s_{i}}^{o_{i}}$ (15) $\displaystyle
Q({\bar{s}},{\bar{o}})=\mathbb{E}[r_{{\bar{s}}}^{{\bar{o}}}+\gamma^{k}\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})]\stackrel{{\scriptstyle\textnormal{Eq.}\eqref{eq_proof:abstraction},\eqref{eq_proof:r}}}{{=}}\\!\\!\\!\\!\\!\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}r_{s_{i}}^{o_{i}}+\\!\\!\\!\\!\\!\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\\!\\!\\!\\!\\!P_{s_{i},s_{j}}^{g^{-1}({\bar{o}})}\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})$
(16) $\displaystyle
Q(s_{1},o_{1})=\mathbb{E}[r_{s_{1}}^{o_{1}}+\gamma^{k}\max_{o^{\prime}_{j}}Q(s^{\prime}_{j},o^{\prime}_{j})]=r_{s_{1}}^{o_{1}}+\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}P_{s_{1},s_{j}}^{o_{1}}\max_{{\bar{o}}^{\prime}}Q(s_{j},o^{\prime}_{j})$
(17) $\displaystyle|Q({\bar{s}},{\bar{o}})-Q(s_{1},o_{1})|$ (18)
$\displaystyle=|\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}(r_{s_{i}}^{o_{i}}-r_{s_{1}}^{o_{1}})+\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\left(P_{s_{i},s_{j}}^{g^{-1}_{s_{i}}({\bar{o}})}\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})-P_{s_{1},s_{j}}^{o_{1}}\max_{o^{\prime}_{j}}Q(s^{\prime}_{j},o^{\prime}_{j})\right)|$
(19) $\displaystyle\leq\underbrace{|\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}w^{T}_{r}(\bm{\psi}_{s_{i}}^{o_{i}}-\bm{\psi}_{s_{1}}^{o_{1}})|+|\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\left(P_{s_{i},s_{j}}^{g^{-1}_{s_{i}}({\bar{o}})}\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})-P_{s_{1},s_{j}}^{o_{1}}\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})\right)|}_{(1)}$
(20) $\displaystyle+\underbrace{|\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}P_{s_{1},s_{j}}^{o_{1}}\left(\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})-\max_{o^{\prime}_{j}}Q(s^{\prime}_{j},o^{\prime}_{j})\right)}_{(2)}|$
(21) $\displaystyle(1)$ $\displaystyle\leq
2|w_{r}|\epsilon_{\bm{\psi}}+|\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\left(P_{s_{i},s_{j}}^{g^{-1}_{s_{i}}({\bar{o}})}-P_{s_{1},s_{j}}^{o_{1}}\right)\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})|\phantom{-}$
(22) $\displaystyle\leq
2|w_{r}|\epsilon_{\bm{\psi}}+\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\epsilon_{P}\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})\leq
2|w_{r}|\epsilon_{\bm{\psi}}+|\bar{\mathcal{S}}|\epsilon_{P}\frac{|w_{r}|\max_{s,a}|\bm{\theta}(s,a)|}{1-\gamma}$
(23) $\displaystyle\textnormal{ Denote
}\kappa=|w_{r}|\left(2\epsilon_{\bm{\psi}}+\frac{|\bar{\mathcal{S}}|\epsilon_{P}\max_{s,a}|\bm{\theta}(s,a)|}{1-\gamma}\right)$
(24) $\displaystyle(2)$ $\displaystyle=\underbrace{|\sum_{s_{i}\in
f^{-1}({\bar{s}})}w_{s_{i}}}_{=1}\underbrace{\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}P_{s_{1},s_{j}}^{o_{1}}}_{(3)\leq\gamma}\left(\max_{{\bar{o}}^{\prime}}Q({\bar{s}}^{\prime},{\bar{o}}^{\prime})-\max_{o^{\prime}_{j}}Q(s^{\prime}_{j},o^{\prime}_{j})\right)|$
(25)
$\displaystyle\leq\gamma\max_{s\in\mathcal{S}}|\max_{{\bar{o}}}Q(f(s),{\bar{o}})-\max_{o}Q(s,o)|\quad\textnormal{Let
}o^{*}=\arg\max_{o}Q(s,o)$ (26)
$\displaystyle\leq\gamma\max_{s\in\mathcal{S}}|Q(f(s),g_{s}(o^{*}))-Q(s,o^{*})|\quad\textnormal{
which goes back to Equation~{}\eqref{eq_proof:q_diff}}.$ (27)

(3) is since the option lasts at least one step and terminates with
probability 1:
$\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\sum_{k=1}^{\infty}P_{s_{1},s_{j},k}^{o_{1}}=1$
Hence (3)
$=\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\sum_{k=1}^{\infty}\gamma^{k}P_{s_{1},s_{j},k}^{o_{1}}\leq\sum_{{\bar{s}}^{\prime}\in\bar{\mathcal{S}}^{\prime}}\sum_{s_{j}\in
f^{-1}({\bar{s}}^{\prime})}\gamma^{k=1}P_{s_{1},s_{j},k}^{o_{1}}=\gamma$.

$\displaystyle|Q({\bar{s}},{\bar{o}})-Q(s_{1},o_{1})|$
$\displaystyle\leq(1)+(2)$ (28)
$\displaystyle\leq\kappa+\gamma\underbrace{\max_{s\in\mathcal{S}}[|Q(f(s),g_{s}(o^{*}))-Q(s,o^{*})|}_{(4)}]\quad\textnormal{,
expand (4) again using Equation~{}\eqref{eq_proof:q_diff}}$ (29)
$\displaystyle\leq\kappa+\gamma\left(\kappa+\gamma\max_{s\in\mathcal{S}}[|Q(f(s),g_{s}(o^{*}))-Q(s,o^{*})|]\right)$
(30)
$\displaystyle\leq\kappa+\gamma\kappa+\gamma^{2}\kappa+\ldots\leq\frac{\kappa}{1-\gamma}$
(31)

_Step 2: The optimal option in the abstract MDP has a Q-value in the ground
MDP that is nearly optimal, i.e.:_

$\forall
s_{1}\in\mathcal{S},Q(s_{1},o^{*}_{1})-Q(s_{1},g^{-1}_{s_{1}}({\bar{o}}^{*}))\leq\frac{2\kappa}{1-\gamma}$
(32)

where $o^{*}_{1}=\arg\max_{o}Q(s_{1},o)\textnormal{ and
}{\bar{o}}^{*}=\arg\max_{{\bar{o}}}Q(f(s_{1}),{\bar{o}})$.

From step 1, we have
$|Q({\bar{s}},{\bar{o}})-Q(s_{1},o_{1})|\leq\frac{\kappa}{1-\gamma}$. Then, by
definition of optimality,

$\displaystyle Q({\bar{s}},g_{s_{1}}(o^{*}_{1}))\leq
Q({\bar{s}},{\bar{o}}^{*})\implies
Q({\bar{s}},g_{s_{1}}(o^{*}_{1}))+\frac{\kappa}{1-\gamma}\leq
Q({\bar{s}},{\bar{o}}^{*})+\frac{\kappa}{1-\gamma}$ (33)
$\displaystyle\textnormal{Therefore, by step 1 then by optimality:
}Q(s_{1},o^{*}_{1})\leq
Q({\bar{s}},g_{s_{1}}(o^{*}_{1}))+\frac{\kappa}{1-\gamma}\leq
Q({\bar{s}},{\bar{o}}^{*})+\frac{\kappa}{1-\gamma}$ (34)
$\displaystyle\textnormal{Again by step 1: }Q({\bar{s}},{\bar{o}}^{*})\leq
Q(s_{1},g_{s_{1}}^{-1}({\bar{o}}^{*}))+\frac{\kappa}{1-\gamma}$ (35)
$\displaystyle\textnormal{Therefore,
}Q(s_{1},o^{*}_{1})\stackrel{{\scriptstyle
Eq.\eqref{eq_proof:qg_leq_qa}}}{{\leq}}Q({\bar{s}},{\bar{o}}^{*})+\frac{\kappa}{1-\gamma}\stackrel{{\scriptstyle
Eq.\eqref{eq_proof:qa_leq_qg}}}{{\leq}}Q(s_{1},g^{-1}({\bar{o}}^{*}))+\frac{2\kappa}{1-\gamma}$
(36)

_Step 3: The optimal abstract SMDP policy yields near optimal performance in
the ground SMDP:_

Denote $g^{-1}({\bar{\pi}})$ as the ground SMDP policy implementing the
abstract SMDP policy ${\bar{\pi}}$, i.e., at state $s$, the ground option
corresponding to the abstract option ${\bar{o}}$ chosen by the abstract policy
is $g_{s}^{-1}({\bar{o}})$.

$\displaystyle
Q^{\pi^{*}}(s,o^{*})-Q^{g^{-1}({\bar{\pi}}^{*})}(s,g_{s}^{-1}({\bar{o}}^{*}))$
(37)
$\displaystyle\leq\frac{2\kappa}{1-\gamma}+Q^{\pi^{*}}(s,g_{s}^{-1}({\bar{o}}^{*}))-Q^{g^{-1}_{s}({\bar{\pi}}^{*})}(s,g^{-1}({\bar{o}}^{*}))\textnormal{
, by step 2}$ (38)
$\displaystyle=\frac{2\kappa}{1-\gamma}+[r_{s}^{g^{-1}_{s}({\bar{o}}^{*})}+\sum_{s^{\prime}\in
S}P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}}^{*})}Q^{\pi^{*}}(s^{\prime},o^{*}_{s^{\prime}})]-[r_{s}^{g^{-1}_{s}({\bar{o}}^{*})}+\sum_{s^{\prime}\in
S}P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}}^{*})}Q^{g^{-1}({\bar{\pi}}^{*})}(s^{\prime},g^{-1}(o^{*}_{{\bar{s}}^{\prime}}))]$
(39) $\displaystyle=\frac{2\kappa}{1-\gamma}+\underbrace{\sum_{s^{\prime}\in
S}P_{s,s^{\prime}}^{g^{-1}_{s}({\bar{o}}^{*})}}_{\textnormal{(1)}\leq\gamma}[Q^{\pi^{*}}(s^{\prime},o^{*}_{s^{\prime}})-Q^{g^{-1}({\bar{\pi}}^{*})}(s^{\prime},g^{-1}_{s^{\prime}}(o^{*}_{{\bar{s}}^{\prime}}))]$
(40) $\displaystyle\leq\frac{2\kappa}{1-\gamma}+\gamma\max_{s^{\prime}\in
S}[|Q^{\pi^{*}}(s^{\prime},o^{*}_{s^{\prime}})-Q^{g^{-1}({\bar{\pi}}^{*})}(s^{\prime},g^{-1}_{s^{\prime}}(o^{*}_{{\bar{s}}^{\prime}}))|]$
(41)
$\displaystyle\stackrel{{\scriptstyle\textnormal{Eq.}\eqref{eq_proof:q_pi}}}{{\leq}}\frac{2\kappa}{1-\gamma}+\gamma\left(\frac{2\kappa}{1-\gamma}+\gamma\max_{s^{\prime}\in
S}[Q^{\pi^{*}}(s^{\prime},g^{-1}_{s^{\prime}}(o^{*}_{{\bar{s}}^{\prime}}))-Q^{g^{-1}_{s^{\prime}}({\bar{\pi}}^{*})}(s^{\prime},g^{-1}(o^{*}_{{\bar{s}}^{\prime}}))]\right)$
(42)
$\displaystyle\leq\frac{2\kappa}{1-\gamma}+\gamma\frac{2\kappa}{1-\gamma}+\gamma^{2}\frac{2\kappa}{1-\gamma}\ldots$
(43) $\displaystyle\leq\frac{2\kappa}{(1-\gamma)^{2}}$ (44)

where (1) is because the option terminates with probability 1 and takes at
least 1 step. ∎

###  A.6 Additional Experiment Details

####  A.6.1 Additional details on the experimental settings

(a) 2 Rooms, 157 states (b) 3 Rooms, 487 states (c) 4 Rooms (small), 348
states  (d) 4 Rooms (large), 1463 states

Figure 4: Object-room layouts used in our experiments. In each object room
instance, blue grids are the walls, orange grids are doors, and there are two
types of objects: stars and keys, which can be picked-up by the agent. The
agent can pick up a key and use it to open a door.

_Object-Rooms_ : $N$ rooms are connected by doors with keys and stars inside.
There are 6 actions, i.e., $\mathcal{A}=\\{$Up, Down, Left, Right, Pick up,
Open$\\}$. The agent can pick up the keys and stars, and use a key to open a
door next to it. The agent starts from the (upper) left room.

_Settings for Table 1:_ The source room where the agent demonstrates and
encodes the abstract options is the 2 Room variant. The 2-4 target rooms
setting used for grounding the options are the 2 Rooms in Figure 4 (a), 3
Rooms in Figure 4 (b), and 4 Rooms (large) in Figure 4 (d) variants.

_Settings for Figure 1 and Figure 11:_ The abstract $\bm{\psi}$-SMDP is
generated using the setting 4 Room (small) in Figure 4 (c), where the first 3
rooms each contain a key and a star is in the final room. For Figure 11, the
task specifications are as follows: We refer to transfer as the task transfer,
i.e., change of reward function. The total reward is discounted and normalized
by the maximum reward achieved.

  * •

dense reward (no transfer): the agent receives a reward for each key picked
up, door opened, and star picked up, i.e., the reward vector $w_{r}=[1,1,1]$
over the features (key, open door, star).

  * •

sparse reward (no transfer): the agent receives a reward for each door opened,
i.e., the reward vector $w_{r}=[0,1,0]$.

  * •

transfer (w. overlap): overlap refers to the overlap between reward function
in the source and target task. In the source task, the agent receives a reward
for each key picked up, and each door opened, i.e., the reward vector
$w_{r}=[1,1,0]$. In the target task, the agent receives a reward for each door
opened and star picked up, i.e., the reward vector $w_{r}=[0,1,1]$.

  * •

transfer (w.o. overlap): In the source task, the agent receives a reward for
each star picked up, i.e., the reward vector $w_{r}=[0,0,1]$. In the target
task, the agent receives a reward for each key picked up, i.e., the reward
vector $w_{r}=[1,0,0]$.

_Settings for Figure 3 and Figure 10:_ The abstract $\bm{\psi}$-SMDP is
generated using the 3 Room setting in Figure 4 (b), where the first 2 rooms
each contains a key and a star, and the final room contains a star. For figure
3, the task specifications is the same as the above description for Figure 11.

####  A.6.2 Additional Experiment Results:

In this section, we present additional experimental results.

Figure 5: Ground options learned in the 4-Room domain via Algorithm 3
(presented in the Appendix). The features correspond to indicators of the room
centers (marked in the orange square). Hence, the ground option should move to
any one of the four room centres. The option policy accurately takes the agent
from each starting state to a nearby room centre and then terminates.

##### Classic 4-Rooms.

Figure 5 shows the ground option policy learned by _IRL-batch_ on the 4-Room
domain. The option is learned by solving $1$ linear program by _IRL-batch_ ,
i.e., the state-action visitation frequencies returned by the IRL program
corresponds to an optimal policy for all starting states. Please refer to the
figure for details of the option.

Minecraft Door-Rooms Experiments: As introduced in Section 5, to test our
batched option grounding algorithm (Algorithm 3) on new environments with
unknown transition dynamics, we built two settings in the Malmo Minecraft
environment: _Bake-Rooms_ and _Door-Rooms_. The results on Bake-Rooms can be
found in Figure 2 in the main text. Here, we present the results on the Door-
Rooms setting shown in Figure 6.

_Training and Results:_ We compare our algorithm with the following two
baselines: eigenoptions Machado et al. [2018] and random walk. For this
experiment, each agent runs for 20 iterations, with 200 steps per iteration as
follows: In the first iteration, all agents execute randomly chosen actions.
After each iteration, the agents construct an MDP graph based on collected
transitions from all prior iterations. The eigenoption agent computes $k=1$
eigenoption of the second smallest eigenvalue (Fiedler vector) using the
normalized graph Laplacian, while our algorithm grounds the $k=1$ abstract
option: _open door and go to door_. In the next iteration, the agents perform
random walks with both the primitive actions and the acquired options, update
the MDP graphs, compute new options, $\ldots$

Figure 6 shows our obtained results. Figure 6(a) shows the state visitation
frequencies of our algorithm in the 20th iteration and the constructed MDP
graph. The agent starts from the bottom room (R1), and learns to navigate
towards the door, open the door and enter the next rooms. Figures 6(b)-(d)
compare the agents in terms of the total number of states explored, number of
doors opened and the maximum distance from the starting location. Note that
the door layouts are different from the Bake-Rooms environment. Our agent
explores on average more than twice as many states as the two baselines,
quickly learns to open the doors and navigate to new rooms, while the
baselines on average only learn to open the first door and mostly stay in the
starting room.

(a) State visitation (b) number of states explored (c) number of doors opened
(d) distance from start

Figure 6: (Minecraft Door-Rooms) Exploring and grounding options in unknown
environments. 4 rooms are connected by doors, the agent starts from the
bottom, opens doors and enters the other rooms. The random agent takes random
actions. Our agent starts with an iteration of random walk, then after each
iteration, it computes the constructed MDP and fits the ”go to and open door”
option, (while the eigenoptions agent finds an eigenoption), and uses the
options for exploration in the next iteration. (a) shows the state visitation
frequency in iteration 20 of our agent (Algorithm 3), and the MDP constructed
throughout the 20 iterations. (b)-(d) compares our agent with the baselines on
the average number of the explored states, doors opened and max distance
traversed. The results are averaged over 10 seeds and shaded regions show the
standard deviation across seeds. Our agent using abstract successor options
explores on average twice as many states as the baselines, as well as quickly
learns to open doors and navigating to new rooms.

More details on Minecraft Bake-Rooms: Besides Figure 2, we now present more
details of our option grounding algorithm in environments with unknown
transition dynamics in the Minecraft Bake-Rooms experiment. Figures 7, 8 and 9
show the state visitation frequencies and MDP graph constructed over 20
iterations by our algorithm. The agent starts from the bottom room R1, a coal
dropper is in R2, a potato dropper is in R3. The rooms are connected by doors
which can be opened by the agent. For clarity of presentation, we show the
undirected graph constructed. Blue nodes denote explored states and red nodes
denote new states explored in the respective iteration.

The shown figures demonstrate that our agent learns to open the door, and open
the door and enter R2 to collect coal in iteration 2, while the eigenoptions
agent learns to collect coal in iteration 18, and the random agent collects a
coal block in iteration 14. Our agent learns to collect potato in R3 in
iteration 3, while the eigenoptions agent learns this in iteration 19, and the
random agent has not reached R3 within 20 iterations.

(a) iteration 0 (b) iteration 1 (c) iteration 2 (d) iteration 3 (e) iteration
4 (f) iteration 5 (g) iteration 6 (h) iteration 7 (i) iteration 8 (j)
iteration 9 (k) iteration 10 (l) iteration 11 (m) iteration 12 (n) iteration
13 (o) iteration 14 (p) iteration 15 (q) iteration 16 (r) iteration 17 (s)
iteration 18 (t) iteration 19

Figure 7: (Our Agent - Algorithm 3) State visitation frequencies and
constructed graph per iteration in Minecraft Bake-Rooms

(a) iteration 0 (b) iteration 1 (c) iteration 2 (d) iteration 3 (e) iteration
4 (f) iteration 5 (g) iteration 6 (h) iteration 7 (i) iteration 8 (j)
iteration 9 (k) iteration 10 (l) iteration 11 (m) iteration 12 (n) iteration
13 (o) iteration 14 (p) iteration 15 (q) iteration 16 (r) iteration 17 (s)
iteration 18 (t) iteration 19

Figure 8: (Eigenoptions Agent) State visitation frequencies and constructed
graph per iteration in Minecraft Bake-Rooms

(a) iteration 0 (b) iteration 1 (c) iteration 2 (d) iteration 3 (e) iteration
4 (f) iteration 5 (g) iteration 6 (h) iteration 7 (i) iteration 8 (j)
iteration 9 (k) iteration 10 (l) iteration 11 (m) iteration 12 (n) iteration
13 (o) iteration 14 (p) iteration 15 (q) iteration 16 (r) iteration 17 (s)
iteration 18 (t) iteration 19

Figure 9: (Random Agent) State visitation frequencies and constructed graph
per iteration in Minecraft Bake-Rooms

Additional results on abstraction: Figure 10 shows the abstract MDPs in the
Object-Rooms with $N=3$ rooms. Figure 10(a) is the abstract $\bm{\psi}$-SMDP
model induced by our approximate successor homomorphism, the colors of the
nodes match their corresponding ground states in the ground MDP shown in
Figure 10(b). The edges with temporal semantics correspond to abstract
successor options and the option transition dynamics. To avoid disconnect
graphs, we can augment the abstract successor options with shortest path
options, which connect ground states of disconnected abstract states to their
nearest abstract states. Figure 10(c) and (d) show the abstract MDPs induced
by the $Q^{*}$-irrelevance (Q-all) and $a^{*}$-irrelevance (Q-optimal)
abstraction methods, for the task _find key_. The distance threshold
$\epsilon=0.1$.

Figure 11 shows the results of using the abstract MDP for planning in the
Object-Rooms with $N=4$ rooms. Please refer to Section A.6.1 for a detailed
description of the settings. Our successor homomorphism model performs well
across all tested settings with few abstract states (number of clusters).
Since successor homomorphism does not depend on rewards, the abstract model
can transfer across tasks (with varying reward functions), and is robust under
sparse rewards settings. Whereas abstraction schemes based on the reward
function perform worse when the source task for performing abstraction is
different from the target task where the abstract MDP is used for planning.

(a) Abstract $\bm{\psi}$-SMDP

(b) Ground MDP

(c) Q-Abstraction w. All Actions

(d) Q-Abstraction w. Optimal Action

Figure 10: Abstract MDP with different abstraction schemes. (a) is the
abstract MDP induced by our proposed successor homomorphism and (b) shows how
the ground states are mapped to the abstract states. Node colors correspond to
the abstract states in (a). (c) and (d) are abstraction induced by the
$Q^{*}$-irrelevance and $a^{*}$-irrelevance abstraction schemes.

(a) no transfer (dense reward)

(b) no transfer (sparse reward)

(c) transfer (w. overlap)

(d) transfer (w.o. overlap)

(e) no transfer (dense reward)

(f) no transfer (sparse reward)

(g) transfer (w. overlap)

(h) transfer (w.o. overlap)

Figure 11: Performance of planning with the abstract MDPs. The upper row shows
the total rewards (normalized by the maximum possible total rewards) obtained,
and the lower row shows the corresponding number of abstract states of the
abstract MDP. The x-axes are the distance thresholds $\epsilon$. transfer
refers to task transfer (i.e., different reward function)