Temporally Abstract Partial Models
Year: 2021

Abstract:
Humans and animals have the ability to reason and make predictions about different courses of action at many time scales. In reinforcement learning, option models (Sutton, Precup & Singh, 1999; Precup, 2000) provide the framework for this kind of temporally abstract prediction and reasoning. Natural intelligent agents are also able to focus their attention on courses of action that are relevant or feasible in a given situation, sometimes termed affordable actions. In this paper, we define a notion of affordances for options, and develop temporally abstract partial option models, that take into account the fact that an option might be affordable only in certain situations. We analyze the trade-offs between estimation and approximation error in planning and learning when using such models, and identify some interesting special cases. Additionally, we empirically demonstrate the ability to learn both affordances and partial option models online resulting in improved sample efficiency and planning time in the Taxi domain.

heading: 1 Introduction
text: Intelligent agents flexibly reason about the applicability and effects of their actions over different time scales, which in turn allows them to consider different courses of action. Yet modeling the entire complexity of a realistic environment is quite difficult and requires a lot of data (Kakade et al., 2003). Animals and people exhibit a powerful ability to control the modelling process by understanding which actions deserve any consideration at all in a situation. By anticipating only certain aspects of their effects over different time horizons may make models more predictable or easier to learn. In this paper we develop the theoretical underpinnings of how such an ability could be defined and studied in sequential decision making. We work in the context of model-based reinforcement learning (MBRL) (Sutton and Barto, 2018) and temporal abstraction in the framework of options Sutton et al. (1999). Theories of embodied cognition and perception suggest that humans are able to represent the world knowledge in the form of internal models across different time scales (Pezzulo and Cisek, 2016). Option models provide a framework for RL agents to exhibit the same capability. Options define a way of behaving, including a set of states in which an option can start, an internal policy that is used to make decisions while the option is executing, and a stochastic, state-dependent termination condition. Models of options predict the (discounted) reward that an option would receive over time and the (discounted) probability distribution over the states attained at termination (Sutton et al., 1999). Consequently, option models enable the extension of dynamic programming and many other RL planning methods in order to achieve temporal abstraction, i.e. to be able to consider seamlessly different time scales of decision-making.
Much of the work on learning and planning with options considers the case where they apply everywhere (Bacon et al., 2017; Harb et al., 2017; Harutyunyan et al., 2019b,a), with some notable recent exceptions which generalize the notion of initiation sets in the context of function approximation (Khetarpal et al., 2020b). Having options that are partially defined is very important in order to control the complexity of the planning and exploration process. However, the notion of partially defined option models, which make predictions only from a subset of states is the focus of our paper.
∗Correspondence to khimya.khetarpal@mail.mcgill.ca
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In natural intelligence, the ability to make predictions across different scales is linked with the ability to understand the action possibilities (i.e. affordances) (Gibson, 1977) which arise at the interface of an agent and an environment and are a key component of successful adaptive control (Fikes et al., 1972; Korf, 1983; Drescher, 1991; Cisek and Kalaska, 2010). Recent work (Khetarpal et al., 2020a) has described a way to implement affordances in RL agents, by formalizing a notion of intent over state space, and then defining an affordance as the set of state-action pairs that achieve that intent to a certain degree. One can then plan with partial, approximate models that map affordances to intents, incurring a quantifiable amount of error at the benefit of faster learning and deliberation. In this paper, we generalize the notion of intents and affordances to option models. As we will see in Sec. 3, this is non-trivial and requires carefully inspecting the definition of option models. The resulting temporally abstract models are partial, in the sense that they apply only in certain states and options.
Key Contributions. We present a framework defining temporally extended intents, affordances and abstract partial option models (Sec. 3). We derive theoretical results quantifying the loss incurred when using such models for planning, exposing trade-offs between single-step models and full option models (Sec. 4). Our theoretical guarantees provide insights and decouple the role of affordances from temporal abstraction. Empirically, we demonstrate end-to-end learning of affordances and partial option models, showcasing significant improvement in final performance and sample efficiency when used for planning in the Taxi domain (Sec. 5).

