Weak Adaptive Submodularity and Group-Based Active Diagnosis with
Applications to State Estimation with Persistent Sensor Faults

arXiv:1701.06731v2 [math.OC] 12 Apr 2017

Sze Zheng Yong a

Lingyun Gao b

Abstract— In this paper, we consider adaptive decisionmaking problems for stochastic state estimation with partial
observations. First, we introduce the concept of weak adaptive submodularity, a generalization of adaptive submodularity,
which has found great success in solving challenging adaptive
state estimation problems. Then, for the problem of active diagnosis, i.e., discrete state estimation via active sensing, we show
that an adaptive greedy policy has a near-optimal performance
guarantee when the reward function possesses this property. We
further show that the reward function for group-based active
diagnosis, which arises in applications such as medical diagnosis
and state estimation with persistent sensor faults, is also weakly
adaptive submodular. Finally, in experiments of state estimation
for an aircraft electrical system with persistent sensor faults,
we observe that an adaptive greedy policy performs equally
well as an exhaustive search.

I. I NTRODUCTION
The operation and control of complex cyber-physical
systems often requires the choice of a sequence of decisions under partial observability. This problem of adaptive
decision-making appears in various applications, both in the
context of stochastic control (e.g., in robot navigation [1] and
reinforcement learning [2]) and stochastic state estimation
(e.g., in information gathering in robotics [3], [4], fault
diagnosis in nuclear plants [5] and sensor placement [6],
[7]). In particular, the research area of active diagnosis and
active learning, i.e., the problem of discrete object or state
identification through a minimal number of sequential actions, has many real-world applications in medical diagnosis
and emergency response [8], [9], electrical systems diagnosis
[10], scheduling [11], etc. Hence, progress in this direction
can have a significant impact on a broad range of problems
in robotics, cyber-physical systems and artificial intelligence.
Literature Review. Finding optimal policies for general
partially observable stochastic estimation problems is often
an intractable combinatorial optimization problem. Hence,
researchers, e.g., [12], [13] in the context of actuator and
sensor placement, have appealed to a diminishing returns
property known as submodularity, which plays a similar
role in combinatorial optimization as convexity in continuous optimization. Moreover, a recent paper [6] introduced
the notion of adaptive submodularity for set functions that
extends submodularity to the adaptive setting, i.e., when
This work was supported by an Early Career Faculty grant from NASA’s
Space Technology Research Grants Program and DARPA grant N6600114-1-4045 and was done at the University of Michigan, Ann Arbor.
a School for Engineering in Matter, Transport and Energy, Arizona State
University, Tempe, AZ, USA. (email: szyong@asu.edu)
b Department of Electrical Engineering and Computer Science,
University of Michigan, Ann Arbor, MI, USA. (e-mail:
{glingyun,necmiye}@umich.edu)

Necmiye Ozay b

actions are sequentially chosen based on observations, and
provided near-optimal performance guarantees for adaptive
greedy policies. However, there are many applications in
which greedy policies perform very well even when the
objective function in question is not adaptive submodular.
This was observed in [14] in the non-adaptive setting, where
“near-submodular” set functions are shown to also lead to
near-optimal performance guarantees. The paper [15] hinted
that this will hold in the adaptive case, but without providing
formal justification. Thus, there is still a need for a rigorous
definition of “near-submodular” set functions in the adaptive
setting, and for the derivation of performance guarantees for
adaptive decision-making problems with such functions.
For the problem of active diagnosis (a.k.a. adaptive
stochastic maximization), where actions or queries are selected sequentially to maximize the accuracy of diagnosis
with a given budget of actions, [6] showed that the reward
function for this problem is adaptive monotone submodular,
when outcomes are not corrupted by noise or faults. Hence,
an adaptive greedy policy yields the best polynomial-time
approximation algorithm [6]. However, the case when the
outcomes are corrupted by noise or faults is less well studied.
The papers [16], [17] considered this problem when the fault
is stochastic/non-persistent, i.e., the case when repeated measurements may yield different outcomes, but the proposed
algorithms have no provable performance guarantees. And
to our best knowledge, the active diagnosis problem with
persistent noise or faults has not been considered, although
this has been investigated for the complementary problem
known as active learning in [9], [18]. In these approaches,
proxy set functions were found to indirectly prove the nearoptimality of the original problem. However, corresponding
specialized algorithms were needed and it is unclear how
these apply to our active diagnosis problem. In fact, these
papers [9], [18] considered a more general problem of groupbased active learning, also studied in [4], of which active
learning with persistent noise is a special case. The objective
of group-based active learning is to learn the group to
which an object or objects belong, as opposed to the objects
themselves with a minimum number of actions or queries. On
the other hand, the problem of group-based active diagnosis
has, to the extent of our knowledge, not been investigated,
despite its potentially broad applicability.
Contributions. To close the gap between non-adaptive
and adaptive settings, we rigorously define the concept of
weak adaptive submodularity for set functions, as a generalization of (strong) adaptive submodularity, and prove that
an adaptive greedy policy yields competitive near-optimal

