Option Transfer and SMDP Abstraction with Successor Features

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), repmove for-

ward). 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.

The appendix to this paper is available at https://hdg94.github. io/assets/img/abstractions appendix.pdf.

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 M = ⟨S, A, P, r, γ⟩, where S is a set of states the environment the agent is interacting with can be in, A is a set of actions the agent can take, P : S ×A → [0, 1]|S| is a transition kernel describing transitions between states of the MDP upon taking actions, r : S × A → R is a reward function, and γ is a discount factor. An agent's behavior can be characterized by a policy π: S → [0, 1]|A| , i.e., π(a|s) is the probability of taking action a in state s. 1

Successor Features (SF). [Barreto et al., 2017] Given features θ : S × A → Rd associated with each state-action pair, the SF ψπ s0 is the expected discounted sum of features of state-action pairs encountered when following policy π starting from s0, i.e.,

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 = ⟨I o , πo , βo ⟩, where I o ⊆ S is a set of states that an option can be initiated at (initiation set), πo : S → [0, 1]|A| is the option's policy, and βo : S → [0, 1] is the termination condition, i.e., the probability that o terminates in state s ∈ S. The transition dynamics and rewards induced by an option o are

where P(s, o, s′ , k) is the probability of transiting from s to s′ in k steps when following option policy πo and terminating in s′ , 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., M = ⟨S,O, P, r, γ⟩, where P : S × O → [0, 1]|S| are the options' transition dynamics, and r : S×O → R are the options' rewards. A family of variable-reward SMDPs [Mehta et al., 2008] (denoted as ψ-SMDP) is defined as M = ⟨S, O, P, ψ, γ⟩, where ψo s is the SF of option o starting at state s. A ψ-SMDP induces an SMDP if the reward is linear in the features, i.e., ro s = wT r ψo s .

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., ra s = wT r θ(s, a), where wr ∈ Rd 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's 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.

1 We only consider stationary policies in this paper.

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 {Mi}ki=1 . Therefore, we assume a feature function which maps stateaction pairs for each MDP to a shared feature space, i.e., θMi : Si ×Ai → Rd . 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 Rd , representing cumulative feature expectations that the corresponding ground options should realise.

Definition 3.1 (Abstract Successor Options, Ground Options). Let M = ⟨S,A, P, r, γ⟩ be an MDP and θM: S × A → Rd be the feature function. An abstract successor option is a vector ψ ¯ o ∈ Rd . For brevity, we will often denote ψ ¯ o ∈ Rd as ¯ o. Let gs : O → Rd denote a state-dependent mapping such that o ↦→ ψo s = E[∑kκ=0 γ κθM(St+κ,At+κ)|E(o, s, t)]. The options o ∈ g-1 s (¯ o) are referred to as ground options of ¯ o in state s.

The initiation set of an abstract successor option ¯ o can now be naturally defined as I ¯ o := {s ∈ S | ∃o: gs(o) = ψ ¯ o }. In the following section, we present an algorithm for grounding abstract successor options in an MDPMusing 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 abstract option grounding: IRL-NAIVE and IRL-BATCH, where the latter algorithm enjoys better runtime performance while achieving similar grounding performance (cf. experiments).

IRL-NAIVE (Algorithm 1). is a naive algorithm for grounding an abstract option ¯ o. The algorithm uses feature matching based IRL to find for each possible starting state sstart an option realizing the feature vector ψ ¯ o . First, we create an augmented MDP which enables termination of options. To do this, we augment the action space with a terminate action aT and append a null state snull to the state space. Specifically, aT 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., θ(snull, ·) = 0. With the augmented MDP, we can compute an option policy via IRL. Several IRL formulations exist, and we adopt the linear programming (LP) approach by [Syed et al., 2008] (Algorithm 2

Algorithm 1 Option Grounding (IRL-NAIVE)

Input:M=⟨S, A, P, r, γ⟩, abstract option ¯ o, ϵthresh. Output: initiation set I ¯ o , dict. of ground option policies Π¯ o

• o , dict. of termination probabilities Ξ¯ 1: // Construct augmented MDP 2: S ′ ←S ∪ {snull},A′ ←A∪ {aT}, P ′ ←P 3: ∀s ∈ S ′ : P ′ (snull|s, aT) = 1 4: ∀a ∈ A′ : P ′ (snull | snull, a) = 1 5: // Find ground options 6: for all sstart ∈ S, do 7: ϵ, πo sstart ← IRL(S ′ , A′ , P ′ , γ, sstart , ψ ¯ o ) 8: if ϵ ≤ ϵthresh. then 9: I ¯ o ← I ¯ o ∪ {sstart} 10: Π¯ o (sstart) = πo sstart 11: Ξ¯ o (sstart) = βo , where βo (s) = πo sstart (aT|s) 12: end if 13: end for 14: return I ¯ o , Π¯ o , Ξ¯ o

in Appendix A.1). Specifically, the LP approach finds discounted visitation frequencies for all state-action pairs such that the induced feature expectations match the abstract successor option. Then the option policy πo (including option termination) can be deduced from the state-action visitation frequencies. Finally, if the discrepancy ϵ of the successor feature of the learned option and the abstract option is below a specified threshold ϵthresh., the start state sstart 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 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.

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 as follows: first find the abstract successor option ¯ o by computing the ground option's successor feature in the source environment, and then ground ¯ o in the target environment using the IRL-NAIVE or IRL-BATCH algorithm, i.e., obtain o′ ∈ g-1 s (¯ o). 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 ¯O, we start with an iteration of a random walk which constructs an approximate MDP ˜M0. In each subsequent iteration k, we ground the abstract options using ˜Mk-1, and update the MDP ˜Mk 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.

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 ψ-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 ψ-SMDPs. We show that planning with these abstract ψ-SMDPs yields nearoptimal performance. Moreover, the abstract ψ-SMDPs can inherit meaningful semantics from the options, cf. Fig. 1.

