Goal-HSVI: Heuristic Search Value Iteration for Goal POMDPs

1 Introduction

POMDPs. The standard model for analysis of probabilistic systems with both nondeterministic as well as probabilistic behaviors are Markov decision processes (MDPs) [Howard, 1960], which are widely used to solve control and planning problems [Filar and Vrieze, 1997; Puterman, 1994]. The nondeterministic choices represent the freedom of the controller to execute control actions, and the probabilistic behavior describes the stochastic system response to these actions. In the presence of uncertainty about the environment, MDPs are extended to partially observable MDPs (POMDPs) where the controller does not have a perfect view of the system [Papadimitriou and Tsitsiklis, 1987; Littman, 1996]. (PO)MDPs provide a model to study a wide variety of applications, ranging from computational biology [Durbin et al., 1998], to speech processing [Mohri, 1997], image processing [Culik and Kari, 1997], software verification [ ˇCern´y et al., 2011], reinforcement learning [Kaelbling et al., 1996], and others.

∗This work has been supported by Vienna Science and Technology Fund (WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), and ERC Starting grant (279307: Graph Games). This research was sponsored by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Security CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.

Classical optimization objectives. In the standard optimization problems related to POMDPs, the transitions are associated with integer costs. Two classical objectives are the finite-horizon and discounted-sum objectives [Filar and Vrieze, 1997; Puterman, 1994; Papadimitriou and Tsitsiklis, 1987]. For finite-horizon objectives, a finite length k is given, and the goal is to minimize the expected total cost for k steps. In discounted-sum objectives, the cost in the j-th step is multiplied by γ j , for 0 < γ < 1, and the goal is to minimize the expected total discounted cost over the infinite horizon.

Goal-POMDPs. Besides the above, another classical and fundamental objective is the indefinite-horizon objective (which is similar to stochastic shortest path problem) that has been widely studied for MDPs and POMDPs [Bertsekas and Tsitsiklis, 1996; Patek, 2001; Bertsekas, 2005; Bonet and Geffner, 2009; Kolobov et al., 2011; Chatterjee et al., 2016], often under the name of Goal-POMDPs. In this case, there is a set of target states, all positive costs, and the goal is to minimize the expected total cost till the target set is reached. Note that the objective is not discounted-sum, but a total sum without discounts. The objective is also not finitehorizon, as there is no a priori bound to reach the target set (a target can be reached at different times along different paths). As an example application, consider robot planning, where a target state or goal must be reached, and each transition has an energy consumption requirement. The objective is to reach the goal while spending as little energy as possible. Since the energy consumption is a sum rather than a discounted sum, this problem (and similarly many other applications [Chatterjee et al., 2016]) is naturally modeled as a Goal-POMDP.

Previous results. In contrast to POMDPs with discountedsum objectives, to the best of our knowledge, there does not exist a practical method for solving Goal-POMDPs that provably converges to a near-optimal policy. The algorithms used previously in practice are RTDP-Bel (real-time dynamic programming) [Bonet, 1998; Bonet and Geffner, 2009] and also heuristic search value iteration (HSVI) algorithm [Smith and Simmons, 2004; 2005] that was used for solving GoalPOMDPs in [Warnquist et al., 2013]. While RTDP-Bel does not guarantee convergence, it performs well in practice on examples such as RockSample [Bonet and Geffner, 2009]. Similarly, HSVI performs well on some Goal-POMDP examples [Warnquist et al., 2013], but it need not work for GoalPOMDPs in general [Smith, 2007, Theorem 6.9].

Our contributions. We extend the discussion on the convergence of HSVI algorithm when applied to Goal-POMDPs, and we illuminate the key issues of HSVI on counterexamples. We address these issues and, based on our insights, we present a novel Goal-HSVI algorithm for solving GoalPOMDPs. Goal-HSVI is an advancement over previous approaches from the theoretical as well as practical perspective: (1) From the theoretical perspective, Goal-HSVI provides upper and lower bounds on the optimal value (and the quality of the currently considered policy) at all points of time and these bounds converge. Thus we provide the first algorithm with a theoretical guarantee of convergence for Goal-POMDPs, and our algorithm provides an anytime approximation. (2) From the practical perspective, we present an implementation of our algorithm and experimental results on several classical POMDP examples from the literature. While Goal-HSVI is comparable to RTDP-Bel on the RockSample domain, it dramatically outperforms RTDP-Bel on several other domains.