performance guarantees for the active diagnosis problem,
when the objective function is adaptive monotone and weakly
adaptive submodular. We observe that the adaptive submodularity factor that characterizes nearness to (strong) adaptive
submodularity affects the performance bound in the same
way as when approximate greedy policies are employed.
Then, we consider the group-based active diagnosis problem and show that the reward function corresponding to
group identification is both adaptive monotone and weakly
adaptive submodular; thus we also obtain competitive performance guarantees for this problem when using a simple
greedy policy without the need for proxy set functions nor
specialized algorithms. We believe that our approach is novel
and valuable especially for its simplicity. Moreover, the
adaptive submodularity factor also offers an alternative explanation for the deterioration of the performance guarantees
that was observed in group-based active learning when proxy
set functions are introduced (cf. [4], [9], [18]).
Furthermore, we demonstrate that the problem of active
diagnosis with persistent noise or fault is equivalent to the
group-based active diagnosis problem; hence, once again, we
have provably competitive performance guarantees for the
adaptive greedy policy and do not require proxy set functions
and algorithms. In addition, our general formulation allows
for state-dependent sensor noise or fault, and also complex
faults, such as faults that give the same outcome regardless
of the system states, or faults that always give the opposite
outcome. Our experiments on aircraft electrical systems show
that the simple adaptive greedy policy performs just as well
as a brute-force policy that tries all possible actions, while
only having a polynomial-time computational complexity.
II. M OTIVATION : A IRCRAFT E LECTRICAL S YSTEM WITH
P ERSISTENT S ENSOR FAULTS
We are motivated by the discrete state estimation problem
of an aircraft electrical system via active sensing, first studied
in [10] (see Figure 1 for an example of a simple circuit and
the readers are referred to [10] for a detailed description
of the electrical circuits). As more systems become more
dependent on electric power systems, this problem is crucial
to the safety of these systems. In the above work, the sensors
are assumed to be healthy or faultless. But in reality, sensors
can be faulty, which means that they can provide incorrect
information about the unknown discrete state (i.e., operating
condition or status) of the electrical components. The faults
can be either stochastic or persistent, and in this paper, we
are mainly interested in persistent faults. One such fault is
when a faulty sensor persistently gives the opposite reading
and another is when a faulty sensor always gives a constant
reading (hence sometimes correctly and others incorrectly).
Despite persistent faults, our goal is similar to that in
[10], i.e., to design a policy that can adaptively estimate the
discrete state of the circuit by taking “actions” (i.e., opening
or closing controllable contactors) and observing the sensor
measurements. Note that we are only interested in estimating
the unknown discrete state of the system and not the true
failure mode of the sensors. Hence, if we group all possible

Fig. 1: A single-line diagram of a simple circuit with AC
components (in black) and DC components (in red).
sensor failure modes that correspond to each state, our
problem of interest is one of group-based active diagnosis,
i.e., we aim to adaptively identify or estimate which group
(i.e., state) is compatible with our sensor measurements.
However, the reward function for this problem is not adaptive
submodular, which motivates the need for the concept of
weak adaptive submodularity, discussed next.
III. W EAK A DAPTIVE S UBMODULARITY
In this section, we propose a generalization of the concept
of adaptive submodularity and show that adaptive greedy
policies achieve near-optimal performance for objective functions with such a property. These results will be useful for
group-based active diagnosis, considered in the next section.
A. Mathematical Preliminaries and Definitions
We begin by introducing notations for the adaptive
decision-making problem we consider. Given a finite set of
actions (or queries), v ∈ V, our objective is to adaptively
select actions to estimate a fixed but hidden state, x0 ∈ X .
We consider a Bayesian approach and model the state as
a random variable, X, with a given prior probability distribution P[x] on X . When we take an action v, we observe
the (sensor) measurement or outcome y ∈ Y, which we will
use to sequentially make a decision about the next action.
We represent the pairs of actions {v1 , . . . , vt } and observed
outcomes {y1 , . . . , yt } up to time t by a partial realization
ψt = {(vi , yi )}i∈{1,...,t} . Given two partial realizations ψt
and ψt0 , we call ψt a subrealization of ψt0 if ψt ⊆ ψt0 .
To evaluate “progress” in the decision-making process, we
define an objective function f : 2V ×X → R≥0 that maps the
set of actions A ⊆ 2V under state x0 to reward f (A, x0 ).
A policy π is a function from a set of partial realizations
to actions, which specifies the action to choose next after
observing ψt , i.e., vt+1 = π(ψt ), and Ṽ(π, x0 ) ⊆ 2V denotes
the set of all actions under policy π. Randomized policies
that specifies the distribution on actions are also allowed.
Next, we provide definitions specific to set functions in [6],
followed by the definition of weak adaptive submodularity.
Definition 1 (Conditional Expected Marginal Benefit). Given
an objective function f , an action v ∈ V and a partial
realization ψt , the conditional expected marginal benefit of
v conditioned on having observed ψt is defined as
∆(v|ψt ) , E[f (v1:t ∪ {v}, X) − f (v1:t , X)|ψt ],

(1)

with the expectation taken with respect to P[x|ψt ]. Similarly,
the conditional expected marginal benefit of a policy π is
∆(π|ψt ) , E[f (v1:t ∪ Ṽ(π, x0 ), X) − f (v1:t , X)|ψt ]. (2)

The following definition of adaptive monotonicity has the
interpretation that the conditional expected marginal benefit
of any action v is non-negative.
Definition 2 (Adaptive Monotonicity). A function f : 2V ×
X → R≥0 is adaptive monotone with respect to distribution
P[x] if for all v ∈ V and ψt with P[ψt ] > 0, ∆(v|ψt ) ≥ 0.
Next, we define a new property that has the interpretation
that the conditional expected marginal benefit of any fixed
action (or query) v does not increase “too much” as more
actions are performed and their measurements are observed.
Definition 3 (ζ-Weak Adaptive Submodularity). A function
f : 2V × X → R≥0 is ζ-weakly adaptive submodular with
respect to distribution P[x] if for all ψt , ψt0 such that ψt is a
subrealization of ψt0 , i.e., ψt ⊆ ψt0 , and for all v ∈ V \ v1:t0 ,
∆(v|ψt0 ) ≤ ζ∆(v|ψt ),
for some constant ζ ≥ 1 that we refer to as the adaptive
submodularity factor. Additionally, let ζ ∗ ≤ ζ be the smallest
such ζ, referred to as the best adaptive submodularity factor.
From the above definition, it is clear that for any ζ ≥ ζ 0 , if
f is ζ 0 -weakly adaptive submodular, then f is also ζ-weakly
adaptive submodular. Further, (strongly) adaptive submodular functions f (with ζ ∗ = 1) are also ζ-weakly adaptive
submodular for any ζ ≥ 1; hence, this is a generalization of
(strong) adaptive submodularity. In fact, any set function is
ζ-weakly adaptive submodular with some (possibly infinite)
ζ. Note that our definition differs from approximate adaptive
submodularity that was defined in [15] without justification.
B. Adaptive Greedy Policies
Weak adaptive submodularity resembles a diminishing
returns property for policies, which suggests that an adaptive
greedy policy can provide nice performance guarantees.
Thus, we consider an adaptive greedy policy that, at each
iteration, myopically follows the greedy heuristic of maximizing its expected gain given its current observations:
π greedy (ψt ) , vt+1 ∈ arg max ∆(v|ψt ).
v∈V

