解决层次化信息共享 Dec-POMDPs 的广义形式博弈方法
内容提要
该文综述部分状态信息下的多智能体规划研究，涵盖MDP与POMDP的推广、分散与集中控制的差异及双指数复杂度，并介绍子博弈分解、部分历史共享模型、MC-JESP、树分解均衡算法、MDP解耦、GMAA*、FOSG建模及影响乐观上界等方法。
延伸解读
计算复杂性的根本挑战
文章指出，部分状态信息下的分散控制与集中控制存在根本差异，相关问题不适合用多项式时间算法求解，而需要双指数时间算法。这揭示了Dec-POMDPs在计算上的本质困难，意味着实际应用中必须依赖近似方法或特定结构分解，而非追求精确最优解。
方法演进：从分解到共享
文章综述了多种方法：子博弈分解、部分历史共享模型、MC-JESP、树分解均衡算法、MDP解耦、GMAA*、FOSG建模及影响乐观上界。这些方法从不同角度应对复杂性，如通过分解降低规模、通过共享信息重构问题、通过模拟避免显式模型，体现了该领域从理论到实践的多样化探索。
部分历史共享的建模思路
部分历史共享信息结构要求控制器分享部分观察和控制历史，基于共同知识将分散问题重构为等价的集中问题。这种方法提供了更简单、综合的解决方案，并具有更好的结构性和动态规划方案，为分散式随机控制提供了一种普适建模框架。
算法性能与适用边界
树分解算法在标准游戏套件上性能超越现有竞争算法，但存在一类特定基准游戏例外；MC-JESP实验证明其竞争力甚至优于许多使用显式模型的离线方法。这些结果表明不同算法各有优势场景，读者需根据问题结构选择合适方法，并注意其局限性。
Q&A
Dec-POMDP 的求解复杂度为什么是双指数级的？
因为分散控制与集中控制在马尔可夫过程中存在根本差异，相关问题不适合使用多项式时间算法求解，需要使用双指数时间算法。
部分历史共享信息结构模型是如何将分散式问题转化为集中式问题的？
在该模型中，每一时刻控制器都要分享他们的部分观察历史和控制历史。基于所有控制器共同知晓的信息，将分散式问题从一个协调者的角度重构为等价的集中式问题，并提出了一种解决这个等价问题的方法。
MC-JESP 方法有什么特点？
MC-JESP 是一种基于模拟的 POMDP 求解器，用于构建 Dec-POMDP 的有限状态控制器节点，并包含一种启发式导出初始 FSC 的相关方法。实验证明其竞争力甚至优于使用显式模型的许多离线方法。
基于树分解的均衡点发现算法有什么突破？
该算法针对协作游戏的均衡点发现问题，不仅能实现多项实践和理论上的突破，而且思路新颖、高效，可以直接描述相关策略的多面体，因此可以免费获取在相关策略下的平衡点。实验结果证明其在标准游戏套件上的性能超越了现有所有竞争算法，唯一的例外是一类特定的基准游戏。
GMAA* 算法如何优化解决大规模 Dec-POMDPs？
GMAA* 引入了增量聚类与增量展开，并提出了新的混合启发式表示，能够优化解决大规模 Dec-POMDPs 的问题。
影响-乐观上界策略解决了什么问题？
该策略用于解决具有非因式价值函数的解离式部分可观察 MDP 的规模为数十甚至数百个代理的规划问题，并在数字上比较了不同的上界，证明了启发式解法的优化保证，展示了该方法在多代理规划方面的潜在应用。
