論文の概要: Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2512.00351v1
• Date: Sat, 29 Nov 2025 06:44:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.188604
• Title: Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning
• Title（参考訳）: モデルレス強化学習のための確率記憶効率の良いセルフプレイアルゴリズム
• Authors: Na Li, Yuchen Jiao, Hangguan Shan, Shefeng Yan,
• Abstract要約: モデルフリーなセルフプレイアルゴリズムであるemphMemory-Efficient Nash Q-Learning (ME-Nash-QL) を2プレイヤーゼロサムマルコフゲーム向けに設計する。 ME-Nash-QLはマルコフポリシーを維持しながら、最小の計算複雑性$O(Tmathrmpoly(H))$を達成する。 また、最高のバーンインコストである$O(SAB,mathrmpoly(H))$を達成する一方、以前のアルゴリズムは少なくとも$O(S3 AB,mathrm)のバーンインコストを持つ。
• 参考スコア（独自算出の注目度）: 16.345627491866527
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The thriving field of multi-agent reinforcement learning (MARL) studies how a group of interacting agents make decisions autonomously in a shared dynamic environment. Existing theoretical studies in this area suffer from at least two of the following obstacles: memory inefficiency, the heavy dependence of sample complexity on the long horizon and the large state space, the high computational complexity, non-Markov policy, non-Nash policy, and high burn-in cost. In this work, we take a step towards settling this problem by designing a model-free self-play algorithm \emph{Memory-Efficient Nash Q-Learning (ME-Nash-QL)} for two-player zero-sum Markov games, which is a specific setting of MARL. ME-Nash-QL is proven to enjoy the following merits. First, it can output an $\varepsilon$-approximate Nash policy with space complexity $O(SABH)$ and sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, where $S$ is the number of states, $\{A, B\}$ is the number of actions for two players, and $H$ is the horizon length. It outperforms existing algorithms in terms of space complexity for tabular cases, and in terms of sample complexity for long horizons, i.e., when $\min\{A, B\}\ll H^2$. Second, ME-Nash-QL achieves the lowest computational complexity $O(T\mathrm{poly}(AB))$ while preserving Markov policies, where $T$ is the number of samples. Third, ME-Nash-QL also achieves the best burn-in cost $O(SAB\,\mathrm{poly}(H))$, whereas previous algorithms have a burn-in cost of at least $O(S^3 AB\,\mathrm{poly}(H))$ to attain the same level of sample complexity with ours.
• Abstract（参考訳）: マルチエージェント強化学習(MARL)の繁栄する分野は、対話エージェントのグループが共有動的環境において自律的に意思決定を行う方法を研究する。 この領域の既存の理論的研究は、メモリ不足、長い地平線と大きな状態空間におけるサンプルの複雑さの重い依存、高い計算複雑性、非マルコフポリシー、非ナッシュポリシー、高燃焼コストの少なくとも2つの障害に悩まされている。 本研究では,MARL の具体的設定である 2 つのプレイヤーゼロサムマルコフゲームに対して,モデルフリーな自己再生アルゴリズム \emph{Memory-Efficient Nash Q-Learning (ME-Nash-QL)} を設計することで,この問題を解決しようとする。 ME-Nash-QLは以下のメリットを享受できることが証明されている。 まず、$\varepsilon$-approximate Nash Policy with space complexity $O(SABH)$ and sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, $S$ is the number of state, $\{A, B\}$ is the number of action for two players, $H$ is the horizon length。 グラフの場合の空間複雑性や、長い地平線の場合のサンプル複雑性、すなわち$\min\{A, B\}\ll H^2$の場合には、既存のアルゴリズムよりも優れる。 次に、ME-Nash-QLは、Markovポリシーを保ちながら、最小の計算複雑性$O(T\mathrm{poly}(AB))$を達成します。 第3に、ME-Nash-QLは、最高のバーンインコストである$O(SAB\,\mathrm{poly}(H))$も達成しますが、以前のアルゴリズムでは、同じレベルのサンプル複雑性を達成するために、少なくとも$O(S^3 AB\,\mathrm{poly}(H))$を持っています。

関連論文リスト

• Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models [34.196233651364615]
  ガウス分布に基づく実数値マルチインデックスモデル(MIM)の学習の複雑さについて検討する。 K$-MIM は関数 $f:mathbbRdto mathbbR$ であり、入力の$K$-次元部分空間への射影のみに依存する。 逆ラベルノイズが存在する場合でも, 正方形損失に対して幅広いMIMを学習するための一般アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-27T17:47:26Z)
• Minimax-Optimal Multi-Agent Robust Reinforcement Learning [7.237817437521988]
  我々は、生成モデルへのアクセスを前提として、Q-FTRLアルゴリズム citepli2022minimax を有限水平設定で RMG に拡張する。 提案アルゴリズムは$varepsilon$-robust coarse correlation equilibrium (CCE) を$widetildeOleft(H3Ssum_i=1mA_iminleftH,1/Rright/varepsilon2right) のサンプル複雑性(ログファクタまで)で達成している。
  論文  参考訳（メタデータ） (2024-12-27T16:37:33Z)
• Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
  平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。 直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T12:24:14Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)
• 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)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

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

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