Utile Distinctions for Relational Reinforcement Learning

1 Introduction

This paper introduces a method that combines the expressive power of a relational representation with the learning power of reinforcement learning (RL). The goal is to autonomously learn a relational state space approximation while simultaneously learning to act optimally. A relational representation enables an agent to reason at a higher level, which can allow an agent to learn in more difficult problems [Kaelbling et al., 2001]. RL is an ideal technique for real-world control because it can learn to achieve a goal without being told how to accomplish it. There has been considerable recent interest in combining these techniques [Tadepalli et al., 2004; van Otterlo, 2005].

The primary contribution of this paper is the introduction of an online RL method, Relational UTree, that can autonomously construct its own tree-based function approximation using a relational representation. UTree [McCallum, 1995] develops its own tree-based state space, allowing it to focus on the most important aspects of observations and to ignore irrelevant ones. Traditionally, a state representation is either designed by the user or learned from the policy.

Learning in a relational representation introduces two key challenges. The first is the exponential growth in search space and the second is that relational environments tend to have a high degree of autocorrelation. This has been shown to cause a selection bias that makes distinctions to appear useful when they are not [Jensen and Neville, 2002]. Relational UTree compensates for the size of the search space by using stochastic sampling [Srinivasan, 1999]. Autocorrelation violates the independent and identically distributed assumption made by many statistical techniques. We compensate for the effects of temporal autocorrelation by temporally sampling.

We separately address the need to adapt to changes in the environment by incorporating efficient tree restructuring [Utgoff et al., 1997]. This allows Relational UTree to create more compact trees with the same representational power and helps to prevent overfitting in stochastic environments.

The most similar works are the G [Finney et al., 2002; Chapman and Kaelbling, 1991] and TG algorithms [Driessens, 2004; Driessens et al., 2006]. There are several major differences between TG, which is based in part on GAlgorithm, and Relational UTree. The primary difference is that Relational UTree can dynamically restructure its trees while TG must build a new tree from scratch. This allows Relational UTree to adapt to changes in the environment and to correct early mistakes made in the tree. While Relational UTree uses graphs to represent observations, TG uses first order logic predicates. In addition, TG creates a separate policy tree (called a P-tree) while Relational UTree derives its policy from the Q-value tree. Finney et al.'s [2002] approach is also based on G algorithm but uses a deictic representation, while Relational UTree makes use of a full relational representation and incorporates tree restructuring. We empirically compare the performance of Relational UTree to these approaches on blocks world environments.

2 AlgorithmDescription

The Relational UTree algorithm follows the UTree algorithm closely. We use the standard RL and partially observable Markov decision process (POMDP) notation where, at each time step t, the agent executes an action at ∈A, and receives an observation ot+1 ∈ O, and a reward rt+1 ∈ ℜ [Sutton and Barto, 1998; Kaebling et al., 1998].

An observation takes the form of an attributed graph G= 〈V,E,A(V),A(E),T(V),T(E)〉. V is the set of all objects in the environment, represented by vertices in the graph and E is the set of all relationships, represented by edges [McGovern et al., 2003]. A(V) and A(E) are the set of attributes for the vertices and edges respectively, the elements of which are discrete or real valued attributes. A(V) and A(E) may contain zero or more elements. T(V) and T(E) are required discrete valued types for vertices and edges. Example observations for blocks world are shown in Figure 1. Some attributes and relationships are omitted for readability. The graphical representation used does not place individual identifiers on objects, but instead objects are identified by their type, attributes, and relationships to other objects. This property of graphical representations is advantageous for generalizing concepts.

Our Relational UTree description uses McCallum's [1995] notations. We refer to the set of distinctions that lead to a tree node and the state represented by a leaf node as s. A transition instance, Tt = 〈Tt-1,at-1,ot ,rt〉, represents one step of the agent's experience. The set of instances contained in a leaf node s is denoted T (s), and the set of instances contained in a leaf node s where the next action is a is T (s,a). The time ordered set of all transition instances is H = {T0,T1, ...,T|H|}. The leaf node to which a specific transition instance belongs is denoted by L(Tt ).

2.1 Relational Utile Distinctions

