論文の概要: A Decentralized Policy with Logarithmic Regret for a Class of
Multi-Agent Multi-Armed Bandit Problems with Option Unavailability
Constraints and Stochastic Communication Protocols
- arxiv url: http://arxiv.org/abs/2003.12968v2
- Date: Tue, 31 Mar 2020 04:29:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-18 13:23:56.545954
- Title: A Decentralized Policy with Logarithmic Regret for a Class of
Multi-Agent Multi-Armed Bandit Problems with Option Unavailability
Constraints and Stochastic Communication Protocols
- Title（参考訳）: 選択不能制約と確率的通信プロトコルを有するマルチエージェントバンディット問題に対する対数的後悔を伴う分散政策
- Authors: Pathmanathan Pankayaraj, D. H. S. Maithripala, and J. M. Berg
- Abstract要約: 本稿では,複数の移動体エージェントが,帯域幅と呼ばれる空間分散プロセスの集合からサンプリングして報酬を受け取る,マルチアーム・バンディット(MAB)問題について考察する。
目標は、すべてのエージェントに対する総累積報酬を最大化するために、オプションの可用性とエージェント間通信の制約を条件として、各エージェントに対して分散されたポリシーを定式化することである。
我々の知る限り、これは通信制約のある非完全連結空間グラフに対する、このような分散化ポリシーとしては初めてのものである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers a multi-armed bandit (MAB) problem in which multiple
mobile agents receive rewards by sampling from a collection of spatially
dispersed stochastic processes, called bandits. The goal is to formulate a
decentralized policy for each agent, in order to maximize the total cumulative
reward over all agents, subject to option availability and inter-agent
communication constraints. The problem formulation is motivated by applications
in which a team of autonomous mobile robots cooperates to accomplish an
exploration and exploitation task in an uncertain environment. Bandit locations
are represented by vertices of the spatial graph. At any time, an agent's
option consist of sampling the bandit at its current location, or traveling
along an edge of the spatial graph to a new bandit location. Communication
constraints are described by a directed, non-stationary, stochastic
communication graph. At any time, agents may receive data only from their
communication graph in-neighbors. For the case of a single agent on a fully
connected spatial graph, it is known that the expected regret for any optimal
policy is necessarily bounded below by a function that grows as the logarithm
of time. A class of policies called upper confidence bound (UCB) algorithms
asymptotically achieve logarithmic regret for the classical MAB problem. In
this paper, we propose a UCB-based decentralized motion and option selection
policy and a non-stationary stochastic communication protocol that guarantee
logarithmic regret. To our knowledge, this is the first such decentralized
policy for non-fully connected spatial graphs with communication constraints.
When the spatial graph is fully connected and the communication graph is
stationary, our decentralized algorithm matches or exceeds the best reported
prior results from the literature.
- Abstract（参考訳）: 本稿では,複数の移動エージェントがバンディットと呼ばれる空間分散確率過程の集合からサンプリングして報奨を受けるマルチアームバンディット(mab)問題について考察する。
目標は、オプションの可用性とエージェント間通信の制約により、すべてのエージェントに対する合計累積報酬を最大化するために、各エージェントに対して分散ポリシーを定式化することである。
問題定式化は、自律移動ロボットチームが不確実な環境で探索と搾取を行うために協力するアプリケーションによって動機付けられている。
バンディットの位置は空間グラフの頂点によって表される。
エージェントのオプションはいつでも、現在の位置でバンドイットをサンプリングするか、空間グラフの端に沿って新しいバンドイットの位置へ移動する。
通信制約は、非定常確率的通信グラフによって記述される。
エージェントはいつでも、隣の通信グラフからのみデータを受け取ることができる。
完全に連結された空間グラフ上の単一のエージェントの場合、任意の最適ポリシーに対する期待された後悔は、時間対数として成長する関数によって必ず下界されることが知られている。
高信頼バウンド(UCB)アルゴリズムと呼ばれる一連のポリシーは、古典的MAB問題に対する対数的後悔を漸近的に達成する。
本稿では,UDBに基づく分散動作とオプション選択ポリシーと,対数的後悔を保証する非定常確率的通信プロトコルを提案する。
我々の知る限り、これは通信制約のある非完全連結空間グラフに対する最初の分散ポリシーである。
空間グラフが完全接続され、通信グラフが定常である場合、分散アルゴリズムは文献から報告された最良の先行結果と一致するか、または上回る。
関連論文リスト
- Networked Communication for Mean-Field Games with Function Approximation and Empirical Mean-Field Estimation [59.01527054553122]
分散エージェントは、経験的システムの単一かつ非エポゾディックな実行から平均フィールドゲームにおける平衡を学ぶことができる。
既存の設定に関数近似を導入し,Munchausen Online Mirror Descent 方式で描画する。
また, エージェントが局所的な周辺地域に基づいて, グローバルな経験分布を推定できる新しいアルゴリズムも提供する。
論文 参考訳（メタデータ） (2024-08-21T13:32:46Z) - Distributed Optimization via Kernelized Multi-armed Bandits [6.04275169308491]
分散最適化問題を異種報酬設定によるマルチエージェントカーネル化されたマルチアームバンディット問題としてモデル化する。
我々は,カーネルの一般的なクラスに対して,サブ線形なリフレッシュバウンドを実現するために,完全に分散化されたアルゴリズムであるマルチエージェントIGP-UCB(MA-IGP-UCB)を提案する。
また,Multi-agent Delayed IGP-UCB (MAD-IGP-UCB)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-07T21:57:48Z) - RGMComm: Return Gap Minimization via Discrete Communications in
Multi-Agent Reinforcement Learning [33.86277578441437]
マルコフ決定過程における協調的マルチエージェント強化学習課題の解決には,コミュニケーションが不可欠である。
本稿では、離散メッセージ生成関数の驚くほど単純な設計であるReturn-Gap-Minimization Communication (RGMComm)アルゴリズムを提案する。
評価の結果、RGMCommは最先端のマルチエージェント通信ベースラインを大きく上回っている。
論文 参考訳（メタデータ） (2023-08-07T07:26:55Z) - Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs [49.71319907864573]
本稿では,分解が容易なマルチエージェントスキル発見法を提案する。
我々のキーとなる考え方は、合同状態空間をクロネッカーグラフとして近似することであり、そのフィドラーベクトルを直接見積もることができる。
ラプラシアンスペクトルを直接計算することは、無限大の状態空間を持つタスクには難易度が高いことを考慮し、さらに本手法の深層学習拡張を提案する。
論文 参考訳（メタデータ） (2023-07-21T14:53:12Z) - QuTE: decentralized multiple testing on sensor networks with false
discovery rate control [130.7122910646076]
本稿では、偽発見率(FDR)の証明可能な保証を備えたグラフ上での分散多重仮説検定法を設計する。
異なるエージェントが無向グラフのノードに存在し、各エージェントはそのノードに局所的な1つ以上の仮説に対応するp値を持つ。
各エージェントは、グラフ全体の大域的FDRが予め定義されたレベルで制御されなければならないという共同目的のもと、隣人とのみ通信することで、それぞれのローカル仮説の1つ以上の拒絶を個別に決めなければならない。
論文 参考訳（メタデータ） (2022-10-09T19:48:39Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Decentralized Optimization Over the Stiefel Manifold by an Approximate
Augmented Lagrangian Function [7.768673476492471]
本稿では、スティーフェル多様体上の分散最適化問題に焦点をあてる。
エージェントは、この問題を解決するための共同作業において、隣人としか通信できない。
既存の方法では、収束を保証するために複数の通信ラウンドが必要である。
本稿では,DESTINYと呼ばれる分散化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-30T07:19:59Z) - Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
本研究では,コミュニケーション制約下での運用を目的とした適応型分散学習戦略について検討する。
我々は,ストリーミングデータの連続的な観察から,オンライン最適化問題を解決しなければならないエージェントのネットワークを考える。
論文 参考訳（メタデータ） (2021-12-03T19:23:48Z) - 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) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Dimension-Free Rates for Natural Policy Gradient in Multi-Agent
Reinforcement Learning [22.310861786709538]
協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。
このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
論文 参考訳（メタデータ） (2021-09-23T23:38:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。