Sparse Tree Search Optimality Guarantees in POMDPs with Continuous Observation Spaces

1 Introduction

The partially observable Markov decision process (POMDP) is a flexible mathematical framework for representing sequential decision problems where knowledge of the state is incomplete [Kaelbling et al., 1998; Kochenderfer, 2015; Bertsekas, 2005]. The POMDP formalism can represent a wide range of real world problems including autonomous driving [Sunberg et al., 2017; Bai et al., 2015], cancer screening [Ayer et al., 2012], spoken dialog systems [Young et al., 2013], and others [Cassandra, 1998]. In one of the most successful applications, an approximate POMDP solution is being used in a new aircraft collision avoidance system that will be deployed worldwide [Holland et al., 2013].

A POMDP is an optimization problem for which the goal is to find a policy that specifies actions that will control the state to maximize the expectation of a reward function. One of the most popular ways to deal with the challenging computational complexity of finding such a policy [Papadimitriou and Tsitsiklis, 1987] is to use online tree search algorithms [Silver and Veness, 2010; Ye et al., 2017; Sunberg et al., 2017; Kurniawati and Yadav, 2016]. Instead of attempting to find a global policy that specifies actions for every possible outcome of the problem, online algorithms look for local approximate solutions as the agent is interacting with the environment.

Previous online approaches such as ABT [Kurniawati and Yadav, 2016], POMCP [Silver and Veness, 2010], and DESPOT [Ye et al., 2017] have exhibited good performance in large discrete domains. However, many real-world domains, notably when a robot interacts with the physical world, have continuous observation spaces, and the algorithms mentioned above will not always converge to an optimal policy in problems with continuous or naively discretized observation spaces [Sunberg and Kochenderfer, 2018].

Two recent approaches, POMCPOW [Sunberg and Kochenderfer, 2018] and DESPOT-α [Garg et al., 2019], have employed a weighting scheme inspired by particle filtering to achieve good performance on realistic problems with large or continuous observation spaces. However, there are currently no theoretical guarantees that these algorithms will find optimal solutions in the limit of infinite computational resources.

A convergence proof for these algorithms must have the following two components: (1) A proof that the particle weighting scheme is sound, and (2) a proof that the heuristics used to focus search on important parts of the tree are sound. This paper tackles the first component by analyzing a new simplified algorithm that expands every node of a sparse search tree.

First, we naively extend the sparse sampling algorithm of Kearns et al. [2002] to the partially observable domain in the spirit of POMCP and explain why this algorithm, known as partially observable sparse sampling (POSS), will converge to a suboptimal solution when the observation space is continuous. Then, we introduce appropriate weighting that results in the partially observable weighted sparse sampling (POWSS) algorithm. We prove that the value function estimated by POWSS converges to the optimal value function at a rate of O(C D exp(-t ·C)), where C is the planning width and number of particles, D is the depth, and t is a constant specific to the problem and desired accuracy. This yields a policy that can be made arbitrarily close to optimal by increasing the computation.

To our knowledge, POWSS is the first algorithm proven to converge to a globally optimal policy for POMDPs with continuous observation spaces without relying on any discretization schemes. Since POWSS fully expands all nodes in the sparse tree, it is not computationally efficient and is only practically applicable to toy problems. However, the convergence guarantees justify the weighting schemes in state-ofthe-art efficient algorithms like DESPOT-α and POMCPOW that solve realistic problems by only constructing the most important parts of the search tree.

The remainder of this paper proceeds as follows: First, Sections 2 and 3 review preliminary definitions and previous work. Then, Section 4 presents an overview of the POSS and POWSS algorithms. Next, Section 5 contains an importance sampling result used in subsequent sections. Section 6 contains the main contribution, a proof that POWSS converges to an optimal policy using induction from the leaves to the root to prove that the value function estimate will eventually be accurate with high probability at all nodes. Finally, Section 7 empirically shows convergence of POWSS on a modified tiger problem [Kaelbling et al., 1998].

2 Preliminaries

POMDP Formulation

A POMDP is defined by a 7-tuple (S,A,O, T ,Z,R, γ): S is the state space, A is the action space, O is the observation space, T is the transition density T (s′ |s, a), Z is the observation density Z(o|a, s′ ), R is the reward function, and γ ∈ [0, 1) is the discount factor [Kochenderfer, 2015; Bertsekas, 2005]. Since a POMDP agent receives only observations, the agent infers the state by maintaining a belief bt at each step t and updating it with new action and observation pair (at+1, ot+1) via Bayesian updates [Kaelbling et al., 1998]. A policy, denoted with π, maps beliefs bt generated from histories ht = (b0, a1, o1, · · · , at, ot) to actions at. Thus, to maximize the expected cumulative reward in POMDPs, the agent wants to find the optimal policy π∗ (bt).

