Stochastic dynamic programming with factored representations
Stochastic dynamic programming with factored representations
复制标题
DOI：
10.1016/s0004-3702(00)00033-3
复制
发表时间：
2000-08-01
影响因子：
14.4
通讯作者：
Goldszmidt, M
中科院分区：
文献类型：
--
作者：
Boutilier, C;Dearden, R;Goldszmidt, M
马尔可夫决策过程（MDP）已被证明是决策理论规划的流行模型，但用于求解MDP的标准动态规划算法依赖于显式的基于状态的规范和计算。为了减轻与这些方法相关的组合问题，我们提出了新的代表性和计算技术的MDP，利用某些类型的问题结构。我们使用动态贝叶斯网络（决策树表示当地的家庭的条件概率分布），以表示随机行动的MDP，连同决策树表示奖励。基于这种表示，我们开发的标准动态规划算法，直接操纵决策树表示的政策和价值函数的版本。这通常消除了对逐状态计算的需要，在这些树的叶子处聚合状态，并且仅需要对每个聚合状态进行计算。这些算法的关键是经典回归分析的决策理论推广，在其中我们确定与预测期望值相关的特征。我们证明了经验的方法在几个规划问题，显示出显着的节省某些类型的域。我们还确定了某些类别的问题，这种技术无法很好地执行，并建议扩展和相关的想法，在这种情况下可能会证明是有用的。我们还简要描述了基于这种方法的近似方案。(C)2000 Elsevier Science B.V.保留所有权利。
Markov decision processes (MDPs) have proven to be popular models for decision-theoretic planning, but standard dynamic programming algorithms for solving MDPs rely on explicit, state-based specifications and computations. To alleviate the combinatorial problems associated with such methods, we propose new representational and computational techniques for MDPs that exploit certain types of problem structure. We use dynamic Bayesian networks (with decision trees representing the local families of conditional probability distributions) to represent stochastic actions in an MDP, together with a decision-tree representation rewards. Based on this representation, we develop versions of standard dynamic programming algorithms that directly manipulate decision-tree representations of policies and value functions. This generally obviates the need for state-by-state computation, aggregating states at the leaves of these trees and requiring computations only for each aggregate state. The key to these algorithms is a decision-theoretic generalization of classic regression analysis, in which we determine the features relevant to predicting expected value. We demonstrate the method empirically on several planning problems, showing significant savings for certain types of domains. We also identify certain classes of problems for which this technique fails to perform well and suggest extensions and related ideas that may prove useful in such circumstances. We also briefly describe an approximation scheme based on this approach. (C) 2000 Elsevier Science B.V. All rights reserved.