提出新方法解决异构多智能体决策难题，实现近最优收益。
Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs
- 用投影构造李雅普诺夫函数，突破异构约束
- 证明每臂长期平均收益差距为 $O(1/\sqrt{N})$
- 适用于大规模异构多子问题系统
异质性是现实世界大规模决策问题的根本挑战，但研究仍不足。本文研究一类典型问题——弱耦合马尔可夫决策过程（WCMDPs）的完全异构情形。每个 WCMDP 包含 $N$ 个臂（或子问题），在完全异构设置下各臂模型参数不同，导致 $N$ 较大时出现维数灾难。我们证明，在温和假设下，一种可高效计算的策略可使每臂长期平均收益的最优性差距达到 $O(1/\sqrt{N})$，这是首个关于完全异构平均奖励 WCMDPs 的渐近最优结果。核心技术创新在于构建基于投影的李雅普诺夫函数，即使在完全异构条件下也能保证收益与成本收敛至最优区域。
原文摘要 · Abstract (English)
Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied. In this paper, we study the fully heterogeneous setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs). Each WCMDP consists of $N$ arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when $N$ is large. We show that, under mild assumptions, an efficiently computable policy achieves an $O(1/\sqrt{N})$ optimality gap in the long-run average reward per arm for fully heterogeneous WCMDPs as $N$ becomes large. This is the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs. Our main technical innovation is the construction of projection-based Lyapunov functions that certify the convergence of rewards and costs to an optimal region, even under full heterogeneity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。