論文の概要: Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2102.07404v1
• Date: Mon, 15 Feb 2021 09:09:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-16 15:55:38.675910
• Title: Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた2プレイヤーマルコフゲームに対する近似最適アルゴリズム
• Authors: Zixiang Chen and Dongruo Zhou and Quanquan Gu
• Abstract要約: 同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
• 参考スコア（独自算出の注目度）: 92.99933928528797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves in the finite-horizon setting, where the transition kernel of the underlying Markov games can be parameterized by a linear function over the current state, both players' actions and the next state. In particular, we assume that we can control both players and aim to find the Nash Equilibrium by minimizing the duality gap. We propose an algorithm Nash-UCRL-VTR based on the principle "Optimism-in-Face-of-Uncertainty". Our algorithm only needs to find a Coarse Correlated Equilibrium (CCE), which is computationally very efficient. Specifically, we show that Nash-UCRL-VTR can provably achieve an $\tilde{O}(dH\sqrt{T})$ regret, where $d$ is the linear function dimension, $H$ is the length of the game and $T$ is the total number of steps in the game. To access the optimality of our algorithm, we also prove an $\tilde{\Omega}( dH\sqrt{T})$ lower bound on the regret. Our upper bound matches the lower bound up to logarithmic factors, which suggests the optimality of our algorithm.
• Abstract（参考訳）: 基本となるマルコフゲームの遷移カーネルを,現在の状態,プレイヤーの行動,次の状態の線型関数でパラメータ化することができる,有限水平設定における同時移動による2プレイヤーゼロサムマルコフゲームの強化学習について検討する。 特に、両プレイヤーを制御でき、双対性ギャップを最小化してナッシュ平衡を求めることができると仮定する。 本論文では, "Optimism-in-Face-of-Uncertainty" の原理に基づくアルゴリズム Nash-UCRL-VTR を提案する。 我々のアルゴリズムは、計算的に非常に効率的である粗相関平衡(CCE)を見つける必要がある。 具体的には,Nash-UCRL-VTR が$\tilde{O}(dH\sqrt{T})$ regret を確実に達成できることを示し,$d$ は線形関数次元,$H$ はゲームの長さ,$T$ はゲームのステップの総数である。 アルゴリズムの最適性にアクセスするために、後悔に対して$\tilde{\Omega}(dH\sqrt{T})$ローバウンドを証明した。 我々の上限は対数因子に対する下限に一致し、アルゴリズムの最適性が示唆される。

関連論文リスト

• 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)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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