論文の概要: Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
- arxiv url: http://arxiv.org/abs/2602.16183v1
- Date: Wed, 18 Feb 2026 05:00:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-19 15:58:30.514203
- Title: Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
- Title（参考訳）: 帯域フィードバック下におけるサブモジュール型福祉問題に対するマルチエージェント・コンビニアル・アーメッド・バンディット・フレームワーク
- Authors: Subham Pokhriyal, Shweta Jain, Vaneet Aggarwal,
- Abstract要約: 本研究では,モノトーンサブモジュール型ユーティリティを持つエージェント間でアイテムを分割する,emph Submodular Welfare Problem (SWP) について検討する。
我々はこれをEmphmulti-agent bandit framework(textscMA-CMAB)に拡張する。
1-1/e のベンチマークに対して $tildemathcalO(T2/3)$ regret を達成し、最初にそのような保証を行う。
- 参考スコア（独自算出の注目度）: 42.17945622232755
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the \emph{Submodular Welfare Problem} (SWP), where items are partitioned among agents with monotone submodular utilities to maximize the total welfare under \emph{bandit feedback}. Classical SWP assumes full value-oracle access, achieving $(1-1/e)$ approximations via continuous-greedy algorithms. We extend this to a \emph{multi-agent combinatorial bandit} framework (\textsc{MA-CMAB}), where actions are partitions under full-bandit feedback with non-communicating agents. Unlike prior single-agent or separable multi-agent CMAB models, our setting couples agents through shared allocation constraints. We propose an explore-then-commit strategy with randomized assignments, achieving $\tilde{\mathcal{O}}(T^{2/3})$ regret against a $(1-1/e)$ benchmark, the first such guarantee for partition-based submodular welfare problem under bandit feedback.
- Abstract（参考訳）: 本研究では,単調なサブモーダルユーティリティを持つエージェント間でアイテムを分割し,全福祉を最大化する「emph{submodular Welfare Problem」について検討する。
古典的なSWPは、連続グリーディアルゴリズムによる1-1/eの近似を達成し、完全なバリューオーラアクセスを前提としている。
我々はこれを,非コミュニケーションエージェントによるフルバンドフィードバックの下での動作がパーティションとなるような 'emph{multi-agent combinatorial bandit} framework (\textsc{MA-CMAB}) に拡張する。
従来の単一エージェントや分離可能なマルチエージェントCMABモデルとは異なり、設定は共有割り当て制約を通じてエージェントをペアリングする。
本稿では, ランダムな代入を伴い, 1-1/e のベンチマークに対して $\tilde{\mathcal{O}}(T^{2/3})$ regret を達成し, 帯域幅フィードバック下での分割型サブモジュール福祉問題に対する最初の保証となる探索的コミット戦略を提案する。
関連論文リスト
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。
1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。
第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
論文 参考訳（メタデータ） (2025-09-26T17:16:34Z) - Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation [33.11114874824768]
両腕を1回だけ引っ張ることができる新しい変種であるFinite-Horizon Single-Pull RMABを紹介した。
我々は、ダミー状態を用いてシステムを複製し、腕が活性化されるとダミー状態内でのみ遷移することを提案する。
有限個のアームに対して,我々の指数ポリシが$tildemathcalOleft(frac1rho1/2right)$の線形に崩壊する平均最適性ギャップを達成できることを初めて実証した。
論文 参考訳（メタデータ） (2025-01-10T16:54:56Z) - Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳（メタデータ） (2024-10-08T09:49:47Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Bandit Multi-linear DR-Submodular Maximization and Its Applications on
Adversarial Submodular Bandits [21.54858035450694]
分割マトロイド制約を持つ部分モジュラー帯域に対するサブ線形後悔アルゴリズムを提案する。
バンドイットの逐次部分モジュラーに対して、既存の研究はO(T2/3)$ regret を証明し、近似比は1/2$である。
論文 参考訳（メタデータ） (2023-05-21T08:51:55Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳（メタデータ） (2021-01-30T21:51:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。