Max-norm Projections for Factored MDPs
Max-norm Projections for Factored MDPs
复制标题
因式分解 MDP 的最大范数投影
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Ronald E. Parr
中科院分区：
文献类型：
--
作者：
Carlos Guestrin;D. Koller;Ronald E. Parr
马尔可夫决策过程（MDP）为不确定性下的规划提供了一个连贯的数学框架。然而，精确的MDP解决方案算法需要操纵值函数，该值函数为系统中的每个状态指定一个值。大多数真实世界的MDP太大，这样的表示是可行的，防止使用精确的MDP算法。已经提出了各种近似解算法，其中许多使用基函数的线性组合作为值函数的紧凑近似。几乎所有这些算法都使用基于（加权）L2范数（欧几里得距离）的近似;这种方法防止了MDP算法的标准收敛结果的应用，所有这些算法都是基于最大范数的。本文有两个贡献。首先，它提出了第一近似MDP解决方案算法-值和策略迭代-使用最大范数投影，从而直接优化所需的数量，以获得最佳的误差界。其次，它显示了这些算法可以有效地应用在分解的MDP的上下文中，其中使用动态贝叶斯网络指定的过渡模型。
Markov Decision Processes (MDPs) provide a coherent mathematical framework for planning under uncertainty. However, exact MDP solution algorithms require the manipulation of a value function, which specifies a value for each state in the system. Most real-world MDPs are too large for such a representation to be feasible, preventing the use of exact MDP algorithms. Various approximate solution algorithms have been proposed, many of which use a linear combination of basis functions as a compact approximation to the value function. Almost all of these algorithms use an approximation based on the (weighted) L2-norm (Euclidean distance); this approach prevents the application of standard convergence results for MDP algorithms, all of which are based on max-norm. This paper makes two contributions. First, it presents the first approximate MDP solution algorithms - both value and policy iteration - that use max-norm projection, thereby directly optimizing the quantity required to obtain the best error bounds. Second, it shows how these algorithms can be applied efficiently in the context of factored MDPs, where the transition model is specified using a dynamic Bayesian network.