Value-Function Approximations for Partially Observable Markov Decision Processes

TLDR

POMDPs model decision problems with partially observable states, but exact solutions are computationally prohibitive, limiting their use to simple problems. The authors aim to develop and evaluate efficient approximation methods for POMDPs, surveying existing techniques and proposing new refinements. They focus on heuristic approximation methods that trade accuracy for speed, analyze various techniques, provide new insights into their differences, and introduce novel refinements. Experiments on an agent navigation problem confirm the theoretical results, demonstrating the effectiveness of the proposed approximations.

Abstract

Partially observable Markov decision processes (POMDPs) provide an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which states of the system are observable only indirectly, via a set of imperfect or noisy observations. The modeling advantage of POMDPs, however, comes at a price -- exact methods for solving them are computationally very expensive and thus applicable in practice only to very simple problems. We focus on efficient approximation (heuristic) methods that attempt to alleviate the computational problem and trade off accuracy for speed. We have two objectives here. First, we survey various approximation methods, analyze their properties and relations and provide some new insights into their differences. Second, we present a number of new approximation methods and novel refinements of existing techniques. The theoretical results are supported by experiments on a problem from the agent navigation domain.