論文の概要: Decentralized Multi-Agent Linear Bandits with Safety Constraints
- arxiv url: http://arxiv.org/abs/2012.00314v1
- Date: Tue, 1 Dec 2020 07:33:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-30 20:05:02.316836
- Title: Decentralized Multi-Agent Linear Bandits with Safety Constraints
- Title（参考訳）: 安全制約のある分散マルチエージェント線形バンディット
- Authors: Sanae Amani, Christos Thrampoulidis
- Abstract要約: 本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。
ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。
私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
- 参考スコア（独自算出の注目度）: 31.67685495996986
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study decentralized stochastic linear bandits, where a network of $N$
agents acts cooperatively to efficiently solve a linear bandit-optimization
problem over a $d$-dimensional space. For this problem, we propose DLUCB: a
fully decentralized algorithm that minimizes the cumulative regret over the
entire network. At each round of the algorithm each agent chooses its actions
following an upper confidence bound (UCB) strategy and agents share information
with their immediate neighbors through a carefully designed consensus procedure
that repeats over cycles. Our analysis adjusts the duration of these
communication cycles ensuring near-optimal regret performance
$\mathcal{O}(d\log{NT}\sqrt{NT})$ at a communication rate of
$\mathcal{O}(dN^2)$ per round. The structure of the network affects the regret
performance via a small additive term - coined the regret of delay - that
depends on the spectral gap of the underlying graph. Notably, our results apply
to arbitrary network topologies without a requirement for a dedicated agent
acting as a server. In consideration of situations with high communication
cost, we propose RC-DLUCB: a modification of DLUCB with rare communication
among agents. The new algorithm trades off regret performance for a
significantly reduced total communication cost of $\mathcal{O}(d^3N^{2.5})$
over all $T$ rounds. Finally, we show that our ideas extend naturally to the
emerging, albeit more challenging, setting of safe bandits. For the recently
studied problem of linear bandits with unknown linear safety constraints, we
propose the first safe decentralized algorithm. Our study contributes towards
applying bandit techniques in safety-critical distributed systems that
repeatedly deal with unknown stochastic environments. We present numerical
simulations for various network topologies that corroborate our theoretical
findings.
- Abstract（参考訳）: 本研究では,n$エージェントのネットワークが協調して作用し,d$次元空間上の線形バンディット最適化問題を効率的に解く分散確率的線形バンディットについて検討する。
そこで本研究では,ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズムDLUCBを提案する。
アルゴリズムの各ラウンドにおいて、各エージェントは、uper confidence bound(ucb)戦略に従ってそのアクションを選択し、エージェントは、サイクルを繰り返す注意深く設計されたコンセンサス手順を通じて情報を共有する。
提案手法は,1ラウンドあたり$\mathcal{o}(dn^2)$の通信速度で,ほぼ最適の後悔性能である$\mathcal{o}(d\log{nt}\sqrt{nt})$を保証する。
ネットワークの構造は、基礎となるグラフのスペクトルギャップに依存する小さな加算項(遅延の後悔)を通して、後悔のパフォーマンスに影響を与える。
特に,サーバとして機能する専用エージェントを必要とせず,任意のネットワークトポロジに適用した。
通信コストの高い状況を考慮して,DLUCBとエージェント間の通信が希少であるRC-DLUCBを提案する。
新しいアルゴリズムは、すべてのT$ラウンドで$\mathcal{O}(d^3N^{2.5})$の通信コストを大幅に削減するために、後悔のパフォーマンスをトレードオフする。
そして最後に、私たちのアイデアが、より困難ではあるが、より安全な盗賊の設定へと自然に広がることを示す。
線形安全制約が未知な線形バンディットの最近研究された問題に対して,我々は最初の安全な分散アルゴリズムを提案する。
本研究は,未知の確率環境に繰り返し対処する安全クリティカル分散システムにおける帯域幅技術の適用に寄与する。
理論的な知見を裏付ける様々なネットワークトポロジーの数値シミュレーションを提案する。
関連論文リスト
- 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) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - 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) - 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) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳（メタデータ） (2022-02-03T21:19:36Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳（メタデータ） (2020-11-05T05:16:04Z) - Bayesian Algorithms for Decentralized Stochastic Bandits [12.350564981588063]
我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。
我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。
目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
論文 参考訳（メタデータ） (2020-10-20T19:14:20Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。