論文の概要: Distributed Bandits: Probabilistic Communication on $d$-regular Graphs
- arxiv url: http://arxiv.org/abs/2011.07720v2
- Date: Sat, 9 Oct 2021 00:51:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 23:58:19.265769
- Title: Distributed Bandits: Probabilistic Communication on $d$-regular Graphs
- Title（参考訳）: 分散帯域:$d$-regularグラフ上の確率的通信
- Authors: Udari Madhushani and Naomi Ehrich Leonard
- Abstract要約: 我々は、$d$-regular graphで定義されたネットワーク上の確率と通信するエージェントに対して、分散マルチエージェントのマルチアームバンディット問題について検討する。
エージェントベースの手法がグループ後悔の最小化にどのように貢献するかを解析し、新しいアッパー信頼境界(UCB)に基づくアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 5.33024001730262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the decentralized multi-agent multi-armed bandit problem for agents
that communicate with probability over a network defined by a $d$-regular
graph. Every edge in the graph has probabilistic weight $p$ to account for the
($1\!-\!p$) probability of a communication link failure. At each time step,
each agent chooses an arm and receives a numerical reward associated with the
chosen arm. After each choice, each agent observes the last obtained reward of
each of its neighbors with probability $p$. We propose a new Upper Confidence
Bound (UCB) based algorithm and analyze how agent-based strategies contribute
to minimizing group regret in this probabilistic communication setting. We
provide theoretical guarantees that our algorithm outperforms state-of-the-art
algorithms. We illustrate our results and validate the theoretical claims using
numerical simulations.
- Abstract（参考訳）: 我々は,$d$-regular graph で定義されたネットワーク上で確率と通信するエージェントに対する分散マルチエージェントマルチアームドバンディット問題について検討した。
グラフのすべてのエッジには、確率的重量が1\!
-\!
p$)通信リンク障害の確率。
各タイミングで各エージェントがアームを選択し、選択したアームに関連する数値報酬を受け取る。
各選択の後、各エージェントは、その隣人の最後に得られる報酬を確率$p$で観察する。
本稿では,この確率的通信環境におけるグループ後悔を最小限に抑えるために,エージェントベースの戦略がいかに貢献するかを分析する。
アルゴリズムが最先端のアルゴリズムを上回るという理論的保証を提供する。
本研究の結果を概説し,数値シミュレーションによる理論的主張を検証した。
関連論文リスト
- 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) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - 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) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with
Heterogeneous Rewards [14.822625665220068]
環境によって提供される時間依存ランダムグラフによって複数のクライアントが接続される分散マルチエージェントマルチアームバンディット問題について検討する。
目標は、コラボレーションを通じてシステム全体の後悔を最小化することです。
論文 参考訳（メタデータ） (2023-06-08T22:37:24Z) - Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。
本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文 参考訳（メタデータ） (2022-10-14T13:09:11Z) - QuTE: decentralized multiple testing on sensor networks with false
discovery rate control [130.7122910646076]
本稿では、偽発見率(FDR)の証明可能な保証を備えたグラフ上での分散多重仮説検定法を設計する。
異なるエージェントが無向グラフのノードに存在し、各エージェントはそのノードに局所的な1つ以上の仮説に対応するp値を持つ。
各エージェントは、グラフ全体の大域的FDRが予め定義されたレベルで制御されなければならないという共同目的のもと、隣人とのみ通信することで、それぞれのローカル仮説の1つ以上の拒絶を個別に決めなければならない。
論文 参考訳（メタデータ） (2022-10-09T19:48:39Z) - Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
論文 参考訳（メタデータ） (2022-05-12T19:46:35Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Bayesian Algorithms for Decentralized Stochastic Bandits [12.350564981588063]
我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。
我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。
目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
論文 参考訳（メタデータ） (2020-10-20T19:14:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。