# Adaptive Information Belief Space Planning

Moran Barenboim1 Vadim Indelman21Technion Autonomous Systems Program
2Department of Aerospace Engineering
${}^{{}^{{}^{\ }}}$Technion - Israel Institute of Technology, Haifa 32000,
Israel<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Reasoning about uncertainty is vital in many real-life autonomous systems.
However, current state-of-the-art planning algorithms cannot either reason
about uncertainty explicitly, or do so with a high computational burden. Here,
we focus on making informed decisions efficiently, using reward functions that
explicitly deal with uncertainty. We formulate an approximation, namely an
abstract observation model, that uses an aggregation scheme to alleviate
computational costs. We derive bounds on the expected information-theoretic
reward function and, as a consequence, on the value function. We then propose
a method to refine aggregation to achieve identical action selection with a
fraction of the computational time.

##  1 Introduction

Planning under uncertainty is a recurrent aspect in many practical autonomous
systems. The uncertainty stems from the fact that in many real-life scenarios
the state of the agent and the surrounding world is not known precisely. Some
of the most common sources for uncertainty include sensor noise, modeling
approximations and the unknown environment of the agent. A common way to
decision making while considering uncertainty is to formulate the problem as a
partially observable Markov decision process (POMDP).

Since in POMDPs states are unobserved directly, all past action-observation
pairs, coined history, serve as an alternative for the decision making.
Accumulating all the history over long trajectories may be expensive to
memorize. Instead, a common approach is to calculate a distribution over the
unobserved states, also known as belief states. In most POMDP formulations,
belief states are assumed to be sufficient statistics, such that they are
equivalent to the history when considering decision making Thrun et al.
(2005). An optimal solution to the POMDP is a policy that maximizes some
objective function, usually defined as the sum of expected future reward
values over the unknown states. A policy then maps each belief state to an
action. Unfortunately, the exact solution of a POMDP is computationally
infeasible for many practical POMDPs Papadimitriou and Tsitsiklis (1987).

A reward in a POMDP is a function that commonly receives a state as an input,
and maps each state to a scalar value. However, when the reward receives a
belief as an input, the problem formulation is considered an extension to
POMDP, called $\rho$-POMDP Araya et al. (2010), POMDP-IR Spaan et al. (2015)
or Belief Space Planning (BSP) Platt et al. (2010), Van Den Berg et al.
(2012), Indelman et al. (2015). An objective function on the distribution
itself allows reasoning about the uncertainty directly, which arises in many
problems such as active localization Burgard et al. (1997), information
gathering Hollinger and Sukhatme (2014) and active SLAM Kim and Eustice
(2014). Although POMDP formulation allows to reason about uncertainty
implicitly, it is insufficient for problems where the goal is defined over a
distribution. For instance, consider the active localization problem, the goal
of the agent is not to reach a certain destination, but to reduce uncertainty
about its state.

Figure 1: An illustration of our approach. The blue clusters correspond to a
single evaluation of the reward function across different posterior nodes,
which is faster to compute. Then, the algorithm initiates a refinement
procedure; The refined clusters guarantee the same action selection as the
original reward evaluation.

Common approaches for measuring uncertainty are information-theoretic
functions, such as entropy, information gain and mutual information. For
continuous distributions, which are of interest in this paper, calculating the
exact values of information-theoretic rewards involves intractable integrals
in the general case. Thus, they are amenable to different approximations, such
as kernel density estimation (KDE), Voronoi diagrams Miller (2003) or
sampling-based approximations Boers et al. (2010). Unfortunately, all such
approximations are expensive to compute, as they require quadratic costs in
the number of samples and are usually the bottleneck of planning algorithms.

Since finding an exact solution to a POMDP is intractable, approximate
algorithms have been developed. Tree search algorithms, which are the main
focus of this paper, are a prominent approach for such approximation; Instead
of considering all possible belief states, tree search algorithms reduce the
belief space to a reachable subset, starting from the prior belief node. In
this paper, we consider an online paradigm, where instead of calculating a
policy in advance, the planner needs to find an (approximately-) optimal
action, by building a tree every time step. POMCP Silver and Veness (2010), is
a tree search algorithm, which extends MCTS Browne et al. (2012) to the POMDP
framework; It is considered as a state-of-the-art (SOTA) algorithm, however,
it is limited to a discrete state, action and observation spaces. DESPOT
Somani et al. (2013) and its descendants Ye et al. (2017); Garg et al. (2019)
consider $\alpha$-vectors in their derivations and are thus limited to reward
functions that are linear in the belief. However, information-theoretic
functions are usually not linear with respect to the belief and thus not
supported by these approaches.

POMCPOW Sunberg and Kochenderfer (2018) is an extension of the POMCP
algorithm, to deal with continuous action and observation spaces. In POMCPOW,
each belief node is represented by a set of particles. The number of particles
in each node is determined by the number of traversals within this node in
planning. Due to the exploratory nature of the algorithm, most belief nodes
contain only a few particles, which are unsuitable to approximate belief-
dependent reward. In PFT-DPW algorithm Sunberg and Kochenderfer (2018), each
expanded node in the belief tree contains the same number of particles and is
better suited for belief-dependent rewards. A recent result by Hoerger and
Kurniawati (2021) shows comparable or better performance than current SOTA
algorithms, by considering trajectories of particles and using a weighted
particle filter to extract trajectories for any observation, but suffers from
the same problem as POMCPOW. Flaspohler et al. (2019) uses MCTS with
information-theoretic as heuristic over state-dependent objective function for
information gathering.

More closely related to our work is Thomas et al. (2021), which interleave
MCTS with $\rho$-POMDP. Their approach considers a discrete observation space.
In each traversal of the tree, their algorithm adds a fixed set of particles
propagated from the root node, which results in an increased number of samples
at each node as the algorithm progresses. According to the authors, the main
motivation is a reduced asymptotic bias. Given a time budget, a significant
reduction in the number of nodes explored is observed by the authors of Thomas
et al. (2021), which in turn impacts the quality of the policy. Fischer and
Tas (2020) consider a belief-dependent reward, in which they build upon PFT-
DPW Sunberg and Kochenderfer (2018). Instead of maintaining the same particle
set in each posterior node, they reinvigorate particles in every traversal of
the posterior node. Then, they propose to average over different estimations
of the reward function. Fischer and Tas (2020) suggest estimating the reward
function using KDE, which scales quadratically with the number of state
samples. Sztyglic and Indelman (2021) consider a sampling-based approximation
to evaluate differential entropy. They propose a simplification procedure that
alters the number of state samples and prune sub-optimal action branches,
using bounds relative to the non-simplified estimator. In a follow-up work,
Sztyglic et al. (2021) propose an approach to interleave simplification with
MCTS while maintaining tree-consistency, thereby increasing computational
efficiency. Our work is complementary to these works and can be combined.

In this paper, we show an approach to alleviate the computational burden of
calculating reward at each belief node of the tree, while guaranteeing an
identical solution. We focus on Shannon’s entropy and differential entropy,
alongside state-dependent reward functions. Our approach relies on clustering
different nodes and evaluating an approximated belief-dependent reward once on
this entire cluster, that is, all the nodes within a cluster share the same
reward value. As a result, the estimated value function is affected. To relate
the approximated value function to the one that would originally be
calculated, each node maintains a lower and upper bound on the value function.

Consequently, our main contributions are as follows. First, we introduce an
abstract observation model. We use the model to form an abstraction of the
expected reward, namely, a weighted average of state-dependent reward and
entropy. Then, using the abstract model, we show how computational effort is
alleviated. Second, we derive deterministic lower and upper bounds for the
underlying expected reward values and the value function. Third, we introduce
a new algorithm, which is able to tighten the bounds upon demand, such that
the selected action is guaranteed to be identical to the non-simplified
algorithm. Last, we evaluate our algorithm in an online planning setting and
show that our algorithm outperforms the current state-of-the-art.

##  2 Preliminaries

###  2.1 POMDP Formulation

POMDP is defined as a 7-tuple, $(S,A,O,T,Z,R,b_{0})$, where, $S,A,O$ denotes
the state, action and observation spaces respectively. $T(s^{\prime}\mid s,a)$
is the transition density function, $Z(o\mid s)$ is the observation density
function and $b_{0}$ denotes the initial belief distribution. A history,
$H_{t}$, is a shorthand for all past action-observation sequences
$(a_{0},o_{1},\dots,a_{t-1},o_{t})$ up to current time. We use $H_{t}^{-}$ to
denote the same history, without the last observation, i.e.
$H_{t}^{-}=(a_{0},o_{1},\dots,a_{t-1})$. Similarly, $b_{t}^{-}$ is a belief
conditioned on $H_{t}^{-}$.

In this work, we focus on a reward function defined as a weighted sum of
state-dependent reward and entropy,

$R(b,a,b^{\prime})=\omega_{1}\mathbb{E}_{s\sim
b^{\prime}}\left[r(s,a)\right]+\omega_{2}\mathcal{H}(b^{\prime}),$ (1)

where $b^{\prime}$ is the subsequent belief to $b$ and $\mathcal{H}(\cdot)$ is
either differential entropy or Shannon’s entropy. The dependence of (1) on
both $b$ and $b^{\prime}$ stems from the definition of the differential
estimator, as will be shown in Section 3.2. A policy, $\pi(\cdot)$, maps a
belief to an action to be executed. Given a belief at time $t$, each policy
corresponds to a value function,