Such greedy strategies do not in general produce an optimal
solution when compared to clairvoyant algorithms, but are
oftentimes near-optimal in practice and have the advantage
of having a polynomial-time computational complexity.
C. Performance Guarantees for Active Diagnosis
We consider an important class of problems as follows:
Problem 1 (Active Diagnosis). Given a reward function f ,
find a policy π ∗ with a budget of k actions such that
π ∗ ∈ arg max E[f (Ṽ(π, X), X)]
π

subject to |Ṽ(π, x)| ≤ k, ∀x ∈ X ,

(3)

with expectation taken with respect to P[x] and Ṽ(π, x) ⊆ 2V
is the set of all actions under policy π when the state is x.
It turns out that for this class of problems, the weak adaptive submodularity property offers a very nice performance

guarantee when used in conjunction with adaptive greedy
policies, which we will prove in Appendix A.
Theorem 1. Fix any ζ ≥ 1. Let the greedy policy π`greedy be
run for ` iterations (so that it select ` actions), and πk∗ be any
policy selecting at most k actions for any realization x. Then
for adaptive monotone and ζ-weakly adaptive submodular f ,
favg (π`greedy ) > (1 − e−`/ζk )favg (πk∗ ),
where favg (π) , E[f (Ṽ(π, X), X)] is the expected reward
of the policy π with respect to the distribution P[x].
A corollary from the above theorem is that our greedy
policy that selects k actions obtains at least (1 − e−1/ζ ) of
the value of the optimal policy that selects k actions. Note
that if ζ is large, then the performance bound can be poor.
Remark 1. The adaptive submodularity factor ζ affects the
performance guarantee in Theorem 1 in the exact way as
the approximation factor of α-approximate greedy policies.
Just as approximate greedy policies suggest that greedy
policies are robust to incorrect priors P[x] by a factor α
(cf. [6, Section 4.3] for a discussion), the ζ-weak adaptive
submodularity property is “robust” to the deviation from
(strong) adaptive submodularity by a factor ζ.
IV. N EAR -O PTIMAL G ROUP -BASED ACTIVE D IAGNOSIS
A. Problem Setup
The objective of group-based active diagnosis is not to
determine the unknown object but rather the group to which
the object belongs via active sensing. For instance, in medical
diagnosis, one is more interested to diagnose the disease that
a patient has without necessarily identifying all its symptoms,
while in movie recommendation systems, it may be of more
interest to identify the genre that a user prefers as opposed
to the exact scene preferences. As also noted in [9], the
group-based diagnosis problem cannot be simply reduced to
an active diagnosis problem with groups as “meta-states”,
since the objects within a group do not generally yield the
same observations. In our motivating example, our goal is to
primarily estimate the hidden system state with no emphasis
on finding the hidden persistent sensor faults. Further, under
the hypotheses of different sensor failure modes for the same
system state, the sensor measurements would be different.
1) Mathematical formulation: In this section, we further
introduce notations that are specific to the group-based active
diagnosis problem. We will only consider non-overlapping
groups in this paper; thus, to make the connection to active
diagnosis with persistent faults clear, we will refer to groups
as (system) states x ∈ X and objects in the groups as (sensor)
modes q ∈ Q. We assume that the true state x0 ∈ X and
the true mode q0 ∈ Q are fixed but unknown. As before,
we will consider a Bayesian approach and model the state
X and mode Q as random variables with a given prior joint
probability distribution P[x, q] on X ×Q. Note that the modes
need not be the same for each state. Q can be taken as the
union of all modes and if a particular mode q does not belong
to a state x, then P[x, q] = 0.

Given the true pair of state x0 and mode q0 , y =
µ(v, x0 , q0 ) ∈ Y is the unique outcome of performing action
v. Further, we define D(y, v, q) as the set of states x ∈ X
that gives the same outcome y under the action v if q were
the true mode. We then define for each iteration t, St,q as
the set of all compatible states with the hypothesis that q
is the true mode, i.e., the set of all states that produce the
same set of outcomes {µ(v1 , x0 , q0 ), ..., µ(vt , x0 , q0 )} under
the set of actions {v1 , ..., vt }, which can also be written as
St,q = ∩i∈{1,...,t} D(µ(vi , x0 , q0 ), vi , q).

(4)

Since only intersections are taken, the order of actions vi
does not matter.
2) Problem statement: The objective of group-based active diagnosis is to eliminate as many of the states as
possible that are incompatible with observed outcomes, i.e.,
the uncertainty of X represented by P[x]. For the groupbased active diagnosis problem, this means that at any step
t, we cannot eliminate any state x that is compatible with
the hypothesis of one or more modes, i.e., x ∈ ∪q∈Q St,q .
Thus, we define a reward function f : 2V × X × Q → R≥0
as follows
X
P[x],
(5)
f (v1:t , x) = f (v1:t , x, q) = 1 −
x∈

S

q∈Q

St,q

with x = (x, q). Note that only the final term in (5) is
essential for the greedy algorithms that we propose. If P[x]
is uniformly distributed on X , then this term is proportional
to the size of ∪q∈Q St,q . The constant is added such that the
reward function is non-negative, and is equal to 0 when no
action has been taken, i.e., f (∅, x) = 0.
We also assume that we are allocated a budget on the
maximum number of actions taken, k  |2V |. To achieve
the goal, we want to design a policy π ∗ that finds the “best
expected estimate” of the state x.
Problem 2 (Group-Based Active Diagnosis). Find a policy
π ∗ that solves Problem 1 with f given in (5).
3) Active diagnosis with persistent faults (special case):
To consider this problem as a group-based active diagnosis
problem (see also [9], [18] for a similar characterization), we
create groups of objects where each group corresponds to a
state and the objects within the group are copies of the state
for each possible mode of sensor faults. For example, we
consider a system with |X | states, each denoted by x ∈ X .
If we have m sensors that can be faulty and there are p
ways a sensor fault can manifest itself, then we have (p +
1)m possible combinations of functioning and faulty sensor
modes, denoted by q ∈ Q, with cardinality |Q| = (p + 1)m .
Next, we define an object as a pair of a state and a mode,
denoted as x = (x, q) ∈ X = X × Q. In other words, for
each group/state x, all pairs of {x, q}q∈Q form the objects
corresponding to this group.
Next, to introduce the types of sensor faults we consider,
we define the function µ(v, x0 ) as the unique outcome under
action v and true state x0 when all sensors are healthy and
the function y 0 = κq (y) as the corruption of the ‘healthy’

sensor outcome y to the ‘faulty’ sensor outcome y 0 when the
failure mode is q. Hence, µ(v, x, q) = κq (µ(v, x)). Further,
we define D(y, v) with y = µ(v, x) as the set of states
x ∈ X that gives the same ‘healthy’ sensor measurement y
under the action v when x is the actual system state. Thus,
−1
D(y, v, q) = D(κ−1
q (y), v), where the inverse function κq
0
−1
0
is such that y = κq (y) implies that y = κq (y ).
Note that the fault function κq is surjective, whereas κ−1
q
is an injective partial function, as can be seen with the
types of sensor faults we consider in this paper. First, a
Type 1 fault is when a faulty sensor persistently outputs
the opposite outcome. Another type of sensor fault is when
the faulty sensor always gives a constant reading, e.g., ‘0’
or ‘1’ (Type 2 fault). For a single sensor with a Type 1
fault, y = κ−1
q (κq (y)), whereas for one with a Type 2 fault,
y ∈ κ−1
(κ
(y)) or κ−1
q
q
q (κq (y)) = ∅. To further illustrate
this, consider a simple example with three sensors: s1 , s2 , s3 ,
where only s2 is faulty, i.e., q = [1, 0, 1], and the ‘faulty’
sensor measurement is y = [1, 0, 1]. If the fault is of Type 1,
0
we have y 0 = κ−1
q (y) = [1, 1, 1] and D(y, v, q) = D(y , v),
whereas if the fault is of Type 2 (with persistent outcome
0 00
0
00
=
‘1’), κ−1
q (y) = {y , y }, with y = [1, 0, 1] and y
0
00
[1, 1, 1], and D(y, v, q) = D(y , v) ∪ D(y , v). On the other
hand, if s2 is faulty of Type 2 (with persistent outcome ‘0’)
and if y2 should always be 1 for all q, then y 0 = κ−1
q (y) is
undefined and by definition, D(y, v, q) = ∅.
B. Adaptive Greedy Policy: Group-Based Active Diagnosis
The optimal policy for Problem 2 may only be obtained by
a clairvoyant algorithm. Moreover, the complexity of planning ahead for k steps scales exponentially with k. Hence,
we resolve to find a scalable (polynomial-time) algorithm
using an adaptive greedy strategy, i.e., to select the action
at time t + 1 that maximizes the expected one-step reward
given the available information ψt , denoted by ∆(v|ψt ) and
given in Definition 1, where the expectation is taken with
respect to P[x, q|ψt ]. This probability measure P[x, q|ψt ] on
the set St,q for each q ∈ Q can be obtained via Bayes’ rule:
(
P[x,q]
∀x ∈ St,q ,
P[ψt |x, q]P[x, q]
= P[ψt ]
(6)
P[x, q|ψt ] =
P[ψt ]
0
otherwise.
Note that we substituted P[ψt |x, q] = 1 if x ∈ St,q because
the measurement process is deterministic,
P
P and P[ψt |x, q] = 0
otherwise. Moreover, since
q∈Q
x∈St,q P[x, q|ψt ] = 1,
the normalization term P[ψ] can be computed as
X X
P[ψt ] =
P[x, q].
(7)
q∈Q x∈St,q

Thus, at each iteration or step t, the policy consists of
choosing the next best action vt+1 that maximizes the gain
in uncertainty reduction as defined in Definition 1, which
can be rewritten for the reward function in (5) as
1 X X
vt+1 ∈ arg max
P[x, q]
v∈V P[ψt ]
q∈Q x∈St,q
X
X
(
P[x̃] −
P[x̃] ),
x̃∈∪q̃∈Q St,q̃

x̃∈∪q̃∈Q St,q̃ ∩D(µ(v,x,q),v,q̃)

where P(ψt ) =

X X

P[x, q]. Since the first term does

q∈Q x∈St,q

not depend on the choice of action v, the above expression
can be equivalently written as
X
X X
vt+1 ∈ arg min
P[x, q]
P[x̃]. (8)
v∈V

S
x̃∈ q̃∈Q (St,q̃
∩D(µ(v,x,q),v,q̃))

q∈Q x∈St,q

In addition, a less computationally expensive algorithm
can be obtained by further transforming (8) to
X
X
X X
vt+1 ∈ arg min
P[x̃]
P[x, q] (9)
v∈V

y∈Y x̃∈

S

q̃∈Q (St,q̃
∩D(y,v,q̃))

q∈Q x∈St,q ∩
D(y,v,q)

C. Near-Optimality Performance Guarantees
To derive performance guarantees for the group-based active diagnosis problem with the reward function f (v1:t , x, q)
in (5), we first show that f satisfies the following (which
will be proven in Appendix B).
Proposition 1 (Adaptive Monotonicity). The reward function
f (v1:t , x, q) in (5) is adaptive monotone.
Proposition 2 (ζ-Weak Adaptive Submodularity). The reward function f (v1:t , x, q) in (5) is ζ-weakly adaptive submodular with
|Q|
,
(10)
1≤ζ≤ζ≤
min{x∈X ,q∈Q:P[x,q]>0} P[x, q]

ζ,

max

v1:k ∈V k , v∈V,
y∈Y, t=1,...,k

x∈

P

q∈Q

P
ζ,

max

v1:k ∈V k , v∈V,
y∈Y, t=1,...,k

S

Pq∈Q

x∈St,q ∩D(y,v,q)

q∈Q

P

q∈Q

St,q ∩D(y,v,q)

P[x]
P[x, q]

,

P

x∈St,q ∩D(y,v,q) P[x, q]

2:
3:
4:
5:
6:
7:
8:
9:

Initialize ζ = 0 and S0,q = X for all q ∈ Q
for each action sequence v1:k ∈ V k do
for t ∈ {1, . . . , k} do
Perform vt and measure yt = µ(vt , x0 , q0 )
St,q = St−1,q ∩ D(yt , vt , q) for all q ∈ Q
for each action v ∈ V do
for each output y ∈ Y do
S t,q =SSt,q ∩ D(y, v, q) for all q ∈ Q
S t = q∈Q SP
t,q
ζt,v,y =

10:

12:

P

q∈Q

x∈S t
P

P[x]
P[x,q]

x∈S t,q

ζ ← max{ζ, ζt,v,y }
return ζ

the adaptive greedy policy πkgreedy guarantees that
favg (πkgreedy ) > (1 − e−1/ζ )favg (πk∗ )
for the group-based active diagnosis problem with the reward
function in (5), where favg (πk∗ ) is what can be achieved in
k steps by any other policy, including the optimal policy and
ζ is given in (10).
Hence, in the absence of informative priors on the sensor
faults (i.e., when ζ = |Q|), our adaptive greedy policy that
selects k actions obtains at least (1 − e−1/|Q| ) of the value
of the optimal strategy that selects k actions. To our best
knowledge, this result is novel. Group identification for the
complementary problem of adaptive stochastic minimum cost
cover, a.k.a. Bayesian active learning has been considered in
[4], [9], [18], but not the group-based active diagnosis problem we consider in this paper. Interestingly, the performance
bounds given in [9], [18] have an additional factor of 2,
which is equal to ζ = |Q| = 2 since they had exactly 2
modes for each persistent sensor fault, while [4] also has a
factor that resembles ζ.
V. E XAMPLES

P

x∈St,q ∩D(y,v,q) P[x]

1:

11:

by using the fact that the sets {D(y, v, q) | y ∈ Y} form
a partition of X as will be described in more detail in the
proof of Lemma 2 in Appendix B.

where ζ and ζ are defined as
P

Algorithm 1 Computation of ζ

.

Both ζ and ζ can be computed algorithmically, but since
we are interested in a smaller ζ, we only provide an algorithm
for computing ζ in Algorithm 1. ζ is of interest because
it can be easily derived analytically for some special cases.
Specifically, for a group-based active diagnosis problem with
uniform P[x, q] for each x ∈ X , which is the case for
active sensing with no informative priors on the sensor
faults, we have P[x] = |Q|P[x, q]. In this case, ζ = |Q|.
Note that these factors are only required for finding the
performance guarantee, and are not needed for the adaptive
greedy strategy we propose.
Since the group-based active diagnosis problem (Problem
2) is equivalent to the active diagnosis problem with an
adaptive monotone and weakly adaptive submodular reward
function, by Propositions 1 and 2, as well as Theorem 1, we
have the following performance guarantee.
Theorem 2. For any true state x ∈ X and true mode q ∈ Q,

We tested the adaptive greedy policy on two electric
power system circuits—small and large circuits. For these
experiments, the state x is uniformly distributed on X , and
for any sensor measurement that is prone to faults, qi for
all i = 1, . . . , |Q|, the conditional probabilities that faults of
Type 1 and Type 2 (with outcome ‘stuck’ at ‘1’) persistently
occur are P[qi1 |x] = 0.2 and P[qi2 |x] = 0.4, respectively.
The conditionalQprobability for each state and mode pair is
|Q|
then P[q|x] = i=1 P[qi |x]. For simplicity, we only allow
two states for the system components, i.e., they are either
healthy or faulty. Correspondingly, the sensor readings can
only take two values, i.e., proper voltage or improper voltage.
We do not assume an initial action v0 , so we initialize our
experiments with S0,q = X for each q.
For many practical cases, it is not possible to reduce the
size of the compatible states to one because the number and
positioning of sensors are often limited, and more so when
the sensors can be faulty. Thus, we compare the performance
of our adaptive greedy policy with the results of a brute force
policy that exhaustively takes every action v ∈ V (thus, violating the given budget on the number of actions). The brute

40

30

30

Count

Count

40

20

10

number (on the abscissa). Since the adaptive greedy strategy
performs equally well as the brute force method, we omit the
plots for the brute force policy that lie exactly on top of the
plots for the adaptive greedy policy. Moreover, comparing
Figures 2(a) and 2(b), we observe that the maximal number
of indistinguishable states is larger when more sensors are
faulty, as expected. Furthermore, for most system states x0 ,
the best reward is already obtained by our adaptive greedy
policy within 2 actions.

20

10

0

0

0.04 0.042 0.044 0.046 0.048

0.2

Execution time (s)

0.22

0.24

Execution time (s)

(a) S2 is fault-prone of Type 1 and (b) S1, S2 are fault-prone of Type
S1, S3 are healthy.
1 and S3 of Type 2.

Fraction of true states x0

Fig. 2: Histogram of execution times (averaged over 6
actions) of the adaptive greedy policy for all true states x0 .
1

0.5

S1,S3: Healthy, S2: Type 1
S1,S2: Type 1, S3: Type 2 (always 1)

0
0

2

4

6

8

10

12

14

16

Maximal number of indistinguishable states

Fig. 3: Fraction of true states x0 with its corresponding
maximal number indistinguishable states after 6 actions.
force policy represents the best achievable outcome, which
we use as a benchmark. Both policies are run in Python on an
Intel R CoreT M i5-4300U 64-bit CPU@1.90GHz 2.50GHz
with 8.00GB RAM, and the experiments are performed for
all possible system states x0 ∈ X and sensor modes q0 ∈ Q.
A. Tests on a small-size circuit
We first tested the proposed adaptive greedy policy on a
small circuit with 13 components, as shown in Figure 1. By
using four controllable contactors {C1, C3, C4, C6} (thus,
|V| = 24 = 16 actions) and observing the measurements
of sensors {S1, S2, S3}, which may be faulty, the objective is to estimate the unknown states of the components
{G1, G2, R1, R2, C2, C5}.
Simulation result: The adaptive greedy policy that takes 6
actions performs equally well as the brute force policy that
takes all 16 actions, i.e., the values of the objective function
f are equal for all possible states x0 and failure modes q0 .
1) Average execution time: We recorded the average execution times to find the next best action, and the results
are shown in Figure 2 for two representative examples for
different true sensor modes q. It takes about 25 milliseconds
to compute the next best action when all the sensors are
healthy, and we observed that the average execution time
increases linearly in the number of modes |Q| = 2m , i.e.,
exponentially with the number of fault-prone sensors m.
2) Maximal number of indistinguishable states: Figure 3
compares the maximal numbers of indistinguishable states
(corresponding to the minimal values of the reward function
f ) after 6 actions for all x0 and two illustrative examples
of q0 . The ordinate shows the fraction of system states x0
6
(out of 2S
= 64) that obtains the number of indistinguishable
states, | q∈Q S6,q |, that is less than or equal to the maximal

B. Tests on a larger circuit
We also tested our greedy policy on a larger circuit with
more sensors and components (cf. [10, Section V-B] for
details), which is more representative of aircraft power distribution systems. When all sensors are healthy, the average
execution time for obtaining the next best action is about
0.22 seconds. As before, the average execution time increases
linearly with the number of sensor modes |Q|. Similarly, the
performance of our adaptive greedy policy with 6 actions is
as good as the brute force policy with 32 actions.
VI. C ONCLUSIONS AND F UTURE D IRECTIONS
In this paper, we considered stochastic state estimation
problems with partial observations via active sensing. First,
we introduced a property for set functions, called weak adaptive submodularity, that generalizes the concept of adaptive
submodularity. Then, for the active diagnosis problem, we
showed that adaptive greedy policies are near-optimal when
the reward function is adaptive monotone and weakly adaptive submodular. Next, we considered the group-based active
diagnosis problem, for which a special case is the active
diagnosis problem with persistent sensor noise or faults,
and proved that the group-based reward function is weakly
adaptive submodular; hence the group-based active diagnosis
problem can be solved using a simple adaptive greedy policy
with guaranteed competitive performance when compared to
the optimal adaptive policy. Our state estimation experiments
with aircraft electrical systems plagued by persistent sensor
faults demonstrated that the adaptive greedy policy performs
just as well as a brute-force policy.
Future work will consider group-based active learning for
decision-making using weak adaptive submodularity with
the hope of removing the need for proxy set functions
and specialized algorithms, while preserving the provable
competitiveness of adaptive greedy policies. We will also
consider the general active diagnosis problem where the sensor noise and faults can be persistent and/or non-persistent.
R EFERENCES
[1] L.P. Kaelbling, M.L. Littman, and A.R. Cassandra. Planning and acting
in partially observable stochastic domains. Artificial intelligence,
101(1):99–134, 1998.
[2] R.S. Sutton and A.G. Barto. Reinforcement learning: An introduction,
volume 1. MIT Press Cambridge, 1998.
[3] A. Singh, A. Krause, C. Guestrin, W.J. Kaiser, and M.A. Batalin.
Efficient planning of informative paths for multiple robots. In IJCAI,
volume 7, pages 2204–2211, 2007.
[4] S. Javdani, Y. Chen, A. Karbasi, A. Krause, D. Bagnell, and S.S.
Srinivasa. Near optimal bayesian active learning for decision making.
In AISTATS, pages 430–438, 2014.

[5] N.I. Santoso, C. Darken, G. Povh, and J. Erdmann. Nuclear plant fault
diagnosis using probabilistic reasoning. In Power Engineering Society
Summer Meeting, 1999. IEEE, volume 2, pages 714–719. IEEE, 1999.
[6] D. Golovin and A. Krause. Adaptive submodularity: Theory and
applications in active learning and stochastic optimization. Journal
of Artificial Intelligence Research, 42:427–486, 2011.
[7] R. Debouk, S. Lafortune, and D. Teneketzis. On an optimization problem in sensor selection. Discrete Event Dynamic Systems, 12(4):417–
445, 2002.
[8] T.S. Jaakkola and M.I. Jordan. Variational methods and the qmrdt database. NATO ASI Series F Computer and Systems Sciences,
168:185–214, 1998.
[9] G. Bellala, S.K. Bhavnani, and C. Scott. Group-based active query
selection for rapid diagnosis in time-critical situations. IEEE Transactions on Information Theory, 58(1):459–478, 2012.
[10] Q. Maillet, H. Xu, N. Ozay, and R.M. Murray. Dynamic state
estimation in distributed aircraft electric control systems via adaptive
submodularity. In 52nd IEEE Conference on Decision and Control,
pages 5497–5503. IEEE, 2013.
[11] S.R. Kosaraju, T.M. Przytycka, and R. Borgstrom. On an optimal split
tree problem. In Workshop on Algorithms and Data Structures, pages
157–168. Springer, 1999.
[12] T.H. Summers and J. Lygeros. Optimal sensor and actuator placement in complex dynamical networks. IFAC Proceedings Volumes,
47(3):3784–3789, 2014.
[13] V. Tzoumas, A. Jadbabaie, and G.J. Pappas. Sensor placement for
optimal Kalman filtering: Fundamental limits, submodularity, and
algorithms. In 2016 American Control Conference, pages 191–196,
July 2016.
[14] A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms
for subset selection, sparse approximation and dictionary selection.
arXiv preprint arXiv:1102.3975, 2011.
[15] M.J. Kusner. Approximately adaptive submodular maximization. In
NIPS workshop on Discrete Optimization and Machine Learning,
2014.
[16] G. Bellala, J. Stanley, S.K. Bhavnani, and C. Scott. A rank-based
approach to active diagnosis. IEEE transactions on pattern analysis
and machine intelligence, 35(9):2078–2090, 2013.
[17] A.X. Zheng, I. Rish, and A. Beygelzimer. Efficient test selection in active diagnosis via entropy approximation. arXiv preprint
arXiv:1207.1418, 2012.
[18] D. Golovin, A. Krause, and D. Ray. Near-optimal bayesian active
learning with noisy observations. In Advances in Neural Information
Processing Systems, pages 766–774, 2010.

A PPENDIX
A. Proof for Weak Adaptive Submodularity (Theorem 1)
The following lemma will be used to prove Theorem 1.
Lemma 1. Suppose we have observed partial realizations
ψt after selecting v1:t and let π ∗ be any policy such that
|Ṽ(π ∗ , x0 )| ≤ k for all x0 . Then for adaptive monotone and
ζ-weakly adaptive submodular f : 2V × X → R≥0 , we have
X
∆(π ∗ |ψt ) ≤ ζ max
∆(v|ψt ).
A⊆V,|A|≤k

v∈A

Proof. This result can be obtained by a slight adaptation
of the proof for Lemma A.9 in [6], where we replaced
∆(v|ψt0 ) ≤ ∆(v|ψt ) with ∆(v|ψt0 ) ≤ ζ∆(v|ψt ) when ψt0
is a subrealization of ψt , and with uniform action cost. 
Proof of Theorem 1. The proof goes along the lines of the
analysis in Theorem A.10 in [6] but for the generalized case
when ζ ≥ 1 and with uniform action cost. First, we consider
a corollary of Lemma 1 for any i, which allows us to bound
E[∆(πk∗ |ψi )] ≤ ζk max(∆(v|ψi )),
v∈V

where the expectation is taken over the internal randomness
of πk∗ , if there is any, and we know that the budget of actions

for all x0 is such that E[|Ṽ(π ∗ , x0 )|] ≤ k. Then,
favg (πi+1 ) − favg (πi ) = max(∆(v|ψi ))
v∈V

≥ E[∆(πk∗ |ψi )]/ζk
= (favg (πi @πk∗ ) − favg (πi ))/ζk,
where πi @πk∗ is a policy obtained by running πi to completion, and then running policy πk∗ as if from a fresh start
and ignoring the gathered information ψi . The first equality
holds because πi (superscript omitted for brevity) is a greedy
policy, while the final equality holds by taking an appropriate
convex combination over the random partial realizations Ψi .
Moreover, due to the adaptive monotonicity of f , by [6,
Lemma A.8], we have favg (πk∗ ) ≤ favg (πi @πk∗ ). Putting
them together, we have for all i = 0, . . . , `,
favg (πk∗ ) − favg (πi ) ≤ ζk(favg (πi+1 ) − favg (πi )).
Then, defining ∆i , favg (πk∗ )−favg (πi ), we obtain ∆i+1 ≤
1 `
1
)∆i and thus, ∆` ≤ (1− ζk
) ∆0 < e−`/ζk ∆0 , where
(1− ζk
−x
we used the fact that 1 − x < e for all x to obtain the last
inequality. Finally, by the definition of ∆i ,
favg (πk∗ ) − favg (π` ) < e−`/ζk (favg (πk∗ ) − favg (π0 ))
≤ e−`/ζk favg (πk∗ ),
since favg (π0 ) ≥ 0 by assumption. Hence, the result in the
theorem follows directly from the above.