We solve the finite-horizon problem of horizon length D. We formulate the state value function V and action value function Q for a given belief state b and policy π at step t by Bellman updates for t ∈ [0,D - 1], where bao indicates the belief b updated with (a, o):

Specifically, the optimal value functions satisfy the following:

Generative models. For many problems, the probability densities T and Z may be difficult to determine explicitly. Thus, some approaches only require that samples are generated according to the correct probability. In this case, a generative model G implicitly defines T , Z by generating a new state, s′ , observation, o, and reward, r, given the current state s and action a.

Probability notation. We denote probability measures with calligraphic letters (e.g. P,Q) to avoid confusion with the action value function Q(b, a). Furthermore, for two probability measures P,Q defined on a σ-algebra F, we denote P ≪ Q to state that P is absolutely continuous with respect to Q; for every measurable set A, Q(A) = 0 implies that P(A) = 0. Also, we use the abbreviations "a.s." for almost surely, and "i.i.d.r.v." for independent and identically distributed random variables.

3 Additional RelatedWork

In addition to the work mentioned in the introduction, there has been much work in similar areas. There are several online tree search techniques for fully observable Markov decision processes with continuous state spaces, most prominently Sparse-UCT [Bjarnason et al., 2009], and double progressive widening [Cou¨etoux et al., 2011].

There are also several approaches for solving POMDPs or belief-space MDPs with continuous observation spaces. For example, Monte Carlo Value Iteration (MCVI) can use a classifier to deal with continuous observation spaces [Bai et al., 2014]. Others partition the observation space [Hoey and Poupart, 2005] or assume that the most likely observation is always received [Platt et al., 2010]. Other approaches are based on motion planning [Bry and Roy, 2011; Agha-Mohammadi et al., 2011], locally optimizing precomputed trajectories [Van Den Berg et al., 2012], or optimizing open-loop plans [Sunberg et al., 2013]. McAllester and Singh [1999] also extend the sparse sampling algorithm of Kearns et al. [2002], but they use a belief simplification scheme instead of the particle sampling scheme.

4 Algorithms

We first define the algorithmic elements shared by POSS and POWSS, SELECTACTION and ESTIMATEV, in Algorithm 1. SELECTACTION is the entry point of the algorithm, which selects the best action for a belief b0 according to the Q-function by recursively calling ESTIMATEQ. ESTIMATEV is a subroutine that returns the value, V , for an estimated belief, by calling ESTIMATEQ for each action and returning the maximum. We use belief particle set ¯b at every step d, which contain pairs (si, wi) that correspond to the generated sample and its corresponding weight. The weight at initial step is uniformly normalized to 1/C, as the samples are drawn directly from b0.

Algorithm 1 Routines common to POWSS and POSS

Algorithm: SelectAction(b0, γ, G, C, D)

Input: Belief state b0, discount γ, generative model G, width C, max depth D.

Output: An action a∗ .

• 1: From the initial belief distribution b0, sample C particles and store it in ¯b0. For POWSS, weights are also initialized with wi = 1/C.
• 2: For each of the actions a ∈ A, calculate:

Algorithm: EstimateV(¯b, d)

Input: Belief particles ¯b, current depth d.

Output: A scalar ˆ V ∗ d (¯b) that is an estimate of V ∗ d (b).

• 1: If d ≥D the max depth, then return 0.
• 2: For each of the actions a ∈ A, calculate:

• 3: Return ˆ V ∗ d (¯b) = maxa∈A ˆQ∗d (¯b, a)

In Algorithms 1 to 3, we omit γ,G,C,D in the subsequent recursive calls for convenience since they are fixed globally.

We define ESTIMATEQ functions in Algorithm 2 for POSS and Algorithm 3 for POWSS, where both methods perform sampling and recursive calls to ESTIMATEV to estimate the Q-function at a given step. The crucial difference between these algorithms is shown in Fig. 1.

POSS naively samples the next s′i , oi, ri via the generating function for each state si in the belief particle set ¯b, at a given step d. Then, for each unique observation oj generated from the sampling step, POSS inserts the states s′i into the nextstep belief particle set baoj only if the generated observation oi matches oj . This behavior is similar to POMCP, DESPOT, or a particle filter that uses rejection and can quickly lead to particle depletion when there are many unique observations. Finally, POSS returns the naive average of the Q-functions calculated via recursive calculation of ESTIMATEV for each of the next-step beliefs.