$V^{\pi}(b_{t})=\mathbb{E}_{o}\left[\sum\nolimits_{\tau=t}^{\mathcal{T}-1}R(b_{\tau},\pi_{\tau}(b_{\tau}),b_{\tau+1})\right],$
(2)

which is the expected cumulative reward following the policy, $\pi$.
Similarly, an action-value function,

$Q^{\pi}(b_{t},a_{t})=\mathbb{E}_{o_{t+1}}\left[R(b_{t},a_{t},b_{t+1})+V^{\pi}(b_{t+1})\right],$
(3)

is the value of executing action $a_{t}$ in $b_{t}$ and then following the
policy $\pi$.

###  2.2 Belief-MDP

A belief-MDP is an augmentation of POMDP to an equivalent MDP, by treating the
belief-states in a POMDP as states in the Belief-MDP. Subsequently, algorithms
developed originally for MDPs can be used for solving POMDPs or BSP problems
with slight modifications, a property that we exploit in this paper.

##  3 Expected Reward Abstraction

In this section we introduce the notion of an abstract observation model and
show how this model can be utilized to ease the computational effort. We then
derive bounds on the expected reward and, as a consequence, on the value
function.

We start this section with a theoretical derivation, where we assume the
reward can be calculated analytically. This appears in special cases, e.g.
when the reward is solely entropy and the belief is parametrized as a Gaussian
or when the state space is discrete. In this part we assume the observation
space is discrete and thus the expected reward can be calculated analytically.
In the second part of this section, we relax those assumptions. Generally, the
observation and state spaces can be continuous and the belief may be
arbitrarily distributed. To deal with such cases, we derive an estimator of
the expected reward, in which the belief is approximated by utilizing a
particle filter.

For both the discrete and continuous observation spaces, we present an
abstract observation model,

######  Definition 1 (Abstract observation model).

An abstract observation model assigns a uniform probability to all
observations within a single set,

$\bar{Z}(o^{j}\mid s)\doteq\frac{1}{K}\sum_{k=1}^{K}Z\left(o^{k}\mid s\right)\
\ \ \ \ \forall j\in[1,K]$ (4)

where $Z\left(o^{k}\mid s\right)$ corresponds to the original observation
model over different observation realizations, $o^{k}$, and $K$ denotes the
cardinality of observations within that set.

The abstract model aggregates $K$ different observations and replaces the
original observation model when evaluating the reward, see Figure 2. In the
continuous case we revert to observation samples, thus the summation in (4)
corresponds to different observation samples. A more precise explanation on
the continuous case will be given in Section 3.2.

Figure 2: An abstraction of the observation model: (a) original discrete
observation model with $N_{o}$ observations. (b) Abstract discrete observation
model with $C$ clusters. (c) Sample set from the original continuous
observation model, with $N_{o}$ observations. (d) Abstract sample set with $C$
clusters.

###  3.1 Discrete Observation Space

Since calculating the exact value of a reward function in every belief node is
expensive, we now formulate an approach to evaluate reward once for an entire
set of $K$ posterior beliefs. Such an abstraction results in a decreased
number of reward evaluations in planning. We show that when constructing the
aggregation scheme as a uniform distribution over a set of observations, one
can achieve tight upper and lower bounds on the expected entropy, defined as
$-\mathbb{E}\left[\sum_{s}b(s)log(b(s))\right]$. Moreover, we show that
abstraction for the expected state-dependent reward does not affect its value,
which remains identical with and without abstraction.

Denote the cardinality of observation space with $N_{o}$, we partition the
observations to $C$ clusters and denote the number of observations within each
cluster as $K$, see Figure 2. Generally, each cluster may contain a different
number of observations, $N_{o}=\sum_{c=1}^{C}K(c)$; For clarity, we assume $K$
is identical for all clusters, but the results below are easily extended to
the more general case.

Our _key result_ , stated in the lemma below, corroborates the intuition that
utilizing an abstract observation model results in a reduced number of reward
evaluations.

######  Lemma 1.

Evaluation of the expected reward with an abstract observation model, (4),
requires only $C$ evaluations of the reward, instead of $N_{o}$, where
$C=\frac{N_{o}}{K}$. That is,

$\displaystyle\sum\nolimits_{n=1}^{N_{o}}\bar{\mathbb{P}}\left(o_{t+1}^{n}\mid
H_{t+1}^{-}\right)R\left(b_{t},a_{t},\bar{b}_{t+1}\right)=$ (5) $\displaystyle
K\sum\nolimits_{c=1}^{C}\bar{\mathbb{P}}\left(o_{t+1}^{c\cdot K}\mid
H_{t+1}^{-}\right)R\left(b_{t},a_{t},\bar{b}_{t+1}\right).$

###### Proof.

see appendix A.1. ∎

Here, $o_{t+1}^{c\cdot K}$ denotes a single representative observation of the
cluster $c$ and

$\displaystyle\bar{\mathbb{P}}\left(o^{n}\mid H^{-}\right)\doteq\sum_{s\in
S}\bar{Z}(o^{n}\mid s)b^{-},$ (6)
$\displaystyle\bar{b}\doteq\frac{\bar{Z}(o^{n}\mid
s)b^{-}}{\sum_{s^{{}^{\prime}}\in S}\bar{Z}(o^{n}\mid s^{{}^{\prime}})b^{-}}\
.$ (7)

For the continuous state case, simply replace summations with integrals.
Furthermore, the expected state-dependent reward remains unchanged when
evaluated over abstract belief and expectation,

######  Lemma 2.

The value of the expected state-dependent reward is not affected by the
abstraction shown in (4), i.e.,

$\displaystyle\mathbb{E}_{o}\left[\mathbb{E}_{s\sim
b}\left[r\left(s,a\right)\right]\right]=\bar{\mathbb{E}}_{o}\left[\mathbb{E}_{s\sim\bar{b}}\left[r\left(s,a\right)\right]\right].$
(8)

###### Proof.

see appendix A.2. ∎

Note that $\\{\mathbb{E}_{o},\mathbb{E}_{b}\\}$ and
$\\{\bar{\mathbb{E}}_{o},\mathbb{E}_{\bar{b}}\\}$ correspond to expectations
with the original and abstract observation models, (6) and (7).

We now transition to the main theorem of this paper. Using (4) as the
abstraction mechanism, we show that,

######  Theorem 1.

The expected entropy is bounded from above and below by,

$0\leq\bar{\mathbb{E}}_{o}\left[\mathcal{H}\left(\bar{b}\right)\right]-\mathbb{E}_{o}\left[\mathcal{H}\left(b\right)\right]\leq
log(K).$ (9)

###### Proof.

see appendix A.3. ∎

The difference between the expected entropy and the abstracted one is bounded
from below by zero. Since the entropy evaluates the uncertainty, the
interpretation of this result is quite intuitive; the uncertainty cannot
reduce when using abstracted models. The upper bound depends on the number of
observations we choose to abstract, $K$. When $K=1$, that is, each cluster
contains a single observation, both the upper and lower bounds are zero and
the abstract expected entropy equals the original expected entropy. Note that
from (1), (8) and (9) it follows that,

$0\leq\\!{\bar{\mathbb{E}}}_{o}\left[R\left({b},a,{\bar{b}}^{\prime}\right)\right]\\!-\\!{\mathbb{E}}_{o}\left[R\left({b},a,{b}^{\prime}\right)\right]\leq\omega_{2}log(K).$
(10)

We now generalize those results and show that the value function is bounded.
An abstract value function is defined as,

$\bar{V}^{\pi}(b_{t})=\bar{\mathbb{E}}_{o_{t+1}}\left[R(b_{t},\pi_{t}(b_{t}),\bar{b}_{t+1})\right]+\mathbb{E}_{o_{t+1}}\left[\bar{V}^{\pi}(b_{t+1})\right].$
(11)

As a direct consequence of (10) and (11),

######  Corollary 1.1.

The difference between the original value function and the abstract value
function is bounded by,

$0\leq\bar{V}^{\pi}(b_{t})-V^{\pi}(b_{t})\leq\mathcal{T}\cdot\omega_{2}log(K).$
(12)

###### Proof.

see appendix A.4. ∎

This result allows us to bound the loss when applying observation abstraction.
In Section 4, we devise an algorithm that adapts the bounds so that the same
best action will be chosen, with and without abstraction, while expediting
planning time.

###  3.2 Continuous Observation Space

Planning with entropy as reward over a continuous observation space is more
cumbersome as it requires calculation of,

$\displaystyle\mathbb{E}[\mathcal{H}(b_{t})]=-\int_{o_{t}}\mathbb{P}(o_{t}\mid
H_{t}^{-})\int_{s_{t}}b(s_{t})log(b(s_{t})).$ (13)

