論文の概要: Bi-Criteria Optimization for Combinatorial Bandits: Sublinear Regret and Constraint Violation under Bandit Feedback

• arxiv url: http://arxiv.org/abs/2503.12285v1
• Date: Sat, 15 Mar 2025 22:52:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-18 16:00:25.027557
• Title: Bi-Criteria Optimization for Combinatorial Bandits: Sublinear Regret and Constraint Violation under Bandit Feedback
• Title（参考訳）: 組合せ帯域のBi-Criteria最適化:帯域フィードバックによるサブ線形回帰と拘束振動
• Authors: Vaneet Aggarwal, Shweta Jain, Subham Pokhriyal, Christopher John Quinn,
• Abstract要約: マルチアームバンディット(CMAB)におけるビクテリア最適化について検討した。 本稿では,離散二線形オフライン近似アルゴリズムをサブ線形後悔と累積制約違反保証を伴うオンラインアルゴリズムに変換する汎用フレームワークを提案する。 これらのアプリケーションは、オフライン保証をランディットフィードバックの下でオンラインの双基準最適化に適応する際のフレームワークの幅広いユーティリティを強調している。
• 参考スコア（独自算出の注目度）: 27.613888121859393
• License:
• Abstract: In this paper, we study bi-criteria optimization for combinatorial multi-armed bandits (CMAB) with bandit feedback. We propose a general framework that transforms discrete bi-criteria offline approximation algorithms into online algorithms with sublinear regret and cumulative constraint violation (CCV) guarantees. Our framework requires the offline algorithm to provide an $(\alpha, \beta)$-bi-criteria approximation ratio with $\delta$-resilience and utilize $\texttt{N}$ oracle calls to evaluate the objective and constraint functions. We prove that the proposed framework achieves sub-linear regret and CCV, with both bounds scaling as ${O}\left(\delta^{2/3} \texttt{N}^{1/3}T^{2/3}\log^{1/3}(T)\right)$. Crucially, the framework treats the offline algorithm with $\delta$-resilience as a black box, enabling flexible integration of existing approximation algorithms into the CMAB setting. To demonstrate its versatility, we apply our framework to several combinatorial problems, including submodular cover, submodular cost covering, and fair submodular maximization. These applications highlight the framework's broad utility in adapting offline guarantees to online bi-criteria optimization under bandit feedback.
• Abstract（参考訳）: 本稿では,複合型マルチアームバンディット(CMAB)におけるビクテリア最適化について検討する。 本稿では,個別の双基準オフライン近似アルゴリズムをサブ線形後悔と累積制約違反(CCV)を保証したオンラインアルゴリズムに変換する汎用フレームワークを提案する。 我々のフレームワークは、$(\alpha, \beta)$-bi-criteria approximation ratio with $\delta$-resilienceを提供し、目的関数と制約関数を評価するために$\texttt{N}$ oracleコールを使用するためにオフラインアルゴリズムを必要とする。 提案するフレームワークは,いずれも${O}\left(\delta^{2/3} \texttt{N}^{1/3}T^{2/3}\log^{1/3}(T)\right)$である。 重要なことに、このフレームワークはオフラインアルゴリズムをブラックボックスとして$\delta$-resilienceで扱い、既存の近似アルゴリズムをCMAB設定に柔軟な統合を可能にする。 その汎用性を示すために、我々のフレームワークを、部分モジュラー被覆、部分モジュラーコスト被覆、公平な部分モジュラー最大化を含むいくつかの組合せ問題に適用する。 これらのアプリケーションは、オフライン保証をランディットフィードバックの下でオンラインの双基準最適化に適応する際のフレームワークの幅広いユーティリティを強調している。

関連論文リスト

• Stochastic $k$-Submodular Bandits with Full Bandit Feedback [29.705337940879705]
  オンラインの$k$-submodular最適化問題に対して,最初のサブ線形$alpha$-regretバウンダリをフルバンドフィードバックで提示する。 私たちの研究の重要な貢献は、アルゴリズムの堅牢性を分析することです。
  論文  参考訳（メタデータ） (2024-12-14T05:02:53Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization [28.598226670015315]
  本稿では,DR-サブモジュラー最適化のための統合プロジェクションフリーのFrank-Wolfe型アルゴリズムを提案する。 非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明されたサブ線形$alpha$-regret境界を持つ最初のものであるか、あるいは、最先端よりもより優れた$alpha$-regret境界を持つかのいずれかである。
  論文  参考訳（メタデータ） (2024-03-15T07:05:44Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
  離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。 提案手法は準モジュラー地平線における多種多様な応用に適用できる。
  論文  参考訳（メタデータ） (2023-01-30T23:18:06Z)
• Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
  本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。 この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。 本稿では,回帰オラクルに基づくCBwLC(CBwK)のアルゴリズムについて述べる。このアルゴリズムは単純で,計算効率が良く,統計的に最適である。
  論文  参考訳（メタデータ） (2022-11-14T16:08:44Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
  我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。 この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。 近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
  論文  参考訳（メタデータ） (2020-06-01T01:28:44Z)

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

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