論文の概要: Constant regret in general games via higher-order optimism
- arxiv url: http://arxiv.org/abs/2609.04113v1
- Date: Thu, 03 Sep 2026 17:16:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-04 18:28:39.180674
- Title: Constant regret in general games via higher-order optimism
- Title（参考訳）: 高次楽観主義による一般ゲームにおける絶え間ない後悔
- Abstract要約: 任意の$N$-playerの正規フォームゲームのすべてのプレイヤーが採用するアンカップリング学習アルゴリズムを導入し、このアルゴリズムは個々の後悔に対して$O(N3log2 K)を保証します。
提案アルゴリズムは、割引された$(N+1)$-th次予測器とエントロピー正規化を組み合わせた楽観的追従正規化リーダ(FTRL)の変種である。
- 参考スコア（独自算出の注目度）: 21.642749388029525
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary $N$-player normal form game with up to $K$ actions per player, guarantees $O(N^3\log^2 K)$ individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted $(N+1)$-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an $O(N^{21}\log^{4} K)$ regret bound through the use of higher-order optimism and an exponential moving average estimator.
- Abstract（参考訳）: 任意の$N$-player正規フォームゲームのプレイヤーに最大$K$アクションを課すと、O(N^3\log^2K)$個々人の後悔を、一様に遊びの地平線上で保証するアンカップリング学習アルゴリズムを導入する。
提案アルゴリズムは,ゲーム戦略空間の「リフティング」に対するエントロピー正則化と,割引された$(N+1)$-th次予測器を組み合わせた楽観的追従型リーダー(OptFTRL)の変種である。
この組み合わせは、一般的なゲームにおいて絶え間ない後悔を達成するために、従来の試みのキースタブルブロックを取り除き、制御された方法で、誘導されたプレーのシーケンスの大きな振動を抑えるように設計されている。
我々のアプローチは、Lou, Farina, and Ozdaglar (arXiv:2608.31166) の同時かつ完全に独立な仕事といくつかの顕著な類似性を持っている。
関連論文リスト
- Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices [6.51943696606773]
有限個のマルチプレイヤー汎用ゲームに対して決定論的かつ非結合的な学習力学を与える。
プレイヤーが$n$、アクションが$m$である場合、各プレイヤーは全ての有限地平線において$O(sqrtn m log m log5/2(nm))$を後悔する。
論文 参考訳（メタデータ） (2026-09-15T07:27:34Z) - 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) - Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。
我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
論文 参考訳（メタデータ） (2025-10-20T00:45:47Z) - Faster Rates for No-Regret Learning in General Games via Cautious Optimism [46.462843198107144]
我々は,マルチプレイヤーの汎用ゲームにおいて,O(n, d log T)$per-playerの後悔を実現する最初の未結合学習アルゴリズムを確立する。
この結果は,Log-Regularized Lifted Optimistic FTRLで達成可能な$O(n, d log T)$ regretと比較して,$d$への依存を指数関数的に改善する。
論文 参考訳（メタデータ） (2025-03-31T17:25:33Z) - 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 $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。
これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
論文 参考訳（メタデータ） (2022-08-20T20:48:58Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。