2 Goal-POMDPs and Previous Algorithm

We use the notation from [Bonet and Geffner, 2009] and define a Goal-POMDP as a tuple 〈S,G,A,O, P,Q, c, b0〉, where S is a finite non-empty set of states, G is a non-empty set of target (or goal) states (G ⊆ S), A is a finite non-empty set of actions, O is a finite non-empty set of observations (og ∈ O notifies the agent about reaching the goal), Pa(s, s′ ) is the probability to transition from s to s′ by using action a, Qa(o|s′ ) is the probability to observe o when entering state s′ by using action a, c(s, a) > 0 is the cost for taking action a in a non-target state s and b0 ∈ ∆(S) is the initial belief (∆(S) denotes the set of all probability distributions over S). Without loss of generality, we assume G = {g}.

We assume that the agent does not incur any cost after reaching the target state g, i.e. c(g, a) = 0 for every a ∈ A. Moreover, state g is absorbing, i.e., Pa(g, g) = 1 for every a ∈ A, and the agent is always certain about reaching g (i.e., Qa(og|g) = 1 for every a ∈ A and Qa(og|s) = 0 for every s ̸= g). We also assume that the goal state is reachable from every non-target state, i.e., the agent can never enter a deadend. This requirement can, however, be overcome by precomputing a set of allowed actions for each belief support [Chatterjee et al., 2016]. The algorithms for Goal-POMDPs can, therefore, be easily extended to the problems with dead-ends by considering only actions that are allowed in the current belief (and thus avoiding dead-ends). Note that the assumption of positive costs is, however, essential for the approximability

of the problem as allowing negative costs renders any approximation undecidable [Chatterjee et al., 2016, Theorem 2].

POMDPs are solved by transformation to MDPs using the notion of belief states b ∈ ∆(S) where b(s) corresponds to the probability that the system is in state s. The probability of being in state s′ after playing action a in belief state b is

Since the probability of observing o depends only on the action a and the state that is reached after playing a, the probability of observing o after playing a in belief state b is

The probability of being in state s′ given that action a was played and observation o received in belief b is

This transformation creates a perfect information MDP with a continuous state space of beliefs with transition function Pa(boa |b) = Oa(o|b). The Bellman equation for POMDPs is

The value function V ∗ is a concave function mapping beliefs to expected total costs, it is unique, and allows us to control a POMDP by always playing the minimizing action according to Equation (4). A common approach to solve POMDPs is thus to approximate V ∗ .

RTDP-Bel. The RTDP-Bel algorithm [Bonet, 1998; Bonet and Geffner, 2009] is based on RTDP [Barto et al., 1995] for perfect-information Goal-MDPs. RTDP-Bel adapts RTDP to partially-observable domains by using a grid-based approximation of V ∗ and using a hash-table to store the values, where V ∗ (b) ∼ ̂ V (⌊K · b⌋) for some fixed parameter K ∈ N. This approximation, however, loses the theoretical properties of RTDP. The algorithm need not converge as the values of the discretized value function may oscillate. Moreover, there is no guarantee that the values stored in the hash-table will form a bound on the values of V ∗ [Bonet and Geffner, 2009, p. 3, last paragraph of Section 3]. Despite the lack of theoretical properties, RTDP-Bel has been shown to perform well in practice both on indefinite-horizon problems [Bonet, 1998] and discounted-sum problems after transforming them into Goal-POMDPs [Bonet and Geffner, 2009]. The RTDP-Bel algorithm performs a sequence of trials (see Algorithm 1).

3 HSVI for Discounted-SumPOMDPs

Unlike RTDP-Bel, most of the point-based approaches approximate V ∗ using piecewise-linear functions [Smith and Simmons, 2004; 2005; Kurniawati et al., 2008]. We illustrate the difference between a grid-based approximation used in RTDP-Bel and a piecewise-linear approximation in Figures 1a and 1b. Observe that unlike the grid-based approximation, piecewise-linear approximation can yield a close approximation of V ∗ even in regions with rapid change of value.