First, the probability density function of the belief may be arbitrary, so the
integral over the state has no closed-form expression. Moreover, usually,
there is no access to the density functions due to the difficulty of exact
Bayesian inference, but only to samples. Second, even if the differential
entropy could be evaluated, integrating over the observation space makes this
calculation intractable. Consequently, it is only feasible to estimate the
value function, here denoted by $\hat{V}^{\pi}(\cdot)$. To approximate the
posterior belief at each time step, we employ the commonly used particle
filter, see e.g. Thrun et al. (2005). Inspired by derivations in Boers et al.
(2010), we estimate (13) using state samples obtained via a particle filter.
We then sample observations using the given observation model, conditioned on
the state particles. This is a common procedure in tree search planning, see
for example Sunberg and Kochenderfer (2018). Using the state and observation
samples, we derive an estimator to (13),

$\displaystyle\hat{\mathbb{E}}[\mathcal{H}(\hat{b}_{t})]=-\hat{\eta}_{t}\sum_{m=1}^{M}\sum_{i=1}^{N}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}$ (14) $\displaystyle\cdot
log\left(\frac{Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)\sum_{j=1}^{N}T\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}}{\sum_{i^{\prime}=1}^{N}Z\left(o_{t}^{m}\mid
s_{t}^{i^{\prime}}\right)q_{t-1}^{i^{\prime}}}\right),$

where $\hat{b}\doteq\\{q^{i},s^{i}\\}_{i=1}^{N}$ denotes the belief particles
with weights $q^{i}$; $M,N$ are the number of observation and state samples
accordingly and
$\hat{\eta}_{t}=\frac{1}{\sum_{m=1}^{M}\sum_{i=1}^{N}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}}$. See appendix A.5 for the full derivation, and
Boers et al. (2010) for a discussion about convergence of the differential
entropy estimator to the true differential entropy value. The estimator for
the expected entropy of $\hat{b}_{t}$, (14), is also a function of
$\hat{b}_{t-1}$, hence the reward structure $R(\hat{b},a,\hat{b}^{\prime})$.

Similar to the discrete case, we use an abstract observation model (4), where
instead of discrete observations, summation is done over observation samples,
see Figure 2. We obtain upper and lower bounds that resemble the results (8),
(9) and (12) but depend on the approximate expected reward value. Combining
results on the expected state-dependent reward and expected entropy,

######  Theorem 2.

The estimated expected reward is bounded by,

$0\leq\\!\hat{\bar{\mathbb{E}}}_{o}\left[R\left(\hat{b},a,\hat{\bar{b}}^{\prime}\right)\right]\\!-\\!\hat{\mathbb{E}}_{o}\left[R\left(\hat{b},a,\hat{b}^{\prime}\right)\right]\leq\omega_{2}log(K).$
(15)

###### Proof.

see appendix A.6. ∎

Here, $\hat{\bar{b}}^{\prime}\doteq\\{\bar{q}^{i},s^{i}\\}_{i=1}^{N}$ denotes
a particle set with abstract weight, $\bar{q}^{i}$, due to the abstract
observation model (4), and

$\hat{\bar{\mathbb{E}}}_{o}\left[\cdot\right]\doteq\sum_{m=1}^{M}\sum_{i=1}^{N}\bar{Z}(o^{m}\mid
s^{i})q_{t-1}^{i}\left[\cdot\right].$ (16)

$\hat{\mathbb{E}}_{o}[\cdot]$ and $\hat{b}^{\prime}$ are defined similarly by
replacing the abstract model with the original one. As a result of Theorem 2,
the estimated value function is bounded,

######  Corollary 2.1.

The difference between the estimated value function and the abstracted value
function bounded by,

$0\leq\hat{\bar{V}}^{\pi}(b_{t})-\hat{V}^{\pi}(b_{t})\leq\mathcal{T}\cdot\omega_{2}log(K).$
(17)

###### Proof.

see appendix A.7. ∎

The computational complexity of the expected reward in (15) is dominated by
complexity of the expected entropy, (14), which is $O(MN^{2})$. By choosing
$K=M$ the computational complexity of the abstract expected reward diminishes
to $O(N^{2})$ with bounded loss.

##  4 Algorithms

Since the derivations in previous sections are agnostic to which algorithm is
being used, we begin this section by presenting the contribution of our work
to an existing algorithm. Then, based on insights gained from the examined
algorithm, we propose modifications to improve the current algorithm. In the
following section, we show that the changed algorithm empirically surpasses
the current SOTA in performance throughout our experiments by a significant
margin.

###  4.1 Baseline Algorithms

Sparse sampling (SS) algorithm, introduced in Kearns et al. (2002), provides
$\epsilon$-accuracy guarantee on the solution at a finite time. However, since
it searches the tree exhaustively, the convergence is quite slow in practice.
On the other hand, MCTS algorithm Browne et al. (2012) has the desirable
property of focusing its search on the more promising parts of the tree, but
was shown to have poor finite-time performance, requiring an
$exp(exp(...exp(1)...))$111A composition of D-1 exponentials, where D denotes
tree depth. iterations in the worst-case scenario Munos (2014). To combat the
worst-case running time of MCTS and the slow running time of SS, Forward
Search Sparse Sampling (FSSS) Walsh et al. (2010) was introduced. It was shown
to achieve comparable performance to MCTS with performance guarantees under
finite computational budget as in SS.

###  4.2 FSSS with Information-Theoretic Rewards

In its original version, FSSS introduced lower and upper bounds on the
estimate of the $Q^{d}(s,a)$ function. In contrast to SS, FSSS builds the tree
incrementally, where each iteration begins at the root node and proceeds down
to horizon $H$, to obtain an estimate for the action-value function. Whenever
a new node is expanded, its direct action nodes are created alongside $M$
randomly sampled children for each of them. The branching factor, $M$, is a
predefined hyper-parameter. After performing $(|A|\cdot M)^{d}$ iterations,
FSSS builds the same tree as SS but enjoys anytime properties. Moreover, FSSS
may benefit from reduced computation by utilizing upper and lower bounds and
pruning sub-optimal actions.
When the reward is defined as an information-theoretic function, such as
differential entropy, upper and lower bounds on the value function cannot be
determined a-priori, thus no pruning can be made. Nonetheless, our
experimental evaluations suggest that FSSS still serves as a strong baseline.

###  4.3 Adaptive Information-FSSS

We coin our new algorithm Adaptive Information FSSS (AI-FSSS). Given the same
number of iterations, the actions obtained by the two algorithms are
identical. The pseudo-code is presented in appendix B. As in FSSS, we build
the tree incrementally, where each iteration adds a new trajectory to the
tree. The algorithm constructs an abstract belief tree, where a set of $K$
posterior beliefs share the same reward upper and lower bounds relating it to
the underlying reward value. This is done by immediately sampling $K$
observation samples whenever a new action node expanded, followed by a
computation of the abstract reward. Based on Theorem 2 we derive an
AdaptBounds procedure, that adapts the number of aggregated observations.
Bounds adaptation halts whenever the highest lower bound,
$\underset{a}{\max}LB(b_{init}a)$, is higher than the upper bound of any other
action. This results in the same action selection for the full FSSS and our
adaptation, AI-FSSS.

###  4.4 Introducing Rollouts to AI-FSSS

A direct adaptation of FSSS to AI-FSSS would abstract $K$ observations in each
new action node up to the full depth of the tree, $d_{max}$. However, when the
time budget is limited, it might not be the best strategy, since the
abstraction of deeper belief nodes of the tree may never be visited twice, but
might need to be refined afterward. Instead, we propose to perform rollout
whenever a new action node is met for the first time. This is similar to MCTS,
where rollouts are used to get an estimate of the action-value function. This
approach will lead to abstraction only for expanded nodes, which are the ones
in proximity to the root node. As the number of iterations grows, action nodes
are expanded gradually and more abstract belief nodes are added to the tree.
Given that the number of iterations equals the number of action nodes in the
original Sparse-Sampling tree, followed by AdaptBounds procedure, both
algorithms converge to the same solution.

##  5 Experiments

(a)

(b)

(c)

Figure 3: Evaluating performance of AI-FSSS. (a-b): Running time comparison of
FSSS, and our adaptation, AI-FSSS without rollouts. Both algorithms end with
the same action selection, but with increasing difference in computation time.
(a) Different observation branching factor, with $20$ particles. (b) Different
number of state particles, with $4$ observation after each action node. (c)
Average total return of AI-FSSS with rollouts in 2D Light-Dark with obstacles.

The goal of the experiment section is to evaluate the influence of the
abstraction mechanism on the planning performance. We examined both the time
difference and the total return. All algorithms use a particle filter for
inference, the choice of the particle filter variant is independent of our
contribution. All experiments were performed on the common 2D Light Dark
benchmark, where both the state and observation spaces are continuous; see an
illustration in Figure 4. In this problem, the agent is required to reach the
goal while reducing localization uncertainty using beacons scattered across
the map. The reward function is defined as a weighted sum of distance to goal,
which is state-dependent reward and entropy, as in (1). Due to space
limitations, domain and implementation details are deferred to appendix C.

###  5.1 Time Performance Evaluation

We compared the basic FSSS with our adaptation, AI-FSSS, in terms of time
efficiency. As stressed in previous sections, both algorithms are guaranteed
to select the same action. To ensure that both algorithms built the same tree,
rollouts were avoided and each iteration proceeded until the maximum depth of
the tree. We note that the expected return was inferior to our full algorithm,
which is evaluated next. Technically, we also fixed the random numbers by
selecting the same seed in both algorithms.

