Autonomously Learning an Action Hierarchy Using a Learned Qualitative State Representation

1 Introduction

Reinforcement learning (RL) is a popular method for enabling agents to learn in unknown environments [Sutton and Barto, 1998]. Much work in RL focuses on learning to maximize a reward given a set of states S and a set of actions A. In this paper we focus on continuous environments and we present a method for learning a qualitative state representation S∗ and a hierarchical set of qualitative actions A∗ using only intrinsic reward. We call the actions that the agent learns qualitative actions because they allow the agent to reach qualitative states. We call our algorithm the Qualitative Learner of Actions and Perception, QLAP.

QLAP makes use of the options framework [Sutton et al., 1999] and learns one or more options to perform each qualitative action, where each option serves as a different way to perform the action. Boutilier [1995] proposed making MDP planning more tractable by exploiting structure in the problem using dynamic Bayesian networks (DBNs). In QLAP there is a one-to-one correspondence between DBNs and options, and each option is treated as a small MDP problem. Each option is learned by first learning a small dynamic Bayesian network (DBN). The variables in the DBN determine the initial state

Benjamin Kuipers

Computer Science and Engineering University of Michigan Ann Arbor, MI 48109 USA kuipers@umich.edu

space for the option. This leads to a state abstraction in the option, because the variables in the DBN are a subset of the available variables. The conditional probability table of the DBN is used to specify the transition function for the option. Since the option's state space is small, the policy can then be learned using dynamic programming.

In QLAP, the agent begins with a very coarse discretization that indicates if the value of each variable is increasing, decreasing, or remaining steady. Using this discretization, the agent first motor babbles and then explores by repeatedly choosing a qualitative action and an option to achieve that action, and then following the policy of that option. While it is exploring it is learning DBNs. Once a DBN is sufficiently deterministic an option is created based on it. The agent also learns new distinctions to improve previously learned DBNs. These new distinctions update the agent's qualitative state representation.

We consider the options that QLAP learns to be hierarchical options because (1) they invoke qualitative actions instead of primitive actions, (2) they use a state abstraction that is specific to the option, and (3) they use a pseudo-reward to learn the policy independent of the calling context. The disadvantage of this hierarchical approach is that the agent may not always find the optimal solution. One important advantage is that the temporal abstraction afforded by the options decreases the task diameter (the number of actions needed to achieve the goal) and therefore reduces the amount of time that the agent spends randomly exploring. Another important advantage is that the agent is able to ignore variables that are not necessary to complete the task. QLAP options are each created to achieve a goal, and since they use a state abstraction and a pseudo-reward, they share similarities with MAXQ subtasks [Dietterich, 1998].

In [Mugan and Kuipers, 2007] a method was proposed for learning both a discretization and small models to describe the dynamics of the environment. In [Mugan and Kuipers, 2008] a method was proposed for enabling an agent to use those models to autonomously formulate reinforcement learning problems. The contributions of this paper are to put the learned small models into the DBN framework and to organize the formulated reinforcement learning problems into a hierarchy using options.

We first discuss how QLAP learns the action hierarchy. We then discuss how the agent executes QLAP. We then evaluate QLAP using a simulated robot with realistic physics, and we show that using QLAP the agent can learn an action hierarchy that allows it to perform both temporal abstraction and state abstraction to complete the task of hitting a block. We then discuss related work and conclude.

2 Learning the Action Hierarchy

2.1 Qualitative Representation

QLAP uses a qualitative representation to abstract the continuous world. A qualitative representation allows an agent to cope with incomplete information and to focus on important distinctions while ignoring unimportant ones [Kuipers, 1994]. A qualitative state representation includes both the continuous state variables, called magnitude variables, as well as change variables that encode the direction of change (increasing, decreasing, or steady) of each magnitude variable. The values of the variables are represented qualitatively using landmarks, and the value of a qualitative variable can be either at a landmark or between two landmarks. In this way, landmarks can convert a continuous variable ˜ v with an infinite number of values into a qualitative variable v with a finite set of qualitative values Q(v) called a quantity space [Kuipers, 1994]. A quantity space Q(v) = L(v) ∪ I(v), where L(v) = {v∗ 1 , · · · , v∗n } is a totally ordered set of landmark values, and I(v) = {(-∞, v∗ 1 ), (v∗ 1 , v∗ 2 ), · · · , (v∗n ,+∞)} is the set of mutually disjoint open intervals that L(v) defines in the real number line. A quantity space with two landmarks might be described by (v∗ 1 , v∗ 2 ), which implies five distinct qualitative values, Q(v) = {(-∞, v∗ 1 ), v∗ 1 , (v∗ 1 , v∗ 2 ), v∗ 2 , (v∗ 2 , +∞)}.

