Signal Processing for Cognitive Radios

7.5.4.3 Sondik’s One-Pass Algorithm

As mentioned earlier, the modified exhaustive search with pruning approach can be seriously wasteful: It first computes the redundant set Λ_m in (7.107) that may contain many dominated vectors that will be removed by the dominance test in the second step of the algorithm. An alternative approach for efficiently computing optimal POMDP solutions thus is to avoid computing the set Λ_m all together and try to directly obtain the parsimonious set from However, so far, there is no algorithm that in general achieves this exactly. Many of the algorithms that follow this alternative approach construct an intermediate set that does not explicitly seem to be constructing Λ_m. Still, usually, this intermediate set can be bigger than the desired . Hence, again, a pruning step is still included to remove the dominated vectors from the intermediate set so as to construct . Sondik’s one-pass algorithm is one such algorithm [70, 71, 75].

We will need the following new notation:

(7.108)

Comparing with (7.98)) and (7.104), it is clear that is the set of β-vectors ...