Myopic Policy Bounds for Information Acquisition POMDPs

0.4

0.6

0.2

0.4
0.6
p(s1 )

0.8

0

3)

p( s

0.6

0.4

0.4

0.4
0.6
p(s1 )

0.8

0.8
0.6

0.4

0.4

0.6
0.2

0.2

0.2

a3

0.8
0

0

a2

0.8

0.6
0.2

0.8

0

3)

0.6

0.4

p( s

3)

0.2

2)

p( s

0.8

a1

p( s

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, {mikko.lauri, risto.ritala}@tut.fi.
N. Atanasov and G. Pappas are with GRASP Lab, University
of Pennsylvania, Philadelphia, PA 19104, USA, {atanasov,
pappasg}@seas.upenn.edu. This work was supported by
TerraSwarm, one of six centers of STARnet, a Semiconductor Research
Corporation program sponsored by MARCO and DARPA.

0.2

Optimal policy

0

2)

The current proliferation of sensors and robots has potential
to transform fields as diverse as environmental monitoring,
security and surveillance, localization and mapping, and structure inspection. One of the technical challenges in these scenarios is to control the sensors and robots to extract accurate
information about various physical phenomena autonomously.
Robotic information acquisition may be thought of as an
optimization problem: given constraints on robot motion and
the available sensing resources, find an optimal control policy
for the robot resulting in the greatest amout of collected information. Assuming Markovian system dynamics and observations conditionally independent given the system state, the
optimization problem is formalized as a partially observable
Markov decision process (POMDP) [1]. A POMDP consists
of the state, action and observation spaces, stochastic system
dynamics and observation models and a real-valued reward
function. As the true state of the robot and environment are
unknown, a probability density function (pdf) known as a
belief state is maintained to represent information regarding
the state. The optimal control policy is a mapping from
belief states to actions such that the expected total reward
accumulated over a given optimization horizon is maximized.
While POMDPs offer a principled framework handling
probabilistic uncertainty in both control actions and sensing

Upper bound policy

0

p( s

I. I NTRODUCTION

Lower bound policy

2)

Abstract—This paper addresses the problem of optimal control
of robotic sensing systems aimed at autonomous information
gathering in scenarios such as environmental monitoring, search
and rescue, and surveillance and reconnaissance. The information gathering problem is formulated as a partially observable
Markov decision process (POMDP) with a reward function that
captures uncertainty reduction. Unlike the classical POMDP
formulation, the resulting reward structure is nonlinear in the
belief state and the traditional approaches do not apply directly.
Instead of developing a new approximation algorithm, we show
that if attention is restricted to a class of problems with certain
structural properties, one can derive (often tight) upper and
lower bounds on the optimal policy via an efficient myopic
computation. These policy bounds can be applied in conjunction
with an online branch-and-bound algorithm to accelerate the
computation of the optimal policy. We obtain informative lower
and upper policy bounds with low computational effort in a target
tracking domain. The performance of branch-and-bounding is
demonstrated and compared with exact value iteration.

p( s

arXiv:1601.07279v1 [] 27 Jan 2016

Mikko Lauri, Nikolay Atanasov, George J. Pappas, and Risto Ritala

0.2

0.8
0

0

0.2

0.4
0.6
p(s1 )

0.8

0

Fig. 1. The optimal policy µ∗ in a POMDP (shown on the right) can be
lower and upper bounded by myopic lower and upper bound policies µ∗1 and
µ∗1 (shown on the left and middle, respectively). The ternary plots cover the
belief simplex B in the three-state case with state space S = {s1 , s2 , s3 },
while the dots indicate the action selected by the policy for a particular belief
point. The inequalities µ∗1 (b) ≤ µ∗ (b) ≤ µ∗1 hold for all b ∈ B. The optimal
policy is fully determined if µ∗1 (b) = µ∗1 (b). Even if the bounds do not agree
they may provide information regarding the optimal action.

outcomes, obtaining optimal policies for them is computationally hard [2]. A wide range of algorithms for computing approximately optimal policies for POMDPs have been
proposed in the literature, see e.g. [3], [4], [5] for reviews.
Most research, however, focuses on a standard formulation in
which the reward is a function of the hidden system state, and
hence necessarily linear in the belief state. When it comes to
information gathering applications in robotics (see e.g. [6], [7],
[8], [9]), reward functions that capture uncertainty reduction
(e.g. negative Shannon entropy [10]) or information gain (e.g.,
mutual information [10]) are often more interesting. These
reward function are nonlinear in the belief state, and hence,
many of the existing approximation techniques for the standard
POMDP formulation do not apply. Approximation methods
applicable for such information acquisition POMDPs include
some online algorithms [11] and specialized value iteration
techniques, see e.g. [12]. Sampling-based online planning
algorithms, such as those based on variants of Monte Carlo
tree search (see e.g. [13], [14]), are also applicable.
Besides approximation algorithms, an alternative route to
handling the inherent complexity of POMDPs with nonlinear
belief-dependent rewards is to make structural statements
about the optimal value function. In the case of state-dependent
rewards, earlier work [15], [16], [17] shows that, if we restrict
attention to a class of POMDPs that satisfy certain assumptions
on the state and observation processes, we can bound the
optimal policy from both below and above by an easily
computable myopic (greedy) policy (see Fig. 1 for details).
The specific case of POMDP multi-armed bandits was studied
in [18].
The goal of this work is to extend these structural results to
POMDPs with belief-dependent rewards. Krishnamurthy and
Djonin [19] determined conditions under which the optimal

policy has a threshold structure with respect to the monotone
likelihood ratio (MLR) order, a partial order on the belief
states. Such partial orders on the belief states have been used
in the related active hypothesis testing field [20] to determine
when a given sensing action dominates all other actions. For
example, Naghshvar and Javidi [21] used Blackwell ordering
of the observation models to reduce an active hypothesis test
with K actions to a passive test with a single action. Compared to active hypothesis testing, information acquisition in
POMDPs is even more challenging because the true underlying
state evolves during the sensing process.
Our first contribution is to extend the structural results of
[17] for POMDPs with state-dependent rewards to POMDPs
with nonlinear belief-dependent rewards. This allows us to
generate upper and lower bounds on the optimal policy (which
agree in large portions of the belief state space and hence
determine the optimal action) via a very efficient myopic
policy computation. Our second contribution is to apply the
myopic policy bounds in conjunction with an online branchand-bound pruning algorithm to accelerate computation of the
optimal policy. Our approach allows anytime computation with
a bounded error from the optimal solution, unlike for instance
sampling-based planning which is only asymptotically optimal.
The remainder of the paper is organized as follows. Section II formulates the information acquisition problem as a
POMDP, and discusses suitable choices of reward functions.
Section III briefly reviews existing structural results. Section IV introduces our extension to belief-dependent rewards
and defines the myopic lower and upper bound policies.
In Section V, we show how to apply the myopic policy
bounds in a branch-and-bound pruning algorithm. Section VI
presents empirical evaluation in target tracking domains, and
Section VII concludes the paper.

the set of all possible pdfs over the system state. Finally, ρ :
B × A → R is the expected reward, which is a (nonlinear)
function of the belief state b.
Our definition subsumes the traditional POMDP definition
with a state-and-action-dependent reward
P function r : S×A →
R. This is seen defining ρ(b, a) := s∈S r(s, a)b(s).
The evolution of the belief state b in a POMDP is conditional on the actions and observations. When action a ∈ A
is executed, the belief state evolves according to the state
transition model T. The evolution can be tracked by Bayesian
filtering, which consists of iterating prediction and update
steps. The prediction step revises the current belief state b ∈ B
to the predicted belief ba ∈ B according to
X
ba (s0 ) =
T(s0 , s, a)b(s).
(1)

II. I NFORMATION ACQUISITION IN POMDP S

Definition 1 (Uncertainty function and information gain [22]).
An uncertainty function is a non-negative, concave function
f : B → R+ . The information gain If (b, a) of an action
a ∈ A in belief state b ∈ B is the expected reduction in the
uncertainty function f :

To model information acquisition problems in robotic applications we define a POMDP with a belief-dependent reward
function. In detail, a POMDP is a tuple hT , S, A, Z, T, O, ρi,
where T is a set of decision epochs and S = {1, 2, . . . , S},
A = {1, 2, . . . , A}, and Z = {1, 2, . . . , Z} are the finite
state, action, and observation spaces, respectively. The function
T : S × S × A → [0, 1] is a stochastic state transition
model such that T(s0 , s, a) is the probability of reaching state
s0 ∈ S from state s ∈ S after executing action a ∈ A and
O : Z × S × A → [0, 1] is a stochastic observation model such
that O(z 0 , s0 , a) is the conditional probability of observing
z 0 ∈ Z when state s0 ∈ S was reached after executing action
a ∈ A. To simplify notation, let Ta := [T(j, i, a)]Si,j=1 be
the matrix of state transition probabilities for a given action
a ∈ A, i.e. previous states are column-wise and next states
row-wise. Similarly, let Oa := [O(z, j, a)] for z ∈ Z, j ∈ S,
and a ∈ A.
As information about the system state is incomplete, it is
modeled by a probability density function (pdf) b(s), s ∈ S
over the system state. The set B, called the belief space, is

s∈S

After the state transition, an observation z 0 ∈ Z is perceived
and the information it provides is incorporated via the update
step:
b0 (s0 ) = τ (b, a, z 0 ) :=

1
· O(z 0 , s0 , a)ba (s0 ),
η(z 0 | b, a)

(2)

P
where η(z 0 | b, a) := s∈S O(z 0 , s, a)ba (s) is a normalization
factor equal to the conditional probability of observing z 0 .
A. Reward functions for information acquisition
The goal in information acquisition is to reduce the uncertainty in the unobservable state of interest s ∈ S. It is
therefore desirable to reach “peaked” belief states that have
the majority of their probability mass on a single underlying
state. In other words, actions that lead the belief state towards
the vertices of the probability simplex B should be rewarded.
Suitable measures of uncertainty are concave functions of the
belief state, called uncertainty functions [22, Sec. 14.16].

If (b, a) := f (ba ) − EZ [f (τ (b, a, Z))].

(3)

Examples of uncertainty functions include Shannon entropy,
the more-general Rényi quadratic entropy, and variants of the
value of information, such as the probability of error in hypothesis testing [10]. For example, the information gain associated
with Shannon entropy is known as mutual information.
For information acquisition tasks, either information gain
or a negative uncertainty function may be used as the reward
function in the POMDP formulation. However, as the following example shows, using an uncertainty function might
be more appropriate when the magnitude of the predicted
uncertainty f (ba ) is significantly affected by the action choice.
Example 1. Consider an active localization problem [23] in
which a mobile robot needs to choose an appropriate action
a to reduce the uncertainty in the distribution b of its current

position s. Suppose that the entropy f (b) of its current position
distribution is n bits. The robot may choose between a risky
high-velocity motion ar leading to a predicted entropy of
f (bar ) = n + m bits or a safe low-velocity motion as leading
to f (bas ) = n + h bits, where h < m. Suppose that in both
cases, after moving, the robot receives the same amount of
information, k bits, from its sensor measurement z 0 . In this
example, the negative uncertainty function correctly predicts
that action ar is risky:
−f (τ (b, ar , z 0 )) = −(n + m − k)
< −(n + h − k) = −f (τ (b, as , z))
but, perhaps surprisingly, the information gain prefers the
risky action:
If (b, ar ) = m − k > h − k = If (b, as ).
In the rest of the paper, we restrict attention to beliefdependent reward functions, specific to the task of information
gathering, which have the following form:
X
ρ(b, a) :=
r(s, a)b(s) − wa f (b),
(4)
s∈S

where f is an uncertainty function (preferred to information
gain due to the observations in Example 1), r(s, a) is any
standard state-dependent reward function, and wa are userspecified weights that trade-off measurement rewards and state
uncertainty.
B. Value functions and optimal policies

the value iteration must be solved is uncountable, the basic
scheme above rarely results in practical methods for computing
optimal policies.
III. M YOPIC POLICY BOUNDS FOR POMDP S
In this section, we review existing results on myopic policy
bounds for POMDPs with state-depend rewards. The idea of
a myopic policy bound is that the optimal policy µ∗k for any
k can be either lower or upper bounded by the myopic policy
µ∗1 (Eq. 8). The results exploit concepts of stochastic partial
orders, summarized in the following definition.
Definition 2 (Stochastic partial orders [25]). Let b1 , b2 ∈ B.
1) b1 first-order stochastically domainates b2 , denoted b1 ≥s
S
S
P
P
b2 , if
b1 (i) ≥
b2 (i) ∀j ∈ S.
i=j

i=j

2) Equivalently, b1 ≥s b2 iff

S
P
i=1

b1 (i)g(i) ≥

S
P

b2 (i)g(i)

i=1

for all increasing functions g : S → R.
3) b1 is greater than b2 in the monotone likelihood ratio (MLR) order, denoted b1 ≥r b2 , if b1 (i)b2 (j) ≤
b2 (i)b1 (j), for all i < j, j ∈ S.
4) A function g : B → R is MLR increasing (decreasing) if
b1 ≥r b2 ⇒ g(b1 ) ≥ g(b2 ) (g(b1 ) ≤ g(b2 )).
5) MLR dominance implies first-order stochastic dominance,
b1 ≥r b2 ⇒ b1 ≥s b2 .
Given conditions on the state transition and observation
models, it was shown in [15], [16] that the optimal value
function is MLR increasing and that the optimal policy may
be lower bounded by µ∗1 . The required conditions, however,
were thought to be too restrictive to be of practical significance
until a recent extension [17] proposed the following revised
assumptions.

Let H ∈ N ∪ {∞} denote a planning horizon so that
T := {1, 2, . . . , H}, and let 0 ≤ γ ≤ 11 denote a discount
factor determining the relative value of immediate and future
rewards. The goal in information acquisition is to choose a
policy µ∗k : B → A for each k ∈ T such that the expected Assumption 1 (Sufficient conditions for existence of myopic
sum of rewards over the decisions epochs is maximized. The policy bounds [17]).
sequence of optimal policies µ∗k for k ∈ T remaining decisions (A1) Ta and Oa are totally positive or order 2 (TP2) ∀a ∈ A,
(A2) For all j ∈ {1, 2, . . . , S − 1}, a ∈ {1, 2, . . . , A − 1}, and
can be computed via value iteration [24] according to:
j,a,z
S×S
z ∈ Z, the matrices Dj,a,z := [dj,a,z
m,n + dn,m ] ∈ R
a+1
a+1
Q∗1 (b, a) = ρ(b, a)
(5)
j,a,z
a
a
are copositive, where dm,n := Oz,j Oz,j+1 Tm,j Tn,j+1 −
a+1
a
Vk∗ (b) = max Q∗k (b, a),
(6)
Oaz,j+1 Oa+1
z,j Tm,j+1 Tn,j , and 
a∈A
P
P
a+1
X
(A3)
Tai,j Oaz,j − Ta+1
≥ 0, ∀i ∈ S, ∀z̄ ∈ Z,
∗
i,j Oz,j
Q∗k (b, a) = ρ(b, a) + γ
η(z 0 | b, a)Vk−1
(τ (b, a, z 0 )), (7)
z≤z̄ j∈S
z 0 ∈Z
∀a ∈ {1, 2, . . . , A − 1}.
µ∗k (b) = argmax Q∗k (b, a),
(8)
The TP2 property for a matrix requires that all its seconda∈A
order minors are nonnegative [26]. Examples of TP2 obser∗
where Vk : B → R is the optimal value function. For infinitevation models include exponential family distributions such
horizon problems with H → ∞ and bounded rewards, value
as Gaussian, exponential, gamma, and binomial pdfs [26];
∗
iteration converges to a unique fixed point V that satisfies
more examples may be found e.g. in [27]. While (A2) may
the Bellman equation:
be checked directly [28], it is much more efficient (but also
X
V ∗ (b) = ρ(b, a) + γ
η(z 0 | b, a)V ∗ (τ (b, a, z 0 )), (9) more restrictive) to check the following:
j,a,z
(A2’) dj,a,z
z 0 ∈Z
m,n + dn,m ≥ 0 for all m, n ∈ S, j ∈ {1, . . . , S − 1},
a ∈ {1, 2, . . . , A − 1}, and z ∈ Z.
and the corresponding optimal infinite-horizon policy µ∗ is
Assumption
(A3) is a revised version of the original assumpstationary [24]. As the set B of belief states over which
tion in [15], [16]. It states that for every state i ∈ S, the prior
1 Note that γ = 1 is only valid for finite H.
pdf of perceiving z ∈ Z after ending in state j ∈ S after