In the original version of the heuristic-search value iteration algorithm (HSVI) [Smith and Simmons, 2004], the algorithm keeps two piecewise-linear and concave (PWLC) functions V and V to approximate V ∗ (see Figure 1b) and refines them over time. The upper bound on the cost is represented in the vector-set representation using a set of vectors Γ, while the lower bound is formed as an upper convex hull of a set of points Υ = {(bi, yi) | i = 1, . . . , m} where bi ∈ ∆(S).

Computing V (b) according to Equation (6) requires solving a linear program. In the second version of the algorithm (HSVI2, [Smith and Simmons, 2005]), the PWLC representation of lower bound has been replaced by a sawtooth-shaped approximation [Hauskrecht, 2000] (see Figure 1c). While the sawtooth approximation is less tight with the same set of points, the computation of V (b) can be done in linear time in the size of Υ. In this work, we consider exactly this HSVI2 version of the algorithm (and we refer to it as vanilla-HSVI).

HSVI2 initializes the value function V by considering policies 'always play action a' and constructing one α-vector for each action a ∈ A corresponding to the expected cost for playing such policy. For the initialization of the lower bound, the fast-informed bound is used [Hauskrecht, 2000].

The refinement of V and V is done by adding new elements to the sets Γ and Υ. Each of these updates is meant to improve the approximation quality in a selected belief b as much as possible, hence termed point-based update (see Algorithm 2). Recall that in discounted-sum POMDPs, γ ∈ [0, 1) is the discount factor and the objective is to minimize the expected discounted sum ∑∞i=1 γ i-1 ci of costs ci incurred during play.

1 αoa ← argminα∈Γ 〈α, boa〉 for all a ∈ A, o ∈ O 2 αa(s) ← c(s, a) +γ ∑o,s′ Pra(o, s′ |s)αoa(s′ ) ∀s, a 3 Γ←Γ∪ {argminαa 〈αa, b〉} 4 Υ ← Υ∪{(b, mina [∑s b(s)c(s, a) + γ ∑oOa(o|b)V (boa)])} Algorithm 2: Point-based update(b) procedure of (V , V ).

Similarly to RTDP-Bel, HSVI2 selects beliefs where the update should be performed based on the simulated play (selecting actions according to V ). Unlike RTDP-Bel, however, observations are not selected randomly. Instead, it selects an observation with the highest weighted excess gap, i.e. the excess approximation error V (boa ) - V (boa ) - ϵγ-(t+1) in boa weighted by the probability Oa(o|b) is the greatest. This heuristical choice attempts to target beliefs where the update will have the most significant impact on V (b0) - V (b0).

The HSVI2 algorithm for discounted-sum POMDPs (0 < γ < 1) is shown in Algorithm 3. This algorithm provably converges to an ϵ-approximation of V ∗ (b0) using values V (b0) and V (b0), see [Smith and Simmons, 2004].

4 Vanilla-HSVI and Goal-POMDPs

While HSVI2 (termed vanilla-HSVI for our purposes) was applied in Goal-POMDPs [Warnquist et al., 2013], it loses its desirable theoretical guarantees as shown already by [Smith, 2007]. We discuss three key issues related to the algorithm in the Goal-POMDP setting and illustrate them on examples.

Initial values can be infinite. Vanilla-HSVI initializes value function V by considering the values of a blind policy (i.e., a policy prescribing the agent to use a fixed action a forever). Such policies, however, need not reach the goal with probability 1. Observe that in the example from Figure 2 the policies 'play a forever' and 'play b forever' never reach the goal and their cost is thus infinite. Moreover, since the play stays in s1 with positive probability, V (s1) remains infinite forever. Solution: Instead of blind policies, we initialize V using the uniform policy. Since the goal state g is reachable from every state, the uniform policy reaches g with probability 1 and thus it has finite values [Chatterjee et al., 2016, Lemma 5 and 6].

