State Similarity Based Approach for Improving Performance in RL

1 Introduction

Reinforcement learning (RL) is the problem faced by an agent that must learn behavior through trial-and-error interactions with a dynamic environment, by gaining percepts and rewards from the world and taking actions to affect it. In most of the realistic and complex domains, the task that an agent tries to solve is composed of various subtasks and has a hierarchical structure formed by the relations between them [Barto and Mahadevan, 2003]. Each of these subtasks repeats many times at different regions of the state space. Although all instances of the same subtask, or similar subtasks, have almost identical solutions, without any (self) guidance an agent has to learn these solutions independently by going through similar learning stages again and again. This situation affects the learning process in a negative way, making it difficult to converge to optimal behavior in reasonable time.

The main reason of this problem is the lack of connections, that would allow to share solutions, between similar subtasks scattered throughout the state space. One possible way to build connections is to use temporally abstract actions (TAAs), which generalize primitive actions and last for a period of time [Sutton et al., 1999; Dietterich, 2000; Barto and Mahadevan, 2003]. TAAs can be included in the problem definition, which requires extensive domain knowledge and becomes more difficult as the complexity of the problem increases, or be constructed automatically either by finding sub-goal states and generating corresponding options that solve them [Stolle and Precup, 2002; Menache et al., 2002; Mannor et al., 2004; Simsek et al., 2005] or by identifying frequently occurring patterns over the state, action and reward trajectories [McGovern, 2002; Girgin et al., 2006]. Since different instances of the same or similar subtasks would probably have different subgoals in terms of state representation, with subgoal based methods they will be discovered and treated separately. Although sequence based methods are capable of combining different instances of the same subtask, multiple abstractions may be generated for each of them.

∗This work was supported by the Scientific and Technological Research Council of Turkey under Grant No. 105E181(HD-7).

TAA based methods try to solve the solution sharing problem inductively. Based on the fact that states with similar patterns of behavior constitute the regions of state space corresponding to different instances of similar subtasks, the notion of state equivalence can be used as a more direct mechanism of solution sharing. By reflecting experience acquired on one state to all similar states, connections between similar subtasks can be established implicitly. In fact, this reduces the repetition in learning, and consequently improves the performance. State equivalence is closely related with model minimization in Markov Decision Processes (MDPs), and various definitions exist. [Givan et al., 2003] define equivalence of states based upon stochastic bisimilarity, such that two states are said to be equivalent if they are both action sequence and optimal value equivalent. Based on the notion of MDP homomorphism, [Ravindran and Barto, 2001; 2002] extended equivalence over state-action pairs, which as a result allows reductions and relations not possible in case of bisimilarity. Furthermore, they applied state-(action) equivalence to the options framework to derive more compact options without redundancies, called relativized options. While relativized options are defined by the user, instances are generated automatically. [Zinkevich and Balch, 2001] also addressed how symmetries in MDPs can be used to accelerate learning by employing equivalence relations on the stateaction pairs; in particular for the multi-agent case, where permutations of features corresponding to various agents are prominent, but without explicitly formalizing them.

In this paper, following homomorphism notion, we propose a method to identify states with similar sub-policies without requiring a model of the MDP or equivalence relations, and show how they can be integrated into RL framework to improve the learning performance. Using the collected history of states, actions and rewards, traces of policy fragments are generated and then translated into a tree form to efficiently identify states with similar sub-policy behavior based on the number of common action-reward sequences. Updates on the action-value function of a state are then reflected to all similar states, expanding the influence of new experiences. The proposed method can be treated as a metaheuristic to guide any underlying RL algorithm. We demonstrate the effectiveness of this approach by reporting test results on two domains, namely various versions of the taxi cab and the room doorway problems. Further, the proposed method is compared with other RL algorithms, and a substantial level of improvement is observed on different test cases. Also, we present how the performance of out work compares with hierarchical RL algorithms, although the approaches are different. The tests demonstrate the applicability and effectiveness of the proposed approach.

The rest of this paper is organized as follows: In Section 2, we briefly describe the standard RL framework of discrete time, finite MDPs, define state equivalence based on MDP homomorphisms, and show how they can be used to improve the learning process. Our approach to how similar states can be identified during the learning process is presented in Section 3. Experimental results are reported and discussed in Section 4. Section 5 is conclusions.