executing action a + 1 first order stochastically dominates that
of action a. The assumptions lead to the following lemma.
Lemma 1 ([17]). Consider a POMDP hT , S, A, Z, T, O, ρi.
Then for all b ∈ B, and a0 , a ∈ A, a0 ≥ a,
(L1) if (A3) holds, η(z 0 | b, a0 ) ≥s η(z 0 | b, a), and
(L2) if (A2) holds, τ (b, a0 , z 0 ) ≥r τ (b, a, z 0 ) for all z 0 ∈ Z.
The following theorem for POMDPs with rewards linear in
the belief state is due to [15, Prop. 2] and [17, Theorem 1]:
Theorem 1. Consider a POMDP hT , S, A, Z, T, O, ρi
satisfying
Assumptions (A1)-(A3), with ρ(b, a)
:=
P
r(s,
a)b(s).
If
r(s,
a)
is
increasing
(decreasing)
s∈S
in S for all a ∈ A, then the optimal value function Vk∗ is
MLR increasing (decreasing) and the optimal policy µ∗k (b) for
any k ∈ T satisfies µ∗1 (b) ≤ µ∗k (b) (µ∗1 (b) ≥ µ∗k (b)) ∀b ∈ B.
IV. T RANSFORMED MLR MONOTONE REWARDS FOR
INFORMATION ACQUISITION POMDP S
In this section, we extend Theorem 1 to apply to reward
functions of the form in (4), which are of interest for information acquisition tasks. To proceed, we need the following
minor extension of Theorem 1.
Corollary 1. Consider a POMDP hT , S, A, Z, T, O, ρi satisfying Assumptions (A1)-(A3) and suppose that ρ is MLR
increasing (decreasing) in B for all a ∈ A. Then, the
optimal policy µ∗k (b) for any k ∈ T satisfies µ∗1 (b) ≤ µ∗k (b)
(µ∗1 (b) ≥ µ∗k (b)) ∀b ∈ B.
Proof. By [15, Prop. 2], it suffices to show Vk∗ is MLR
increasing. We proceed by induction. For the base case k = 1,
V1∗ (b) = max ρ(b, a) is clearly MLR increasing. For the
a∈A
∗
induction step, suppose the claim holds for Vk−1
. Consider
the sum part of the value iteration in Eq. (7). Let b1 , b2 ∈ B
s.t. b1 ≥r b2 . Now
Z
X

