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
.

Thu Feb 15 14:47:09 HKT 2001