Observation branching factor. In the first experiment, we fixed the number of
state particles to $n=40$, and examined the influence of different branching
factors over the observation space, see Figure 3. The algorithms were limited
to 20,000 iterations before performing an action. The computation time
indicates an empirical average of over 1,000 simulations, approximating the
mean time for a full trajectory. As one would expect, the more observations
are clustered in each aggregate, the more time-efficient AI-FSSS compared to
the basic FSSS. To obtain the same best action in both algorithms, the tree
construction was followed by a refinement step, see appendix B, AdaptBounds.
In the adapt-bounds step, we incrementally reduce the number of aggregates, so
in the worst-case, every aggregate will only hold a single observation and
thus recover the FSSS tree. This will occur only in a degenerate case, where
all action-values $Q(b_{0},\cdot)$ will have the same value, which is rarely
the case.

Number of particles. In our second experiment, we evaluated the effect of the
number of particles representing the belief. Here, the number of observations
was fixed to $M=4$. Figure 3 shows the change in computational speed with
regard to the number of particles in our experiments. Both algorithms
performed 1,000 simulations; The empirical running time mean and standard
deviation are presented in the graph.

Figure 4: An illustration of the environment being used in our experiments.

###  5.2 Total Return Evaluation

In the experiments where only few particles were used, e.g. 5, the efficiency
gain was mild. In a setting where few particles are sufficient, computing the
entropy is relatively cheap compared to other parts of the algorithm, which
become relatively more significant (e.g. the different $\max$ operators).
However, we observed that the burden became significant even in a mild number
of particles, e.g. when $n=20$ the speed-up ratio more than doubled while only
a modest cluster size of 4 observations was used.

In contrast to the previous experiments, in this section we evaluate the full
version of AI-FSSS, that is, with rollouts for every newly expanded action
node. We evaluated performance against FSSS Walsh et al. (2010) and PFT-DPW
Sunberg and Kochenderfer (2018), by augmenting a POMDP to a belief-MDP. In
this setting, each node holds $n$ particles. All algorithms had a 1-second
limitation for planning before each interaction with the environment. Except
for PFT-DPW, the algorithms shared the same observation branching factor,
$M=4$. PFT-DPW opens new observation nodes as time progresses, depending on
hyper-parameters defined by the expert. We identified $k_{o}$ as the dominant
hyper-parameter that controls the number of observations in our experiment. We
experimented with both $k_{o}=4$ and $k_{o}=2$ in order to keep a comparable
observation branching size. The better result is shown here, see Figure 3.

Each algorithm performed 1,000 full trajectories in the environment, each
containing 25 steps. As suggested in Figure 3, our algorithm performed better
than PFT-DPW and FSSS when information-gathering was an explicit part of the
task.

##  6 Conclusions

This paper deals with online planning under uncertainty with information-
theoretic reward functions. Information-theoretic rewards facilitate explicit
reasoning about state uncertainty, contrary to the more common expected reward
over the state. Due to the added computational burden of evaluating such
measures, we consider an observation model abstraction that improves
efficiency. We derived analytical bounds with respect to the original reward
function. Additionally, we introduced a new algorithm, AI-FSSS, that contracts
the bounds upon need, and is guaranteed to select identical action as the
vanilla algorithm. Finally, we conducted an empirical performance study with
and without observation abstraction. Our results suggest a significant speed-
up as the cardinality of the particle set and the observation-branching factor
increases while yielding the same performance.

## Acknowledgements

The research presented in this paper was partially funded by the Israel
Science Foundation (ISF), by US NSF/US-Israel BSF, by the Isarel Ministry of
Science and Technology (MOST) and by the Israeli Smart Transportation Research
Center (ISTRC).

## References

  * Araya et al. [2010] Mauricio Araya, Olivier Buffet, Vincent Thomas, and Françcois Charpillet.  A pomdp extension with belief-dependent rewards.  In Advances in Neural Information Processing Systems (NIPS), pages 64–72, 2010.
  * Boers et al. [2010] Y. Boers, H. Driessen, A. Bagchi, and P. Mandal.  Particle filter based entropy.  In 2010 13th International Conference on Information Fusion, pages 1–8, 2010.
  * Browne et al. [2012] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton.  A survey of monte carlo tree search methods.  IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012.
  * Burgard et al. [1997] Wolfram Burgard, Dieter Fox, and Sebastian Thrun.  Active mobile robot localization.  In Intl. Joint Conf. on AI (IJCAI), pages 1346–1352. Citeseer, 1997\.
  * Fischer and Tas [2020] Johannes Fischer and Omer Sahin Tas.  Information particle filter tree: An online algorithm for pomdps with belief-based rewards on continuous domains.  In Intl. Conf. on Machine Learning (ICML), Vienna, Austria, 2020\.
  * Flaspohler et al. [2019] Genevieve Flaspohler, Victoria Preston, Anna PM Michel, Yogesh Girdhar, and Nicholas Roy.  Information-guided robotic maximum seek-and-sample in partially observable continuous environments.  IEEE Robotics and Automation Letters (RA-L), 4(4):3782–3789, 2019\.
  * Garg et al. [2019] Neha P Garg, David Hsu, and Wee Sun Lee.  Despot-$\alpha$: Online pomdp planning with large state and observation spaces.  In Robotics: Science and Systems (RSS), 2019.
  * Hoerger and Kurniawati [2021] Marcus 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.
  * Hollinger and Sukhatme [2014] G. A. Hollinger and G. S. Sukhatme.  Sampling-based robotic information gathering algorithms.  Intl. J. of Robotics Research, pages 1271–1287, 2014.
  * Indelman et al. [2015] V. Indelman, L. Carlone, and F. Dellaert.  Planning in the continuous domain: a generalized belief space approach for autonomous navigation in unknown environments.  Intl. J. of Robotics Research, 34(7):849–882, 2015.
  * Kearns et al. [2002] Michael Kearns, Yishay Mansour, and Andrew Y Ng.  A sparse sampling algorithm for near-optimal planning in large markov decision processes.  volume 49, pages 193–208. Springer, 2002.
  * Kim and Eustice [2014] A. Kim and R. M. Eustice.  Active visual SLAM for robotic area coverage: Theory and experiment.  Intl. J. of Robotics Research, 34(4-5):457–475, 2014.
  * Miller [2003] Erik G Miller.  A new class of entropy estimators for multi-dimensional densities.  In 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings.(ICASSP’03)., volume 3, pages III–297. IEEE, 2003.
  * Munos [2014] Rémi Munos.  From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning.  2014\.
  * Papadimitriou and Tsitsiklis [1987] C. Papadimitriou and J. Tsitsiklis.  The complexity of markov decision processes.  Mathematics of operations research, 12(3):441–450, 1987.
  * Platt et al. [2010] R. Platt, R. Tedrake, L.P. Kaelbling, and T. Lozano-Pérez.  Belief space planning assuming maximum likelihood observations.  In Robotics: Science and Systems (RSS), pages 587–593, Zaragoza, Spain, 2010.
  * Silver and Veness [2010] David Silver and Joel Veness.  Monte-carlo planning in large pomdps.  In Advances in Neural Information Processing Systems (NIPS), pages 2164–2172, 2010.
  * Somani et al. [2013] Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lee.  Despot: Online pomdp planning with regularization.  In NIPS, volume 13, pages 1772–1780, 2013.
  * Spaan et al. [2015] Matthijs TJ Spaan, Tiago S Veiga, and Pedro U Lima.  Decision-theoretic planning under uncertainty with information rewards for active cooperative perception.  Autonomous Agents and Multi-Agent Systems, 29(6):1157–1185, 2015\.
  * Sunberg and Kochenderfer [2018] 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.
  * Sztyglic and Indelman [2021] Ori Sztyglic and Vadim Indelman.  Online pomdp planning via simplification.  arXiv preprint arXiv:2105.05296, 2021.
  * Sztyglic et al. [2021] Ori Sztyglic, Andrey Zhitnikov, and Vadim Indelman.  Simplified belief-dependent reward mcts planning with guaranteed tree consistency.  arXiv preprint arXiv:2105.14239, 2021.
  * Thomas et al. [2021] Vincent Thomas, Geremy Hutin, and Olivier Buffet.  Monte carlo information-oriented planning.  arXiv preprint arXiv:2103.11345, 2021.
  * Thrun et al. [2005] S. Thrun, W. Burgard, and D. Fox.  Probabilistic Robotics.  The MIT press, Cambridge, MA, 2005.
  * Van Den Berg et al. [2012] J. Van Den Berg, S. Patil, and R. Alterovitz.  Motion planning under uncertainty using iterative local optimization in belief space.  Intl. J. of Robotics Research, 31(11):1263–1278, 2012.
  * Walsh et al. [2010] Thomas Walsh, Sergiu Goschin, and Michael Littman.  Integrating sample-based planning and model-based reinforcement learning.  In Nat. Conf. on Artificial Intelligence (AAAI), volume 24, 2010\.
  * Ye et al. [2017] Nan Ye, Adhiraj Somani, David Hsu, and Wee Sun Lee.  Despot: Online pomdp planning with regularization.  JAIR, 58:231–266, 2017.

##  Appendix A Proofs

###  A.1 Lemma 1

