論文の概要: Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

• arxiv url: http://arxiv.org/abs/2002.07066v3
• Date: Tue, 23 Jun 2020 21:09:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 12:43:29.526687
• Title: Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Title（参考訳）: 関数近似と相関平衡を用いたゼロサム同時モーブマルコフゲーム学習
• Authors: Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang
• Abstract要約: 両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
• 参考スコア（独自算出の注目度）: 116.56359444619441
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an $\tilde O(\sqrt{d^3 H^3 T} )$ upper bound on the duality gap and regret, where $d$ is the linear dimension, $H$ the horizon and $T$ the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash Equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right.
• Abstract（参考訳）: 同時動作のゼロサム有限ホライゾンマルコフゲームに対して,効率的な強化学習アルゴリズムを開発した。 関数近似を組み込むために、報酬関数と遷移カーネルが線形構造を持つマルコフゲーム群を考える。 問題のオフライン設定とオンライン設定の両方が考慮されている。 オフライン環境では,両プレイヤーを制御し,双対性ギャップを最小化することでナッシュ均衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。 どちらの設定でも最小二乗最小値反復アルゴリズムの楽観的変種を提案する。 このアルゴリズムは計算効率が良く、双対性ギャップと後悔において$\tilde o(\sqrt{d^3 h^3 t} )$上限を達成できることを示し、ここで$d$は線形次元、$h$ the horizon、$t$は時間ステップの総数である。 我々の結果はサンプリングモデルに追加の仮定を必要としない。 私たちの設定では、マルコフ決定プロセスやターンベースのマルコフゲームに欠けているいくつかの新しい課題を克服する必要があります。 特に、同時移動による楽観性を達成するために、値関数の上下の信頼境界を構築し、これらの境界をペイオフ行列として一般サム行列ゲームを解くことで楽観的ポリシーを計算する。 一般ゲームにおけるナッシュ平衡の探索は計算が難しいため、我々のアルゴリズムは、効率よく得られる粗相関平衡 (CCE) を解く。 我々の知る限りでは、そのようなCCEに基づく楽観主義のスキームは文献に現れておらず、それ自体が関心を持つかもしれない。

関連論文リスト

• Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning [105.7510838453122]
  制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。 我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。 提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
  論文  参考訳（メタデータ） (2023-05-31T22:09:24Z)
• 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)
• 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)
• 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)

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

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