2 Background andMotivation

In this section, we briefly overview the background necessary to understand the material introduced in this paper. We start by defining MDP and related RL problem.

An MDP is a tuple 〈S,A,Ψ, T,R〉, where S is a finite set of states, A is a finite set of actions, Ψ ⊆ S×A is the set of admissible state-action pairs, T : Ψ×S → [0, 1] is a state transition function such that ∀(s, a) ∈ Ψ, ∑s′ ∈S T (s, a, s′) = 1, and R : Ψ → ℜ is a reward function. R(s, a) is the immediate expected reward received when action a is executed in state s. 1 A (stationary) policy, π : Ψ → [0, 1], is a mapping that defines the probability of selecting an action in a particular state. The value of a state s under policy π, V π (s), is the expected infinite discounted sum of rewards that the agent will gain if it starts in state s and follows π. In particular, if the agent takes action a at state s and then follows π, the resulting sum is called the value of the state-action pair (s, a) and denoted Qπ (s, a). The objective of an agent is to find an optimal policy, π∗ , which maximizes the state value function for all states. Based on the experience in the form of sample sequences of states, actions, and rewards collected from on-line or simulated trial-and-error interactions with the environment, RL methods try to find a solution to an MDP by approximating optimal value functions. Detailed discussions of various approaches can be found in [Kaelbling et al., 1996; Sutton and Barto, 1998; Barto and Mahadevan, 2003].

RL problems, in general, inherently contain subtasks that need to be solved by the agent. These subtasks can be represented by simpler MDPs that locally preserve the state transition and reward dynamics of the original MDP. Let M =

1 s, a is used instead of (s, a), wherever possible.

〈S, A, Ψ, T , R〉 and M ′ = 〈S ′ ∪{sΥ}, A′ ∪{aΥ}, Ψ′ , T ′ , R′ 〉 be two MDPs, such that sΥ is an absorbing state with a single admissible action aΥ which, once executed, transitions back to sΥ with certainty. A surjection h : Ψ → Ψ′ ∪ {(sΥ, aΥ)} is a partial MDP homomorphism (pMDPH) from M to M ′ , if for all states that do not map to sΥ, state-action pairs that have the same image under h also have the same block transition behavior in M and the same expected reward 2 . Under h, M ′ is called the partial homomorphic image of M 3 . Two state-action pairs (s1, a1) and (s2, a2) in M are said to be equivalent if h(s1, a1) = h(s2, a2); states s1 and s2 are equivalent if there exists a bijection ρ : As1 →As2 such that ∀a ∈ As1 , h(s1, a) = h(s2, ρ(a)). The set of state-action pairs equivalent to (s, a), and the set of states equivalent to s are called the equivalence classes of (s, a) and s, respectively. [Ravindran and Barto, 2001] proved that if h above is a complete homomorphism, then an optimal policy π∗ for M can be constructed from an optimal policy for M ′4 . This makes it possible to solve an MDP by solving one of its homomorphic images which can be structurally simpler and easier to solve. However, in general such a construction is not viable in case of pMDPHs, since the optimal policies would depend on the rewards associated with absorbing states.

For example, consider the deterministic MDP M given in Fig. 1(a). If the discount factor, γ, is set as 0.9, then optimal policy at s2 is to select action a2; M ′ given in Fig. 1(b) is a partial homomorphic image of M 5 and one can easily determine that Q∗ (s2, a1) = 1 and Q∗ (s2, a2) = 9 ∗ c, where c is the expected reward for executing action aΥ at the absorbing state. Accordingly, the optimal policy for M ′ at s2 is to select a1 if c < 1/9, and a2 otherwise, which is different than the optimal policy for M. This example demonstrates that unless reward functions are chosen carefully, it may not be possible to solve a given MDP by employing the solutions of its partial homomorphic images. However, if equivalence classes of state-action pairs and states are known, they can be used to speed up the learning process. Let (s, a) and (s′ , a′ ) be two equivalent state-action pairs in a given MDP M based on the partial homomorphic image M ′ of M under the surjection h.

2h((s, a)) = (f(s), gs(a)), where f : S → S′ ∪ Υ is a surjection and {gs : As → A′f(s) |s ∈ S} is a set of state dependent surjections.

