An Anytime Algorithm for Decision Making under Uncertainty
In Proc. 14th Conference
on Uncertainty in Artificial Intelligence (UAI-98),
Madison, Wisconsin, USA, July 1998, pages 246-255.
We present an anytime algorithm which computes policies for decision
problems represented as multi-stage influence diagrams. Our algorithm
constructs policies incrementally, starting from a policy which makes
no use of the available information. The incremental process
constructs policies which includes more of the information available to
the decision maker at each step. While the process converges to the
optimal policy, our approach is designed for situations in which
computing the optimal policy is infeasible. We provide examples of the
process on several large decision problems, showing that, for these
examples, the process constructs valuable (but sub-optimal) policies
before the optimal policy would be available by traditional methods.
You can get the postscript or
get the pdf.
Last updated 8 May 1998 - David Poole