Fugu-MT 論文翻訳(概要): Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

論文の概要: Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

arxiv url: http://arxiv.org/abs/2611.07078v1
Date: Wed, 04 Nov 2026 19:34:53 GMT
ステータス: 翻訳完了
システム内更新日: 2026-11-06 21:50:50.440112
Title: Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation
Title（参考訳）: 一般サムゲームにおける最適ヘッジ:時間近似による基本限界とレグレト境界
Abstract要約: 有限一般サムゲームでは、各プレイヤーの後悔は地平線上の多元対数的(polylogarithmic)である。 2人のプレイヤーのゲームでは、オプティスティック・ヘッジが水平線から独立して$O(nlog n)$後悔することを保証する学習レートが存在する。しかし、3人プレイのゲームでは、そのような制限はあり得ない。
参考スコア（独自算出の注目度）: 26.326025099480262
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{Ω(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{Ω(mn)}$; for learning rates above $2^{-Ω(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.
Abstract（参考訳）: Optimistic Hedge(オプティスティック・ヘッジ)は、外挿の一段階を加味した乗法的ウェイトアップデートであり、ゲームにとって最も自然な後悔を最小化するダイナミクスの1つである。 Daskalakis, Fishelson, Golowich は、有限の一般サムゲームにおけるすべての$m$プレーヤーがオプティスティック・ヘッジに一定の学習率で従えば、各プレイヤーの後悔は地平線上の多元対数であることを示した。その後、ハは学習率の適切な選択により、各プレイヤーの後悔は$T$とは無関係に束縛されることを示した。しかし、この境界は非構成的であり、作用数への依存$n$は明示的ではなく、楽観的ヘッジがゲームの大きさの多項式である定数な後悔境界を達成できるかどうかを問わない。解答は選手数に左右される。 2人のプレイヤーのゲームでは、楽観的ヘッジが水平線から独立して$O(n\log n)$後悔することを保証する学習レートが存在する。しかし、3人プレイヤゲームでは、そのような制限はない: 絶対定数までの学習率と十分大きな水平線に対して$T$、プレイヤー当たり$n$アクションを持つゲームがあり、あるプレイヤーの後悔が$2^{Ω(n)}$で、より一般的には、あるプレイヤーの後悔が$2^{Ω(mn)$で、あるプレイヤーの後悔が$2^{Ω(mn)$で、また、学習レートが$2^{-Ω(mn)$で、そのプレイヤーの後悔が$T$で線形に増加する。我々の上界は、最適化ヘッジの分析のための時間近似フレームワークに基づいている。 Daskalakis et al の分散に基づく RVU 境界から始めて、時間的局所化されたウィンドウ上の損失を、その総変分がその累積分散のごく一部であるよく定義された関数によって近似する。 m$-playerゲームでは、同じフレームワークが最近の$O(\sqrt{m}\log n\log T)$ regret bound due to Ha の証明を著しく単純化する。

論文の概要: Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

関連論文リスト