heading: 2 Background
text: In RL, a decision-making agent interacts with an environment through a sequence of actions, in order to learn a way of behaving (aka policy) that maximizes its value, i.e. long-term expected return (Sutton and Barto, 2018). This process is typically formalized as a Markov Decision Process (MDP). A finite MDP is a tuple M = 〈S,A, r, P, γ〉, where S is a finite set of states, A is a finite set of actions, r : S × A → [0, Rmax] is the reward function, P : S × A → Dist(S) is the transition dynamics, mapping state-action pairs to a distribution over next states, and γ ∈ [0, 1) is the discount factor. At each time step t, the agent observes a state st ∈ S and takes an action at ∈ A drawn from its policy π : S → Dist(A) and, with probability P (st+1|st, at), enters the next state st+1 ∈ S while receiving a numerical reward r(st, at). The value function of policy π in state s is the expectation of the long-term return obtained by executing π from s, defined as: V π(s) = E [∑∞ t=0 γ tr(St, At) ∣∣S0 = s,At ∼ π(·|St), St+1 ∼ P (·|St, At) ∀t]. The goal of the agent is to find an optimal policy, π∗ = arg maxπ V π. If the model of the MDP, consisting of r and P , is given, the value iteration algorithm can be used to obtain the optimal value function, V ∗, by computing the fixed-point of the Bellman equations (Bellmann, 1957): V ∗(s) = maxa ( r(s, a) + γ ∑ s′ P (s ′|s, a)V ∗(s′) ) ,∀s. The optimal policy π∗ can be obtained by acting greedily with respect to V ∗.
Semi-Markov Decision Process (SMDP). An SMDP (Puterman, 1994) is a generalization of MDPs, in which the amount of time between two decision points is a random variable. The transition model of the environment is therefore a joint distribution over the next decision state and the time, conditioned on the current state and action. SMDPs obey Bellman equations similar to those for MDPs.
Options. Options (Sutton et al., 1999) provide a framework for temporal abstraction which builds on SMDPs, but also leverages the fact that the agent acts in an underlying MDP. A Markovian option o is composed of an intra-option policy πo, a termination condition βo : S → Dist(S), where βo(s) is the probability of terminating the option upon entering s, and an initiation set Io ⊆ S. Let Ω be the set of all options. In this document, we will use O ⊂ Ω to denote the set of options available to the agent and O(s) = {o|s ∈ Io} denote the set of options available at state s. In call-and-return option execution, when an agent is at a decision point, it examines its current state s, chooses o ∈ O(s) according to a policy over options πΩ(s), then follows the internal policy πo, until the option terminates according to βo. Termination yields a new decision point, where this process is repeated.
Option Models. The model of an option o predicts its reward and transition dynamics following a state s ∈ Io, as follows: r(s, o) . = E[Rt+1 + γRt+2 + · · · + γk−1Rt+k|St = s,Ot = o], and p(s′|s, o) .= ∑∞ k=1 Pr(Sk = s ′, Tk = 1, T0<i<k = 0|S0 = s,A0:k−1 ∼ πo, T0:k−1 ∼ βo) =
∑∞ k=1 γ
kp(s′, k|s, o), where Ti is an indicator variable equal to 1 if the option terminates upon entering state i, and 0 otherwise. p(s′, k|s, o) is the probability that option o terminates in s′ after exactly k time-steps, given that it started at s. Bellman optimality equations can then be expressed in terms of option models. The optimal state value function and state-option value function, V ∗Ω and Q∗Ω, are defined as follows:
V ∗Ω(s) = max o∈O(s) Q∗Ω(s, o) and Q ∗ Ω(s, o) = r(s, o) + ∑ s′ p(s′|s, o) max o′∈O(s′) Q∗Ω(s ′, o′).
Partial Models. MBRL methods build reward and transition models from data, which are then used to plan, e.g. by using the Bellman equations. However, learning an accurate model can be quite difficult, requiring a lot of data. Moreover, the model does not need to be accurate everywhere, as long as it is accurate in relevant places, and/or it provides useful information for identifying good actions. A useful approach is to build partial models (Talvitie and Singh, 2009), which only make predictions for specific parts of the observation-action space. Partial models come in two flavors: predicting only the outcome of a subset of state-action pairs, or making predictions only about certain parts of the observation space. Option models can be interpreted as partial models, of the first type, because they are defined only on states where the option applies.
Affordances. Gibson (1977) coined the term “affordances” to describe the fact that certain states enable certain actions, in the context of embodied agents. For instance, a chair “affords” sitting for humans, water “affords” swimming for fish, etc. As a result, affordances are a function of the environment as well as the agent, and emerge out of their interaction. In the context of Object Oriented-MDPs (Diuk et al., 2008), Abel et al. (2014, 2015) define affordances as propositional functions on states, which assume the existence of objects and object class descriptions. We build on a more general notion of affordances in MDPs (Khetarpal et al., 2020a), defined as a relation between states and actions, where an action is affordable in a state if its desired outcome (i.e. intent) is likely to be achieved.

