Let be a set of vectors and b be a belief state. The backup operator constructs a new vector in three steps:
It has been shown (Smallwood and Sondik 1973, Littman 1996) that is a member of -- the set of vectors obtained by performing DP update on . Moreover, b is a witness point for .
The above fact is the corner stone of several DP update algorithms. The one-pass algorithm (Sondik 1971), the linear-support algorithm (Cheng 1988), and the relaxed-region algorithm (Cheng 1988) operate in the following way: They first systematically search for witness points of vectors in and then obtain the vectors using the backup operator. The witness algorithm (Kaelbling et al. 1998) employs a similar idea.