On the other hand, POWSS uses particle weighting rather than using only unweighted particles with matching observation histories as in POSS. POWSS samples the next s′i , oi, ri via the generating function for each state-weight pair (si, wi) in the belief particle set ¯b. Now, for each observation oj generated from the sampling step, POWSS inserts all the states s′i and the new weights w′i = wi · Z(oj|a, s′i ) into the next-step belief particle set baoj. These weights are the adjusted probability of hypothetically obtaining oj from state s′i . POWSS then returns the weighted average of the Q-functions.

5 Importance Sampling

We begin the theoretical portion of this work by stating important properties about self-normalized importance sampling estimators (SN estimators). One goal of importance sampling is to estimate an expected value of a function f(x)

Algorithm 2 POSS

Algorithm: EstimateQ(¯b, a, d)

Input: Belief particles ¯b, action a, current depth d.

Output: A scalar ˆQ∗d (¯b, a) that is an estimate of Q∗d (b, a).

• 1: For each particle si in ¯b, generate s′i , oi, ri = G(si, a). If i > |¯b|, use si mod |¯b|.
• 2: For each unique observation oj fromprevious step, insert all s′i that satisfy oi = oj to a new belief particle set baoj .
• 3: Return

Algorithm 3 POWSS

Algorithm: EstimateQ(¯b, a, d)

Input: Belief particles ¯b, action a, current depth d.

Output: A scalar ˆQ∗d (¯b, a) that is an estimate of Q∗d (b, a).

• 1: For each particle-weight pair (si,wi) in ¯b, generate s′i , oi, ri fromG(si, a).
• 2: For each observation oj from previous step, iterate over i = {1, · · · ,C} to insert (s′i ,wi · Z(oj|a, s′i )) to a new belief particle set baoj.
• 3: Return

where x is drawn from distribution P, while the estimator only has access to another distribution Q along with the importance weights wP/Q(x) ∝ P(x)/Q(x). This is crucial for POWSS because we wish to estimate the reward for beliefs conditioned on observation sequences, while only being able to generate the marginal distribution of states with correct probability for an action sequence.

We define the following quantities:

Theorem 1 (SN d∞-Concentration Bound). Let P and Q be two probability measures on the measurable space (X,F) with P ≪ Q and d∞(P||Q) < +∞. Let x1, · · · , xN be i.i.d.r.v. sampled from Q, and f : X → R be a bounded Borel function (‖f‖∞ < +∞). Then, for any λ > 0 and N large enough such that λ > ‖f‖∞ d∞(P||Q)/√N, the following bound holds with probability at least 1 - 3 exp(-N · t2 (λ, N )):

where t(λ,N) is defined as:

Theorem 1 builds upon the derivation in Proposition D.3 of Metelli et al. [2018], which provides a polynomially decaying bound by assuming d2 exists. Here, we compromise by further assuming that the infinite R´enyi divergence d∞ exists and is bounded to get an exponentially decaying bound: d∞(P||Q) = ess supx∼QwP/Q(x) < +∞. The proof of Theorem 1 is given in Appendix A. 1

This exponential decay is important for the proofs in Section 6.2. We need to ensure that all nodes of the POWSS tree at all depths d reach convergence. The branching of the tree induces a factor proportional to N D . To offset this, we need a probabilistic bound at each depth that decays exponentially with N. Intuitive explanation of the d∞ assumption is given at the beginning of Section 6.2.

6 Convergence

6.1 POSS Convergence to QMDP

We present a short informal argument for the convergence of the Q-value estimates of POSS to the QMDP value (Definition 1) in continuous observation spaces. Sunberg and Kochenderfer [2018] provide a formal proof for a similar algorithm.

Definition 1 (QMDP value). Let QMDP(s, a) denote the optimal Q-function evaluated at state s and action a for the fully observable MDP relaxation of a POMDP. Then, the QMDP value at belief b, QMDP(b, a), is Es∼b [QMDP(s, a)].

