論文の概要: Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2608.25182v1
• Date: Tue, 25 Aug 2026 21:56:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.455389
• Title: Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
• Title（参考訳）: エキスパート問題とオンライン凸最適化のためのminimax Alternating Regret
• Abstract要約: ミニマックスの交互後悔は地平線から独立して$(log d)$であることを示す。 さらに、この結果を$d$次元コンパクト凸集合上で一般のOCOに拡張する。
• 参考スコア（独自算出の注目度）: 13.08870048693199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$, independent of the horizon $T$. This significantly improves upon the best-known $\mathcal{O}(T^{1/3}\log^{2/3} d)$ established by Hait et al. [2025]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the best-known $\mathcal{O}((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by Cevher et al. [2023], Hait et al. [2025]. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge, in which carefully designed correction terms cancel the unfavorable curvature arising in the alternating-regret analysis. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the expert construction repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.
• Abstract（参考訳）: 本稿では,オンライン凸最適化(OCO)における後悔の交替について検討する。 以前の研究は、損失関数や実現可能な領域に関する様々な仮定の下で、$o(\sqrt{T})$交互後悔は達成可能であることを示したが、ミニマックスの後悔率は、専門家の問題においても未解決のままである。 本稿では,専門家問題と一般OCOの双方に対して,下界と上界の整合性を示すことで,この問題を解決する。 驚くべきことに、$d$-expert 問題に対して、ミニマックスの交互後悔は、地平線から独立して$(\log d)$であることを示す。 これは最もよく知られた $\mathcal{O}(T^{1/3}\log^{2/3} d)$ を Hait et al [2025] により大幅に改善する。 我々はさらに、$d$-次元コンパクト凸集合上の一般 OCO に結果を拡張し、最悪の場合のミニマックスの交互後悔が$(d\log \left(1+\frac{T}{d}\right)\right)$であることを証明するとともに、最もよく知られた $\mathcal{O}((d\log T)^{2/3}T^{1/3})$ の上界を改良し、チェバーらによる開問題を解き、2023], Hait et al [2025] によって生じる。 技術的には、専門家問題の上限はHedgeの修正版によって達成され、慎重に設計された補正項は、交互回帰解析で生じる好ましくない曲率をキャンセルする。 我々は、OCOの最適交互相対レートを得るために、同じ修正されたポテンシャル引数を連続的な作用集合に拡張する。 下位境界については、専門家構成は候補エキスパートの半分を繰り返し排除し、OCOの下限インスタンス構成は、単位円板上のより複雑なマルチスケール構成によって、この離散的な除去を置き換える。

関連論文リスト

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Online Convex Optimization with Sublinear Noisy Probes [6.998574163422056]
  オンライン凸最適化(OCO)を凸集合として$Ksubseteq mathbb Rd$で検討する。 我々は最近の2つの作業の行を一般化する統一された探索モデルを導入する: 専門家設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用できるペアワイズフィードバックである。 本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
  論文  参考訳（メタデータ） (2026-06-12T17:05:08Z)
• Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets [27.973926244529267]
  本研究では,コンテキストレコメンデーションとして知られる逆逆線形最適化について検討する。 学習者は、M-集合上の最適解のキャラクタリゼーションとボリューム引数を組み合わせることで、これを後悔する。
  論文  参考訳（メタデータ） (2026-02-02T05:48:54Z)
• 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)
• Alternating Regret for Online Convex Optimization [43.12477663757647]
  連続Hedgeアルゴリズムは,任意の逆数$次元OCO問題に対して,$tildemathcalO(dfrac23Tfrac13)$の繰り返し後悔を実現することを示す。 例えば、Regret Matching 変種に対する$Omega(sqrtT)$ lower boundなどである。
  論文  参考訳（メタデータ） (2025-02-18T04:32:52Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。 また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
  論文  参考訳（メタデータ） (2022-01-21T22:08:07Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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