arXiv:2509.22596cs.MAcs.LG2025-09NeurIPS被引 4

提出两种无需参数的多智能体在线协调算法,可处理弱次模目标。

Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives

  • 基于新型策略连续扩展技术,实现无损取样
  • 在弱次模场景下仍保持(1−c/e)近似比
  • 无需预知参数,适合复杂动态环境

本文提出两种有效的多智能体在线协调(MA-OC)策略学习算法。首个算法 exttt{MA-SPL} 不仅对子模目标能达到最优的 (1−c/e) 近似保证,还可处理 α-弱递减回报(DR-submodular)和 (γ,β)-弱子模情形,其中 c 为子模函数的曲率,α 表示边际递减比率,(γ,β) 为子模比率。为降低 exttt{MA-SPL} 中对未知参数 α,γ,β 的依赖,我们进一步提出完全无参数的 exttt{MA-MPL} 算法,其同样保持与 exttt{MA-SPL} 相同的近似比。核心在于一种新颖的基于策略的连续扩展方法,相比经典的多线性扩展,该方法可对任意集合函数提供无损取样,从而有效应对困难的弱子模目标。大量仿真实验验证了所提算法的有效性。

原文摘要 · Abstract (English)

In this paper, we present two effective policy learning algorithms for multi-agent online coordination(MA-OC) problem. The first one, \texttt{MA-SPL}, not only can achieve the optimal $(1-\frac{c}{e})$-approximation guarantee for the MA-OC problem with submodular objectives but also can handle the unexplored $α$-weakly DR-submodular and $(γ,β)$-weakly submodular scenarios, where $c$ is the curvature of the investigated submodular functions, $α$ denotes the diminishing-return(DR) ratio and the tuple $(γ,β)$ represents the submodularity ratios. Subsequently, in order to reduce the reliance on the unknown parameters $α,γ,β$ inherent in the \texttt{MA-SPL} algorithm, we further introduce the second online algorithm named \texttt{MA-MPL}. This \texttt{MA-MPL} algorithm is entirely \emph{parameter-free} and simultaneously can maintain the same approximation ratio as the first \texttt{MA-SPL} algorithm. The core of our \texttt{MA-SPL} and \texttt{MA-MPL} algorithms is a novel continuous-relaxation technique termed as \emph{policy-based continuous extension}. Compared with the well-established \emph{multi-linear extension}, a notable advantage of this new \emph{policy-based continuous extension} is its ability to provide a lossless rounding scheme for any set function, thereby enabling us to tackle the challenging weakly submodular objectives. Finally, extensive simulations are conducted to validate the effectiveness of our proposed algorithms.

多智能体在线学习次模优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。