The proof is provided for continuous state space; The discrete case obtained
similarly by changing integrals to summations.

###### Proof.

$\displaystyle\sum_{n=1}^{N_{o}}\bar{\mathbb{P}}\left(o^{n}\mid
H^{-}\right)\mathcal{H}(\bar{b})=$ $\displaystyle-$
$\displaystyle\sum_{n=1}^{N_{o}}\bar{\mathbb{P}}\left(o^{n}\mid
H^{-}\right)\int_{s}\bar{\mathbb{P}}(s\mid H)\cdot log(\bar{\mathbb{P}}(s\mid
H))$ (18)

applying Bayes’ rule for $\bar{\mathbb{P}}(s\mid H)$,

$\displaystyle-$ $\displaystyle\sum_{n=1}^{N_{o}}\int_{s}\bar{Z}(o^{n}\mid
s)\mathbb{P}\left(s\mid H^{-}\right)$ (19) $\displaystyle\cdot$ $\displaystyle
log\left(\frac{\bar{Z}(o^{n}\mid s)\mathbb{P}\left(s\mid
H^{-}\right)}{\int_{s^{\prime}}\bar{Z}(o^{n}\mid
s^{\prime})\mathbb{P}\left(s^{\prime}\mid H^{-}\right)}\right)$

Splitting summation to follow the partitioning of the abstract observation
model,

$\displaystyle-$
$\displaystyle\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}\int_{s}\bar{Z}(o^{k}\mid
s)\mathbb{P}\left(s\mid H^{-}\right)$ (20) $\displaystyle\cdot$ $\displaystyle
log\left(\frac{\bar{Z}(o^{k}\mid s)\mathbb{P}\left(s\mid
H^{-}\right)}{\int_{s^{\prime}}\bar{Z}(o^{k}\mid
s^{\prime})\mathbb{P}\left(s^{\prime}\mid H^{-}\right)}\right)$

By construction, $\bar{Z}(o\mid s)$ has uniform distribution for $o^{k}$,
where $k\in[K(c-1)+1,Kc]$. Thus,

$\displaystyle-$
$\displaystyle\sum_{c=1}^{C}\left[\sum_{k=K(c-1)+1}^{Kc}1\right]\int_{s}\bar{Z}(o^{Kc}\mid
s)\mathbb{P}\left(s\mid H^{-}\right)$ (21) $\displaystyle\cdot$ $\displaystyle
log\left(\frac{\bar{Z}(o^{Kc}\mid s)\mathbb{P}\left(s\mid
H^{-}\right)}{\int_{s^{\prime}}\bar{Z}(o^{Kc}\mid
s^{\prime})\mathbb{P}\left(s^{\prime}\mid H^{-}\right)}\right)=$
$\displaystyle-$ $\displaystyle\sum_{c=1}^{C}K\cdot\int_{s}\bar{Z}(o^{Kc}\mid
s)\mathbb{P}\left(s\mid H^{-}\right)$ (22) $\displaystyle\cdot$ $\displaystyle
log\left(\frac{\bar{Z}(o^{Kc}\mid s)\mathbb{P}\left(s\mid
H^{-}\right)}{\int_{s^{\prime}}\bar{Z}(o^{Kc}\mid
s^{\prime})\mathbb{P}\left(s^{\prime}\mid H^{-}\right)}\right)=$
$\displaystyle K\cdot\sum_{c=1}^{C}\bar{\mathbb{P}}\left(o^{Kc}\mid
H^{-}\right)\mathcal{H}(\bar{b})$

which concludes the proof. ∎

###  A.2 Lemma 2

###### Proof.

We begin with,

$\bar{\mathbb{E}}_{o}\left[\mathbb{E}_{s\sim\bar{b}}\left[r\left(s,a\right)\right]\right]$
(23)

by definition of $\bar{\mathbb{E}}_{o}\left[\cdot\right]$, $\bar{b}(s)$,

$\sum_{n=1}^{N_{o}}\bar{\mathbb{P}}\left(o^{n}\mid
H^{-}\right)\left[\sum_{s\in S}\bar{\mathbb{P}}(s\mid
o^{n},H^{-})r\left(s,a\right)\right]$ (24)

applying chain rule,

$\displaystyle\sum_{n=1}^{N_{o}}\sum_{s\in S}\bar{\mathbb{P}}(s,o^{n}\mid
H^{-})r\left(s,a\right)=$ (25) $\displaystyle\sum_{n=1}^{N_{o}}\sum_{s\in
S}\bar{Z}(o^{n}\mid s)b^{-}(s)r\left(s,a\right)$

we split the sum over the observations to comply with the abstraction
partitioning and use the the abstract observation model definition, (4),

$\sum_{s\in
S}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}\frac{\sum_{m=K(c-1)+1}^{Kc}Z(o^{m}\mid
s)}{K}b^{-}(s)r\left(s,a\right)$ (26)

we then arrive at the desired result,

$\displaystyle\sum_{s\in S}\sum_{n=1}^{N_{o}}Z(o^{n}\mid
s)b^{-}(s)r\left(s,a\right)=$ (27)
$\displaystyle\mathbb{E}_{o}\left[\mathbb{E}_{s\sim
b}\left[r\left(s,a\right)\right]\right]$ (28)

∎

###  A.3 Theorem 1

###### Proof.

For clarity, we omit the time index in the derivation, the result holds for
any time step. We use $H^{-}$ to denote past history while excluding last
observation. We also use $b$ and $\mathbb{P}(s\mid o,H^{-})$ interchangeably.
Rearranging the abstraction from (1),

$\displaystyle\sum_{k=1}^{K}\bar{Z}\left(o^{k}\mid
s\right)=K\cdot\bar{Z}(o^{b}\mid s)\doteq\sum_{k=1}^{K}Z\left(o^{k}\mid
s\right)\ \ \ \ \ \forall b\in[1,K]$

Plugging it to the expected entropy term, (11),

$\displaystyle\bar{\mathbb{E}}_{o}\left[\mathcal{H}\left(\bar{b}\right)\right]-\mathbb{E}_{o}\left[\mathcal{H}\left(b\right)\right]=$
(29) $\displaystyle\sum_{i=1}^{N_{o}}\bar{\mathbb{P}}\left(o_{i}\mid
H^{-}\right)\mathcal{H}\left(\bar{b}\right)-\sum_{i=1}^{N_{o}}\mathbb{P}\left(o_{i}\mid
H^{-}\right)\mathcal{H}\left(b\right)$ (30)

expanding the entropy term,

$\displaystyle-$
$\displaystyle\sum_{i=1}^{N_{o}}\bar{\mathbb{P}}\left(o_{i}\mid
H^{-}\right)\int_{s}\bar{\mathbb{P}}\left(s\mid
o_{i},H^{-}\right)log\left(\bar{b}\right)$ (31) $\displaystyle+$
$\displaystyle\sum_{i=1}^{N_{o}}\mathbb{P}\left(o_{i}\mid
H^{-}\right)\int_{s}\mathbb{P}\left(s\mid o_{i},H^{-}\right)log\left(b\right)$

by Bayes’ rule,

$\displaystyle-$
$\displaystyle\sum_{i=1}^{N_{o}}\int_{s}\bar{Z}\left(o_{i}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(\bar{b}\right)$ (32)
$\displaystyle+$ $\displaystyle\sum_{i=1}^{N_{o}}\int_{s}Z\left(o_{i}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(b\right)$

a change in the order of summation and integral and a split of $N_{o}=C\cdot
K$ result in,

$\displaystyle-$
$\displaystyle\int_{s}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}\bar{Z}\left(o_{k}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(\bar{b}\right)$ (33)
$\displaystyle+$
$\displaystyle\int_{s}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}Z\left(o_{k}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(b\right)$

By plugging-in the definition of the abstract model,

$\displaystyle-$
$\displaystyle\int_{s}\sum_{c=1}^{C}\left[\sum_{k=K(c-1)+1}^{Kc}\frac{\sum_{\bar{k}=K(c-1)+1}^{Kc}Z\left(o_{\bar{k}}\mid
s\right)}{K}\right]$ (34) $\displaystyle\mathbb{P}\left(s\mid
H^{-}\right)log\left(\bar{b}\right)$ $\displaystyle+$
$\displaystyle\int_{s}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}Z\left(o_{k}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(b\right)=$ $\displaystyle-$
$\displaystyle\int_{s}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}Z\left(o_{k}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(\bar{b}\right)$ (35)
$\displaystyle+$
$\displaystyle\int_{s}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}Z\left(o_{k}\mid
s\right)\mathbb{P}\left(s\mid H^{-}\right)log\left(b\right)=$
$\displaystyle\sum_{i=1}^{N_{o}}\mathbb{P}\left(o_{i}\mid
H^{-}\right)\int_{s}b\cdot log\left(\frac{b}{\bar{b}}\right)=$ (36)
$\displaystyle E_{o}\left[\mathcal{D}_{KL}\left(b||\bar{b}\right)\right]\geq
0$

(36) obtained by applying similar steps in reverse order. The last equality
holds since KL-divergence is non-negative and so is its expectation. It is
left to prove the upper bound; Applying Bayes rule to the nominator and
denominator of (36),

$\displaystyle\sum_{i=1}^{N_{o}}\mathbb{P}\left(o_{i}\mid
H^{-}\right)\int_{s}blog\left(\frac{Z\left(o_{i}\mid
s\right)}{\bar{Z}\left(o_{i}\mid s\right)}\right)$ (37) $\displaystyle+$
$\displaystyle\sum_{i=1}^{N_{o}}\mathbb{P}\left(o_{i}\mid
H^{-}\right)log\left(\frac{\bar{\mathbb{P}}\left(o_{i}\mid
H^{-}\right)}{\mathbb{P}\left(o_{i}\mid H^{-}\right)}\right)\int_{s}bds$

By construction of the abstract observation model,

$\displaystyle\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}\mathbb{P}\left(o_{k}\mid
H^{-}\right)\int_{s}b\cdot log\left(\frac{Z\left(o_{k}\mid s\right)\cdot
K}{\sum\limits_{k=K(c-1)+1}^{Kc}Z\left(o_{\bar{k}}\mid s\right)}\right)ds$
$\displaystyle+$
$\displaystyle\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}\mathbb{P}\left(o_{k}\mid
H^{-}\right)log\left(\frac{\bar{\mathbb{P}}\left(o_{k}\mid
H^{-}\right)}{\mathbb{P}\left(o_{k}\mid H^{-}\right)}\right)$
$\displaystyle\leq$ $\displaystyle\
log(K)\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{Kc}\mathbb{P}\left(o_{k}\mid
H^{-}\right)\int_{s}bds+0=log(K).$

