Online POMDP Planning with Anytime Deterministic Guarantees
Authors: Moran Barenboim
Vadim Indelman
Venue: NeurIPS 2023 poster (2023)
Keywords: POMDPs
Planning under uncertainty
Robotics

Abstract: Autonomous agents operating in real-world scenarios frequently encounter uncertainty and make decisions based on incomplete information. Planning under uncertainty can be mathematically formalized using partially observable Markov decision processes (POMDPs). However, finding an optimal plan for POMDPs can be computationally expensive and is feasible only for small tasks. In recent years, approximate algorithms, such as tree search and sample-based methodologies, have emerged as state-of-the-art POMDP solvers for larger problems. Despite their effectiveness, these algorithms offer only probabilistic and often asymptotic guarantees toward the optimal solution due to their dependence on sampling. To address these limitations, we derive a deterministic relationship between a simplified solution that is
easier to obtain and the theoretically optimal one. First, we derive bounds for selecting a subset of the observations to branch from while computing a complete belief at each posterior node. Then, since a complete belief update may be computationally demanding, we extend the bounds to support reduction of both the state and the observation spaces. We demonstrate how our guarantees can be integrated with existing state-of-the-art solvers that sample a subset of states and observations. As a result, the returned solution holds deterministic bounds relative to the optimal policy. Lastly, we substantiate our findings with supporting experimental results.

Online POMDP Planning with Anytime Deterministic Guarantees
Moran Barenboim
Vadim Indelman
Technion Autonomous Systems Program (TASP)
Department of Acrospace Engineering
Technion Israel Institute Technology NVIDIA
Technion Israel Institute of Technology vadim. Indemmm@@techhin ac. il
moranbarocanpus. technion. ac
Abstract
Autonomous agents operating in real-world scenarios frequently encounter un- certainty and make decisions based incomplete information. Planning under uncertainty can be mathematically formalized using partially observable Markov decision processes (POMDPs). However, finding an optimal plan for POMDPs can be computationally expensive and is feasible only for small tasks. In recent years, approximate algorithms, such as tree search and sample- sample-based methodologies, have emerged as state-of-the art POMDP solvers for larger problems. Despite their effectiveness, these algorithms offer only probabilistic and often asymptotic guarantees toward the optimal solution due to their dependence sampling. To ad- dress these limitations, we derive a deterministic relationship between simplified solution that is easier to obtain and the theoretically optimal one. First, we derive bounds for selecting subset the observations branch from while computing complete belief at each posterior node. Then, since complete belief update may be computationally demanding, we extend the bounds to support reduction both the state and the observation spaces. We demonstrate how our guarantees can be integrated with existing state-of-the-ar solvers that sample a subset of states and observations. As result, the returned solution holds deterministic bounds relative to the optimal policy. Lastly, we substantiate our findings with supporting experimental results.
Introduction
Partially Observable Markov Decision Processes (POMDPs) serve as a comprehensive mathematical framework for addressing uncertain sequential decision-making problems. Despite their applicability, most problems framed as POMDPs struggle to achieve optimal solutions, largely due to factors such as large state spaces and an extensive range of potential future scenarios. The latter tends grow exponentially with the horizon, rendering the solution process computationally prohibitive. The advent of approximate online, tree-based solvers has expanded the capacity of POMDPs. enabling them to tackle larger problems by providing more scalable approach to problem-solving.
A prominent search algorithm addressing the challenges posed by large state and observation spaces in POMDPs POMCP [Silver and Veness, 2010). POMCP is forward search algorithm which handles the large state and observation spaces by aggregating Monte-Carlo rollouts of future scenarios in tree structure. During each rollout, a single state particle is recursively propagated from the root node to the leaves of the tree. adaptively trades off between actions that lead unexplored areas of the tree and actions that lead to rewarding areas of the tree search by utilizing UCT [Auer et al. 2002). The guarantees on the provided solution by POMCP are asymptotic, implying that the quality of the solution remains unknown within any finite time frame.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

60
Simplified tree
Tyta
Tylre
Ozir
Deterministic guarantees IV, V,I
Tylna
Tylke
Osi
Oav
Figure I: The figure depicts two search trees: complete tree (left) that considers all states and observations at each planning step, and simplified tree (right) that incorporates only subset of states and observations, linked to simplified models. Our methodology establishes a deterministic link between these two trees.
Another notable approximate solver, Anytime Regularized DESPOT (AR-DESPOT) [Somani et al. 2013 Ye et al., 2017) is derived from Regularized DESPOT, which holds theoretical guarantees for the solution quality with respect to its optimal value. Similar to POMCP. AR- RR-DESPOT performs forward search and propagates single particle from the root node down to its leaves. It relies on branch-and- houdb approach in the forward search, and utilizes dynamic programming techniques to update the value function estimate at each node. In contrast to POMCP, Regularized DESPOT offers probabilistic lower bound on the value function obtained at the root node, providing a theoretical appeal by measuring its proximity the optimal policy.
While the primary focus of this paper is on discrete POMDP planning, it is essential to acknowledge recent advancements in POMDP planning that encompass both discrete and continuous observation spaces, Few notable approaches include POMCPOW [Sunberg and Kochenderfer 2018), LABECOP (Hoerger and Kurniawati] 2021] and AdaOPS [Wu et al., 2021]. which leverage explicit use of observation models. These algorithms employ importance sampling mechanisms to weigh each state sample based on its likelihood value, which assumed to be known. Although these methods have exhibited promising performance in practical scenarios, they currently lack formal guarantees. To address this gap, [Lim al. 20200 2022] introduced a simplified solver aimed at bridging the theoret- ical gap between the empirical success of these algorithms and the absence of theoretical guarantees for continuous observation spaces. In [Lim et al., 2022], probabilistic guarantees were derived for the simplified solver concerning its proximity to the optimal value function, thus contributing to more comprehensive understanding of POMDP planning both discrete and continuous settings.
In this paper, we focus on deriving deterministic guarantees for POMDPs with discrete state and observation spaces. Unlike existing black-box sampling mechanisms employed in algorithms such as (Sunberg and Kochenderfer 2018 Hoerger and Kurniawati 2021 Wu et al., 2021]. our approach assumes access not only to the observation model but also the transition model and the prior. By leveraging this additional information, we develop a novel algorithm that utilizes a subset of the observation space, enabling the computation of deterministic bounds with respect to the optimal policy at any belief node within the constructed tree. Furthermore, we demonstrate how these deterministic bounds can be integrated with state-of-the-e algorithms, including those that sample subsets of both the state and observation spaces. In particular, we provide experimental results showcasing the use of our bounds incorporated into the AR-DESPON algorithm.
In this paper, our main contributions are as follows. First, we derive deterministic upper and lower bounds for a POMDP problem by considering subset of the observation space each node along the tree under a fixed policy. Next, we extend these bounds to cover scenarios where both the state and observation spaces are restricted subsets, enhancing the applicability of our bounds practical settings. Based on the derived bounds, we illustrate how to incorporate the bounds into a general structure of common state-of-the-art algorithms. Specifically, in the experimental section, we present results demonstrating the integration of our theoretical guarantees with the AR-DESPOT algorithm, yielding certified solutions with deterministic bounds. Last, we perform simulations to demonstrate the use of our derived bounds in practice, further validating their relevance in POMDP planning.

---