Exploration need not terminate. In discounted-sum problems, the sequence ϵγ-t is strictly increasing and unbounded (since 0 < γ < 1). Its value therefore eventually exceeds the gap V (b) - V (b) (which is guaranteed by the initialization to be bounded) and the recursive explore procedure of

1 Initialize V and V 2 while V (b0) -V (b0) > ϵ do explore(b0, ϵ, 0) 3 procedure explore(b, ϵ, t) 4 if V (b) - V (b) ≤ ϵγ-t then return 5 a∗ ← arg mina [∑s b(s)c(s, a)+γ ∑o Oa(o|b)V (boa)] 6 update(b) 7 o∗ ← arg maxo Oa∗ (o|b)·[V (boa∗ ) - V (boa∗ ) - ϵγ-(t+1) ] 8 explore(bo∗ a∗ , ϵ, t + 1) 9 update(b)

c(r, ri) = 50, c(s1, r2) = c(s2, r1) = 100, other costs in non-goals 1

Figure 3: Goal-POMDP where the explore procedure of vanillaHSVI does not terminate, ri must be played to reach g, b0(r) = 1.

vanilla-HSVI terminates. This is clearly not the case in GoalPOMDPs where γ = 1. In [Smith, 2007, Theorem 6.9], it has been shown that the observation-selection heuristic of vanillaHSVI (HSVI2) may cause the algorithm to enter an infinite loop. We show that even the action selection (line 5 of Algorithm 3) is susceptible to this behavior (and thus modifying the observation-selection heuristic does not fix the algorithm).

Consider the Goal-POMDP shown in Figure 3 where r is the initial state. The target state g can only be reached by playing action r1 or r2 at some point. We show, however, that the way the value function V is updated and beliefs are changed during the explore recursion prevents these actions to be ever considered. First, observe that the only reachable non-goal beliefs in this POMDP are bT , where T ∈ Z+0 and

and that the lower bound on the cost of playing ri in bT , V ri (bT ), is independent of T and constant

This means that the explore procedure selects ri in bT only if V m(bT ) = V (bT+1 ) + c(∗, m) ≥ V ri (bT ) = 50.

The recursion starts with a linear V where V (b∞) = 1 and V (b0 ) = 6 (as initialized by the fast informed bound). In this situation, V (b1 ) is a convex combination 0.8V (b0 ) + 0.2V (b∞) and action m is optimal in b0 , its value in b0 is

and the addition of the point (b0 , y0 ) does not change V . At the T-th level of explore recursion, set Υ contains (b0 , y0 ), . . . , (bT-1 , yT-1 ) and (b∞, 1). A point-based update is performed in bT (generating point (bT , yT )). It holds

At this point, V (bT+1 ) is a convex combination of values yT-1 = V (bT-1 ) and V (b∞), 0.82 yT-1 + 0.36 · 1 (see Figure 4 for illustration). If mwas always optimal, the sequence of yT values can be characterized by a difference equation yT = 1 + 0.82 yT-1 + 0.36 · 1. For y0 = 6, this sequence (generating points on the dashed line in Figure 4) is decreasing and it never exceeds value 50. Hence m is always optimal and actions r1 and r2 are never used during the trial. Note that V (bT ) ≥ V ∗ (bT ) = 50 for every T ∈ Z+0 (we cannot avoid playing ri eventually) and thus for sufficiently small ϵ the excess gap is always positive, and the trial never terminates. Solution: In our Goal-HSVI algorithm, we cut off excessively long samples while guaranteeing that an ϵ-optimal solution is found within this limit. Such an approach has been used previously in practice without studying its impact on the solution quality (e.g., in POMDPSolver for discounted-sum POMDPs used in [Warnquist et al., 2013] where the depth limit is set to 200). However, using any fixed depth limit for all indefinitehorizon POMDPs is not sound (consider a POMDP where more than 200 precisely timed steps have to be taken to reach the goal). We address this and consider a depth limit that provides theoretical guarantees on the solution quality.