Since the observations oi are drawn from a continuous distribution, the probability of obtaining duplicate oi values in ESTIMATEQ, line 1 is 0. Consequently, when evaluating ESTIMATEQ, all the belief particle sets after the root node only contain a single state particle each (Fig. 1, left), which means that each belief node is merely an alias for a unique state particle. Therefore, ESTIMATEV performs a rollout exactly as if the current state became entirely known after taking a single action, identical to the QMDP approximation. Since QMDP is sometimes suboptimal [Kaelbling et al., 1998], POSS is suboptimal for some continuous-observation POMDPs.

6.2 Near-Optimality of POWSS

On the other hand, we claim that the POWSS algorithm can be made to perform arbitrarily close to the optimal policy by increasing the width C.

In analyzing near-optimality of POWSS, we view POWSS Q-function estimates as SN estimators, and we apply the concentration inequality result from Theorem 1 to show that POWSS estimates at every node have small errors with high probability. Through the near-optimality of the Q-functions, we conclude that the value obtained by employing POWSS policy is also near-optimal with further assumptions on the closed-loop POMDP system.

1 Appendices are available in the pre-print version of this paper: https://arxiv.org/abs/1910.04332.

Assumptions for Analyzing POWSS

The following assumptions are needed for the proof:

• (i) S and O are continuous spaces, and the action space has a finite number of elements, |A| < +∞.
• (ii) For any observation sequence {on}j, the densities Z, T , b0 are chosen such that the R´enyi divergence of the target distribution P d and sampling distribution Qd (Eqs. (20) and (21)) is bounded above by dmax ∞ < +∞ a.s. for all d = 0, · · · ,D-1:

• (iii) The reward function R is Borel and bounded by a finite constant ||R||∞ ≤ Rmax < +∞ a.s., and Vmax ≡ Rmax 1-γ < +∞.
• (iv) We can sample from the generating function G and evaluate the observation probability density Z.
• (v) The POMDP terminates after D < ∞ steps.

Intuitively, condition (ii) means that the ratio of the conditional observation probability to the marginal observation probability cannot be too high. Additionally, our results still hold even when either of S,O are discrete, as long as it doesn't violate condition (ii), by appropriately switching the integrals to Riemann sums.

While we restrict our analysis to the case when γ < 1 for a finite horizon problem, the authors believe that similar results can be derived for either when γ = 1 or when dealing with infinite horizon problems.

Theorem 2 (Accuracy of POWSS Q-Value Estimates). Suppose conditions (i)-(v) are satisfied. Then, for a given ϵ > 0, choosing constants C, λ, δ that satisfy:

The Q-function estimates obtained for all depths d = 0, · · · , D - 1 and all actions a are near-optimal with probability at least 1- δ:

Theorem 3 (POWSS Policy Convergence). In addition to conditions (i)-(v), assume that the closed-loop POMDP Bayesian belief update step is exact. Then, for any ϵ > 0, we can choose a C such that the value obtained by POWSS is within ϵ of the optimal value function at b0 a.s.:

Theorems 2 and 3 are proven sequentially in the following subsections. We generally follow the proof strategy of Kearns et al. [2002] but with significant additions to account for the belief-based POMDP calculations rather than statebased MDP calculations. We use induction to prove a concentration inequality for the value function at all nodes in the tree, starting at the leaves and proceeding up to the root.

Value Convergence at Leaf Nodes

First, we reason about the convergence at nodes at depth D-1 (leaf nodes). In the subsequent analysis, we abbreviate some terms of interest with the following notation:

Here d denotes the depth, i denotes the index of the state sample, and j denotes the index of the observation sample. Absence of indices i, j means that {sn} and/or {on} appear as regular variables. Intuitively, T i 1:d is the transition density of state sequence i from the root node to depth d, and Z i,j 1:d is the conditional density of observation sequence j given state sequence i from the root node to depth d. Additionally, bid denotes bd(sd,i), rd,i the reward R(sd,i, ad), and wd,i the weight of sd,i.

Since the problem ends after D steps, the Q-function for nodes at depth D-1 is simply the expectation of final reward and the POWSS estimate has the following form:

Lemma 1 (SN Estimator Leaf Node Convergence). ˆQ∗D-1 (¯bD-1, a) is an SN estimator of Q∗D-1 (bD-1, a), and the following leaf-node concentration bound holds with probability at least 1-3 exp(-C · t2max (λ,C)),

Proof. First, we show that ˆQ∗D-1 (¯bD-1, a) is an SN estimator of Q∗D-1 (bD-1, a). By following the recursive belief update, the belief term can be fully expanded:

Then, Q∗D-1 (bD-1, a) is equal to the following:

