Solving POMDPs: RTDP-Bel vs. Point-based Algorithms

1 Introduction

In recent years, a number of point-based algorithms have been proposed for solving large POMDPs [Smith and Simmons, 2005; Spaan and Vlassis, 2005; Pineau et al., 2006; Shani et al., 2007]. These algorithms adopt Sondik's representation of the value function but replace the complex full synchronous updates by faster and more effective updates at selected beliefs. Some of the elements of point-based algorithms are common to RTDP-Bel, an older and simpler approximate algorithm based on RTDP [Barto et al., 1995], that also combines simulation and point-based updates but represents the value function in a straightforward manner by means of a table and a discretization function [Bonet and Geffner, 1998a; 1998b; 2000]. While the two type of algorithms have not been experimentally compared up to now, it is widely believed that Sondik's representation is crucial for speed and quality, and thus, that algorithms such as RTDP-Bel cannot match them. One of the reasons that this comparison has not been done is that RTDP-Bel targets a class of shortest-path POMDPs with positive action costs while point-based algorithms target

H´ector Geffner

Departamento de Tecnolog´ıa ICREA & Universitat Pompeu Fabra 08003 Barcelona, SPAIN

hector.geffner@upf.edu

discounted POMDPs. In this paper, we bridge the representational gap among the different types of POMDPs, showing in particular how to transform discounted POMDPs into equivalent Goal POMDPs, and use this transformation to compare point-based algorithms and RTDP-Bel over the existing discounted benchmarks. The results appear to contradict the conventional wisdom in the area showing that RTDP-Bel is competitive, and indeed, often superior to point-based algorithms. The transformations among POMDPs are also new, and show that Goal POMDPs are actually more expressive than discounted POMDPs, a result that generalizes one for MDPs in [Bertsekas and Tsitsiklis, 1996, pp. 39-40].

The paper is organized as follows. We consider in order Goal MDPs and RTDP (Sect. 2), Goal POMDPs and RTDPBel (Sect. 3), discounted POMDPs and point-based algorithms (Sect. 4), the equivalence-preserving transformations among different types of POMDPs (Sect. 5), the experimental comparison between point-based algorithms and RTDPBel (Sect. 6), and end with a brief discussion (Sect. 7).

2 Goal MDPs and RTDP

Shortest-path MDPs provide a generalization of the state models traditionally used in heuristic search and planning, accommodating stochastic actions and full state observability [Bertsekas, 1995]. They are given by

• SP1. a non-empty state space S,
• SP2. a non-empty set of target states T ⊆ S,
• SP3. a set of actions A, 1
• SP4. probabilities Pa(s′ |s) for a ∈ A, s, s′ ∈ S, and
• SP5. costs c(a, s) for a ∈ A and s ∈ S.

The target states t are assumed to be absorbing and cost-free; meaning Pa(t|t) = 1 and c(a, t) = 0 for all a ∈ A. Goal MDPs are shortest-path MDPs with a known initial state s0 and positive action costs c(a, s) for all a and non-terminal states s. A Goal MDP has a solution, and hence, an optimal solution, if a target (goal) state is reachable from every state. A policy π is optimal if it minimizes the expected cost to the goal V π (s) for all states s. This optimal expected cost,

1 For simplicity, and without loss of generalization, we assume that all actions in A are applicable in all states.

1. Start with s = s0.
2. Evaluate each action a in s as:

initializing V (s′ ) to h(s′ ) when s′ is not in hash

1. Select action a that minimizes Q(a, s).
2. Update V (s) to Q(a, s)
3. Sample next state s′ with probability Pa(s′ |s)
4. Finish if s′ is target, else s := s′ and goto 2

Figure 1: Single Trial of RTDP

denoted as V ∗ (s), is the unique solution of the Bellman equation

for all s ∈ S \ T, and V ∗ (s) = 0 for s ∈ T. The Bellman equation can be solved by the Value Iteration (VI) method, where a value function V , initialized arbitrarily, except V (t) = 0 for targets t, is updated iteratively until convergence using the right-hand side of (1) as:

This method for computing V ∗ is known as parallel value iteration. In asynchronous value iteration, states are updated according to (2) in any order. Asynchronous VI also delivers the optimal value function V ∗ provided that all the states are updated sufficiently often [Bertsekas, 1995]. With V = V ∗ , the greedy policy πV is an optimal policy, where πV is

