論文の概要: Bayesian Algorithms for Decentralized Stochastic Bandits
- arxiv url: http://arxiv.org/abs/2010.10569v2
- Date: Wed, 28 Oct 2020 00:06:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 06:18:55.709729
- Title: Bayesian Algorithms for Decentralized Stochastic Bandits
- Title（参考訳）: 分散確率バンディットに対するベイズアルゴリズム
- Authors: Anusha Lalitha and Andrea Goldsmith
- Abstract要約: 我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。
我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。
目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
- 参考スコア（独自算出の注目度）: 12.350564981588063
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a decentralized cooperative multi-agent multi-armed bandit problem
with $K$ arms and $N$ agents connected over a network. In our model, each arm's
reward distribution is same for all agents, and rewards are drawn independently
across agents and over time steps. In each round, agents choose an arm to play
and subsequently send a message to their neighbors. The goal is to minimize
cumulative regret averaged over the entire network. We propose a decentralized
Bayesian multi-armed bandit framework that extends single-agent Bayesian bandit
algorithms to the decentralized setting. Specifically, we study an information
assimilation algorithm that can be combined with existing Bayesian algorithms,
and using this, we propose a decentralized Thompson Sampling algorithm and
decentralized Bayes-UCB algorithm. We analyze the decentralized Thompson
Sampling algorithm under Bernoulli rewards and establish a problem-dependent
upper bound on the cumulative regret. We show that regret incurred scales
logarithmically over the time horizon with constants that match those of an
optimal centralized agent with access to all observations across the network.
Our analysis also characterizes the cumulative regret in terms of the network
structure. Through extensive numerical studies, we show that our extensions of
Thompson Sampling and Bayes-UCB incur lesser cumulative regret than the
state-of-art algorithms inspired by the Upper Confidence Bound algorithm. We
implement our proposed decentralized Thompson Sampling under gossip protocol,
and over time-varying networks, where each communication link has a fixed
probability of failure.
- Abstract（参考訳）: ネットワーク上で接続されたK$アームとN$エージェントを用いた分散協調型マルチエージェントマルチアームバンド問題について検討した。
我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。
各ラウンドでは、エージェントがプレーする腕を選択し、次に隣人にメッセージを送信する。
目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
本稿では,単一エージェントのベイジアンバンディットアルゴリズムを分散設定に拡張した分散ベイジアンマルチアームドバンディットフレームワークを提案する。
具体的には,既存のベイズアルゴリズムと組み合わせることができる情報同化アルゴリズムについて検討し,これを用いて,分散トンプソンサンプリングアルゴリズムと分散ベイズUCBアルゴリズムを提案する。
ベルヌーイ報酬の下で,分散型トンプソンサンプリングアルゴリズムを解析し,累積的後悔に対する問題依存上界を確立する。
後悔は時間軸上で対数的にスケールし、最適な集中型エージェントの値とネットワーク全体のすべての観測値と一致する定数を示す。
また,ネットワーク構造における累積的後悔を特徴付ける分析を行った。
広範な数値的な研究を通して、トンプソンサンプリングとベイズUCBの拡張は、アッパー信頼境界アルゴリズムにインスパイアされた最先端のアルゴリズムよりも累積的後悔の少ないことを示す。
提案する分散トンプソンサンプリングをゴシッププロトコルで実装し,各通信リンクに障害の確率が一定である時間変動ネットワーク上で実装する。
関連論文リスト
- Multi-Agent Best Arm Identification in Stochastic Linear Bandits [0.7673339435080443]
固定予算シナリオ下での線形包帯における協調的ベストアーム識別の問題について検討する。
学習モデルでは、複数のエージェントがスターネットワークまたはジェネリックネットワークを介して接続され、線形バンディットインスタンスと並列に相互作用すると考えられる。
我々は、スターネットワークとジェネリックネットワークのためのアルゴリズムMaLinBAI-StarとMaLinBAI-Genをそれぞれ考案した。
論文 参考訳（メタデータ） (2024-11-20T20:09:44Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Distributed Consensus Algorithm for Decision-Making in Multi-agent
Multi-armed Bandit [7.708904950194129]
動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。
グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。
目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
論文 参考訳（メタデータ） (2023-06-09T16:10:26Z) - Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。
エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。
我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
論文 参考訳（メタデータ） (2022-06-01T00:44:53Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound: A Homogeneous Case over Strongly Connected Graphs [9.84486119211443]
本稿では、複数のエージェントのネットワークが同じアームの集合に直面する均質な分散化されたマルチアームバンディット問題について検討する。
隣接関係を有向グラフで記述したマルチエージェントネットワークに対して,完全分散上界信頼度(UCB)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-22T01:05:52Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。
ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。
私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
論文 参考訳（メタデータ） (2020-12-01T07:33:00Z) - Distributed Bandits: Probabilistic Communication on $d$-regular Graphs [5.33024001730262]
我々は、$d$-regular graphで定義されたネットワーク上の確率と通信するエージェントに対して、分散マルチエージェントのマルチアームバンディット問題について検討する。
エージェントベースの手法がグループ後悔の最小化にどのように貢献するかを解析し、新しいアッパー信頼境界(UCB)に基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-16T04:53:54Z) - Neural Thompson Sampling [94.82847209157494]
本稿では,ニューラルトンプソンサンプリング(Neural Thompson Smpling)と呼ばれる新しいアルゴリズムを提案する。
我々のアルゴリズムの中核は報酬の新たな後部分布であり、その平均はニューラルネットワーク近似器であり、その分散は対応するニューラルネットワークのニューラル・タンジェントな特徴に基づいて構築されている。
論文 参考訳（メタデータ） (2020-10-02T07:44:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。