B. Proofs for Near-Optimal Group-Based Active Diagnosis
1) Conditional Expected Marginal Benefit ∆(v|ψt ): Our
proofs for Propositions 1 and 2 rely heavily on the particular
form that ∆(v|ψt ) takes on, given in the following:
Lemma 2 (Conditional Expected Marginal Benefit). The
conditional expected marginal benefit of action v for the
reward function f (v1:t , x, q) in (5) can be expressed as
P|Y|
|Y|
X
ζi τi2
∆(v|ψt ) =
ζi τi − Pi=1
,
(11)
|Y|
i=1
i=1 τi
for some τi ≥ 0 and ζi ≥ 1 that are both explicitly dependent
on the partial realization ψt for all 1 ≤ i ≤ |Y|.
Proof. By definition,
∆(v|ψt ) = E[f (v1:t ∪ {v}, X, Q) − f (v1:t , X, Q)|ψt ]
= E[f˜(v1:t ∪ {v}, X, Q) − f˜(v1:t , X, Q)|ψt ]
with the expectation taken
Pwith respect to P[x, q|ψt ] and
where f˜(v1:t , x, q) , − x∈ S St,q P[x]. The individual
q∈Q

terms can be computed as:
E[f˜(v1:t ∪ {v}, X, Q)|ψt ]
P P
=
P[x, q|ψt ]f˜(v1:t ∪ {v}, x, q)
q∈Q x∈St,q
P P
P
=−
P[x, q|ψt ] S
q∈Q x∈St,q

