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.
POINT-BASED-DPU:
1.
2.
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.