Markovian State and Action Abstractions for MDPs via Hierarchical MCTS

1 Introduction

Markov decision processes (MDPs) provide a rich framework for planning and learning under uncertainty. In this paper, we focus on the problem of online planning in MDPs. An online planning algorithm finds the best action for the current state by exploring an expectimax search tree starting from the current state [Barto et al., 1995; Hansen and Zilberstein, 2001; Kocsis and Szepesv´ari, 2006]. Take Monte Carlo tree search (MCTS) [Browne et al., 2012] as an example. It has been observed that the performance of MCTS is typically dominated by the effective search depth [Kearns et al., 2002; Hostetler et al., 2014], which in turn is determined by the branching factor of the search tree. In MDPs, the branching factor consists of action branching and stochastic branching. Action branching depends on the number of available actions; stochastic branching depends on the number of possible outcomes for an action. Most online planning algorithms build search trees in the ground state space; for large problems, the branching factor leads to poor performance as the feasible search depth is too small.

State abstraction is an important technique for reducing the stochastic branching factor by treating a group of states as a unit [Dearden and Boutilier, 1997; Li et al., 2006]. The space of abstract states is typically much smaller than the original

Stuart Russell

UC Berkeley russell@cs.berkeley.edu

concrete state space. However, abstraction results in a nonMarkovian model, because the transition probability of reaching the next abstract state and the reward received by taking an action within an abstract state depend on the occupancy probability over concrete states represented by that abstract state. The occupancy probability depends on the history of all past actions and abstract states. As an example, in the 3-state MDP depicted in Figure 1a, an edge represents a deterministic transition that is invoked by executing the labeled action. If we group states 1 and 2 into an abstract state S1↪2, then the probability of reaching state 3 after taking action a in S1↪2 equals the probability of being actually in state 1, which depends exactly on the number of times that the agent has executed action b in ground state 1 and action a in ground state 2 in the past history prior to entering state 3.

Safe state abstraction methods avoid the non-Markovian problem by ignoring only irrelevant state variables [Dietterich, 1999b; Andre and Russell, 2002] or exploiting particular structure in the transition function (e.g., bisimulation and homomorphism) [Dearden and Boutilier, 1997; Givan et al., 2003; Jiang et al., 2014; Anand et al., 2015]. Such methods result in (near) lossless abstractions but are often inapplicable. One popular proposal to resolve this situation is to introduce an ad hoc weighting function (a.k.a. an aggregation probability), which functions like an occupancy probability for each concrete state given the abstract state [Bertsekas, 1995; Singh et al., 1995; Li et al., 2006]. Superficially, this ensures that the abstract transition and reward functions can be written in a Markovian way. It is usually assumed that the weighting function is manually specified and remains constant in computation. We argue that such approaches cannot be accurate enough to capture the true dynamics of the abstract system, where the occupancy probability is in fact non-stationary, depending on the whole history of past actions and abstract states, or in other words, the policy being computed/executed!

In this paper, we show that a ground MDP with state abstraction turns out to be a POMDP with the original ground MDP as the underlying MDP and the set of abstract states as the set of observations. Belief states in the resulting POMDP replace the otherwise necessary weighting function, with the advantage that the belief state can be calculated by Bayesian updating. We show that algorithms such as POMCP can be naturally extended to do online planning for the ground MDP.

Observing that the set of abstract states introduces automatically a hierarchical structure, we further define temporal transitions between abstract states as abstract actions by extending the theory of options [Sutton et al., 1999] to a POMDP setting, and develop a hierarchical MCTS algorithm that handles Markovian state and action abstractions for MDPs within a POMDP formulation. Theoretically, we show that the performance loss in terms of action values due to approximation in state abstraction is bounded by a constant multiple of a state aggregation error introduced by grouping states with different optimal actions; the resulting algorithm converges to a recursively optimal hierarchical policy consistent with the input state and action abstractions. Perhaps counterintuitively, we find that a hierarchical MCTS algorithm solving the abstracted POMDP can outperform ground MCTS by orders of magnitude.

2 Background

2.1 MDPs and POMDPs

An MDP is a tuple hS↪A↪ T↪R↪ γi, where S and A are the state and action spaces, T(s0 ♣s↪ a) and R(s↪ a) are the transition and reward functions, and γ is a discount factor [Bellman, 1957]. A solution for an MDP is an optimal policy ⇡⇤ : S ! A that maximizes the expected cumulative discounted reward (the value function) for all states. The optimal value function V ⇤ satisfies the Bellman equation:

