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 .