The magnitude variables initially have no landmarks, and the agent must learn the important distinctions. Each direction of change variable ˙v has a single intrinsic landmark at 0, so its quantity space is Q( ˙v) = {(-∞, 0), 0, (0, +∞)}. Motor variables are a third type of qualitative variable. They are also given an initial landmark at 0, but the agent must learn further distinctions. For example, in the evaluation the agent learns that it takes a force of at least 300.0 to move the hand.

Using a qualitative representation allows the agent to focus its attention on events and ignore unimportant sensory input. We define the event Xt→x to be when X(t - 1) ̸= x and X(t) = x, where x ∈ Q(X) is a qualitative value of a qualitative variable X.

2.2 Qualitative Actions

The qualitative representation defines a set of qualitative actions. QLAP creates a qualitative action qa(v, q) to achieve each qualitative value q ∈ Q(v) for each qualitative variable v. There are three types of qualitative actions corresponding to the three types of qualitative variables: motor, magnitude, and change. A motor action qa(v, q) sets ˜ v to a random continuous value within the range covered by q.

Magnitude and change actions are high-level actions. When a magnitude or change action is executed it chooses an option and executes the policy for that option. Each option is associated with only one qualitative action, and the actions that an option can invoke are qualitative actions.

A magnitude action qa(v, q) has one option to achieve v = q if the value of v is currently less than q, and another option to achieve v = q if the value of v is currently greater than q. A change action qa(v, q) may have multiple options to choose from to achieve v = q. To learn each option, QLAP first learns a DBN. There is a one-to-one correspondence between DBNs and options.

2.3 DBNRepresentation

In Mugan and Kuipers [2007] a method was presented for learning small models to predict qualitative values of variables. In this paper we put those models into the dynamic Bayesian network framework. We refer to these models as dynamic Bayesian networks and not simply Bayesian networks because we are using them to model a dynamic system. The notation we use for these DBNs is r = 〈C : E1 ⇒ E2〉 where C is a set of qualitative variables that serves as a context, event E1 = X→x is the antecedent event, and event E2 = Y →y is the consequent event (see Figure 1). This DBN r can be written as

DBN r gives the probability that event Y→y will soon follow event X→x for each qualitative value in C. Focusing only on timesteps in which event X→x occurs helps to focus the agent's attention to make learning more tractable. And using a time window for event Y →y allows the DBN to account for influences that may take more than one timestep to manifest. Notice that these DBNs differ from the typical DBN formulation, e.g. [Boutilier et al., 1995], in that there is no action associated with the DBN. This is because QLAP does not begin with a set of primitive actions, it only assumes that the agent has motor variables. The DBNs in QLAP are tied to the agent's motors because the antecedent event of the DBN can be on a motor variable.

To learn each DBN, QLAP finds a pair of events E1 and E2 such that E2 is more likely to occur soon given that E1

has occurred than otherwise. It then creates a DBN with an empty context. QLAP then iteratively adds context variables that improve the predictive ability of the DBN (cf. marginal attribution [Drescher, 1991]). Additionally, predicting when the Boolean child variable will be true is a supervised learning problem. This formulation allows the agent to learn new landmarks (distinctions) that improve the predictive ability of the DBN (see [Mugan and Kuipers, 2007; 2008] for details.)

The DBNs we have just discussed predict events on change variables and are called change DBNs. QLAP also uses magnitude DBNs to predict events on magnitude variables. For each magnitude variable v and each qualitative value q ∈ Q(v), QLAP creates two DBNs, one that corresponds to approaching the value v = q from below on the number line, and another that corresponds to approaching v = q from above. Magnitude DBNs are similar to change DBNs. For example, if v < q and the robot successfully performs the action to achieve ˙v = (0, +∞), then the DBN gives the probability, for each value of the variables in the context, of event v→q occurring before ˙v ̸= (0,+∞). Magnitude DBNs have no concept of "soon," as long as v < q and ˙v = (0, +∞), the agent will wait for v→q.

For a DBN r, we denote the probability of the child variable being true in state s by CPTr(s) (we only consider the cases where the non-context parent variable is true). We call the highest probability CPTr(s∗ ) for any state s∗ the best reliability of DBN r.

2.4 Options