We approximate the Q∗ function with importance sampling by utilizing problem requirement (iv), where the target density is bD-1. First, we sample the sequences {sn}i according to the joint probability (T1:D-1)b0. Afterwards, we weight the sequences by the corresponding observation density Z1:D-1, obtained from the generated observation sequences {on}j. For now, we assume the observation sequences {on}j are fixed.

Applying the importance sampling formalism to our system for all depths d = 0, · · · ,D - 1, P d is the normalized measure incorporating the probability of observation sequence j on top of the state sequence i until the node at depth d, and Qd is the measure of the state sequence. We can think of P d being indexed by the observation sequence {on}j .

The weighing step is done by updating the self-normalized weights given in POWSS algorithm. We define wd,i and rd,i as the weights and rewards obtained at step d for state sequence i from POWSS simulation. With our recursive definition of the empirical weights, we obtain the full weight of each state sequence i for a fixed observation sequence j:

Realizing that the marginal observation probability is independent of indexing by i, we show that ˆQ∗D-1 (¯bD-1, a) is an SN estimator of Q∗D-1 (bD-1, a):

Since {sn}1, · · · {sn}C are i.i.d.r.v. sequences of depth D sampled from QD-1 , and R is a bounded function from problem requirement (iii), we can apply the SN concentration bound in Theorem 1 to prove Lemma 1. Detailed finishing steps of the proof are given in Appendix B.

Induction from Leaf to Root Nodes

Now, we want to show that nodes at all depths have convergence guarantees via induction.

Lemma 2 (SN Estimator Step-by-Step Convergence). ˆQ∗d (¯bd, a) is an SN estimator of Q∗d (bd, a), and for all d = 0, · · · ,D - 1 and a, the following holds with probability at least 1 - 3|A|(3|A|C)D exp(-C · t2max ):

Proof. First, we set C such that C > (3Vmaxdmax ∞ /λ)2 to satisfy tmax(λ, C) > 0, which ensures that the SN concentration inequality holds with probability 1 - 3 exp(-C · t2max (λ, C)) at any given step d and action a. Furthermore, we multiply the worst-case union bound factor (3|A|C)D , since we want the function estimates to be within their respective concentration bounds for all the actions |A| and child nodes C at each step d = 0, · · · ,D-1, for the 3 times we use SN concentration bound in the induction step. We once again multiply the final δ by |A| to account for the root node Q-value estimates also satisfying their respective concentration bounds for all actions.

Following our definition of ESTIMATEQ, the value function estimates at step d are given as the following:

The base case d = D - 1 holds by Lemma 1. Then for the inductive step, we assume Eq. (29) holds for all actions at step d + 1. Using the triangle inequality for step d, we split the difference into two terms, the reward estimation error (A) and the next-step value estimation error (B):

Each of the error terms are bound by (A) ≤ Rmax 3Vmax λ and (B) ≤ 1 3 λ+ 2 3γ λ+αd+1. We provide a detailed justification of these bounds in Appendix C, which uses the SN concentration bound 3 times. Combining (A) and (B), we prove the inductive hypothesis:

Proof. (Theorem 2) First, we choose constants C, λ, δ and densities Z, T , b0 that satisfy the conditions in Theorem 2. Since αd ≤ α0, the following holds for all d = 0, · · · ,D-1 with probability at least 1 - δ through Lemmas 1 and 2:

Note that the convergence rate δ is O(C D exp(-tC)), where t = (λ/(3Vmaxdmax ∞ ))2 .

Near-Optimal Policy Performance

We have proven in the previous subsection that the planning step results in a near-optimal Q-value for a given belief. Assuming further that we have a perfect Bayesian belief update in the outer observe-plan-act loop, we prove Theorem 3, which states that the closed-loop POMDP policy generated by POWSS at each planning step results in a near-optimal policy. The proof given in Appendix D combines Theorem 2 with results from Kearns et al. [2002]; Singh and Yee [1994]:

7 Experiments

The simple numerical experiments in this section confirm the theoretical results of Section 6. Specifically, they show that the value function estimates of POSS converge to the QMDP approximation and the value function estimates of POWSS converge to the optimal value function for a toy problem.

7.1 Continuous Observation Tiger Problem

