Optimal Sensing via Multi-armed Bandit Relaxations in Mixed
Observability Domains

arXiv:1603.04586v1 [cs.AI] 15 Mar 2016

Mikko Lauri and Risto Ritala
Abstract— Sequential decision making under uncertainty is
studied in a mixed observability domain. The goal is to
maximize the amount of information obtained on a partially
observable stochastic process under constraints imposed by
a fully observable internal state. An upper bound for the
optimal value function is derived by relaxing constraints. We
identify conditions under which the relaxed problem is a multiarmed bandit whose optimal policy is easily computable. The
upper bound is applied to prune the search space in the
original problem, and the effect on solution quality is assessed
via simulation experiments. Empirical results show effective
pruning of the search space in a target monitoring domain.

I. INTRODUCTION
Deploying autonomous agents such as robots equipped
with an appropriate set of sensors allows automated execution of various information gathering tasks. The tasks
can include monitoring and identification of spatio-temporal
processes, automated exploration, or other data collection
campaigns in environments where human presence is undesired or infeasible. Robots are mobile sensor platforms whose
actions are optimized to maximize the informativeness of
measurement data.
As the target state is not known, a probability density function (pdf) over the state, called a belief state, is
maintained. Information conveyed by measurement data is
incorporated into the belief state by Bayesian filtering. Assuming Markovian dynamics and conditional independence
of measurement data given the system state, the problem is
a partially observable Markov decision process, or POMDP
[1].
Optimal information gathering has been studied in the
context of sensor management [2], and a review of applying POMDPs for sensor management is presented in [3].
The problem is formulated as a decision process under
uncertainty. The goal is to find a control policy mapping
belief states to actions, that when followed maximizes the
expected sum of discounted rewards over a horizon of time.
The reward associated with an action may depend either on
the true state of the system or the belief state. The former
can encode objectives such as reaching a favorable state or
avoiding costly ones, useful e.g. for navigation and obstacle
avoidance. The latter option allows information theoretic
rewards, such as mutual information, applied in various
sequential information gathering problems in robotics, see
e.g. [4], [5], [6]. Indefinite-horizon problems that terminate
M. Lauri and R. Ritala are with Department of Automation Science and Engineering, Tampere University of Technology, P.O. Box
692, FI-33101 Tampere, Finland. Email: mikko.lauri@tut.fi,

risto.ritala@tut.fi

when a special stopping action is executed are a natural
model for tasks that may be stopped once a certain level
of confidence about the state is reached [7].
Finding optimal policies for POMDPs is computationally
hard [8], and several approximate methods have been suggested. Point-based algorithms [9], [10] track so-called alpha
vectors at a set of points in the belief space. The alpha vectors
may then be used to approximate the optimal policy at any
belief state. Online planning methods [11] find an optimal
action for the current belief state instead of a representation
of the optimal policy. The problem is cast as a search over
the tree of belief states reachable from the current belief state
under various action-observation histories. Combining online
methods with Monte Carlo simulations to evaluate utility of
actions has lead to approximate algorithms able to handle
problems with up to 1052 states [12].
In mixed observability domains a part of the state space
is fully observable. The belief space is a union of lowdimensional subspaces, one for each value of a fully observable state variable. Robotic systems often exhibit mixed
observability which may be exploited to derive efficient
POMDP algorithms [13].
A multi-armed bandit (MAB) is a model for sequential
decision-making also applied in sensor management [2]. A
decision-maker plays one arm of the MAB and collects a
reward depending on the state of the arm. The arm then
randomly transitions to a new state while other arms remain
stationary. Solutions to MABs are index policies that are
easier to compute than solutions to general POMDPs [14].
Most of the aforementioned research applies reward functions that only depend on the true state and action. The
expectation of the reward is linear in the belief state, a feature
leveraged by many of the solution algorithms. Information
theoretic quantities such as entropy and mutual information
that would be useful as reward functions in optimal sensing
problems are nonlinear in the belief state. Classical POMDP
algorithms cannot be applied to solve such problems.
In this paper, we study POMDPs with mixed observability
with mutual information as the reward function. As such, our
approach is especially suited for optimal sensing problems in
robotics domains. We remove constraints on available actions
to obtain a relaxed problem. The optimal value of the relaxed
problem obtained is an upper bound on the optimal value
in the POMDP. We identify the conditions under which the
relaxed problem is a MAB and has an easily computable
optimal solution. The upper bound is applied in an online
planning algorithm to prune the search space.
The paper is organized as follows. In Section II, the mixed-