An option [Sutton et al., 1999] is like a subroutine that can be called to perform a task. An option oi is typically expressed as the triple oi = 〈Ii, πi, βi〉 where Ii is a set of initiation states, πi is the policy, and βi is a set of termination states or a termination function. Options in QLAP follow this pattern except that πi is a policy over qualitative actions instead of being over primitive actions or options. Additionally, since each option in QLAP learns its policy using its own state abstraction, associated with option oi is a state space Si, a set of qualitative actions Asi for each state s ∈ Si, and a transition function Ti : Si ×Asi →Si.

QLAP creates a magnitude option for each magnitude DBN. QLAP creates a change option for each change DBN where (1) the best reliability is estimated to be greater than θr = 0.75 and (2) the antecedent event can be achieved with an estimated probability greater than θr = 0.75 and (3) the option would not create a cycle of change options. (We also limit the number of change options to 3 for any qualitative action). The goal of the option is to make the child variable of the DBN true. If this occurs, then the option succeeds. If the option succeeds, then the qualitative action that invoked it also succeeds.

Creating an Option from a DBN

When an option or is created for a DBN r, the set of initiation states Ir is the set of all states, and the termination function βr terminates or when it succeeds (the child variable becomes true) or when it becomes stuck for 10 timesteps or exceeds resource constraints (300 timesteps, or 5 suboption calls). To learn the policy πr, QLAP uses the DBN to create a transition function Tr : Sr×Asr → Sr and then learns the Q-table using dynamic programming with value iteration [Sutton and Barto, 1998]. The pseudo-reward is 10.0 for reaching the goal and a transition cost of 0.50 is imposed for each transition.

We now describe how QLAP constructs the state space Sr, the set of available actions Asr , and the transition function Tr for option or from a change DBN r = 〈C : X→x ⇒ Y→y〉. Recall that Q(v) is the set of qualitative values for qualitative variable v. If we define the set Zr = C∪X∪Y , then the state space Sr for option or is Sr = ∏v∈Zr Q(v). (We will see in Section 2.5 how more variables can be added to state spaces.)

Recall that the notation qa(v, q) means the qualitative action to bring about v = q. The set of qualitative actions Asr available in state s ∈ Sr is

The definition of Asr consists of three parts. (1) The qualitative actions AC allow the agent to move within the context

(although any action on the corresponding magnitude variable of Y is excluded fromAC to prevent infinite regress). (2) The qualitative action qa(X, x) brings about the antecedent event of r. (3) QLAP subtracts those actions whose goal is already achieved in state s.

To construct Tr : Sr ×Asr → Sr, QLAP must compute a set of possible next states for each s ∈ Sr and a ∈ Asr . It must then compute the distribution P(s′ |s, a). To compute P(s′ |s, a), QLAP uses the statistics gathered on DBN r and the statistics gathered to estimate the probability Pr(a) of success for qualitative action a. When calculating the possible next states after a qualitative action, QLAP limits its scope to those next states that are most important for learning the Q-table. For a qualitative action a = qa(v, q) with v ∈ C to change the value of a context variable, QLAP considers two possible next states. State s′1 where the action is successful and the only change is that s′1 (v) = q, and state s′2 where the action fails and s′2 = s. The probability distribution over s′ then is Pr(s′1 |s, a) = Pr(a) and Pr(s′2 |s, a) = 1 - Pr(a). For the qualitative action a = qa(X, x) to bring about the antecedent of r, QLAP also considers two possible next states. State s′1 is where the antecedent event occurs and the consequent event follows, so that s′1 is the same as s except that s′1 (X) = x and s′1 (Y ) = y. State s′2 is where the antecedent event occurs but the consequent event does not follow, so that s′2 is the same as s except that s′2 (X) = x. The probability distribution over s′ is Pr(s′1 |s, a) = CPTr(s) and P r(s′2 |s, a) = 1 - CP Tr(s).

For a magnitude option the state space Sr, the set of available actions Asr , and the transition function Tr are computed similarly as they are for change options. One difference is that magnitude options have a special action called wait. For the option to reach v = q from below on the number line, the action wait can be taken if the value of variable v is less than q and is moving towards q.

2.5 Second-Order DBNs

Once a change or magnitude option is created, a second-order DBN is created to track its progress. The statistics stored for second-order DBNs help the agent choose which option it should invoke to perform a qualitative action. Second-order DBNs also allow the agent to determine if there are additional variables necessary for the success of an option. A secondorder DBN r2 o created for option o has the form

The child variable of second-order DBN r2 o is succeeds(t, o), which is true if option o succeeds after being invoked at time t and is false otherwise. The parent variables of r2 o are invoke(t, o) and and the context variables in Co. The Boolean variable invoke(t, o) is true when the option is invoked at time t and is false otherwise. When created, DBN r2 o initially has an empty context, and context variables are added in as they are for magnitude and change DBNs.