x̃∈

(12)
P[x̃],

(St,q̃ ∩D(µ(v,x,q),v,q̃))

q̃∈Q

E[f˜(v1:t , X, Q)|ψt ] =
=

P

P

P[x, q|ψt ]f˜(v1:t , x, q)

q∈Q x∈St,q
P
− x̃∈ S St,q̃
q̃∈Q

P[x̃],

(13)

where the final equality holds because f˜(v1:t , x, q) is independent of q and x.
To proceed, since the probability measure on (X , Q) is
non-uniform and can take values in some set {p1 , . . . , pN },
we define subsets of (X , Q) where P[x, q] is constant with
Fn,q , {(x, q) ∈ X × Q | P[x, q] = pn }. Furthermore, since
for every x ∈ X , there is a corresponding y = µ(v, x, q) for
any given v ∈ V and q ∈ Q, the sets {D(y, v, q) | y ∈ Y}
also form a partition of X . Finally, we define a partition
of St,q for each q ∈ Q using the sets {St,q ∩ D(y, v, q) ∩
Fn,q | y ∈ Y, n ∈ 1 : N } and denote with a shorthand
αn,y,q , St,q ∩D(y, v, q)∩Fn,q . Thus, for all (x, q) ∈ αn,y,q ,
µ(v, x, q) = y and P[x, q] = pn .
Moreover, for all x ∈ Fn,q , the conditional probabilities
in (6) can be rewritten as
pn
pn
,
(14)
,P
P[x, q|ψt ] =
P[ψt ]
y∈Y τy
where we obtain the expression for P[ψt ] from (7) as
P P
P[ψt ] =
P[x, q]
q∈Q x∈St,q
P P P P
=
x∈St,q ∩D(y,v,q)∩Fn,q pn
n∈1:N
y∈Y q∈Q
P P
P
P
=
pn |αn,y,q | =
τy ,
y∈Y n∈1:N q∈Q

