Adaptive Online Packing-guided Search for POMDPs
Authors: Chenyang Wu
Guoyu Yang
Zongzhang Zhang
Yang Yu
Dong Li
Wulong Liu
Jianye HAO
Venue: NeurIPS 2021 Poster (2021)
Keywords: POMDPs
Online Planning
Decision under Uncertainty

Abstract: The partially observable Markov decision process (POMDP) provides a general framework for modeling an agent's decision process with state uncertainty, and online planning plays a pivotal role in solving it. A belief is a distribution of states representing state uncertainty. Methods for large-scale POMDP problems rely on the same idea of sampling both states and observations. That is, instead of exact belief updating, a collection of sampled states is used to approximate the belief; instead of considering all possible observations, only a set of sampled observations are considered. Inspired by this, we take one step further and propose an online planning algorithm, Adaptive Online Packing-guided Search (AdaOPS), to better approximate beliefs with adaptive particle filter technique and balance estimation bias and variance by fusing similar observation branches. Theoretically, our algorithm is guaranteed to find an $\epsilon$-optimal policy with a high probability given enough planning time under some mild assumptions. We evaluate our algorithm on several tricky POMDP domains, and it outperforms the state-of-the-art in all of them.

A Adaptive Online Packing-guided Search for POMDPs
Chenyang Wu', Guoyu Yang', Zongzhang Zhang'; Yang Yu!:?, Dong Li', Wulong Liu', Jianye Hao"
National Key Lab for Novel Software Technology, Nanjing University, Nanjing 210023, China Pazhou Lab, Guangzhou 510330, China
Nooh's Ark Lab, Huawei Company
{wucy, yanggy Banggyy/llmdee amladda. www.:nj.uuuu..oo.omm (lidong106, liusulong, haojianye) com
edu. en, {zzzhang, yny}@nju. edu. cn,
Abstract
The partially observable Markov decision process (POMDP) provides general framework for modeling an agent's 's decision process with state uncertainty, and online planning plays pivotal role in solving A belief is a distribution of states representing state uncertainty. Methods for large-scale POMDP problems rely on the same idea of sampling both states and observations. That is, instead of exact belief updating, collection of sampled states is used to approximate the belief; instead of considering all possible observations, only set of sampled observations are considered. Inspired by this, we take one step further and propose an online planning algorithm, Adaptive Online nacking-ggiddee Search (AdaOPS), to better approximate beliefs with adaptive particle filter technique and balance estimation bias and variance by fusing similar observation branches. Theoretically, our algorithm is guaranteed to find e-optimal policy with high probability given enough planning time under some mild assumptions. evaluate our algorithm several tricky POMDP domains, and it outperforms the state-of-the-art in all of them. Codes are available at https://github.ccom httppiib..oom..MMMAPAP///AAAOOO
1 Introduction
POMDPs generalize the MDPs by considering the state uncertainty [1]. In MDPs, the agent knows its state exactly. In POMDPs, though an MDP determines the underlying dynamics, the agent cannot access its actual state at each timestep and, instead, receives an observation serving as a clue. order to make decisions in POMDPs, the state uncertainty must be handled. A popular method for tackling the uncertainty is to maintain belief, a distribution on the state space, where the probability a state indicates how possible the agent believes it is. However, computations, which is unaffordable in immense state space. A practical way is to approximate the belief with collection of weighted particles (or samples) and update it with particle filtering [2].
exact belief updating requires ((
Finding an optimal solution for finite-horizon POMDPs or a near-optimal solution for discounted Saanite-horizon POMDPs is proved to be PSPACE-compled [3, 4]. Therefore, online planning, which computes real-time solution, plays a crucial role in solving POMDPs, following for two reasons. The first is that online planning searches for solution for not all possible beliefs but the current belief alone, relieving the computational load significantly. Second, online planning can take advantage of the approximate offline solution and other heuristics to expedite the tree search process.
Online planning algorithms have made substantial progress in solving large-scale POMDP problems [5-9]. These methods approximate the belief with a collection of sampled states instead of updating
*Corresponding Author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

it exactly and consider a set of sampled observations instead of all possible observations. However, the estimation derived by simple belief upproximation methods that have been applied, such as direct sampling and sequential importance sampling [10], have a variance increasing exponentially with searching depth. Besides, naive sampling for observations, either the direct sampling as in [7] or importance sampling as in [9], yields a large variance when the sample size is small. Inspired by this, we take one step further and propose an online planning algorithm, Adaptive Online Packing-guides Search (AdaOPS), to better approximate belief's and better balance estimation bias and variance. It features two innovations, adaptive particle filtering, and belief packing.
The adaptive particle filter is designed for online planning, During the belief updating, it resamples adaptively and adjusts the sample size on the fly according to the dispersion of the belief distribution, which allows achieving high approximation accuracy with only handful of particles.
AdaOPS forms belief packing by merging similar beliefs. Only belief' in the packing are explored, hence the name "packing-guie guided search". Belief packing is meant to balance estimation bias and variance. With the use of belief's in their exact form, it is guaranteed that similar belief's yield a slight difference in their optimal values []]]. We further extend this conclusion to cases where beliefs are approximated by collection of weighted particles and prove that by merging similar beliefs, our algorithm can converge to the e-optimal policy with high probability under some mild assumptions.
2 Background
2.1 POMDPs
An MDP is mathematically defined as a tuple (S, R,,), where S and are the state and action spaces, respectively, and T and I are the transition and reward functions, respectively. 7 E [0, I] is the discount factor. POMDP problem can be seen as an extension to an MDP problem, which introduces two additional components, the observation space O and the observation function Z. At each timestep, instead of observing the actual state as an MDP agent does, a POMDP agent can only get observation according the observation function Z( s s',a) = Pr(o s s², which determines the probability of observing o E O after exccuting action a E AA and reaching state s' e S. The transition function T and observation function Z are sometimes hard to define explicitly. An alternative is the generative model s', "0, + G(s,, a). which implicitly defines the transition and observation distributions by randomly generating possible combination of next state s', observation o, and reward r given state s and action a. The POMDP agent maintains a belief b in states, a distribution on S. and seeks to find a policy x mapping beliefs actions, which maximizes the expected sum of discounted rewards, E ('(,, π (b.)).
2.2 Particle Filters
Bayes filter recursively updates the posterior of the hidden states from a sequence of noisy and incom- plete observations. In POMDPs, this technique is usually used to maintain a belief approximation.
Particle filter [10] is an essential class of Bayes filter, which approximates the belief with collection of weighted particles. {(w,, s;) he] where s; is the i-th particle, and wy is the corresponding normalized weight. Sequential importance sampling (SIS) is widely used particle filtering method. It updates the belief by propagating particles with action a, s ~ T(- s;, a), and reweighting particles with observation o, i.e., w = w, (o s/ a)/p. where p normalizing factor. However, continuously updating weights will lead to sample degeneracy where most particles become impos- sible and have negligible weights. This problem causes the estimation variance of SIS to increase exponentially with depth [10].
In another particle filtering method, sequential importance resampling (SIR), the weight updating is followed by a resampling step, which samples N particles from ((w), se) with probability proportional to the weights, and the weights of the resampled particles are set to be 1/N. Resampling alleviates the sample degeneracy by replicating high-weight particles and dropping low-weight ones. Theoretically, resampling is critical, without which we cannot derive the uniform convergence the time horizon for particle filters [12]. However, frequent resampling induces sample impoverishment, which means that particles' diversity diminished, and the whole collection of particles contains few distinct ones. In practice, resampling is only performed when necessary. A rule of thumb is

---

to resample when the ratio of particle number N to effective sample size (ESS) is greater than threshold, say two. Here, ESS is the sample size required from the true distribution achieve the same sampling error as sampling N samples from the proposal distribution and can be approximately calculated [13, 14]:
ESS
(1)
n==1 W
Intuitively, this strategy ensures that we only resample when the weight disparity is significant.
2.3
KLD-Sampling
Instead of using fixed sample size, [15] proposes KLD- SLD-Sampling for adapting the sample size in particle filters according the dispersion of the posterior distributions. Assuming the true posterior can be represented by discrete piece-wise constant distribution consisting of l different multidimensional bins, it calculates the number of samples needed to ensure that the Kullback-Leibte divergence (KLD) between the approximated distribution and the true distribution is less than an error ( with a confidence level - 1). The number of samples N is given by
k: --11 1 (1-9 - 2
2
2
1) 21 21-1
(2)
9(k
where - is the 7/ quantile of the standard normal distribution. This dynamic strategy ensures approximation quality while uses less particles on average. During the sampling, one should keep track of the number of bins that the approximated distribution occupies and estimate the number of samples needed accordingly.
2.4 Belief Packing
Definition 1 (ō-packing). Let (X, || II) be normed space and Y C X. {1I, .2,..., yn C Y is a 8-packing of Y if minezj Ily: - ツز > 5. The 8-packing number of Y. denoted PY(Y), is the maximum cardinality of any ò-packing of Y.
Remark. If X is totally bounded and Y S X, then we have P²(Y) < oo for all > 0.
belief packing is a special case of 5-packing, where the X the belief space, a probability simplex of [S] 1 dimensions, and the norm || || is the L1 norm, Since a simplex is totally bounded, it follows that the packing number of a belief packing is finite.
2.5 Related Work
The covering number is the minimum number of balls needed to cover the entire space. It is closely related to the packing number and is extensively used identify the complexity of POMDP problems [11, 16-18.. SARSOP [19] is an offline solver which builds an approximate cover of the beliefs space reachable by the optimal policy and performs point-based backup beliefs in the cover. PGVI [17] improves SARSOP by maintaining belief packings and only expanding belief's in the packing. FMP [20] applies the idea of PGVI to online planning and builds a 5-cover of beliefs. Notwithstanding, all these methods only work in discrete state spaces and require enumerating all observations.
Online POMDP solvers mainly include POMCP [5], DESPOT [6], and their variants [7-9]. We will introduce them in terms of approximating beliefs and addressing large observation spaces.
On the belief approximation, DESPOT and POMCP sample from the joint distribution of states and observations and approximate a belief with samples having consistent observations. These methods doomed to failure in large or continuous observation space because the same observation is unlikely to be produced twice. POMCPOW [7] weights particles according to the likelihood, which makes its belief updating close to SIR. Nonetheless, most of its belief's are approximated by merely several particles causing the approximation to be inaccurate. PTF-DPW [7] updates beliefs with SIR particle filters. However, standard particle filters excessively costly. The best performance of PTF-DPW is achieved when the number of particles used is only 20. DESPOT-a [9] and LABECOP [21] approximate beliefs with SIS, which is, explained, ineffective compared to SIR.
On addressing observations, DESPOT and POMCP expand sampled observations, which causes the observation branches explode quickly. POMCPOW and PTF-DPW introduce the progressive
3

---

widening technique [22], which restricts the number of observation branches and gradually relaxes the restriction when a node revisited multiple times. DESPOT-a instead fixes the maximum number of observation branches to be C. However, restricting the number of observation branches inevitably produces extra estimation variance, damaging the performance. LABECOP adopts the lazy belief extraction technique, which always extracts the belief from seratch with the newly sampled observation sequence. This method naturally comes with a higher computational cost.
3 Method
Online planning (Alg. 1) consists of two alter- nating stages, planning and execution. A look- ahead search is conducted during the planning stage to find the best action for the current be- lief. At the execution stage, the algorithm per- forms in the real environment the action found, gets new observation, and updates the belief with a Bayes filter. Then a planning stage fol- lows. AdaOPS follows the general procedure and makes changes in the planning part.
Algorithm 1 General Procedure
Input: initial belief bel
1:
6 <- bel
2: while True do
3: a" + PLANNING(6)
4: Execute action a
5: Receive observation
6: Update the belief with a" and o
3.1 Planning
At each timestep, AdaOPS gradu- ally builds up a belief tree (as shown in Figure 1) consisting of alternating action and belief nodes, of which the root belief by is sampled from the current belief bo using KLD- Sampling. Each belief 6 on the tree is represented by a collection of weighted particles and is an ap- proximation to corresponding true belief b. Note that an approximated belief also corresponds to belief node, and we will not distinguish between them in the following. Sib- ling beliefs on the tree share the par- ticles and differ in the correspond- ing weights. Initially, the belief tree is comprised of the root node alone. series of explorations will then be made, each traversing a path on the tree and expanding new nodes in the meantime. The complete pseudocode of AdaOPS is shown in Appendix A.
Belicf Nockss
Bellef Parking
02
Weightse Particien
Action Nodes
Resimole
111
612
013
A belief tree built by AdaOPS. The sibling beliefs share the same particles and differ in the corresponding weights, forming a belief packing. The blue arrow indicates that similar nodes are merged. Beliefs with nigh-weight disparity will be resampled using KLD-Sampling as the red arrow shows.
Figure 1:
AdaOPS maintains an upper bound u(b, a) and a lower bound l(b, a) of the optimal value for every action node a of belief b. During the exploration, the action a" with the highest upper bound will be chosen (Line 10 in Alg. 2). This strategy ensures that an action branch gets explored only when its upper bound is higher than or equal to the optimal value. AdaOPS also maintains lower and upper bounds, I(b) and ubb). for each belief node b. After choosing the action, it will choose (Line 11 in Alg. 2) the child belief with the highest wreiabelity-wiihheed excess uncertainty (EU) [6, 23], p(o b, a" (UT()) a", ,0)), where ý(o b, a²) is an estimation of the probability Pr(o b, ), and T(b a", 0) is the belief reached after executing a" and receiving The way to estimate Pr(o b, a*)
is stated in Section 3.2. The excess uncertainty is defined as
EU(b) = (b) ((b) - E (u(bi) 1(bo))/² depthh(6)
where E is a parameter for adjusting the desired gap between upper and lower bounds at the root and defaults to 0.95, and (b) is the depth of belief b on the belief tree. The excess uncertainty measures how much uncertainty we need to eliminate at the belief node b if we want the gap at the root, ((bb)) to be reduced to &. (u(bp)) (o((6)))((()))) I(bo)). The excess uncertainty has desirable property: (U) < Eveo,.. p(0 i, a" (EU(((b a" ,o),, where 0b,a- is the set of expanded observations

---

Algorithm 2 PLANNING(6))
1: by KLDD-SAPPLING(H))
2: while time permitting and 1(bo) < u(bn) do
3: 5 + bo
4:
while depth(6) < DD do
5:
if b is leaf node then EXPAND(b) BACKUP(b)
6:
7:
8:
if best action branch changes for some ancestors of b or EU(b) S 0 then break
9:
10:
a² < arg max u(b, a)
11:
0" +- arg max, P(o b, (,))EU(r(E,a", ,0))
12:
- ((b,a","")
13:
if (b) > D then
14:
ubb) 6 1(b)
15:
return arg ma ((b0, a)
under the action branch a" of belief b. So, we can reduce the excess uncertainty on b by reducing the excess uncertainty on its child beliefs. Note that minimizing the excess uncertainty on the root belief is equívalent to minimizing u(bo) -(bo).
Each time leaf node is encountered (Line 6 in Alg. 2), all valid actions will be tried with new helief nodes expanded. For new belief nodes, the lower and upper bounds will be initialized with heuristics. This process of expanding leaf nodes is detailed in Section 3.2, After expanding leaf node, backup will be performed (Line 7 in Alg. 2) to update the bounds of ancestor nodes, which is realized by recursively applying the Bellman equation:
U(b) max U(b,a) max {S b(s) / Pr(o b, (r))
(4)
(b) max Σ .ES b(s) + Eoco, p(o b (01,,))((((.,.0))
where (b) and Ub, a) can be either upper or lower bound of the optimal value, b(s) E, s)me; is the probability of state 8 estimated by the weighted particle collection of belief b, and I(()) is the indicator function. After backup, the upper bounds of ancestor nodes tend decrease, approaching the optimal value. According to Equation (4), the upper bound of a belief node is only determined by its best action branch, i.e., the action branch with the highest upper bound. Therefore. the best action branch changes for some ancestor nodes during the backup due to the decreasing of the upper bound, expanding the current branch will longer decrease the upper bound of the root. In this case, AdaOPS will end the exploration and restart from the root node (Line 8 in Alg. 2). The exploration will also end if the excess uncertainty is less than or equal to 0 since we want to focus on branches with high uncertainty. Moreover, if belief exceeds the maximum depth D (Line 13 in Alg. 2). its upper bound will be its lower bound as prevent further searching.
With the process of explorations, the bounds on the root will progressively approach the optimal value. Nevertheless, the planning time is often not adequate for it converge. When the allocated time is up, the highest lower-bound action at the root belief will be chosen for execution.
3.2 Expanding Leaf Nodes
During the expansion of leaf nodes, AdaOPS first checks if the resampling condition is met (Line 1 in Alg. 3). If does, AdaOPS performs the KL.D-Resampling [24], which means we apply the KL.D-Samllig method to the resampling procedure. Then, for each action A, AdaOPS will propagate particles in belief 6 with a generative model (Line 4 in Alg. 3). This process is further discussed in Section 3.2.1. Particle propagation will produce set of sampled observations and their corresponding beliefs, Bra,, the average reward Rs for performing action at belief b, and an estimate p( b, for the probability Pr(o b, a). With the sample observations, AdaOPS generates
5

---

belief packing (Line 5 in Alg. 3), Pb.a described in Section 3.2.2. Finally, all beliefs in the belief packing will be expanded to the belief tree, and their upper and lower bounds will be initialized with some value approximation techniques [25], which are outlined in Appendix B.
3.2.1 Adaptive Particle Filter
According to Equation (4), we need to approximate beliefs accurately so that the estimation for the first integral Is ((s) a) = Egss ((s) a) is accurate. However, in online plan- ning, we cannot afford tons of particles for belief approximation and need a par- ticle filter that works well with merely few particles. That is why we intro- duce the adaptive resampling (Lines 2 in Alg. 3) and the KIDD-Samllig method. When the sample size is small, the particle impoverishment issue will be prominent, which can be alleviated with adaptive resampling. Moreover, LLD-Sampling ensures the approxima- 3: Sample N particles in belief b
Algorithm 3 EXPAND(b)
1: if (B)/ESS(0) > / then
2:
b+ (LDD-SMMPLING())
3: for E do
Bg ai p( b, t- PROPAGATE(B, a)
5:
Pr.a + GENERATEPACKING
D( b,a))
6: Expand action node
7: Expand beliefs in Po.a as child beliefs of
Algorithm 4 LLD--AMPPINGGÓ)
1: Count the number of bins with support for belief b Calculate the number N satisfying Equation (2)
tion quality while using fewer particles.
AdaOPS performs the KLD- DLD-Resampling adaptively (Lines 1-2 in Alg. 3) when the particle number of the leaf belief b is greater than Eb)( where f4 2 1 adjusts the frequency of resampling and is set to throughout the paper. According to Equation (1), low effective sample size indicates a high level of weight disparity. It is also illustrated in Figure that AdaOPS resamples when the weight disparity of belief is high. In order to determine the particle number for resampling, the state space is partitioned into grid (described in Appendix D.2, Figure 5). Then, we can count the number of bins occupied by belief b and calculate the particle number for resampling with Equation (2). The hyperparameter 1) is set to be 0.05, and the is tuned such that Mmin is the minimal number
satisfying Equation (2) when & = 2, i.e., < 2miin (1 (1- 3 + (22.995) where Main is another hyperparameter representing the minimum number of particles needed for approximating the belief.
Algorithm 5 PROPAGATE(Ó a)
O - 0, B 25, +- 0, <-
2: Initialize b as an empty weighted particle collection
3: for (w, do
4: d', G(s,a)
5: b (+bu((u,ss)) (0 ou R R+ wr
6:
f(o)
7:
for o E do
8:
Initialize D' an empty weighted particle collection
9:
for (w, s') b do + B (',(o//'
10:
D Em 2oo 8))
11: B+BU
12:
return B, R.P
For each action a E A, AdaOPS propagates all particles (wi, of through a generative model, i.c., s o4, + G(s,, a) (Line in Alg. 5) and calculates the average reward, R. >E way, (Line in Alg. 5). We estimate the probability of generating an observation o, Pr(o b,a), by the sum of weights of particles generating it (Line 6 in Alg. 5), i.e., Pr(o b,a) R p(o b, a) Σ, I[ = oz)w,
The belief 7b, a, o) for sampled observation is approximated by the same collection of particles but assigns different weight for each (Line 10 in Alg. 5). The weight for the i-th particle under

---

Optimal Value
(a)
Optinal Value
(b)
Probability
Probrobiiltty
20-
10
0.7
0
6
6
10
Observation
Observation
Figure 2: The solid orange line stands for an observation distribution Pr(- 6, a) distributed between
0 to 10. The dashed blue line illustrates the optimal values of observations, (r a, -)). (a) shows 10 samples from the observation distribution, forming unbiased estimator for the first integral in Equation (4). Nonetheless, this estimator has a high variance since the sample size is too small. (b) shows 50 samples from the observation distribution. By building belief packing, only 10 dissimilar beliefs having distinct optimal values are retained for evaluation. Each solid red line the figure corresponds to belief in the packing. The values of beliefs on the line are set to the value of the corresponding belief in the packing. By doing so, we obtain a low variance estimator with slight bias at the cost of 10 evaluations.
observation is w m: ( 5/, a/pa where p = E, w; Z 64,0) is normalizing factor. The set of sampled observations and their corresponding beliefs is denoted as Bg,a"
3.2.2 Belief Packing
Equation (4) reveals that we can approximate the integral So Pr(o b, (r o) with
Algorithm 6 GGNNERATEPACKINGGG
the value of some sampled observations. The
1: P +
more observations we sample, the lower the es- timation variance is. However, each sampled ob- servation corresponds Suppose we expand all observations in Bi,a as new branches, the induced branching factor is often beyond our computational capability. Nev-
2: for (o, B do
3: covered <- false
observation branch.
4: for (o' b¹) E do
5:
if 88 b|| < 8 then
6:
p(o') + p(o') p(o)
7:
(())= + 0
ertheless, restricting the number of observations 8: renders high estimation variance. Inspired by [16-18], we introduce belief packing to fuse
covered + true break not covered then
9:
10:
similar beliefs and only evaluate the distinct 11:
P PU ((o
ones, balancing estimation bias and variance.
12:
return P
Since the sibling beliefs and D' share the same particles, we can calculate their L1 distance with [
((s))-((s){ = E; |w;- - w//l where w, and w are the weights of the i-th particle for beliefs b and 8' respectively. As will be shown in Lemma 1, when the belief approximation is accurate, and the L1 distance between two approximated beliefs is small, the true optimal value are also close. In other words, it safe fuse similar beliefs. The formal convergence analysis given in Theorem
In AdaOPS, belief packing is maintained under each action branch of belief b as illustrated in Figure 1. We merge two observation branches when their beliefs are within a distance of (Line 5 in Alg. 6). Specifically, if the distance between by in the packing and b2 is within 6, we set p(01 b, a) + f(00 bb a) + p(02 b, a) and p(02 b, a) <- 0 for their corresponding observations or and 02, which is equivalent to approximate the value of by with that of by If the belief by is not covered by any 5-ball centered at beliefs in the packing, then we add to the packing (Line 10 in Alg. 6).
As shown Figure 2, by setting the value of a belief to that the closest belief in the 6-packing, we obtain piece-wise constant approximation to V* (r((r,, a,.)) which avoids evaluating V*(+) at similar beliefs at the cost of introducing limited bias.
4 Theoretical Analysis
This section demonstrates some theoretical results and provides some insights on why and when AdaOPS works. The proof, along with running time analysis, is detailed in Appendix C.
7

---

Assuming the reward function is Borel measurable and bounded, we denote Rmax - || It already proved in [11] that the value function of POMDPs satisfies the Lipschitz condition, i.e. [V(6) ((b) < 1 6, if ||b - 6' 1 S 8. We present another theorem extending this conclusion to the case where we only have access sets of weighted samples approximating the beliefs.
Lemma 1. By assigning the same set of N samples different weights, we get b(s) E w;
s4) and (s) = Ei= will(s = 51) approximating beliefs and 6. There exist bounded functions a and a' such that (b) = {())((()) ds, and (b') ) a''(s)b ds. Supposing that ||6 - 8'|l s N 5. (b) Σnn (x)(ss)) s X, and (V*()) Eim u (s.)l I X, it follows that
Rmux
(- - V- 2A+
(5)
1-7
This result indicates that merging similar beliefs works well when the approximated beliefs are indeed good approximations to the original beliefs.
In the following, we will present the convergence analysis of AdaOPS. In other words, we will bound the difference between the real optimal value Vi (by) of the current belief by and the estimated optimal value (bp) of the root belief bp. As the resampling will cause the particles to be interrelated and significantly increase the difficulty of analysis, we follow the proof in [26] and disables the resampling for now. The effectiveness of the adaptive particle filter is empirically demonstrated in Section 5.2. Our convergence analysis is built upon the following assumptions:
1. The ESS threshold y for adaptive resampling is set co.
2. The reward function is Borel measurable and bounded.
3. The upper bound of AdaOPS is initialized to +oo. Its lower bound is initialized with any function bounded by 1-y"
Rmax
4. The state and observation spaces are continuous, and the action space is finite.
5. For all d E 10....... D - 1} and all observation sequences fon), the essential supremum of the importance weight ess supz~0" Wpd (on)) (om) / (zr is upper bounded by dmaxx where
(p/e(x))
Piz) "()
Theorem 1. Suppose that all assumptions listed above hold. Let N |bol Minin- For 0, IV (bo) V. (bo)) Se
(6)
holds with probability of at least
15| min(N, pd 1) exp (-N maxx)
where Imax sups,a pô p²(Y,,a) and Yi,a is the set of reachable beliefs after executing action a at belief
(1-21A
N 8 =
(1-7)'
(1-7)e D = log, ORmax max 3(+6-/23
(1-7)e pó
Bmaxe Craac
3-y
The sample size N in Theorem I is at an order of Ô logarithmic part. Since the term dyuxx can increase exponentially could scale poorly, highlighting the importance of eafple-efficient belief approximation.
n2 Chaan (I-T)
where the tilde means to omit the
the depth D, the sample size
The benefit of belief packing is not evident from the convergence result. In fact, it affects the performance by controlling the tree size. AdaOPS builds tree of size O((IA) min( Paax N)ax)) where Nmax is the maximum sample size given by KLD-Sampling. For discrete state spaces, the maximum packing number p8 Paxx is always finite and will not increase w.rt. depth D. Although this may not hold in every continuous state problem, belief packing still shows great potential empirically.
5 Experiments
This section evaluates our method on four domains based on the POMDPs.jI framework [27] and conducts an ablation study showing the contribution of each component. Besides, we compare the adaptive particle filter with other particle filter variants demonstrating that the adaptive particle filter can approximate the belief better.
8

---

5.1 Performance Comparison
In what follows, we compare AdaOPS with DESPOT [6] and POMCPOW [7] on four domains, Laser Tag [6], Rock Sample (RS) [23], Roomba [28], and Light Dark [7]. These domains are carefully chosen so that they can cover various types of POMDPs. The details of these domains are shown in Appendix D.1. In order to understand the contribution from adaptive resampling (AR), KLD- Sampling (KIDD-S), and belief packing (BP), respectively, we remove one component at time and tune the hyperparameters to achieve the best performance for others. Specifically, the removal of adaptive resampling means we resample at each timestep as a standard particle filter does.
5.1.1 Experiment settings
In all these tasks, solvers are allocated 1s for planning per step. Since the obstacle positions in Laser Tag and the rock positions Rock Sample greatly influence the optimal value, tests on these domains are conducted with one hundred randomly generated maps so that the result is trustworthy, Hyperparameters for each algorithm are tuned via grid search, and another independent experiment conducted to test their performance. DESPOT and AdaOPS initialize upper and lower bounds with heuristics, and POMCPOW evaluates nodes it encountered for the first time with a value estimator. All experiments were conducted computer with Intel(R) Core(TM) 17-10750H, 6vCPUs running at 2.6GHz, and 32G main memory. Please refer to Appendix D.2 for the ranges of grid search and the hyperparameters and heuristics selected for each algorithm. Besides, time sensitivity analysis is presented in Appendix D.3.
5.1.2 Results
In Table 1, the average discounted return is shown along with the corresponding standard error of mean (SEM) in the form Return + SEM. In all these domains, AdaOPS outperforms other solvers with statistical significance (p < 0.0001). A hyperparameter sensitivity analysis in Light Dark is
presented in Appendix D.4.
Table 1: Performance Comparison
Laser Tag
RS(15,15)
Bumper Roomba
Lidar Roomba
Light Dark
4, 830
7,372 800
00
oo
L
5 1.5 10
20
9
3
O
3
2
DESPOT
-10.71 + 0.22
15.67 + 0.20
-2.18 + 0.11
-0.84 + 0.06
2.50 + 0.10
POMCPOW
-10.15 1 0.17
10.40 1 0.18
-228 1 0.09
0.50 -1: 0.07
3.23 1: 0.11
AdaOPS
-8.31 + 0.18
17.16 + 0.21
-1.48 + 0.11
-0.09 + 0.07
3.79 + 0.07
AdaOPS(AR)
-8.79 17990.11 0.17
16.73 = 0.21
-.163
-0.21 = 0.06
3.62 + 0.07
AddOPS(KLD-S)
0.19
-1171
-..0 + 0.07
3.72 + 0.07
AdaOPS(BP)
-9.84
17.10 = 0.21
-0.51 + 0.07
1.50 + 0.20
Note: RS(nm) stands for the Rock Sample with map and jocks. continuous observation) space.
AdxOPS(XX) denotes AdaOPS without component XX. Adaptive Resampling, KLD-S KLD-Sampling BP Belief Packing.
Laser Tag In Laser Tag, agent tries to tag an escaping target. Initially, the agent knows nothing about its own position and the target's position, and the belief is spread over the entire grid. It can then access the map and infer the positions from the sensor information. After several steps, the belief will shrink into a small region. Since the dispersion of beliefs varies considerably, the KI.D-Sampling is advantageous. The adaptive resampling avoids sample impoverishment and contributes equally with -aamplnng The belief packing contributes most by allowing AdaOPS handle massive observation space effectively.
Rock Sample In Rock Sample, a Mars rover intends to sample as many good rocks as possible while only inferring the goodness of rocks from its noisy sensor measurements. It maintains belief of the goodness for each rock, which is always comprised of two bins, good and bad. Thus, the particle number given by Equation (2) is always miin. i.c., KLD-Sampling makes difference in

---

Roomba Roomba is a robotic vacuum cleaner that attempts to locate itself in a familiar room and Lidar sensor the Rock Sample problem. Besides, belief packing is also unproductive since there are only two observations. The improvements of AdaOPS mainly come from the fact that AdaOPS maintains an accurate belief approximation in the depth of the tree using particle filter techniques. Contrarily, DESPOT and POMCPOW tend be overoptimistic on future uncertainty.
reach the target region. can equip either a Bumper sensor that senses the collision that measures the distance to the obstacle in the front. As state is either collided or not, the belief's corresponding different observations in Bumper Roomba always have an L1 distance 2, which means there are no similar beliefs, and belief packing is of little avail in this case. However, in Lidar Roomba, belief packing handles continuous observation gracefully, making significant contribution. The KLD-Samp LLD-Sampling fails to contribute much as expected in the Roomba domain. A possible reason is that according to Equation (2), high state uncertainty comes with a large number of particles and, consequently, observations, making online planning extremely hard given limited planning time. The above analysis is corroborated by an additional result presented in Appendix D.5.
Light Dark Light Dark is an information gattiiiin task. With the aim of reaching the target area, the agent needs to find its way the light region, gathering intelligence. This requires the agent be fully aware of the state uncertainty while factoring in all possible observations. The belief packing empowers AdaOPS consider only distinct observations. On the KLD-Sampling, the problem in Roomba also occurs in Light Dark, resulting in little improvement.
5.2 Benefits of Adaptive Particle Filters
We present comparison between different particle filters on the Laser Tag domain, in- cluding SIS, SIR, and Adaptive particle fil- ter. Each particle filter is given the same sequence of action-observation history for belief updating. The approximation error (measured by total variation distance) is checked after 10 steps. As illustrated in Fig-
SIS Particle Filter Particle Adaptive Particie Filtor
Total Vartation Distance
0.6
0.4
3, the adaptive particle filter gets the lowest approximation error and the lowest variance using the same amount of parti- cles. This result supplements the conver- gence analysis in Section 4 since a better approximation of beliefs will not undermine the convergence.
0.2
0.0 200
400
600
500
1000
Average Particle Number
Figure 3: The belief approximated via the adaptive particle filter is the closest to the real posterior, using the same amount of particles.
6
Discussion
This paper presents an online planning algorithm, AdaOPS, featuring adaptive particle filter and belief packing, which is able to solve most POMDP problems optimally, given enough planning time. The success of the adaptive particle filter points out that in previous methods [6. 7]. the inaccurate belief updating is detriment to the performance, outweighing the potential benefit of efficiency. Furthermore, is demonstrated that forming a belief packing with approximated beliefs is an effective tool for handling large observation spaces. We believe it could find itself extensive use in POMDP planning.
The size of the tree AdaOPS built could go unmanageable when |A] and pá max are large. Though it caused by the complexity of the problem itself [11], J, we can abate this problem by implementing a parallel version following [8]. Furthermore, it is possible to improve the search efficiency with sawtooth approximation [25] and alpha vectors as described in [9]. We will also explore the possibility
of handling large-scale or continuous action spaces.
10

---

Acknowledgements
We thank Haoran Xiang, Dongyu Guo, Weijian Liao, and Feng Xu for helpful discussions and support in this project. This work was in part supported by the NSFC (618761 19), the Fundamental Research Funds for the Central Universities (0221 14380010), Huawei Noah's Ark Lab (HF2019105005), and Alibaba Group through Alibaba Research Fellowship Program.
References
[1] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, "Planning and Acting in Partially Observ- able Stochastic Domains," Artificial Intelligence, vol. 101, no. 1-2, pp. 99-134, 1998.
[2] M. J. Kochenderfer, Decision Making Under Uncertainty: Theory and Application. MIT press, 2015.
[3] C. H. Papadimitriou and J. N. Tsitsiklis, "The Complexity of Markov Decision Processes," Mathemalics of Operations Research, vol. 12, no. 3, pp. 441-450, 1987.
[4] O. Madani, S. Hanks, and A. Condon, "On the Undecidability of Probabilistic Planning and Related Stochastic Optimization Problems," Artificial Intelligence, vol. 147, no. 1-2, pp. 5-34, 2003.
[5] D. Silver and J. Veness, "Monte-Carke Planning in Large POMDPs," in NIPS, pp. 2164-2172 2010.
[6] N. Ye, A. Somani, D. Hsu, and W. S. Lee, "DESPOT: Online POMDP Planning with Regular- ization," Journal of Artificial Intelligence Research, vol. 58, pp. 231-266, 2017.
[7] Z. N. Sunberg and M. J. Kochenderfer, "Online Algorithms for POMDPs with Continuous State, Action, and Observation Spaces," in ICAPS, pp. 259-263, 2018.
[8] Cai, Y. Luo, D. Hsu, and W. S. Lee, "HyP-DESPOT: A Hybrid Parallel Algorithm for Online Planning under Uncertainty," in RSS, 2018.
[9] N. Priyadarshini Garg, D. Hsu, and W. Sun Lee, "DESPOT-Alpha: Online POMDP Planning with Large State and Observation Spaces," in RSS, 2019.
[10] A. Doucet and A. M. Johansen, "A Tutorial Partiele Filtering and Smoothing: Fifteen Years Later," Handbook of Nonlinear Filtering, vol. 12, no. 3, pp. 656-704, 2009.
[11] D. Hsu, S. Lee, and N. Rong. "What Makes Some POMDP Problems Easy to Approximate?," in NIPS, pp. 689-696, 2007.
[12] P. Del Moral, A. Doucet, and A. Jasra, "On Adaptive Resampling Procedures for Sequential Monte Carlo Methods," Bernoulli, vol. 18, no. 1, pp. 252-278, 2012.
[13] L. Kish, Survey Sampling. John Wiley & Sons Inc, 1965.
[14] S. Liu, Monte Carlo Strategies in Scientific Computing. Springer Science & Business Media, 2008.
[15] D. Fox, "KLD :amplign Adaptive Particle Filters," in NIPS, pp. 713-720, 2001.
[16] Z. Zhang, M. Littman, and X. Chen, "Covering Number as A Complexity Measure for POMDP Planning and Learning." in AAAI, pp. 1853-1859, 2012.
[17] Z. Zhang, D. Hsu, and W. S. Lee. "Covering Number for Efficient Heuristic-based POMDP Planning," " in ICML, pp. 48 60, 2014.
[18] Z. Zhang, Q. Fu, X. Zhang, and Q. Liu, "Reasoning and Predicting POMDP Planning Com- plexity via Covering Numbers," Frontiers of Computer Science, vol. 10, no. 4, pp. 726-740, 2016.
[19] H. Kurniawati, D. Hsu, and S. Lee, "SARSOP: Efficient Point-based POMDP Planning by Approximating Optimally Reachable Belief Spaces.," in RSS, 2008.

---

[20] D. Grover and C. Dimitrakakis, "Adaptive Belief Discretization for POMDP Planning," arX1v:2104.07776 [es], Apr. 2021.
[21] M. Hoerger and H. Kurniawati, "An On-Line POMDP Solver for Continuous Observation Spaces," in ICRA, 2021.
[22] A. Couëtoux, J.-B. Hoock, N. Sokolovska, O. Teytaud, and N. Bonnard, "Continuous Upper Confidence Trees," in LION, 2011.
[23] T. Smith and R. Simmons, "Heuristic Search Value Iteration for POMDPs," in UAI, pp. 520-527, 2004.
[24] Li, S. Sun, and T. P. Sattar, "Adapting Sample Size in Particle Filters through KLD- Resampling," Electronics Letters, vol. 49, pp. 740-742, June 2013.
[25] M. Hauskrecht, "Value-Function Approximations for Partially Observable Markov Decision Processes," " Journal of Artificial Intelligence Research, vol. 13, pp. 33-94, 2000.
[26] M. H. Lim, C. Tomlin, and Z. N. Sunberg, "Sparse Tree Search Optimality Guarantees in POMDPs with Continuous Observation Spaces," in ICCAI, pp.
2020.
[27] M. Egorov, Z. N. Sunberg, E. Balaban, T. A. Wheeler, J. K. Gupta, and M. J. Kochenderfer, "POMDPs.jl: A Framework for Sequential Decision Making under Uncertainty," Journal of Machine Learning Research, vol. 18. no. 26, pp. 2017.
[28] K. Menda, Sunberg, and M. Kochenderfer, "RoombaPOMDPsji. https//giitub..om//ss// RoombaPOMDPs.j. 2021.
[29] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, "Learning Policies for Partially Observable Environments: Scaling Up." ICML, pp. 362-370, 1995.
12


Reviews:
[{"review_id": "rpLCIg_JwkG", "reviewer": "Reviewer_7fyM", "summary": "This paper proposes an online POMDP algorithm that performs belief tree search to find an action for current belief at each step. Building on the HSVI algorithm and more recent works using Monte Carlo belief tree approximations, the paper leverages on two ideas to achieve better performance: KLD sampling for more accurate belief representation, and the idea of belief packing to combine observation branches. The algorithm seems to have strong performance on several benchmark problems. A theoretical analysis is given.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Belief representation and control of observation branching factor are two important considerations in the design of belief-tree based POMDP solver's performance. This paper proposes leveraging on the ideas of KLD-sampling and belief packing, and demonstrates that these two ideas work well on several benchmark datasets.\n\nThe paper is generally well-written and easy to follow, but discussion on related works should be in the main text rather than in the supplementary materials. The algorithm is an interesting combination of several ideas, which seem to be sound and effective in practice.\n\nA theoretical analysis is given for a reduced version of the algorithm (without resampling), but it seems that there are a few limitations that are not discussed.  Theorem 1 shows that if two estimated beliefs are similar, then the estimated value for one is a good approximation to the true value of the other, provided that each estimated belief is represented by sufficiently many particles. \n- It'd be helpful to discuss the magnitude of the sampel size $N$. Currently $N$ is related to other parameters in a complex inequality, and it'd be helpful to show $N$ grows as other parameters grow.\n- It will be helpful to discuss on both the definition and the magnitude of $d_{\\infty}^{\\max}$, which is defined as the \"essential supremum of the Rényi divergences between the sampling and target distributions\". The \"sampling and target distributions\" seem to refer to the estimated beliefs and true beliefs. If that's the case, the analysis seems to focus on the discrete case only otherwise the Rényi divergences will be undefined. In addition, it seems $d_{\\infty}^{\\max}$ can be bounded in terms of the transition model and the observation model, and some discussion on the magnitude of $d_{\\infty}^{\\max}$ will help understanding the required sample size for good approximation.\n- It is also not clear whether the analysis takes the errors due to belief packing into account. The first term in the bound seems to take the belief packing error at the current belief into account, but errors arising due to belief packing for descendant belief nodes doesn't seem to captured anywhere. \n- The notation $\\hat{V}^{*}$ isn't defined anywhere, but it seems to be the same as $V^{*}_{\\text{AdaOPS}}$ in Theorem 2, which denotes the estimated optimal value given by AdaOPS.\n- Theorem 2 sets $N$ to $m_{\\min}$, but $m_{\\min}$ is a hyperparameter that doesn't depend on the required value function error and the confidence level. How is it possible to have such a universally good sample size?\n\nOverall, the proposed algorithm has some interesting ideas and seem to have good empirical performance, but it seems that the theoretical analysis has a few limitations. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The theoretical analysis seem to have a few limitations that are not discussed. See the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Iny-Kld7y5l", "reviewer": "Reviewer_g6M6", "summary": "This paper presents an online planning algorithm, called Adaptive Online Packing-guided Search (AdaOPS), for Partially Observable Markov Decision Processes.\nThe article addresses the problem of improving the approximations of a belief using a particle filter. This improvement comes from two elements: adaptive particle filtering and belief packing.\n\nSpecifically, During the planning step, a particle resampling procedure is performed adaptively on new leaf nodes.\nThis happens when the number of particles in the belief of the node is greater than twice the Effective Sample Size (ESS), as explained in (Kish [11], Liu [12]).\nAdaOPS use a KLD-sampling for this adaptive resampling (Fox [13], Li, Sun, Satter [15]), this guarantees a good approximation using a limited number of particles.\n\nThe article also presents a technique called Belief Packing, inspired by (Zhang, Hsu, Lee [17]).\nIt is used to fuse similar beliefs, thus the planning procedure explores only beliefs that are significantly different.\nThis improves the scalability of the online algorithm.\n\nThe paper shows that with enough planning time, this packing produces results that are $\\epsilon$-optimal (i.e., the difference between the original belief and the belief that employs the packing is lower than a constant $\\epsilon$ with a probability of at least $1 - \\eta$).\nThe article also presents an empirical evaluation of AdaOPS in four different domains (Laser Tag, Rocksampe, Roomba, and Light-Dark). The results show that AdaOPS can outperform state of the art planning algorithms (POMCPOW, ARDESPOT).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses an important problem, namely, improving the approximation of a correct belief using particle filters and this is achieved by combining different techniques.\nEach technique, by itself, does not provide an original contribution, but the non-trivial combination of such techniques is an interesting and valuable contribution.\nIn this regard, I believe that the paper should discuss in more detail why combining adaptive particle filters and belief packing is beneficial with respect to considering the two techniques independently.\n\nThe main theoretical proof presented in the article concerns the convergence to an optimal policy given enough planning time.\nThe proof is, as far as I understand, correct, but it is not clear to me how fast this convergence is (i.e., is this result useful in practical applications ?).\n\nThe empirical evaluation section considers four domains and presents a comparison of the performance achieved by AdaOPS with two state-of-the-art planning algorithms. In each instance, solvers have 1 second for planning a step.\nI find this experimental setup incomplete.\nThe main theoretical proof presented in the article concerns the convergence to an optimal solution given enough time, but the impact of this result is not explored empirically.\nIn particular, it is not clear how fast and reliable this convergence is. \nUsing 1 second for step is a reasonable choice, but it should not be the only one considered.\nIt could be that AdaOPS performs very well with constrained resources but it is outperformed by other algorithms when the planning time is shorter or longer. This may still be a valuable result for AdaOPS but should be clearly discussed to better define in which situation it is beneficial to use AdaOPS.\nI point this out because the performance achieved by POMCP in Rocksample in this scenario seems low compared to my expectation. I believe that with more resources POMCP can achieve a greater reward, is AdaOPS still significantly better in other cases?\n\nThe paper is well written, but I find the usage of the appendix excessive. This makes the paper hard to follow. In particular, the main paper should present a brief description of the proofs for theorems 1 and 2. Similarly, the short discussion of the size of the generated tree should be moved from section 6 to section 4.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors indicate that they do not see potential negative societal impacts with their work and I agree.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "30"}, "extra_text": {}}, {"review_id": "8-asTU7zyOp", "reviewer": "Reviewer_abPZ", "summary": "This paper presents an online method for approximately solving POMDPs, called AdaOPS. The method combines several known techniques for belief-tree construction and sampling. Specifically, it maintains upper and lower bound and uses the highest upper bound for action selection and weighted excess uncertainty for observation selection. It uses weighted particles to represent beliefs and use the weights together with KLD for resampling to improve belief estimates. It then uses belief packing to aggregate values of nearby beliefs. The methods are tested on four benchmark problems and indicate better performance compared to DESPOT and POMCPOW. Convergence results that expand the work in [18] are also presented.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper presents an online method for approximately solving POMDPs, called AdaOPS. The method combines several known techniques for belief-tree construction and sampling. Specifically, it maintains upper and lower bound and uses the highest upper bound for action selection and weighted excess uncertainty for observation selection. It uses weighted particles to represent beliefs and use the weights together with KLD for resampling to improve belief estimates. It then uses belief packing to aggregate values of nearby beliefs. The methods are tested on four benchmark problems and indicate better performance compared to DESPOT and POMCPOW. Convergence results that expand the work in [18] are also presented.\n\nI think the method is a relatively non-trivial combination of known components, though the components themselves and their applications to generating POMDP policies have been used in other solvers. In particular:\n*/ The use of upper bound and weighted excess uncertainty are relatively common in POMDP solvers (as cited, [5, 14] have used them too). \n*/ The use of KLD-sampling from particle filter[13]  to help identify the number of particles that need to be sampled in a sampled-based POMDP solver is new. Though, the idea of exploiting SIR techniques from particle filter to improve belief estimates without unnecessarily increasing the number of belief samples have been proposed in \"M. Hoerger and H. Kurniawati. An On-Line POMDP Solver for Continuous Observation Spaces. ICRA 2021.\".\n*/ The idea of belief packing to aggregate values have also been applied in a POMDP solver since awhile back, albeit in an offline solver (\"H. Kurniawati,  D. Hsu, and W. S. Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. RSS 2008.\").\n\nKLD-sampling can be used to incrementally increase the number of samples without requiring the effective sample size (ESS) nor posterior distribution to be computed. It would be useful to clarify why in the proposed method, there need to be a distinct step where ESS is used to determine whether to run KLD-sampling or not. The potential issue is that to keep computation fast, the ESS approximation used in the paper can actually be quite loose. Elaborating the trade-off between the two could be useful.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As any tools, methods for automated decision-making can be applied for both positive and negative purposes. This is akin to the fact that knife is very useful in our daily life, but of course, can be used for harm. The key is to ensure the application of the method is not used for negative purposes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "3xz3gYZGJ_U", "reviewer": "Reviewer_rLs9", "summary": "This paper proposes an online tree-search algorithm for partially observable Markov decision processes (POMDPs). Taking sampling-based tree search style (e.g., POMCP) approach as a basis, the paper proposes to employ an adaptive particle filter that tunes the number of samples in each branch of the tree using the KLD-sampling method (Fox, 2001). To prune the search tree, the paper proposes a new method of observation aggregation called belief packing: here, observation branches resulting in similar beliefs (and hence similar values) are aggregated together. The benefits of these ideas applied to online tree search planning are demonstrated empirically.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- The idea of belief packing is an interesting and reasonable alternative to progressive widening and other strategies used to deal with very large observation spaces. In the context of online tree search for POMDPs, this seems to be a novel contribution.\n- The empirical results nicely show cases where it is helpful and where it does not bring additional benefits. The results overall show improvements over DESPOT and POMCPOW, indicating the usefulness of the proposed approach where the requirements of the proposed method can be fulfilled.\n\nLimitations:\n\n1. The main idea is reasonable and seems useful, but is still a modification of the well-known online tree search approach to solving POMDPs. The contribution might be relevant for POMDP practicioners, but may not receive much interest elsewhere.\n\n2. One algorithmic limitation is that to perform resampling, the state space has to be partitioned into a grid. This is unlikely to scale to high dimensional state spaces. Another limitation is the requirement of access to a fully specified observation model for particle reweighting. This makes the setting where the proposed algorithm can be applied more limited than DESPOT and POMCP.\n\n3. The belief packing idea is nice, but it does not seem to be completely developed in the paper. For instance, I was expecting the delta-packing number to make an appearance in the main theorems of the paper. I was not sure if the delta there is to be interpreted as the packing number, or if the two theorems are generic results for particle-based online tree search.\n\n4. I do not appreciate the choice to defer discussion of related work to an appendix. I think this is very useful information to understand the relation of this work to others, and should be included in the main paper.\n\n5. Some parts of the paper are unclear, and the two theorems rely heavily on [17], also for the underlying asumptions, which makes the paper not that self-contained.\n\nI would appreciate comments from the authors especially on points 2 and 3.\n\nDetailed comments:\n\n- The writing in the paper could be improved to make it more accessible:\n* The introduction could motivate the need for the algorithm generally at least a little, instead of the very focused technical POMDP angle taken. \n*Especially Sect. 3 needs improvement, it introduces many concepts and includes many forward references that make following the flow of ideas arduous. The basic algorithm seems very similar to POMCP, although with several modifications, so it might even make sense to explicitly note the differences to POMCP for improved clarity. \n* Also in Sect 3., it would be worthwhile to focus on the main contributions of this paper, and give less emphasis on already known algorithmic ideas.\n\n- Is the Light Dark domain the same as in Table 1 of Sunberg & Kochenderfer (ICAPS 2018)? Or has the reward function been scaled somehow? I am wondering since the reported average performance is quite different.\n\n** The following comments are for the information of the authors only, and do not need to be answered.\n\n- The belief packing idea is a type of observation aggregation into meta observations considered in earlier work, e.g., [2, 3]. Expanding on this connection might give a nice alternative view of belief packing.\n\nMinor:\nLine 22-23: Exact belief updating is possible with parametric distributions in certain continuous-state cases, see, e.g., Kalman filters in linear-Gaussian POMDPs.\nLine 25-26: Papadimitriou & Tsitsiklis only consider the finite horizon undiscounted expected cost case for POMDP. For the infinite horizon case, see [1].\nLine 65: \"average\" --> \"expected sum of\"?\nLine 69: Bayesian filtering is not necessarily approximate, it can also be exact.\nEq. (2): Compared to Fox (2001), this equation is missing the power of three for the term in the parentheses. Same mistake later on Line 208.\n\nReferences:\n[1] Madani et al., \"On the undecidability of probabilistic planning and related stochastic optimization problems\", Artificial Intelligence, Volume 147, Issues 1–2, July 2003, Pages 5-34\n[2] Hoey & Poupart, \"Solving POMDPs with Continuous or Large Discrete Observation Spaces\", IJCAI 2005\n[3] Porta et al., \"Point-Based Value Iteration for Continuous POMDPs\", JMLR, Vol. 7, 2329-2367\n\nComments added after author response:\nThanks for answering my comments. While I remain by my original rating, I hope to see a future version of the paper incorporating useful suggestions from all the reviews. Besides an updated main theorem, an empirical demonstration of how to deal with scalability concerns would be very helpful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, this is adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper describes a new online planning technique for POMDPs that introduces two new ideas: re-sampling based on KLD and belief packing.  The paper is well written and comprehensive in the sense that it includes a good empirical evaluation and a theoretical analysis.  The reviewers raised concerns about the scalability of the approach, the notation and the assumptions of the theoretical analysis.  The author response was very helpful in terms of clarifying those issues.  If the paper is accepted, the authors are strongly encouraged to follow the reviewers' advice.
Decision: Accept (Poster)