≥

z 0 =1
Z
X

∗
η(z 0 | b1 , a)Vk−1
(τ (b1 , a, z 0 ))

∗
η(z 0 | b2 , a)Vk−1
(τ (b1 , a, z 0 ))

(10)

z 0 =1

≥

Z
X

∗
η(z 0 | b2 , a)Vk−1
(τ (b2 , a, z 0 )).

z 0 =1

The first inequality follows by Lemma (L1), [15,
Lemma 1.2(2),1.3(1)] which state τ (b, a, z 0 ) is MLR
increasing in z 0 , and the the induction hypothesis. The
second inequality follows by Lemma (L2) and the induction
hypothesis. The proof for the MLR decreasing part is similar
and omitted.
Following the observation in Corollary 1, the main idea
is to transform the reward function ρ(b, a) (4) to one that
is MLR monotone but leaves the optimal policy unchanged.
Accordingly, we define two transformed reward functions:
ρ(b, a) = ρ(b, a) + [(I − γ(Ta )T )g]T b
ρ(b, a) = ρ(b, a) + [(I − γ(Ta )T )h]T b,

(11)

where g, h ∈ RS are parameter vectors chosen so that ρ(b, a)
is MLR increasing and ρ(b, a) is MLR decreasing in B.
Note that, by construction the transformed rewards in (11)
leave the optimal policy unaffected. This can be verified
by plugging either one into the Bellman equation (9). The
corresponding infinite horizon value functions are V ∗ (b) =
∗
V ∗ (b) + g T b, V (b) = V ∗ (b) + hT b, and µ∗ ≡ µ∗ ≡ µ∗ [17].
The following theorem gives necessary conditions for the
existence of vectors g and h at a single belief state.
Theorem 2. Let b0 ∈ B. If there exists a g ∈ RS such that
the set of linear constraints given by
∂ρ(b, a)
∂b

K + [(I − γ(Ta )T )g]T K ≥ 0

∀a ∈ A (12)

b=b0