The inequality is due to positiveness of the denominator in the first term and
Jensen’s inequality in the second term. we end up with,

$0\leq\bar{\mathbb{E}}_{o}\left[\mathcal{H}\left(\bar{b}\right)\right]-\mathbb{E}_{o}\left[\mathcal{H}\left(b\right)\right]\leq
log(K).$ (38)

∎

###  A.4 Corollary 1.1

###### Proof.

From Lemma 2 it is clear that the expected state-dependent reward is
unaffected by the abstraction, and thus will not affect the value function.
For the sake of conciseness and clarity, we prove the case that the value
function depends only on the entropy. The general case derived similarly by
applying Lemma 2 instead of the expected state-dependent reward.

$\displaystyle V$
${}^{\pi}(b_{t})=\sum_{n=1}^{N_{o}}\mathbb{P}\left(o_{t+1}^{n}\mid
H_{t+1}^{-}\right)\left[-\mathcal{H}(b_{t+1})+V^{\pi}(b_{t+1})\right]$

expanding the value function,

$\displaystyle-\sum_{n=1}^{N_{o}}\mathbb{P}\left(o_{t+1}^{n}\mid
H_{t+1}^{-}\right)\bigr{[}\mathcal{H}(b_{t+1})$ (39)
$\displaystyle+\sum_{n^{\prime}=1}^{N_{o}}\mathbb{P}\left(o_{t+2}^{n^{\prime}}\mid
H_{t+2}^{-}\right)\mathcal{H}(b_{t+2})+\cdots\bigl{]}\bigl{]}$

by linearity of expectation,

$\displaystyle-\mathbb{E}_{o_{t+1}}\left[\mathcal{H}(b_{t+1})\right]+\mathbb{E}_{o_{t+1}}\left[\mathbb{E}_{o_{t+2}}\mathcal{\Bigl{[}H}(b_{t+2})\Bigr{]}\right]+\cdots$
(40)

using Theorem 1 for each of the expected entropy terms separately until time-
step $\mathcal{T}-1$,

$\displaystyle V^{\pi}(b_{t})\geq$
$\displaystyle-\Bigl{[}\mathbb{\bar{E}}[\mathcal{H}(\bar{b}_{t+1})]+log(K)\Bigr{]}$
(41)
$\displaystyle-\mathbb{E}_{o_{t+1}}\left[\bar{\mathbb{E}}_{o_{t+2}}[\mathcal{H}(\bar{b}_{t+2})]+log(K)\right]\cdots$
$\displaystyle=$
$\displaystyle-\bar{\mathbb{E}}_{o_{t+1}}\Bigl{[}\mathcal{H}(\bar{b}_{t+1})\Bigr{]}$
(42)
$\displaystyle-\mathbb{E}_{o_{t+1}}\bar{\mathbb{E}}_{o_{t+2}}\Bigl{[}\mathcal{H}(\bar{b}_{t+2})\Bigr{]}\cdots+\mathcal{T}\cdot
log(K)$

applying similar steps in reverse order yields the abstract value function,

$\displaystyle\bar{V}^{\pi}(b_{t})+\mathcal{T}\cdot log(K)$
$\displaystyle\Longrightarrow$
$\displaystyle\bar{V}^{\pi}(b_{t})-V^{\pi}(b_{t})\leq\mathcal{T}\cdot log(K).$

Following the same derivation and applying the other side of the inequality of
Theorem 1, completes the derivation for the entropy as reward. Using the more
general reward, (1), and applying Lemma 2, yields the proof for corollary 1.1,

$0\leq\bar{V}^{\pi}(b_{t})-V^{\pi}(b_{t})\leq\mathcal{T}\cdot\omega_{2}log(K).$

∎

###  A.5 Expected Entropy Estimation

We derive an estimator to the expected differential entropy with continuous
observation space. The discrete state or observation spaces follows similar
derivation by replacing integrals with summations.

$\displaystyle\mathbb{E}[\mathcal{H}(b_{t})]=-\int_{o_{t}}p(o_{t}\mid
H_{t}^{-})\int_{s_{t}}p(s_{t}\mid o_{t},H_{t}^{-})$ (43) $\displaystyle\cdot
log(p(s_{t}\mid o_{t},H_{t}^{-}))$

applying Bayes’ rule,

$\displaystyle\mathbb{E}[$
$\displaystyle\mathcal{H}(b_{t})]=-\int_{o_{t}}\int_{s_{t}}p(s_{t},o_{t}\mid
H_{t}^{-})$ (44) $\displaystyle\cdot log\left(Z(o_{t}\mid
s_{t})\int_{s_{t-1}}T(s_{t}\mid s_{t-1},a_{t-1})b(s_{t-1})\right)$
$\displaystyle+\int_{o_{t}}\int_{s_{t}}p(s_{t},o_{t}\mid H_{t}^{-})\cdot
log(p(o_{t}\mid H_{t}^{-}))$

by chain rule and marginalization,

$\displaystyle\mathbb{E}[$
$\displaystyle\mathcal{H}(b_{t})]=-\int_{o_{t}}\int_{s_{t}}Z(o_{t}\mid
s_{t})b^{-}(s_{t})$ (45) $\displaystyle\cdot log\left(Z(o_{t}\mid
s_{t})\int_{s_{t-1}}T(s_{t}\mid s_{t-1},a_{t-1})b(s_{t-1})\right)$
$\displaystyle+\int_{o_{t}}\int_{s_{t}}Z(o_{t}\mid s_{t})b^{-}(s_{t})$
$\displaystyle\cdot log\left(\int_{s_{t}}Z(o_{t}\mid
s_{t})b^{-}(s_{t})\right)$

using particle filter, the belief represented as a set of weighted particles,
$\\{(s^{1},q^{1}),\dots,(s^{i},q^{i}),\dots,(s^{n},q^{n})\\}$. Where $q^{i}$
denotes the weight of particle $i$.

$\displaystyle\mathbb{E}[\mathcal{H}(b_{t})]\approx-$
$\displaystyle\int_{o_{t}}\eta_{t}\sum_{i=1}^{n}Z\left(o_{t}\mid
s_{t}^{i}\right)q_{t-1}^{i}\cdot$ (46) $\displaystyle\cdot
log\left(Z\left(o_{t}\mid s_{t}^{i}\right)\sum_{j=1}^{n}p\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}\right)$ $\displaystyle+$
$\displaystyle\int_{o_{t}}\eta_{t}\sum_{i=1}^{n}Z\left(o_{t}\mid
s_{t}^{i}\right)q_{t-1}^{i}\cdot$ $\displaystyle\cdot
log\left(\sum_{i}Z\left(o_{t}\mid s_{t}^{i}\right)q_{t-1}^{i}\right)$

where $\eta_{t}=\int_{o_{t}}\sum_{i=1}^{n}Z\left(o_{t}\mid
s_{t}^{i}\right)q_{t-1}^{i}$ normalizes the estimator for the probability
function so that it sums to 1. Then, we approximate expectation over the
observation space using observation samples, and query the likelihood model
conditioned on the state samples, $Z\left(o^{m}\mid s^{i}\right)\ \ \ \forall
o^{m}\in\\{o^{1},\dots,o^{M}\\}$,

$\displaystyle\hat{\mathbb{E}}[$
$\displaystyle\mathcal{H}(\hat{b}_{t})]=-\overline{\eta}_{t}\sum_{m=1}^{M}\sum_{i=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}\cdot$ (47) $\displaystyle\cdot
log\left(Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}T\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}\right)$ $\displaystyle+$
$\displaystyle\overline{\eta}_{t}\sum_{m=1}^{M}\left[\sum_{i=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}\right]$ $\displaystyle\cdot
log\left(\sum_{i^{\prime}=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i^{\prime}}\right)q_{t-1}^{i^{\prime}}\right)$
$\displaystyle\overline{\eta}_{t}=\frac{1}{\sum_{m=1}^{M}\sum_{i=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}}$ (48)

