論文の概要: Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
- arxiv url: http://arxiv.org/abs/2303.02738v1
- Date: Sun, 5 Mar 2023 18:08:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 17:56:22.967633
- Title: Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
- Title(参考訳): 2プレイヤーゼロサムマルコフゲームにおけるアンカップリングと収束学習
- Authors: Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
- Abstract要約: 2プレイヤーゼロサムマルコフゲームにおける学習の問題を再考する。
我々は,非漸近収束率を持つ$uncoupled$,$convergent$,$rational$というアルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 41.80321968944094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of learning in two-player zero-sum Markov games,
focusing on developing an algorithm that is $uncoupled$, $convergent$, and
$rational$, with non-asymptotic convergence rates. We start from the case of
stateless matrix game with bandit feedback as a warm-up, showing an
$\mathcal{O}(t^{-\frac{1}{8}})$ last-iterate convergence rate. To the best of
our knowledge, this is the first result that obtains finite last-iterate
convergence rate given access to only bandit feedback. We extend our result to
the case of irreducible Markov games, providing a last-iterate convergence rate
of $\mathcal{O}(t^{-\frac{1}{9+\varepsilon}})$ for any $\varepsilon>0$.
Finally, we study Markov games without any assumptions on the dynamics, and
show a $path convergence$ rate, which is a new notion of convergence we
defined, of $\mathcal{O}(t^{-\frac{1}{10}})$. Our algorithm removes the
synchronization and prior knowledge requirement of [Wei et al., 2021], which
pursued the same goals as us for irreducible Markov games. Our algorithm is
related to [Chen et al., 2021, Cen et al., 2021] and also builds on the entropy
regularization technique. However, we remove their requirement of
communications on the entropy values, making our algorithm entirely uncoupled.
- Abstract(参考訳): 非漸近収束率を持つ$uncoupled$、$convergent$、$rational$というアルゴリズムの開発に焦点を絞って、2人のプレイヤーによるゼロサムマルコフゲームにおける学習の問題を再検討する。
我々は、バンド利得をウォームアップとしたステートレス行列ゲームの場合から始め、$\mathcal{O}(t^{-\frac{1}{8}})$ last-iterate convergence rateを示す。
我々の知る限りでは、これはバンディットフィードバックのみにアクセス可能な有限のラストイテレート収束率を得る最初の結果である。
我々はその結果を既約マルコフゲームの場合にまで拡張し、任意の$\varepsilon>0$に対して$\mathcal{O}(t^{-\frac{1}{9+\varepsilon}})$の最終定値収束率を与える。
最後に、力学の仮定なしにマルコフゲームを研究し、$path convergence$ rate を示し、これは定義した収束の新しい概念である $\mathcal{O}(t^{-\frac{1}{10}})$ を示す。
我々のアルゴリズムは[Wei et al., 2021]の同期と事前の知識要件を取り除き、既約マルコフゲームにおいて私たちと同じ目標を追求した。
本アルゴリズムは[chen et al., 2021, cen et al., 2021]と関連しており,エントロピー正規化手法を基礎としている。
しかし、エントロピー値に関するコミュニケーションの必要性を取り除き、アルゴリズムを完全に無結合にしています。
関連論文リスト
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in
Games [72.43065138581589]
RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。
本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。
そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
論文 参考訳(メタデータ) (2023-11-01T17:34:58Z) - $O(T^{-1})$ Convergence of Optimistic-Follow-the-Regularized-Leader in
Two-Player Zero-Sum Markov Games [10.915751393257011]
O(T-1)$-approximate Nash equilibrium in $T$ for two-player zero-sum Markov games with full information。
これにより、Zhang et al (2022)に最近示されている$tildeO(T-5/6)$収束率が向上する。
論文 参考訳(メタデータ) (2022-09-26T05:35:44Z) - Policy Optimization for Markov Games: Unified Framework and Faster
Convergence [81.3266426402464]
このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。
このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
論文 参考訳(メタデータ) (2022-06-06T14:23:13Z) - Independent Policy Gradient for Large-Scale Markov Potential Games:
Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。
我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。
我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
論文 参考訳(メタデータ) (2022-02-08T20:09:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。