論文の概要: Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

• arxiv url: http://arxiv.org/abs/2608.04149v1
• Date: Tue, 04 Aug 2026 18:58:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-06 14:48:43.598786
• Title: Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
• Title（参考訳）: ハイブリッド正規化によるマルチプレイヤー汎用ゲームにおけるサブ対数スワップレグレット
• Authors: Taira Tsuchiya,
• Abstract要約: スワップ後悔は、非結合学習力学がマルチプレイヤー一般サムゲームにおける平衡に収束する速度を支配している。 我々は、すべてのプレイヤーが$O(nm2sqrtlog mlog T/T)$スワップ後悔を発生させるアンカップリング力学を構築する。
• 参考スコア（独自算出の注目度）: 12.597979977402543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best previous guarantee when every player follows the same dynamics grows logarithmically in the horizon $T$. We construct uncoupled dynamics under which every player incurs only $O(nm^2\sqrt{\log m\log T})$ swap regret, where $n$ is the number of players and $m$ bounds the number of actions per player. To our knowledge, this is the first sublogarithmic individual guarantee in this setting, and it implies that the time-averaged product distribution of play is an $O(nm^2\sqrt{\log m\log T}/T)$-approximate correlated equilibrium. The key algorithmic choice is to combine the Blum--Mansour reduction with optimistic follow-the-regularized-leader using a hybrid regularizer that separately weights negative Shannon entropy and the log-barrier: the entropy controls the optimistic prediction error, whereas the log-barrier controls the transition-matrix movement through its Bregman divergence. A new sensitivity theorem for stationary distributions of Markov chains, which involves neither mixing parameters nor the smallest transition probability, transfers this control to the played strategies and yields a simpler analysis without local-norm or self-concordance arguments. The guarantee is preserved by an adversarially robust variant that additionally ensures $O(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})$ swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of $T$.
• Abstract（参考訳）: スワップ後悔は、非結合学習力学がマルチプレイヤー一般サムゲームにおける平衡に収束する速度を支配している。 完全な情報フィードバックの下では、すべてのプレイヤーが同じダイナミクスに従うときの最も古い保証は、水平線で対数的に$T$になる。 我々は、すべてのプレイヤーが$O(nm^2\sqrt{\log m\log T})$スワップ後悔を発生させるアンカップリング力学を構築し、$n$はプレイヤー数、$m$はプレイヤー当たりのアクション数にバウンドする。 我々の知る限り、これはこの設定における最初の非対数的個人保証であり、プレイの平均積分布が$O(nm^2\sqrt{\log m\log T}/T)$-近似相関平衡であることを意味する。 主要なアルゴリズム選択は、Blum-Mansour還元と、負のシャノンエントロピーと対数バリアを別々に重み付けするハイブリッド正則化器を併用することである:エントロピーは予測誤差を制御し、対数バリアはブレグマンの発散を通じて遷移行列運動を制御する。 マルコフ連鎖の定常分布に対する新しい感度定理は、パラメータの混合も最小の遷移確率も含まないもので、この制御をプレイされた戦略に転送し、局所ノルムや自己調和の議論なしにより単純な解析を与える。 この保証は、さらに$O(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})$ を任意のユーティリティ列に置き換えることを保証する逆堅牢な変種と、$T$の事前の知識を必要としない地平線のない変種によって保持される。

関連論文リスト

• 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)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• $\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)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• 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)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
  論文  参考訳（メタデータ） (2020-06-10T01:59:34Z)

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

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