Observation-selection heuristic may suppress exploration. Finally, terminating excessively long trials alone is not sufficient. Consider the example from [Smith, 2007, Theorem 6.9]. Value functions V and V are never changed during the trial. Hence, after termination, a new trial operates on the same V and V . Thus it remains in states s0 and s1 - and the state s2 that is necessary for convergence is never considered. Solution: There are multiple possible solutions to this problem (e.g., changing the observation-selection heuristic). To remain consistent with vanilla-HSVI (and use the same heuristic), our Goal-HSVI algorithm keeps a data structure (a closed-list, denoted CL) tracking the action-observation sequences that have been already considered. When selecting an observation according to the observation-selection heuristic, the algorithm avoids choosing one that would lead to an action-observation sequence fully explored earlier.

5 Goal-HSVI

In this section, we present our novel Goal-HSVI approach to solve Goal-POMDPs. In Section 5.1, we present the basic algorithm and its theoretical guarantees, and in Section 5.2, we extend this algorithm to obtain a practical approach.

5.1 Basic Algorithm

The changes we presented in the previous section constitute the basis for our Goal-HSVI algorithm (see Algorithm 4). Our algorithm extends the vanilla-HSVI (Algorithm 3) with the three following key modifications:

1. The uniform policy is used for initialization of V (line 1).
2. The search depth is bounded (line 5). We terminate trials longer than C cmin · C-ηϵ (1-η)ϵ steps where C is the upper bound on cost of playing the uniform policy and cmin is the minimum per-step cost. We prove that this choice together with a stricter termination condition V (b) - V (b) ≤ ηϵ

(for η < 1) guarantees that an ϵ-optimal solution is found by the Goal-HSVI algorithm (see Theorem 1).

1. Exploring the same history more than once is avoided. We keep track of the action-observation history (a, o) during the exploration. A history is marked as closed by adding it to the closed list CL in case the history is terminal (line 6) or all histories reachable when using action a∗ are already closed (lines 9-10). The set of observations O′ denotes all observations that lead to an actionobservation history that has not yet been closed. Together with the choice of o∗ ∈ O′ (line 11), this guarantees that no action-observation history is considered twice.

Note that the closed list CL can be efficiently represented using a prefix tree. Each action-observation history is represented by a path in the tree (where each node corresponds to playing the given action or seeing the given observation). Furthermore, each node is attributed a binary flag indicating whether the given action-observation history is closed. The memory efficiency of this representation comes from the fact that multiple histories share the same prefix (and thus the same part of the path). This claim is supported by the experimental evaluation (see Table 1) as the number of nodes in the prefix tree is typically comparable with the number of elements representing value functions V and V .

Theorem 1. Assume η ∈ [0, 1) and let C be the maximum cost of playing the uniform policy (C = maxs V (bs ) for the initial V ). Let cmin = mins,a c(s, a). Then the Goal-HSVI algorithm (Algorithm4) with the cutoff after T = C cmin · C-ηϵ (1-η)ϵ steps terminates and yields an ϵ-approximation of V ∗ (b0).

Proof. Let (∅, ∅) ∈ CL. Let σ be an action-observation history and consider a policy π(σ) where the agent plays action a∗ chosen in explore when σ (represented by (a, o) in the algorithm) was closed on line 10. Since a history is closed when the horizon T or precision ηϵ is reached, or when all action-observation histories reached by playing a∗ are closed, it is clear that all plays according to π eventually reach a terminal action-observation history (closed on line 6). Let bσ be the belief after playing σ and let us assign values vlb(σ) and vub(σ) to each terminal action-observation history σ corresponding to values V (bσ) and V (bσ) at the time σ has been

1 Initialize V and V (V initialized by the uniform policy) 2 CL← ∅ 3 while V (b0) -V (b0) > ϵ do explore(b0, ϵ, 0, ∅, ∅) 4 procedure explore(b, ϵ, t, a, o) 5 if V (b) -V (b) ≤ ηϵ or t ≥ C cmin · C-ηϵ (1-η)ϵ then 6 CL ← CL ∪ {(a, o)} and return 7 a∗ ← arg mina [∑s b(s)c(s, a) + ∑o Oa(o|b)V (boa)] 8 update(b) 9 O′ ← {o | (aa∗ , oo) ̸∈ CL} 10 if O′ = ∅ then CL ← CL ∪ {(a, o)} and return 11 o∗ ← arg maxo∈O′ Oa∗ (o|b) · [V (boa∗ ) - V (boa∗ ) - ηϵ] 12 explore(bo∗ a∗ , ϵ, t + 1, aa∗ , oo∗) 13 update(b) Algorithm 4: Goal-HSVI, η ∈ [0, 1)