A partially observable MDP, or POMDP, is a tuple hS↪A↪Z↪ T↪R↪⌦↪ γi, where Z is the observation space and ⌦(z♣s↪ a) is the observation function. A sequence of actions and observations defines a history h = ¶a0↪ z1↪ a1↪ z2 · · · ↪ at-1↪ zt♦, which determines uniquely a belief state b with b(s♣h) being the probability of being in state s given h. Let end(h) be the last observation in h and let B and H be the set of all belief states and histories respectively. A POMDP can be equivalently transformed into an MDP defined over the belief space B (or the history space H). The Bellman equation for a POMDP in terms of histories is as follows:

where R(h↪ a) = Ps2S R(s↪ a)b(s♣h), Pr(z♣h↪ a) is the probability of observing z after taking action a at history h, and haz denotes the history resulting from taking action a at history h and observing z afterwards.

2.2 Monte Carlo Tree Search

For online planning in (PO)MDPs, the idea of MCTS is to build a best-first search tree by simulating a tree policy and a rollout policy to estimate the optimal action values using sampled trajectories. Upper confidence bounds for trees (UCT) is one of the most popular implementations of MCTS for MDPs using the UCB action-selection heuristic to guide the tree search [Kocsis and Szepesv´ari, 2006]. Partially observable Monte Carlo planning (POMCP) extends UCT to POMDPs by employing particle filtering and root sampling, where each simulation starts with a state sampled from the belief state b(s♣h) represented as a set of particles at the root node [Silver and Veness, 2010].

3 The Approach

3.1 State Abstraction

Consider a ground MDP M = hS↪A↪ T↪R↪ γi. Let X = ¶x1↪ x2↪ · · · ♦ be a partition on S, and ' : S ! X be an abstraction function, such that '(s) 2 X is the abstract state corresponding to ground state s. As an example, Figure 1b illustrates a rooms domain, where a robot needs to navigate from position S to position G. In the figure, black cells represent walls; all other cells are valid ground states. Cells sharing the same color correspond to the same abstract state, which in turn represents a room.

A so-called weighting function w has been introduced in the literature to ensure that the abstract transition and reward functions can be written in a Markovian way:

and

where w(s↪ x) approximates the abstract-state-specific occupancy probability Pr(s♣x) of being in ground state s given that the agent is in abstract state x [Bertsekas, 1995; Li et al., 2006]. An abstract MDP hX↪A↪ T'↪R'↪ γi is then defined on the abstract space X. Solving this abstract MDP gives a policy ⇡' : X ! A, which can be translated to the ground MDP M. The problem here is that the true occupancy probability Pr(s♣h), with h being the whole history of past actions and abstract states, is non-stationary. It cannot reasonably be approximated as a constant weighting function conditioned only on abstract state; in fact, it follows a Bayesian update

where 1 is the indicator function and ⌘ is a normalizing factor. On the other hand, if we introduce ⌦ as a conditional probability function such that ⌦(x♣s) = 1[x = '(s)] for any x 2 X and s 2 S, then the abstract problem turns out to be a POMDP hS↪ A↪ X↪ T↪ R↪ ⌦↪ γi with X and ⌦ being the observation space and the observation function respectively. We denote the resulting POMDP by POMDP(M↪ ') indicating that it is created by applying abstraction function ' on the ground MDP M.

From a POMDP perspective, the weighting function approach actually tries to approximate the belief state b(s♣h) using a constant distribution w(s↪ x) with end(h) = x, and finds a memoryless policy ⇡' as a mapping from observation space X to action space A. It has been shown that a memoryless policy for a POMDP can be arbitrarily worse than an optimal policy for the POMDP, which in turn can be arbitrarily worse than an optimal policy for the underlying MDP [Singh et al., 1994]. Thus, the weighting function approach is not well motivated from a POMDP point of view. In contrast, finding directly a near-optimal policy for POMDP(M↪ ') could be a considerably better choice for planning with state abstraction over the ground MDP M. Additionally, bounded optimality results within the POMDP formulation can also be established given a bounded state abstraction.

