In many fields in computational sustainability, applications of POMDPs are inhibited by the complexity of the optimal solution. One way of delivering simple solutions is to represent the policy with a small number of α-vectors. We would like to find the best possible policy that can be expressed using a fixed number N of α-vectors. We call this the N-POMDP problem. The existing solver α-min approximately solves finite-horizon POMDPs with a controllable number of α-vectors. However α-min is a greedy algorithm without performance guarantees, and it is rather slow. This paper proposes three new algorithms, based on a general approach that we call α-min-2. These three algorithms are able to approximately solve N-POMDPs. α-min-2-fast (heuristic) and α-min-2-p (with performance guarantees) are designed to complement an existing POMDP solver, while α-min-2-solve (heuristic) is a solver itself. Complexity results are provided for each of the algorithms, and they are tested on well-known benchmarks. These new algorithms will help users to interpret solutions to POMDP problems in computational sustainability.
展开▼