observability POMDP is defined. In Section III, methods
for solving the problem are discussed. In Section IV, two
relaxations are derived that provide upper bounds for the
optimal value function. Section V determines the conditions
under which the relaxations are MABs. Empirical results are
provided in Section VI. Section VII concludes the paper.
II. A MIXED OBSERVABILITY POMDP
Notation. We denote random variables and sets by uppercase letters, and realizations of random variables and
members of sets as lowercase letters. Time instants are
distinguished by writing e.g. x and x′ for realizations at time
t and (t + 1), respectively.
An agent, e.g. a robot or another sensor platform, has an
internal state x ∈ X that captures the dynamics and constraints of operating on-board sensors and other devices. The
internal state evolves according to a deterministic dynamics
model DX , defined x′ = fa (x) where a ∈ A(x) is a control
action in the finite set of actions allowed in internal state x.
Let Y = {Y1 , Y2 , . . . , Yn }, X ∩ Y = ∅, denote a set of
random inference variables an agent wishes to obtain information about. The dynamics of the variables are governed
by a stochastic model DY , defined as a Markov chain p(y ′ |
y, a). The complete state of the system is s ∈ S = X × Y .
The problem features mixed observability, where the internal state is fully observable and the inference variables are
partially observable. The agent’s observations z ′ ∈ Z follow
an observation model O, defined by p(z ′ | y ′ , a).
The agent maintains a belief state b = (x, p(y)) ∈ B,
consisting of the deterministic, fully observable internal state
and a pdf over Y . The initial belief state b0 is given. Given
a belief state b, an action a, and an observation z ′ , the belief
state at the next time instant is given by the belief update
equation b′ = τ (b, a, z ′ ) = (x′ , p(y ′ | z ′ , a, b)) where x′ =
fa (x), and the pdf over the inference variables is obtained
from a Bayesian filter
1
(1)
p(y ′ | z ′ , a, b) = p(z ′ | y ′ , a)p(y ′ | a, b)
η
P
p(y ′ | y, a)p(y) is the predictive
where p(y ′ | a, b) =
y∈Y

pdf and η = p(z ′ | a, b) is the normalization factor denoting
the prior probability of observing z ′ . Given any sequence of
actions and observations, there is no uncertainty about the
resulting internal state x. Thus we can equivalently define
the set of allowed actions A(x) via the belief state as Ab .
The agent’s objective is encoded by a reward function R.
The objective is to maximize the expected sum of discounted
rewards over a horizon of T decisions. The discount factor
is γ ∈ [0, 1].
We consider belief-dependent reward functions. Let
R(b, a) = I(Y ; Z | a), i.e. the mutual information (MI)
between the posterior state and observation. MI is defined
I(Y ; Z | a) = H(Y | a) − E [H(Y | z ′ , a)] ,
Z

(2)

where H(Y | a) is the entropy of the predictive pdf p(y ′ |
a, b) and the second term is the expected entropy of the
posterior pdf (1) under the prior pdf p(z ′ | a, b).

The problem P = hS, A, Z, D, O, R, b0 , γi where D =
DX ×DY is an instance of a POMDP. By Bellman’s principle
of optimality [15] the solution may be found via a backward
in time recursion procedure known as value iteration. An
optimal value function Vt∗ : B → R maps a belief state to
its maximum expected sum of discounted rewards when an
optimal policy is followed for the next t decisions. Optimal
value functions are computed by
X
∗
Qt (b, a) = R(b, a) + γ
p(z | a, b)Vt−1
(b′ )dz
(3a)
z∈Z

Vt∗ (b) = max Qt (b, a),
a∈Ab

(3b)

