論文の概要: Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2510.11691v1
• Date: Mon, 13 Oct 2025 17:52:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:30.495721
• Title: Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
• Title（参考訳）: 2プレイヤーゼロサムゲームにおける最適ヘッジのための上下境界の厳格化
• Authors: Taira Tsuchiya,
• Abstract要約: ゼロサムゲームにおいて、楽観的なヘッジに基づく学習力学は、最もよく知られた後悔の上界の1つを達成する。 本研究は,楽観的ヘッジを後悔した$m$および$n$への依存の最適性について検討する。
• 参考スコア（独自算出の注目度）: 12.597979977402543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In two-player zero-sum games, the learning dynamic based on optimistic Hedge achieves one of the best-known regret upper bounds among strongly-uncoupled learning dynamics. With an appropriately chosen learning rate, the social and individual regrets can be bounded by $O(\log(mn))$ in terms of the numbers of actions $m$ and $n$ of the two players. This study investigates the optimality of the dependence on $m$ and $n$ in the regret of optimistic Hedge. To this end, we begin by refining existing regret analysis and show that, in the strongly-uncoupled setting where the opponent's number of actions is known, both the social and individual regret bounds can be improved to $O(\sqrt{\log m \log n})$. In this analysis, we express the regret upper bound as an optimization problem with respect to the learning rates and the coefficients of certain negative terms, enabling refined analysis of the leading constants. We then show that the existing social regret bound as well as these new social and individual regret upper bounds cannot be further improved for optimistic Hedge by providing algorithm-dependent individual regret lower bounds. Importantly, these social regret upper and lower bounds match exactly including the constant factor in the leading term. Finally, building on these results, we improve the last-iterate convergence rate and the dynamic regret of a learning dynamic based on optimistic Hedge, and complement these bounds with algorithm-dependent dynamic regret lower bounds that match the improved bounds.
• Abstract（参考訳）: 2人のプレイヤーによるゼロサムゲームにおいて、楽観的なヘッジに基づく学習力学は、強く非結合な学習力学の中で最もよく知られた後悔の上界の1つを達成する。 適切に選択された学習率では、社会的および個人的後悔は2人のプレイヤーのアクションの数で$O(\log(mn))$と$n$に制限される。 本研究は,楽観的ヘッジを後悔した$m$および$n$への依存の最適性について検討する。 この目的のために、既存の後悔分析を精査し、相手の行動の数を知っている強い未結合の環境では、社会的および個人的後悔境界を$O(\sqrt{\log m \log n})$に改善できることを示す。 本稿では,学習率と負の項の係数に関する最適化問題として,後悔の上限を表現し,先行定数の洗練された解析を可能にする。 次に,既存の社会的後悔境界と,これら新たな社会的後悔上限と個人的後悔上限は,アルゴリズムに依存した個人的後悔上限を提供することによって,楽観的なヘッジに対してさらに改善できないことを示す。 重要なことは、これらの社会的後悔と下限は、前項の定数要素を正確に含んでいることである。 最後に、これらの結果に基づいて、楽観的なHedgeに基づく学習力学の最後の項目収束率と動的後悔を改善し、改善された境界に一致するアルゴリズム依存の動的後悔低境界でこれらの境界を補完する。

関連論文リスト

• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [2.628557920905129]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
  論文  参考訳（メタデータ） (2023-03-06T16:41:57Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。 これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
  論文  参考訳（メタデータ） (2022-08-20T20:48:58Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness [2.628557920905129]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 この目的を達成するために、損失系列に関連する2つの重要な量を導入し、累積分散と対角変動と呼ぶ。 完全な i.d. の場合、我々の境界は加速の結果から期待される速度と一致し、完全に反対の場合、ミニマックスの後悔と一致するように優雅に劣化する。
  論文  参考訳（メタデータ） (2022-02-15T16:39:33Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• 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)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)

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

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