Second-order DBNs allow the qualitative action to choose an option that has a high probability of success in the current state. The option is chosen randomly based on the weight wo. Weight wo is calculated using the current state, the original change or magnitude DBN r, and the second-order DBN r2 o where

(To prevent loops in the call stack, an option whose DBN has its antecedent event already in the call stack is not considered a valid choice.)

Second-order DBNs allow the agent to identify other variables necessary for the success of an option o because those variables will be added to its context. Each variable that is added to r2 o is also added the state space Sr of its associated change or magnitude DBN r. For example, if DBN r = 〈C : X→x ⇒ Y →y〉, the state space Sr is updated so that Sr = ∏v∈Z′r Q(v) where Z ′r = Co ∪ C ∪ X ∪ Y . For both magnitude and change options, a qualitative action qa(v, q) where v ∈ Q(Co) is treated the same way as those where v ∈ Q(C).

3 Execution

The agent motor babbles for the first 20,000 timesteps (1000 seconds of physical experience) by picking random motor values and maintaining those values for random numbers of timesteps (≤ 40). During this time the agent learns landmarks on motor variables and its first DBNs, options, and qualitative actions. Exploration then follows a developmental progression as the agent randomly chooses qualitative actions for execution among those actions that have at least one option.

To perform an action the agent chooses one of the action's options and then follows the policy. When following a policy QLAP uses ϵ-greedy action selection and updates the Qtables using Sarsa(λ). The reward for reaching the goal is 10.0, the step cost is 0.01 for each timestep, and it uses the parameter values λ = 0.9, ϵ = 0.05, γ = 1.0, and α = 0.2.

Every 2000 timesteps the agent learns new DBNs, augments the contexts of existing DBNs, and learns new landmarks (see [Mugan and Kuipers, 2007]). QLAP also creates new options corresponding to the new DBNs and it does a Dyna-inspired [Sutton and Barto, 1998] update of the existing Q-tables by recalculating the transition function and then doing a one-step update of each Q-table.

4 Evaluation

4.1 The Environment and Task

We evaluate QLAP using the environment shown in Figure 2. The environment is implemented in Breve [Klein, 2003] and has realistic physics. The simulation consists of a robot at a table with a block, and in some experiments there are floating objects that the robot can perceive but cannot interact with. As the agent explores, each time the block is knocked out of reach it is replaced with a different block. Each block has the same mass, but the block size varies randomly in length from 1.0 to 3.0.

QLAP autonomously learns without being specified a task. To evaluate QLAP, we choose the task of having the agent hit the block in a specified direction, either left, right, or forward. During learning, the agent does not know that it will be evaluated on this task. We know of no other RL algorithm that learns in an unsupervised way that would be appropriate for this task, so we compare our method to reinforcement learning using tile coding, which we call RL-Tile. RL-Tile was trained only on the evaluation task. This puts QLAP at a disadvantage on the evaluation task because QLAP learns more than the evaluation task. For example, QLAP learns to move its hand away from the block as well as towards it. It is because of the simplicity of the environment that we can count on QLAP learning the task that was assigned to RL-Tile.

RL-Tile was trained using linear, gradient-descent Sarsa(λ) with binary features [Sutton and Barto, 1998] where the binary features came from tile coding. There were 16 tilings and a memory size of 65,536. The motor variables ux and uy were each divided into 10 equal-width bins, so that there were 20 actions with each action either setting ux or uy to a nonzero value. The change variables were each divided into 3 bins: (-∞,-0.05), [-0.05, 0.05], (0.05,∞). The goal was represented with a discrete variable that took on three values, one for each of the three goals. The remaining variables were treated as continuous (normalized to the range [0, 1]) with a generalization of 0.25. The parameter values used were λ = 0.9, γ = 1.0, and α = 0.2. Action selection was ϵgreedy where ϵ = 0.05. The code for the implementation came from PLASTK [Provost, 2008].

For each experiment we trained 30 QLAP agents and 30 RL-Tile agents, and we trained each for 150,000 timesteps (about two hours of physical experience). The QLAP agents autonomously explored the environment, and the RL-Tile agents continually repeated the task. We compare QLAP and RL-Tile by storing the learned state of each every 10,000 timesteps (about every 8 minutes of physical experience). We then test how well each can do that task starting from this stored learned state. Each evaluation consisted of 100 episodes. Each episode lasted for 300 timesteps or until the block was moved. The agent received a penalty of -0.01 for each timestep, and it received a reward of 10.0 if it hit the block in the specified direction.