We refer to a distinction as being utile if and only if the distinction statistically separates the set of transition instances so that the agent is better able to predict reward. The sets of possible distinctions are: Object existence {(x,h) | x ∈ T(V),h ∈ N}, relationship existence {(x,o1,o2,h) | x ∈ T(E),o1 ̸= o2∀o1,o2 ∈M(V),h ∈N}, and attribute value {(a, valuea,o1,h) | (a,valuea) ∈ A(o1),o1 ∈ {M(V)∪M(E)},h ∈ N}, where h is the history index, M is the memory, x is a parameter limiting the number of previous observations that can be considered, and N is the set of natural numbers.

The variables o1 and o2 are pointers to variable memories. Variable memories reference previous distinctions in s, allowing simple distinctions to be used to construct complex queries. For each type of distinction, the set of variable memories created when an instance is dropped down a node with that distinction is given by: {v ∈ Vi | T(v) = X} for object distinctions, {(e,v1,v2) ∈ Ei | T(e) =X,v1 ̸= v2,v1,v2 ∈Vi} for relationship distinctions, and {p ∈Vi ∪Ei | (a,valuea) ∈ A(v), a = X , valuea = Y } for attribute value distinctions.

Figure 2 shows an example of how Relational UTree uses variable memories. As the observation shown in Figure 1(c) falls down the root node, blocks are added to the variable memory. The second node selects blocks from this list with "Color = Green" and saves the matches.

Relational UTree allows static objects to be referenced so that their non-static attributes may be accessed. The set of static objects is defined as S = THVi. A focal object, f ∈V, can be incorporated to allow an agent to reason deictically. Let M(V,N) be the set of object variable memories for the node N. At the root node, Nr, M(V,Nr) = S∪{ f }. The set of object variable memories created by the distinction at a given node, N, is denoted m(V,N). If we let Np be the parent node to N, then the set of object variable memories at any node, N, is defined as M(V,N) =M(V,Np)∪m(V,Np). We similarly define M(E,N), given M(E,Nr) = /0.

2.2 The Relational UTree Algorithm

The Relational UTree algorithm works as follows:

1. Create a tree with no distinctions. Initialize T (s) = /0 and H = /0.
2. Take one step of experience in the environment. Choose the action at-1 to be the policy action of L(Tt-1), with ε probability of choosing a random action. Record the experience as Tt = 〈Tt-1, at-1, ot , rt 〉 and H = H ∪ {Tt }. Using standard decision tree methods, drop Tt down the tree. Save Tt to the leaf node, L(Tt) = s, setting T (s) = T (s)∪{Tt}. Mark all tree node N ∈ s as stale, where a

stale node indicates that the distinction at that node may need to be changed during restructuring.

In some environments, observations ot and ot+1 are autocorrelated. For example, in the blocksworld2 environment shown in Figure 1 (c), the objects and relationships will remain largely the same regardless of the next action performed. This is an example of temporal autocorrelation, and can cause a feature selection bias [Jensen and Neville, 2002]. In these situations, we remove autocorrelation through temporal sampling. Every c steps, Tt is forgotten, where c is a user defined value.

1. With the leaves of the tree representing the states, perform one step of value iteration using Equations 1 - 4. The equations for estimated immediate reward and estimated probability of arriving in state s′ after executing action a in state s are given in Equation 3 and 4 and directly follow McCallum's equations.

1. Update the tree every k steps by first ensuring the quality of current distinctions, followed by expanding the tree by adding new distinctions at the leaves. All stale tree nodes N are updated as follows.

(a) First, stochastically generate a set of distinction trees Φ. Include the existing distinction tree, φN, in the set Φ, with Φ=Φ∪{φN}. A distinction tree is made up of one or more distinctions on a set of instances, organized into a tree structure. We consider distinction trees with depth up to some constant k, and consider larger depths only if no utile distinction trees are found. Each distinction tree φ ∈ Φ defines a set of fringe leaf nodes L.

For each fringe leaf node s ∈ L, the set of expected future discounted rewards for s makes up a distribution δ(s) given by Equation 5 [McCallum, 1995].