3 For a formal definition see [Ravindran and Barto, 2001; 2002] 4∀a ∈ g-1 s (a′), π∗(s, a) = π∗M′ (f (s), a′ )/|g-1 s (a′ )|

5 Under h defined as f(s1) = s1, f(s2) = s2, f(s3) = f(s4) = sΥ, g{s1,s2}(a1) = a1, gs2 (a2) = a2, g{s3,s4}(a1) = aΥ

Suppose that while learning the optimal policy, the agent selects action a at state s which takes it to state t with an immediate reward r, such that t is mapped to a non-absorbing state under h. Let Ω be the set of states in M which are accessible from s′ by taking action a′ , i.e. probability of transition is non-zero, and are mapped to the same state in M ′ as t under h. By definition, for any t′ ∈ Ω, the probability of experiencing a transition from s′ to t′ upon taking action a′ is equal to that of from s to t upon taking action a. Also, since (s, a) and (s′ , a′ ) are equivalent, we have R(s, a) = R(s′ , a′ ), i.e., both state-action pairs have the same expected reward, and since t is mapped to a non-absorbing state, independent of the reward assigned to the absorbing state, they have the same policy. Therefore, for any state t′ ∈ Ω, o = 〈s′ , a′ , r, t′ 〉 can be regarded as a virtual experience tuple and Q(s′ , a′ ) can be updated similar to Q(s, a) based on observation o, i.e., pretending as if action a′ transitioned the agent from state s′ to state t′ with an immediate reward r.

The method described above assumes that equivalence classes of states and corresponding pMDPHs are already known. If such information is not available prior to learning, then, for a restricted class of pMDPHs, it is still possible to identify states that are similar to each other with respect to state transition and reward behavior based on the history of events, as we show in the next section. Experience gathered on one state, then, can be reflected to similar states to improve the performance of learning.

3 Finding Similar States

For the rest of the paper, we will restrict our attention to direct pMDPHs in which, except the absorbing state and its associated action, the action sets of an MDP and its homomorphic image are the same and there is an identity mapping on the action component of state-action tuples 6 . Let M = 〈S,A,Ψ, T,R〉 be a given MDP. Starting from state s, a sequence of states, actions and rewards σ = s1, a2, r2, . . . , rn-1, sn, such that s1 = s and each ai, 2 ≤ i ≤ n - 1, is chosen by following a policy π is called a π-history of s with length n. ARσ = a1r1a2 . . . an-1rn-1 is the action-reward sequence of σ, and the restriction of σ to Σ ⊆ S, denoted by σΣ, is the longest prefix s1, a2, r2, . . . , ri-1, si of σ, such that for all j = 1..i, sj ∈ Σ and si+1 /∈ Σ. If two states of M are equivalent under a direct pMDPH h, then the set of images of π-histories restricted to the states that map to non-absorbing states under h, and consequently, the list of associated actionreward sequences are the same 7 . This property of equivalent states leads to a natural approach to calculate the similarity between any two states based on the number of common action-reward sequences.

6 gs(a) = a, for every s that maps to a non-absorbing state.

7 Let (s, a) and (s′ , a′ ) be two state-action pairs that are equivalent to each other based on partial homomorphic image M ′ = 〈S′ ∪ {sΥ}, A ∪ {aΥ}, Ψ′ , T ′ ,R′ 〉 of M = 〈S,A, Ψ, T,R〉 under direct pMDPH h. Consider a π-history of state s of length n, and let Σh ⊆ S be the inverse image of S′ under h, and σΣh = s1, a2, r2, . . . , rk-1, sk, k ≤ n be the restriction of σ on Σh. The image of σΣh under h, denoted by F(σΣh ), is obtained by mapping each state si to its counterpart in S′ , i.e., F(σΣh ) = h(s1), a2, r2, h(s2), a3, . . . , rk-1, h(sk). By definition, F(σΣh ) is a π-history of h(s) in M ′ , and since s and s′ are equivalent, there

Given any two states s and s′ in S, let Πs,i be the set of π-histories of state s with length i, and ςi(s, s′ ) calculated as

