The latest approach, Zhang and Liu (1996), called incremental pruning, combines elements of Monahan's enumeration and the witness algorithms. Like witness, it considers constructing sets of vectors for each action individually and then focusing on each one observation at a time.
The basic idea is to eliminate doing all this region business. Since the main problem is in finding all the different combinations of future strategies, we focus on this aspect of Zhang's algorithm. Adding the immediate rewards is an easy step.
For a given action, we first construct all of S(a,z) sets (one for each observation). In Monahan's algorithm we would then try all ways of combining choices from each of these. Zhang's algorithm does this incrementally observation by observation. For example: