論文の概要: Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits

• arxiv url: http://arxiv.org/abs/2508.18768v1
• Date: Tue, 26 Aug 2025 07:51:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-27 17:42:38.734878
• Title: Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits
• Title（参考訳）: コンテクスト型コンビネーションセミバンドのためのBest-of-Both-Worldsアルゴリズム
• Authors: Mengmeng Li, Philipp Schneider, Jelisaveta Aleksić, Daniel Kuhn,
• Abstract要約: コンテクスト的半帯域に対して,$widetildemathcalO(sqrtT)$ regretを同時に保証する,初めてのベスト・オブ・ボス・ワールド・アルゴリズムを導入する。 Karush-Kuhn-Tucker条件を利用することで、$K$凸射影問題を1次元のルートフィニング問題に変換する。 実証的な評価は、この組み合わせ戦略が、最高の世界のアルゴリズムの魅力的な後悔の限界に達するだけでなく、ラウンドごとの大幅なスピードアップをもたらすことを示している。
• 参考スコア（独自算出の注目度）: 3.448177863267093
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the first best-of-both-worlds algorithm for contextual combinatorial semi-bandits that simultaneously guarantees $\widetilde{\mathcal{O}}(\sqrt{T})$ regret in the adversarial regime and $\widetilde{\mathcal{O}}(\ln T)$ regret in the corrupted stochastic regime. Our approach builds on the Follow-the-Regularized-Leader (FTRL) framework equipped with a Shannon entropy regularizer, yielding a flexible method that admits efficient implementations. Beyond regret bounds, we tackle the practical bottleneck in FTRL (or, equivalently, Online Stochastic Mirror Descent) arising from the high-dimensional projection step encountered in each round of interaction. By leveraging the Karush-Kuhn-Tucker conditions, we transform the $K$-dimensional convex projection problem into a single-variable root-finding problem, dramatically accelerating each round. Empirical evaluations demonstrate that this combined strategy not only attains the attractive regret bounds of best-of-both-worlds algorithms but also delivers substantial per-round speed-ups, making it well-suited for large-scale, real-time applications.
• Abstract（参考訳）: 我々は、文脈的組合せ的半帯域に対する最初のベスト・オブ・ボス・ワールド・アルゴリズムを導入し、このアルゴリズムは、敵対的体制において$\widetilde{\mathcal{O}}(\sqrt{T})$後悔と、腐敗した確率的体制において$\widetilde{\mathcal{O}}(\ln T)$後悔を同時に保証する。 提案手法は,シャノンエントロピー正規化器(Shannon entropy regularizer)を備えたFTRL(Follow-the-Regularized-Leader)フレームワーク上に構築され,効率的な実装を実現する柔軟な手法が得られた。 後悔の限界の他に、各相互作用のラウンドで遭遇する高次元投影ステップから生じるFTRL(オンライン確率鏡の輝き)の実用的ボトルネックに取り組む。 カルーシュ・クーン・タッカー条件を利用することで、K$次元凸射影問題を1変数のルートフィニング問題に変換し、各ラウンドを劇的に加速する。 実証的な評価は、この組み合わせ戦略が、最高の世界のアルゴリズムの魅力的な後悔の限界に達するだけでなく、ラウンドごとの大幅なスピードアップも達成し、大規模でリアルタイムなアプリケーションに適していることを示している。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。 この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。 本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-31T22:59:23Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。 我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
  論文  参考訳（メタデータ） (2023-05-26T23:20:48Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• A Blackbox Approach to Best of Both Worlds in Bandits and Beyond [33.13041034490332]
  オンライン学習のためのベスト・オブ・ザ・ワールドズ(Best-of-worlds)アルゴリズムは、敵対政権と敵対政権の両方において、ほぼ最適に後悔する。 両世界の長所から、フォロー・ザ・レギュラライズド・リーダー(FTRL)とオンライン・ミラーダネッセンス(OMD)アルゴリズムの幅広いファミリーへの一般化を提案する。
  論文  参考訳（メタデータ） (2023-02-20T03:42:31Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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