heading: 3 Affordances for Temporal Abstractions
text: We seek to reduce both the planning complexity when using option models, and the sample complexity of learning such models, by actively eliminating from consideration choices that are unlikely to improve the planning outcome. In particular, we build temporally abstract partial models informed by affordances. Previous work (Khetarpal et al., 2020a) has formalized affordances in RL by considering the desired outcome of a primitive action, i.e. the intent associated with the action. We will now generalize this notion to intents for options, which can be achieved over the duration of the option. To make this idea concrete, consider the example of a taxicab, which needs to pick up passengers from given locations and drop them off at a desired destination. As discussed in Dietterich (2000), the use of abstraction, in both state space and time, can help solve this problem. In this context, an option could be to navigate at a particular grid location and an intent would be to pick up a passenger, or to drop off the passenger currently in the car at the desired destination. Such an intent limits the
space of possible options under consideration to those that have desired consequences. These intents capture long-term desired consequences of executing options.
Given the generalization of intents to temporal abstraction, the notion of affordance can still be defined similarly to the primitive action case in Khetarpal et al. (2020a), by including state-option pairs which achieve the intent to a certain degree. Indeed, primitive affordances will be a special case of option affordances. Some examples of affordances for our illustration are depicted in Fig. 1. An agent can then build partial models of only affordable options enabling it to not only “navigate in the affordance landscape” (Pezzulo and Cisek, 2016), but also to better gauge action choices (Cisek and Kalaska, 2010).

heading: 3.1 Trajectory Based Option Models
text: In order to justify the upcoming definitions, we will start with a slight re-writing of the option models in terms of trajectories. A trajectory τ(t) is a random variable, denoting a state-action sequence of length t ≥ 1, τ(t) = 〈S0, A0, . . . St−1, At−1, St〉. Overloading notation, let τ(s, t) denote a trajectory of length t for which S0 = s. Further, let τ(s, t, s′) be a trajectory of length t with S0 = s and St = s′ and τ(s, s′) a trajectory of any length t for which S0 = s and St = s′. The return is then a deterministic function of a trajectory: G(τ) = ∑|τ |−1 k=0 γ
kr(Sk, Ak), where |τ | is the length of the trajectory. The probability of observing a given trajectory 〈s, a0 . . . st〉, s ∈ Io, under option o is:
P (τ=〈s0,a0...st〉|o)= ( t−1∏ k=0 πo(Ak=ak|Sk=sk)P (Sk+1=sk+1|Sk=sk,Ak=ak)(1−βo(sk+1)) ) βo(st) 1−βo(st)
where the last fraction is there just to capture correctly termination at t. To simplify notation, we denote this by Po(τ(s, t)). We can define analogously the probability of a trajectory being generated by o starting at state s ∈ Io and ending at a given state s′ after t steps by Po(τ(s, t, s′)). The probability of a trajectory of any length τ(s, s′) under o is then: Po(τ(s, s′)) = ∑∞ t=1 Po(τ(s, t, s
′)) Let T (s, t, s′) denote the set of all trajectories starting at s, ending at s′ and of length t and T (s, s′) = ∪tT (s, t, s′). We can write the undiscounted transition model of an option o as:
P (s′|s, o) = ∑ τ(s,s′)∈T (s,s′) Po(τ(s, s ′))
The discount on a trajectory τ will be denoted γ(τ). If the discount factor is fixed per time step, this will simply be γ|τ |; all trajectories of the same length will have the same discount, which will allow us to factor it out of products.
The reward model of an option is: r(s, o, s′) = ∑∞ t=1 ∑ τ(s,t,s′)∈T (s,t,s′) Po(τ(s, t, s ′))G(τ(s, t, s′))
The expected discount for option o on a trajectory going from s to s′ is defined as:
γo(s, s ′) = ∑∞ t=1 ∑ τ(s,t,s′)∈T (s,t,s′) Po(τ(s, t, s ′))γt
Note that when the action is a primitive action, then γo(s, s′) = ∑ s′ P (s
′|s, o)γ We can re-write the optimal value function of an option as:
Q∗(s, o) = ∑ s′∈S ∞∑ t=1 ∑ τ(s,t,s′) P (τ(s, t, s′)|o)[G(τ(s, t, s′)) + γ(τ(s, t, s′)) max o′ Q∗(s′, o′)]
Note that the order of the two outer sums can be reversed. This form is equivalent to the one in Sutton et al. (1999), but will be more useful for our results.

