論文の概要: Towards General Function Approximation in Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2107.14702v1
• Date: Fri, 30 Jul 2021 15:25:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-02 13:06:04.176842
• Title: Towards General Function Approximation in Zero-Sum Markov Games
• Title（参考訳）: ゼロサムマルコフゲームにおける一般関数近似に向けて
• Authors: Baihe Huang and Jason D. Lee and Zhaoran Wang and Zhuoran Yang
• Abstract要約: 本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
• 参考スコア（独自算出の注目度）: 126.58493169301012
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. The study focuses on the challenging settings where the value function or the model is parameterized by general function classes. Provably efficient algorithms for both decoupled and {coordinated} settings are developed. In the {decoupled} setting where the agent controls a single player and plays against an arbitrary opponent, we propose a new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension -- a new dimension of the function class in Markov games. As a special case, this method improves the state-of-the-art algorithm by a $\sqrt{d}$ factor in the regret when the reward function and transition kernel are parameterized with $d$-dimensional linear features. In the {coordinated} setting where both players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can be bounded by a generalization of Witness rank to Markov games. The model-free algorithm enjoys a $\sqrt{K}$-regret upper bound where $K$ is the number of episodes. Our algorithms are based on new techniques of alternate optimism.
• Abstract（参考訳）: 本稿では,同時移動を伴う2プレイヤーゼロサム有限ホライゾンマルコフゲームについて考察する。 この研究は、値関数やモデルが一般的な関数クラスによってパラメータ化される困難な設定に焦点を当てている。 疎結合と {coordinated} 設定の両方の効率的なアルゴリズムが開発されている。 エージェントが1人のプレイヤーを制御し、任意の相手と対戦する {decoupled} 設定において、新しいモデルフリーアルゴリズムを提案する。 サンプル複雑性は、マルコフゲームにおける関数クラスの新しい次元であるミニマックスエルダー次元によって支配される。 特別な場合として、この手法は、報奨関数と遷移核が$d$次元の線形特徴でパラメータ化されている場合の後悔における$\sqrt{d}$ factorによって最先端アルゴリズムを改善する。 双方のプレイヤーがエージェントによって制御される {coordinated} の設定では、モデルベースアルゴリズムとモデルフリーアルゴリズムを提案する。 モデルに基づくアルゴリズムでは、サンプルの複雑さはマルコフゲームへのウィットネスランクの一般化によって制限できることを示す。 モデルなしのアルゴリズムは、$\sqrt{K}$-regret上界を楽しみ、$K$はエピソードの数である。 我々のアルゴリズムは新しい楽観主義の手法に基づいている。

関連論文リスト

• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
  論文  参考訳（メタデータ） (2023-08-17T08:34:58Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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