Efficient Planning in Large POMDPs through Policy Graph Based Factorized Approximations
Efficient Planning in Large POMDPs through Policy Graph Based Factorized Approximations
复制标题
通过基于策略图的因式分解近似法对大型 POMDP 进行高效规划
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Uusitalo
中科院分区：
文献类型：
--
作者：
J. Pajarinen;J. Peltonen;A. Hottinen;M. Uusitalo
部分可观测马尔可夫决策过程（POMDPs）被广泛用于不确定性规划。在许多应用中，POMDP状态空间的巨大尺寸使得计划（策略）的直接优化在计算上难以处理。为了解决这个问题，我们引入了一个有效的POMDP规划算法。许多当前的方法部分地通过一组“值向量”来存储策略，该“值向量”在每次迭代时通过进一步规划来更新;这样的向量的大小遵循状态空间的大小，使得对于大型POMDPs的计算变得棘手。我们只将策略存储为一个图，这允许在每个策略更新步骤中进行易于处理的近似：对于由多个变量描述的状态空间，我们用因子分解形式近似未来状态的信念，最小化Kullback-Leibler发散到非因子分解分布。我们的其他加速近似包括限制潜在奖励。我们证明了我们的方法在几个强化学习问题中的优势，与以前的四种方法相比。
Partially observable Markov decision processes (POMDPs) are widely used for planning under uncertainty. In many applications, the huge size of the POMDP state space makes straightforward optimization of plans (policies) computationally intractable. To solve this, we introduce an efficient POMDP planning algorithm. Many current methods store the policy partly through a set of "value vectors" which is updated at each iteration by planning one step further; the size of such vectors follows the size of the state space, making computation intractable for large POMDPs. We store the policy as a graph only, which allows tractable approximations in each policy update step: for a state space described by several variables, we approximate beliefs over future states with factorized forms, minimizing Kullback-Leibler divergence to the nonfactorized distributions. Our other speedup approximations include bounding potential rewards. We demonstrate the advantage of our method in several reinforcement learning problems, compared to four previous methods.