heading: 3.2 Option Affordances
text: We will now define an intent through a desired probability distribution in the space of all possible trajectories of an option. The goal will be to obtain a strict generalization of the results established in Khetarpal et al. (2020a) for primitive actions, in the case where each action is an option and β(s) = 1, ∀s.
Definition 1 (Temporally Extended Intent I→o ): A temporally extended intent of option o ∈ Ω, I→o : S → Dist(T ) specifies for each state s, a probability distribution over the space of trajectories
T , describing the intended result of executing o in s. The associated intent model will be denoted by PI(τ |s, o) = I→o (s, τ). A temporally extended intent I→o is satisfied to a degree, ζs,o at state s ∈ S and option o ∈ Ω if and only if:
d(PI(τ |s, o), Po(τ(s)))≤ ζs,o, (1)
where d is a metric between probability distributions2, and τ(s, o) denotes the trajectory starting in state s and following the option o.
We note that primitive actions have a “degenerate" trajectory, consisting of only the next state. Hence, the only reasonable choice there is to define intent based on the next-state distribution, as done in Khetarpal et al. (2020a). However, options have a whole trajectory, and defining intents on the trajectory distribution provides maximum flexibility. In practice, we expect that most useful intents would be defined in relation with the endpoint of the option, e.g. specifying an intended distribution over the state at the end of the option, or over the joint distribution of the state and duration. Further discussion of special cases is included in the Appendix. Based on this notion of temporally extended intents, affordances for options can be defined as follows:
Definition 2 (Option Affordances AFI→): Given a set of options O ⊆ Ω and set of temporally extended intents I→ = ∪o∈OI→o , and ζI
→ ∈ [0, 1], we define the affordances AFI→ associated with I→ as a relation AFI→ ⊆ S ×O, such that ∀(s, o) ∈ AFI→ , I→o is satisfied to at (s, o) to degree ζs,o ≤ ζI → .
Intuitively, we specify temporally extended intents such as “pick up passenger”, “drop a passenger at destination”, etc. such that the intent is satisfied to a certain degree. Affordances can then be defined as the subset of state-option pairs that can satisfy the intent to a that degree. Fig. 1 depicts a cartoon illustration of intents and corresponding option affordances in the classic Taxi environment.

heading: 4 Theoretical Analysis
text: We now analyze the value loss (Sec. 4.1) and planning loss (Sec. 4.2) induced by temporally extended intents I→ and corresponding temporally abstract affordances AFI→ . Lemma 1. Given a finite set of optionO ⊂ Ω and a set of temporally extended intents I→ = ∪o∈OI→o that are satisfied to degrees ζs,o, there exist constants (ζI → P , ζ I→ R ), such that:
maxs,o,t,s′ ∑ τ(s,t,s′)∈T (s,t,s′) ∣∣∣Po(τ(s, t, s′))− PI(τ(s, t, s′)|s, o))∣∣∣≤ ζI→P and (2) maxs,o
∣∣∣r(s, o)− Eτ∼PI [G(τ |s, o)]∣∣∣≤ ζI→R (3) where ζI →
P := maxs,o ζs,o, ζ I→ R := ζ I→ P ||G||∞, and G(τ) is the return on the trajectory τ .
The proof is in the Appendix A.1.1. We note that the error in the approximate probability distribution is bounded by the degree of intent satisfaction for each option i.e ζs,o. If intents are far from the true distribution P (i.e. much larger d in Def. 1) or misspecified, then the bounds above are predominantly governed by the approximation error induced due to the intent specification. Moreover, the approximate reward distribution is also a factor of the error in approximating probability distribution.

