論文の概要: Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
with Bandit Feedback
- arxiv url: http://arxiv.org/abs/2303.02738v2
- Date: Wed, 8 Nov 2023 19:47:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-10 18:34:22.434678
- Title: Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
with Bandit Feedback
- Title（参考訳）: バンドフィードバックを持つ2プレイヤーゼロサムマルコフゲームにおけるアンカップリングと収束学習
- Authors: Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
- Abstract要約: 非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。
我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
- 参考スコア（独自算出の注目度）: 49.1061436241109
- 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
$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 $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
$O(t^{-\frac{1}{10}})$. Our algorithm removes the coordination 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（参考訳）: 2人プレイのゼロサムマルコフゲームにおける学習の問題を再検討し、非漸近収束率で非結合、収束、合理的なアルゴリズムを開発することに焦点を当てる。
我々は、バンドフィードバックをウォームアップとしたステートレス行列ゲームの場合から始め、$O(t^{-\frac{1}{8}})$ last-iterate convergence rateを示す。
我々の知る限りでは、これはバンディットフィードバックのみにアクセス可能な有限のラストイテレート収束率を得る最初の結果である。
我々はその結果を既約マルコフゲームの場合にまで拡張し、任意の$\varepsilon>0$に対して$O(t^{-\frac{1}{9+\varepsilon}})$の最終定値収束率を与える。
最後に、マルコフゲームについてダイナミクスを仮定せずに研究し、経路収束率を示し、これは我々が定義した収束の新しい概念である、$o(t^{-\frac{1}{10}})$を示す。
我々のアルゴリズムは[Wei et al., 2021]の協調と事前の知識要件を取り除き、既約マルコフゲームにおいて私たちと同じ目標を追求した。
本アルゴリズムは[chen et al., 2021, cen et al., 2021]と関連しており,エントロピー正規化手法を基礎としている。
しかし、エントロピー値に関するコミュニケーションの必要性を取り除き、アルゴリズムを完全に無結合にしています。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
楽観的フォロー・ザ・レギュラライズド・リーダー・アルゴリズムは,フル情報汎用マルコフゲームにおいて,$widetildeO(T-1)$-approximate iterationsを$T$内で見つけることができることを示す。
論文 参考訳（メタデータ） (2024-02-02T20:40:27Z) - 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) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。