論文の概要: Doubly Adversarial Federated Bandits
- arxiv url: http://arxiv.org/abs/2301.09223v1
- Date: Sun, 22 Jan 2023 22:36:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 14:29:03.686766
- Title: Doubly Adversarial Federated Bandits
- Title（参考訳）: 二重敵対的フェデレーションバンド
- Authors: Jialin Yi and Milan Vojnovi\'c
- Abstract要約: 本稿では,複数のエージェントが通信ネットワークを介して協調する,非確率的フェデレーション型多武装バンディット問題について検討する。
我々のアルゴリズムは、Cesa-Bianchi et alで提案されたオープンな質問に対して肯定的な答えを与える。
- 参考スコア（独自算出の注目度）: 4.721069729610892
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a new non-stochastic federated multi-armed bandit problem with
multiple agents collaborating via a communication network. The losses of the
arms are assigned by an oblivious adversary that specifies the loss of each arm
not only for each time step but also for each agent, which we call ``doubly
adversarial". In this setting, different agents may choose the same arm in the
same time step but observe different feedback. The goal of each agent is to
find a globally best arm in hindsight that has the lowest cumulative loss
averaged over all agents, which necessities the communication among agents. We
provide regret lower bounds for any federated bandit algorithm under different
settings, when agents have access to full-information feedback, or the bandit
feedback. For the bandit feedback setting, we propose a near-optimal federated
bandit algorithm called FEDEXP3. Our algorithm gives a positive answer to an
open question proposed in Cesa-Bianchi et al. (2016): FEDEXP3 can guarantee a
sub-linear regret without exchanging sequences of selected arm identities or
loss sequences among agents. We also provide numerical evaluations of our
algorithm to validate our theoretical results and demonstrate its effectiveness
on synthetic and real-world datasets
- Abstract（参考訳）: 本稿では,複数のエージェントが通信ネットワークを介して協調する,非確率的フェデレーション型多武装バンディット問題について検討する。
腕の喪失は、各時間ステップだけでなく、各エージェントに対しても、各アームの喪失を特定する、不可解な敵によって割り当てられる。
この設定では、異なるエージェントは同じ時間ステップで同じアームを選択するが、異なるフィードバックを観察する。
それぞれのエージェントの目標は、すべてのエージェントの平均累積損失が最も低い、エージェント間のコミュニケーションを必要とする後見の世界で最高のアームを見つけることである。
エージェントが全情報フィードバックやバンディットフィードバックにアクセスできる場合、異なる設定下でのフェデレーションバンディットアルゴリズムに対して、残念な低限度を提供する。
バンディットフィードバック設定のために,federated banditアルゴリズムfeedexp3を提案する。
我々のアルゴリズムは、Cesa-Bianchi et al. (2016): FEDEXP3は、選択された腕のアイデンティティやエージェント間の損失シーケンスを交換することなく、サブ線形後悔を保証できる。
また、理論結果を検証するアルゴリズムの数値評価を行い、合成データと実世界データセットの有効性を実証する。
関連論文リスト
- On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [4.721069729610892]
我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。
また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2022-11-30T16:46:41Z) - Federated Best Arm Identification with Heterogeneous Clients [79.973538434633]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
本稿では,指数時間瞬間にのみ通信を行うエム・トラック・アンド・ストップ戦略に基づく新しいアルゴリズムを提案する。
最適なアームを見つけるための期待時間に上限があるアルゴリズムが乗算定数まで下限と一致する場合、任意の2つの連続する通信時間の比率は有界でなければならないことを示す。
論文 参考訳（メタデータ） (2022-10-14T13:09:11Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳（メタデータ） (2022-06-13T09:17:40Z) - Near-Optimal Collaborative Learning in Bandits [15.456561090871244]
本稿では,各エージェントが有限個のアームに対向する一般マルチエージェントバンディットモデルを提案する。
ツイストは、各エージェントの最適なアームは最大の混合報酬を持つアームであり、アームの混合報酬は全てのエージェントに対するこのアームの報酬の重み付けの和である。
純粋探索のための近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-31T21:11:47Z) - Optimal Clustering with Bandit Feedback [84.04424523097168]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Collaborative Learning in General Graphs with Limited Memorization:
Learnability, Complexity and Reliability [30.432136485068572]
エージェントが任意に連結された一般グラフにおいて、K武装バンディット問題を考える。
目標は各エージェントに最高の腕を学ばせることだ。
本稿では,3段階の協調学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-01-29T02:42:25Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
論文 参考訳（メタデータ） (2020-12-07T08:23:08Z) - Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
最近の研究によると、$Kの武器を持った盗賊の独立した事例に直面しているエージェントが、後悔を減らすために協力できることが示されている。
我々は、悪質なエージェントの振る舞いを仮定することなく、$m$が$K$よりも小さいと仮定すると、このアルゴリズムに対するコラボレーションは本当に後悔を減らせることを示した。
論文 参考訳（メタデータ） (2020-07-07T22:27:30Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-23T19:52:44Z) - The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [19.457336747088593]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文 参考訳（メタデータ） (2020-01-15T17:49:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。