closed. Let us propagate values vlb and vub using Bellman equation in a bottom-up manner, i.e. for i ∈ {lb, ub},

Since the bounds might have improved since the histories were closed, it holds vlb(∅) ≤ V (b0) ≤ V (b0) ≤ vub(∅). Observe that the probability that any history consistent with π reaches the depth limit T (i.e., the sum of probabilities of all plays reaching the depth T when following π) is at most pcutoff ≤ (1 - η)ϵ/(C - ηϵ). Otherwise, the contribution of those plays to the expected cost vlb(∅) would have been greater than C (as at least cmin is paid per step) which would have contradicted that C is the upper bound. Now, since vub(σ) - vlb(σ) in terminal histories that were cut off is less than C (reached with probability pcutoff ), and vub(σ)- vlb(σ) ≤ ηϵ otherwise, the difference vub(∅) - vlb(∅) in the root is a weighted average of these values,

5.2 Practical Extension: Iterative Deepening

The bound on the search depth induced by Theorem 1 can be unnecessarily large in practice. To avoid generating excessively long trials, we propose a variant of our Goal-HSVI algorithm enriched by the ideas of iterative deepening. Instead of terminating trials when they exceed T = C cmin · C-ηϵ (1-η)ϵ , a cut-off depth ̂ T is introduced, starting with ̂ T := 1 and increasing it when one of the following situations occur:

1. All action-observation histories within the current depth limit ̂ T are explored. If no ϵ-optimal solution was found with the current depth limit, the limit must be increased. This situation is indicated by (∅, ∅) ∈ CL.
2. The improvement during the current trial was insufficient. We say that the improvement is sufficient if the difference V (b)-V (b) before and after a call to explore (denoted δ and δ′ ) weighted by the probability of seeing the observation sequence o when playing actions a (denoted Oa(o)) is greater than ρ( ̂ T), i.e. Oa(o) · (δ - δ′ ) ≥ ρ( ̂ T). Our implementation uses ρ( ̂ T) = p ̂ T with p = 0.95.

Whenever ̂ T is increased, CL is set to ∅ to allow the algorithm to reexplore action-observation histories considered previously and search them to a greater depth. In our implementation, we always increase the search depth ̂ T by one.

6 Empirical Evaluation

We present an experimental evaluation of Goal-HSVI in comparison with RTDP-Bel [Bonet and Geffner, 2009]. We do not include vanilla-HSVI (HSVI2 [Smith and Simmons, 2005]) in the experiments as the algorithm without modifications is theoretically incorrect in the Goal-POMDP setting, and it indeed crashed due to the recursion limit on some instances

(Hallway 2, Seq[5,5,3], Seq[5,5,4]). We start with the description of the setting of the algorithms considered.

Goal-HSVI. Our implementation is based on the ZMDP 1 implementation of HSVI2. We updated the solver according to Section 5. Few other changes were made: (1) We do not use adaptive precision from ZMDP that changes ϵ between iterations (fixed values ϵ = 2 and η = 0.8 are used). (2) We do not use α-vector masking as the implementation of this technique in ZMDP is incompatible with Goal-POMDPs. We terminate the algorithm after 900s if an ϵ-optimal solution is not found.

RTDP-Bel. GPT solver 2 is used as a reference implementation of RTDP-Bel. Since there are no guidelines for choosing the parameters of RTDP-Bel, we use the default values used in GPT (most importantly, K = 15 as in [Bonet and Geffner, 2009]) except for increasing the cutoff parameter from 250 to 2000. In our experiments we let RTDP-Bel perform 150,000 trials before terminating. As RTDP-Bel is a randomized algorithm, we perform 12 independent runs and report the result with the lowest average cost. We consider the cost of RTDPBel policies as a reference, and we report the time when GoalHSVI finds a policy of the same quality as tRTDP.