Recent AI methods for solving MDPs are aimed at making dynamic programming methods more selective by incorporating ideas developed in heuristic search. One of the first such methods is Real-Time Dynamic Programming (RTDP), introduced in [Barto et al., 1995], which is a generalization of the LRTA* algorithm [Korf, 1990] that works for deterministic models only.

RTDP is an asynchronous value iteration algorithm of a special type: it can converge to the optimal value function and policy over the relevant states without having to consider all the states in the problem. For achieving this, and in contrast with standard value iteration algorithms, RTDP uses an admissible heuristic function or lower bound h as the initial value function. Provided with such a lower bound, RTDP selects for update the states that are reachable from the initial state s0 through the greedy policy πV in a way that interleaves simulation and updates. The code for a single trial of RTDP is shown in Fig. 1.

The quality of the heuristic used to initialize the value function is crucial for RTDP and LRTA*. In both cases, better heuristic values mean a more focused search, and a more focused search means more updates on the states that matter, thus allowing the value function to bootstrap more quickly.

For the implementation of RTDP, the estimates V (s) are stored in a hash table that initially contains the heuristic value of the initial state only. Then, when the value of a state s that is not in the table is needed, a new entry for s with value V (s) = h(s) is allocated. These entries are updated following (2) when a move from s is performed.

The simple greedy search combined with updates in both RTDP and LRTA* yields two key properties. First, a single trial of these algorithms eventually terminates in a goal state. Second, successive trials, using the same hash table, eventually deliver an optimal cost function V ∗ , and thus an optimal (partial) policy πV ∗ over the relevant states.These two properties hold for Goal MDPs only, under the assumption that the goal is reachable from any state (with positive probability) and that the initial value function is a lower bound [Barto et al., 1995]. They do not hold in general for arbitrary shortestpath MDPs nor for general discounted cost-based (or rewardbased) MDPs. Indeed, in such cases RTDP may easily enter into a loop, as when some of the action costs are zero.

3 Goal POMDPs and RTDP-Bel

Partially Observable MDPs generalize MDPs by modeling agents that have incomplete state information [Sondik, 1978; Monahan, 1983; Kaelbling et al., 1999] in the form of a prior belief b0 that expresses a probability distribution over S, and a sensor model made up of a set of observation tokens O and probabilities Qa(o|s) of observing o ∈ O upon entering state s after doing a. Formally, a Goal POMDP is a tuple given by:

• PO1. a non-empty state space S,
• PO2. an initial belief state b0,
• PO3. a non-empty set of target (or goal) states T ⊆ S,
• PO4. a set of actions A,
• PO5. probabilities Pa(s′ |s) for a ∈ A, s, s′ ∈ S,
• PO6. positive costs c(a, s) for non-target states s ∈ S,
• PO7. a set of observations O, and
• PO8. probabilities Qa(o|s) for a ∈ A, o ∈ O, s ∈ S.

It is assumed that target states t are cost-free, absorbing, and fully observable; i.e., c(a, t) = 0, Pa(t|t) = 1, and t ∈ O, so that Qa(t|s) is 1 if s = t and 0 otherwise. The target beliefs or goals are the beliefs b such that b(s) = 0 for s ∈ S \ T .

The most common way to solve POMDPs is by formulating them as completely observable MDPs over the belief states of the agent [Astrom, 1965; Sondik, 1978]. Indeed, while the effects of actions on states cannot be predicted, the effects of actions on belief states can. More precisely, the belief ba that results from doing action a in the belief b, and the belief boa that results from observing o after doing a in b, are:

As a result, the partially observable problem of going from an initial state to a goal state is transformed into the completely observable problem of going from one initial belief state into a target belief state. The Bellman equation for the resulting belief MDP is

for non-target beliefs b and V ∗ (bt) = 0 otherwise, where c(a, b) is the expected cost ∑s∈S c(a, s)b(s).

