論文の概要: Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost

• arxiv url: http://arxiv.org/abs/2205.13170v1
• Date: Thu, 26 May 2022 05:56:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-27 13:17:36.941729
• Title: Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost
• Title（参考訳）: ミニマックス最適通信コストを用いた分散文脈線形バンディット
• Authors: Sanae Amani, Tor Lattimore, Andr\'as Gy\"orgy, Lin F. Yang
• Abstract要約: そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。 本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。 我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
• 参考スコア（独自算出の注目度）: 48.288452411283444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study distributed contextual linear bandits with stochastic contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features. For this problem, we propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that over $T$ rounds ($NT$ actions in total) the communication cost of DisBE-LUCB is only $\tilde{\mathcal{O}}(dN)$ and its regret is at most $\tilde{\mathcal{O}}(\sqrt{dNT})$, which is of the same order as that incurred by an optimal single-agent algorithm for $NT$ rounds. Remarkably, we derive an information-theoretic lower bound on the communication cost of the distributed contextual linear bandit problem with stochastic contexts, and prove that our proposed algorithm is nearly minimax optimal in terms of \emph{both regret and communication cost}. Finally, we propose DecBE-LUCB, a fully decentralized version of DisBE-LUCB, which operates without a central server, where agents share information with their \emph{immediate neighbors} through a carefully designed consensus procedure.
• Abstract（参考訳）: そこで,n$エージェントが協調して作用し,d$-次元特徴を持つ線形バンディット最適化問題を解く,確率的文脈を持つ分布線形バンディットについて検討した。 本研究では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。 我々は、DisBE-LUCBの通信コストが$\tilde{\mathcal{O}}(dN)$であり、その後悔は少なくとも$\tilde{\mathcal{O}}(\sqrt{dNT})$であることを示す。 ここでは,確率的文脈を用いた分散文脈線形帯域問題における通信コストに関する情報理論の下限を導出し,提案アルゴリズムが<emph{both regret and communication cost} の観点で最小値に近いことを証明した。 最後に,disbe-lucb の完全分散バージョンである decbe-lucb を提案する。これは中央サーバ無しで動作し,エージェントは注意深く設計されたコンセンサス手続きを通じて \emph{immediate neighbors} と情報を共有する。

関連論文リスト

• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• 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)
• Settling the Communication Complexity for Distributed Offline Reinforcement Learning [10.315054389907031]
  オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。 各マシンが送信できる情報の総数(ビット数)には予算の制約がある。 文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
  論文  参考訳（メタデータ） (2022-02-10T06:27:07Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。 ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。 私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
  論文  参考訳（メタデータ） (2020-12-01T07:33:00Z)
• Federated Bandit: A Gossiping Approach [22.595542913855624]
  我々は、分散化されたマルチアーマッド・バンドイット問題であるemphFederated Banditを、$N$エージェントのセットで研究し、接続グラフ$G$で記述された隣人とのみローカルデータを通信できる。 Gossip_UCBは、ローカルな帯域学習をグローバルなゴシッププロセスに適応させ、接続されたエージェント間で情報を共有し、$O(max textttpoly(N,M) log T, textttpoly(N,M) log_lambda-1の順序で後悔を保証できることを示す。
  論文  参考訳（メタデータ） (2020-10-24T03:44:25Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。