通过局部策略降低多智能体博弈的通信与内存开销，同时保证逼近最优解。
Multi-agent Reach-avoid MDP via Potential Games and Low-rank Policy Structure
- 用局部反馈策略替代全局策略，实现低秩分解以减少资源消耗。
- 在不同场景下，峰值内存和离线计算复杂度显著下降，误差仍可控。
- 利用潜在博弈结构，确保学习算法收敛到确定性纳什均衡，适合分布式部署。
我们通过局部反馈策略优化有限时域多智能体追逃马尔可夫决策过程（MDP）。全局反馈策略虽能实现全局最优，但其通信、内存和计算复杂度随智能体数量呈指数增长。通过将解空间限制为局部反馈策略，并证明其为全局策略的秩一分解，提供了降低通信复杂度与内存占用的理论依据。此外，我们证明基于局部策略的多智能体追逃MDP具有潜在博弈结构，使得迭代最佳响应成为可计算的多智能体学习方案，且保证收敛至确定性纳什均衡；各智能体的最佳响应可通过联合状态空间上的乘法动态规划求解。数值仿真在多个不同MDP与智能体配置下验证：峰值内存使用量与离线计算复杂度显著降低，同时保持对最优全局追逃目标的近似误差。
原文摘要 · Abstract (English)
We optimize finite horizon multi-agent reach-avoid Markov decision process (MDP) via \emph{local feedback policies}. The global feedback policy solution yields global optimality but its communication complexity, memory usage and computation complexity scale exponentially with the number of agents. We mitigate this exponential dependency by restricting the solution space to local feedback policies and show that local feedback policies are rank-one factorizations of global feedback policies, which provides a principled approach to reducing communication complexity and memory usage. Additionally, by demonstrating that multi-agent reach-avoid MDPs over local feedback policies has a potential game structure, we show that iterative best response is a tractable multi-agent learning scheme with guaranteed convergence to deterministic Nash equilibrium, and derive each agent's best response via multiplicative dynamic program (DP) over the joint state space. Numerical simulations across different MDPs and agent sets show that the peak memory usage and offline computation complexity are significantly reduced while the approximation error to the optimal global reach-avoid objective is maintained.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。