heading: 4.1 Value Loss Bound
text: A set of temporally extended intents I→ define an intent-induced SMDPMI→ , in which the intents can be used to approximate the option transition and reward models. The lemma above establishes this approximation, which in turn allows us to compute the value loss incurred when planning in the intent-induced SMDP.
Theorem 1 (Trajectory-Based Value-Loss Bound). Given a SMDPM corresponding to a finite set of options O and a set of temporally extended intents I→ = ∪o∈OI→o defined on option trajectories (Def. 1), the value loss between the optimal policy for the original SMDPM and the optimal policy
2In this work, we use d to be the total variation.
π∗I→ for the induced SMDPMI→ is given by:∣∣∣∣∣∣V π∗I→ − V ∗∣∣∣∣∣∣ ∞ ≤ ζ I→ R( 1− γI→ ) + 2ROmax∑∞t=1 γt|S|ζI→P( 1− γI→ )( 1− γO ) (4)
where ζI → P and ζ I→ R are defined in Lemma 1, R O max = maxs,o r(s, o) is the maximum option reward, γI → = maxs,o ∑ s′ γ I o (s, s ′) and γO = maxs,o ∑ s′ γo(s, s
′) are the maximum expected discount factor for the intents and options respectively.
Proof is in Appendix A.2.1. Our result is a strict generalization of the results established for primitive actions (Khetarpal et al., 2020a). Note that the value loss bound is better for temporally extended options than for primitives, due to the dependence on the maximum expected option discount (See Table 1). Note that in our bounds, ROmax and Rmax denote the maximum achievable reward for options and primitive actions respectively. Further interesting corollaries are included in the Appendix.

heading: 4.2 Planning Loss Bound
text: In this section, we analyze the effect of incorporating affordances and use temporally extended intents to build partial option models from data on the speed of planning. Similar results have previously been established to spell out the role of the planning horizon (Jiang et al., 2015) and to plan affordance-based partial models of primitive actions (Khetarpal et al., 2020a).
In practical scenarios, the agent may have limited information about the true model of the world. Moreover, it might be infeasible and intractable to build a full model, especially in real-life applications. To address this, we consider the SMDPMI→ induced by models associated with temporally extended intents and the associated affordances, and quantify the loss incurred when planning with this model. Theorem 2 (Trajectory-Based Planning-Loss Bound). Let I→ be a set of temporally extended intents for a finite set of options O, and M̂AFI→ the corresponding approximate SMDP over affordable state-option pairsAFI→ . Then, the loss incurred when using M̂AFI→ to compute a policy π∗M̂AFI→ and then using this policy in the original MDPM (also known as the certainty-equivalence planning loss) can be bounded by:∣∣∣∣∣∣V ∗−V π∗M̂AFI→ ∣∣∣∣∣∣
∞ ≤ 5ζ
I→ R
(1−γI→) + 2ROmax (1−γI→)(1−γO)
( 2 ∞∑ t=1 γt|S|ζI → P + √ 1 2n log 2|AFI→ ||ΠI→ | δ ) with probability at least 1− δ, where ζI→P and ζI → R are defined in Lemma 1, R O max = maxs,o r(s, o) is the maximum option reward, γI → = maxs,o ∑ s′ γ I o (s, s ′) and γO = maxs,o ∑ s′ γo(s, s
′) are the maximum expected discount factor for the intents and options respectively.
The proof is in Appendix A.3.1. The planning loss result generalizes the result for primitive actions provided in Khetarpal et al. (2020a). We note a similar effect of incorporating affordances in partial models for temporally extended actions. The accuracy in approximation of the intent (via (ζI →
P , ζ I→ R )), the size of affordable state-option pairs |AFI→ |, and the SMDP policy class Π→I will induce a trade-off between approximation of the intents and space of affordances. A key difference
in planning with the approximate partial option models M̂AFI→ is that the error can be controlled through the maximum expected discount factor for both intent and option models which in turn depends on the minimum expected duration of all affordable options.
Table 2 summarizes the effects of using temporally extended models and affordances. First, we note that the planning with affordances introduces a trade-off between approximation and estimation in both primitive and temporally extended actions. Concretely, the approximation error is induced due to the specification of intents through ζI → , whereas the estimation error is induced due to learning of the transition and has a dependence on the data size n and the size of the policy class ΠI→ .

