論文の概要: Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives

• arxiv url: http://arxiv.org/abs/2509.22596v1
• Date: Fri, 26 Sep 2025 17:16:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.60995
• Title: Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives
• Title（参考訳）: サブモジュールオブジェクトを越えたマルチエージェントオンラインコーディネートのための効果的なポリシー学習
• Authors: Qixin Zhang, Yan Sun, Can Jin, Xikun Zhang, Yao Shu, Puning Zhao, Li Shen, Dacheng Tao,
• Abstract要約: マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。 1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。 第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
• 参考スコア（独自算出の注目度）: 64.16056378603875
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\alpha$-weakly DR-submodular and $(\gamma,\beta)$-weakly submodular scenarios, where $c$ is the curvature of the investigated submodular functions, $\alpha$ denotes the diminishing-return(DR) ratio and the tuple $(\gamma,\beta)$ represents the submodularity ratios. Subsequently, in order to reduce the reliance on the unknown parameters $\alpha,\gamma,\beta$ 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.
• Abstract（参考訳）: 本稿では,マルチエージェントオンラインコーディネーション(MA-OC)問題に対する2つの効果的なポリシー学習アルゴリズムを提案する。 1つ目の例である \texttt{MA-SPL} は、部分モジュラー目的を持つ MA-OC 問題に対する最適な $(1-\frac{c}{e})$-approximation guarantee を達成するだけでなく、探索されていない $\alpha$-weakly DR-submodular and $(\gamma,\beta)$-weakly submodular scenarios を扱える。 その後、未知パラメータ $\alpha,\gamma,\beta$ を \texttt{MA-SPL} アルゴリズムに固有のものにするため、さらに、 \texttt{MA-MPL} という2番目のオンラインアルゴリズムを導入する。 この \texttt{MA-MPL} アルゴリズムは完全に \emph{parameter-free} であり、同時に最初の \texttt{MA-SPL} アルゴリズムと同じ近似比を維持することができる。 我々の \texttt{MA-SPL} アルゴリズムと \texttt{MA-MPL} アルゴリズムの中核は \emph{policy-based continuous extension} と呼ばれる新しい連続緩和手法である。 十分に確立された \emph{multi-linear extension} と比較すると、この新しい \emph{policy-based continuous extension} の顕著な利点は、任意の集合函数に対して損失のない丸めスキームを提供することであり、これにより、挑戦的な弱部分モジュラー目的に取り組むことができる。 最後に,提案アルゴリズムの有効性を検証するため,広範囲なシミュレーションを行った。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  本研究では,有限状態空間を持つ無限水平割引決定過程(MD)に対して,単時間アクタークリティカル(AC)アルゴリズムのグローバル収束を解析する。 我々は,アクタと批評家の両方のステップサイズが (O(k-Pfrac12) として崩壊し,従来の (O(k-Pfrac12) ) レートから (非最適) の Markov フレームワーク最適化で一般的に使用される (O(k-Pfrac12) ) レートから$k$ になることを示した。
  論文  参考訳（メタデータ） (2024-10-11T14:46:29Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization [11.889570525184801]
  単調連続DR-submodular-Frank問題に対する2つの分散オンラインアルゴリズムを提案する。 1つはOne-shot Decentralized Meta-Wolfe (Mono-DMFW)で、1-1/e)$regret bound $O(T4/5)$を達成している。 次に,非公開ブースティング関数citepzhang2022 に着想を得て,分散オンラインブースティング・グラディエント・アセンジ(DOBGA)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-18T07:32:28Z)
• Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback [12.914842850902456]
  本稿では, 閉鎖凸集合上でのオンライン非単調連続DR-サブモジュラー問題を再検討する。 メタ-MFWアルゴリズムは$O(sqrtT)$の1/e$-regret境界を達成する。 次に、Mono-MFWを帯域設定に拡張し、$O(T8/9)の1/e$-regretバウンダリのBandit-MFWアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-16T09:32:37Z)
• Faster First-Order Algorithms for Monotone Strongly DR-Submodular Maximization [11.919431962501479]
  連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。 そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-15T18:53:14Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。