An Anytime Approximation for Optimizing Policies Under UncertaintyRina Dechter (firstname.lastname@example.org)
The paper presents a scheme for approximation for the task of maximizing the expected utility over a set of policies, that is, a set of possible ways of reacting to observations about an uncertain state of the world. The scheme which is based on the minibucket idea for approximating variable elimination algorithms, is parameterized, allowing a flexible control between efficiency and accuracy. Furthermore, since the scheme outputs a bound on its accuracy, it allows an anytime scheme that can terminate once a desired level of accuracy is achieved. The presented scheme should be viewed as a guiding framework for approximation that can be improved in a variety of ways.