be the ratio of the number of common action-reward sequences of π-histories of s and s′ with length up to i to the number of action-reward sequences of π-histories of s with length up to i. ςi(s, s′ ) will be close to 1, if s′ is similar to s in terms of state transition and reward behavior; and close to 0, in case they differ considerably from each other. Note that, even for equivalent states, the action-reward sequences will eventually deviate and follow different courses as the subtask that they are part of ends. As a result, for i larger than some threshold value, ςi would inevitably decrease and no longer be a permissible measure of the state similarity. On the contrary, for very small values of i, such as 1 or 2, ςi may over estimate the amount of similarity since number of common action-reward sequences can be high for short action-reward sequences. Also, since optimal value of i depends on the subtasks of the problem, to increase robustness, it is necessary to take into account action-reward sequences of various lengths. Therefore, the maximum value or weighted average of ςi(s, s′ ) over a range of problem specific i values, kmin and kmax, can be used to combine the results of evaluations and approximately measure the degree of similarity between states s and s′ , denoted by ς(s, s′ ). Once ς(s, s′ ) is calculated, s′ is regarded as equivalent to s if ς(s, s′ ) is over a given threshold value τsimilarity . Likewise, by restricting the set of π-histories to those that start with a given action a in the calculation of ς(s, s′ ), similarity between state-action pairs (s, a) and (s′ , a) can be measured approximately.

If the set of π-histories for all states are available in advance, then equivalent states can be identified prior to learning. However, in general, the dynamics of the system is not known in advance and consequently such information is not accessible. Therefore, using the history of observed events (i.e. sequence of states, actions taken and rewards received), the agent must incrementally store the π-histories of length up to kmax during learning and enumerate common actionreward sequences of states in order to calculate similarities between them. For this purpose, we propose an auxiliary structure called path tree, which stores the prefixes of actionreward sequences of π-histories for a given set of states. A path tree P = 〈N, E〉 is a labeled rooted tree, where N is the set of nodes, such that each node represents a unique actionreward sequence; and e = (u, v, 〈a, r〉) ∈ E is an edge from u to v with label 〈a, r〉, indicating that action-reward sequence v is obtained by appending a, r to u, i.e., v = uar. The root node represents the empty action sequence. Furthermore, each node u holds a list of 〈s, ξ〉 ∈ S ×R tuples, stating that state s has one or more π-histories starting with

exists a π-history σ′ of s′ such that the image of its restriction to Σh under h is equal to F(σΣh ), i.e., F(σ′Σh ) = F(σΣh ); and furthermore ARσ′Σh = ARσΣh .

Algorithm 1 Q-learning with equivalent state update.

• 1: Initialize Q arbitrarily (e.g., Q(·, ·) = 0) 2: Let T be the path tree initially containing root node only. 3: repeat 4: Let s be the current state 5: repeat ▷ for each step 6: Choose and execute a from s using policy derived from Q with sufficient exploration. Observe r and the next state s′ ; append 〈s, a, r, s′ 〉 to observation history. 7: ΔQ(s, a) = α(r + γ maxa′∈As′ Q(s′ , a′ ) - Q(s, a)) 8: for all (t, at) similar to (s, a) do 9: Let t′ be a state similar to s′ . 10: ΔQ(t, at) = α(r + γ maxat′∈At′ Q(t′ , at′) - Q(t, at)) 11: end for 12: s = s′ 13: until s is a terminal state 14: Using the observation history, generate the set of π-histories of length up to kmax and add them T . 15: Traverse T and update eligibility values of the tuples in each node; prune tuples with eligibility value less than ξthreshold. 16: Calculate ς and determine similar states s, s′ such that ς(s, s′ ) > τsimilarity. 17: Clear observation history. 18: until a termination condition holds

action sequence σu. ξ is the eligibility value of σu for state s, representing its occurrence frequency. It is incremented every time a new π-history for state s starting with action sequence σu is added to the path tree, and gradually decremented otherwise. A π-history h = s1a2r2 . . . rk-1sk can be added to a path tree by starting from the root node, following edges according to their label. Let ˆn denote the active node of the path tree, which is initially the root node. For i = 1..k-1, if there is a node n such that ˆn is connected to n by an edge with label 〈ai, ri〉, then either ξ of the tuple 〈s1, ξ〉 in n is incremented or a new tuple 〈s1, 1〉 is added to n if it does not exist, and ˆn is set to n. Otherwise, a new node containing tuple 〈s1, 1〉 is created, and ˆn is connected to this node by an edge with label 〈ai, ri〉. The new node becomes the active node.