heading: 5 Empirical Analysis
text: In this section, we study the impact of using affordances to learn partial option models which are then used for planning, in order to corroborate the theoretical results established in Sec. 4. In Sec. 5.1, we use a hand designed set of affordances to show that it can improve training stability as well as sample efficiency when used to learn a single partial option model, conditioned on a state-option pair. Then, in Sec. 5.2 we demonstrate the viability of learning the set of affordances at the same time as the partial option model resulting in a set of affordances that were smaller than those that were hand designed.
Environment. We consider the 5× 5 Taxi domain (Dietterich, 2000). The domain is a grid world with four designated pickup/drop locations, marked as R(ed), B(lue), G(reen), and Y(ellow). See Fig. 1 for illustration. The agent controls a taxi and faces an episodic problem: the taxi starts in a randomly-chosen square and is given a goal location at which a passenger must be dropped. The passenger is at one of the three other locations. To complete the task, the agent must drive the taxi to the passenger’s location, pick them up, go to the destination, and drop the passenger there. The action space consists of six primitive actions: Up, Down, Left, Right, Pickup, and Drop. The agent gets a reward of −1 per step, +20 for successfully dropping the passenger at the goal and −10 for dropping the passenger at the wrong location. There are a total of 25 (grid positions) ×4 (goal destinations) ×5 (passenger scenarios) = 500 states in this environment and the observation is a one-hot vector.
Option set O. We consider a fixed set of taxi-centric options, defined as follows: Go to a grid position (25 options); Drop passenger at grid position (25 options); Pickup passenger from grid position (25 options). The options are pre-trained via value iteration and fixed for all our experiments. In total there are 75× 500 = 37500 state-option pairs.
Experimental pipeline. 3 We use pre-trained options, o= 〈Io = S, πo(a|s), βo(s)〉, to collect transition data (st, o, T, st+T , r = ∑T i=t ri) where option o was initiated at state st and ended in state st+T after T steps, accumulating a reward of r. We execute options until termination or for Tmax steps, whichever comes first. We learn linear models to predict the next state distribution P̂φ1(s
′|s, o), option duration, L̂φ2(s, o) and reward r̂φ3(s, o), where φ denote parameter vectors. Affordances can be incorporated in model learning by selecting only affordable options during the data collection and to mask the loss of unaffordable state-option transitions:∑
(s,o,T,s′,r)∈D A(s, o, s ′, I→) [ − log P̂φ1(s′|o, s) + (L̂φ2(o, s)− T )2 + (r̂φ3(s, o)− r)2 ] (5)
where A(s, o, s′, I) is 1 if (s, o, s′) is affordable according to the intent I and 0 otherwise. We use the learned models, M̂ , in value iteration to obtain a policy over options πO(o|st). Affordances can be incorporated into planning by only considering state-option pairs in the affordance set (See Algorithm 1 in the Appendix). We report the success rate, i.e., the proportion of episodes in which the agent successfully drops the passenger at the correct location. Data collection, learning, and evaluation happen asynchronously and simultaneously (Fig 2) using the Launchpad framework (Yang et al., 2021).

