論文の概要: When is Offline Two-Player Zero-Sum Markov Game Solvable?

• arxiv url: http://arxiv.org/abs/2201.03522v1
• Date: Mon, 10 Jan 2022 18:34:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-11 14:46:58.864008
• Title: When is Offline Two-Player Zero-Sum Markov Game Solvable?
• Title（参考訳）: オフライン2人のゼロサムマルコフゲームはいつ解決できるのか?
• Authors: Qiwen Cui and Simon S. Du
• Abstract要約: オフライン2プレイヤーゼロサムマルコフゲームにおいて,ナッシュ均衡(NE)戦略を学習するには単一戦略集中仮定が不十分であることを示す。 本稿では,一方向集中という新しい仮定を提案し,この仮定の下で有効である悲観型アルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 48.34563955829649
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study what dataset assumption permits solving offline two-player zero-sum Markov game. In stark contrast to the offline single-agent Markov decision process, we show that the single strategy concentration assumption is insufficient for learning the Nash equilibrium (NE) strategy in offline two-player zero-sum Markov games. On the other hand, we propose a new assumption named unilateral concentration and design a pessimism-type algorithm that is provably efficient under this assumption. In addition, we show that the unilateral concentration assumption is necessary for learning an NE strategy. Furthermore, our algorithm can achieve minimax sample complexity without any modification for two widely studied settings: dataset with uniform concentration assumption and turn-based Markov game. Our work serves as an important initial step towards understanding offline multi-agent reinforcement learning.
• Abstract（参考訳）: オフライン2人プレイヤゼロサムマルコフゲームの解法について,データセット仮定を用いて検討する。 オフライン単一エージェントマルコフ決定過程とは対照的に,オフライン2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡(NE)戦略の学習には単一戦略集中仮定が不十分であることを示す。 一方,一方向集中という新しい仮定を提案し,この仮定の下で証明可能な悲観的アルゴリズムを設計する。 また,NE戦略の学習には一方的な濃度仮定が必要であることを示す。 さらに,本アルゴリズムは,一様濃度を仮定したデータセットとターンベースのマルコフゲームという,広く研究されている2つの設定を修正せずに,ミニマックスサンプル複雑性を実現することができる。 私たちの仕事は、オフラインマルチエージェント強化学習を理解するための重要な最初のステップとして役立ちます。

関連論文リスト

• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。 我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。 提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
  論文  参考訳（メタデータ） (2023-02-07T18:47:48Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。 マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
  論文  参考訳（メタデータ） (2023-02-06T05:22:27Z)
• Decentralized model-free reinforcement learning in stochastic games with average-reward objective [1.9852463786440127]
  本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。 本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
  論文  参考訳（メタデータ） (2023-01-13T15:59:53Z)
• 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)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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