論文の概要: Regret Matching+: (In)Stability and Fast Convergence in Games

• arxiv url: http://arxiv.org/abs/2305.14709v1
• Date: Wed, 24 May 2023 04:26:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-25 19:50:15.653611
• Title: Regret Matching+: (In)Stability and Fast Convergence in Games
• Title（参考訳）: regret matching+: (in)安定性とゲームの高速収束
• Authors: Gabriele Farina and Julien Grand-Cl\'ement and Christian Kroer and Chung-Wei Lee and Haipeng Luo
• Abstract要約: RM+とその予測バージョンは不安定であり,他のプレイヤーが大きな後悔を味わう可能性がある。 これらの修正は、RM+による通常のゲームにおいて、個々の後悔に対して$O(T1/4)$$と$O(1)$の社会的後悔を得るのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 68.13214224119024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Regret Matching+ (RM+) and its variants are important algorithms for solving large-scale games. However, a theoretical understanding of their success in practice is still a mystery. Moreover, recent advances on fast convergence in games are limited to no-regret algorithms such as online mirror descent, which satisfy stability. In this paper, we first give counterexamples showing that RM+ and its predictive version can be unstable, which might cause other players to suffer large regret. We then provide two fixes: restarting and chopping off the positive orthant that RM+ works in. We show that these fixes are sufficient to get $O(T^{1/4})$ individual regret and $O(1)$ social regret in normal-form games via RM+ with predictions. We also apply our stabilizing techniques to clairvoyant updates in the uncoupled learning setting for RM+ and prove desirable results akin to recent works for Clairvoyant online mirror descent. Our experiments show the advantages of our algorithms over vanilla RM+-based algorithms in matrix and extensive-form games.
• Abstract（参考訳）: Regret Matching+ (RM+)とその変種は大規模ゲームを解く上で重要なアルゴリズムである。 しかし、実際の成功に関する理論的理解はまだ謎である。 さらに、ゲームにおける高速収束の最近の進歩は、安定性を満足するオンラインミラー降下のような非回帰アルゴリズムに限定されている。 本稿では,まずrm+とその予測バージョンが不安定になりうることを示す反例を示す。 次に、RM+が機能する正のオルサントを再開および切断する2つの修正を提供します。 これらの修正は, RM+による正規形ゲームにおいて, 個々の後悔に対して$O(T^{1/4})$$と$O(1)$の社会的後悔を与えるのに十分であることを示す。 また、rm+の非結合学習環境における透視的更新に安定化技術を適用し、最近の透視的オンラインミラー降下の成果に類似した望ましい結果を証明した。 実験により,行列ゲームや広角ゲームにおいて,バニラRM+に基づくアルゴリズムよりもアルゴリズムの利点が示された。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [72.43065138581589]
  RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。 本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。 そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)

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

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