The RTDP-Bel algorithm, depicted in Fig. 2 is a straightforward adaptation of RTDP to Goal POMDPs where states are replaced by belief states updated according to (7). There is just one difference between RTDP-Bel and RTDP: in order to bound the size of the hash table and make the updates more effective, each time that the hash table is accessed for reading or writing the value V (b), the belief b is discretized. The discretization function d is extremely simple and maps each entry b(s) into the entry:

where D is a positive integer (the discretization parameter), and ceil(x) is the least integer ≥ x. For example, if D = 10 and b is the vector (0.22, 0.44, 0.34) over the states s ∈ S, d(b) is the vector (3, 5, 4).

Notice that the discretized belief d(b) is not a belief and does not have to represent one. It just represents the unique cell in the hash table that stores the value function for b and of all other beliefs b′ such that d(b′ ) = d(b). The discretization is used only in the operations for accessing the hash table and it does not affect the beliefs that are generated during a trial. Using a terminology that is common in Reinforcement Learning, the discretization is a simple function approximation device [Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 1998], where a single parameter, the value stored at cell d(b) in the hash table is used to represent the value of all beliefs b′ that discretize into d(b′ ) = d(b). This approximation relies on the assumption that the value of beliefs that are close, should be close as well. Moreover, the discretization preserves supports (the states s with b(s) > 0) and thus never collapses the value of two beliefs if there is a state that is excluded by one but not by the other. 2

The theoretical consequences of the discretization are several. First, convergence is not guaranteed and actually the value in a cell may oscillate. Second, the value function approximated in this way does not remain necessarily a lower bound. 3 These problems are common to most of the (nonlinear) function approximations schemes used in practice, and the simple discretization scheme used in RTDP-Bel is no exception. The question, however, is how well this function approximation scheme works in practice.

2 This property becomes more important in problems involving action preconditions [Bonet, 2002].

3 Some of the theoretical shortcomings of RTDP-Bel can be addressed by storing in the hash table the values of a set of selected belief points, and then using suitable interpolation methods for approximating the value of beliefs points that are not in the table. This is what grid-based methods do [Hauskrecht, 2000]. These interpolations, however, involve a large computational overhead, and do not appear to be cost-effective.

1. Start with b = b0.
2. Sample state s with probability b(s).
3. Evaluate each action a in b as:

initializing V (boa ) to h(boa ) if boa is not in the hash.

1. Select action a that minimizes Q(a, b).
2. Update V (b) to Q(a, b).
3. Sample next state s′ with probability Pa(s′ |s).
4. Sample observation o with probability Qa(o|s′ ).
5. Compute boa using (6).
6. Finish if boa is target belief, else b := boa and s := s′ and goto 3.

Figure 2: RTDP-Bel is RTDP over the belief MDP with an additional provision: for reading or writing the value V (b) in the hash table, b is replaced by d(b) where d is the discretization function.

4 Discount and Point-based Algorithms

Discounted cost-based POMDPs differ from Goal POMDPs in two ways: target states are not required and a discount factor γ ∈ (0, 1) is used instead. The Bellman equation for discounted models becomes:

The expected cost V π (b) for policy π is always well-defined and bounded by C/(1 -γ) where C is the largest cost c(a, s) in the problem.

Discounted reward-based POMDPs are similar except that rewards r(a, s) are used instead of costs c(a, s), and a max operator is used in the Bellman equation instead of min. A discounted reward-based POMDP can be easily translated into an equivalent discounted cost-based POMDP by simply multiplying all rewards by -1.

Point-based algorithms target discounted POMDPs. They use a finite representation of the (exact) value function for POMDPs due to Sondik [1971] that enables the computation of exact solutions. In Sondik's representation, a value function V is represented as a finite set Γ of |S|-dimensional real vectors such that

Point-based algorithms, however, replace the updates of full synchronous value iteration with faster and more effective updates at selected beliefs. The update at a single belief b of a function V , represented by a set Γ of vectors α, results in the addition of a single vector to Γ, called backup(b), whose computation in vector notation is [Pineau et al., 2006;

Shani et al., 2007]:

This computation can be executed efficiently in time O(|A||O||S||Γ|) and forms the basis of all point-based POMDP algorithms that differ mainly in the selection of the belief points to update and the order of the updates.

5 Transformation of POMDPs

