論文の概要: Minimax-Optimal Multi-Agent Robust Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2412.19873v1
• Date: Fri, 27 Dec 2024 16:37:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:05:34.563193
• Title: Minimax-Optimal Multi-Agent Robust Reinforcement Learning
• Title（参考訳）: Minimax-Optimal Multi-Agent Robust Reinforcement Learning
• Authors: Yuchen Jiao, Gen Li,
• Abstract要約: 我々は、生成モデルへのアクセスを前提として、Q-FTRLアルゴリズム citepli2022minimax を有限水平設定で RMG に拡張する。 提案アルゴリズムは$varepsilon$-robust coarse correlation equilibrium (CCE) を$widetildeOleft(H3Ssum_i=1mA_iminleftH,1/Rright/varepsilon2right) のサンプル複雑性(ログファクタまで)で達成している。
• 参考スコア（独自算出の注目度）: 7.237817437521988
• License:
• Abstract: Multi-agent robust reinforcement learning, also known as multi-player robust Markov games (RMGs), is a crucial framework for modeling competitive interactions under environmental uncertainties, with wide applications in multi-agent systems. However, existing results on sample complexity in RMGs suffer from at least one of three obstacles: restrictive range of uncertainty level or accuracy, the curse of multiple agents, and the barrier of long horizons, all of which cause existing results to significantly exceed the information-theoretic lower bound. To close this gap, we extend the Q-FTRL algorithm \citep{li2022minimax} to the RMGs in finite-horizon setting, assuming access to a generative model. We prove that the proposed algorithm achieves an $\varepsilon$-robust coarse correlated equilibrium (CCE) with a sample complexity (up to log factors) of $\widetilde{O}\left(H^3S\sum_{i=1}^mA_i\min\left\{H,1/R\right\}/\varepsilon^2\right)$, where $S$ denotes the number of states, $A_i$ is the number of actions of the $i$-th agent, $H$ is the finite horizon length, and $R$ is uncertainty level. We also show that this sample compelxity is minimax optimal by combining an information-theoretic lower bound. Additionally, in the special case of two-player zero-sum RMGs, the algorithm achieves an $\varepsilon$-robust Nash equilibrium (NE) with the same sample complexity.
• Abstract（参考訳）: マルチエージェント・ロバスト強化学習(マルチエージェント・ロバスト・マルコフ・ゲーム、マルチエージェント・ロバスト・マルコフ・ゲーム)は、環境不確実性の下での競合相互作用をモデル化するための重要なフレームワークである。 しかしながら、RMGのサンプル複雑性に関する既存の結果は、少なくとも3つの障害の少なくとも1つ、不確実性レベルまたは精度の制限範囲、複数のエージェントの呪い、そして長い水平線の障壁に悩まされており、これら全てが既存の結果が情報理論の下界をはるかに上回っている。 このギャップを埋めるために、生成モデルへのアクセスを想定したQ-FTRLアルゴリズムを有限水平設定でRMGに拡張する。 提案アルゴリズムは,$\varepsilon$-robust coarse equilibrium (CCE) を$\widetilde{O}\left(H^3S\sum_{i=1}^mA_i\min\left\{H,1/R\right\}/\varepsilon^2\right)$のサンプル複雑性(ログファクタまで)で達成している。 また,このサンプルの組合せ性は情報理論の下界を組み合わせることで最小限の最適性を示す。 さらに、2-player 0-sum RMGs の特殊な場合、このアルゴリズムは同じサンプル複雑性を持つ$\varepsilon$-robust Nash equilibrium (NE) を達成する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds [24.571530193140916]
  エントロピーリスク尺度(EntRM)が目的である有限エピソードマルコフ決定過程を考察する。 モデルフリーとモデルベースを含む2つの異なるスキームを用いて最適化を実装する2つの新しいDRLアルゴリズムを提案する。 いずれも$tildemathcalO(fracexp(|beta|H)-1|beta|HsqrtS2AK)$ regret upper bound, where $S$, $A$, $K$, $H$は数値を表す。
  論文  参考訳（メタデータ） (2022-10-25T14:30:48Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。