Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.


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.

I 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:
*/ The use of upper bound and weighted excess uncertainty are relatively common in POMDP solvers (as cited, [5, 14] have used them too). 
*/ 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.".
*/ 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.").

KLD-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.
 
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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

The 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.

A 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. 
- 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.
- 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.
- 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. 
- 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.
- 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?

Overall, 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. 
limitations_and_societal_impact: The theoretical analysis seem to have a few limitations that are not discussed. See the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an online planning algorithm, called Adaptive Online Packing-guided Search (AdaOPS), for Partially Observable Markov Decision Processes.
The 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.

Specifically, During the planning step, a particle resampling procedure is performed adaptively on new leaf nodes.
This 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]).
AdaOPS 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.

The article also presents a technique called Belief Packing, inspired by (Zhang, Hsu, Lee [17]).
It is used to fuse similar beliefs, thus the planning procedure explores only beliefs that are significantly different.
This improves the scalability of the online algorithm.

The 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$).
The 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).
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.
Each technique, by itself, does not provide an original contribution, but the non-trivial combination of such techniques is an interesting and valuable contribution.
In 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.

The main theoretical proof presented in the article concerns the convergence to an optimal policy given enough planning time.
The 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 ?).

The 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.
I find this experimental setup incomplete.
The 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.
In particular, it is not clear how fast and reliable this convergence is. 
Using 1 second for step is a reasonable choice, but it should not be the only one considered.
It 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.
I 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?

The 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.

limitations_and_societal_impact: Authors indicate that they do not see potential negative societal impacts with their work and I agree.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Strengths:

- 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.
- 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.

Limitations:

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

I would appreciate comments from the authors especially on points 2 and 3.

Detailed comments:

- The writing in the paper could be improved to make it more accessible:
* The introduction could motivate the need for the algorithm generally at least a little, instead of the very focused technical POMDP angle taken. 
*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. 
* 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.

- 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.

** The following comments are for the information of the authors only, and do not need to be answered.

- 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.

Minor:
Line 22-23: Exact belief updating is possible with parametric distributions in certain continuous-state cases, see, e.g., Kalman filters in linear-Gaussian POMDPs.
Line 25-26: Papadimitriou & Tsitsiklis only consider the finite horizon undiscounted expected cost case for POMDP. For the infinite horizon case, see [1].
Line 65: "average" --> "expected sum of"?
Line 69: Bayesian filtering is not necessarily approximate, it can also be exact.
Eq. (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.

References:
[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
[2] Hoey & Poupart, "Solving POMDPs with Continuous or Large Discrete Observation Spaces", IJCAI 2005
[3] Porta et al., "Point-Based Value Iteration for Continuous POMDPs", JMLR, Vol. 7, 2329-2367

Comments added after author response:
Thanks 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.
limitations_and_societal_impact: Yes, this is adequately addressed.
review_title: null

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)