heading: 5.1 Intents and affordances are most useful in model learning when the affordance sets are more relevant.
text: In this section we investigate the utility of using affordances on different aspects of the pipeline by considering a fixed set of affordances used either during model learning or planning. We first define three intent sets, I→, and their corresponding affordances:
1. Everything: All options are affordable at every state resulting in 37,500 state-option pairs in this affordance set. 2. Pickup+Drop: We build this set of affordances heuristically, by eliminating all options that simply go to a grid position, resulting in 25,000 state-option pairs . 3. Pickup+Drop@Goal: We create this affordance set of 4,000 state-option pairs that terminate at the four destination positions only.
When learning the partial model, using the most restrictive and relevant affordance set (Pickup+Drop@Goal) to collect data and mask the loss (*→ Everything) significantly improves the sample efficiency (Fig. 3(a)). The difference between Everything and Pickup+Drop was insignificant suggesting that the order of magnitude decrease in the number of state-option pairs in the affordance set is important (See also Sec 5.2 for more analysis of the affordance set size). Additionally, using any affordance set enables the use of a higher learning rate for learning the model without divergence (Fig. B1). On the other hand, given the same option model, using affordance sets only during planning (Everything→*) does not create any improvement in the success rate (Fig. 3(b)) or decrease in the planning iterations (Fig. 4): the quality of the model dictates the success rate.
3We will provide the source code for our empirical analysis here.
Finally, using the most restrictive affordance set for both model learning and planning (Pickup+Drop@Goal→Pickup+Drop@Goal) can result in further improvements in the sample efficiency (Fig. 3(c)) as well as accelerated planning time (Fig. 4)) demonstrating a combined benefit of using affordances in more aspects of the pipeline.

heading: 5.2 Relevant affordances can be learned online and result in improved sample efficiency.
text: In this section, we demonstrate the ability to learn affordances at the same time as learning the partial option model. To do this, we train a classifier, Aθ(s, o, s′, I) ∈ [0, 1] corresponding to intent I ∈ I→, which predicts if a stateoption pair is affordable. Pickup+Drop@Goal is defined by 8 intents: four that are completed when the agent has a passenger in the vehicle at the destinations; and four that are completed when the agent has dropped the passenger at the destinations. We convert Aθ(s, o, s
′, I) into an indicator for Eq. 5, by ensuring that at least one of the intents in the intent set is affordable, A(s, o, s′, I→) = 1[(maxI∈I→(A(s, o, s
′, I))> k] at some threshold value, k. When k = 0, all state and options are affordable. The affordance classifier is learned at the same time as the option model, M̂ , using the standard cross entropy objective: − ∑ I∈I→ c(s, o, s
′, I) log A(s, o, s′, I) where c(s, o, s′, I) is the intent completion function indicating if intent I was completed during the transition.
The threshold, k, controls the size of the affordance set (Fig. 5(a)) with larger k’s resulting in smaller affordance sets. The learned affordance set for Pickup+Drop@Goal is 2,000 state-option pairs which smaller than what we heuristically defined (4,000 state-option pairs). Smaller affordance sets result in improved sample efficiency (Fig. 5(b)). We highlight that this is not necessarily obvious since the learned affordance sets could remove potentially useful state-options pairs and k would be used to control how restrictive the sets are. These results show that affordances can be learned online for a defined set of intents and result in good performance. In particular, there are sample efficiency gains by using more restricted affordance sets.
Our results here demonstrate empirically that learning a partial option model requires much fewer samples as opposed to learning a full model. We also corroborate this with theoretical guarantees on sample and computational complexity of obtaining an ε-estimation of the optimal option value function, given only access to a generative model (See Appendix Sec. C).

heading: 6 Related Work
text: Affordances are viewed as the action opportunities (Gibson, 1977; Chemero, 2003), emerging out of the agent-environment interaction (Heft, 1989), and have been typically studied in AI as possibilities associated with an object (Slocum et al., 2000; Fitzpatrick et al., 2003; Lopes et al., 2007; Montesano et al., 2008; Cruz et al., 2016, 2018; Fulda et al., 2017; Song et al., 2015; Abel et al., 2014). Affordances have also been formalized in RL without the assumption of objects (Khetarpal et al., 2020a). Our work presents the general case of temporal abstraction (Sutton et al., 1999).
The process model of behavior and cognition (Pezzulo and Cisek, 2016) in the space of affordances is expressed at multiple levels of abstraction. During interactive behavior, action representations at different levels of abstraction can indeed be mapped to findings about the way in which the human brain adaptively selects among predictions of outcomes at different time scales (Cisek and Kalaska, 2010; Pezzulo and Cisek, 2016).
In RL, the generalization of one-step action models to option models (Sutton et al., 1999) enables an agent to predict and reason at multiple time scales. Precup et al. (1998) established dynamic programming results for option models which enjoy similar theoretical guarantees as primitive action models. Abel et al. (2019) proposed expected-length models of options. Our theoretical results can also be extended to expected-length option models.
Building agents that can represent and use predictive knowledge requires efficient solutions to cope with the combinatorial explosion of possibilities, especially in large environments. Partial models (Talvitie and Singh, 2009) provide an elegant solution to this problem, as they only model part of the observation. Existing methods focus on predictions for only some of the observations (Oh et al., 2017; Amos et al., 2018; Guo et al., 2018; Gregor et al., 2019; Zhao et al., 2021), but they still model the effects of all actions and focus on single-step dynamics (Watters et al., 2019). Recent work by Xu et al. (2020) proposed a deep RL approach to learn partial models with goals akin to intents, which is complementary to our work.

heading: 7 Conclusions and Limitations
text: We presented notions of intents and affordances that can be used together with options. They allow us to define temporally abstract partial models, which extend option models to be conditioned on affordances. Our theoretical analysis suggests that modelling temporally extended dynamics for only relevant parts of the environment-agent interface provides two-fold benefits: 1) faster planning across different timescales (Sec. 4), and 2) improved sampled efficiency (Appendix Sec. C). However, these benefits can come at the cost of some increase in approximation bias, but this tradeoff can still be favourable. For example, in the low-data regime, intermediate-size affordances (much smaller than the entire state-option space) could really improve the speed of planning. Picking intents judiciously can also induce sample complexity gains, if the approximation error due to the intent is manageable. Our empirical illustration shows that our approach can produce significant benefits.
Limitations & Future Work. Our analysis assumes that the intents and options are fixed apriori. To learn intents, we envisage an iterative algorithm which alternates between learning intents and affordances, such that intents can be refined over time and the mis-specifications can also be selfcorrected (Talvitie, 2017). Our analysis is complimentary to any method for providing or discovering intents. Another important future direction is to build partial option models and leverage their predictions in large scale problems (Vinyals et al., 2019). Besides, it would be useful to relate our work to cognitive science models of intentional options, which can reason about the space of future affordances (Pezzulo and Cisek, 2016). Aligned with future affordances, a promising research avenue is to study the emergence of new affordances at the boundary of the agent-environment interaction in the presence of non-stationarity (Chandak et al., 2020).
Acknowledgments and Disclosure of Funding
The authors would like to thank Feryal Behbahani and Dave Abel for a very detailed feedback, Martin Klissarov and Emmanuel Bengio for valuable comments on a draft of this paper, and Joelle Pineau for feedback on ideas presented in this work. A special thank you to Ahmed Touati for discussion and detailed notes (Azar et al., 2012) presented in RL theory reading group at Mila.