Exactly solving POMDP(M↪ ') via a dynamic programming method such as value iteration is usually infeasible due to the continuous nature of the belief space. However, from an online planning point of view, it can be observed that the search tree in POMDP(M↪ ') typically has a much lower branching factor than in the ground MDP M. This makes it feasible to use approximate, search-based solution techniques for solving POMDP(M↪ '). More precisely, a search-based online planning algorithm running in M starting from state s0 builds an expectimax tree T (s0) with actions as the expectation nodes and states as the maximization nodes. The branching factor of T (s0) is bounded by ♣A♣B, where B is the maximal number of possible outcomes for any state-action pair. A similar expectimax tree T (b0) with the same actions as the expectation nodes and belief states as the maximization nodes can be built by running a search-based online planning algorithm in POMDP(M↪ ') starting from belief state b0 with b0(s) = 1[s = s0]. The branching factor of T (b0) is bounded by ♣A♣B0 where B0 is the maximal number of possible observations (i.e., abstract states) for any belief-action pair. Generally, we have ♣A♣B0 < ♣A♣B, if B0 < B which holds for most abstractions due to the fact that B  ♣S♣, B0  ♣X♣ and ♣X♣ ⌧ ♣S♣. Therefore, a search-based online planning algorithm running in POMDP(M↪ ') resulting from abstraction could be much more efficient than running directly in the ground MDP M in terms of exploring the underlying expectimax search tree.

In this paper, we employ a POMCP algorithm running within POMDP(M↪ ') to find an online policy for the ground MDP with state abstraction, and refer to the resulting algorithm as POMCP(M↪ '). The online policy produced by POMCP(M↪ ') can be translated naturally to M, given the fact that when the agent is in ground state s, it can conclude that the respective belief state satisfies b(s0 ) = 1[s0 = s] for any s0 2 S. Since we are using a Monte Carlo algorithm to build the search tree, it is not necessary to have explicit representations of the underlying transition and reward functions for the ground MDP M. Only a generative model as a simulator of M is needed. Another important advantage with POMCP(M↪ ') is that it can be extended naturally to problems with continuous state spaces without significant modifications, given suitable abstraction functions defined over continuous states.

3.2 Action Abstraction

The proposed approach of state abstraction, we suggest, typically results in a search tree with a lower stochastic branching factor. The complementary approach of action abstraction (a.k.a. temporal abstraction) can increase the effective search depth by considering high-level actions composed from many concrete actions [Parr and Russell, 1998; Sutton et al., 1999; Dietterich, 1999a; Barto and Mahadevan, 2003]. A given state abstraction naturally induces an action abstraction, where abstract actions connect abstract states in a one high-level step.

We extend Sutton's options framework to a POMDP setting to model abstract actions within POMDP(M↪ '). A temporal transition from an abstract state x 2 X to one of its neighbors y 2 X is considered a named option ox!y, which is defined as a tuple hI↪ ⇡↪ βi. Here, I is the initiation set I = ¶h ♣ h 2 H ^ end(h) = x♦ indicating that ox!y is executable only at a history ending with observation x, ⇡ : H ! A is a local policy for ox!y defined over H and β is a termination condition with β(h) = 1 if end(h) = y, and β(h) = 0 otherwise. In the rooms domain, for example, oA!B is an option moving the agent from room A to room B, which is executable only if the agent observes that it is in room A, and terminates when the agent observes that it is in room B.

Let O be the set of options consisting of all possible direct transitions between abstract states. The set O can either be constructed manually by utilizing the neighboring relationship between abstract states, or learned incrementally from an empty set by introducing a new option each time a new abstract-state transition has been observed in a Monte Carlo simulation process. In this paper, we assume the former case for convenience, so the set of options is fixed in advance. The main results can also be extended to the latter case. It is not necessary to specify the local policy for each option beforehand. In fact, the proposed algorithm learns the high-level option-selection policy and the low-level, local option policies simultaneously via Monte Carlo simulation.