where K is an S-by-S matrix with entries
(
1
if i = j
,
kij =
−1 if j = i + 1

(13)

are satisfied, then ρ(b, a) as defined in Eq. (11) is MLR
increasing at b0 .
Proof. As in the supplementary material of [17], let ∆ = {δ ∈
RS : 1 = δ(1) ≥ δ(2) ≥ . . . ≥ δ(S)}. Any belief state b ∈ B
may be represented as δ = Kb ∈ ∆. Let b1 = Kδ1 , b2 =
Kδ2 such that b1 ≥r b2 . By Definition 2, b1 ≥s b2 , and the
equivalent partial order on ∆ ⊂ RS is the component-wise
partial order between δ1 and δ2 . Then, the function ρ(Kδ, a)
is increasing on ∆ if its partial derivatives are non-negative:
∂ρ(Kδ, a)
∂ρ(Kδ, a) ∂[(I − γ(Ta )T )g]T Kδ
=
+
∂δ
∂δ
∂δ
(14)
∂ρ(b, a)
a T
=
K + [(I − γ(T ) )g]T K ≥ 0
∂b
and the claim follows by evaluating the derivative at b0 .
The proof for ρ(b, a) being MLR decreasing is obtained
similarly, by swapping the required sign for the partial derivatives. Practically, the condition of the theorem may be checked
by solving a feasibility linear program (LP) with (S − 1) · A
constraints. If a single g and h may be chosen such that the
transformed rewards are MLR monotone for all b ∈ B, then
the myopic policies
µ∗1 (b) = argmax ρ(b, a)
a∈A

µ∗1 (b) = argmax ρ(b, a)

(15)

a∈A

satisfy µ∗1 (b) ≤ µ∗ (b) ≤ µ∗1 (b) for all b ∈ B. This follows from
Corollary 1, and the fact that the optimal stationary policy is
unaffected by applying the transformed rewards. It is imporant
to note that the preceding inequalities do not hold anymore for
finite horizon optimal policies.
Consider the following two examples of nonlinear beliefdependent reward functions obtained by applying different
uncertainty functions in Eq. (4). In both examples, we denote
by ra the column vector formed from the elements of r(s, a)
for all s ∈ S.

Original reward

Example 2 (Shannon Entropy). Let the uncertainty function
in (4) be the Shannon entropy:
f (b) := −

S
X

Transformed reward

ρ(b, a1 )
ρ(b, a2 )

b(i) log b(i).

i=1

The derivative of ρ(b, a) for the constraints in Thm. 2 is:


∂ρ(b, a)
= raT + wa 1 + log(b(1)), . . . 1 + log(b(S)) .
∂b
As log(0) is not well defined, we consider the inner belief
simplex B := {b ∈ B | ∀i : b(i) ≥ } for  ∈ (0, 1). Note that
log() ≤ log(b(i + 1)) − log(b(i)) ≤ − log().
For i = 1, . . . , S −1 and ∀a ∈ A, the ith constraint in Eq. (12)
can then be bounded by a belief-independent quantity:
φai − φai+1 ≥ wa (log(b(i + 1) − log(b(i))) ≥ −wa log(),
where φa := ra + (I − γ(Ta )T )g.
Example 3 (Rényi Quadratic Entropy). Let the uncertainty
function in (4) be the Rényi quadratic entropy:
f (b) := − log

S
X

b2 (i).

i=1

The derivative of ρ(b, a) for the constraints in Thm. 2 is:
2wa
∂ρ(b, a)
= raT + PS
bT .
2 (i)
∂b
b
i=1
S

and

0.2 0.4 0.6 0.8 1 0
p(s = 1)

0.2 0.4 0.6 0.8 1
p(s = 1)

Fig. 2. Expected original (left axes) and transformed (right axes) rewards as
function of the belief state according to Example 3. Rewards for action a1 are
shown by a solid line and for action a2 by a dashed line. The increasing blue
curves in the right axes depict the MLR increasing rewards ρ(b, a), and the
decreasing red curves depict the MLR decreasing rewards ρ(b, a). The two
regions on the right axes indicated by lines starting and ending with circle
markers are the parts of the belief space where the optimal policy is fully
determined by the myopic policy bounds. The dashed region corresponds to
µ∗1 (b) = µ∗1 (b) = a2 and the solid region to µ∗1 (b) = µ∗1 (b) = a1 .

is equivalent to the familiar notion of monotonicity on R. On
the bottom of the right axes, two regions in B are indicated
by a dashed and a solid line. These are regions where the
myopic policy bounds agree and the optimal policy is thus
fully determined.
V. M YOPIC BOUNDS FOR BRANCH - AND - BOUND PRUNING

Note that:
−1 ≤ b(i + 1) − b(i) ≤ 1

0

X
1
b2 (i) ≤ 1,
≤
S
i=1

which can be used to obtain belief-independent bounds in (12).
In particular, the ith constraint in (12) may be bounded by a
belief-independent quantity:
2wa
φai − φai+1 ≥ PS
(b(i + 1) − b(i)) ≥ −2wa ,
2
j=1 b (j)
where φa := ra + (I − γ(Ta )T )g and i = 1, . . . , S − 1.
In both examples, belief independent bounds for finding
h are obtained with straightforward changes. For Shannon
entropy, one ideally wants to choose  as small as possible to
cover the greatest possible subset of the belief space. On the
other hand, the smaller  is, the more restrictive the constraints
become, making it more unlikely to find feasible solutions. The
issue is resolved by considering a different quantification of
uncertainty, such as the Rényi quadratic entropy.
Figure 2 shows an example of the transformation of Rényi
quadratic entropy rewards and the associated monotonicity
properties as discussed in Example 3. The left axes show
the original expected reward as function of the belief state,
and the right axes show the transformed MLR increasing and
decreasing rewards, respectively. For S = 2, the belief space
B can be represented by [0, 1] ⊂ R and MLR monotonicity

The significance of Theorems 1 and 2 is that they give a
prescription for constructing policy bounds µ∗1 (b) ≤ µ∗ (b) ≤
µ∗1 (b) for all b ∈ B. In this section, we show that the
bounds can be used in an online branch-and-bound scheme to
accelerate the computation of the optimal policy for POMDPs
that satisfy Assumption 1.
Branch-and-bound pruning for POMDPs is based on a tree
search over the set of belief states reachable by finite-length
action and observation sequences, see e.g. [11]. The search is
started from the current belief state b0 at the root of the search
tree. The tree branches due to action choices and observation
possibilities, so that each node corresponds to a belief state
b reachable from b0 via the prediction and update iteration
in (1), (2). The standard branch-and-bound algorithm works
with lower and upper bounds on the optimal action values,
i.e., Qk (b, a) ≤ Q∗k (b, a) ≤ Qk (b, a). Starting from node b,
the subtree corresponding to action a may be pruned if it is
known to be suboptimal (i.e, the upper bound Qk (b, a) is lower
than the lower bound Qk (b, â) for some other action â), thus
saving computational resources.
Following the intuition of the branch-and-bound scheme
above, we design a new algorithm (Alg. 1), which employs
our policy bounds, instead of bounds on the optimal action
values. Given a belief state b and a search depth d > 0, the
algorithm constructs a search tree over reachable belief states,
storing the estimate of the value Q̂(b, a) for each visited belief
state. Only actions within the myopic lower and upper bound
policies are considered.

Algorithm 1 Branch-and-bound with myopic policy bounds.
Input: Belief state b, search depth d
Output: Estimate of the value of the best action at b
1: function S EARCH (b, d)
2:
if d = 1 then return max ρ(b, a)
a
3:
end if
do
4:
for all a ∈ A ∩ [µ∗1 (b), µ∗1 (b)] 
P
5:
Q̂(b, a) ← ρ(b, a) + γ
η(z 0 | b, a)
z 0 ∈Z

6:
×S EARCH(τ (b, a, z 0 ), d − 1)
end for
return max Q̂(b, a)
a
9: end function

7:
8:

for each action a ∈ A

q



(1 − q)/2
Oaz,j =

(1 − q)



0

has elements
if z = j
if j 6= 1, i 6= S and |z − j| = 1
, (16)
if j = 1, i = S and |z − j| = 1
otherwise

i.e. with probability q < 1 the observation identifies the true
state, with symmetric error probability in either direction.
This model corresponds to a situation where e.g. entering a
dangerous state is perceived e.g. by the robot being damaged
by hazardous environmental conditions. This class of target
tracking domains can be checked to satisfy Assumptions 1.
A. Minimizing the uncertainty of the target state

The next proposition follows from [11, Theorem 3.1].
Proposition 1. After Alg. 1 terminates, its action recommendation â is guaranteed to coincide with the optimal action
a∗ := µ∗ (b) if the myopic lower and upper bounds agree at
b, i.e., if µ∗1 (b) = µ∗1 (b). Otherwise, the suboptimality of â is
of order γ d , i.e., |Q∗ (b, â) − Q∗ (b, a∗ )| ∼ o(γ d ).
VI. A PPLICATION TO TARGET T RACKING
We evaluate the performance of Algorithm 1 in a target
tracking application. Let s ∈ S model the state of a physical
process of interest such as the position of an adversarial
aircraft or certain environment conditions (e.g., temperature,
chemical concentration, air pollution, etc.). Let s = 1 correspond to an innocuous target state (e.g., the aircraft poses no
danger or the environment levels are normal) and, at the other
extreme, let s = S correspond to a red-alert state in which
there is imminent danger. We aim to design a control policy
for an autonomous robotic platform to track the target state s.
Let the available robot actions A = {1, 2, . . . , A} model the
priority invested into tracking the target, with 1 corresponding
to greatest priority (e.g, all available resources being dedicated
to tracking the target) and A corresponding to lowest effort,
i.e. the target is not being tracked.
The state transition model is such that the lower the priority
invested into tracking, the more likely it is to transition to
a state that is considered dangerous. Conversely, the higher
the priority given to tracking, the less likely it is to accidentally enter a dangerous state. In other words, supposing
the current state is i, the likelihood of transitioning to state
j > i should increase as function of a. State transition
matrices Ta modeling this can be defined e.g. as follows.
Let {xi }Si=1 and {yj }SA
j=1 be two increasing sequences of real
numbers, and define a matrix Aij = exp(xi yj ), normalizing
it such that each column sums to one, and define Ta as the
submatrix of A containing all rows and columns j for which
1 + (a − 1) · S ≤ j ≤ a · S. Each Ta also satisfies the required
TP2 condition [26].
The robot has access to Z = S observations providing
information about the target state. The observation matrix Oa

We first consider target tracking with a penalty for uncertain
tracker state information. We set S = A = Z = 3 and defined
the sequences {xi } = {1, 2, 3}, {yj } = {−9, −8, . . . , −1}.
The observation model was as defined in Eq. (16). The reward
was as in Eq. (4), with


2 2.5 1
r(s, a) = 1.1 1.2 0.5 ,
(17)
0.3 2 0.2


wa = 1.1 1.6 1 , and f equal to Rényi quadratic entropy.
The discount factor was γ = 0.99, and the observation
accuracy parameter was q = 0.7.
We computed the lower and upper myopic policy bounds for
the problem. The bounds are visualized on the belief simplex
B in Figure 1. The figure shows on the left and middle the
lower and upper myopic policies, and on the right the optimal
policy determined when the two bounds agree.
We defined a larger problem with S = Z = 8 and A = 3,
and in it compared Algorithm 1 against an exhaustive tree
search. There are Nd = (AZ)d reachable belief states after d
decisions,
Pdand the number of belief states in a complete search
tree is i=0 Ni .
TABLE I
AVERAGE PERCENTAGE OF BELIEF STATES PRUNED AS FUNCTION OF THE
SEARCH DEPTH d APPLYING THE MYOPIC POLICY BOUNDS .

Belief states pruned

d=2

d=3

d=4

d=5

d=6

26.3%

36.3%

44.9%

52.3%

58.8%

Table I shows the average percentage of belief state pruned
from the search tree for 100 randomly sampled initial belief
states. Computing the myopic policy bound requires solving
a feasibility LP with (S − 1) · A constraints offline, and
then during the search computing for each belief encountered
the action maximizing the immediate expected transformed
reward. Empirically, we found that for d ≥ 3 branch-andbounding was faster than the exhaustive search measured by
computation time.

B. Comparison with existing approaches

1
s
1
S−s+1

if s ∈ Sp
if s ∈ Sd
otherwise

(18)

where Sp and Sd are the regions of the state space corresponding to poor and dangerous tracking, respectively, and cp and
cd are the respective penalty costs. If the state is not in Sl or
Sh , a tracking reward proportional to kr is received.
1
In our experiments, we set ca = 2A
, cp = 1, cd = 0.1, and
2
kr = S . Furthermore, we set Sl = {s ∈ S | s ≤ S/5} and
Sh = {s ∈ S | s ≥ 9S/10}, and γ = 0.99. The observation
accuracy parameter was q = 0.8.
Table II shows the minimum, average and maximum percentage of actions that could be pruned by applying the myopic
policy bounds as function of the domain size. A value of
0% would indicate that the bounds were completely noninformative, and a value of 100% that the optimal policy is
fully determined by the bounds. The results were obtained by
evaluating the bounds with 500 randomly sampled reachable
belief states in each problem. We note that pruning efficiency
tends to decrease both as function of the state space and action
space size, but in all cases at least one third pruning rate was
achieved even in the worst case. For S = 256 and A = 64, a
vector satisfying the constraints of Thm. 2 could not be found.
As we computed the optimal solution, we could examine
how close the bounds are to the optimal policy. Figure 3 shows
an example of the looseness of the upper bound measured
by the average of µ∗1 (b) − µ∗ (b) over the 500 belief states.
The greater the difference is, the further away the myopic
upper bound policy is from the optimal policy, and the less
informative it is. We note that even as the number of states
and actions increases, the upper bound remains at a distance
of less than 10 actions from the optimal.
2 We applied the implementation from the pomdp-solve package of A.
Cassandra, see http://pomdp.org

µ∗1 (b) − µ∗ (b)

Next, we compare the performance of our approach to an
optimal incremental pruning algorithm2 in a target tracking
scenario with a state space size S between 4 and 256, and
action space size A between 4 and 64. Since the incremental
pruning algorithm (as well as other existing approaches)
can handle only state-dependent rewards, we do not add an
uncertainty function to the reward, i.e., f ≡ 0 in (4). The
state-dependent reward r(s, a) is designed to 1) incur a lower
reward for investing higher priority in target tracking and to 2)
penalize for both tracking the target poorly or too dangerously.
The penalty on dangerous tracking models a situation where
attempting to track the state too aggressively may make the
robot vulnerable to environmental hazards. The reward is set
as r(s, a) = −ca · (A − a + 1) + t(s, a), where ca is the cost
of expending one unit of effort in tracking, and t(s, a) is a
tracking performance reward, defined