Calculate the Kolmogorov-Smirnov distance between each pair of distributions, denoted KS(δ0,δ1). Let Pφ be the set of these p-values, given by Equation 6.

Choose the best distinction tree from among Φ and the current distinction tree, φN, using Equation 7.

If there is no p ∈ Pφ′ below the user specified value, then N is pruned from the tree. We used p = 0.001 for this paper. Otherwise, φN is replaced by φ′ through a series of tree transpositions. For distinction trees of depth greater than one, the distinctions are 'pulled-up' one at a time, beginning with the root distinction.

(b) Once the best distinction tree at a given node is determined, the tree is restructured following Utgoff et al. [1997]. If the current distinction at N is already the best, φN = φ′ , then we are done. Otherwise, a recursive depth first traversal of the tree is applied until one of the base cases, shown in Figure 3, is reached. At this point, the utile distinction, φ′ , is "pulled-up" by recursively performing the tree transposition steps shown in the figure. After a single "pull-up" has been performed, the next base case in the tree is addressed until the best distinction tree, φ′ , is at the target node, N.

When the tree restructuring operation has completed for N, mark it as not stale. If the node has changed through tree restructuring, then mark all nodes in its subtree as stale. Continue to apply step 4 to each stale child node of N. This process continues until no branches are stale, and the quality of the distinctions in the tree are ensured. Finally, perform value iteration until convergence.

1. Every k steps, expand the tree at the leaves. For each leaf node of the tree, s, determine the best distinction tree for the instances at that node using the process outlined in step 4 (a). If the new distinction tree is utile, then expand the tree by adding a subtree at the leaf s and dropping the instances T (s) down the new distinction tree. This removes s from the list of leaves and adds the set of leaves L to that list. Continue expanding the tree until it is no longer utile to do so. Perform value iteration until convergence after expansion is done.
2. Repeat at step 2 until stopped.

2.3 Stochastic Sampling

We use stochastic sampling [Srinivasan, 1999] to address the large space of possible distinctions introduced with a relational representation. Srinivasan shows that if we can sample tests stochastically that we can look at only a small fraction of the total and still be highly confident in finding one that is among the best possible. The number of tests that must be sampled is given by n ≥ ln(1-α) ln(1-k) , where α is the probability of finding a test in the top (100×k)% [Srinivasan, 1999]. The key to this equation is that the sample size does not depend on the number of possible distinctions.

For this paper, we have used k = 0.01 and α = 0.99 to be 99% confident in finding a distinction in the top 1%. In this situation we only need to sample 458 distinctions. By gradually reducing k, we can move the search for distinctions toward an exhaustive search. With our values, it took under a second to expand a leaf node containing 5000 instances. When we reduce k to 0.001, it takes two minutes to do the same expansion. Similarly, with k = 0.0001 the expansion time for the leaf node is almost 13 minutes. This demonstrates that an exhaustive search of the distinction space is not feasible. To compensate, we use stochastic sampling.

2.4 Tree Restructuring

In the early stages of learning, an agent will have only seen a fraction of the environment and may create a state representation that is not well suited to the true nature of the environment. To prevent the tree from over-fitting and to allow it to adapt to changing environments, Relational UTree implements online tree restructuring based on the Iterative Tree Induction algorithm [Utgoff et al., 1997]. Iterative Tree Induction ensures that the best split for the instances is used at each node of the tree, beginning with the root and working its way to the leaves.

The original ITI algorithm kept track of a list of statistics for each possible test at every tree node. Because Relational UTree is instance based, this would be redundant. While ITI looked at the list of statistics for a node to decide the current best test at that node, Relational UTree regenerates tests for the node and decides which is best directly. Keeping track of all possible tests is not a practical solution in this situation because of the large search space for distinctions in relational environments. This large search space is a well known problem for inductive logic programming [Dzeroski et al., 2001]. Although it is more computationally expensive to recompute the tests, restructuring leads to significantly smaller trees which reduces overall computation time.

3 Experimental Results

3.1 Blocks World Results

