基于覆盖数的部分可观察不确定性规划理论及方法

The partially observable Markov decision process (POMDP) provides a general mathematical model for single agent of planning under uncertainty in stochastic environments. The POMDP planning problem of finding a near optimal solution often suffers from the curse of dimensionality and the curse of history. The state space size and the covering number of the search space are two complexity metrics in terms of the curse of dimensionality and the curse of history, respectively. Our project includes the following aspects: First, by generalizing the covering number concept mathematically, we extend the covering number theory from the discrete POMDP planning domain to continuous-state POMDP planning domain. Second, we use the tree-trials search technique to improve a state-of-the-art offline algorithm based on the covering number idea, aiming to improve the original algorithm's convergence. Third, we propose a novel online algorithm also based on the covering number idea, by combing the existing deterministic sparse partially observable tree method with other techniques, such as the covering number theory, the hybrid heuristics and tree-trials search. Fourth, we evaluate the empirical performance of our new proposed offline and online planning algorithms in handling large POMDPs. Through these researches, the project will enrich the covering-number based POMDP planning theories and propose the offline and online approximate planning methods for large POMDPs from the covering number perspective.

部分可观察马氏决策过程（简称POMDP）为智能体在随机环境中的不确定性规划问题提供了一个通用的数学模型。POMDP规划问题的近似求解容易陷入信念状态“维数灾”和“历史灾”问题。问题的状态数是“维数灾”的度量，搜索空间的覆盖数是“历史灾”的度量。本项目的研究内容包括：（1）通过在数学上一般化覆盖数的概念，把离散空间POMDP模型中有关覆盖数的规划理论推广到连续空间的POMDP模型；（2）利用树状试探搜索的思想，改进现有的基于覆盖数的离线规划算法，提高算法的收敛速度；（3）基于已提出的确定性的稀疏部分可观察树在线算法，结合覆盖数理论、杂合启发法和树状试探搜索法等，提出新的基于覆盖数理论的在线近似规划方法；（4）评估新提出的离线和在线规划算法处理大空间POMDP规划问题的实验性能。通过以上研究，拟丰富基于覆盖数的POMDP规划理论体系，提出基于覆盖数理论的大空间POMDP离线和在线规划方法。

本项目（1）用覆盖数理论研究了连续状态空间POMDP模型的近似规划复杂性；把POMDP近似规划问题的覆盖数理论从1范数度量空间推广到了n范数度量空间；建立了基于不容许的启发式信息约束下的搜索空间覆盖数的近似规划理论；提出了可扩展的估算覆盖数的方法。（2）针对连续状态空间的POMDP问题，提出了三种途径来裁剪并优化由蒙特卡罗值迭代方法得到的策略图。（3）综述了POMDP近似规划理论和方法、深度强化学习方法。（4）针对Q学习方法中Q值高估和双Q学习方法中Q值低估的问题，提出了加权双Q学习方法。（5）为提升深度强化学习方法在部分可观察随机环境中的稳定性和学习效果，提出了基于多重门限机制的异步行动者-评论家算法、带优先级采样的深度Q网络模型和带视觉注意力机制的双层门限循环神经网络模型。（6）为提升深度强化学习方法在多智能体非静态对手环境中的学习效果，提出了深度贝叶斯策略重用方法。基于上述成果，在IJCAI、NeurIPS、AAMAS、《Frontiers of Computer Science》和《计算机学报》等会议和期刊发表学术论文15篇（其中，SCI检索1篇，EI检索13篇），撰写专著章节2章，授权中国发明专利1项，登记软件著作权4项。本项目培养了多名研究生，其中已毕业的研究生4名，在读硕士研究生3名。