論文の概要: Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2404.19292v1
- Date: Tue, 30 Apr 2024 06:48:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-01 15:14:12.844222
- Title: Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning
- Title(参考訳): 多エージェント強化学習のための確率的情報指向サンプリングアルゴリズム
- Authors: Qiaosheng Zhang, Chenjia Bai, Shuyue Hu, Zhen Wang, Xuelong Li,
- Abstract要約: 本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。
エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。
我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
- 参考スコア(独自算出の注目度): 50.92957910121088
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS). These algorithms draw inspiration from foundational concepts in information theory, and are proven to be sample efficient in MARL settings such as two-player zero-sum Markov games (MGs) and multi-player general-sum MGs. For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. The basic algorithm, referred to as MAIDS, employs an asymmetric learning structure where the max-player first solves a minimax optimization problem based on the joint information ratio of the joint policy, and the min-player then minimizes the marginal information ratio with the max-player's policy fixed. Theoretical analyses show that it achieves a Bayesian regret of tilde{O}(sqrt{K}) for K episodes. To reduce the computational load of MAIDS, we develop an improved algorithm called Reg-MAIDS, which has the same Bayesian regret bound while enjoying less computational complexity. Moreover, by leveraging the flexibility of IDS principle in choosing the learning target, we propose two methods for constructing compressed environments based on rate-distortion theory, upon which we develop an algorithm Compressed-MAIDS wherein the learning target is a compressed environment. Finally, we extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
- Abstract(参考訳): 本研究は,情報指向サンプリング(IDS)の原理に基づいて,マルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。
これらのアルゴリズムは情報理論の基本概念からインスピレーションを得ており、2プレイヤーのゼロサムマルコフゲーム(MG)やマルチプレイヤーのジェネラルサムMGなどのMARL設定においてサンプリング効率が良いことが証明されている。
エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。
MAIDSと呼ばれる基本的なアルゴリズムは非対称な学習構造を用いており、そこでは、まず、最大プレイヤが結合ポリシーのジョイント情報比に基づいて最小マックス最適化問題を解き、最小プレイヤは最大プレイヤのポリシーを固定した限界情報比を最小化する。
理論的解析により,K エピソードに対する tilde{O}(sqrt{K}) のベイズ的後悔が達成された。
MAIDSの計算負荷を低減するため,計算複雑性の少ないベイズ的後悔境界を持つReg-MAIDSアルゴリズムを開発した。
さらに, 学習対象の選択におけるIDS原理の柔軟性を活用し, 速度歪み理論に基づく圧縮環境構築法を提案し, 学習対象が圧縮環境である圧縮・MAIDSアルゴリズムを開発した。
最後に、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明した。
関連論文リスト
- A Learned Proximal Alternating Minimization Algorithm and Its Induced Network for a Class of Two-block Nonconvex and Nonsmooth Optimization [4.975853671529418]
本研究では,学習可能な2ブロック非平滑問題の解法として,一般学習型交互最小化アルゴリズムLPAMを提案する。
提案するLPAM-netはパラメータ効率が高く,いくつかの最先端手法と比較して良好な性能を示す。
論文 参考訳(メタデータ) (2024-11-10T02:02:32Z) - Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning [37.80275600302316]
分布的にロバストなマルコフゲーム (RMG) は、MARLのロバスト性を高めるために提案されている。
RMGがマルチ緊急の呪いから逃れられるかどうか。
これは、RMGに対するマルチ緊急の呪いを破る最初のアルゴリズムである。
論文 参考訳(メタデータ) (2024-09-30T08:09:41Z) - Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳(メタデータ) (2023-10-10T01:39:04Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳(メタデータ) (2023-04-12T14:51:47Z) - A Unifying Multi-sampling-ratio CS-MRI Framework With Two-grid-cycle
Correction and Geometric Prior Distillation [7.643154460109723]
本稿では,モデルベースと深層学習に基づく手法の利点を融合して,深層展開型マルチサンプリング比CS-MRIフレームワークを提案する。
マルチグリッドアルゴリズムにインスパイアされ、まずCS-MRIに基づく最適化アルゴリズムを補正蒸留方式に組み込む。
各段の圧縮サンプリング比から適応的なステップ長と雑音レベルを学習するために条件モジュールを用いる。
論文 参考訳(メタデータ) (2022-05-14T13:36:27Z) - Efficient Model-based Multi-agent Reinforcement Learning via Optimistic
Equilibrium Computation [93.52573037053449]
H-MARL (Hallucinated Multi-Agent Reinforcement Learning) は,環境と数回交流した後の平衡政策を学習する。
自律運転シミュレーションベンチマークにおいて,本手法を実験的に実証した。
論文 参考訳(メタデータ) (2022-03-14T17:24:03Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳(メタデータ) (2021-07-08T18:01:02Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳(メタデータ) (2020-11-18T16:40:45Z) - Online Learning with Cumulative Oversampling: Application to Budgeted
Influence Maximization [7.893654261799925]
オンライン学習のための累積オーバー(CO)手法を提案する。
私たちのキーとなるアイデアは、各ラウンドで一度更新された信念空間からパラメータ推定をサンプリングすることです。
IMの半帯域に対して,我々のCOベースのアルゴリズムは,理論上はUPBベースのアルゴリズムに匹敵する規模の後悔を達成できることを示す。
論文 参考訳(メタデータ) (2020-04-24T19:46:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。