−cp ·
t(s, a) = −cd ·


kr · s

Upper bound looseness

15

A = 16
A = 32
A = 64

10
5
0
2

4

8

16

32

64

128

256

S (log scale)
Fig. 3. The average distance between the upper bound and optimal policy as
function of state space size S for various action space sizes A.

VII. C ONCLUSION
We examined information acquisition in POMDPs with a
reward function nonlinear in the belief state. We showed
that if the POMDP fulfills certain structural properties, the
optimal infinite horizon stationary policy may be lower and
upper bounded by myopic (greedy) lower and upper bound
policies. Based on the bounds, we designed a branch-andbound pruning algorithm for online planning in POMDPs, and
demonstrated its effectiveness in a target tracking application.
The main advantage of our approach is that, if the structural
properties are satisified in the POMDP model, the resulting
branch-and-bound algorithm saves orders of magnitude in
computation compared to the existing approaches. The main
drawback is that the requred structural properties can be quite
restrictive in some applications. For example, a natural order
in the state and action spaces is required.
Future work will focus on relaxing the structural requirements while keeping track of the effect on the policy bounds.
This has potential to widen the scope of the possible applications of our apporach significantly.
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. [Online]. Available: http:
//linkinghub.elsevier.com/retrieve/pii/S000437029800023X
[2] O. Madani, S. Hanks, and A. Condon, “On the Undecidability
of Probabilistic Planning and Related Stochastic Optimization
Problems,” Artificial Intelligence, vol. 147, no. 1–2, pp. 5–34,
2003. [Online]. Available: http://www.sciencedirect.com/science/article/
pii/S0004370202003788
[3] W. Lovejoy, “A Survey of Algorithmic Methods for Partially Observed
Markov Decision Processes,” Annals of Operations Research, vol. 28,
no. 1, pp. 47–65, 1991.
[4] M. Hauskrecht, “Value-function Approximations for Partially Observable Markov Decision Processes,” Journal of Artificial Intelligence
Research, vol. 13, no. 1, pp. 33–94, 2000.
[5] G. Shani, J. Pineau, and R. Kaplow, “A Survey of Point-based POMDP
Solvers,” Autonomous Agents and Multi-Agent Systems, vol. 27, no. 1,
pp. 1–51, 2013.
[6] C. Stachniss, G. Grisetti, and W. Burgard, “Information Gain-based
Exploration using Rao-Blackwellized Particle Filters,” in Proc. Robotics:
Science and Systems (RSS), Cambridge, MA, USA, Jun. 2005.
[7] 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.

