Flexible Policy Construction by Information Refinement
This work addresses decision-making under uncertainty for AI and operations research, but it appears incremental as it builds on existing dynamic programming techniques with a focus on flexibility.
The paper tackles the problem of constructing flexible decision policies for influence diagrams by incrementally building tree structures for each decision node, which converge to the optimal decision function with asymptotic performance only a constant factor worse than dynamic programming in terms of Bayesian network queries.
We report on work towards flexible algorithms for solving decision problems represented as influence diagrams. An algorithm is given to construct a tree structure for each decision node in an influence diagram. Each tree represents a decision function and is constructed incrementally. The improvements to the tree converge to the optimal decision function (neglecting computational costs) and the asymptotic behaviour is only a constant factor worse than dynamic programming techniques, counting the number of Bayesian network queries. Empirical results show how expected utility increases with the size of the tree and the number of Bayesian net calculations.