and defined τy ,

X X

y∈Y

pn |αn,y,q | ≥ 0.

Furthermore, the following inequality holds:
X
X X
X X
P[x] =
P[x, q] ≥
P[x, q], (15)
S

q∈Q x∈

St,q̃

q̃∈Q

S

q∈Q x∈St,q

St,q̃

since ζi ≥ 1 and τi ≥ 0 for all i = 1, . . . , |Y|. Hence,
adaptive monotonicity holds by Definition 2.

To prove Proposition 2, i.e., that the reward function f
in (5) is weakly adaptive submodular, we first state the
following lemma from [10] that will be useful.
Lemma 3. [10, Lemma 1] The function b : R|Y| → R
P|Y| 2
|Y|
X
τi
(19)
τi − Pi=1
b(τ1 , τ2 , . . . , τ|Y| ) =
|Y|
i=1
i=1 τi

Proof of Proposition 2. First, taking the partial derivative of
(11) with respect to ζi , we obtain
P
τi j=1,...,|Y|,j6=i τj
∂∆(v|ψt )
τi2
= τi − P|Y|
=
≥ 0.
P|Y|
∂ζi
i=1 τi
i=1 τi
From the above, we can conclude that
b(ψt ) ≤ b(ψt ) min ζi ≤ ∆(v|ψt ) ≤ b(ψt ) max ζi ≤ ζb(ψt ),
i