Specifically, an abstract ψ-SMDP is a tuple ¯M = ⟨ ¯ S, ¯O, ¯ P, ¯ ψ, γ⟩, where ¯ S is a set of abstract states, ¯O are the abstract options, whose transition dynamics between the abstract states are described by ¯ P ¯ o ¯ s,¯ s′ , and ¯ ψ ¯ o ¯ s is the SF of executing ¯ o from ¯ s. A successor homomorphism h = (f(s), gs(o), ws) maps a (ground) ψ-SMDP to an abstract ψSMDP, where f(s) aggregates ground states with approximately equal option transition dynamics into abstract states, gs(o) is our state-dependent mapping between ground and abstract options, and ws is a weight function which weighs the aggregated ground states towards each abstract state.

Definition 4.1 (ϵ-Approximate Successor Homomorphism). Let h = (f(s), gs(o),ws) be a mapping from a ground ψ-SMDP M = ⟨S,O, P,ψ, γ⟩ to an abstract ψ-SMDP ¯M = ⟨ ¯ S, ¯O, ¯ P, ¯ ψ, γ⟩, where f : S → ¯ S, gs : O → ¯O and w: S → [0, 1] s.t. ∀¯ s ∈ ¯ S, ∑s∈f -1 (¯ s) ws = 1. h is an (ϵP , ϵψ)-approximate successor homomorphism if for ϵP , ϵψ > 0, ∀s1, s2 ∈ S, o1, o2 ∈ O,

Having defined the abstract states, the transition dynamics and features of the abstract ψ-SMDP ¯Mcan be computed by:

where ∑s′′∈f -1 (f(s′ )) P o s,s′′ refers to the transition probability from ground state s to an abstract state ¯ s′ = f(s′ ) 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(s1, o1) = h(s2, o2) =⇒ ∀s′ ∈ S,

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 (¯ o) picks one of the ground options. An example abstract ψ-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 multistep 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 ψ-SMDP with semantic meanings obtained from the options. Furthermore, each abstract ψ-SMDP instantiates a family of abstract SMDPs (cf. Def. A.3, Appendix A.3) by specifying a task, i.e., reward weight wr on the features. Extending results from [Abel et al., 2016; Abel et al., 2020] to our setting, we can guarantee performance of planning with the abstract ψ-SMDP across different tasks.

Theorem 4.1. Let wr ∈ Rd be a reward vector such that ra s = wT r θ(s, a). Under this reward function, the value of an optimal abstract policy obtained through the (ϵP , ϵψ)- approximate successor homomorphism is close to the optimal ground SMDP policy, where the difference is bounded

5 Experiments

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.

Transfer to Environments with Known Dynamics

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

· 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 baked potatos in inventory demonstration as an abstract option, then grounding the abstract option in the target environment.

· 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 with keys and stars inside are connected by doors. There are 6 actions: 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.

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×3 grids, and the items in inventory.

Baselines and learning. We compare our algorithm IRLBATCH 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 14th 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) show 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 ψ-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(s1) = f(s2), then ∀a, |Q∗ (s1, a) - Q∗ (s2, a)| ≤ ϵ, where Q∗ (s, a) is the optimal Q-function for the considered MDP.

2. Q (optimal): (a∗ -irrelevance abstraction), if f(s1) = f(s2) then s1 and s2 share the same optimal action a∗ and |Q∗ (s1, a∗ ) - Q∗ (s2, a∗ )| ≤ ϵ.

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

maxs′ ,¯ o |P g-1 s1 (¯ o) s1,s′ -P g-1 s2 (¯ o) s2,s′ | 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∗ (s1, ·) -Q∗ (s2, ·)|∞ for the Q (all) approach, then compute the abstract transition dynamics.

Figure 3 shows the results of using the induced abstract models for planning. Ours performwell across all tested settings with few abstract states. Since abstract ψ-SMDPs do not depend on rewards, the abstract model is robust across tasks (with varying reward functions) and sparse rewards settings. In contrast, abstraction schemes based on the reward functions perform worse when the source task for performing abstraction is different from the target task for planning.

6 RelatedWork

Agent-space options [Konidaris and Barto, 2007] are one of our conceptual inspirations. In our work, we tie the agentspace to the problem-space through features.

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 rewardbased abstractions in SMDPs in [Abel et al., 2020]. Different from prior abstraction formulations which are rewardbased, 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 the successor homomorphism, which produces abstract ψ-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 ψ-SMDP models exhibit meaningful temporal semantics, with near-optimal planning performance across tasks.