論文の概要: Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and
Generalization
- arxiv url: http://arxiv.org/abs/2110.14622v1
- Date: Wed, 27 Oct 2021 17:45:22 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 13:58:31.574893
- Title: Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and
Generalization
- Title（参考訳）: 不均質なマルチプレイヤーマルチアームバンド:ギャップの閉鎖と一般化
- Authors: Chengshuai Shi, Wei Xiong, Cong Shen, Jing Yang
- Abstract要約: 本稿では,アダプティブ・コミュニティオ(Adaptive CommunicatioN)を用いたバッチド・エクスプロレーション(Batched Exploration with Adaptive CommunicatioN)を提案する。
次に、既存の線形回帰MP-MAB問題を、システム報酬が個々の報酬の一般(非線形)関数である新しいMP-MAB問題に一般化する。
BEACONを拡張してこの問題を解決し、対数的後悔を証明する。
- 参考スコア（独自算出の注目度）: 20.77492493886307
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite the significant interests and many progresses in decentralized
multi-player multi-armed bandits (MP-MAB) problems in recent years, the regret
gap to the natural centralized lower bound in the heterogeneous MP-MAB setting
remains open. In this paper, we propose BEACON -- Batched Exploration with
Adaptive COmmunicatioN -- that closes this gap. BEACON accomplishes this goal
with novel contributions in implicit communication and efficient exploration.
For the former, we propose a novel adaptive differential communication (ADC)
design that significantly improves the implicit communication efficiency. For
the latter, a carefully crafted batched exploration scheme is developed to
enable incorporation of the combinatorial upper confidence bound (CUCB)
principle. We then generalize the existing linear-reward MP-MAB problems, where
the system reward is always the sum of individually collected rewards, to a new
MP-MAB problem where the system reward is a general (nonlinear) function of
individual rewards. We extend BEACON to solve this problem and prove a
logarithmic regret. BEACON bridges the algorithm design and regret analysis of
combinatorial MAB (CMAB) and MP-MAB, two largely disjointed areas in MAB, and
the results in this paper suggest that this previously ignored connection is
worth further investigation. Supplementary Material: pdf
- Abstract（参考訳）: 近年の分散マルチプレイヤーマルチアーム・バンディット(MP-MAB)問題における大きな関心と多くの進展にもかかわらず、異種MP-MABセッティングにおける自然集中化下限に対する後悔のギャップは未解決のままである。
本稿では,このギャップを埋めるBEACON (Batched Exploration with Adaptive CommunicatioN)を提案する。
BEACONは暗黙のコミュニケーションと効率的な探索において、新しい貢献によってこの目標を達成する。
前者に対しては,暗黙的通信効率を大幅に向上させる新しい適応的微分通信(adc)設計を提案する。
後者では、組合せ上信頼境界(CUCB)の原理を組み込むために、慎重に構築されたバッチ探索方式が開発されている。
次に、システム報酬が常に個別に収集された報酬の和である既存の線形回帰MP-MAB問題を、システム報酬が個々の報酬の一般(非線形)関数である新しいMP-MAB問題に一般化する。
BEACONを拡張してこの問題を解決し、対数的後悔を証明する。
BEACONは合成MAB(CMAB)とMP-MAB(MP-MAB)のアルゴリズム設計と再帰解析を橋渡しする。
補助材料:pdf
関連論文リスト
- A Federated Online Restless Bandit Framework for Cooperative Resource Allocation [23.698976872351576]
MRPの未知系力学を用いた協調資源配分問題について検討する。
我々は、このマルチエージェントオンラインRMAB問題を解決するために、フェデレートトンプソン対応Whittle Index(FedTSWI)アルゴリズムを作成した。
数値計算の結果,提案アルゴリズムは,ベースラインと比較して,$mathcalO(sqrtTlog(T))$の高速収束率と性能の向上を実現している。
論文 参考訳（メタデータ） (2024-06-12T08:34:53Z) - Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
CMAB(Multi-armed bandits)の多変量および確率的トリガーアーム(CMAB-MT)を用いた新しい枠組みを導入する。
CMAB-MTは既存のCMABと比べ、モデリング能力を高めるだけでなく、多変量確率変数の異なる統計特性を活用することで結果を改善することができる。
本フレームワークは, エピソード強化学習(RL)や商品分布の確率的最大カバレッジなど, 応用として多くの重要な問題を含むことができる。
論文 参考訳（メタデータ） (2024-06-03T14:48:53Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Distributed Consensus Algorithm for Decision-Making in Multi-agent
Multi-armed Bandit [7.708904950194129]
動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。
グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。
目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
論文 参考訳（メタデータ） (2023-06-09T16:10:26Z) - Implicitly normalized forecaster with clipping for linear and non-linear
heavy-tailed multi-armed bandits [85.27420062094086]
Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。
重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。
INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
論文 参考訳（メタデータ） (2023-05-11T12:00:43Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:56:59Z) - Non-stationary Bandits with Knapsacks [6.2006721306998065]
非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
論文 参考訳（メタデータ） (2022-05-25T01:22:36Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-16T17:52:32Z) - Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
本稿では、インテリジェントSMSルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提案する。
既存のMABアルゴリズムの素早い一般化は、この問題に対してうまく機能しないことを示す。
また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を定めている。
論文 参考訳（メタデータ） (2020-11-03T05:38:42Z) - UneVEn: Universal Value Exploration for Multi-Agent Reinforcement
Learning [53.73686229912562]
我々はUniversal Value Exploration(UneVEn)と呼ばれる新しいMARLアプローチを提案する。
UneVEnは、一連の関連するタスクと、普遍的な後継機能の線形分解を同時に学習する。
一連の探索ゲームにおける実証的な結果、エージェント間の重要な調整を必要とする協調捕食・捕食作業への挑戦、およびStarCraft IIのマイクロマネジメントベンチマークは、UneVEnが他の最先端のMARLメソッドが失敗するタスクを解決できることを示している。
論文 参考訳（メタデータ） (2020-10-06T19:08:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。