starting from Q1 (b, a) = R(b, a). The optimal policy πt∗ :
B → Ab for t remaining decisions is found by extracting the
argument a maximizing Qt (b, a). The recursion is continued
up to VT .
III. SOLVING POMDPS WITH
BELIEF-DEPENDENT REWARDS
In most POMDPs, the reward function is state-dependent
and its expectation is linear in the belief state. The finitehorizon optimal value function then has a finite representation by a convex hull of a set of hyperplanes over the belief
space [16]. Many exact [17] and approximate [18], [10], [9]
offline algorithms for POMDPs rely on this piecewise linearity and convexity of the value function. Reward functions
such as mutual information and entropy that are useful in
optimal sensing problems are nonlinear in the belief state.
Thus, these offline algorithms are not applicable to solve the
recursion (3) with a belief-dependent reward function.
Online planning methods [11] find an optimal action for
the current belief state instead of a closed form representation
of the optimal policy. As explicit representations of policies
are not required, a nonlinear belief-dependent reward function does not constitute any additional difficulty.
In online planning, a tree graph of belief states reachable
from the current belief state is constructed. The current belief
state is the root of the tree, and belief states computed via
τ (b, a, z ′ ) are added as child nodes of node b. When a desired
search depth is reached, the values from the leaves of the tree
are propagated back to the root according to (3).
Suboptimal actions may sometimes be pruned from the
search tree by branch-and-bound pruning when the optimal
value for executing action a in belief state b, Qt (b, a), has
an upper bound U (b, a) and a lower bound L(b, a). For a
given a and any â 6= a, if U (b, a) ≤ L(b, â) then action a is
suboptimal at b and all its successor nodes may be pruned
from the tree. The bounds may similarly be propagated via
(3). The number of belief states in the search tree is reduced.
Alternatives to online tree search include e.g. specialized
approximate methods [19], however limited to small problems, open-loop approximation applied with the receding
horizon control principle [6], or reduced value iteration [5]
for Gaussian beliefs over Y in a mixed-observability case.
For a theoretical treatment of nonlinear but convex reward
functions in POMDPs, we refer the reader to [20].

IV. BOUNDS FOR THE VALUE FUNCTION
πt∗

The optimal policy
attains the optimal value for all
belief states. Then any other policy πt achieves a value that
is a lower bound on the optimal value. A simple choice is
to set πt as the greedy one-step look-ahead policy πG (b) =
argmaxa∈Ab R(b, a). Other options include random policies
or blind policies [18] always executing a single fixed action.
Upper bounds are found by deriving two relaxed versions
of the original POMDP problem by removing constraints on
the applicable actions. The set of internal states reachable
from a subset XS ⊆ X in a single time step is
[
[
fa (x).
(4)
F (XS ) =
∀x∈XS ∀a∈A(x)

The set of internal states reachable in k steps from XS is
F k (XS ) = F ◦ . . . ◦ F (XS ) .
{z
}
|

(5)

k times

The first relaxation is obtained by removing all constraints
imposed by the internal state as follows.
Universal sensor relaxation. Given a POMDP problem
P = hS, A, Z, D, O, R, b, γi, its universal sensor relaxation
is Pu = hY, Â, Z, DY , O, R, p(y), γi, where Â =
S
x∈X A(x) contains all actions, DY is the stochastic part
from D, and b = (x, p(y)) is replaced by p(y).
When we consider only actions applicable in the internal
states reachable within k = T − t decisions, where t is the
current time step, we obtain the k-step sensor relaxation.
k-step sensor relaxation. Given a POMDP problem P =
hS, A, Z, D, O, R, b, γi, its k-step sensor relaxation
is Pk =
S
hY, Âk , Z, DY , O, R, p(y), γi, where Âk = i∈F k ({x}) A(i)
is the set of all actions possible in the internal states
reachable within k time steps from the current internal state
x, and DY and p(y) are as for Pu .
As Ab ⊆ Âk ⊆ Â, the optimal value in either relaxed
problem is greater than or equal to the optimal value in the
original problem. Let V ∗ , Vu∗ , and Vk∗ denote the optimal
value functions for P , Pu , and Pk , respectively, and let V πG
denote the value function for the greedy policy in P for a
given 1 ≤ t ≤ T . Now
V πG (b) ≤ V ∗ (b) ≤ Vk∗ (b) ≤ Vu∗ (b) ∀b ∈ B

(6)

holds for the optimal value and the bounds.
V. MULTI-ARMED BANDIT INDEX POLICIES FOR
POMDP RELAXATIONS
Both relaxations defined above are POMDPs themselves.
Solving even the relaxed problems may thus be a computationally intractable task. This motivates identifying POMDPs
whose relaxations have easily computable optimal policies.
In a multi-armed bandit (MAB) problem, a decision-maker
plays one arm of the MAB and collects a reward depending
on the state of the arm. Four requirements distinguish MABs
among general stochastic control problems [2]: 1) exactly

one machine is played by the agent per action, and the state
of that machine evolves such that the agent may not affect
it, 2) machines not played remain in their current state, 3)
the machines are independent, and 4) the machines that are
not played do not contribute any reward. Gittins [21] showed
that the optimal policies in MABs are so-called greedy index
allocation policies. For each arm, an allocation index known
as the Gittins index is calculated with the optimal selection
yielding the highest index value. Index policies are optimal
when actions are not irrevocable [14], [2]: any action is
available at any stage, and may be chosen at a later stage
with the same reward, excluding the effect of the discount
factor. Index policies are usually much easier to compute
than backward induction solutions of POMDPs [14].
An index policy is in general not optimal for the mixedobservability POMDP of Section II, as actions are irrevocable
due to the constraints imposed by the internal state. However,
both of the relaxations Pu and Pk have a fixed action
space. The following three properties are required for the
relaxations to be MABs. Results are derived for Pu , and
they hold for the more restricted case Pk as well.
Property 1. Each a ∈ Â is related to Ya ⊂ Y , such that
Ya 6= ∅ and i, j ∈ Â : i 6= j ⇒ Yi ∩ Yj = ∅.
Property 2. Given a ∈ Â, each yi′ ∈ Ya is conditional on
the values ui ∈ Ui ⊆ Ya of some subset Ui of the inference
variables in Ya , and yi ∈
/ Ya are stationary, i.e.
Y
Y
′
p(y | y, a) =
δ(yi′ − yi ), (7)
p(yi′ | ui )
yi ∈Ya

