Point-based value iteration: An anytime algorithm for POMDPs

1 Introduction

The value iteration algorithm for planning in partially ob­ servable Markov decision processes (POMDPs) was intro­ duced in the 1970s [Sondik, 1971]. Since its introduction numerous authors have refined it [Cassandra et al., 1997; Kaelbling et at., 1998; Zhang and Zhang, 2001] so that it can solve harder problems. But, as the situation currently stands, POMDP value iteration algorithms are widely believed not to be able to scale to real-world-sized problems.

There are two distinct but interdependent reasons for the limited scalability of POMDP value iteration algorithms. The more widely-known reason is the so-called curse of dimen­ ~ionality [Kaelbling et al., 1998]: in a problem with n phys­ Ical states, POMDP planners must reason about belief states in an (n - I)-dimensional continuous space. So, naive ap­ proaches like discretizing the belief space scale exponentially with the number of states.

The less-well-known reason for poor scaling behavior is what we will call the curse of history: POMDP value iter­ ation is in many ways like breadth-first search in the space of belief states. Starting from the empty history, it grows a set of histories (each corresponding to a reachable belief) by simulating the POMDP. So, the number of distinct action­ observation histories considered grows exponentially with the planning horizon. Various clever pruning strategies [Littman et ~l., 1995; Cassandra et at., 1997] have been proposed to whittle down the set of histories considered, but the pruning steps are usually expensive and seem to make a difference only in the constant factors rather than the order of growth.

