論文の概要: Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium

• arxiv url: http://arxiv.org/abs/2208.05363v1
• Date: Wed, 10 Aug 2022 14:21:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-11 12:24:22.899515
• Title: Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium
• Title（参考訳）: 2人混合マルコフゲームを学ぶ:カーネル関数近似と相関平衡
• Authors: Chris Junchi Li, Dongruo Zhou, Quanquan Gu, Michael I. Jordan
• Abstract要約: 非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 157.0902680672422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation, where the action-value function is approximated by a function in a Reproducing Kernel Hilbert Space (RKHS). The key challenge is how to do exploration in the high-dimensional function space. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap. At the core of our algorithms are upper and lower confidence bounds that are derived based on the principle of optimism in the face of uncertainty. We prove that our algorithm is able to attain an $O(\sqrt{T})$ regret with polynomial computational complexity, under very mild assumptions on the reward function and the underlying dynamic of the Markov Games. We also propose several extensions of our algorithm, including an algorithm with Bernstein-type bonus that can achieve a tighter regret bound, and another algorithm for model misspecification that can be applied to neural function approximation.
• Abstract（参考訳）: 非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討し、そこでは、アクション値関数を再生ケルネルヒルベルト空間(RKHS)内の関数で近似する。 鍵となる課題は高次元関数空間での探索方法である。 双対性ギャップを最小化することでnash平衡を求める新しいオンライン学習アルゴリズムを提案する。 我々のアルゴリズムの中核は、不確実性に直面した楽観主義の原理に基づいて導出される上下の信頼境界である。 我々のアルゴリズムは、報酬関数とマルコフゲームの基礎となる力学に関する非常に穏やかな仮定の下で、多項式計算の複雑さで$O(\sqrt{T})$後悔を達成できることを示す。 我々はまた,より厳密な後悔境界を達成できるベルンシュタイン型ボーナス付きアルゴリズムや,ニューラル関数近似に適用可能なモデルミス特定のためのアルゴリズムなど,アルゴリズムの拡張についても提案する。

関連論文リスト

• Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games [31.554420227087043]
  そこで本稿では,関数近似を用いた2時間スムーズなQ$学習アルゴリズムを提案する。 2時間スケールの$Q$ラーニングでは、高速スケールは勾配降下に精力的に更新され、より遅いスケールは、前回と最新の高速スケールのコンベックスを組み合わせて更新される。 重要な新規性は、遅い時間スケールの進化を捉えるために有効なリャプノフ函数を構築することである。
  論文  参考訳（メタデータ） (2023-12-08T08:39:36Z)
• 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)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
  本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。 我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
  論文  参考訳（メタデータ） (2022-05-27T03:24:12Z)
• 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)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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