論文の概要: Collaborative Multi-agent Stochastic Linear Bandits
- arxiv url: http://arxiv.org/abs/2205.06331v1
- Date: Thu, 12 May 2022 19:46:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 01:48:55.495069
- Title: Collaborative Multi-agent Stochastic Linear Bandits
- Title(参考訳): 協調型マルチエージェント確率線形帯域
- Authors: Ahmadreza Moradipari, Mohammad Ghavamzadeh, and Mahnoosh Alizadeh
- Abstract要約: 我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
- 参考スコア(独自算出の注目度): 28.268809091816287
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a collaborative multi-agent stochastic linear bandit setting, where
$N$ agents that form a network communicate locally to minimize their overall
regret. In this setting, each agent has its own linear bandit problem (its own
reward parameter) and the goal is to select the best global action w.r.t. the
average of their reward parameters. At each round, each agent proposes an
action, and one action is randomly selected and played as the network action.
All the agents observe the corresponding rewards of the played actions and use
an accelerated consensus procedure to compute an estimate of the average of the
rewards obtained by all the agents. We propose a distributed upper confidence
bound (UCB) algorithm and prove a high probability bound on its $T$-round
regret in which we include a linear growth of regret associated with each
communication round. Our regret bound is of order
$\mathcal{O}\Big(\sqrt{\frac{T}{N \log(1/|\lambda_2|)}}\cdot (\log T)^2\Big)$,
where $\lambda_2$ is the second largest (in absolute value) eigenvalue of the
communication matrix.
- Abstract(参考訳): 我々は,ネットワークを形成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント確率線形帯域設定について検討した。
この設定では、各エージェントは独自の線形バンディット問題(それ自体は報酬パラメータ)を持ち、ゴールは報酬パラメータの平均値として最高のグローバルアクションw.r.tを選択することである。
各ラウンドで各エージェントがアクションを提案し、1つのアクションがランダムに選択され、ネットワークアクションとして再生される。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
本稿では,分散上信頼度境界(UCB)アルゴリズムを提案し,各通信ラウンドに関連付けられた後悔の線形成長を含む,T$ラウンドの後悔に基づく高い確率を証明した。
我々の後悔は、$\mathcal{o}\big(\sqrt{\frac{t}{n \log(1/|\lambda_2|)}}\cdot (\log t)^2\big)$という順序である。
関連論文リスト
- Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis [5.02063914741425]
Zhang, Johansson, Li が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。
上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔が$O(Nlog(T)[sqrtKT + DK])$で束縛されていることを証明した。
論文 参考訳(メタデータ) (2024-01-18T21:36:17Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳(メタデータ) (2023-05-30T16:05:44Z) - 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) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳(メタデータ) (2022-03-29T15:27:13Z) - Cooperative Online Learning in Stochastic and Adversarial MDPs [50.62439652257712]
我々は、協調的オンライン学習と敵対的マルコフ決定過程(MDP)について研究する。
各エピソードでは、$m$エージェントが同時にMDPと対話し、個人の後悔を最小限に抑えるために情報を共有する。
協調強化学習(RL)を非フレッシュランダム性, あるいは敵対的MDPで検討したのは, 初めてである。
論文 参考訳(メタデータ) (2022-01-31T12:32:11Z) - 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) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳(メタデータ) (2021-12-13T09:48:54Z) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。