論文の概要: Distributed Consensus Algorithm for Decision-Making in Multi-agent
Multi-armed Bandit
- arxiv url: http://arxiv.org/abs/2306.05998v1
- Date: Fri, 9 Jun 2023 16:10:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 12:43:00.274344
- Title: Distributed Consensus Algorithm for Decision-Making in Multi-agent
Multi-armed Bandit
- Title(参考訳): マルチエージェントマルチアームバンドにおける意思決定のための分散コンセンサスアルゴリズム
- Authors: Xiaotong Cheng, Setareh Maghsudi
- Abstract要約: 動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。
グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。
目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
- 参考スコア(独自算出の注目度): 7.708904950194129
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a structured multi-agent multi-armed bandit (MAMAB) problem in a
dynamic environment. A graph reflects the information-sharing structure among
agents, and the arms' reward distributions are piecewise-stationary with
several unknown change points. The agents face the identical
piecewise-stationary MAB problem. The goal is to develop a decision-making
policy for the agents that minimizes the regret, which is the expected total
loss of not playing the optimal arm at each time step. Our proposed solution,
Restarted Bayesian Online Change Point Detection in Cooperative Upper
Confidence Bound Algorithm (RBO-Coop-UCB), involves an efficient multi-agent
UCB algorithm as its core enhanced with a Bayesian change point detector. We
also develop a simple restart decision cooperation that improves
decision-making. Theoretically, we establish that the expected group regret of
RBO-Coop-UCB is upper bounded by $\mathcal{O}(KNM\log T + K\sqrt{MT\log T})$,
where K is the number of agents, M is the number of arms, and T is the number
of time steps. Numerical experiments on synthetic and real-world datasets
demonstrate that our proposed method outperforms the state-of-the-art
algorithms.
- Abstract(参考訳): 動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。
グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。
エージェントは同じ部分的なmab問題に直面します。
目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
提案手法であるRestarted Bayesian Online Change Point Detection in Cooperative Upper Confidence Bound Algorithm (RBO-Coop-UCB) は,ベイジアン変化点検出器で強化されたコアとして,効率的なマルチエージェント UCB アルゴリズムを含む。
また,意思決定を改善するための簡単な再起動決定協調も開発した。
理論的には、RBO-Coop-UCB の期待された群後悔は $\mathcal{O}(KNM\log T + K\sqrt{MT\log T})$ で上界であると証明する。
合成および実世界のデータセットに関する数値実験により,提案手法が最先端のアルゴリズムより優れていることを示す。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Decentralised Q-Learning for Multi-Agent Markov Decision Processes with
a Satisfiability Criterion [0.0]
マルチエージェントマルコフ決定過程(MMDP)を解決するための強化学習アルゴリズムを提案する。
目標は、各エージェントの時間平均コストを、指定されたエージェント固有のバウンド以下にすることである。
論文 参考訳(メタデータ) (2023-11-21T13:56:44Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳(メタデータ) (2023-05-01T06:46:22Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳(メタデータ) (2023-04-01T15:50:18Z) - A Reduction-based Framework for Sequential Decision Making with Delayed
Feedback [53.79893086002961]
汎用マルチエージェントシーケンシャル意思決定における遅延フィードバックについて検討する。
本稿では, 逐次的意思決定のためのマルチバッチアルゴリズムを, 即時フィードバックにより, サンプル効率のよいアルゴリズムに変換する, 新たなリダクションベースフレームワークを提案する。
論文 参考訳(メタデータ) (2023-02-03T01:16:09Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Reinforcement Learning for Finite-Horizon Restless Multi-Armed
Multi-Action Bandits [8.136957953239254]
本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。
各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。
最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
論文 参考訳(メタデータ) (2021-09-20T21:40:12Z) - Bayesian Algorithms for Decentralized Stochastic Bandits [12.350564981588063]
我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。
我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。
目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
論文 参考訳(メタデータ) (2020-10-20T19:14:20Z) - Kernel Methods for Cooperative Multi-Agent Contextual Bandits [15.609414012418043]
協調的マルチエージェント意思決定は、遅延のあるネットワーク上で通信しながら、学習問題を協調的に解決するエージェントのグループを含む。
エージェントが得られる報酬は、関連するカーネル再生ヒルベルト空間(RKHS)におけるコンテキストのイメージの任意の線形関数である。
我々は, 年齢ごとの後悔に対して, ほぼ最適境界を与えるアルゴリズムであるtextscCoop- KernelUCBを提案する。
論文 参考訳(メタデータ) (2020-08-14T07:37:44Z) - Distributed Cooperative Decision Making in Multi-agent Multi-armed
Bandits [6.437761597996503]
複数のエージェントが同じバンディット(MAB)に直面している分散意思決定問題について検討する。
我々は,各アームの平均報酬を協調的に推定するための動的,コンセンサスに基づく分散推定アルゴリズムを設計する。
両アルゴリズムが中心核融合センターの性能に近いグループ性能を達成することを示す。
論文 参考訳(メタデータ) (2020-03-03T03:20:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。