The overall option-selection policy θ is defined as a mapping from histories to options θ : H ! O. Let ⇡o be the local policy of option o. The hierarchical policy as a set of policies ⇧ = ¶θ↪ ⇡o1 ↪ ⇡o2 ↪ · · · ♦ represents a hierarchical solution for POMDP(M↪ '), where θ corresponds to the root task and the ⇡os correspond to its subtasks. Given ⇧, in a hierarchical control mode, the agent selects an option o = θ(ht) when initiated in a history ht, and follows the option o according to ⇡o until it terminates in ht+k (k ≥ 1), at which point a new option θ(ht+k) is selected; in a polling control mode, the agent executes the action suggested by the current option θ(ht) selected by θ at history ht, regardless of which option is selected at the last timestep. It has been shown that the polling execution of a hierarchical pol-

Agent(s0 : initial state, ' : abstraction function, ' : abstraction function, ⇧rollout : rollout policy) OnlinePlanning(h : history, T : search tree,

⇧rollout : rollout policy) h ? P(h) ¶s0♦ repeat T an empty search tree a OnlinePlanning(h↪ T ↪ '↪⇧rollout) Execute a and observe abstract state x h hax P(h) ParticleFilter(P(h)↪ a↪ x) until termination conditions Rollout(t : task, s : state, h : history, d : depth, if d ≥ H or t terminates at h then return h0↪ 0↪ h↪ si elsea GetPrimitive(⇧rollout↪ t↪ h) hs0 ↪ r0 i Simulate(s↪ a) x '(s0 ) hr00 ↪ n↪ h00 ↪ s00 i Rollout(t↪ s0 ↪ hax↪ d + 1↪ '↪ ⇧rollout) r r0 +γr00 return hr↪ n + 1↪ h00 ↪ s00 i GetGreedyPrimitive(t : task, h : history) if t is primitive then return t elsea⇤ argmaxa Q[t↪ h↪ a] return GetGreedyPrimitive(a⇤ ↪ h) GetPrimitive(⇧ : policy, t : task, h : history) if t is primitive then return t else return GetPrimitive(⇧↪ ⇡t(h)↪ h)

' : abstraction function, ⇧rollout : rollout policy) repeat s ⇠ P(h) Search(root task↪ s↪ h↪ 0↪ T ↪ '↪ ⇧rollout) until resource budgets reached return GetGreedyPrimitive(root task↪ h) Search(t : task, s : state, h : history, d : depth, T : search tree, ' : abstraction function, ⇧rollout : rollout policy) if t is primitive then hs0 ↪ ri ⇠ Simulate(s↪ t) x '(s0 ) return hr↪ 1↪ htx↪ s0 i else if d ≥ H or t terminates at h then return h0↪ 0↪ h↪ si else if node ht↪ hi is not in tree T then Insert node ht↪ hi to T return Rollout(t↪ s↪ h↪ d↪ '↪ ⇧rollout) elsea⇤ argmaxa nQ[t↪ h↪ a] + cq logN[t↪h] N[t↪h↪a] o hr0 ↪ n0 ↪ h0 ↪ s0 i Search(a⇤ ↪ s↪ h↪ d↪ T ↪ '↪ ⇧rollout) hr00 ↪ n00 ↪ h00 ↪ s00 i Search(t↪ s0 ↪ h0 ↪ d + n0 ↪ T ↪ '↪ ⇧rollout) N[t↪ h] N[t↪ h] +1 N[t↪ h↪ a⇤ ] N[t↪ h↪ a⇤ ] +1 r r0 +γ n0 r00 Q[t↪ h↪ a⇤ ] Q[t↪ h↪ a⇤ ] + r-Q[t↪h↪a⇤ ] N[t↪h↪a⇤ ] return hr↪ n0 + n00 ↪ h00 ↪ s00 i

icy ⇧ yields higher expected value than the hierarchical execution of the same hierarchical policy [Sutton et al., 1999; Dietterich, 1999a]. In this paper, we develop a hierarchical MCTS algorithm with state and action abstractions according to the value function decomposition as in the hierarchical control mode, but run the algorithm empirically as in the polling control mode.

In the hierarchical control mode, let V θ (h) be the value of following θ starting from history h, and let Qθ (h↪ o) be the value of executing option o at history h and following θ thereafter. Let ♣h♣ be the number of action-observation pairs of history h. It turns out that V θ (h) = Qθ (h↪ θ(h)), and

where Pr(h0 ♣h↪ o) - the termination distribution of option o - gives the probability that o terminates at history h0 after ♣h0 ♣ - ♣h♣ timesteps. Here, V ⇡o (h) gives the value of follow-

ing option o starting from history h, which can be further expressed as V ⇡o (h) = Q⇡o (h↪ ⇡o(h)), where Q⇡o (h↪ a) gives the value of executing the primitive action a at history h and following o thereafter, i.e.

Combining policy evaluation with policy improvement, an optimal hierarchical policy ⇧⇤ = ¶θ⇤ ↪ ⇡⇤ o1 ↪ ⇡⇤ o2 ↪ · · · ♦ can be computed in principle by iteratively applying V θ⇤ (h) = maxo Qθ⇤ (h↪ o) and V ⇡⇤ o (h) = maxa Q⇡⇤ o (h↪ a). The problem here is that the termination distributions are unknown for the agent, because complete options with local policies are not assumed to be provided in advance, and estimating the termination distribution of an option implies that the local policy of the option is known. Instead, the agent has to find near-optimal policies for the root task and its subtasks simultaneously. We alleviate this problem by conducting a series of nested MCTS (namely POMCP) processes over the hierarchy. A high-level search tree for the root task is built by running MCTS with options as the macro actions. Each option builds its own sub-search tree via a nested MCTS process. In the search step, when simulating an option, its own sub-search tree is used to evaluate its Q-value. The leaf nodes of a sub-search tree serve as the next nodes of the high-level search tree. The simulation inside the sub-search tree is directed by its own tree and rollout policies, which guide the simulation in accomplishing the subtask corresponding to this option. It is also possible to design option-specific informative (rather than purely random) rollout policies for particular options, which is usually easier than designing an informative rollout policy for the ground MDP. In the back-propagation step, Q-values are updated according to Equations 6 and 7. This learning-by-simulation process ensures that the local policies of options as well as their termination distributions converge simultaneously. Given converged low-level policies and their termination distributions, the high-level policy converges in the limit as well. The resulting algorithm is denoted by POMCP(M↪ '↪ O) indicating that it is a hierarchical MCTS algorithm running in POMDP(M↪ ') resulting from doing state and action abstractions on the ground MDP M with ' as the state abstraction function and O as the set of abstract actions.

3.3 The Main Algorithm

The main algorithm POMCP(M↪ '↪O) is outlined in Figure 2. In the algorithm, the root task, its subtasks (modeled as options) and primitive actions are considered uniformly as tasks. For example, a task as a parameter of the Search function could be either the root task, or one of the options, or one of the primitive actions. The algorithm builds a search tree for each task, up to the maximal planning horizon H, in the space of histories consistent with the hierarchy defined by the input abstraction function '. The belief state corresponding to a history h is represented as a set of particles, denoted by P(h), which are updated using a particle filter. In the implementation, we do not need to explicitly maintain h as a full sequence of actions and observations. Instead, we use a hash value of h as an index, and update it incrementally, i.e. hash(haz) = hash combine(hash(h)↪ a↪ z).

We now describe the subroutines in more detail. The GetPrimitive function returns a primitive action at history node h for task t suggested by a hierarchical policy ⇧. It recursively finds the right action suggested by the current task t according to ⇡t 2 ⇧ until it reaches a primitive action. In particular, the GetGreedyPrimitive function returns the greedy action at history h for task t suggested by the hierarchical policy represented by the current search tree and action values. The Rollout function uses a hierarchical rollout policy ⇧rollout to run a sequence of Monte Carlo simulations in a polling control mode according to the generative model of the ground MDP which is encoded in the function Simulate It returns a tuple hr↪ n↪ h↪ si where r is the sum of sampled rewards, n is the total number of steps, h is the resulting history and s is the final state which follows the belief state corresponding to h.

The Search function builds a search tree for each task in the space of histories constrained by the hierarchy. For a primitive action, it simply runs a one-step simulation and returns the result encoded in a tuple. For a non-primitive action t which could either be the root task or one of its subtasks, it returns the result returned by a Rollout subroutine if the node ht↪ hi is not already in the tree, otherwise it 1) selects a greedy (macro) action a⇤ for task t according to the UCB action-selection heuristic, 2) invokes a nested search process for the selected (macro) action a⇤ with the same state s, history h and depth d as the input parameters, 3) recursively explores the current search tree starting from the history h0 and state s0 returned by the search of a⇤ , and 4) updates estimated Q-values according to Equation 6 for the root task or Equation 7 for an option. More precisely, Q[root task↪ h↪ a] ⇡ Qθ (h↪ a), where θ is the highlevel policy represented by the high-level search tree, and a is an option executable at history h; and Q[t↪ h↪ a] ⇡ Q⇡t (h↪ a), where t is an option, ⇡t is the local policy represented by the nested search tree of t, and a is a primitive action The OnlinePlanning function runs in an anytime fashion. At each iteration, it samples a state s from the belief state represented as a set of particles corresponding to h, and invokes a hierarchical search process for the root task from history h and sampled state s by calling Search. It finally returns a greedy primitive action according to the current search tree and action values. The Agent function is the overall procedure interacting with the environment in a polling control mode. It calls OnlinePlanning to select a primitive action, executes it, observes the resulting abstract state, and updates particles repeatedly. It is worth noting that in practice the algorithm can also take advantage of the fact that at the root node of the search tree the agent actually has access to the true ground state, in which case the set of particles at the root node contains only one single state. This does not change the fact that the algorithm is searching in the space of belief states due to the way the tree is expanded and the value functions are updated.

4 Theoretical Results

4.1 Optimality Results with State Abstraction

Inspired by the abstraction criteria introduced in [Hostetler et al., 2014], we define aggregation error as follows

Definition 1. The aggregation error of state abstraction hX↪ 'i for a ground MDP M = hS↪A↪ T↪R↪ γi is e, if 9˚a 2 A, such that for all x 2 X, '(s) = x and d 2 [0↪H], ♣Vd(s) -Qd(s↪˚a)♣  e, where Vd and Qd are the optimal value and action-value functions at depth d in the search tree of M, and H is the maximal planning horizon.

A bounded aggregation error requires that the action-value of˚a is close to the optimal value for all ground states within the same abstract state x. Particularly, e = 0 implies that all ground states within the same abstract state share the same optimal action. Computing exactly the aggregation error implies solving the entire ground MDP completely which is usually infeasible, but this doesn't change the fact that such aggregation error exists and measures the approximation error introduced by grouping states that have different optimal actions when doing state abstraction.

Theorem 1. For state abstraction hX↪ 'i for a ground MDP M = hS↪A↪ T↪R↪ γi with aggregation error e, let s0 be the current state in the ground MDP M and let h0 with P(h0) = ¶s0♦ be the corresponding history in POMDP(M↪ '). Let Q⇤ (s↪ ·) and Q⇤ (h↪ ·) be the optimal action values of M and POMDP(M↪ ') respectively. Let a⇤ = argmaxa2AQ⇤ (h0↪ a) be the optimal primitive action found in POMDP(M↪ ') at history h0, and define an actionvalue error as E(a⇤ ) = ♣maxa2AQ⇤ (s0↪ a) -Q⇤ (s0↪ a⇤ )♣. Suppose the maximal planning horizon is H, then E(a⇤ ) is bounded by E(a⇤ )  2He if γ = 1, else E(a⇤ )  2γ 1-γH 1-γ e.

