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

In this paper, we present two effective policy learning algorithms for multi-agent online coordination(MA-OC) problem. The first one, textttMA-SPL, not only can achieve the optimal (1-fracce)-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 textttMA-SPL algorithm, we further introduce the second online algorithm named textttMA-MPL. This textttMA-MPL algorithm is entirely parameter-free and simultaneously can maintain the same approximation ratio as the first textttMA-SPL algorithm. The core of our textttMA-SPL and textttMA-MPL algorithms is a novel continuous-relaxation technique termed as policy-based continuous extension. Compared with the well-established multi-linear extension, a notable advantage of this new 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.