論文の概要: A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits
- arxiv url: http://arxiv.org/abs/2207.03106v1
- Date: Thu, 7 Jul 2022 06:16:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-08 13:36:39.917084
- Title: A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits
- Title（参考訳）: 非同期フェデレーションコンテキスト線形バンディットのための単純かつ有理効率なアルゴリズム
- Authors: Jiafan He and Tianhao Wang and Yifei Min and Quanquan Gu
- Abstract要約: 我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
- 参考スコア（独自算出の注目度）: 77.09836892653176
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study federated contextual linear bandits, where $M$ agents cooperate with
each other to solve a global contextual linear bandit problem with the help of
a central server. We consider the asynchronous setting, where all agents work
independently and the communication between one agent and the server will not
trigger other agents' communication. We propose a simple algorithm named
\texttt{FedLinUCB} based on the principle of optimism. We prove that the regret
of \texttt{FedLinUCB} is bounded by $\tilde{O}(d\sqrt{\sum_{m=1}^M T_m})$ and
the communication complexity is $\tilde{O}(dM^2)$, where $d$ is the dimension
of the contextual vector and $T_m$ is the total number of interactions with the
environment by $m$-th agent. To the best of our knowledge, this is the first
provably efficient algorithm that allows fully asynchronous communication for
federated contextual linear bandits, while achieving the same regret guarantee
as in the single-agent setting.
- Abstract（参考訳）: 我々は,M$エージェントが相互に協力し,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
楽観主義に基づく単純なアルゴリズムである \texttt{fedlinucb} を提案する。
我々は、 \texttt{FedLinUCB} の後悔は $\tilde{O}(d\sqrt{\sum_{m=1}^M T_m})$ で有界であり、通信複雑性は $\tilde{O}(dM^2)$ であり、$d$ は文脈ベクトルの次元であり、$T_m$ は$m$-th エージェントによる環境との相互作用の総数であることを示す。
我々の知る限り、これはフェデレーションされたコンテキスト線形帯域に対して完全な非同期通信を可能にする最初の証明可能な効率的なアルゴリズムであり、単一エージェント設定と同じ後悔の保証を達成する。
関連論文リスト
- Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Federated Contextual Cascading Bandits with Asynchronous Communication
and Heterogeneous Users [95.77678166036561]
繊細な通信プロトコルを用いたUPB型アルゴリズムを提案する。
同期フレームワークで達成されたものと同等のサブ線形後悔境界を与えます。
合成および実世界のデータセットに関する実証評価は、後悔と通信コストの観点から、我々のアルゴリズムの優れた性能を検証する。
論文 参考訳（メタデータ） (2024-02-26T05:31:14Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Distributed Contextual Linear Bandits with Minimax Optimal Communication
Cost [48.288452411283444]
そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。
本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。
我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
論文 参考訳（メタデータ） (2022-05-26T05:56:23Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。
我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
論文 参考訳（メタデータ） (2021-02-22T02:46:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。