論文の概要: Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism

• arxiv url: http://arxiv.org/abs/2609.16751v2
• Date: Sat, 19 Sep 2026 22:18:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:28:59.841797
• Title: Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism
• Title（参考訳）: 2次元高次最適化による一般サムゲームにおける定数スワップレグレクト
• Abstract要約: 有限個のマルチプレイヤー汎用ゲームに対して決定論的かつ非結合的な学習力学を与える。 プレイヤーが$n$、アクションが$m$である場合、各プレイヤーの個々のスワップ後悔はすべての有限地平線において$O(sqrt n,mlog mlog5/2(nm))$である。
• 参考スコア（独自算出の注目度）: 6.51943696606773
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon $T$. With $n$ players and at most $m$ actions each, every player's individual swap regret is $O(\sqrt n\,m\log m\log^{5/2}(nm))$ at every finite horizon. The dynamics use the classical Blum-Mansour framework with optimism. Each player predicts the deviation gains, uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. Our new ingredients include a tailored row normalization map and a two-scale higher-order predictor. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most $7\sqrt{mT\log m}$ in the adversarial setting.
• Abstract（参考訳）: 有限多人数汎用ゲームに対する決定論的かつ非結合的な学習力学をフルインフォメーションフィードバックで提供し、水平線$T$とは無関係に、自己プレーにおける絶え間ない個々人のスワップ後悔を実現する。 プレイヤーが$n$、アクションが$m$である場合、各プレイヤーの個々のスワップ後悔はすべての有限地平線において$O(\sqrt n\,m\log m\log^{5/2}(nm))$である。 力学は古典的なBlum-Mansourフレームワークと楽観主義を用いる。 各プレイヤーは偏差ゲインを予測し、これらの予測を使用して行確率遷移行列を更新し、その定常分布を再生する。 我々の新しい材料には、調整された行正規化マップと2スケールの高次予測器が含まれる。 一般的なコモン・プレフィックス・スイッチング・ラッパー(英語版)を通して得られる逆堅牢な変種は、自己プレイを普遍定数に有界に保ち、対向的な設定で少なくとも7\sqrt{mT\log m}$で個々のスワップ後悔を保証する。

関連論文リスト

• Constant regret in general games via higher-order optimism [21.642749388029525]
  任意の$N$-playerの正規フォームゲームのすべてのプレイヤーが採用するアンカップリング学習アルゴリズムを導入し、このアルゴリズムは個々の後悔に対して$O(N3log2 K)を保証します。 提案アルゴリズムは、割引された$(N+1)$-th次予測器とエントロピー正規化を組み合わせた楽観的追従正規化リーダ(FTRL)の変種である。
  論文  参考訳（メタデータ） (2026-09-03T17:16:13Z)
• Independent Reinforcement Learning in Discounted Markov Games [5.5438676149999075]
  各固定割引係数に対して、割引された一般マルコフゲームにおいて、逆多項式的精度の粗相関平衡に対する非時間アルゴリズムが存在することを示す。 提案アルゴリズムは,マルチエージェント設定に合わせたステップサイズスケジュールの増大を伴う,楽観的ミラー降下の多層版である。
  論文  参考訳（メタデータ） (2026-09-01T00:07:45Z)
• Constant Individual Regret in General Games [27.786964046329455]
  EmphECHO-OFTRL:高次楽観主義(ECHO)のためのEMAカスケードを備えた楽観的追従型リーダーについて紹介する。 もし$m_max$が最大のアクションセットサイズであるなら、すべての水平線に対して$Tgeq1$を同時にすると、ゲーム内の$N$のプレイヤーは、$O(textrmpoly(N, log m_max))$で囲まれた上界を後悔する。 我々のアルゴリズムは、現代のフィルタ設計にインスパイアされた新しい楽観主義の形式を利用する。
  論文  参考訳（メタデータ） (2026-08-31T17:59:16Z)
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization [12.597979977402543]
  スワップ後悔は、非結合学習力学がマルチプレイヤー一般サムゲームにおける平衡に収束する速度を支配している。 我々は、すべてのプレイヤーが$O(nm2sqrtlog mlog T/T)$スワップ後悔を発生させるアンカップリング力学を構築する。
  論文  参考訳（メタデータ） (2026-08-04T18:58:51Z)
• Scale-Invariant Fast Convergence in Games [67.02769061793619]
  我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。 2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。 マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
  論文  参考訳（メタデータ） (2026-02-12T11:57:20Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Swap Regret and Correlated Equilibria Beyond Normal-Form Games [62.01542145970044]
  「我々は、プロファイルスワップ後悔と呼ぶポリトープゲームのスワップ後悔の新しい変種を提示する。」 プロファイルスワップ後悔は、プレイの書き起こしが与えられた場合、NPハードであることが示されるが、少なくとも$O(sqrtT)$プロファイルスワップ後悔を保証する効率的な学習アルゴリズムを設計することは可能である。
  論文  参考訳（メタデータ） (2025-02-27T16:16:26Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)

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

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