TABLE II
T HE ( MINIMUM , AVERAGE , MAXIMUM ) PERCENTAGE OF ACTIONS PRUNED IN TARGET TRACKING DOMAINS AS FUNCTION OF STATE SPACE SIZE S AND
ACTION SPACE SIZE A.
S

A=4

A=8

A = 16

A = 32

A = 64

4
8

(75.0, 94.9, 100)
(50.0, 75.0, 75)

(75.0, 83.3, 87.5)
(37.5, 59.5, 62.5)

(75.0, 78.7, 87.5)
(50.0, 58.0, 75.0)

(71.9, 74.7, 75.0)
(59.4, 64.9, 71.9)

(64.1, 72.0, 75.0)
(48.4, 57.6, 67.2)

16
32

(50.0, 72.7, 75)
(50.0, 73.9, 75)

(50, 65.2, 75.0)
(37.5, 58.5, 62.5)

(43.8, 61.3, 68.8)
(37.8, 54.9, 62.5)

(46.9, 55.0, 62.5)
(37.5, 49.9, 59.4)

(46.9, 55.5, 62.5)
(43.8, 52.6, 59.4)

64
128

(50.0, 71.9, 75)
(50.0, 73.2, 75)

(37.5, 60.4, 62.5)
(50, 61.1, 62.5)