4.2 HowQLAP Achieves the Task

The QLAP agent learns a qualitative action to hit the block in each specified direction. For example, to hit the block to the right, QLAP learned the qualitative action qa( ˙bx, (0, +∞)). QLAP is able to perform this action because it learned an option or to bring about ˙bx = (0,+∞). QLAP learned this option by learning the DBN r = 〈ytb : xrl →[0] ⇒ ˙bx→(0,+∞)〉, which predicts that if the distance between the right side of the hand and the left side of the block goes to 0, then the block will soon move to the right. The CPT of this DBN says that in order for this to occur reliably the top of the hand must be above the bottom of the block. QLAP learned the landmarks at 0 on both ytb and xrl. These landmarks allow the agent to make the important distinctions of the hand being above the bottom of the block and being to the left of the block. The second order DBN r2 o = 〈xrl : invoke(t, or) ⇒ succeeds(t, or)〉 predicted that for or to work the hand must be to the left of the block. This allowed the agent to add moving the hand to the left of the block as an action in or.

4.3 Results

In the first experiment we compare QLAP with RL-Tile in the environment without the distractor objects. The results are shown in Figure 3(a). QLAP learns the necessary actions at around 80,000 timesteps. Although it appears that RL-Tile could eventually overtake QLAP, RL-Tile learns much more slowly. This is because the task diameter is so high that the RL-Tile agent initially does a lot of flailing around before it reaches the goal.

In the second experiment we make the task easier for RLTile by reducing the task diameter by making its actions last for 10 timesteps (we call this RL-Tile-10). The results are shown in Figure 3(b). RL-Tile-10 learns the task quickly and then improves only gradually because it cannot take actions that last for less than 10 timesteps.

To demonstrate that QLAP ignores irrelevant variables, the third experiment was conducted using distractor objects. The results are shown in Figure 3(c). When the distractor objects are added, RL-Tile's reward per episode degrades significantly, but QLAP is unaffected.

5 Related work

Given a DBN model of the environment, the VISA algorithm [Jonsson and Barto, 2006] learns a hierarchical decomposition of a factored Markov decision process. VISA learns options and finds a state abstraction for each option. However, VISA requires a discretized state and action space. QLAP learns actions from the agent's continuous motors and learns a discretized state representation.

Options can be learned by first identifying a subgoal and then learning an option to achieve that subgoal. McGovern and Barto [2001] proposed a method whereby an agent autonomously finds subgoals based on bottleneck states that are visited often during successful trials and rarely during unsuccessful ones. Subgoals have also been found by constructing a transition graph based on recent experience and then searching for "access states" [Simsek et al., 2005] that allow the agent to go from one partition of the graph to another. In Barto et al. [2004] options are learned to achieve salient events. However, these salient events are determined outside the algorithm, and all of this work takes place in discrete environments.

Once an option is identified, the agent must learn how to achieve it. One way to do this is by learning a model. In environments with large state spaces, the model in the form of a transition function cannot be represented explicitly and the agent must learn a structured representation. Degris et al. [2006] proposed a method called SDYNA that learns a structured representation and then uses that structure to compute a value function. Similarly, Strehl et al. [2007] learn a DBN to predict each component of a factored state MDP. Both of these methods are evaluated in discrete environments where transitions occur over one-timestep intervals. Another method is learning probabilistic planning rules [Pasula et al., 2007]. In the domain of first-order logic they learn rules that given a context and an action provide a distribution over results. This algorithm also assumes a discrete state space and that the agent already has basic actions such as pick up.

6 Conclusion

We present QLAP, a method for enabling an agent to learn a hierarchy of actions in a continuous environment. QLAP assumes that the agent is able to change the values of individual variables. Future work will focus on determining the importance of this assumption and how QLAP can overcome it. QLAP is designed for continuous environments where the agent has very little prior knowledge. QLAP bridges an important gap between continuous sensory input and motor output and a discrete state and action representation.

Acknowledgments

This work has taken place in the Intelligent Robotics Lab at the Artificial Intelligence Laboratory, The University of Texas at Austin. Research of the Intelligent Robotics lab is supported in part by grants from the Texas Advanced Research Program (3658-0170-2007), and from the National Science Foundation (IIS-0413257, IIS-0713150, and IIS0750011). The authors would also like to thank Matt MacMahon and Joseph Modayil, as well as the anonymous reviewers for helpful comments and suggestions.