We apply Relational UTree to two versions of the blocks world domain. The first, blocksworld1, is a partially observable blocksworld task with low-level actions and two blocks, as in Finney et al. [2002]. The second, blocksworld2, is a fully observable domain with high-level relational actions and three blocks, as in Driessens et al. [2001]. Both domains contain moveable colored blocks and unmovable table blocks.

Example observations for both domains are shown in Figure 1.

In the blocksworld1 domain, the agent has a focus marker and a deictic marker. The agent perceives all attribute information for the focused object but none for the marked object. The marker is only observable if it is adjacent to the focus marker. For example, if the marker is below the focus block, then the agent will observe a block object, a marker object, and a relationship indicating the block object is on the marker object. The small difference from Finney's domain arise from the translation from a deictic representation to a truly relational one. The goal is to pick up the green block, which requires first removing any blocks covering it. The actions available to the agent are identical to that of Finney: move-focus(direction), focus-on(color), pick-up(), put-down(), marker-to-focus(marker), and focusto-marker(marker). The agent is given a reward of +10 for reaching the goal, a penalty of -0.2 for invalid moves and -0.1 per time step.

The second domain, blocksworld2, is fully observable and the task is to stack the green block on the red block. The actions are move(x,y) for unique blocks x and y. As with Driessens, the agent received a reward of 1 for reaching the goal in the minimal number of steps and a 0 otherwise.

The performance of Relational UTree with and without tree restructuring for both domains is shown in Figure 4 (left panels). Empirical performance is ε-optimal, with ε = 0.10, for both domains. These results are averages across 30 runs. Because this is online performance, large changes to the tree's structure are reflected as temporary drops in performance. This happens less frequently as the tree converges.

In the more difficult blocksworld1 domain, Relational UTree converges faster than Finney's approach with more accurate results. After 100,000 training instances Finney's performance was approximately 68% with final convergence to 80%. Our method converges to 90% of optimal, due to the use of ε-greedy exploration methods, and does so within the first 100,000 steps.

Comparatively, the actions in the blocksworld2 domain are higher level which allows the agent to discover the goal much faster than in blocksworld1. The performance of Driessens' TG algorithm on the same domain was comparable. TG does not explore the environment, and does not use an ε-greedy exploration method like we do. This allows their algorithm to converge to an average reward of 1, while we converge to an average reward per trial of 0.9.

Figure 4 (right panels) compares the tree sizes with and without tree restructuring for the two domains. In both domains, performance is comparable but the average tree size is considerably smaller when tree restructuring is used. The agent is able to construct a smaller tree to capture the same amount of information because it can remove irrelevant information gained early in learning. The use of restructuring introduces an increased variance due to the temporary loss in performance directly following a large tree restructuring. However, smaller trees result in a significant improvement in running time.

10 3

3.2 Autocorrelation

To detect potential temporal autocorrelation, we used randomization on sets of observations. We perform 10000 randomizations on this data, each time performing a Kolmogorov-Smirnov test. The test statistics form a distribution which can be analyzed to find the effective sample size, similar to what was done with χ 2 by Jensen and Neville [2002]. If there is no autocorrelation, the effective sample size should match the actual sample size used in the tests.

The Kolmogorov-Smirnov test compares two distributions, of sizes N1 and N2. The total size of the data, N1+N2, remains constant throughout, while the proportion of data split into either distribution can change from one distinction to the next. In our experiment, the actual number of instances varied but the proportions that a specific distinction created was held constant. We use p = max(N1,N2) (N1+N2) to represent the relative sizes of the two distributions. By substituting p into the original equation for KS, given by [Sachs, 1982], we obtain R = (2×(Kα)2 ) Dα and NE = 2× R (4×(p-p 2 )) for the effective sample size NE. Kα and Dα are the critical values for the KS test.

Figure 5 shows the results of our detection and removal of the temporal autocorrelation in the blocks world domain. The top pie chart for each group is the effective sample size without sampling. The lower two pie charts are for removing every 15th or every 10th instance. Effective sample sizes for an object existence, relationship, and action test are shown.

The effective sample size is dramatically lower without sampling and small amounts of sampling dramatically increase the sample size. Tests on actions have no temporal autocorrelation because there is no direct correlation between what action will be performed and what the most recent action was. Since autocorrelation causes a feature selection bias [Jensen and Neville, 2002], Relational UTree used sampling to remove the autocorrelation.