After each episode, or between two termination conditions such as reaching reward peaks in case of non-episodic tasks, using the consecutive fragments of the observed sequence of states, actions and rewards, a set of π-histories of length up to kmax are generated and added to the path tree using the procedure described above. Then, the eligibility values of tuples in the nodes of the tree are decremented by a factor of 0 < ξdecay < 1, called eligibility decay rate, and tuples with eligibility value less than a given threshold, ξthreshold, are removed to keep the tree of manageable size and focus the search on recent and frequently used action-reward sequences. Using the generated path tree, ς(s, s′ ) can be calculated incrementally for all s, s′ ∈ S by traversing it in breadth-first order and keeping two arrays κ(s) and K(s, s′ ). κ(s) denotes the number of nodes containing s, and K(s, s′ ) denotes the number of nodes containing both s and s′ in their tuple lists. Initially ς(s, s′ ), K(s, s′ ), and κ(s) are set to 0. At each level of the tree, the tuple lists of nodes at that level are processed, and κ(s) and K(s, s′ ) are incremented accordingly. After processing level i, kmin ≤ i ≤ kmax, for every s, s′ pair that co-exist in the tuples list of a node at that level, ς(s, s′ ) is compared with K(s, s′ )/κ(s) and updated if the latter one is greater. Note that, since eligibility values stored in the nodes of the path tree is a measure of occurrence frequencies of corresponding sequences, it is possible to extend the similarity function by incorporating eligibility values in the calculations as normalization factors. This would improve the quality of the metric and also result in better discrimination in domains with high degree of non-determinism, since the likelihood of the trajectories will also be taken into consideration. In order to simplify the discussion, we opted to omit this extension. Once ς values are calculated, equivalent states, i.e., state pairs with ς greater than τsimilarity, can be identified and incorporated into the learning process. The proposed method applied to Q-learning algorithm is presented in Alg. 1.

4 Experiments

We applied the similar state update method described in Section 3 to Q-learning and compared its performance with different RL algorithms on two test domains: a six-roommaze 8 and various versions of the taxi problem 9 (Fig. 2(a)). Also, its behavior is examined under various parameter settings, such as maximum length of π-histories and eligibility decay rate. In all test cases, the initial Q-values are set to 0, and ϵ-greedy action selection mechanism, where action with maximum Qvalue is selected with probability 1 - ϵ and a random action is selected otherwise, is used with ϵ = 0.1. The results are averaged over 50 runs. Unless stated otherwise, the path tree is updated using an eligibility decay rate of ξdecay = 0.95 and an eligibility threshold of ξthreshold = 0.1, and in similarity calculations the following parameters are employed: kmin = 3, kmax = 5, and τsimilarity = 0.8.

Fig. 2(b) shows the total reward obtained by the agent until goal position is reached in six-room maze problem when equivalent state update is applied to Q-learning and Sarsa(λ) algorithms. Based on initial testing, we used a learning rate and discount factor of α = 0.125, and γ = 0.90, respectively. For the Sarsa(λ) algorithm, λ is taken as 0.98. State similarities are calculated after each episode. As expected, due to backward reflection of received rewards, Sarsa(λ) converges much faster compared to Q-learning. The learning curve of

8 The agent's task is to move from a randomly chosen position in the top left room to the goal location in the bottom right room using primitive actions that move the agent to one of four neighboring cells. Each action is non-deterministic and succeeds with probability 0.9, or moves the agent perpendicular to the desired direction with probability 0.1. The agent only receives a reward of 1 when it reaches the goal location and a negative reward of -0.01 otherwise.

9 The agent tries to transport a passenger between predefined locations on a n × n grid world using six primitive actions: move to one of four adjacent squares, pickup or dropoff the passenger. Should a move action cause the agent hit to wall/obstacle, the position of the agent will not change. The movement actions are nondeterministic and with 0.2 probability agent may move perpendicular to the desired direction. An episode ends when the passenger is successfully transported and the agent receives a reward of +20. There is an immediate negative reward of -10 if pickup or drop-off actions are executed incorrectly, and -1 for any other action.

Q-learning with equivalent state update indicates that, starting from early states of learning, the proposed method can effectively utilize state similarities and improve the performance considerably. Since convergence is attained in less than 20 episodes, the result obtained using Sarsa(λ) with equivalent state update is almost indistinguishable from that of Q-learning with equivalent state update.