q̃∈Q

since on the right hand side, q is a particular choice of q̃ ∈ Q.
Using the above-defined partitions, we can equivalently write
P
P
P
P[x] =
P[x]
S
S
n∈1:N x∈

St,q̃ ∩D(y,v,q̃)

x∈

Proof of Proposition 1. From (11) in Lemma 2,
P|Y|
P|Y|
P|Y|
( i=1 τi )( i=1 ζi τi ) − i=1 ζi τi2
∆(v|ψt ) =
P|Y|
τ
P|Y|
P i=1 i
(ζ
τ
τ
)
i=1 i i
j6=i j
≥ 0,
=
P|Y|
i=1 τi

is increasing on the positive orthant, i.e., b(τ1 , τ2 , . . . , τ|Y| )
≥ b(s1 , s2 , . . . , s|Y| ) if τi ≥ si ≥ 0 for all 1 ≤ i ≤ |Y|.

n∈1:N q∈Q

x∈

2) Performance Guarantees: Armed with Lemma 2,
Proposition 1 can be shown to directly hold.

q̃∈Q

St,q̃ ∩D(y,v,q̃)∩Fn,q̃

q̃∈Q

= ζ(ψt , y)

P

P P

n∈1:N q∈Q

x∈αn,y,q

pn

= ζ(ψt , y)τy ,
where we defined
P