Review summaries:
This paper presents a formalism for semi-Markov decision processes that defines "intention" (desirable outcomes of behavior) and "affordances" (behaviors that achieve an intention). The main idea is that the agent may have many options, but may have a more limited set of intentions, and affordances can constrain the problem of selecting a good option. Theoretical results are also presented, bounding the sub-optimality caused by operating in intention/affordance/option space, rather than in primitive actions. Finally an illustrative empirical experiment gives a proof of concept for learning affordances, given fixed options and intentions.

This paper describes options models as partial models, meaning that the options model predict only the outcome of a subset of state-action pairs (both the state transition and the reward). Options enable temporal abstraction by allowing an agent to select an option at a particular decision point and follow it until it satisfies the termination condition. The primary contribution of the paper is the development of theory which quantifies the loss incurred by using temporal abstraction (options) relative to single step decision making.   

This paper addresses the problem of learning and planning with options framework in RL. The authors extend an existing notations of affordness and intent in the context of options and perform a mathematical analysis of the bound and the value loss. The ideas are demonstrated on a taxi benchmark with predefined set of options to illustrates the benfit of the approach.   

This paper studies an option-based setting where each option is associated with an _intent_, a distribution over desired trajectories following the option execution. Intents induce _affordances_,  which are starting states that are likely to lead to the intents for each option. Intents and affordances induce a partial option model, where the usual transition model over options is replaced with the intents, and the model is partial over the affordances. The main theoretical questions concern the extent to which planning in this partial option model will lead to good performance in the original semi-MDP. Experiments are in a standard taxi domain with given options and intents.