Partially Observable Markov Decision Process - Approximate POMDP Solutions

Approximate POMDP Solutions

In practice, POMDPs are often computationally intractable to solve exactly, so computer scientists have developed methods that approximate solutions for POMDPs.

Grid-based algorithms comprise one approximate solution technique. In this approach, the value function is computed for a set of points in the belief space, and interpolation is used to determine the optimal action to take for other belief states that are encountered which are not in the set of grid points. More recent work makes use of sampling techniques, generalization techniques and exploitation of problem structure, and has extended POMDP solving into large domains with millions of states For example, point-based methods sample random reachable belief points to constrain the planning to relevant areas in the belief space. Dimensionality reduction using PCA has also been explored.