A New Perspective on Algorithms for Optimizing Policies under Uncertainty
A New Perspective on Algorithms for Optimizing Policies under Uncertainty
复制标题
不确定性下优化政策算法的新视角
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Dechter
中科院分区：
文献类型：
--
作者：
R. Dechter
本文重新审视了一组政策的预期效用最大化的算法，也就是说，一组可能的方式来对世界的不确定状态的观察作出反应。使用桶消除框架，我们的特点，这个优化任务的复杂性，基于图形的参数，并设计一个改进的现有算法的变体。的改进，以产生一个显着的增益的复杂性时，概率子图（的影响图）是稀疏的，无论其实用程序子图引入的复杂性。
The paper takes a fresh look at algorithms for maximizing 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. Using the bucket-elimination framework, we characterize the complexity of this optimization task by graph-based parameters, and devise an improved variant of existing algorithms. The improvement is shown to yield a dramatic gain in complexity when the probabilistic subgraph (of the influence diagram) is sparse, regardless of the complexity introduced by its utility subgraph.