which concludes the derivation.

###  A.6 Theorem 2

Note that the reward function, (1), is built of two terms, state dependent
reward and entropy,

$R(b,a,b^{\prime})=\omega_{1}\mathbb{E}_{s\sim
b^{\prime}}\left[r(s,a)\right]+\omega_{2}\mathcal{H}(b^{\prime}).$ (49)

For clarity, we divide the proof into two parts,

$\displaystyle\\!\hat{\bar{\mathbb{E}}}_{o}$
$\displaystyle\left[R\left(\hat{b},a,\hat{\bar{b}}^{\prime}\right)\right]\\!-\\!\hat{\mathbb{E}}_{o}\left[R\left(\hat{b},a,\hat{b}^{\prime}\right)\right]=$
(50)
$\displaystyle\omega_{1}\left(\hat{\bar{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{\bar{b}}^{\prime}}\left[r(s,a)\right]\right]-\hat{{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{{b}}^{\prime}}\left[r(s,a)\right]\right]\right)$
(51) $\displaystyle+$
$\displaystyle\omega_{2}\left(\hat{\bar{\mathbb{E}}}_{o}\left[\mathcal{H}\left(\hat{\bar{b}}\right)\right]-\hat{\mathbb{E}}_{o}\left[\mathcal{H}\left(\hat{b}\right)\right]\right).$

The first is about the difference in expected entropy, which is similar in
spirit to the proof of Theorem 1. The second follows the claim and proof of
Lemma (2). We begin with the difference of the expected entropy. For clarity,
we derive the upper and lower bounds separately. For the upper bound,

###### Proof.

In the following we directly plug-in the expected entropy estimator, with both
the abstract observation model and the original observation model. For
clarity, we split the expression into two parts and deal with each separately.

$\displaystyle\hat{\bar{\mathbb{E}}}_{o}\left[\mathcal{H}\left(\hat{\bar{b}}\right)\right]-\hat{\mathbb{E}}_{o}\left[\mathcal{H}\left(\hat{b}\right)\right]$
$\displaystyle=-$
$\displaystyle\underbrace{\overline{\eta}_{t}\sum_{m=1}^{M}\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}}_{(a)}$ (52) $\displaystyle\cdot$
$\displaystyle\underbrace{log\left(\overline{Z}\left(o_{t}^{m}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}T\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}\right)}_{(a)}$ $\displaystyle+$
$\displaystyle\underbrace{\overline{\eta}_{t}\sum_{m=1}^{M}\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}\cdot
log\left(\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}\right)}_{(b)}$ $\displaystyle+$
$\displaystyle\underbrace{\overline{\eta}_{t}\sum_{m=1}^{M}\sum_{i=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}}_{(a)}$ $\displaystyle\cdot$
$\displaystyle\underbrace{log\left(Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}T\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}\right)}_{(a)}$ $\displaystyle-$
$\displaystyle\underbrace{\overline{\eta}_{t}\sum_{m=1}^{M}\sum_{i=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}\cdot log\left(\sum_{i=1}^{n}Z\left(o_{t}^{m}\mid
s_{t}^{i}\right)q_{t-1}^{i}\right)}_{(b)}$

In the first expression we start by splitting the summation to sum over its
clusters and sum over the components of each cluster,

$\displaystyle(a)=$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (53)
$\displaystyle\cdot$ $\displaystyle log\left(\frac{Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}p\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}}{\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}p\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}}\right)$ $\displaystyle(a)=$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (54)
$\displaystyle\cdot$ $\displaystyle log\left(\frac{Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)}{\overline{Z}\left(o_{t}^{k}\mid s_{t}^{i}\right)}\right)$

using the abstract model, (4),

$\displaystyle(a)=$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (55)
$\displaystyle\cdot$ $\displaystyle log\left(\frac{K\cdot Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)}{\sum_{k=K(c-1)+1}^{K\cdot c}Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)}\right).$ (56)

since the denominator within the log is a sum of positive values, the
following clearly holds,

$\displaystyle(a)\leq$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}\cdot log(K)$
(57)

by taking the constant $log(K)$ out of the summation, the rest sums to one, so
$(a)\leq log(K)$. Next we bound the second expression from above,

$\displaystyle(b)=$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (58)
$\displaystyle\cdot$ $\displaystyle
log\left(\frac{\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}/\overline{\eta}_{t}}{\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}/\overline{\eta}_{t}}\right)$

applying Jensen’s inequality,

$\displaystyle(b)\leq$ $\displaystyle
log\left(\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}\right)$ (59)

by recalling the definition of the normalizer, we end up with $log(1)=0$ ∎

Last, we provide a proof for the lower bound,

###### Proof.

$\displaystyle\hat{\bar{\mathbb{E}}}_{o}\left[\mathcal{H}\left(\hat{\bar{b}}\right)\right]-\hat{\mathbb{E}}_{o}\left[\mathcal{H}\left(\hat{b}\right)\right]=$
$\displaystyle-$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (60)
$\displaystyle\cdot$ $\displaystyle
log\Bigl{[}\frac{\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}T\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}}{\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}}$ $\displaystyle\cdot$
$\displaystyle\frac{\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}}{Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)\sum_{j=1}^{n}T\left(s_{t}^{i}\mid
s_{t-1}^{j},a_{t-1}\right)q_{t-1}^{j}}\Bigr{]}$

since $log(x)\leq x-1,\ \forall x>0$,

$\displaystyle\hat{\bar{\mathbb{E}}}_{o}\left[\mathcal{H}\left(\hat{\bar{b}}\right)\right]-\hat{\mathbb{E}}_{o}\left[\mathcal{H}\left(\hat{b}\right)\right]\geq$
$\displaystyle\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (61)
$\displaystyle\cdot$
$\displaystyle\left(1-\frac{\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)}{\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}}\cdot\frac{\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}}{Z\left(o_{t}^{k}\mid s_{t}^{i}\right)}\right)$

rearranging terms,

$\displaystyle 1-\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}$ (62)
$\displaystyle\cdot$ $\displaystyle\frac{\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)}{\sum_{i=1}^{n}\overline{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}}\cdot\frac{\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}}{Z\left(o_{t}^{k}\mid s_{t}^{i}\right)}$ (63)

we conclude with,

$\displaystyle 1-\overline{\eta}_{t}\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}Z\left(o_{t}^{k}\mid s_{t}^{i}\right)q_{t-1}^{i}=0$ (64)

∎

We now derive the second part of Theorem 2, i.e. for the difference of
expected state-dependent reward.

######  Lemma 3.

The value of the estimated expected state-dependent reward is not affected by
the abstraction shown in (4), i.e.,

$\displaystyle\hat{\bar{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{\bar{b}}^{\prime}}\left[r(s,a)\right]\right]=\hat{{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{{b}}^{\prime}}\left[r(s,a)\right]\right]$
(65)

###### Proof.

$\displaystyle\hat{\bar{\mathbb{E}}}_{o}$
$\displaystyle\left[\mathbb{E}_{s\sim\hat{\bar{b_{t}}}^{\prime}}\left[r(s_{t},a_{t})\right]\right]=$
(66) $\displaystyle\sum_{m=1}^{M}\mathbb{\bar{P}}(o^{m}_{t}\mid
H_{t}^{-})\sum_{i=1}^{n}\mathbb{\bar{P}}(s^{i}_{t}\mid
o_{t}^{m},H_{t}^{-})r(s^{i}_{t},a_{t})$ (67)

applying chain rule,

$\displaystyle\sum_{m=1}^{M}\sum_{i=1}^{n}\mathbb{\bar{P}}(s^{i}_{t},o_{t}^{m}\mid
H_{t}^{-})r(s^{i}_{t},a_{t}),$ (68)

then applying chain-rule from the other direction and using the markovian
assumption of the observation model,

$\displaystyle\sum_{m=1}^{M}\sum_{i=1}^{n}\bar{Z}(o_{t}^{m}\mid
s^{i}_{t})b_{t}^{-}\cdot r(s^{i}_{t},a_{t}).$ (69)

Applying the transition function on particles from $b_{t-1}$, does not alter
their weights, therefore we receive the following expression,

$\displaystyle\sum_{c=1}^{C}\sum\limits_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}\bar{Z}\left(o_{t}^{k}\mid
s_{t}^{i}\right)q_{t-1}^{i}r(s_{t}^{i},a_{t})$ (70)

Using (1),

$\displaystyle\sum_{c=1}^{C}\sum_{k=K(c-1)+1}^{K\cdot
c}\sum_{i=1}^{n}\frac{\sum\limits_{\bar{k}=K(c-1)+1}^{K\cdot
c}Z\left(o_{t}^{\bar{k}}\mid
s_{t}^{i}\right)}{K}q_{t-1}^{i}r(s_{t}^{i},a_{t}),$ (71)

followed by canceling the summation over $k$ with $K$ in the denominator,

$\displaystyle\sum_{m=1}^{M}\sum_{i=1}^{n}Z(o_{t}^{m}\mid
s^{i}_{t})b_{t}^{-}\cdot r(s^{i}_{t},a_{t}).$ (72)

