通过计数策略解决多智能体决策爆炸问题，实现高效求解。
The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting
- 用策略计数替代传统代理计数，压缩复杂度
- 新方法使多智能体问题在多项式时间内可解
- 适合大规模协同决策场景的算法设计
去中心化部分可观测马尔可夫决策过程（DecPOMDPs）是建模多智能体不确定性决策的通用框架。然而，其复杂度随智能体数量呈指数增长。现有方法通过识别具有对称性的智能体分组，利用计数进行紧凑编码以缓解此问题。但即便模型复杂度降低，策略空间仍会爆炸。本文转而对策略进行计数，提出策略计数型DecPOMDPs，实现了在智能体数量上的可计算性。进一步，我们提出了基于紧凑表示的策略计数动态规划算法，高效求解该类问题。
原文摘要 · Abstract (English)
Decentralised partially observable Markov decision processes (DecPOMDPs) provide a general framework for modelling multi-agent decision making under uncertainty. However, DecPOMDPs are known to suffer from exponential complexity in the number of agents. One way to combat this intractability in agent numbers is to look at partitions of agents that exhibit a form of symmetry among agents, allowing for a compact encoding by counting. However, a challenge arises as the policy space explodes, even though the model complexity and evaluation cost reduce to a polynomial dependence. In this paper, we redirect our focus from counting agents to counting policies, which actually enables tractability in agent numbers for so called policy-counted DecPOMDPs. Further, we present policy-counted dynamic programming using the compact representation to solve policy-counted DecPOMDPs efficiently.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。