論文の概要: 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は、選択された腕のアイデンティティやエージェント間の損失シーケンスを交換することなく、サブ線形後悔を保証できる。
また、理論結果を検証するアルゴリズムの数値評価を行い、合成データと実世界データセットの有効性を実証する。
関連論文リスト
- Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳(メタデータ) (2024-10-08T09:49:47Z) - Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-08-20T13:57:00Z) - Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - Byzantine-Resilient Decentralized Multi-Armed Bandits [25.499420566469098]
エージェント間の情報混合ステップを不整合および極端な値の切り離しで融合するアルゴリズムを開発する。
このフレームワークは、コンピュータネットワークの攻撃者をモデル化したり、攻撃的なコンテンツをレコメンデーターシステムに攻撃したり、金融市場のマニピュレータとして利用することができる。
論文 参考訳(メタデータ) (2023-10-11T09:09:50Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳(メタデータ) (2023-08-29T18:18:21Z) - On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [7.23389716633927]
我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。
また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
論文 参考訳(メタデータ) (2022-11-30T16:46:41Z) - Near-Optimal Collaborative Learning in Bandits [15.456561090871244]
本稿では,各エージェントが有限個のアームに対向する一般マルチエージェントバンディットモデルを提案する。
ツイストは、各エージェントの最適なアームは最大の混合報酬を持つアームであり、アームの混合報酬は全てのエージェントに対するこのアームの報酬の重み付けの和である。
純粋探索のための近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-31T21:11:47Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳(メタデータ) (2021-01-21T10:35:09Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-23T19:52:44Z) - The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [20.259428328004738]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文 参考訳(メタデータ) (2020-01-15T17:49:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。