Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs
Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs
复制标题
在多目标和部分可观测 MDP 的价值迭代中引导 LP
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Spaan
中科院分区：
文献类型：
--
作者：
D. Roijers;E. Walraven;M. Spaan
迭代求解一组线性程序 (LP) 是解决人工智能中各种决策问题的常见策略，例如多目标或部分可观察马尔可夫决策过程 (MDP) 中的规划。一个普遍的特征是，随着求解算法收敛，这些 LP 的解变得越来越相似，因为算法计算的解接近贝尔曼备份算子的不动点。在本文中，我们建议通过基于先前解决的类似 LP 进行引导来加速这些 LP 的求解过程。在迭代生成剩余约束之前，我们使用这些 LP 来初始化相关 LP 约束的子集。由此产生的算法是第一个考虑跨迭代共享信息的算法。我们评估了我们在多目标 MDP (MOMDP) 和部分可观察 MDP (POMDP) 中的规划方法，表明它比现有技术解决的 LP 更少，从而显着提高了速度。此外，对于 MOMDP，我们表明我们的方法在状态数量和目标数量方面都有更好的扩展性，这对于多目标规划至关重要。
Iteratively solving a set of linear programs (LPs) is a common strategy for solving various decision-making problems in Artificial Intelligence, such as planning in multi-objective or partially observable Markov Decision Processes (MDPs). A prevalent feature is that the solutions to these LPs become increasingly similar as the solving algorithm converges, because the solution computed by the algorithm approaches the fixed point of a Bellman backup operator. In this paper, we propose to speed up the solving process of these LPs by bootstrapping based on similar LPs solved previously. We use these LPs to initialize a subset of relevant LP constraints, before iteratively generating the remaining constraints. The resulting algorithm is the first to consider such information sharing across iterations. We evaluate our approach on planning in Multi-Objective MDPs (MOMDPs) and Partially Observable MDPs (POMDPs), showing that it solves fewer LPs than the state of the art, which leads to a significant speed-up. Moreover, for MOMDPs we show that our method scales better in both the number of states and the number of objectives, which is vital for multi-objective planning.