yi ∈Y \Ya

where δ is the Dirac delta function.
Property 3. For a ∈ Â, the observation is conditional on
ya′ ∈ Ya , i.e.
(8)
p(z ′ | y ′ , a) = p(z ′ | ya′ ).
Corollary 1. When p(y) =

Q

p(ya ), ya ∈ Ya , i.e. the prior

a∈Â

on inference variables is independent between the subsets Ya
and properties 2 and 3 hold, the independence is preserved
in the posterior,
Y
p(y ′ | z ′ , a, b) =
p(yk′ | z ′ , a, b).
(9)
k∈Â

Furthermore,
I(Y ; Z | a) = I(Ya ; Z).

(10)

Equation (9) is seen to hold applying (1) to the given prior
with models satisfying (7) and (8). Equation (10) is seen to
hold through two steps. First, due to the independence
strucP
ture of the prior and posterior, H(Y | a) = k∈Â H(Yk | a)
and similarly for H(Y | z ′ , a). Second, by (1) we see from
(9) that for k 6= a : p(yk′ | z ′ , a, b) = p(yk ) ⇒ H(Yk | a) =
H(Yk | z ′ , a). Applying these steps to (2) leads to (10).
We now state our main result determining the conditions
under which a POMDP relaxation is a MAB.

armed bandit problems.

