Fast Elimination Method for Pruning in POMDPs

This paper aims to speed up the pruning procedure that is encountered in the exact value iteration in POMDPs. The value function in POMDPs can be represented by a finite set of vectors over the state space. In each step of the exact value iteration algorithm, the number of possible vectors increases linearly with the cardinality of the action set and exponentially with the cardinality of the observation set. This set of vectors should be pruned to a minimal subset retaining the same value function over the state space. Therefore, pruning procedure in general is the bottleneck of finding the optimal policy for POMDPs. This paper analyses two different linear programming methods, the classical Lark's algorithm and the recently proposed Skyline algorithm for detecting these useless vectors. We claim that using the information about the support region of the vectors that have already been processed, both algorithms can be drastically improved. We present comparative experiments on both randomly generated problems and POMDP benchmarks