Optimality Guarantees for Particle Belief Approximation of POMDPs
Optimality Guarantees for Particle Belief Approximation of POMDPs
复制标题
DOI：
10.1613/jair.1.14525
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
M. H. Lim;Tyler J. Becker;Mykel J. Kochenderfer;C. Tomlin;Zachary Sunberg
中科院分区：
文献类型：
--
作者：
M. H. Lim;Tyler J. Becker;Mykel J. Kochenderfer;C. Tomlin;Zachary Sunberg
部分可观测马尔可夫决策过程(POMDP)为现实世界的决策和控制问题提供了一种灵活的表示方法。然而，POMDP是出了名的难以解决，特别是当状态空间和观测空间是连续的或混合的时，这通常是物理系统的情况。虽然最近的基于在线采样的带有观测似然加权的POMDP算法已经显示出实用的有效性，但这些算法所使用的粒子滤波技术的逼近误差的一般理论还没有被提出。我们的主要贡献是对任意POMDP与其相应的有限样本粒子信念MDP(PB-MDP)近似之间的误差进行了界。PB-MDP和POMDP之间的这一基本桥梁允许我们通过求解相应的粒子信念MDP来使任何基于采样的MDP算法适应于POMDP，从而将MDP算法的收敛保证扩展到POMDP。实际上，这是通过使用粒子过滤器信念转移模型作为MDP求解器的生成器模型来实现的。虽然这需要从POMDP访问观测密度模型，但它只会将MDP解算器的过渡采样复杂性增加O(C)倍，其中C是粒子数。因此，当与稀疏采样MDP算法相结合时，该方法可以产生与状态和观测空间的大小没有直接理论依赖的POMDP算法。除了我们的理论贡献，我们还在基准POMDP上进行了五个数值实验，证明了一种基于PB-MDP近似的简单MDP算法Sparse-PFT，其性能与其他领先的连续观测POMDP解算器相当。
Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. However, POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid, which is often the case for physical systems. While recent online sampling-based POMDP algorithms that plan with observation likelihood weighting have shown practical effectiveness, a general theory characterizing the approximation error of the particle filtering techniques that these algorithms use has not previously been proposed. Our main contribution is bounding the error between any POMDP and its corresponding finite sample particle belief MDP (PB-MDP) approximation. This fundamental bridge between PB-MDPs and POMDPs allows us to adapt any sampling-based MDP algorithm to a POMDP by solving the corresponding particle belief MDP, thereby extending the convergence guarantees of the MDP algorithm to the POMDP. Practically, this is implemented by using the particle filter belief transition model as the generative model for the MDP solver. While this requires access to the observation density model from the POMDP, it only increases the transition sampling complexity of the MDP solver by a factor of O(C), where C is the number of particles. Thus, when combined with sparse sampling MDP algorithms, this approach can yield algorithms for POMDPs that have no direct theoretical dependence on the size of the state and observation spaces. In addition to our theoretical contribution, we perform five numerical experiments on benchmark POMDPs to demonstrate that a simple MDP algorithm adapted using PB-MDP approximation, Sparse-PFT, achieves performance competitive with other leading continuous observation POMDP solvers.