論文の概要: Optimism Without Regularization: Constant Regret in Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2506.16736v1
• Date: Fri, 20 Jun 2025 04:10:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:05.336305
• Title: Optimism Without Regularization: Constant Regret in Zero-Sum Games
• Title（参考訳）: 正規化のない最適化 - ゼロサムゲームにおける一定の規則
• Authors: John Lazarsfeld, Georgios Piliouras, Ryann Sim, Stratis Skoulakis,
• Abstract要約: 同様の最適なレートが、正規化なしで達成可能であることを初めて示します。 我々は、オプティスティック・フィクティトゥス・プレイ(タイブレッシング・ルールを使用)が絶え間ない後悔しか得られない2つのストラテジー・ゲームについて証明する。
• 参考スコア（独自算出の注目度）: 35.34620729951821
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the optimistic variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a regularized algorithm with a bounded stepsize parameter -- obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable without regularization: we prove for two-strategy games that Optimistic Fictitious Play (using any tiebreaking rule) obtains only constant regret, providing surprising new evidence on the ability of non-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors, where we show a certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret lower bound of $\Omega(\sqrt{T})$ for Alternating Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving $o(\sqrt{T})$ regret.
• Abstract（参考訳）: 本稿では,2プレイヤーゼロサムゲームにおける学習のためのFactitious Playの楽観的な変形について検討する。 制限付き段数パラメータを持つ正規化アルゴリズムであるOptimistic FTRLは、この設定で常に後悔するが、同様の最適なレートも正規化なしで達成可能であることを示すのは初めてである。 我々の証明手法は、ペイオフベクトルの双対空間におけるオプティスティック・フィクティトゥス・プレイの幾何学的ビューを利用しており、そこでは、繰り返しのエネルギー関数が時間とともに有界であることを示す。 さらに、Alternating Fictitious Playの$\Omega(\sqrt{T})$に対する後悔の低い境界も証明します。 正規化されていない状態において、これは$o(\sqrt{T})$ regret を達成する際の楽観主義と交替の能力を分離する。

関連論文リスト

• Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play [39.1873150563222]
  本稿では,ゼロサムゲームにおける2つの非regretアルゴリズムのサブ線形後悔保証について検討する。 Fictitious Play と Online Gradient Descent は、正規化がないために不安定さと線形後悔を示す。 我々は、任意のタイブレークルールを持つ有限プレイが$O(sqrtT)$後悔していることを証明し、カルリンの有限プレイ予想が持つ新しいクラスのゲームを確立する。
  論文  参考訳（メタデータ） (2025-06-16T04:07:15Z)
• Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games [46.462843198107144]
  本研究では,学習者の適応的ペアリングによる学習促進は孤立的な現象ではないことを示す。 汎用ゲームにおいて,より高速な正規化学習を実現するフレームワークであるemphCautious Optimismを導入する。
  論文  参考訳（メタデータ） (2025-06-05T13:13:48Z)
• Achieving Better Regret against Strategic Adversaries [15.51709428653595]
  本研究では,学習者が相手の行動について余分な知識を持つオンライン学習問題について検討する。 我々は,正規化リーダ(AFTRL)とProd-Best Response(Prod-BR)の2つの新しいオンライン学習アルゴリズムを提案する。 AFTRLは、外部の後悔に対して$O(1)$、または$O(1)$、遠回りの後悔に対して$O(1)$を達成する。
  論文  参考訳（メタデータ） (2023-02-13T19:34:36Z)
• Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
  本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。 このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
  論文  参考訳（メタデータ） (2023-01-30T17:55:53Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• 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)

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

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