Here is the complete description of point-based DP update. It first backs up on the witness points of the input vectors. Then, it solves linear programs to identify more belief points and backs up on them so that its output dominates its input and hence is uniformly improvable.
3. return .
In terms of computational complexity, point-based DP update performs exactly backups in the first step and no more than backups in the second step. It solves linear programs only in the second step. The number of linear programs solved is upper bounded by and is usually much smaller than the bound. The numbers of constraints in the linear programs are upper bounded by .
There are several algorithms for standard DP update. Among them, the incremental pruning algorithm (Zhang and Liu 1997) has been shown to be the most efficient both theoretically and empirically (Cassandra et al. 1997). Empirical results (Section 6) reveal that point-based DP update is much less expensive than incremental pruning on a number of test problems. It should be noted, however, that we have not proved this is always the case.