2 Preliminaries
finite horizon POMDP M is defined as tuple AX, R), where X, A, and Z repre- sent a discrete state, action, and observation spaces, respectively. The transition density function T(F,, d2, Fe+1) _ P( Ix,, ax) defines the probability of transitioning from state 2, E X' to state Ie-1 E X' by taking action E A. The observation density function (Zz,, 24) é ((2)(2)) expresses the probability of receiving observation 2, E 2 from state T2 E X.
Given the limited information provided by observations, the true state of the agent is uncertain and probability distribution function over the state space, also known as belief, is maintained. The belief depends the entire history of actions and observations, and is denoted H, _ {Z1::; 00--1 )- We also define the propagated history as II, _ { a0:--13- 1. At each time step t, the belief is updated by applying Bayes' rule using the transition and observation models, given the previous action 0 and the current observation žt. b (x²z
(z)a)) Ex, IEX (1
(Ir-1).
where t/s denotes normalization constant and b, - P(x, H₂) denotes the belief time t. The updated belief, b, is sometimes referred to as the posterior belief, or simply the posterior. We will use these interchangeably throughout the paper.
policy function d, = IT (be) determines the action to taken at time step I, based on the current belief by and time 1. In the rest of the paper we write = T. (bx) for conciseness. The reward is defined as an expectation over a state-dependent function, r(b,, at) = Eg=o, [T2 at)], and is bounded by mmmax (z, ax)= S. Rmax. The value function for policy over finite horizon T is defined as the expected cumulative reward received by executing πT and can be computed using the Bellman update equation,
T Σ
V (b.) = r(b,, TT)
E ZE41IT
r(b TT.) Lr-r+1
(1)
The action-value function is defined by executing action oe and then following policy т. The optimal value function may be computed using Bellman's 's principle of optimality,
VT (b,) max(r(be, o.) +
E
[V (
(2)
seti/ae,le
The goal of the agent to find the optimal policy n² that maximizes the value function.
3 Mathematical Analysis
Typically, it is infeasible to fully expand Partially Observable Markov Decision Process (POMDP) tree due to the extensive computational resources and time required. To address this challenge, we propose two approaches. In the first approach, we propose a solver that selectively chooses a subset of the observations to branch from, while maintaining a full posterior belief each node. This allows us to derive a hypothetical algorithm that directly uses our suggested deterministic bounds to choose which actions to take while exploring the tree. As in some scenarios computing a complete posterior belief may be too expensive, we suggest second method that in addition to branching only a subset of the observations, selectively chooses a subset of the states at each encountered belief. Using the deterministic bounds at the root node for each action value allows us certify the performance of given policy at the root of the planning tree. Moreover, given scenario in which an action exists whose lower bound surpasses all other actions' upper bound, the algorithm can identify the optimal action and stop further exploration. In contrast, existing state-of- the-hhhr art algorithms either do not provide any guarantee the solution quality (e.g. POMCP Silver and Veness (2010) or merely provide probabilistic guarantee on the solution (c.g. DESPOT Somani et al. [2013) ). In the following section, we show how to the deterministic bounds in conjunction with of-te-o algorithms to obtain performance guarantees.
Both of the presented approaches diverge from many existing algorithms that rely on black-box prior, transition, and observation models. Instead, our method directly utilizes state and observation probability values to evaluate both the value function and the associated bounds. In return, we offer
All proof's and derivations deferred to the supplementary file.
3

---

anytime deterministic guarantees on the value function for the derived policy and establish bounds on its deviation from the value function of the optimal policy.
In this section we provide a mathematical quantification of the impact of using a solver that only considers small subset of the theoretical tree branches and subset of states within each node. We begin by defining a simplified POMDP, which is a reduced complexity version of the original POMDP that abstracts or ignores certain states and observations. We then establish connection between the simplified value function and its theoretical counterpart. Finally, we demonstrate relationship between the simplified value function, obtained by following the best policy for the simplified problem, and the theoretically optimal value function.
We begin with general definitions of simplified prior, transition and observation models,
x E &
(x()))
(3)
0
otherwise
P(1++1
(1)
r++1 (H
P(1 (,)
(4)
0
otherwise
Pizz xt)
2 E (11,
P(2 24) A
(5)
otherwise
where ((H S X and (HH) S Z may be chosen arbitrarily, e.g. by sampling or choosing a fixed subset a-priori, the derivations of the bounds independent of the subset choice. Note that the simplified prior, transition and observation models are unnormalized and thus do not represent valid distribution function. For the rest of the sequel will drop the explicit dependence
the history, and denote {H1++) = X. ((H,) = 2. Using the simplified models, we define the simplified belief 1 The simplified belief is updated using the simplified belief update equation, which is modification of the standard belief update equation that replaces the usual models with the simplified ones. More precisely,
P(eess (244)) Ex, 1(
P (ze+1 Hi+1) # 4
(6)
otherwise
where 1 (x) = PP(x++1 Het1), and P( H(+1)
P(zz+1 | (1+1) Σx, P(re-1
Te; mT Pax, H,). Note that simplified belief cannot depend on an observation that is not part of the simplified observation set and considered undefined. Last we define a simplified value function,
F (b)) - r(br, me) + E [b.)]
Σ (at)r(( me)+ )+
Σ P(ze+) [
(8)
where the simplified expectation operator, B|-], is taken with respect to the unnormalized likelihood P( H(41).
3.1 Simplified observation space
We first analyze the performance guarantees of simplified observation space, while assuming complete belief update at each belief state, i.e., X' = X. The following theorem describes the guarantees of the inneevvationsimpliife value function with respect to its theoretical value,
Theorem 1. Let by belief state time t, and T be the last time step of the POMDP. Let V (bbb) be the theoretical value function by following policy n, and let V (be) be the simplified value function, as defined in (8), by following the same policy. Then, for any policy n, the difference between the theoretical and simplified value functions is bounded as follows,
T
(*. -0 S Σ
1- E
EMS (Ix)) II
P(Zz xx Px)P(I Fk-15 1, Th-
2 e (br),
T=t++
Retlir BLT
k=t+1
(9)

---

where we use subscript of (2) in e" (bç) to denote observation-only simplification. Importantly, the bound only contains terms which depend on observations that are within the simplified space, 2 Z. This is an essential property of the bound, as it is value that can easily be calculated during the planning process and provides certification of the policy quality at any given node along the tree. Furthermore, it is apparent from (20) that as the number of observations included in the simplified set, 2, increases, the value of e (be) consequently diminishes,
ΣΣ ((r)
II P(zs Px) Ik-1, Tk-1) A=1
8 2+22
F1r Fo.T
leading to convergence towards the theoretical value function, i.e. e (be) - 0.
Theorem 3 provides both lower and upper bounds for the theoretical value function, assuming fixed policy. Using this theorem, we can derive upper and lower bounds for any policy, including the optimal one. This achieved by applying the Bellman optimality operator the upper bound in repeated manner, instead of the estimated value function; In the context of tree search algorithms,, our algorithm explores only a subset of the decision tree due to pruned observations. However, every belief node encountered during this exploration, all potential actions are expanded. The action-value of these expanded actions is bounded using the Upper Deterministic Bound, which we now define as
UDB" (b,, a.) A Q" (be, 0e) + cg (be, oz) = r(bb, az) + Rezzz [V" (b++1)) + E (b,,at),
(10)
where the action-dependent bound on the value difference, e (be, az), is the bound of taking action or in belief b, and following policy thereafter,
T
c (be, a1) - Rmax
Σ 7=1+1
Σ Z14-1:7 Zte
E
P(241 (++1)P( De, at).
(11)
II k=
P(ZN PIF [k-1,,
In the event that no subsequent observations are chosen for a given history, the value of Q (b,, az) simplifies to the immediate reward plus an upper bound for any subsequent policy, given by Rmax (I' - ----- 1).
Using UDB define the action selection criteria according to
a arg max UDB" (bt, oz)] arg max (Qr, + (b (b). E.
(12)
aj
Moreover, the optimal value function can be bounded as follows, Lemma 1. The optimal value function can be bounded as
V (be) S @UDB((b),,
(13)
where the policy π is determined according to Bellman optimality over the UDB, i.e.
UDBT(b:) max 1"T (br, ax) c. (,e,,,,, at)]
(14)
a.EAA
maxir(b, a.) ) + +E (V* + (b,, az)l.
(15)
Corollary 1.1. By utilizing Lemma 7 and the exploration criteria defined in (65). an increasing number of explored belief nodes guarantees convergence the optimal value function.
Notably, UDB does not require complete recovery of the posterior branches to yield an optimal policy. Each action- value bounded by a specific lower and upper bound, which can be represented as an interval enclosing the theoretical value. When the bound intervals of two candidate actions do not overlap, one can clearly discern which action is suboptimal, rendering its subtree redundant for further exploration. This distinction sets UDB apart from current state-of-the-arr online POMDP algorithms. In those methods, any finite-time stopping condition fails to ensure optimality since the bounds used are either heuristic probabilistic in nature.
5

---

3.2 Simplified State and Observation Spaces
In certain scenarios, the complete evaluation posterior beliefs during the planning stage may pose significant computational challenges. To tackle this issue, propose the of simplified state space in addition to the simplified observation space considered thus far. Specifically, we derive deterministic guarantees of the value function that allow for the selection of subset from both the states and observations.
Theorem 2. Let by and by be the theoretical and simplified belief states, respectively, time and T be the last time step of the POMDP. Let v (bbbb) be the theoretical value function by following a policy v, and let V (bg) be the simplified value function by following the same policy, as defined in (18). Then, for any policy the difference between the theoretical and simplified value functions is bounded as follows.
('*(b)) Vd y0*(bo) Ruax 1
Σ ()( + R
1 Ezir Eb((2) C (b)), E
(16)
Similar to Theorem 3 -. (bu) only contains probability values of instances from the simplified sets. However, this bound accounts for both the states and observations that are within the simplified spaces, 2, X, 2, which makes it viable to compute at planning time. In contrast to Theorem 3 this bound can only be calculated at the root since relies on the knowledge the actual probability value of the prior, (x)),, for states now the belief density function at different belief nodes is not required, we demonstrate in the next section that belief update can be avoided completely, which makes it suitable to attach guarantees to cateeoff-hheare algorithms.
X, which only available at the root. Furthermore, since
The process of maintaining upper bound for action-value function follows similarly the one presented in the observation-onie -nly simplification subsection 3.1
G, (br,aa) & Rmax
Σ
b(x))((4411 (2) +
(17)
Rmax
Σ
1- Σ Σ
F++1) P((0H Fez 0e)
II F(Eu xxx) P(r k=
- 1b-1)
r=1+1
Zer
In (b,, az). the subscript of (x, 2) differentiates the bound of the state- and observation- simplification from the observation-only simplification bound.
Computing the bounds in practice is straightforward and can be done iteratively, which fits many online planning algorithms. As it requires the summation over probability values for every considered trajectory, Ti, ao, 1 ø1, at- 3t, Zt, as shown equations (17) and (TI). In the subsequent section, we provide further details and illustrate how the bounds derived from the state-observation
simplification can be used to derive deterministic guarantees on policies obtained from existing state-of-the-aa algorithms.

---

4 Methods
Algorithm 1 ALGORITHM-AA
function SEARCH
function SIMULATE((4, d, Pa)
1: while time permits do
if d then
2: Generate states from bu
2: return 5(h) + 0
To f x
3: end if
4:
IPo < b(za Ita)
4: Select action
5:
7o & r(h) then
5: Generate next states and observations, x/
6: P(h) < P(h) + Po
Ta, IP, (aa, haz, Td. Pr, 7x,4
7: end if
7: Select next observation 2.
SIMULATE(H, D, TO, Po).
8: SIMULATE(haz, d Tu, P.)
9: end while
9: BWDUPDATE(N,,Oo)
10: return
10: return
function FWDUPDATE(ha, huz, Ta, P..
function BWDUPDATE(H, ha, d)
1: Ta & T (hea) then
1: <(ha) 7 - Vmax (P(x) - P(ha)) 1 D-
2: T(ha) - T(ha) U (Ta)
Viax (h(h)) Σ P(haz))
3: R(ha)= + R(ha) +Pr ((
2/ho
4: end if
2: U(ha)= R((ha) - 2/haa U(aaz) c(ha)
5: Ta - (z)
3: I(ha)= R(ha) +7 I(haz)) c(ha)
T P-P..77ua" Ta
4: U(h) max,' {haa))
7: Ta E T(haz) then
L(h) < max. [L(ha))
8: P((az)) + (haz)) + P-
9:
r(haz) r (haz) {Tu)
6: return
10: end if
11: return
In this section we aim to describe how to fit our bounds to general structure algorithm, named ALGORITHM - A, which serves as an abstraction to many existing algorithms. To compute the deterministic bounds, we utilize Bellman's 's update and optimality criteria. This approach naturally fits dynamic programming approaches such as DESPOT (Ye et al. [017] and AdaOPS (Wu et al.) 2021]. However, it may also be attached with algorithms that rely Monte-Carlo estimation, such as POMCP [Silver and Veness, 2010), by viewing the search tree as a policy tree.
While the analysis presented in section 3 is general and independent of the selection mechanism of the states or observations, we focus on sampling as a way choose the simplified states at each belief node and the observations to branch from. Furthermore, the selection of the subspaces X Z need not be fixed, and may change over the course of time, similar to state-of-the-ar algorithms, such as Hoerger and Kurniawati [2021), Silver and Veness (2010), [Somani et al. [2013) Sunberg and Kochenderfer] 2208), J Wu al. 2022]. Alternative selection methods may also feasible, as sampling from the correct distribution is not required for the bounds to hold. Importantly, attaching our bounds to arbitrary exploration mechanism, such as in POMCP or DESPOT, leverages the derivations and convergence guarantees shown in 3.2 Clearly, the deterministic bounds remain valid, but a convergence analysis depends on the characteristics of the specific ALGORITHM A being used.
ALGORITHM A is outlined in algorithm [ For the clarity of exposition, we assume the following: at each iteration single state particle is propagated from the root node to the leaf (line of function SEARCH). The selection and transition models (line 5). and each iteration ends with the full horizon of the POMDP (lines 2 However, none of these are a restriction of our approach and may be replaced with arbitrary number of particles, arbitrary state and observation selection mechanism and single multiple expansions of new belief nodes at each iteration.
next state and observations are done by sampling from the observation
To compute the UDB value, we require both the state trajectory, denoted т, and its probability value, Fr. We use the state trajectory as a mechanism avoid duplicate summation of an already accounted for probability value and is utilized to ascertain its uniqueness at belief node. The probability value, Pr, is the likelihood of visiting trajectory as the product of the prior, transition and observation likelihoods (line 6). If a trajectory was not seen before belief node, its reward value multiplied by the trajectory likelihood, shown in Each node maintains cumulative sum of the likelihoods of all visited trajectories. This is then being
{aro; do, 21, #1,..., at Ft. 2x) and is calculated
7

---

used to compute the upper and lower bounds, shown in [ The bounds are computed in lines | represent the loss holding only a subset of the sates in node ha from the set node h. plus the loss of having only subset of the future states and observations, where Vmnax represent the maximum possible value function. A simple bound on the value function may be Vmax Rmax (D - 1), but other more sophisticated bounds are also possible, as well as different values for lower and upper bounds.
The time complexity for each posterior node, primarily depends on the specific algorithm being used. In the case of dynamic programming methods, such as DESPOT and AdaOPS, there is negligible added computational complexity detailed below. In the case of Monte Carlo methods, such as POMCP, the computational complexity is O(]-A]) attributed mainly to the action-selection, while our approach adds another linear time complexity term, making it O[I + [2]) due to the summation over the simplified observation space. During each iteration of the algorithm, an "IF" statement used to determine whether a specific trajectory has already been encountered at the current node. This verification process can potentially result in an added linear complexity of O(D), where represents the planning horizon. However, this overhead can be circumvented by assigning a unique ID value to each trajectory at the previous step and subsequently checking whether a pair, comprising the ID value and the new state, has already been visited. This approach reduces the overhead to an average time complexity of O(1) by utilizing hash maps efficiently.
Experiments
In this section, we present the experimental results obtained by integrating deterministic bounds into tfate-of-the-as algorithms namely, AR-DESPOT Soomni et al. 2013) and POMCP Silver and Veness 2010) as baseline. The pri- mary objective of these experiments is to demon- strate the validity of our derived bounds, as pre-
330
Upee Bound
Wil
200
Value function
sented in Theorem 2] and the corresponding al- gorithm outlined in Algorithm [
-199
The implementation of our algorithm was car- ried out using the Julia programming language and evaluated through the Julia POMDPs pack- age, provided by [gorov et al. [2017]. Although the library primarily focused on infinite horizon problems, we made the required modifications to extend its capabilities accommodate finite- horizon POMDPs. The experiments were con- ducted on computing platform consisting of an Intel(R) CTr)(TM) 17-7700 processor with CPUs operating 3.60GHz and 15.6 GHz. The selection of hyper-parameters for the POMCP and AR-DESPOT solvers, and further details about the POMDPs used for our experiments are detailed in the appendix.
-308
Planning Time [s]
Figure 2: The graph illustrates the convergence of the deterministic bounds using Deterministically-Bonnde -ounnee-- AR-DESPOT, with upper and lower bounds depicted alongside the optimal value obtained through exhaustive search.
In Figure 2 we demonstrate the empirical convergence of the deterministic bounds relation to planning time. For these experiments, we focused on toy example, Tiger POMDP Kaelbling et al. [1998.. By conducting an exhaustive search and computing a full posterior belief for each node, derived the optimal value, depicted as dashed green line in figure 2 The graph presents the convergence of the bounds calculated with Deterministically-Buunn -Bundeed AR- DE-PEST DD--DESPOT), to the optimal value. The mean values of the upper and lower bounds across 100 simulations are plotted, accompanied by the standard deviation, for time increments of At 0.1 seconds.
Algorithms that provide probabilistic guarantees have a non-zero probability of taking suboptimal action regardless of the planning time. contrast, when given sufficient planning time, the deter- ministic bounds can certify the optimal action once the lower bound of an immediate action exceeds the upper bounds of all other actions. In our experiments, we observed that although the baseline algorithms, AR- DESPOT and POMCP, and the deterministically bounded algorithms, DB-DESPOT
8

---

and DB-POMCP, had access to the same tree and samples, AR-DESPOT and POMCP occasionally made incorrect decisions, resulting in degraded performance.
We evaluated the performance of both algorithms on different POMDPs, including the Tiger POMDP, Discrete Light Dark [Sunberg and Kochenderfer [2018] and Baby POMDP. The corresponding results are summarized in Table After each planning session the calculated best action is executed, the belief is updated according to the captured observation and new planning session is invoked. The table reports the empirical mean and std of the cumulative rewards obtained by executing the calculated best actions based on 100 runs.
In the POMDPs with manageable state, action and observation sizes, both the DB-DESPOT and AB-POMCP algorithms frequently identified the optimal action within I-second time budget. It's important to highlight that these algorithms employ stochastic methods for belief tree exploration as in the baseline algorithms. Consequently, the outcomes between DB-DESPOT and DB-POMCP can vary, and there is no guarantee of consistently identifying the optimal action in every constrained-tine planning session. An optimal action determined when lower bound of given action is higher than any other upper bound; notably, this does not necessitates construction of the entire planning tree and can be used as an early stopping mechanism for the optimal action. In the larger Laser Tag POMDP Somani et al. 22033), the DB-DESPOT and DB-POMCP did not outperform AR-DESPOT and POMCP. This discrepancy occurred because the planning time was insufficient to find an optimal action due to larger state, action and observation spaces of Laser Tag POMDP. While our proposed algorithms shows promise in more compact POMDPs, their performance in larger-scale problems, like the I Laser Tag POMDP, especially when constrained by external time budgets, merits further investigation.
Table 1; Performance comparison with and without deterministic bounds.
Algorithm
Tiger POMDP
Laser Tag
Discrete Light Dark
Baby POMDP
DB-DESPOT (ours)
0.74
-..2
-0.29
0.59
AR-DESPOT
2.85
-5.10:10.14
-61.53::5.80
-5.40
DB-POMCP (ours)
3.01
-3.97+0.24
-3.70+00.2 -1.51+1.15
0.54
POMCP
2.18+0.76
-3.92+0.27
-5.39+0.63
Conclusions
In this work, we presented a novel methodology aimed offering anytime, deterministic guarantees for approximate POMDP solvers. These solvers strategically leverage subset of the state and observation spaces alleviate the computational overhead. Our key proposition elucidates linkage between the optimal value function, which is inherently computationally intensive, and a more tractable approximation frequently employed in contemporary algorithms. In the first part of the paper, we derived the theoretical relationship between the use of selective subset of observations in a planning tree. One contribution of this work is the formulation of an upper deterministic bound (UDB) which governs exploration within the belief space, and is theoretically guaranteed to converge to the optimal value. This approach, however, depends on a complete belief update at each node of the tree, a requirement that can be computationally infeasible in many practical POMDPs. In the second part, we address this computational challenge, by extending our derivations to account for both subset of the observations and states. This extension increases the feasibility of our approach and allows it to be incorporated into existing state-of-the-art algorithms. We have outlined how methodology can be integrated within these algorithms. To illustrate the practical utility of our derivations, we applied them to certify and improve the solution of AR-DESPOT and POMCP algorithms, ofte-of-the-arr solvers for POMDPs.
6.1 Limitations and future work
While the application of our deterministic bounds within the context of the AR-DESPOT algorithm showcased its potential, there are several challenges that need to be addressed in future work. Firstly, the convergence rate of our proposed method remains an area for further exploration. A detailed theoretical analysis on this aspect could provide valuable insights into the practicality of our approach

---

for larger, more complex domains. Secondly, the current use of the UDB is predominantly restricted problems characterized by low state dimensionality. Extending the UDB handle higher state dimensionality is significant challenge due to the increased computational complexity involved. Finally, we consider the integration of the UDB with simplified state and observation spaces to be promising future direction. This could potentially lead to more comprehensive and efficient strategy for handling larger POMDPs, thereby further enhancing the applicability of our deterministic approach.
Acknowledgments
This work was supported by the Israel Science Foundation (ISF) and by US NSF/US-IsTac BSF.
References
Peter Auer, Nicolo Cesa BesacBianchh, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22 256,, 2002.
Maxim Egorov, Zachary N. Sunberg, Edward Balaban, Tim A. Wheeler, Jayesh K. Gupta, and Mykel Kochenderfer. POMDPs.jl: A framework for sequential decision making under uncertainty. Journal of Machine Learning Research, 18(26):1-5, 2017. URL http::/jmll wwwpeorrggpppaaa. papers/ v18/16-30 300.000.000 html
Mareus Hoerger and Hanna Kurniawati. An on-line pomdp solver for continuous observation spaces. In IEEE Intl. Conf. on Robotics and Automation (ICRA), pages 7643-7649. IEEE, 2021.
L. P. Kaelbling, M. L. Littman, and A. R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1):99-1)) 134, 1998.
Michael H. Lim, Claire Tomlin, and Zachary N. Sunberg. Sparse tree search optimality guarantees in pomdps with continuous observation spaces. In Intl. Joint Conf. on Al (IJCAI), pages 4135-4142, 2020.
Michael H Lim, Tyler J Becker, Mykel Kochenderfer, Claire J Tomlin, and Zachary N Sunberg. Generalized optimality guarantees for solving continuous observation pomdps through particle belief mdp approximation. arXiv preprint 10.0051,, 2022.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Advances in Neural Information Processing Systems (NIPS), pages 2164-2172, 2010.
Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lec. Despot: Online pomdp planning with regularization. In NIPS, volume 13, pages 1772-1780, 2013.
Zachary Sunberg and Mykel Kochenderfer. Online algorithms for pomdps with continuous state, action, and observation spaces. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 28, 2018.
Chenyang Wu, Guoyu Yang, Zongzhang Zhang, Yang Yu, Dong Li, Wulong Liu, and Jianye Hao. Adaptive online packing-guide guided search for pomdps. In M. Ranzato, A. Beygelz- imer, Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances Neural In- formation Processing Systems (NIPS), volume 34, pages 28419-28430. Curran Associates, Inc., 2021. URL httpl/tttt///poeeedinnge wttpeeeedddnnnnenuuss.re. neurips. ceuppps.ccpppperrr httpe///pappr.flll/eppppppe htteeerfiilee/ppeee//////iieeee ef @ff118888755333116600fff000e6eee .pff
Nan Ye. Adhiraj Somani, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. JAIR, 58:231-266, 2017.
10

---

Appendices
7 Mathematical Analysis
We start by restating the definition of the simplified value function,
V- (b,) - r(b,, me) + + [V.b)]
(18)
Σ (as)r( mt)+ Σ P( (((2)))(
(19)
7.1 Theorem
Theorem 3. Let be belief state time I, and T be the last time step of the POMDP. Let V* be the theoretical value function by following policy æ. and let V* (br) be the simplified value function, as defined in (18). by following the same policy. Then, for any policy x, the difference between the theoretical and simplified value functions is bounded as follows.
("*b))-
1- Σ
P(Zu Pxx) 1x-1, Th k=1+1
II
(b)).
T=2+1
(20)
Proof. For notational convenience, we derive the bounds for the value function by denoting the prior belief as bo.
T Σ rbe, at)
Vo (bo) = EZIT
(21)
applying the belief update equation,
T
T
P(ze xx)) En, [P( | 0r-1, Te- 1)6c-1
(b) EIP
(ZT
P
H
Σ
(xx,, at)
P (zx HH,)
T=1
t=
21
(22)
T
T
Ih P(ck xx P(rr IK-1, TT-1 Mb(0))
E
P(
H
r(z1, as)
II P (zr HF)
1=
(23)
ΣΣΣЛ #1.T Re: k=1
P(
(24)
which applies similarly to the simplified value function,
1Σ3Ī P(Zx Px)))( 24-1, TT- (0)
(b)(
(25)
21.7 SETT

---

We begin the derivation by focusing on a single time step, t, and later generalize to the complete value function.
E [r(br]] E.... ir(b:)ll
(26)
EIII
P(ZH 2x) (TT ER Th- (4-1)6(())((()))
II ='=1
P(z
[gg) P
21--1, Te (1)0)))()))((z))
1=1
(27)
ΣΣ r(x))
II P(ck (x)P((x)) #k-1, #k-1, 7k-1)6mm Lk=1
II =1=1
b(xo) P(ze ax PPw
I -1, Tk--1)
2002
(28)
= =Σ (x())))
II P( ax) Px) 1x-11 Tk- Tk-1)6(<oo)
II b(zo) P(a (g)) P(r
zg- TK
F1.r 20.4
where the second transition is due to triangle inequality, the third transition is equality by the construction, i.c. using the simplified observation models imply that the difference nonnegative. We add and subtract, followed by rearranging terms.
Σ> |x()))) Fiir 2012
(30)
P(za, The Ik-1, 1k-))(())) - II
b(zo PTz Tx-) (1-11,
k=
A=
((o)P((2 I& Zk-1, TH- PP) (1-1)T11) II
6(x0 P(zw, 11 Tw
k'=1
Σ (r())))
(31)
#1: 00.4
[-1
P(z Te 1z-1: Tz-1) 1)
P(zs, Ty 12-1, - II
b(xo ((z)) Pl xx 1T
k=1
+ II ((xo)) 2x-1, Th Th-1) (Pee, (c-1) Pl m(-1;
1=1
applying Holder's incquality,
Rmax ΣEP(a,
P( (--1) b(zo) II P(zk, 2& T2-1, b(oo)
P I&
28-1, Tk
21ct Ross
(32)
+ Runxx ΣΣ
II
P(zk 2e 1() 12-1, Te-1)
P(z,,
1x--1, TT-1
Jugee 1=1
=R Σ)
a( 12-11 Tt-1)-
(33)
(-1
b(xo) II
Pi2k, ok Dk-1, Tk-1) b(xr)) II P(ck, o* x (k-1) Rmaxx:
k=l
[-1
=Rmax Σ
Σ
((ro) II
P(zK, I6 1k-1,
TT-1) 1
Mxx))
P(zk, th 1x-1, T6-1)
(34)
S1ie-1 Bott1
k=1
Reaxdr
12

---

following similar steps recursively,
Rmax
8+
(35)
7=1
Finally, applying similar steps for every time step E [1, T
results in,
VT V (b+) S Rmax Σ 8
(36)
(=1==1
where,
6, = 3E
(iZ Th 2k-1, Th- ( [P 27 I+-1, TT-1) - P(er, Ir
-+-1)
Fger 1=1
= ΣED
II
F( F(z,
FL 27-11
(37)
2i-r-1 100
plugging the term in 37 to 36
and expanding the terms results in the desired bound,
V - (b)) S Rax
1- E E(
II k=t+1
F(zx
Pt) 0x-1, T Tk-1)
(38)
+=++1
2641:
Zur
which concludes our derivation.
7.2 Lemma 1
Lemma 2. The optimal value function can be bounded as
V (be) S UDB (b:)
(39)
where the policy is determined according Bellman optimality over the UDB, i.e.
UDB" (b:) A max 1 (be, at) + 6 (be,,, at)] a,EA
(40)
max/r(be a.) +E. Bi (be+1)) E (b), a.EA
(41)
Proof. In the following, we prove by induction that applying the Bellman optimality operator on upper bounds to the value function in optimal value function. The notations are the same as the ones presented in the main body of the paper. We restate some of the definitions from the paper for convenience.
POMDPs will result in an upper bound on the
The policy ne (be) determined by applying Bellman optimality belief by, i.e.,
(b.) arg max (Q" (br. ar) + (br, (be,,
(42)
As will needed in the following proof, we also define the value belief which includes in its history least one observation out of the simplified set, e.g. H, {ao, 21,....24 2k & Z...., ......,2] as being equal to zero. Explicitly,
(TP(aa ag. 21, ... 2k & 2,...,,20
21) = 0 Vk E [1,t].
(43)
We also use the following simple bound,
Va
Runxx -T-t-1)
(44)
Base case (1. - T) At the final time step T, for each belief we set the value function to be equal to the reward value that belief state, by and taking the action that maximizes the immediate reward,
UDB (bT) max(r(br, aT) + (br, ar) = arg max(r(br aT) or
(45)
13

---

which provides an upper bound for the optimal value function for the final time step, V2((r) - UDB*(bT). Induction hypothesis Assume that for given time step, i, for all belief states the following holds,
(b:) & UDB (6:).
(46)
Induction step We will show that the hypothesis holds for time step 1. By the induction hypothesis,
(b, - (DB Abe.
(47)
thus,
((b-11:0-1)== = r(b,-,,, + Σ
P (z H,) VT
(48)
2,EZ
S a-1 +
Σ
P (( H1 UDB"(b(z)))
(49)
2E2
=r(b:-1,0-1)+
Σ P (2 HT))
V (be) (b,))
(50)
#,
For the following transition, make of lemma
= =r(b(-1, + Eejlh 1
(i(b)) + (b(-11,
(51)
= (UDB*(b,-1,44
(52)
Therefore, under the induction hypothesis, Qi (1-1(b1-1,0 I (b-1((1-1, Taking the maximum over all actions dz.
UDB UDB (bi-1)= max G--EEÀ
(IDBB((r-11.44
(53)
max a1 IEA
{Qi-1 a111) V2 (b--1)
which completes the induction step and the required proof.
Lemma 3. Let by denote a belief state and गi a policy at time t. Let P( | xx) be the simplified observation model which represents the likelihood of observing 2t given Iy. Then, the following terms are equivalent,
Ex. (7(+,)) + c = -Ez, (V( c (br-1,,
(54)
Proof.
Ez
(T, + +
(55)
T Σ
Exz
Vi (be(
+ Ez,
Riax
Σ Σ b II
P(zx PP IK-1, 1)
r=t+1
2t+ Zur
k=++1
(56)
focusing on the second summand,
Σ P (21 Hi) R
Σ
1 1- Σ b
II Piza PPF 1 10- Tk-1) A=t+1
(57)
T=+11
Zttlir
T
Rmax
Σ
1- Σ P
(ze HH))
Σ Σ b(z))
II P(zu (1) 1T--1,TA-)
(58)
r=#11
k=t+1
14

---

by marginalizing over 21-1,
T Σ 7=1+1
P(z. 2t (t) 12-11 TT 1)((00)))))))
= Raxx
P1- 11-2
1
H;) Σ E
(59)
P P(ze H₂)
2t
Zetisr Fe-lir
II
F(zk I P(xx)
- Th TB-1)
km1+1
canceling out the denominator,
Σ1-Σ P(ze 2x)P(2z, |
Rax
(60)
T=I+1
Relr
II P(Zk (P 1 (A-1) (be-1,, (bc-1,
R=t+1
V7 (b.) Baib 1.01 V7 (b:)) By the definition of a value
it is left to show that B 1.02
function a belief not included in the simplified set, we have that,
Egg |4- 1 (.(b))
EP(s (21 H;) V. (b.)
(61)
Σ P (2)
H₂) V (bt)
Σ (z HJ
Vi
(62)
ZE
=E2iZ
Σ P (z+ Hτ) (b,)
(bx)
Σ
PP (z H
(63)
2,EZ
=
161-1 [i(1)]
Exg
(64)
which concludes the derivation.
7.3
Corollary 1.1
We restate the definition of UDB exploration criteria,
0t = arg max (UDB" (bt, 0t) = arg max 'Q" (he, 0z) + + (bt,a))) at)] E.A
(65)
agE. E.A
Corollary 3.1. Using Lemma and the exploration criteria defined in 665 guarantees convergence to the optimal value function.
Proof. Let us define a sequence of bounds, UDB (b.) and corresponding difference value between
UDB, and the simplified value function,
UDB - V. (be (T, (bc),
(66)
where n E [0, [ corresponds to the number of unique observation instances within the simplified observation set, 2,, and |2| denotes the cardinality of the complete observation space. Additionally, for the clarity of the proof and notations, assume that by construction the simplified is chosen such that Z, (H,) Z, remains identical for all time steps t and history sequences, H, given n. By the definition of =²,,(bb)). (bt).
JT. (bc) R Rmax
Σ
1- Σ b(o))
II PiZu Px) Ik-1, Th TT-1)
(67)
Fetlir EZ, Bii
k=t+1
15

---

we have that (bt)
+ 0 as - 2 since
Σ
Σ b(x))
II k=++1
P( 2z (PTx)
2k-1, Tk-1)
(68)
as more unique observation elements are added to the simplified observation space, nn, eventually recovering the entire support of the discrete observation distribution.
From lemma 2 we have that, for all n E [0, [2]] the following holds,
Va* (be) - UDB (b.) V (be) + (bt).
(69)
Additionally, from theorem 3 we have that,
V (b.) V (b,) S (bi,,
(70)
for any policy π and subset nn S Z, thus,
V. (be)
5 (bb) < (*(be) V (b:) Vo (b,) + (be).
(71)
1=|22 V (b,)
Since ch,2 + 0 as n + 1 and 2 is finite, it is guaranteed that UDB which completes our proof.
Moreover, depending the algorithm implementation, the number of iterations can be finite (e.g. by directly choosing actions and observations to minimize the bound). A stopping criteria can also be verified by calculating the difference between the upper and lower bounds. The optimal solution is obtained once the upper bound equals the lower bound.
Experiments
8.1 POMDP scenarios
We begin with a brief description of the Partially Observable Markov Decision Process (POMDP) scenarios implemented for the experiments. each scenario bounded by finite number of time steps used for every episode, where each action taken by the agent led to a decrement in the number of time steps left. After the allowable time steps ended, the simulation was reset its initial state.
8.1.1 Tiger POMDP
The Tiger is classic POMDP problem Kaelbling et al. [1998] involves an agent making decisions between doors, concealing tiger and the other reward. The agent needs to choose among three actions, either open each one of the doors or listen to receive an observation about the tiger position. In our experiments, the POMDP was limited horizon of steps. The problem consists of actions, 2 observations and 2 states.
8.1.2 Discrete Light Dark
an adaptation from Sunberg and Kochenderfer (2018) In this setting the agent needs to travel on a ID grid to reach a target location. The grid is divided into dark region, which offers noisy observations, and a light region, which offers accurate localization observations. The agent receives penalty for every step and reward for reaching the target location. The key challenge is to balance between information gathering by traveling towards the light area, and moving towards the goal region.
8.1.3 Laser Tag POMDP
In the Laser Tag problem, Somani et al. [0013, an agent has to navigate through a grid world, shoot and tag opponents by using a laser gun. The main goal is to tag as many opponents as possible within a given time frame. The grid is segmented into various sections that have varying visibility, characterized by obstacles that block the line of sight, and open areas. There are five possible actions,
16

---

moving in four cardinal directions (North, South, East, West) and shooting the laser. The observation space cardinality is |z| 1.5 x 10", which described discretized normal distribution and reflect the distance measured by the laser. The states reflect the agent's current position and the opponents" positions. The agent receives reward for tagging an opponent and a penalty for every movement, encouraging the agent to make strategic moves and shots.
8.1.4
Baby POMDP
The Baby POMDP is a classic problem that represents the scenario of a baby and a caregiver. The agent, playing the role of the caregiver, needs to infer the baby's s needs based on its state, which can be either crying or quiet. The states in this problem represent the baby's ' needs, which could be hunger, discomfort no need. The agent has three actions to choose from: feeding, changing the diaper, or doing nothing. The observations are binary, either the baby is crying or not. The crying observation does not uniquely identify the baby's state, the baby may ery due to hunger or discomfort, which makes this a partially observable problem. The agent receives a reward when it correctly addresses the baby's ss needs and penalty when the wrong action is taken.
8.2 Hyperparameters
The hyperparameters for both DB-DESPOT and AR-DESPOT algorithms were selected through grid search. We explored an array of parameters for AR-DESPOT, choosing the highest-nerforming configuration. Specifically, the hyperparameter K was varied across {10, 50, 500, 5000), while À was evaluated at {0, 0.01, 0.13. Similarly, DB-POMCP and POMCP were examined three different values for the exploration-exte intorattioncplliiatttio. exploitation weight, c = {0.1, 1.0, 10.0) multiplied by Vmazs which denotes an upper bound for the value function.
For the initialization of the upper and lower bounds used by the algorithms, we used the maximal reward, multiplied by the remaining time steps of the episode, Rmax (T-t-11
Finally, we provide our algorithm implementation in http:://jiibbcommmoooaa////nninp Guarantees.....
17


Reviews:
[{"review_id": "4Gn9XmADcn", "reviewer": "Reviewer_9qkM", "summary": "The paper introduces novel contributions in the form of deterministic bounds for discrete state space POMDPs and an algorithm to effectively implement these bounds in existing algorithms. The authors' key innovation lies in the identification of a specific subset within the observation and state space.\n\nThrough experimentation, the results demonstrate that incorporating these bounds leads to notable performance improvements in the majority of cases.\n\n\n\n\n", "questions": "See weaknesses", "limitations": "The limitation is addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's presentation is commendable, offering clarity, and the derivations appear to be accurate. The inclusion of pseudo-code facilitates easy comprehension of the algorithm.\n\nThe presence of theoretical guarantees adds value to the research, instilling confidence in the proposed approach.", "weaknesses": "The authors' assumptions in this paper include a discrete state space and a known transition and observation model, which may not always align with real-world practicality.\n\nCertain notations concerning reward functions are found to be inadequately defined, requiring further clarification.\n\nRegarding the experimental results, the substantial gap observed on the Discrete Light Dark scenario is mentioned but lacks in-depth discussion, leaving room for further elaboration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "T33FNiCYek", "reviewer": "Reviewer_JfUf", "summary": "This submission develops a method for POMDP planning based on a notion of limiting the states and observations that have been and will be encountered during the tree search.  Two cases are developed, one where only observations are limited, and one where both states and observations are limited.\n\nIn both cases, the theory develops the notion of a value associated with this limited setting, and shows that the limited value has a well-defined absolute-error bound w.r.t. the real `unlimited` value function.  Such bounds are then used to choose actions in an UCB-like fashion, which results in the final planning method.\n\nThe simplified POMDP formalism is quite interesting, and explained clearly enough.  However, it might benefit from aditional discusssion about the assumptions that the limited observation and state sets need to satisfy, e.g., it seems like the limites state set must contain at least one state that is supported by the non-limited initial belief.  It also seems like the observation and state sets may not always be chosen freely and independently, because if the limited observation set allows for limited histories whose beliefs **only** support states that don't belong to the limited state set, then the limited version of belief updates shown in equation (6) breaks with a division by 0.", "questions": "In addition to any possible question that has sneaked in the previous forms, I have additional questions\n\n\n- in line 156, the first clause of the sentence seems incomplete \"In the event that no subsequent chosen observations [...], the value of Q etc\";  what condition do the subsequence chosen observations have satisfy?\n\n- in corollary 1.1, it's not very clear what are the conditions for the convergence to work out.  I assume this is the convergence as \\bar Z -> Z.  is this right?\n\n- in line 233, it is said that the complexity attributed to the Bellman upate is linear due to the max and expectation operators.  Since the operators are nested and not independent, shouldn't the complexity be quadratic?\n\n# Minor notes and comments about notation\n\n- although clear enough from context and formalization, it might be worthwhile to make a explicit comment about the fact that deterministic policies are implied by the formalization.\n\n- the expectation in equation (1) should be conditioned on b_t.\n\n- the notation in line 89 \"\\pi_t \\equiv \\pi_t(b_t)\" is a bit confusing;  you're now using \\pi_t to refer not just to the policy, but also to the action determined by the policy.  why not use a_t instead, as that's how a_t was already appropriately defined?\n\n- in equation (7), is the simplified expectation suppsed to be of the next simplified belief \\bar V(b_{t+1}) ?  If so (as it seems), then the expectation should be conditioned on the current belief.\n\n- in equation (7), is it correct that the expectation  is not conditioned on anything?  it seems like that might be correct just due to a combination of the deterministic actions and how simplified expectation is defined, but a clarification would be helpful.  Arguably, the notation of simplified expectation is confusing, and lines (7-8) would be simpler if an explicit sum is used directly.\n\n- in equation (8), it seems like \\bar b(z_{t+1}) is trying to denote the updated belief after integrating the current belief with the new observation z_{t+1}, but this notation was not introduced, and seems in conflict with the notation of b(x) denoting the probabiliy of a state according to the belief.  I think overloading the symbol b this way is fine, as long as both uses have been previously defined appropriately.\n\n- in equation (9), R_max is not defined.  Supposedly this is either the maximal absolute reward achievable by a reachable state-action pair, or the maximal absolute reward achievable by a reachable belief-action pair.  Either way, it should be defined earlier in the preliminaries section.\n\n- in the preliminaries section, the pomdp is defined in terms of R, which supposedly is the reward function, but is never defined.  Later in the section, rewards are instead expressed as r(b, a) for beliefs and r_x(x, a) for states.  In later sections, state rewards are only identified as r(x, a), according to their inputs.  This is fine, but the notation should remain consistent.\n\n- the bound term defined in equation (11) includes the subscript z, in contrast to the one defined in equation (9).  What is the significance of this notation difference?  Similarly, the bound term defined in equation (17) inclues the subscript \"x,z\".  Including the initial bound denoted with the subscript 0, there are not 4 different notations used, which can be confusing, so a clearer explanation would help.  Anything as simple as explicitly describing that e_0 is the initial bound term, e(b) is the belief-only bound term, e_z(b, a) is the belief-action bound term using simplified observations only, and e_{x,z} is the belief-action bound term using simplified states and observations.\n\n- in many equations, the notation for expectation (and limited expectations) appears to be inconsistent, as sometimes the expectation conditions on an action and sometimes it doesn't.  It appears like this may simply be the case the conditional action is shown explicitly when it is not the one which would be chosen deterministically by the policy \\pi, while it is implied when it is the action chosen by the deterministic policy \\pi, but it is not clear whether this is really the case.  I urge the authors to standardize their notation as to avoid confusion and maximize comprehension for the reader.\n\n- Algorithm (1) is never referred to in the text, or described.  Further, both algorithm (1) and (2) have the same name `Algorithm-A`.  Please describe the contents of both.", "limitations": "As noted by the authors themselves, their proposed method had additional requirements compared to other similar methods, specifically the ability to not just simulate/sample states and observations, but also to compute the respective probabilities.  Although this does not automatically disqualify the proposed method, its validity, and the authors' contributions, it is a significant requirement.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The topic addressed by the authors is interesting and novel, and a theoretically driven approach is highly appreciated.  With significant improvements in the presentation and evaluation, this work will become much stronger.", "weaknesses": "The inconsistency of the presentation and notation is a significant drawback to comprehension. The first few sections of the document are well written and clear, however the last few sections seem rushed and with a significant drop in discussion and analysis.  The general impression I get is that the writing of the final parts was rushed due to lack of time.  The mathematical formalisms are for the most part clear, but there are some instances of typos, inconsistent notation, and undefined terms that should be addressed.  I invite the authors to carefully review the math to make sure these issues are addresses.  The algorithm description and discussion in section (4) also may use improvements and clarifications.\n\nThe exact significance of the theoretical erorr bounds for any given limited set Z or X is unclear, as it seems like they may be as large as the real values themselves.  The main theorems of this paper seem to only guarantee optimality in the limit as the limited sets Z and X grow to cover the respective original sets.\n\nThe evaluation setting seems a bit questionable and confusing;  It seems like the main advantage of the proposed method would be in tackling complicated POMDPs that have many possible states and observations.  Instead, the evaluation is performed on the Tiger problem, which contains only 2 possible states and 2 possible observations.  The tiger problem contains complexities that are related to the estimation of values in the highly stochastic and uncertain setting, but in terms of state and observation spaces, it is truly minimal, to the point that it's unclear how a method that is designed around a notion of \"ignoring\" certain states and observations could possibly work well or even at all.  Any clarification would be greatly appreciated.  In addition, a broader discussion about sizes of these problems, and how they related to the possibility of limiting the observation and state spaces would greatly help make the evaluation section more convincing.\n\nIn addition to the above, it seems like the evaluation could be performed on larger problems, since for tiger, discrete-light and baby, the authors claim an optimal action could be found within 1 second.  What kind of problems could be solved as well, if e.g., 10 minutes were allowed?\n\nThe submission title refers to \"anytime deterministic guarantees\", but aside from a single claim that this is achieved, no additional discusssion of the meaning of this term is provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- **Limited state and observation sets** - In the theoretical analysis section, we provide flexibility in determining both the limited state and observation sets, enabling us to generalize the results for various algorithms, as discussed in the methods section. Indeed, the reviewer accurately points out a missing clarification concerning the case of a belief in a posterior node, where all states have zero-density value. However, such a situation does not necessitate a restrictive assumption on the set. This is because, in the case the reviewer suggests both the nominator and the denominator of equation (6) nullify. A statement in the spirit of the ones in rows (128-130) will be integrated to the final manuscript regarding the state space as well.\n\n- **Error bounds** - The bounds are problem- and algorithm-dependent and may be loose or tight. For instance, in the experimental section, specifically in Figure 2, the bounds are initially loose but gradually tightened to the optimal value over time. Generally speaking, deterministic bounds will always be at least as large as the original values before performing any calculation. Still, an adaptive algorithm, such as the one used to generate the data for Figure 2, can recover the optimal policy with an increasing number of iterations.  \nClearly, when recovering the entire reachable belief space, the optimal value is obtained. One can construct a POMDP problem where any approximate solver with deterministic bounds only guarantees optimality with the complete state and observation sets; consider an extreme scenario where all actions have equal value. However, this is generally not required with the use of UDB. Whenever the deterministic upper and lower bounds of two candidate actions do not overlap, there is a clear distinction which action is suboptimal, and its subtree needs no further exploration, as implied in the experimental section, lines (297-299); This is in contrast to current state-of-the-art online POMDP algorithms, where any finite-time stopping condition will not guarantee optimality, as the bounds in those algorithms are probabilistic. We agree with the reviewer that this could be made more explicit for better presentation.\n\n- **Evaluation** - The toy Tiger POMDP problem is required by the need to demonstrate our algorithm convergence to the theoretical value obtained via an exhaustive search algorithm, which is highly inefficient in terms of computational burden and will take much longer to converge to the optimal value. Note that the green-dashed line in Figure 2 corresponds to the optimal value obtained by the exhaustive search, as described in the figure caption and lines (269-273).  \nAs the allowable planning time increases, more challenging POMDPs can be tackled. The time it takes to find the optimal immediate action or policy is problem-dependent.\n\n- **Anytime deterministic guarantees** - This title reflects the contribution of the paper, which are deterministic guarantees of an obtained policy with respect to the optimal value function, which can be obtained anytime, as shown in algorithm-A. Further discussion will be added to the revised version.\n\n- **Q1 - line 156** - No subsequent chosen observation refers to the case where the subtree of a given posterior node is not explored. Thus, the following observations don't have to satisfy any conditions apart from not being chosen for further exploration.\n\n- **Q2 - corollary 1.1** - Although this may happen, in practice, this is not required but only in worst-case scenarios, where the lower and upper bounds continue to overlap in all belief-action nodes until the theoretical tree is fully recovered. As discussed in the comment regarding the \\textit{\"error bounds\"}, often there will be no overlap between bounds for two candidate actions, thus, further exploration in a suboptimal action is not required. \n\n- **Q3 - line 233** - The linear complexity discussed in line 233 only referred to Monte-Carlo solvers, such as POMCP. It is shown in the original paper by Silver et al. [1] (Algorithm 1, procedure Simulate()), that visitation to a posterior node will induce at most $O(|A|)$ complexity, where $|A|$ is the cardinality of the action space. Applying our bounds to POMCP will hinder an additional term to the linear complexity due to the summation over the next observations, as shown in algorithm 2 (lines 19-23). This will result in a linear complexity as well, $O(|A|+|\\bar{\\mathcal{Z}}|)$, where $|\\bar{\\mathcal{Z}}|$ is the simplified observation set. Note that our bounds do not require nested summation at any point of the Simulate procedure, as it updates the bounds incrementally. Similarly, POMCP does not require a complete belief update, which would otherwise require nested summation.\n\n- **Minors** - Minors and notation comments will be considered in the final submission.\n\n[1] David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Advances in Neural Information Processing Systems (NIPS), pages 2164–2172, 2010."}, {"review_id": "dGej9Dk4Q3", "reviewer": "Reviewer_GBcp", "summary": "This paper studies online planning in partially observable Markov decision processes (POMDP). POMDP is known to be a difficult problem, and this paper focuses on how to get anytime deterministic guarantees. This paper proposes to consider a simplified version of the problem by using only a subset of observation space and a subset of state space. They prove the gap between the value functions of an algorithm $\\pi$ in the original problem and in the simplified problem. The gap mainly depends on how many states or observations are dropped in the simplified problem.", "questions": "1. What is $R_{max}$ in equation (9) and (16)? It seems not defined in the paper.\n\n2. Why is there an algorithm 1? It seems not mentioned or used in the paper.\n\n3. What is the difference between $\\epsilon^{\\pi}(b_t)$ in equation (9) and $\\epsilon_z^{\\pi}(b_t,a_t)$ defined in equation (11)? Is $\\epsilon^{\\pi}(b_t)$ just a special case of $\\epsilon_z^{\\pi}(b_t,a_t)$ when the action $a_t = \\pi_t$?", "limitations": "See weaknesses and questions above.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper studies an important and difficult problem, online planning in POMDP.\n\n2. This paper provides an idea to simplified the problem by reducing the state space and observation space, which seems interesting to me.", "weaknesses": "1. The nontriviality and contribution of the results seem limited. Theorem 1 and Theorem 2 basically shows that the value functions of the algorithm $\\pi$ in the original problem and in the simplified problem depends on how many states or observations are dropped in the subset that is used. This seems trivial to me. The relations shown in Theorem 1 and Theorem 2 seem also trivial. The second term in the bracket basically shows the probability that the chosen observations can be received, and then the gap between the value functions depends on the probability of the other observations that cannot be received, i.e., one minus the previous probability. Moreover, is the selection of the subset of states and observations more important and interesting, compared to showing the impact on the gap of value functions of dropped states and observations?\n\n2. The presentation needs to be improved. See my questions below. Moreover, according to the statement in line 88, the policy considered is a deterministic policy, why the random policy is not considered? Around line 105, some intuition about why \"This will allow us to certify the performance of a given policy at the root of the planning tree\" will be easier for me to understand. According to line 121, the subsets could be chosen arbitrarily. But then, how could you guarantee that the probabilities in equations (3), (4) and (5) are well-defined?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- **Contribution** - We believe that the theoretical contribution of an algorithm with deterministic bounds with respect to the optimal value is significant and novel. To the authors' knowledge, no online planning algorithm exists for POMDPs with deterministic guarantees. If the reviewer finds the resulting bounds clear and simple, we consider this a benefit of the suggested method, contributing to its accessibility.    \nIn addition to the theoretical contribution, we suggest a general blueprint of an algorithm that suits in structure to multiple state-of-the-art algorithms, for instance, DESPOT and POMCP and their variants (e.g., AR-DESPOT [1], AdaOPS [2], POMCPOW [3], PFT-DPW [3]), and discuss how our bounds can be attached to many of those algorithms to provide deterministic guarantees. Crucially, these bounds are not merely theoretical but are computed online, with marginal effect on the planning efficiency.  \nIn the first part of this paper, we use sampling of the observations from their respective distribution; this is common in current state-of-the-art algorithms and was empirically shown to perform well in practice. In the second part, we suggest accompanying bounds to a given algorithm, e.g., AR-DESPOT, which depends on the algorithm to select the states and observations. Using the bounds to efficiently choose the subset of states and observations is another interesting direction and is deferred for future research.\n\n- **Deterministic policy** - In this paper, we have decided to address the case of a deterministic policy. We believe the bounds can be easily generalized to the case of stochastic policy using similar derivations, but this is not shown in this paper.\n\n- **Certify performance at the root** - Theorem 2, which examines the discrepancy between the theoretical value function and its simplified version, offers deterministic bounds at the root node, which are computed in practice. In contrast to algorithms that do not provide any finite time guarantees (e.g., POMCP) or algorithms that only provide probabilistic guarantees (e.g., DESPOT), we apply Theorem 2 in practice to determine both the upper and lower bounds of the value functions for every action selection at the root node of the tree. Furthermore, envision a scenario in which an action exists whose lower bound surpasses all other actions' upper bound. In that case, we can identify the optimal action, thus certifying the solution's optimality.\n\n- **Choosing the state-observation subsets** - The subsets may be chosen arbitrarily, while the simplified models in equations (3-5) are not intended to represent valid distribution functions, as stated explicitly in lines (121-136). Instead, they are merely functions approximating the original models, which relax some of the computational burden when exploring the tree.\n\n- **$R_{max}$** - Is the maximum possible reward value. We appreciate the reviewer noticing the missing definition; we will add it in the final version of the paper.\n\n- **Algorithm 1** - Complements Algorithm 2, which describes the recursive procedure. It is required to have a complete overview of the algorithm as it generates some of the required values that are transferred to Algorithm 2. We will add a clarification in the final version.\n\n- **$\\epsilon^{\\pi}(b_t), \\epsilon^{\\pi}_z(b_t, a_t)$** - Indeed as the author noted, $\\epsilon^{\\pi}(b_t)=\\epsilon^{\\pi}_z(b_t, \\pi_t)$.\n\n[1] Nan Ye, Adhiraj Somani, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. JAIR, 58:231–266, 2017.\n\n[2] Chenyang Wu, Guoyu Yang, Zongzhang Zhang, Yang Yu, Dong Li, Wulong Liu, and Jianye Hao. Adaptive online packing-guided search for pomdps. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems (NIPS), volume 34, pages 28419–28430. Curran Associates, Inc., 2021.\n\n[3] Zachary Sunberg and Mykel Kochenderfer. Online algorithms for pomdps with continuous state, action, and observation spaces. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 28, 2018."}, {"review_id": "lnsugJpGnF", "reviewer": "Reviewer_T4b6", "summary": "The paper derives deterministic upper and lower bounds for POMDP. It also proposes a relationship between the computationally intensive optimal value function and a more accessible, simplified approximation.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper provides a strong theoretical analysis", "weaknesses": "The empirical results are limited", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "2rce4hRseK", "reviewer": "Reviewer_3sFn", "summary": "This paper provides theoretical bounds for POMDP planning algorithms and derive a new planning algorithms. The method applies to POMDP with discrete actions and observations spaces where the transition and observation distributions are known. \n\nThe derivation of the bound relies on considering a POMDP with only a subset of observations and states with unnormalized distributions for the transition and the observation. \n\nThe authors proceed to compute the difference in value for this simplified POMDP and the original problem for a given policy and then extend the derivation to the optimal policy in the case of limited observations. This step should address the fact that tree based solver have limited branching in the observations. \n\nThen they update the bounds to address subsets of states. This part addresses the challenge that the belief update requires summing over all possible states which can be expensive. \n\nThe theoretical results are used to improved upon existing tree-based POMDP planners and the resulting algorithm is evaluated on well-known benchmark problems.\n", "questions": "- Does $\\bar{P}(x_t | H_t) = \\bar{b_t}(x_t)$ ?\n\n- What is $H_t^-$? The superscript – is not explained I think.\n\n- Why normalizing the simplified belief? \n\n- Can you clarify the dependency between the bound and the future observations? Why $\\epsilon_z$?\n\n- How is the subset of state determined to derive the bound in theorem 2?\n\n- For theorem 2, does it have the property that if the subset of states tends towards the full state space then the bound goes to 0?\n\n- What time horizon is used to compute the optimal value function in figure 2?\n\n- What do you mean by “non overlapping bounds between actions at the decision time”?\n\n- Is the computation of the bound more expensive than one Bellman backup? \n", "limitations": "Using black-box models for transition and observations can be easier to implement in practice. \n\nThe authors could be a bit more up front in the beginning of the paper about the finite horizon aspect, although it might not matter much in practice since the tree-based method have limited depth anyway.\n\nThe author mention the limitation regarding the computational complexity, however it was not very clear to me if this was a limitation of their method specifically or a general statement since they also mention that the added complexity is negligible compared to AR-DESPOT.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "They are able to leverage the explicit transition model in a tree-based POMDP solver. They derive bounds using a creative idea of a simplified POMDP model ignoring the observations that are not in the planning tree.\n\nThe theoretical bounds seem easier to use than previous probabilistic bounds in AR-DESPOT. However, the computational tractability of the bounds seem to be very reliable on the sampling of the states.\n\nThey show competitive performance on standard POMDP problems against a state of the art algorithm.\n\nThe main approach is quite easy to follow and mostly well motivated. \n", "weaknesses": "Soundness / intuitive justification of the choice of the simplified model. Although the mathematical derivation of the bound seem correct, it would be nice to further motivate this choice. \n\nThe notation is sometimes confusing and could use extra clarification (see questions for specific examples). Equation (6), none of the distributions are normalized, yet the simplified belief is normalized.\n\nIf my understanding is correct, given a POMDP planning tree, and a subset of states per node, the bounds can be calculated and are deterministic guarantees. However, the construction of the tree itself is still probabilistic since sampling is used at two places: sampling the observations, and sampling the subset of states to use. I think it was a bit misleading initially, the bounds are deterministic, but the performance of the algorithm will still be probabilistic. The authors could clarify that aspect, and comment on whether the convergence properties change or would be the same as the underlying algorithm using the bounds. \n\nThe paragraph line 215 was a very clear explanation of how to perform the calculation of the bound and could come sooner.\n\nThere are some inaccuracies in the complexity discussion: “the Bellman update is linear in terms of time complexity”. This statement does not make sense.\n\nIt would have been very strong if the bounds had been added to POMCP or POMCPOW as well to show that the theoretical results indeed applies to different algorithms.\n\nI did not understand the discussion about why DB-DESPOT did not perform better on the Laser tag problem. \n\nIn the supplementary material, it wouldn’t hurt to add a few extra steps between 4 and 7 to make it easier on the reader. Specifically between step (6) and (7).\n\n\nMinor typos and formatting:\n- In the background in the belief equation, take $P(z_t \\mid x_t)$ out of the sum for easier mapping with Equation (6)\n- Equation (6) should be $b_{t+1}(x_{t+1})$\n- Equation (28) in supplementary material seems wrong.\n- L208 A is outlined.\n- L220 seeing->seen\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- **Probabilistic performance** - The reviewer is correct that the algorithmic examples shown in this paper lead to probabilistic performance with deterministic guarantees. In practice, the performance can become deterministic with a deterministic selection of the states and observations. However, this is not explored in this paper and may be an exciting topic for a follow-up paper.\n\n- **Complexity analysis of Monte-Carlo algorithms with our bounds** - Lines (233-238) refers to the Bellman-like update of our bounds using online Monte-Carlo algorithms such as POMCP. Since the updates at each posterior node in a POMCP algorithm are at most $O(|A|)$, our bounds add another term to the linear complexity to an overall of $O(|A|+|\\bar{\\mathcal{Z}}|)$, where $|\\bar{\\mathcal{Z}}|$ is the simplified observation set. We agree with the reviewer that the phrasing may be misleading; this point will be clarified in the final version of the paper.\n\n- **Additional algorithms** - As discussed in the paper, our bounds are also applicable to the POMCP algorithm; we will provide a pseudo-code of our approach to POMCP, which will give deterministic guarantees on the result of the algorithm.\n\n- **Convergence of algorithm** - The bounds discussed in this paper provide the worst-case gap between the simplified and the theoretical value function. When an action $a$ has it lower bound surpasses the upper bounds of all other actions (i.e., their bounds interval do not overlap), it is theoretically guaranteed that action $a$ is optimal. However, before that, when given little time for planning,  the optimal action is unknown. Since multiple actions may be optimal, selecting one can be made based on different heuristics to break the tie. For instance, heuristics may include the action with the highest lower bound, the highest upper bound, or the action with the highest number of visitations. In such scenarios, the selected action is not guaranteed to be optimal (as with LaserTag) but is guaranteed to have a bounded difference from the optimal value. In this example, the AR-DESPOT heuristic was empirically shown to perform better.\n\n- **Equation (28)** - The proof of Lemma 1 in the supplementary refers to the case where only observations are simplified. In that case, $\\epsilon^\\pi (b_T, a_T) \\triangleq 0$ since no observations are involved, and the immediate reward is computed entirely. A further clarification will be added in the final manuscript.\n\n- **Further answers, corresponding to the order of the Questions section:**\n  + $\\bar{\\mathbb{P}}(x_t\\mid H_t) \\triangleq \\bar{b}_t(x_t)$ as shown in equation (6).\n  + $H_t^-$ is the propagated belief, as shown in line 82.\n  + The subscript $z$ in $\\epsilon^{\\pi}_z(\\cdot,\\cdot)$ was mainly to disambiguate the action dependency of that function from $\\epsilon^{\\pi}(\\cdot)$.\n  + In theorem 2, the subset can be chosen arbitrarily. For instance, using a POMCP-like approach, it could be determined online by sampling or offline before planning. The choice does not affect the bounds' correctness but may affect how loose the bounds are.\n  + Yes, as the full subset of states tends to the complete state space, the bound will converge to zero, thus recovering the theoretical value function.\n  + The horizon in that experiment was limited to five steps.\n  + As mentioned earlier, each action has different upper and lower bounds. When the interval determined by the lower- and upper-bound for action $a$ does not intersect with the bound interval of any other action, we say that the bounds of action $a$ do not overlap. For instance, when the lower bound of action $a$ is higher than the upper bound of all other actions.\n  + Generally no. Compared to the complete Bellman update, our algorithm improves the computational complexity by performing a Bellman update with approximations. In practice, algorithms such as the original AR-DESPOT algorithm perform approximate Bellman-update in the back-propagation phase, which costs $O(|A|+|\\bar{\\mathcal{Z}|})$. DB-DESPOT(ours) performs similar calculations and thus adds no additional computational cost."}]

Author rebuttal:
We thank all reviewers for their constructive review, which will help us improve the paper's presentation. Additionally, we acknowledge some missing notations and clarifications, which will be fully addressed in the final manuscript.

Meta-review: This paper derives and integrates deterministic bounds in online POMDP planning algorithms (such as POMCP and DESPOT). 

As pointed out by the authors, current guarantees are only probabilistic so developing stronger bounds for online planning problems is an important problem. As a result, the method is theoretically interesting and the resulting integration into DESPOT creates a practical algorithm with strong performance. 

Nevertheless, there are concerns about the presentation and experiments in the paper. As discussed by the reviewers, the paper should improve the clarity of the approach as well as the assumptions needed for the method. Results on larger problems would greatly strengthen the paper but, at the least, the current results should be clarified with improved discussion.
 
The author response was helpful about these issues but there are significant updates that need to be integrated into the paper.
Decision: Accept (poster)