論文の概要: Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards

• arxiv url: http://arxiv.org/abs/2611.04774v1
• Date: Tue, 03 Nov 2026 12:14:56 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-04 17:46:49.86047
• Title: Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards
• Title（参考訳）: 部分モジュラ形軌道逆流を用いた協調的マルチエージェント強化学習
• Abstract要約: 疎結合力学とサブモジュラー報酬関数を用いた協調型マルチエージェント強化学習について検討した。 本稿では,局所的なポリシーを逐次最適化するために,分離されたダイナミクスを利用するグリージーアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.767665631734795
• License:
• Abstract: We study cooperative multi-agent reinforcement learning with decoupled dynamics and a monotone submodular reward function over joint trajectories. Due to the non-additive reward, an optimal policy may depend on the history of all agents. This dependence makes exact optimization exponential in the horizon and the number of agents. To overcome this challenge while retaining theoretical guarantees, we introduce pre-window curvature $c_m$, which quantifies how states visited more than $m$ steps earlier reduce current marginal gains. Using this curvature to control the error from restricting the policy of each agent to depend only on its last $m+1$ states, we propose a greedy algorithm that exploits the decoupled dynamics to optimize local policies sequentially. For fixed $m$, the algorithm achieves a $\frac{1-c_m}{2-c_m}$ approximation guarantee up to estimation error, and its computation time is polynomial in the number of agents and the horizon. We recover the known $1/2$-factor approximation for time-additive rewards and obtain an approximation factor no smaller than the known total-curvature bound for a single agent. We formulate multi-agent traffic monitoring as an example of this framework and evaluate our algorithm on it.
• Abstract（参考訳）: 結合軌道上の非結合力学と単トン部分モジュラー報酬関数を用いた協調型マルチエージェント強化学習について検討した。 非付加的な報酬のため、最適な政策はすべてのエージェントの歴史に依存するかもしれない。 この依存は、水平線とエージェント数において正確な最適化を指数関数化する。 理論的保証を維持しながら、この課題を克服するために、我々は、現在の限界ゲインを減少させる前に、州がどのように$m$以上のステップを訪れたかを定量化する、事前の曲率$c_m$を導入する。 この曲率を用いて、各エージェントのポリシが最後の$m+1$状態のみに依存するように制限されないようエラーを制御し、分離されたダイナミクスを利用して局所的なポリシーを逐次最適化するグリーディアルゴリズムを提案する。 固定された$m$の場合、アルゴリズムは推定誤差まで$\frac{1-c_m}{2-c_m}$近似を達成し、その計算時間はエージェントの数と水平線の多項式である。 我々は、時間付加的な報酬に対する既知の1/2$-factor近似を回復し、単一のエージェントに対する既知の全曲率よりも小さい近似係数を得る。 このフレームワークの例としてマルチエージェントトラフィック監視を定式化し,その上でアルゴリズムを評価する。

関連論文リスト

• Fine-Tuning on Self-Generated and Reward-Weighted Data: Learning Dynamics, Convergence Rates, and Benefits of Off-Policyness [69.00065140233411]
  REINFORCE -- RE(S) と呼ばれる -- は、$S ge 1$グルーフステップ毎にロールアウト分布を更新する。 我々は、$ ge 1$のスペクトルを網羅するRE(S) の統一理論を開発する。 任意の固定された$S$に対して、RE(S) は、ロールアウト分布の更新数$B = lfloor T / S rfloor rightarrow infty$ として最適ポリシーへの大域収束を楽しむ。
  論文  参考訳（メタデータ） (2026-09-29T07:54:06Z)
• Multi-Agent Reinforcement Learning with Submodular Reward [7.561267501457281]
  協調型マルチエージェント強化学習(MARL)について検討した。 提案手法は,サンプルの効率と後悔の束縛を保証できるアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2026-03-06T19:17:29Z)
• 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)
• Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning [8.400105595501158]
  我々は、新しい$textttSUBPLE-MFQ$(textbfSubsample$-$textbfMean-$textbfF$ield-$textbfQ$-learning)と、$n$エージェントを持つシステムの分散ランダム化ポリシーを提案する。 我々は、この学習されたポリシーが$tilde$O (1/sqrtk)$の順序の最適ポリシーに収束することを証明する。
  論文  参考訳（メタデータ） (2024-12-01T03:45:17Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである 本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。 マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-02-11T01:51:15Z)
• Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities [12.104551746465932]
  安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。 我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。 サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
  論文  参考訳（メタデータ） (2023-05-27T20:08:35Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
  複数の長期目標の非線形凹関数を最大化する問題を定式化する。 この問題に対してポリシー段階に基づくモデルフリーアルゴリズムを提案する。 提案アルゴリズムは,グローバルオプティマの$epsilon$以内に収束することが示されている。
  論文  参考訳（メタデータ） (2021-05-28T22:20:54Z)

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

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