The two curses, history and dimensionality, are related: the higher the dimension of a belief space, the more room it has states, A is a set of discrete actions, and 0 is a set of dis­ crete observations providing incomplete and/or noisy state in­ formation. The POMDP model is parameterized by: bo(s), the initial belief distribution; T(s, a, s') := Pr(st+l = s I at = a, St = s ), the distribution describing the probability of transitioning from state s to state s' when taking action a; n(o, s, a) := Pr(Ot+1 = 0 I at = a, St+1 = s), the dis­ tribution describing the probability of observing o from state s after taking action a; R( s, a), the reward signal received when executing action a in states; and"(, the discount factor.

A key assumption of POMDPs is that the state is only p~­ tially observable. Therefore we rely on the concept of a beltef state, denoted b, to represent a probability distribution over states. The belief is a sufficient statistic for a given history:

and is updated at each time-step to incorporate the latest ac­ tion, observation pair:

where TJ is the normalizing constant.

The goal of POMDP planning is to find a sequence of ac­ tions { a0 , ... , at} maximizing the expected sum of rewards E[2:t "'t R(st, at)]. Given that the state is not necessarily fully observable, the goal is to maximize expected reward for each belief. The value function can be formulated as:

When optimized exactly, this value function is always piece­ wise linear and convex in the belief [Sondik, 1971] (see Fig. 1, left side). After n consecutive iterations, the solution consists of a set of a-vectors: Vn = {no, a1, ... , am}. Each a-vector represents an lSI-dimensional hyper-plane, and de­ fines the value function over a bounded region of the be­ lief: Vn(b) = maxaEVn I:sES a(s)b(s). In addition, each a-vector is associated with an action, defining the best imme­ diate policy assuming optimal behavior for the following ( n1) steps (as defined respectively by the sets {Vn-1, ... , Vo} ).

The n-th horizon value function can be built from the pre­ vious solution Vn_1 using the Backup operator, H. We use notation V = HV' to denote an exact value backup:

A number of algorithms have been proposed to implement this backup by directly manipulating a-vectors, using a com­ bination of set projection and pruning operations [Sondik, 1971; Cassandra et al., 1997; Zhang and Zhang, 2001]. We now describe the most straight-forward version of exact POMDP value iteration.

To implement the exact update V = HV', we first generate intermediate sets ra,* and ra,o, Va E A, Vo E 0 (Step 1 ):

Next we create ra (\Ia E A), the cross-sum over observa­ tions, which includes one aa,o from each ra,o (Step 2):

Finally we take the union of ra sets (Step 3 ):

In practice, many of the vectors in the final set V may be completely dominated by another vector (ai · b < Ctj · b, Vb), or by a combination of other vectors. Those vectors can be pruned away without affecting the solution. Finding dom- · inated vectors can be expensive (checking whether a single vector is dominated requires solving a linear program), but is usually worthwhile to avoid an explosion of the solution size.

To better understand the complexity of the exact update, let IV' I be the number of a-vectors in the previous solution set. Step 1 creates IAIIOI JV'I projections and Step 2 generates IAIIV'Ii 0 1 cross-sums. So, in the worst case, the new solu­ tion JVI has size IAI JV'Ii 0 1 (time ISI 2 IAI JV'Ii 0 1). Given that this exponential growth occurs for every iteration, the impor­ tance of pruning away unnecessary vectors is clear. It also highlights the impetus for approximate solutions.

3 Point-based value iteration

It is a well understood fact that most POMDP problems, even given arbitrary action and observation sequences of infinite length, are unlikely to reach most of the points in the belief simplex. Thus it seems unnecessary to plan equally for all beliefs, as exact algorithms do, and preferable to concentrate planning on most probable beliefs.

The point-based value iteration (PBVI) algorithm solves a POMDP for a finite set of belief points B = { bo, b1, ... , bq}. It initializes a separate a-vector for each selected point, and repeatedly updates (via value backups) the value of that a­ vector. As shown in Figure 1, by maintaining a full a-vector for each belief point, PBVI preserves the piece-wise linear­ ity and convexity of the value function, and defines a value function over the entire belief simplex. This is in contrast to grid-based approaches [Lovejoy, 1991; Brafman, 1997; Hauskrecht, 2000; Zhou and Hansen, 2001; Bonet, 2002], which update only the value at each belief grid point.

The complete PBVI algorithm is designed as an anytime algorithm, interleaving steps of value iteration and steps of belief set expansion. It starts with an initial set of belief points for which it applies a first series of backup operations. It then grows the set of belief points, and finds a new solution for the expanded set. By interleaving value backup iterations with expansions of the belief set, PBVI offers a range of solutions, gradually trading off computation time and solution quality. We now describe how we can efficiently perform point-based value backups and how we select belief points.

3.1 Point-based value backup

To plan for a finite set of belief points B, we modify the backup operator (Eqn 4) such that only one a-vector per belief point is maintained. For a point-based update V = HV', we start by creating projections (exactly as in Eqn 5) \fa E A , Vo E 0 (Step 1):

Next, the cross-sum operation (Eqn 6) is much simplified by the fact that we are now operating over a finite set of points. We construct Vb E B, \fa E A (Step 2):

Finally, we find the best action for each belief point (Step 3 ):

When performing point-based updates, the backup creates IAIIOIIV'I projections as in exact VI. However the final so­ lution V is limited to containing only IBI components (in time ISIIAIIV'IIOIIBI). Thus a full point-based value up­ date takes only polynomial time, and even more crucial, the size of the solution set V remains constant. As a result, the pruning of a vectors (and solving of linear programs), so cru­ cial in exact POMDP algorithms, is now unnecessary. The only pruning step is to refrain from adding to V any vector already included, which arises when two nearby belief points support the same vector (e.g. b1 , b2 in Fig. 1).

In problems with a finite horizon h, we run h value backups before expanding the set of belief points. In infinite-horizon problems, we select the horizon so that (Rmax- Rminhh < E.

3.2 Belief point set expansion

As explained above, PBVI focuses its planning on relevant beliefs. More specifically, our error bound below suggests that PBVI performs best when its belief set is uniformly dense in the set of reachable beliefs. So, we initialize the set B to contain the initial belief b0 and expand B by greedily choos­ ing new reachable beliefs that improve the worst-case density as rapidly as possible.

For a given b E B, PBVI stochastically simulates a single­ step forward trajectory using each action to produce new be­ liefs { ba 0 , ba 1 , ··· } · 1 It then measures the £ 1 distance from ba, to B, and throws away ba, if ba, E B. Finally, it keeps only the new belief ba, which is farthest away from any point al­ ready in B. 2 PB VI tries to generate one new belief from each previous belief; so, B at most doubles in size on each ex­ pansion.3 Since expansion phases are interleaved with value iteration, PBVI offers an anytime solution.

1 To simulate an action a, first sample a states from the distribu­ tion b. Then sample an observation according to n(s, a, o) for the given s and a. Finally compute ba using a Bayesian update (Eqn 2).

3.3 Convergence and error bounds

For any belief set B and horizon n, PBVI produces an esti­ mate V ,fl. The error between V ,fl and the true value function v; is bounded. The bound depends on how densely B sam­ ples the belief simplex ~; with denser sampling, V,f con­ verges to v;, the true value function. 4 As n -+ oo, V ,fl does not necessarily converge; but, our error bound still holds. Cutting off the PBVI iteration at any sufficiently large hori­ zon, we know that the difference between V ,fl and the op­ timal infinite-horizon V* is not too large. (The overall er­ ror is bounded by IIV,fl- vr:lloo + IIVr:- V*ll oo· The first term is bounded by our theorem below; the second is bounded by f'n IIV 0 * - V*lj.) The remainder of this section states and proves our error bound.

Define the density EB of a set of belief points B to be the maximum distance from any legal belief to B . More pre­ cisely, EB = maxb'EA minbEB llb-b'III· Then, we can prove:

Lemma 1 The error introduced by PBVI's pruning step is at most '11 _ (Rmax-Rmin)<s ·tprune - 1-1'

Proof: Let b' E ~ be the point where PBVI makes its worst pruning error, and b E B be the closest (1-norm) sampled belief to b'. Let a be the vector which is maximal at b, and a' be maximal at b'. By erroneously pruning a', PBVI makes an error of at most a' · b' - a · b'. On the other hand, since a is maximal at b, then a' · b ~ a · b. So,

The last inequality holds because each a-vector represents the reward achievable starting from some state and following some sequence of actions and observations.

Theorem 1 For any belief set Band any horizon n, the error of the PBVJ algorithm rJn = IIVnB - v; lloo is bounded by

2 The actual choice of norm doesn't appear to matter in practice; some of our experiments below used Euclidean distance (instead of £1) and the results appear identical.

3 We experimented with other strategies such as adding a fixed number of new beliefs, but since value iteration is much more ex­ pensive than belief computation the above algorithm worked best. If desired, we can impose a maximum size on B based on time con­ straints or performance requirements.

4 If not all beliefs are reachable, we don't need to sample all of/::,.. densely, but replace /::,.. by the set of reachable beliefs li below. The error bounds and convergence results hold on li.

Proof:

4 Experimental results

The domain of Tag is based on the popular game of lasertag. The goal is to search for and tag a moving opponent [Rosen­ crantz et a/., 2003]. Figure 2a shows the live robot as it moves in to capture an opponent. In our POMDP formula­ tion, the opponent moves stochastically according to a fixed policy. The spatial configuration of the domain used for plan­ ning is illustrated in Figure 2b. This domain is an order of magnitude larger (870 states) than most other POMDP prob­ lems considered thus far in the literature [Cassandra, 1999], and is proposed as a new challenge for fast, scalable, POMDP algorithms. A single iteration of optimal value iteration on a problem of this size could produce over 10 20 a-vectors before pruning.

The state space is described by the cross-product of two features, Robot = {so, ... , s29} and Opponent = {so, ... , s29, Stagged}. Both agents start in independently­ selected random positions, and the game finishes when Opponent= Stagged· The robot can select from five actions: {North, South, East, West, Tag}. A reward of -1 is imposed for each motion action; the Tag action results in a +10 re­ ward if Robot = Opponent, or -10 otherwise. Throughout the game, the Robot's position is fully observable, and the ef­ fect of a Move action has the predictable deterministic effect, e.g.:

The position of the opponent is completely unobservable un­ less both agents are in the same cell. At each step, the op­ ponent (with omniscient knowledge) moves away from the robot with Pr = 0.8 and stays in place with Pr = 0.2, e.g.:

Figure 3 shows the performance of PBVI on the Tag do­ main. Results are averaged over 10 runs of the algorithm, times 100 different (randomly chosen) start positions for each run. It shows the gradual improvement in performance as samples are added (each shown data point represents a new expansion of the belief set with value backups). In addition to PBVI, we also apply the QMDP approximation as a baseline comparison [Littman eta/., 1995]. The QMDP approxima­ tion is calculated by solving a POMDP as though it were fully observable: Q(s, a) = R(s, a) + 1 Ls'ES T(s, a, s')V(s'), and linearizing across Q-values to obtain the value at a be­ lief: V(b) = maxaEA LsES b(s)Q(s, a). This approxima­ tion is quick to compute, and is remarkably effective in some domains. In the Tag domain, however, it lacks the represen­ tational power to compute a good policy.

5 Additional experiments

5.1 Comparison on well-known problems

To further analyze the performance of PBVI, we applied it to three well-known problems from the POMDP literature. We selected Maze33, Hallway and Hallway2 because they are commonly used to test scalable POMDP algorithms [Littman et a/., 1995; Brafman, 1997; Poon, 200 1]. Figure 3 presents results for each domain. Replicating earlier experiments, re­ sults for Maze33 are averaged over 151 runs (reset after goal, terminate after 500 steps); results for Hallway and Hallway2 are averaged over 251 runs (terminate at goal, max 251 steps). In all cases, PBVI is able to find a good policy. Table I compares PBVI's performance with previously published re­ sults, comparing goal completion rates, sum of rewards, pol­ icy computation time, and number of required belief points. In all domains, PBVI achieves competitive performance, but with fewer samples.

5.2 Validation of the belief set expansion

To further investigate the validity of our approach for gen­ erating new belief states (Section 3.2), we compared our approach with three other techniques which might appear promising. In all cases, we assume that the initial belief b0 (given as part of the model) is the sole point in the initial set, and consider four expansion methods:

1. Random (RA)
2. Stochastic Simulation with Random Action (SSRA)
3. Stochastic Simulation with Greedy Action (SSGA)
4. Stochastic Simulation with Explorative Action (SSEA)

The RA method consists of sampling a belief point from a uniform distribution over the entire belief simplex. SSEA is the standard PBVI expansion heuristic (Section 3.2). SSRA similarly uses single-step forward simulation, but rather than try all actions, it randomly selects one and automatically ac­ cepts the posterior belief unless it was already in B . Finally, SSGA uses the most recent value function solution to pick the greedy action at the given belief b, and performs a single-step simulation to get a new belief b' --+ B.

We revisited the Hallway, Hallway2, and Tag problems from sections 4 and 5.1 to compare the performance of these n.a.=not applicable n. v.=not available four heuristics. For each problem we apply PBVI using each of the belief-point selection heuristics, and include the QMDP approximation as a baseline comparison. Figure 4 shows the computation time versus the reward performance for each do­ main.

Table 1: Results for POMDP domains. Those marked[*) were com­ puted by us; other results were likely computed on different plat­ forms, and therefore time comparisons may be approximate at best. All results assume a standard (not lookahead) controller.

The key result from Figure 4 is the rightmost panel, which shows performance on the largest, most complicated domain. In this domain our SSEA rule clearly performs best. In smaller domains (left two panels) the choice of heuristic mat­ ters less: all heuristics except random exploration (RA) per­ form equivalently well.

6 Related work

Significant work has been done in recent years to improve the tractability of POMDP solutions. A number of increas­ ingly efficient exact value iteration algorithms have been proposed [Cassandra et al., 1997; Kaelbling et al. , 1998; Zhang and Zhang, 2001]. They are successful in finding op­ timal solutions, however are generally limited to very small problems (a dozen states) since they plan optimally for all beliefs. PBVI avoids the exponential growth in plan size by restricting value updates to a finite set of (reachable) beliefs.

There are several approximate value iteration algorithms which are related to PBVI. For example, there are many grid­ based methods which iteratively update the values of discrete belief points. These methods differ in how they partition the belief space into a grid [Brafman, 1997; Zhou and Hansen, 2001].

More similar to PBVI are those approaches which update both the value and gradient at each grid point [Lovejoy, 1991; Hauskrecht, 2000; Poon, 2001]. While the actual point-based update is essentially the same between all of these, the over­ all algorithms differ in a few important aspects. Whereas Poon only accepts updates that increase the value at a grid point (requiring special initialization of the value function), and Hauskrecht always keeps earlier a-vectors (causing the set to grow too quickly), PBVI requires no such assumptions. A more important benefit of PBVI is the theoretical guaran­ tees it provides: our guarantees are more widely applicable and provide stronger error bounds than those for other point­ based updates.

In addition, PBVI is significantly smarter than previous algorithms about how it selects belief points. PBVI selects only reachable beliefs; other algorithms use random beliefs, or (like Poon's and Lovejoy's) require the inclusion of a large number of fixed beliefs such as the corners of the probabil­ ity simplex. Moreover, PBVI selects belief points which im­ prove its error bounds as quickly as possible. In practice, our experiments on the large domain of lasertag demonstrate that PBVI's belief-selection rule handily outperforms several al­ ternate methods. (Both Hauskrecht and Poon did consider using stochastic simulation to generate new points, but nei­ ther found simulation to be superior to random point place­ ments. We attribute this result to the smaller size of their test domains. We believe that as more POMDP research moves to larger planning domains, newer and smarter belief selection rules will become more and more important.)

Gradient-based policy search methods have also been used to optimize POMDP solutions [Baxter and Bartlett, 2000; Kearns et al., 1999; Ng and Jordan, 2000], successfully solv­ ing multi-dimensional, continuous-state problems. In our view, one of the strengths of these methods lies in the fact that they restrict optimization to reachable beliefs (as does PBVI). Unfortunately, policy search techniques can be ham­ pered by low-gradient plateaus and poor local minima, and typically require the selection of a restricted policy class.

7 Conclusion

This paper presents PBVI, a scalable anytime algorithm for approximately solving POMDPs. We applied PBVI to a robotic version of lasertag, where it successfully developed a policy for capturing a moving opponent. Other POMDP solvers had trouble computing useful policies for this domain. PBVI also compared favorably with other solvers on three well-known smaller test problems. We attribute PBVI's suc­ cess to two features, both of which directly target the curse of history. First, by using a trajectory-based approach to se­ lect belief points, PBVI focuses planning on reachable be­ liefs. Second, because it uses a fixed set of belief points, it can perform fast value backups.

In experiments, PBVI beats back the curse of history far enough that we can solve POMDPs an order of magnitude larger than most previous algorithms. With this success, we can now identify the next hurdle for POMDP research: con­ trary to our expectation, it turns out to be the old-fashioned MDP problem of having too many distinct physical states. This problem hits us in the cost of updating the point-based value function vectors. (This cost is quadratic in the num­ ber of physical states.) While this problem is not necessar­ ily easy to overcome, we believe that sparse matrix computa­ tions, together with other approaches from the existing liter­ ature [Poupart and Boutilier, 2003; Roy and Gordon, 2003], will allow us to to scale PBVI to problems which are at least another order of magnitude larger. So, PBVI represents a considerable step towards making POMDPs usable for real­ world problems.