論文の概要: A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
- arxiv url: http://arxiv.org/abs/2609.22839v1
- Date: Sat, 19 Sep 2026 07:15:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-22 20:29:00.571054
- Title: A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
- Title（参考訳）: 一般ゲームにおける最適ヘッジのための水平非独立レギュレット境界
- Abstract要約: ステップサイズが一定であれば、一般ゲームにおいてO_n,d(1)$の個別後悔が得られることを示す。
我々の証明はフリッシュ (1967) の非構成的ネーター性論証に基づいているので、$(n,d)$-依存は暗黙的に残る。
- 参考スコア（独自算出の注目度）: 0.7106986689736826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Can simple learning rules keep their regret bounded in self-play? Recent work achieves constant regret bounds through modified regularization and higher-order prediction. Yet for Optimistic Hedge, arguably the most canonical method in games, the best known individual regret bound remains logarithmic. In this work, we prove that plain Optimistic Hedge with a constant step size can attain $O_{n,d}(1)$ individual regret in general-sum games with $n$ players and $d=(d_1,\ldots,d_n)$ actions, under expected loss-vector feedback. As a corollary, its time-averaged play enjoys an $O_{n,d}(1/T)$ coarse correlated equilibrium (CCE) gap. Our analysis represents Optimistic Hedge as a real-analytic recurrence on a compact space, which yields an exact finite-order difference relation that eliminates horizon dependence. Our proof hinges on nonconstructive Noetherianity argument of Frisch (1967), so the $(n,d)$-dependence remains implicit.
- Abstract（参考訳）: 単純な学習ルールは、後悔を自己プレイに縛り付けることができるのか?
最近の研究は、修正された正規化と高次予測を通じて、一定の後悔境界を達成する。
しかし、ゲームで最も標準的な方法であるオプティスティック・ヘッジにとって、最もよく知られた個々の後悔境界は対数的のままである。
本研究は,一定のステップサイズを持つ平易なオプティミスティック・ヘッジが,期待される損失ベクトルフィードバックの下で,$n$プレーヤーと$d=(d_1,\ldots,d_n)$アクションを持つ一般サムゲームにおいて,$O_{n,d}(1)の個々の後悔を達成できることを証明する。
時系列として、その平均的な遊びは$O_{n,d}(1/T)$ coarse correlation equilibrium (CCE) ギャップを享受する。
我々の分析は、最適化ヘッジをコンパクト空間上の実解析的再帰として表現し、地平線依存を排除した正確な有限階差分関係を与える。
我々の証明はフリッシュ (1967) の非構成的ネーター性論証に基づいているので、$(n,d)$-依存は暗黙的に残る。
関連論文リスト
- Multiplicative Optimism for Constant Regret in Games [29.477078788138154]
乗法的最適回帰マッチング(英: multiplicatively Optimistic Regret Matching)は、有限一般ゲームにおける非結合学習規則である。
学習率の保護は、敵のユーティリティに直面して、$O(sqrtTlog d)$ regretを与える。
論文 参考訳（メタデータ） (2026-09-18T16:38:29Z) - 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) - Scale-Invariant Fast Convergence in Games [67.02769061793619]
我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。
2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。
マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
論文 参考訳（メタデータ） (2026-02-12T11:57:20Z) - Swap Regret Minimization Through Response-Based Approachability [66.39400409563976]
オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。
我々は、一般凸集合に対して$O(d3/2 sqrtT)$リニアスワップ後悔を保証し、集合が中央対称であるときに$O(d sqrtT)$を保証し、より単純で効率的なアルゴリズムを開発する。
論文 参考訳（メタデータ） (2026-02-05T23:43:25Z) - Small Gradient Norm Regret for Online Convex Optimization [19.699405661554845]
我々は、$Gstar$後悔は、既存の$Lstar$(小さな損失)後悔を厳しく洗練させることを示した。
結果をダイナミックな後悔と盗賊の設定にまで拡張します。
論文 参考訳（メタデータ） (2026-01-20T02:11:01Z) - Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。
我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
論文 参考訳（メタデータ） (2025-10-20T00:45:47Z) - Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。
また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
論文 参考訳（メタデータ） (2025-02-24T20:20:06Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - Near-Optimal No-Regret Learning in General Games [31.293412884145066]
マルチプレイヤー汎用ゲームにおいて,Optimistic Hedge が $rm poly(log T)$ regret を達成することを示す。
我々の境界の系は、最適化的ヘッジが一般ゲームにおいて$tildeOleft(frac 1Tright)$の速度で粗相関平衡に収束するということである。
論文 参考訳（メタデータ） (2021-08-16T06:53:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。