3.3 Tsume Go Results

The Tsume Go domain is a sub-task of the game of Go where stones have already been placed in different configurations. The task is to identify the best move for protecting the player's stones or capturing the opponent's stones. Relational UTree learns to play the best first move of a Tsume Go game. Relational UTree is trained on a set of 30000 randomly sampled problems from the GoTools database [Wolf, 1996], and then tested on a set of 10000 randomly sampled independent problems from the same database. The agent receives a reward between 0 and 1 for correct answers depending on the quality of the move and is penalized -0.5 for incorrect attempts. It is also penalized with -1.0 for invalid moves such as placing a stone on top of another stone or trying to move off the board.

Similar to Ramon et al.'s [2001] approach, we test Relational UTree's approximation by ranking moves using the Qvalues. Across 7 runs, Relational UTree averaged 65% accuracy on the test set after one move. Ramon et al.'s [2001] approach obtained 35% accuracy on a test set of 1000 problems generated by GoTools, after training on 2600 problems. We are encouraged by our results and are exploring this domain in greater detail as future work.

4 Discussion

Due to the significant performance difference between Finney and the large degree of similarities between our algorithm and Finney's, it is useful to discuss why Relational UTree was able to overcome some of the problems previously reported. Relying on observation history to disambiguate states and using state values to determine a policy before the states are disambiguated is a difficult problem that can be overcome through the use of tree restructuring. As the agent continues to learn, it carries older instances whose histories reflect outdated policies. As the agent's performance increases, the vast majority of new observations will conform to an increasingly consistent policy. Given sufficient experience with the new policy, old observations will be in such a minority that splitting on them will no longer be statistically significant. Another method would be to remove the oldest memories of the agent when they are likely to no longer be relevant but this approach requires another parameter.

Finney's approach uses a combination of the G-Algorithm and UTree to learn with a deictic representation. In their approach, once the tree has been expanded at a node, all the instance information that caused that split is dropped. This is in contrast to the approach taken by Relational UTree, which saves instances and continues to use all observations to decide if a split is utile. We hypothesize that this difference is the cause of their convergence issues. Each split relies only on the most recent observations to see how the environment behaves. This could lead to incorrect assumptions if the current set of data is not representative of the entire environment.

Another problem encountered comes from the nature of POMDPs. If the agent in blocksworld1 performed the action focus on color(red), its history of observations would not tell it what state it was in. Finney suggests that history based decision tree algorithms will never be able to fully disambiguate the state space. While it is true that the agent's history would not help it to know the current state of the world, this information is not required for optimal behavior. Instead, the optimal behavior for this agent is to explore. Balancing the need to explore to discover information about the environment, and seeking out potential rewards, is a primary property of POMDPs [Kaebling et al., 1998]. As such, the optimal policy would explore the environment, thus providing the agent with the useful historical observations that it needs.

5 Conclusions and FutureWork

We have introduced Relational UTree, a significant modification to the UTree algorithm that automatically creates a treebased function approximation in a relational representation. Relational UTree allows us to apply the advantages of the UTree algorithm to inherently relational environments without the need to convert into propositional logic. We demonstrated that Relational UTree is able to learn in a blocks world domain and on the task of Tsume Go. Relational UTree addresses the exponential growth in search space of a relational representation using stochastic sampling. We also demonstrated that temporal sampling was necessary to address the issues of autocorrelation that arise in a relational representation. We separately show that incorporating tree restructuring into Relational UTree gives it the critical ability to learn compact representations and to adapt to changing environments.

Current and future work focuses on applying Relational UTree to more complex relational domains, including the full game of Go. We are also exploring ways to improve the efficiency of storing and handling large numbers of observations. We are studying knowledge transfer and background knowledge using Relational UTree. The ability to approximate a state space independently of a human designer allows for many interesting future applications.

Acknowledgements

We would like to thank the anonymous reviewers for their insightful comments. This material is based upon work supported by the National Science Foundation under Grant No. NSF/CISE/REU 0453545.