Proof. (Sketch). Consider the four requirements for MABs
introduced above. Property 1 establishes the ”arms” of the
bandit, partly satisfying requirement 1. The rest of requirements 1 and 2 are satisfied by Properties 2 and 3, which
establish the states of the bandit arms as p(ya ), ya ∈ Ya , a ∈
Â. Requirement 3 is satisfied by the independence properties
in the first part of Corollary 1. The latter part of the corollary
shows that requirement 4 is satisfied.
When the proposition holds, the optimal policies for Pu
and Pk are greedy index policies with values Vu∗ = VuπG
and Vk∗ = VkπG , respectively. These optimal values are thus
much easier to compute than for general POMDPs.
Let us consider the following example problem.
Monitoring reactive targets. An agent is located at x ∈
X = {1, 2, . . . , M }. At every time step the agent may either
stay where it is or move to one of the neighboring locations
N (x) ⊂ X. The applicable actions are A(x) = x ∪ N (x).
Let Y = {Y1 , Y2 , . . . , YM }, with Yi assuming value 1 if a
target is present at location i and 0 if not. Each target Yi
reacts to the agent’s presence such that
(
wi (yi′ | yi ) if a = i
′
p(yi | yi , a) =
(11)
ri (yi′ | yi ) if a 6= i
The agent records measurements in Z = {0, 1} according to
(
1 − q− if ya′ = 0
′
′
p(z = 0 | y , a) =
,
(12)
q+
if ya′ = 1
where q− < 0.5, q+ < 0.5 are the false negative and positive
probabilities, respectively, and p(z ′ = 1 | y ′ , a) = 1−p(z ′ =
0 | y ′ , a). The reward function is (2).
Consider the relaxations Pu and Pk of this problem.
Property 1 is immediately seen to be satisfied. Property 2
is satisfied if ri (yi′ | yi ) = δ(yi′ − yi ) for 1 ≤ i ≤ M , i.e. if
targets remain stationary when the agent is not present, while
wi (yi′ | yi ) may be chosen freely. Property 3 is satisfied as
the observation only depends on the value ya′ .
VI. EMPIRICAL EVALUATION
We ran simulation experiments on the monitoring problem
defined above. There were |Y | = M = 36 inference
variables, arranged on a rectangular two-dimensional fourconnected grid. The agent was allowed to move on this
grid and sense the targets. We examined two cases. In the
first case, all of the properties 1-3 were satisfied. In the
second case, we relaxed Property 2 by allowing all inference
variables to change state. In all cases, the optimization
horizon T was varied from 1 to 6 decisions. The other
parameters were q− = 0.05, q+ = 0.05, γ = 0.95.
We implemented the real-time belief space search
(RTBSS) algorithm of [22] as presented in [11]. RTBSS

A. Case 1: Properties 1-3 satisfied
We defined ri = δ(yi′ − yi ), and wi were two-state
Markov chains with parameters pi01 , pi11 , where pijk denotes
the probability that Yi transitions from j to k. For each
1 ≤ i ≤ M , we sampled uniformly at random pi01 ∈
[0.0, 0.2], pi11 ∈ [0.8, 1.0]. A set of 1000 initial belief states
(x0 , p(y0 )) satisfying the independence assumption between
inference variables was sampled uniformly at random.
As Proposition 1 holds, Vu∗ = VuπG and Vk∗ = VkπG , and
the greedy MAB policies give valid upper bounds, see (6).
Applying RTBSS with these bounds hence always finds the
optimal solution, which was verified in our simulations. The
number of visited nodes in the search tree for each of the
1000 belief states is shown in Fig. 1 for 3 ≤ T ≤ 6 and
both upper bounds. Since the bound Vk∗ is tighter, applying
it results in a lower or equal number of visited nodes than Vu∗ .
For comparison, the average number of visited nodes for the
exhaustive search is shown in Table I. We note that applying
either bound greatly reduces the number of visited nodes,
in some cases by up to an order of magnitude. Although
the reduction in the number of visited nodes is substantial,
evaluating the bounds has a computational cost that must be
balanced with the savings from visiting fewer nodes. This
point is discussed in more detail in the next subsection.
5

Nodes expanded: Pk

a∈Â

implements an online search of belief states reachable from
the current belief state, and applies lower and upper bounds
to prune suboptimal actions. We applied the greedy lower
bound V πG (Section IV) and upper bounds VkπG or VuπG
(Section V). We compared this approach to an exhaustive
search of all reachable belief states equivalent to using lower
and upper bounds (−∞, ∞), and to the POMCP algorithm
[12], which gives a recommendation on the next action to
execute based on a series of Monte Carlo (MC) simulations.

10

Nodes expanded: Pk

Proposition 1 (MAB equivalence of POMDP relaxations).
When
Q properties 1-3 are fulfilled, and the prior is p(y) =
p(ya ), ya ∈ Ya , the relaxations Pu and Pk are multi-

10

T=3

T=4

T=5

T=6

4

10

3

10

2

10

1

10

5
4

10

3

10

2

10

1

10 1
10

2

3

4

10
10
10
Nodes expanded: P

u

5

1

10 10

2

3

4

10
10
10
Nodes expanded: P

5

10

u

Fig. 1. The number of search tree nodes expanded by RTBSS for 3 ≤
T ≤ 6 with the upper bound from Pu (x-axis) or Pk (y-axis). The diagonal
line shows where the two values are equal.

POMCP recommendations coincide with the optimal action more reliably when the number of MC simulations is increased and the optimization horizon T is short, see Table II.
We compared the values of optimal actions to those recommended by POMCP when the two differed. The difference

TABLE I
AVERAGE NUMBER OF NODES EXPANDED BY EXHAUSTIVE SEARCH .

Nodes

TABLE IV
P ERCENTAGE OF RTBSS SOLUTIONS AGREEING WITH OPTIMAL
SOLUTION WHEN

T =3

T =4

T =5

T =6

4.0 · 102

3.8 · 103

3.6 · 104

3.5 · 105

TABLE II
P ERCENTAGE OF POMCP RECOMMENDATIONS AGREEING WITH

Dynamics

Bound

T =2

T =3

T =4

T =5

T =6

Slow

Pu
Pk

100%
100%

100%
99.9%

100%
99.9%

100%
99.6%

100%
99.6%

Medium

Pu
Pk

100%
100%

100%
99.8%

99.9%
99.7%

100%
99.1%

100%
98.8%

Fast

Pu
Pk

100%
100%

100%
99.9%

100%
99.7%

100%
99.0%

100%
98.9%

OPTIMAL .

T =2

T =3

T =4

T =5

T =6

101
102
103
104

40.7
57.4
69.5
75.0

36.8
50.1
62.2
74.9

31.3
45.3
54.0
69.1

28.1
43.2
47.6
63.5

29.2
40.1
46.8
59.1

between the two values is the performance loss, for which
we computed the mean values and worst-case maximum
values. The results are shown in Table III. Performance loss
tends to be greater for fewer MC simulations and a greater
optimization horizon T . As the number of MC simulations
increases the mean performance loss is low, indicating that
on average POMCP performs very well compared to the
optimal solution. However, even if the mean performance
loss is low, the worst case performance loss from following
POMCP recommendations may be significantly greater. In
problems where suboptimal actions may lead to unacceptable
performance loss, methods such as RTBSS with valid bounds
may be preferable to POMCP.
B. Case 2: Property 2 not satisfied
We next examined the case where Property 2 was not
satisfied. We set ri = wi for each i. Each of the dynamics
models was a two-state Markov chain. We considered three
subcases distinguished by the rate of the state transitions:
slow, medium or fast. For slow dynamics, the parameters
were sampled for each i uniformly at random such that
∈ [0.8, 1.0], for medium dy∈ [0.0, 0.2], pi,slow
pi,slow
11
01
namics pi,med
∈
[0.2,
0.4],
pi,med
∈ [0.6, 0.8], and for
01
11
i,f ast
ast
fast dynamics p01
∈ [0.4, 0.6], pi,f
∈ [0.4, 0.6]. Each
11
experiment was repeated for 1000 randomly sampled initial
belief states and dynamics models. All beliefs satisfied the
independence assumption between inference variables.
The problem is quite similar to the one in Subsection VI-A, and POMCP performance was also observed to be
very good on average. The MAB equivalence, Proposition 1,
is now not satisfied for the relaxed problems. Thus, the upper
bounds are approximate, and optimality for RTBSS cannot be
guaranteed. We examined the effect that this had on solutions
provided by RTBSS. The results are summarized in Table
IV. The table shows the percentage of solutions equal to the
optimal solution in case of slow, medium or fast dynamics
for either the universal sensor upper bound VuπG from Pu or
the k-step sensor upper bound VkπG from Pk .
Optimal solutions are found in the majority of cases, with
the percentage decreasing as the optimization horizon is

greater and the rate of dynamics faster. Since often VkπG (b) <
VuπG (b), it is more likely that the bound obtained from the
universal sensor relaxation does not overestimate the optimal
value, and consequently better agreement with the optimal
solution is observed. The results suggest that it may still be
reasonable to approximate upper bounds for V ∗ by the value
of greedy policies in the relaxed problems Pu or Pk , even if
their optimality cannot be guaranteed.
Efficiency of pruning the search tree was not affected
significantly compared to the case of the previous subsection.
Applying either bound dramatically reduced the number of
visited nodes in the search tree. We examined the mean time
required to find a solution for a belief state either by exhaustive search or branch-and-bound pruning. A representative
comparison is presented in Fig. 2 for the case of medium
dynamics. For T < 3, exhaustive search performs fastest: the
computational burden of computing the bounds outweighs
the savings from visiting fewer nodes during the search. The
advantages of pruning the search tree become apparent for
T ≥ 4. At best, applying pruning is an order or magnitude
faster than exhaustive search. For T ≥ 3, the upper bound
from Pk is fastest. Using the upper bound from Pu is faster
than exhaustive search for T ≥ 5. Comparing computation
times between POMCP and RTBSS were not meaningful, as
the experiments were run on different computer platforms
with different implementations of e.g. the search trees.

10
10
Average runtime [ms]

MC simulations

P ROPERTY 2 WAS NOT SATISFIED .

10
10
10
10
10

Case: Medium dynamics

4

3

2

1

0

Exhaustive
Pu

−1

Pk

−2

1

2

3
4
Optimization horizon T

5

6

Fig. 2. The mean runtime per decision in milliseconds as a function of
optimization horizon T for the exhaustive and branch-and-bound search
applying upper bounds from Pu or Pk .

TABLE III
P ERFORMANCE LOSS OF POMCP COMPARED TO
T =2
MC simulations
101
102
103
104

Mean
0.0749
0.0298
0.0122
0.0064

Max
0.3930
0.2296
0.1025
0.0503

T =3
Mean
0.0948
0.0518
0.0294
0.0168

Max
0.5278
0.3299
0.1751
0.0893

VII. CONCLUSIONS
An optimal sensing problem in a mixed-observability
domain where an internal state is fully observable and a set of
inference variables are partially observable was formulated
as a POMDP. The objective was the sequential maximization
of mutual information of the inference variables and observations. Upper bounds for the optimal value function were
found by relaxing constraints of the original problem.
When three conditions are fulfilled, the relaxed problems
are MABs. First, each action is related to a unique subset
of inference variables. Secondly, only inference variables
in the subset corresponding to the current action evolve,
while the other inference variables remain stationary. Finally,
observations depend only on the inference variables in the
subset related to the current action. The optimal solution of
a MAB problem is a greedy index allocation policy, which
is much easier to find than solving a general POMDP.
The POMDP was solved by a branch-and-bound search.
The effectiveness of the bounds for pruning the search space
was empirically verified in a target monitoring problem.
Finding an optimal action by requires searching a fraction
of the reachable belief states compared to an exhaustive
search. Computation time is at best an order of magnitude
smaller when applying pruning. The computational savings
become apparent when savings due to reduced search space
size exceed the additional cost of computing the bounds.
Future work includes studying applicability of our methodology in a wider range of mixed observability domains. Motivated by positive results on optimality of greedy policies for
the restless bandit problem [23], we believe there may exist
more classes of stochastic control problems than currently
known where a greedy policy is optimal. Identifying such
classes would further expand the applicability of our results.
R EFERENCES
[1] L. Kaelbling, M. Littman, and A. Cassandra, “Planning and acting in
partially observable stochastic domains,” Artificial Intelligence, vol.
101, no. 1-2, pp. 99–134, 1998.
[2] A. O. Hero, D. Castañón, D. Cochran, and K. Kastella, Eds., Foundations and Applications of Sensor Management. New York, NY:
Springer, 2007.
[3] E. K. P. Chong, C. M. Kreucher, and A. O. Hero, “Partially Observable
Markov Decision Process Approximations for Adaptive Sensing,”
Discrete Event Dynamic Systems, vol. 19, no. 3, pp. 377–422, May
2009.
[4] B. Charrow, V. Kumar, and N. Michael, “Approximate representations
for multi-robot control policies that maximize mutual information,”
Autonomous Robots, vol. 37, no. 4, pp. 383–400, Aug. 2014.

T =4
Mean
0.1061
0.0584
0.0402
0.0261

Max
0.5283
0.2953
0.2035
0.1399

OPTIMAL .

T =5
Mean
0.1084
0.0642
0.0487
0.0317

Max
0.5587
0.3251
0.3639
0.1816

T =6
Mean
0.1175
0.0670
0.0518
0.0380

Max
0.6278
0.3968
0.2839
0.2020

[5] N. Atanasov, J. Le Ny, K. Daniilidis, and G. Pappas, “Information
Acquisition with Sensing Robots: Algorithms and Error Bounds,” in
IEEE Int. Conf. on Robotics and Automation (ICRA), Hong Kong,
China, June 2014, pp. 6447–6454.
[6] M. Lauri and R. Ritala, “Stochastic control for maximizing mutual
information in active sensing,” in ICRA 2014 Workshop on Robots in
Homes and Industry: Where to Look First?, Hong Kong, China, June
2014.
[7] E. A. Hansen, “Indefinite-horizon POMDPs with action-based termination,” in Proceedings of the National Conference on Artificial
Intelligence, Vancouver, Canada, July 2007, pp. 1237–1242.
[8] C. H. Papadimitriou and J. N. Tsitsiklis, “The Complexity of Markov
Decision Processes,” Mathematics of Operations Research, vol. 12,
pp. 441–450, 1987.
[9] M. T. Spaan and N. A. Vlassis, “Perseus: Randomized point-based
value iteration for POMDPs,” Journal of Artificial Intelligence Research, vol. 24, pp. 195–220, 2005.
[10] J. Pineau, G. Gordon, and S. Thrun, “Anytime point-based approximations for large POMDPs,” Journal of Artificial Intelligence Research,
vol. 27, no. 1, pp. 335–380, 2006.
[11] S. Ross, J. Pineau, S. Paquet, and B. Chaib-Draa, “Online planning
algorithms for POMDPs,” Journal of Artificial Intelligence Research,
vol. 32, pp. 663–704, 2008.
[12] D. Silver and J. Veness, “Monte-Carlo Planning in Large POMDPs,”
in Advances in Neural Information Processing Systems 23, Vancouver,
Canada, Dec. 2010, pp. 2164–2172.
[13] S. C. Ong, S. W. Png, D. Hsu, and W. S. Lee, “Planning under
uncertainty for robotic tasks with mixed observability,” International
Journal of Robotics Research, vol. 29, no. 8, pp. 1053–1068, 2010.
[14] A. O. Hero and D. Cochran, “Sensor management: Past, present, and
future,” IEEE Sensors Journal, vol. 11, no. 12, pp. 3064–3075, 2011.
[15] R. Bellman, Dynamic Programming. Princeton, New Jersey: Princeton University Press, 1957.
[16] R. D. Smallwood and E. J. Sondik, “The optimal control of partially
observable Markov processes over a finite horizon,” Operations Research, vol. 21, no. 5, pp. 1071–1088, 1973.
[17] W. S. Lovejoy, “A survey of algorithmic methods for partially observed
Markov decision processes,” Annals of Operations Research, vol. 28,
no. 1, pp. 47–65, 1991.
[18] M. Hauskrecht, “Value-function approximations for partially observable Markov decision processes,” Journal of Artificial Intelligence
Research, vol. 13, no. 1, pp. 33–94, 2000.
[19] V. Krishnamurthy and D. V. Djonin, “Structured Threshold Policies for
Dynamic Sensor Scheduling – A Partially Observed Markov Decision
Process Approach,” IEEE Transactions on Signal Processing, vol. 55,
no. 10, pp. 4938–4957, Oct. 2007.
[20] M. Araya, O. Buffet, V. Thomas, and F. Charpillet, “A POMDP
Extension with Belief-dependent Rewards,” in Advances in Neural
Information Processing Systems 23, Vancouver, Canada, Dec. 2010,
pp. 64–72.
[21] J. C. Gittins, “Bandit processes and dynamic allocation indices,”
Journal of the Royal Statistical Society. Series B (Methodological),
pp. 148–177, 1979.
[22] S. Paquet, B. Chaib-draa, and S. Ross, “Hybrid POMDP algorithms,”
in Proceedings of The AAMAS Workshop on Multi-Agent Sequential
Decision Making in Uncertain Domains, Hakodate, Japan, May 2006,
pp. 133–147.
[23] S. H. A. Ahmad, M. Liu, T. Javidi, Q. Zhao, and B. Krishnamachari,
“Optimality of myopic sensing in multichannel opportunistic access,”
IEEE Transactions on Information Theory, vol. 55, no. 9, pp. 4040–
4050, 2009.