For transforming discounted POMDPs into equivalent Goal POMDPs, we need to make precise the notion of equivalence. Let us say that the sign of a POMDP is positive if it is a costbased POMDP, and negative if it is a reward-based POMDP. Also, let V πM (b) denote the expected cost (resp. reward) from b in a positive (resp. negative) POMDP M. Then, if the target states are absorbing, cost-free, and observable, an equivalence relation among two POMDPs of any types can be expressed as follows:

Definition 1. Two POMDPs R and M are equivalent if they have the same set of non-target states, and there are two constants α and β such that for every policy π and non-target belief b, V π R (b) = αV πM (b) + β with α > 0 if R and M are POMDPs of the same sign, and α < 0 otherwise.

That is, two POMDPs R and M are equivalent if their value functions are related by a simple linear transformation over the same set of non-target beliefs. It follows that if R and M are equivalent, they have the same optimal policies and the same 'preference order' among policies. Thus, if R is a discounted reward-based POMDP and M is an equivalent Goal POMDP, we can obtain optimal and/or suboptimal policies for R by running an optimal and/or approximate algorithm over M.

We say that a transformation that maps a POMDP M into M ′ is equivalence-preserving if M and M ′ are equivalent. In this work, we consider three transformations, all of which leave certain parameters of the POMDP unaffected. In the following transformations, we only mention the parameters that change:

• T1. R ↦→ R+C is about the addition of a constant C (positive or negative) to all rewards/costs. It maps a discounted POMDP R into the discounted POMDP R + C by replacing the rewards (resp. costs) r(a, s) (resp. c(a, s)) by r(a, s) + C (resp. c(a, s) + C).
• T2. R ↦→ kR is about the multiplication by a constant k ̸= 0 (positive or negative) of all rewards/costs. It maps a discounted POMDP R into the discounted POMDP kR by replacing the rewards (resp. costs) r(a, s) (resp. c(a, s)) by kr(a, s) (resp. kc(a, s)). If k is negative, R and kR have opposite signs.
• T3. R ↦→ R eliminates the discount factor. It maps a discounted cost-based POMDP R into a shortest-path

POMDP R by adding a fully observable target state t so that Pa(t|s) = 1 - γ, Pa(s′ |s) = γP R a (s′ |s), Oa(t|t) = 1 and Oa(s|t) = 0 where γ is the discount factor in R and P R a (s′ |s) refers to the transition probabilities in model R.

Theorem 2. The transformations R ↦→ R+C, R ↦→ kR and R ↦→ R are all equivalence-preserving.

Proof (sketch): One shows that if V π R (b) is the value function for the policy π in R over the non-target beliefs b, and hence the (unique) solution of the Bellman equation for π in R:

then V π R (b) + C/(1 -γ) is the solution of the Bellman equation for the same policy π in the model R + C, kV π R (b) is the solution of the Bellman equation for π in kR, and V π R (b) itself is the solution of Bellman equation for π in R. This all involves the manipulation of the Bellman equation for π in the various models. In particular, for proving V π R+C (b) = V π R (b) + C/(1 - γ), for example, we add the expression C′ = C/(1 - γ) to both sides of (14), to obtain:

as C′ = C + γC′ , and thus V π R (b) +C′ is the solution of the Bellman equation for π in R + C.

Theorem 3. Let R be a discounted reward-based POMDP, and C a constant that bounds all rewards in R from above; i.e. C > maxa,s r(a, s). Then, M = -R+C is a Goal POMDP equivalent to R. Indeed,

for all non-target beliefs b and policies π.

Proof (sketch): For such C, -R is a discounted cost-based POMDP, -R + C is a discounted cost-based POMDP with positive costs, and M = -R+C is a Goal POMDP. A straightforward calculation shows that V π R (b) = -V πM (b) + C/(1 - γ) for all non-target beliefs b, and hence V π R (b) = αV πM (b) + β with a negative α = -1, in agreement with the signs of R and M.

As an illustration, the transformation of the discounted reward-based POMDP Tiger with 2 states into a Goal POMDP with 3 states is shown in Fig. 3, where the third state is a target (absorbing, costs-free, and observable). Although not shown, the rewards are transformed into positive costs by multiplying them by -1 and adding them the constant 11, as the maximal reward for the original problem is 10.

6 RTDP-Bel vs. Point-based Algorithms