(43.8, 54.0, 62.5)
(43.8, 54.7, 56.3)

(37.5, 49.6, 59.4)
(40.6, 49.3, 53.1)

(40.6, 47.9, 53.1)
(42.2, 48.3, 53.1)

256

(50.0, 72.8, 75)

(50, 60.4, 62.5)

(43.8, 50.9, 56.3)

(43.8, 49.1, 53.1)

(n/a)

[8] N. Atanasov, J. Le Ny, K. Daniilidis, and G. J. Pappas, “Information
Acquisition with Sensing Robots: Algorithms and Error Bounds,” in
Proc. IEEE International Conference on Robotics and Automation
(ICRA), Hong Kong, China, Jun. 2014, pp. 6447–6454.
[9] M. Lauri and R. Ritala, “Optimal Sensing via Multi-armed Bandit Relaxations in Mixed Observability Domains,” in Proc. IEEE International
Conference on Robotics and Automation (ICRA), Seattle, WA, May
2015, pp. 4807–4812.
[10] T. Cover and J. Thomas, Elements of Information Theory. John Wiley
& Sons, 2012.
[11] S. Ross, J. Pineau, S. Paquet, and B. Chaib-draa, “Online planning
algorithms for POMDPs,” Journal of Artificial Intelligence Research,
vol. 32, no. 1, pp. 663–704, 2008. [Online]. Available: http:
//www.aaai.org/Papers/JAIR/Vol32/JAIR-3217.pdf
[12] M. Araya-López, O. Buffet, V. Thomas, and F. Charpillet, “A POMDP
Extension with Belief-dependent Rewards,” in Advances in Neural
Information Processing Systems 23, J. Lafferty, C. Williams, J. ShaweTaylor, R. Zemel, and A. Culotta, Eds., Vancouver, Canada, Dec. 2010,
pp. 64–72.
[13] D. Silver and J. Veness, “Monte-Carlo Planning in Large POMDPs,”
in Advances in Neural Information Processing Systems 23, J. Lafferty,
C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, Eds., Vancouver, Canada, Dec. 2010, pp. 2164–2172.
[14] A. Somani, N. Ye, D. Hsu, and W. S. Lee, “DESPOT: Online POMDP
Planning with Regularization,” in Advances in Neural Information
Processing Systems 26, C. J. C. Burges, L. Bottou, M. Welling,
Z. Ghahramani, and K. Q. Weinberger, Eds. Curran Associates, Inc.,
2013, pp. 1772–1780. [Online]. Available: http://papers.nips.cc/paper/
5189-despot-online-pomdp-planning-with-regularization.pdf
[15] W. S. Lovejoy, “Some Monotonicity Results for Partially Observed
Markov Decision Processes,” pp. 736–743, 1987.
[16] U. Rieder, “Structural results for partially observed control models,”
ZOR Zeitschrift für Operations Research Methods and Models of
Operations Research, vol. 35, no. 6, pp. 473–490, Nov. 1991. [Online].
Available: http://link.springer.com/10.1007/BF01415990
[17] V. Krishnamurthy and U. Pareek, “Myopic Bounds for Optimal Policy
of POMDPs: An Extension of Lovejoys Structural Results,” Operations
Research, vol. 63, no. 2, pp. 428–434, Apr. 2015. [Online]. Available:
http://pubsonline.informs.org/doi/10.1287/opre.2014.1332
[18] V. Krishnamurthy and B. Wahlberg, “Partially Observed Markov Decision Process Multiarmed Bandits–Structural Results,” Mathematics of
Operations Research, vol. 34, no. 2, pp. 287–302, 2009.
[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. [Online]. Available: http:
//ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4305446
[20] M. Naghshvar and T. Javidi, “Active sequential hypothesis testing,”
The Annals of Statistics, vol. 41, no. 6, pp. 2703–2738, Dec. 2013.
[Online]. Available: http://projecteuclid.org/euclid.aos/1387313387
[21] ——, “Active M-ary sequential hypothesis testing,” in 2010 IEEE
International Symposium on Information Theory, vol. 1, no. 1. IEEE,
Jun. 2010, pp. 1623–1627. [Online]. Available: http://ieeexplore.ieee.
org/lpdocs/epic03/wrapper.htm?arnumber=5513381
[22] M. H. DeGroot, Optimal Statistical Decisions. Hoboken, New Jersey:
John Wiley & Sons, Inc., 2004, Wiley Classics Library edition.

[23] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics. Cambrdige,
MA: The MIT Press, 2006.
[24] D. Bertsekas and S. Shreve, Stochastic Optimal Control: The DiscreteTime Case. Athena Scientific, 1996.
[25] M. Shaked and J. G. Shanthikumar, Stochastic Orders. New
York, NY: Springer New York, 2007. [Online]. Available: http:
//link.springer.com/10.1007/978-0-387-34675-5
[26] S. M. Fallat and C. R. Johnson, Totally Nonnegative Matrices. Princeton, NJ: Princeton University Press, 2011.
[27] S. Karlin, Total Positivity. Stanford University Press, 1968.
[28] W. Kaplan, “A Test for Copositive Matrices,” Linear Algebra and its
Applications, vol. 313, no. 1-3, pp. 203–206, 2000.

