論文の概要: A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem

• arxiv url: http://arxiv.org/abs/2603.11764v1
• Date: Thu, 12 Mar 2026 10:11:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-13 14:46:26.012337
• Title: A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem
• Title（参考訳）: 半帯域問題に対するBest-of-Both-Worlds Guaranteesを用いたさらなる効率的なアルゴリズム
• Authors: Botao Chen, Jongyeong Lee, Chansoo Kim, Junya Honda,
• Abstract要約: 本稿では,$m$セット半帯域問題におけるFollow-the-Perturbed-Leader(FTPL)ポリシーの最適性と複雑性について検討する。 Fréchetと特定のパラメータを持つ分布を持つFTPLは、逆向きの設定で$O(sqrtmdT)$を最善に後悔することを示す。 また,条件付き幾何再サンプリングを$m$セットの半帯域に拡張し,FTPLの効率よく損失推定を行う。
• 参考スコア（独自算出の注目度）: 11.27658240767421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in $m$-set semi-bandit problems. FTPL has been studied extensively as a promising candidate of an efficient algorithm with favorable regret for adversarial combinatorial semi-bandits. Nevertheless, the optimality of FTPL has still been unknown unlike Follow-the-Regularized-Leader (FTRL) whose optimality has been proved for various tasks of online learning. In this paper, we extend the analysis of FTPL with geometric resampling (GR) to $m$-set semi-bandits, which is a special case of combinatorial semi-bandits, showing that FTPL with Fréchet and Pareto distributions with certain parameters achieves the best possible regret of $O(\sqrt{mdT})$ in adversarial setting. We also show that FTPL with Fréchet and Pareto distributions with a certain parameter achieves a logarithmic regret for stochastic setting, meaning the Best-of-Both-Worlds optimality of FTPL for $m$-set semi-bandit problems. Furthermore, we extend the conditional geometric resampling to $m$-set semi-bandits for efficient loss estimation in FTPL, reducing the computational complexity from $O(d^2)$ of the original geometric resampling to $O(md(\log(d/m)+1))$ without sacrificing the regret performance.
• Abstract（参考訳）: 本稿では,$m$セット半帯域問題におけるFollow-the-Perturbed-Leader(FTPL)ポリシーの最適性と複雑性について検討する。 FTPLは効率の良いアルゴリズムの候補として広く研究されてきた。 それでもFTPLの最適性は、オンライン学習の様々なタスクに最適なFTRL(Follow-the-Regularized-Leader)とは異なる。 本稿では,幾何再サンプリング (GR) によるFTPLの解析を$m$-set 半バンドウィットに拡張し,Fréchet と Pareto の分布をパラメータとしたFTPL が$O(\sqrt{mdT})$の逆条件で最善の後悔を実現することを示す。 また,Fréchet と Pareto の分布をパラメータとしたFTPL が確率的設定に対する対数的後悔を達成し,$m$ の半帯域問題に対するFTPL の最適性を示す。 さらに,条件付き幾何再サンプリングを$m$集合半帯域に拡張してFTPLの効率な損失推定を行い,元の幾何再サンプリングの$O(d^2)$から$O(md(\log(d/m)+1)$へ計算複雑性を低減させる。

関連論文リスト

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems [10.435741631709403]
  小型不変半帯域問題におけるFollow-the-Perturbed-Leader(FTPL)ポリシーの最適性と複雑性について検討する。 我々は条件付き幾何再サンプリング(CGR)をサイズ不変半帯域設定に拡張し、計算の複雑さをオリジナルのGRの$O(d2)$から$Oleft(mdleft(log(d/m)+1right)$に縮める。
  論文  参考訳（メタデータ） (2025-06-14T13:06:30Z)
• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。 また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
  論文  参考訳（メタデータ） (2025-04-09T22:07:01Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.075593833879357]
  FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。 本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-30T16:00:23Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• 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)

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

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