Fugu-MT 論文翻訳(概要): Individual Regret in Cooperative Stochastic Multi-Armed Bandits

論文の概要: Individual Regret in Cooperative Stochastic Multi-Armed Bandits

arxiv url: http://arxiv.org/abs/2411.06501v1
Date: Sun, 10 Nov 2024 15:54:23 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-12 14:12:04.208035
Title: Individual Regret in Cooperative Stochastic Multi-Armed Bandits
Title（参考訳）: 協調的確率的マルチアーマッドバンドにおける個人レグレット
Authors: Idan Barnea, Tal Lancewicki, Yishay Mansour,
Abstract要約: ここでは、$A$はアクションの数、$T$は時間軸、$m$はエージェントの数です。特に、十分な数のエージェントを仮定すると、通信グラフの準最適ギャップと直径に依存しない$tildeO(A)$の後悔境界が得られる。
参考スコア（独自算出の注目度）: 44.34612921224053
License:
Abstract: We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We show a near-optimal individual regret bound of $\tilde{O}(\sqrt{AT/m}+A)$, where $A$ is the number of actions, $T$ the time horizon, and $m$ the number of agents. In particular, assuming a sufficient number of agents, we achieve a regret bound of $\tilde{O}(A)$, which is independent of the sub-optimality gaps and the diameter of the communication graph. To the best of our knowledge, our study is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter and applicable to non-fully-connected communication graphs.
Abstract（参考訳）: 任意の通信グラフ上で通信する複数のエージェントを用いて,確率的マルチアーマッドバンド (MAB) における後悔について検討する。ここでは、$A$はアクションの数、$T$はタイムホライズ、$m$はエージェントの数を示す。特に、十分な数のエージェントを仮定すると、通信グラフの準最適ギャップと直径に依存しない$\tilde{O}(A)$の後悔境界が得られる。我々の知る限り、我々の研究は、グラフの直径によらず、完全連結でない通信グラフに適用可能な、協調確率的MABに束縛された個々の後悔を示す最初のものである。

関連論文リスト

Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文参考訳（メタデータ） (2024-05-09T17:40:09Z)
Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis [5.02063914741425]
Zhang, Johansson, Li が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔が$O(gamma Nlog(T)[sqrtKT + DK])$で束縛されていることを証明した。
論文参考訳（メタデータ） (2024-01-18T21:36:17Z)
Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文参考訳（メタデータ） (2023-05-30T16:05:44Z)
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)
Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文参考訳（メタデータ） (2022-06-13T09:17:40Z)
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)
Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
論文参考訳（メタデータ） (2022-05-12T19:46:35Z)
Distributed Bandits: Probabilistic Communication on $d$-regular Graphs [5.33024001730262]
我々は、$d$-regular graphで定義されたネットワーク上の確率と通信するエージェントに対して、分散マルチエージェントのマルチアームバンディット問題について検討する。エージェントベースの手法がグループ後悔の最小化にどのように貢献するかを解析し、新しいアッパー信頼境界(UCB)に基づくアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-11-16T04:53:54Z)
The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [20.259428328004738]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文参考訳（メタデータ） (2020-01-15T17:49:29Z)

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