S

x∈

ζ(ψt , y) , P

St,q̃ ∩D(y,v,q̃)

P[x]

q̃∈Q

q∈Q

P

x∈St,q ∩D(y,v,q)

P[x, q]

(16)

and from (15), we have ζ(ψt , y) ≥ 1. This simplifies (12) to
E[f˜(vP
{v}, X, Q)|ψt ]
1:t ∪ P
=−
P[x, q|ψt ]ζ(ψt , µ(v, x, q))τµ(v,x,q)
q∈Q x∈St,q
P
P P P
1
(17)
P[x, q]ζ(ψt , y)τy
= − P[ψ
t]
=−

P

y∈Y n∈1:N q∈Q x∈αn,y,q
ζ(ψt ,y)τy2
.
y∈Y τy

y∈Y
P

Similarly, (13) simplifies to
P
E[f˜(v1:t , X, Q)|ψt ] = −
y∈Y x̃∈

P
S

St,q̃ ∩D(y,v,q̃)

q̃∈Q

=−

P[x̃]
(18)

i

(20)
where we used b(ψt ) as a shorthand for b(τ1 , τ2 , . . . , τ|Y| )
defined in (19) since ψt is related to τi ’s via (11), and ζ is
given in (10), which is conservatively chosen to be larger
than maxi ζi across all possible realizations and sequence of
actions, while by Lemma 2, we have mini ζi ≥ 1 .
Moreover, the expression for ∆(v|ψt0 ) is similar for the
partial realization ψt0 but with different τi0 and ζi0 . For ψt
as a subrealization of ψt0 , i.e., ψt ⊆ ψt0 , by construction,
St0 ,q ⊆ St,q for all q ∈ Q and by definition of τi and Lemma
3, we know that τi0 ≤ τi for all i and b(ψt0 ) ≤ b(ψt ).
Note that the following inequality from (20)
∆(v|ψt0 ) ≤ ζb(ψt0 )
also holds for ψt0 since we have chosen ζ to be the maximum
across all t. Thus, from the above and from (20), we find
1
∆(v|ψt ) ≥ b(ψt ) ≥ b(ψt0 ) ≥ ∆(v|ψt0 ),
ζ
from which ζ-weak adaptive submodularity holds by Definition 3. Further, we can find the upper bounds on ζ since
P
P
P
P[x] ≤
P[x]
S
q∈Q x∈St,q ∩D(y,v,q)
x∈ q∈Q St,q ∩D(y,v,q)
P P
≤
P[x] = |Q|
q∈Q x∈X

P

y∈Y ζ(ψt , y)τy .

Finally, from (17) and (18), we obtain ∆(v|ψt ) of the form
(11) with ζy = ζ(ψt , y) ≥ 1 and τy ≥ 0 for all y ∈ Y.


and

P

P

P[x, q] ≥

q∈Q x∈St,q ∩D(y,v,q)

while ζ ≥ 1 by (16).

min

{x∈X ,q∈Q:P[x,q]>0}

P[x, q],