For comparing RTDP-Bel with point-based algorithms over discounted benchmarks R, we run RTDP-Bel over the equivalent Goal POMDPs M and evaluate the resulting policies back in the original model R in the standard way. In the experiments, we use the discretization parameter D = 15. We have also found it useful to avoid transitions in the simulation to the dummy target state t created in the transformation which makes long trials unlikely. Notice that target beliefs bt do not need to be explored or visited as V ∗ (bt) = h(bt) = 0.

The point-based algorithms considered are HSVI2 [Smith and Simmons, 2005], PBVI [Pineau et al., 2006], Perseus [Spaan and Vlassis, 2005] and FSVI [Shani et al., 2007]. As usual, we also include the QMDP policy.

Table 1 displays the average discounted reward (ADR) of the policies obtained by each of the algorithms, the time in seconds for obtaining such policies, and some algorithmspecific information: for HSVI2 the number of planes in the final policy, for Perseus and PBVI+GER the number of beliefs points in the belief set, for FSVI the size of the final value function, and for RTDP-Bel the final number of entries in the hash table and the number of trials.

Except when indicated, the data has been collected by running the algorithms on our machine (a Xeon at 2.0GHz), from code made available by the authors. For FSVI, the experiments on Tag and LifeSurvey1 did not finish, with the algorithm apparently cycling with a poor policy.

The ADR is measured over 1,000 simulation trials of 250 steps each, except in three problems: Hallway, Hallway2, and Tag. These problems include designated 'goal states' that are not absorbing. In these cases, simulation trials are terminated when such states are reached.

As it can be seen from the table, RTDP-Bel does particularly well in the 6 largest problems (Tag, RockSample, and LifeSurvey1): in 4 of these problems RTDP-Bel returns the best policies (highest ADR) and in the other two, it returns policies that are within the confidence interval of the best algorithm. In addition, in 4 of these problems (the largest 4), RTDP-Bel is also the fastest. On the other hand, RTDPBel does not perform as well in the 3 smallest problems, and in particular in the two Hallway problems where it produces weaker policies in more time than all the other algorithms.

We also studied the effect of using different discretizations. Fig. 4 shows the quality of the policies resulting from up to 300,000 trials, for the Tag problem using D = 5, 15, 25. The cases for D = 5 and D = 15 are similar in this problem except that in the first case RTDP-Bel takes 290 seconds and uses 250k hash entries, and in the second, 493 seconds and 2.5m hash entries. The case of D = 25 is different as RTDPBel needs then more than 300,000 trials to reach the target ADR. In this case, RTDP-Bel takes 935 seconds and uses 7.7m hash entries. In this problem D = 5 works best, but in other problems finer discretizations are needed. All the results in Table 1 are with D = 15.

7 Discussion

RTDP-Bel is a simple adaptation of the RTDP algorithm to goal POMDPs that precedes the recent generation of pointbased algorithms and some of its ideas. The experiments show, however, that RTDP-Bel can be competitive, and even superior to point-based algorithms in both time and quality. This raises two questions. First, why RTDP-Bel has been neglected up to now, and second, why RTDP-Bel does as well? We do not know the answer to the first question but suspect that the reason is that RTDP-Bel has been used over discounted benchmarks where it doesn't work. RTDP-Bel, is for Goal POMDPs, in the same way that RTDP is for Goal MDPs. In this work, we have shown how discounted POMDPs can be translated into equivalent Goal POMDPs for RTDP-Bel to be used. About the second question, the reasons that RTDP-Bel does well on goal POMDPs appear to be similar to the reasons that RTDP does well on goal MDPs: restricting the updates to the states generated by the stochastic simulation of the greedy policy appears to be quite effective, ensuring convergence without getting trapped into loops. The discretization in POMDPs, if suitable, doesn't appear to hurt this. On the other hand, this property does not result from value functions represented in Sondik's form that encode upper bounds rather than lower bounds (in the cost setting). The two type of methods, however, are not incompatible and it may be possible to combine the strengths of both.

Acknowledgments

We thank J. Pineau and S. Thrun, T. Smith and G. Shani for helping us with PBVI, HSVI2 and FSVI. The work of H. Geffner is partially supported by grant TIN2006-15387-C03-03 from MEC/Spain.