論文の概要: Oracle-Efficient Combinatorial Semi-Bandits

• arxiv url: http://arxiv.org/abs/2510.21431v1
• Date: Fri, 24 Oct 2025 13:07:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 09:00:15.476317
• Title: Oracle-Efficient Combinatorial Semi-Bandits
• Title（参考訳）: Oracle が効率の良い Combinatorial Semi-Bandits を発表
• Authors: Jung-hun Kim, Milan Vojnović, Min-hwan Oh,
• Abstract要約: エージェントがベースアームのサブセットを選択し、個別のフィードバックを受け取るという半帯域問題について検討する。 我々は,厳格な後悔の保証を維持しつつ,オラクル呼び出しを大幅に削減するオラクル効率の高いフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 38.838934613131535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the combinatorial semi-bandit problem where an agent selects a subset of base arms and receives individual feedback. While this generalizes the classical multi-armed bandit and has broad applicability, its scalability is limited by the high cost of combinatorial optimization, requiring oracle queries at every round. To tackle this, we propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees. For the worst-case linear reward setting, our algorithms achieve $\tilde{O}(\sqrt{T})$ regret using only $O(\log\log T)$ oracle queries. We also propose covariance-adaptive algorithms that leverage noise structure for improved regret, and extend our approach to general (non-linear) rewards. Overall, our methods reduce oracle usage from linear to (doubly) logarithmic in time, with strong theoretical guarantees.
• Abstract（参考訳）: 本研究では,エージェントがベースアームのサブセットを選択し,個々のフィードバックを受信する組合せ半帯域問題について検討する。 これは、古典的なマルチアームバンディットを一般化し、幅広い適用性を持つが、そのスケーラビリティは結合最適化のコストが高いため、各ラウンドでオラクルクエリを必要とする。 これを解決するために,私たちは,難解な保証を維持しつつ,オラクル呼び出しを大幅に削減するオラクル効率のよいフレームワークを提案する。 最悪の場合、我々のアルゴリズムは、$O(\log\log T)$ Oracleクエリのみを使用して、$\tilde{O}(\sqrt{T})$ regretを達成する。 また、雑音構造を利用して後悔を改善する共分散適応アルゴリズムを提案し、そのアプローチを一般(非線形)報酬に拡張する。 総じて、本手法は、線形から(二重)対数的な時間におけるオラクルの使用を、強力な理論的保証とともに削減する。

関連論文リスト

• Adaptive Sparsification for Linear Programming [3.735586259382096]
  線形プログラムを多くの制約で解くための一般的なフレームワークを適応的なスペーシングにより$(n gg d)$で導入する。 制約行列に対して$tildeO(sqrtn d3)$ row-queries を用いて、LPの正確な解を求めるクラークソンのアルゴリズムの量子バージョンを示す。 第二に、我々のフレームワークは、パッキング制約が単純であるときに、混成パッキングと問題をカバーするための新しい最先端のアルゴリズムを生み出します。
  論文  参考訳（メタデータ） (2025-10-09T15:36:00Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Projection-Free Online Convex Optimization with Time-Varying Constraints [19.993839085310643]
  逆時間制約によるオンライン凸最適化の設定について検討する。 固定可能な集合を投影することが難しいシナリオによって動機付けられ、線形最適化オラクル(LOO)を通してのみこの集合にアクセスするプロジェクションフリーアルゴリズムを考える。 我々は、長さ$T$のシーケンスで、全体$T$をLOOに呼び出し、$tildeO(T3/4)$ regret w.r.t.の損失と$O(T7/8)$制約違反を保証します。
  論文  参考訳（メタデータ） (2024-02-13T21:13:29Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Distributionally Robust Optimization via Ball Oracle Acceleration [8.417186276756336]
  凸損失の分散ロバスト最適化(DRO)のためのアルゴリズムを開発し,解析する。 この問題に対する既存のアルゴリズムと比較して、最大$epsilon-4/3$の係数で複雑性を改善する。
  論文  参考訳（メタデータ） (2022-03-24T17:31:43Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle [16.50998008977657]
  トンプソンサンプリング(TS)は、バンディット地域に多くの関心を集めている。 1930年代に導入されたが、理論上は近年まで証明されていない。
  論文  参考訳（メタデータ） (2021-11-08T06:40:03Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability [18.45278329799526]
  オフライン回帰オラクルへの$O(log T)$呼び出しだけで統計的に最適な後悔を実現する高速で単純なアルゴリズムを設計する。 この結果は、文脈的帯域幅からオフライン回帰への最初の普遍的かつ最適の還元を提供する。
  論文  参考訳（メタデータ） (2020-03-28T04:16:52Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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