Policy evaluation. We evaluate the quality of the policies computed by the algorithms using simulation. We perform 250,000 simulated plays (we cut each of them after 2,000 steps if the goal is not reached by that time) and we report the average total cost. We also report the percentage of simulated plays that did not terminate within the limit.

We evaluate the performance of our Goal-HSVI algorithm on three different domains. The domains are: Hallway [Littman et al., 1995] and RockSample [Smith and Simmons, 2004] in their Goal-POMDP variants, and a new domain of Sequencing (inspired by [Kress-Gazit et al., 2009]).

Hallway [Littman et al., 1995]. An agent is navigating in a maze trying to reach the goal location while using unreliable actuators and sensors. In the original version, the agent receives a reward only when the goal is reached, and the discounted-sum objective is considered. For the GoalPOMDP version of the problem, we assume that the goal state is absorbing and each step of the agent costs one unit.

1 https://github.com/trey0/zmdp

2 https://github.com/bonetblai/gpt-rewards

[Bonet and Geffner, 2009] observed that RTDP-Bel had been outperformed by HSVI2 in the discounted-sum setting. Our Goal-HSVI algorithm similarly outperforms RTDP-Bel in the Goal-POMDP variant of Hallway (see Table 1). Moreover, the upper bound on cost produced by Goal-HSVI after 2s is lower than the cost of RTDP-Bel, and unlike RTDP-Bel, the policy produced by our algorithm always reached the goal in less than 2000 steps. (RTDP-Bel failed to reach goal in 2.5% and 16.5% of plays on Hallway and Hallway 2, respectively.)

RockSample[n,k] [Smith and Simmons, 2004]. A robot is operating in an n×n grid with k rocks. Each of the rocks can be either 'good' or 'bad' (unknown to the agent). The goal is to sample all the good rocks (approach them and perform expensive sampling) and then leave the map. In the GoalPOMDP version [Chatterjee et al., 2016], a cost is associated with each movement. Moreover, the agent pays a penalty for all the 'good' rocks he failed to sample upon leaving the map.

RTDP-Bel works well on discounted RockSample [Bonet and Geffner, 2009] due to the problem structure (e.g., knowledge of the current position), and the same is expected in the Goal-POMDP setting. Although Goal-HSVI does not leverage the problem structure, it is competitive on all RockSample instances we consider, see Table 1. Moreover, it provably found solutions of a comparable (or even better) quality as RTDP-Bel by decreasing the upper bound on cost (see tRTDP for the time required). Recall that RTDP-Bel cannot provide any such guarantees on the quality of the computed policy.

Sequencing[n,k,t]. An agent inspects t targets in an n × n grid with k obstacles (see Figure 5). He is uncertain about his position, and he has 5 actions available - 4 movement actions N, S, W, E and the inspection action. The movement actions are not reliable and may result in a step in any unintended direction with probability 0.15. The inspection action is deterministic and inspects the target (if there is one at the current position). The agent may receive two observations - either the last action succeeded (he stepped on an empty square / inspected a target) or it failed (he hit an obstacle / there is no target to inspect). The agent has to inspect the targets in a prescribed order - otherwise he pays a penalty 100t where t is the number of targets he should have inspected earlier. For example, if he inspects targets in Figure 5 in the order (4, 1, 3, 2), he accumulates a penalty 400.

We observe that RTDP-Bel does not work well for Sequencing and fails to find a policy reaching the goal state reliably, especially on the larger two instances. In contrary, our Goal-HSVI algorithm produces superior policies that always reached the goal (see Table 1). Notice that on Sequencing[5,5,3] and Sequencing[5,5,4], the time to complete 150,000 trials of RTDP-Bel is comparable to the time given to Goal-HSVI, yet still, the policy of RTDP-Bel is inferior.

7 Conclusions

We address the theoretical foundations of point-based methods for Goal-POMDPs. Previous approaches like RTDP-Bel and HSVI2 provide no convergence guarantees. We present the first algorithm, namely Goal-HSVI, with convergence guarantees and experimental results show it also performs well on examples. We believe that our work may spark further interest in analyzing point-based methods for Goal-POMDPs or generalizing Goal-HSVI to a multi-agent setting.