Abstract
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 un­certain state of the world. The scheme which is based on the mini­bucket 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.