Proof. Consider the search trees of M and POMDP(M↪ '). We define a specific action-value error for history h and action a at depth d in the search tree of POMDP(M↪ ') to be:

where Qd(s↪ ·) and Qd(h↪ ·) are optimal action values at depth d in the search trees of M and POMDP(M↪ ') respectively. By applying Bellman equations, we have

it follows that

Therefore,

for all h 2 H and a 2 A. Let E(d) = maxh2H↪a2A Ed(h↪ a). We get E(d)  γ[E(d + 1) + e]. At terminal nodes, both QH(h↪ ·) and QH(s↪ ·) equal 0, so E(H) = 0. Therefore, E(d)  (H - d)e if γ = 1, otherwise E(d)  γ 1-γH-d 1-γ e. At the root node, let a⇤ = argmaxa Q0(h0↪ a), and b⇤ = argmaxa2AQ0(s0↪ a⇤ ). If a⇤ = b⇤ , E(a⇤ ) = 0; otherwise, we must have Q0(h0↪ a⇤ ) ≥ Q0(h0↪ b⇤ ). Noticing that P(h0) = ¶s0♦, since ♣Q0(s0↪ b⇤ ) - Q0(h0↪ b⇤ )♣  E(0) and ♣Q0(s0↪ a⇤ ) - Q0(h0↪ a⇤ )♣  E(0), we get E(a⇤ ) = ♣Q0(s0↪ b⇤ ) - Q0(s0↪ a⇤ )♣  2E(0).

4.2 Convergence Results with Action Abstraction

Theorem 2. With probability 1, POMCP(M↪ '↪O) converges to a recursively optimal hierarchical policy for POMDP(M↪ ') over the hierarchy defined by the input state and action abstractions.

Proof. (Sketch) For a particular option, POMCP(M↪ '↪O) finds the optimal policy with probability 1 following the convergence results of POMCP in the limit. Given the fact that, when an option converges, its termination distribution also converges, the root task reduces to a stationary semiMarkov Decision Process (SMDP) defined over the belief space. POMCP(M↪ '↪O) thus finds the optimal policy in the limit for the root task within the converged SMDP by extending the convergence results of POMCP to SMDPs. Since the high-level policy is optimal given optimal low-level policies, POMCP(M↪ '↪O) converges to a recursively optimal hierarchical policy.

5 Experiments

5.1 Rooms Domain

The ROOMS[m↪ n↪ k] problem simulates a robot navigating in a m ⇥ n grid map containing k rooms, as depicted in Figure 1b. The 8 primitive actions are E, SE, S, SW, W, NW, N and NE. Each action has a probability 0.2 of mistake, in which case a random action is executed instead. If any movement is going to collide with the wall, the agent stays at its current position. Each primitive action has a reward of -1. Moving into the goal has a reward of 10. In the ground MDP, the stochastic branching factor for an action is up to 8. With state abstraction by assuming a room as an abstract state, the stochastic branching factor for an action reduces to 2. An option is defined as a transition from a room to one of its neighbors. The discount factor is γ = 0▷98. The maximal planning horizon is determined as H = blogγ ✏c = 341, where ✏ is set to be 0.001. Figures 3a, 3e, 3b and 3f with x axis in log scale show the results of running UCT, UCT', POMCP(M↪ '), POMCP(M↪ '↪O) and smart-POMCP(M↪ '↪O) in ROOMS[17↪ 17↪ 4] and ROOMS[25↪ 13↪ 8] problems, where UCT runs directly in the ground state space, UCT' is a UCT algorithm running entirely in the abstract state space, POMCP(M↪ ') is a POMCP algorithm running on POMDP(M↪ ') resulting from doing state abstraction on the ground MDP M, POMCP(M↪ '↪ O) is the proposed hierarchical MCTS algorithm running on POMDP(M↪ '), and smart-POMCP(M↪ '↪O) is a POMCP(M↪ '↪O) algorithm equipped with hand-coded informative rollout policies for options. UCT, UCT', POMCP(M↪ ') and POMCP(M↪ '↪ O) are all developed with purely random rollout policies. The performance is evaluated using averaged discounted return in terms of the number of simulations and the averaged computation time per action. Each data point is averaged over 100 runs (or up to 2 hours of total computation time) in terms of the number of simulations and the averaged computation time per action. It can be seen from the results that POMCP(M↪ ') outperforms UCT or has at least the same performance, indicating that modeling a ground MDP with state abstraction as a POMDP and solving the POMDP via approximated, search-base online planning algorithms is feasible. UCT' uses the empirical distributions of Pr(s♣x) to approximate w(s↪ x) and finds a memoryless policy as a mapping from abstract states to actions following the weighting function approach. It has easily the worst performance in all cases, confirming that finding memoryless policies might not be the right way to do state abstractions since too much information on the abstract level is ignored. The main algorithm - POMCP(M↪ '↪ O) - outperforms UCT by orders of magnitude. POMCP(M↪ '↪O) also outperforms POMCP(M↪ ') substantially suggesting that exploiting the hierarchical structure introduced by doing state abstraction contributes the main improvement. With the help of an option-specific rollout policy which is designed to near-optimally move to the intersection area of two connected rooms, smart-POMCP(M↪ '↪O) improves on POMCP(M↪ '↪O) significantly. The possibility of introducing option-specific rollout policies can also be considered as an advantage of POMCP(M↪ '↪ O).

5.2 Continuous Rooms Domain

We further extend ROOMS[m↪ n↪ k] into a continuous state space and propose a C-ROOMS[m↪ n↪ k] problem, where each cell has a size of 1 (m2 ). The position of the agent is represented using continuous (x↪ y) coordinates. A primitive action moves the agent by a distance of 1 (m) in expectation, augmented with a Gaussian error. The agent finishes this task if the distance to the goal is within 0.5 (m). UCT in such continuous domains reduces to a depth-1 search which can be seen as a single step of policy improvement over the rollout policy. To run POMCP(M↪ ') and POMCP(M↪ '↪ O) algorithms in this domain, we need only provide the appropriate observation function defined over the continuous state space. Figures 3c, 3g, 3d and 3h show the results of running UCT, UCT', POMCP(M↪ '), POMCP(M↪ '↪O) and smart-POMCP(M↪ '↪ O) in C-ROOMS[17↪ 17↪ 4] and CROOMS[25↪ 13↪ 8] problems, confirming that POMCP(M↪ ') and POMCP(M↪ '↪O) algorithms have the ability to run in continuous domains without significant modifications. Similar trends can be seen in the results. It is also interesting to see that although UCT has reduced to a depth-1 search in this continuous domain, it still has rather good performance. This might be because the value function of a random policy in this domain provides a good heuristic, thus a greedy policy over this heuristic can work well.

6 RelatedWork

Hostetler et al. (2014) analyzed state aggregation in MDPs following the weighting function approach. They established a performance loss bound in terms of a state abstraction error and a weighting function error. Our method has removed the weighting function error since the POMDP formulation guarantees that the optimal weighting function will always be used in the algorithm. Vien and Toussaint (2014) developed a similar hierarchical MCTS framework for MDPs and POMDPs according to the theory of MAXQ value function decomposition. The original MAXQ decomposition is not completely applicable to exploit the hierarchical structure defined by abstract states. A MAXQ subtask is designed to be specified with a termination predicate which partitions the (belief) state space into a set of active (belief) states and a set of terminal (belief) states [Dietterich, 1999a]. Using MAXQ subtasks to model temporal transitions between abstract states as abstract actions results inevitability in a set of overlapping subtasks, in which case we have also to introduce a pseudoreward function for each subtask. Taking the rooms domain as an example, let x ! y be the subtask of moving from room x to room y. If we treat histories ending with x as the set of active belief states, then histories not ending with x have to be the respective terminal belief states, in which case supposedly different abstract actions A ! B and A ! C actually have the same termination condition, which leads them to have the same learned policy. One way to avoid this problem is to introduce a pseudo-reward function within each subtask to encourage the subtask to move to the abstract goal state by additionally collecting a pseudo-reward, e.g. r(h) = 1 if end(h) = y, otherwise r(h) = 0. On the other hand, if we treat histories ending with y as the set of terminal belief states, then histories not ending with y have to be the respective active belief states, in which case abstract actions A ! B and D ! B have the same active belief states such that they are executable in the same set of belief states, which is not desirable either. The options theory used in this paper does not have this overlapping-subtask problem thanks to the concepts of termination condition and initiation set, which can be seen as an extension of the MAXQ termination predicate. Bai et al. (2012; 2015) also developed a hierarchical online planning algorithm for MDPs (namely MAXQ-OP) based on MAXQ value function decomposition. Their method needs to estimate the termination distribution for each subtask in order to evaluate the completion function recursively in a dynamic programming way. In this paper, the high-level and low-level policies are learned simultaneously via a hierarchical MCTS approach, without the need to estimate the termination distributions in advance.

7 Conclusion

In this paper, we propose state- and action-abstracted MDPs can be viewed as POMDPs. We bound the performance loss induced by the abstraction and we describe a hierarchical MCTS algorithm for approximately solving the abstract POMDP. The algorithm converges to a recursively optimal hierarchical policy for the ground MDP consistent with the input state and action abstractions. Empirical results show that the proposed approach improves ground MCTS by orders of magnitude. In future work, we plan to extend this approach to reinforcement learning algorithms with features (such as those introduced by various state-space function approximators). The non-Markovianess introduced by features can be overcome by using a POMDP formulation; the hierarchical structure in the feature space can be exploited by using a similar hierarchical MCTS approach as in this paper.

Acknowledgments

Funding for this research was provided by ONR under contract N00014-12-1-0609, by DARPA under contract N6600115-2-4048, and by the United Technologies Research Center. Opinions, findings, and conclusion or recommendations expressed in this material are those of the authors and do not necessarily reflect the view of the funding agencies. The authors would also like to thank Richard Doan and the anonymous reviewers for their valuable comments and suggestions.