The results of the corresponding experiments in 5 × 5 taxi problem showing the total reward obtained by the agent is presented in Fig. 2(c). The initial position of the taxi agent, location of the passenger and its destination are selected randomly with uniform probability. α is set to 0.05, and λ is taken as 0.9 in Sarsa(λ) algorithm. State similarities are computed every 5 episodes starting from the 20th episode in order to let the agent gain experience for the initial path tree. Similar to the six-roommaze problem, Sarsa(λ) learns faster than regular Q-learning. In SMDP Q-learning [Bradtke and Duff, 1994], in addition to primitive actions, the agent can select and execute hand-coded options, which move the agent from any position to one of predefined locations using minimum number of steps. Although SMDP Q-learning has a very steep learning curve in the initial stages, by utilizing abstractions and symmetries more effectively Q-learning with equivalent state update performs better in the long run. The learning curves of algorithms with equivalent state update reveals that the proposedmethod is successful in identifying similar states which leads to an early improvement in performance, which allows the agent to learn the task more efficiently. The results for the larger 12 × 12 taxi problem presented in Fig. 2(d) demonstrate that the improvement becomes more evident as the complexity of the problem increases.

The proposed idea of using state similarities and then updating similar states leads to more state-action value, i.e., Qvalue, updates per experience. It is known that remembering past experiences and reprocessing them as if the agent repeatedly experienced what it has experienced before, which is called experience replay [Lin, 1992], speed up the learning process by accelerating the propagation of rewards. Experience replay also results in more updates per experience. In order to test whether the gain of the equivalent state update method in terms of learning speed is simply due to the fact that more Q-value updates are made or not, we compared its performance to experience replay using the same number of updates. The results obtained by applying both methods to regular Q-learning algorithm on the 5 × 5 taxi problem are presented in Fig. 2(e). Even though the performance of learning improves with experience replay, it falls short of Q-learning with equivalent state update. This indicates that in addition to number of updates, how they are determined is also important. By reflecting updates in a semantically rich manner based on the similarity of action-reward patterns, rather than neutrally as in experience replay, the proposed method turns out to be more efficient. Furthermore, in order to apply experience replay, the state transition and reward formulation of a problem should not change over time as past experiences may no longer be relevant otherwise. The dynamic nature of the sequence tree allows the proposed method to handle such situations as well.

In order to analyze how various parameter choices of the proposed method affect the learning behavior, we conducted a set of experiments under different settings. The results for various ξdecay values are presented in Fig. 2(f,g). As the eligibility decay decreases, the number of π-histories represented in the path tree also decrease, and recent π-histories dominate over existing ones. Consequently, the less number of equivalent states can be identified and the performance of the method also converges to that of regular Qlearning. Fig. 2(h,i) shows how the length of π-histories affect the performance in the taxi domain. Different kmax values show almost indistinguishable behavior, although the path tree shrinks considerably as kmax decreases. Despite the fact that minimum and maximum π-history lengths are inherently problem specific, in most applications, kmax near kmin is expected to performwell as restrictions of pMDPHs to smaller state sets will also be pMDPHs themselves.

5 Conclusions

In this paper, we proposed and analyzed the interesting and useful characteristics of a tree-based approach that, during learning, identifies states similar to each other with respect to action-reward patterns, and based on this information reflects state-action value updates of one state to multiple states. Experiments conducted on two well-known domains highlighted the applicability and effectiveness of utilizing such a relation between states in the learning process. The reported test results demonstrate that experience transfer performed by the algorithm is an attractive approach to make learning systems more efficient. However, when the action set is very large, the parameters, such as eligibility decay, must be chosen carefully in order to reduce the computational cost and keep the size of the tree manageable. Also, instead of matching actionreward sequences exactly, they can be matched partially and grouped together based on their reward values (ex. ϵ neighborhood). This is especially important in cases where the immediate reward has a distribution. We are currently working on adaptation of the method to continuous domains, which also covers these issues. Furthermore, since the similarity between two states is a value which varies between 0 and 1, rather than thresholding to determine equivalent states and reflecting the whole experience, it is possible to make use of the degree of similarity, for example, by updating Q-values in proportion to their similarity. Future work will examine possible ways of extending and improving the proposed method to consider such information.