For convenience, we view functions over the state space
vectors of size 
.
We use lower case Greek letters 
and 
to refer to vectors and script
letters 
and 
to refer to sets of vectors.
In contrast, the upper case letters V and U always refer to
value functions, that is
functions over the belief space 
.
Note that a belief state is a function over the state space and
hence can be viewed as a vector.
A set of vectors induces
a value function as follows:
where 
is the inner product of and b, that is
.
For convenience, we shall abuse notation
and use to denote both a set of vectors and the value function
induced by the set. Under this convention,
the quantity f(b) can be written as 
.
A vector in a set is extraneous if its removal does not affect the function that the set induces. It is useful otherwise. A set of vectors is parsimonious if it contains no extraneous vectors.
Given a set and a vector in , define the
open witness region
and closed witness region
of w.r.t to be regions of the
belief space respectively given by
In the literature,
a belief state in the open witness region
is usually called a witness point for
since it testifies to the fact that is useful.
In this paper, we shall call a belief state in
the closed witness region
a witness point for .
Figure 1: Illustration of Technical Concepts.
Figure 1 diagrammatically illustrates
the aforementioned concepts. The line at the bottom
depicts the belief space of a POMDP with two states.
The point at the left end represents the probability
distribution that concentrates all its masses on
one of the states, while the point at the right end represents
the one that concentrates all its masses on the other
state. There are four vectors 
, 
,
, and 
.
The four slanting lines represent the linear
functions 
(i=1, 2, 3, 4)
of b. The value function induced
by the four vectors is represented by the three bold line
segments at the top. Vector is extraneous
as its removal does not affect the induced function. All the other
vectors are useful. The first segment of the line at the bottom is
the witness region of , the second segment is that
of , and the last segment is that of
.