We then end up with the desired result,

$\hat{\bar{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{\bar{b}}^{\prime}}\left[r(s,a)\right]\right]=\hat{{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{{b}}^{\prime}}\left[r(s,a)\right]\right]$
(73)

∎

To conclude the proofs of Theorem 2, note that,

$\displaystyle
0\leq\omega_{1}\left(\hat{\bar{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{\bar{b}}^{\prime}}\left[r(s,a)\right]\right]-\hat{{\mathbb{E}}}_{o}\left[\mathbb{E}_{s\sim\hat{{b}}^{\prime}}\left[r(s,a)\right]\right]\right)$
(74)
$\displaystyle+\omega_{2}\left(\hat{\bar{\mathbb{E}}}_{o}\left[\mathcal{H}\left(\hat{\bar{b}}\right)\right]-\hat{\mathbb{E}}_{o}\left[\mathcal{H}\left(\hat{b}\right)\right]\right)\leq\omega_{2}log(K)$
(75)

###  A.7 Corollary 2.1

The proof of 2.1 follows closely to the proof in A.4. Replacing the exact
value function with its estimated counterpart from A.6 yields the desired
result.

##  Appendix B AI-FSSS

In this section we present the main procedures to derive our algorithm. The
variables used in Algorithm 1 are $b$, $ba$ and $b^{\prime}$ which represent a
belief node, a predicted belief node, i.e. after performing an action and
posterior belief, after incorporating a measurement. $C(\cdot)$ denotes a list
of their corresponding children. $a$ and $o_{\\{1,...,K\\}}$ denotes an action
and a list of $K$ sampled observations respectively. $\bar{P}_{o|s}$ is a list
holding the abstract probability values of the measurement model, as in
equation (4). $R_{state}(\cdot,\cdot)$ denotes a state-dependent reward
function, which may be defined arbitrarily. $\gamma$ denotes the discount
factor. $LB,UB$ and $N$ are all initialized to zero. Rollout performs a
predefined policy. In our experiments, we chose uniform distribution over all
actions for the rollout policy. Algorithm 2 uses $b_{init}$, which represents
the initial belief at the root node, $n$ is the number of iterations and
$d_{max}$, the maximum depth of the planning tree.

Algorithm 1 AI-FSSS

Procedure: Simulate(b,d)

1: if d = 0 then

2: return 0, 0

3: else if $|C(b)|<|\mathcal{A}|$ then

4: $a,o_{\\{1,...,K\\}}\xleftarrow{}$Gen$(b,K)$

5: $\bar{P}_{o|s}\xleftarrow{}$ AbstractObs$(ba,o_{\\{1,...,K\\}})$ // eq.(4)

6:
$\bar{\mathbb{E}}[\mathcal{R}(ba)]\xleftarrow{}$ExpectedReward$(b,a,ba,\bar{P}_{o|s})$

7: else

8: $a\xleftarrow{}$ SelectAction$(b)$

9: end if

10: $lb\xleftarrow{}\bar{\mathbb{E}}[\mathcal{R}(ba)]$

11: $ub\xleftarrow{}\bar{\mathbb{E}}[\mathcal{R}(ba)]+log(K)$

12: if $0<N(ba)<K$ then

13: $o\xleftarrow{}$ Pop $(o_{\\{1,...,K\\}})$

14: $b^{\prime}\xleftarrow{}$ Posterior$(b,a,o)$

15: $V_{LB},V_{UB}\xleftarrow{}$Simulate$(b^{\prime},d-1)$

16: else if $N(ba)=K$ then

17: $b^{\prime}\xleftarrow{}\underset{b^{\prime}}{\arg\min}N(b^{\prime})$

18: $V_{LB},V_{UB}\xleftarrow{}$Simulate$(b^{\prime},d-1)$

19: else if $N(ba)=0$ then

20: $V_{LB},V_{UB}\xleftarrow{}$Rollout$(ba,d-1)$

21: end if

22: $LB(ba)\xleftarrow{}lb+\frac{\gamma
V_{LB}+(|C(ba)|-1)(LB(ba)-lb)}{|C(ba)|}$

23: $UB(ba)\xleftarrow{}ub+\frac{\gamma
V_{UB}+(|C(ba)|-1)(LB(ba)-ub)}{|C(ba)|}$

24: $LB(b)\xleftarrow{}\underset{a}{\max}LB(ba)$

25: $UB(b)\xleftarrow{}\underset{a}{\max}UB(ba)$

26: $N(b)\xleftarrow{}N(b)+1$

27: $N(ba)\xleftarrow{}N(ba)+1$

28: return $LB(b),UB(b)$

Algorithm 2 Solve

Procedure: Solve

1: for $i\in 1:n$ do

2: Simulate$(b_{init},d_{max})$

3: end for

4: $action\xleftarrow{}$ AdaptBounds$(b_{init})$

5: return $action$

Algorithm 3 Refine

Procedure: Refine(b,ba,d)

1: if IsLeaf(b) then

2: return 0, 0

3: else if Abstract$(ba)$ then

4: $r_{old}\xleftarrow{}$ReuseReward$(ba)$

5: $P_{o|s}\xleftarrow{}$ OriginalObsModel$(ba,o_{\\{1,...,K\\}})$

6: $\mathbb{E}[\mathcal{H}(ba)]\xleftarrow{}$ExpectedEntropy$(b,ba,P_{o|s})$

7:
$r\xleftarrow{}r_{old}+\omega_{2}(\mathbb{E}[\mathcal{H}(ba)]-\bar{\mathbb{E}}[\mathcal{H}(ba)])$

8: else

9: $r\xleftarrow{}r_{old}$

10: end if

11:
$b^{\prime}\xleftarrow{}\underset{b^{\prime}}{\arg\max}(UB(b^{\prime})-LB(b^{\prime}))$

12:
$a^{\prime}\xleftarrow{}\underset{a^{\prime}}{\arg\max}(UB(b^{\prime}a^{\prime})-LB(b^{\prime}a^{\prime}))$

13: $V_{LB},V_{UB}\xleftarrow{}$Refine$(b^{\prime},b^{\prime}a^{\prime},d-1)$

14: $LB(ba)\xleftarrow{}lb+\frac{\gamma
V_{LB}+(|C(ba)|-1)(LB(ba)-lb)}{|C(ba)|}$

15: $UB(ba)\xleftarrow{}ub+\frac{\gamma
V_{UB}+(|C(ba)|-1)(LB(ba)-ub)}{|C(ba)|}$

16: $LB(b)\xleftarrow{}\underset{a}{\max}LB(ba)$

17: $UB(b)\xleftarrow{}\underset{a}{\max}UB(ba)$

18: return $LB(b),UB(b)$

Procedure: AdaptBounds($b_{init}$)

1: while
$\underset{a^{+}\in\mathcal{A}}{\max}LB(b_{init}a^{+})<\underset{a\in\mathcal{A}\backslash
a^{+}}{\max}UB(b_{init}a)$ do

2: $a^{*}\xleftarrow{}\underset{a\in\mathcal{A}}{\arg\max}LB(b_{init}a)$

3: Refine$(b_{init},b_{init}a^{*},d)$

4: end while

5: return $a^{*}$

##  Appendix C Implementation Details

###  C.1 Domain

We compared the different algorithms on a two-dimensional Light Dark
environment. In this domain, the unobserved state of the agent is its pose,
$(X,Y)$, defined relative to a global coordinate frame, located at $(0,0)$.
There are 9 possible actions, eight of which has one unit of translation, and
they differ from each other by the direction which is equally spaced on a
circle, the ninth action has zero translation. We denote the transition model
as $x^{\prime}=f(x,a,w)$. At each time step, the agent receives a noisy
estimate of its position as an observation, denoted by $o=h(x,v)$. In our
experiments we chose $w$ and $v$ to be distributed according to a Gaussian
noise, although in general they may be arbitrary. The reward function defined
as the negative weighted sum of distance to goal and entropy,

$r(b,a)=-\mathrm{E}_{b}[\|x-x_{g}\|]-\mathcal{H}(b),$ (76)

The prior belief assumed to be Gaussian,
$b_{0}=\mathcal{N}([0,0],\Sigma_{0})$. In all our experiments, we employ a
receding horizon approach. At each iteration we calculate a solution from
scratch and share no information across different time steps.

###  C.2 Domain - Total Return Evaluation

We performed the experiments on a modification of Light Dark 2D and added
forbidden regions to the environment. Whenever the agent crosses to a
forbidden region, a -10 reward was added to its immediate reward. Also, we
added +10 reward whenever the agent reached the goal and stayed there until
the episode terminated.

###  C.3 Hyperparameters

Here we present the hyperparameters used to evaluate the total return
performance.

AI-FSSS |  |  |
---|---|---|---
$n$ | $C$ | $K$ |
$20$ | $4$ | $4$ |
FFFS |  |  |
$n$ | $C$ |  |
$20$ | $4$ |  |
PFT-DPW |  |  |
$n$ |  $c$222 | $k_{o}$ | $\alpha_{o}$
$20$ | $1$ | $4$ | $0.014$
Table 1: Hyperparameters used in the experiments.

2 $c$ controls the bonus of the UCB function, which is different from the
observation branching factor in FSSS and AI-FSSS, $C$.