We consider a simple modification of the classic tiger problem [Kaelbling et al., 1998] that we refer to as the continuous observation tiger (CO-tiger) problem. In the CO-tiger problem, the agent is presented with two doors, left (L) and right (R). One door has a tiger behind it (S = {Tiger L, Tiger R}). In the classic problem, the agent can either open one of the doors or listen, and the CO-tiger problem has an additional wait action to illustrate the suboptimality of QMDP estimates (A = {Open L, Open R, Wait, Listen}). If the agent opens a door, the problem terminates immediately; If the tiger is behind that door, a penalty of -10 is received, but if not, a reward of 10 is given. Waiting has a penalty of -1 and listening has a penalty of -2. If the agent waits or listens, a noisy continuous observation between 0 and 1 is received (O = [0, 1]). In the wait case, this observation is uniformly distributed, independent of the tiger's position, yielding no information. In the listen case, the observation distribution is piecewise uniform. An observation in [0, 0.5] corresponds to a tiger behind the left door and (0.5, 1] the right door. Listening yields an observation in the correct range 85% of the time. The discount is 0.95, and the terminal depth is 3.

The optimal solution to this problem may be found by simply discretizing the observation space so that any continuous observation in [0, 0.5] is treated as a Tiger L observation, and any continuous observation in (0.5, 1] is treated as a Tiger R observation. This fully discrete version of the problem may be easily solved by a classical solution method such as the incremental pruning method of Cassandra et al. [1997]. Given an evenly-distributed initial belief, the optimal action is Listen with a value of 4.65, and the Wait action has a value of 3.42. The QMDP estimate for Wait is 8.5 and for Listen is 7.5.

While the CO-tiger problem is too small to be of practical significance, it serves as an empirical demonstration that POWSS converges toward the optimal value estimates and that POSS converges toward the QMDP estimates. In fact, the QMDP estimates generated by POSS are suboptimal in this example and lead to picking the suboptimal Wait action. Both POWSS and POSS were implemented using the POMDPs.jl framework, [Egorov et al., 2017] and opensource code can be found at https://github.com/JuliaPOMDP/ SparseSampling.jl.

7.2 Results

The results plotted in Fig. 2 show the Q-value estimates of POWSS converging toward the optimal Q-values as the width C is increased. Each data point represents the mean Q-value from 200 runs of the algorithm from a uniformly-distributed belief, with the standard deviation plotted as a ribbon. The estimates for POSS have no uncertainty bounds since the estimates in this problem are the same for all C.

With C = 1, POWSS suffers from particle depletion and, because of the particular structure of this problem, finds the QMDP Q-values. As C increases, one can observe that both bias and variance in the Q-value estimates significantly decrease in agreement with our theoretical results, while POSS continues to yield incorrect estimates.

Some estimates by POMCPOW are also included. These are not directly comparable since POMCPOW is parameterized differently. For these tests, the double progressive widening parameters ko = C, αo = 0 were used to limit the tree width, with n = C 3 iterations to keep the particle density high in wider trees (see Sunberg and Kochenderfer [2018] for parameter definitions). POMCPOW's value estimates are strongly biased downwards by exploration actions, but the estimated value for Listen action is much higher than the estimated value for the Wait action, which is too low to appear on the plot. Thus the correct action will usually still be chosen. At C = 41, POMCPOW is about an order of magnitude faster than POWSS.

8 Conclusion

This work has proposed two new POMDP algorithms and analyzed their convergence in POMDPs with continuous observation spaces. Though these algorithms are not computationally efficient and thus not suitable for realistic problems, this work lays the foundation for analysis of more complex algorithms, rigorously justifying the observation likelihood weighting used in POWSS, POMCPOW, and DESPOT-α.

There is a great deal of future work to be done along this path. Most importantly, the theory presented in this work should be extended to more computationally efficient and hence practical algorithms. Before extending to POMCPOW and DESPOT-α, it may be beneficial to apply these techniques to an algorithm that is less conceptually complex, such as a modification of Sparse-UCT [Bjarnason et al., 2009] extended to partially observable domains. Such an algorithm could enjoy strong theoretic guarantees, ease of implementation, and good performance on large problems.

Moreover, the proof techniques in this work may yield insight into which problems are difficult for sparse tree search techniques. For example, the R´enyi divergence between the marginal and conditional state distributions (assumption (ii)) may be a difficulty indicator for likelihood-weighted sparse tree solvers, similar to the covering number of the optimal reachable belief space for point-based solvers [Lee et al., 2008].

Acknowledgements

This material is based upon work supported by a DARPA Assured Autonomy Grant, the SRC CONIX program, NSF CPS Frontiers, the ONR Embedded Humans MURI, and the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE 1752814. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of any aforementioned organizations. The authors also thank Lasse Peters for valuable manuscript feedback.