論文の概要: Submodular Bandit Problem Under Multiple Constraints

• arxiv url: http://arxiv.org/abs/2006.00661v5
• Date: Mon, 29 Mar 2021 02:02:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-26 06:06:00.866650
• Title: Submodular Bandit Problem Under Multiple Constraints
• Title（参考訳）: 多重制約下における部分モジュラバンド問題
• Authors: Sho Takemori, Masahiro Sato, Takashi Sonoda, Janmajay Singh, Tomoko Ohkuma
• Abstract要約: 我々は、$l$knapsacksと$k$-system制約の交わりの下で、部分モジュラーバンディット問題を導入する。 この問題を解決するために,標準あるいは修正された高信頼境界に適応的に焦点をあてる非グレーディアルゴリズムを提案する。 近似比が高速アルゴリズムのそれと一致するような近似後悔の確率の高い上限を提供する。
• 参考スコア（独自算出の注目度）: 8.100450025624443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The linear submodular bandit problem was proposed to simultaneously address diversified retrieval and online learning in a recommender system. If there is no uncertainty, this problem is equivalent to a submodular maximization problem under a cardinality constraint. However, in some situations, recommendation lists should satisfy additional constraints such as budget constraints, other than a cardinality constraint. Thus, motivated by diversified retrieval considering budget constraints, we introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. Here $k$-system constraints form a very general class of constraints including cardinality constraints and the intersection of $k$ matroid constraints. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast offline algorithm. Moreover, we perform experiments under various combinations of constraints using a synthetic and two real-world datasets and demonstrate that our proposed methods outperform the existing baselines.
• Abstract（参考訳）: 多様な検索とオンライン学習を同時に行うために,線形部分モジュラー帯域問題を提案した。 不確実性がなければ、この問題は濃度制約の下での部分モジュラー最大化問題と等価である。 しかしながら、いくつかの状況では、リコメンデーションリストは、基準制約以外の予算制約のような追加の制約を満たすべきである。 そこで,予算制約を考慮した多角化検索により,$l$knapsacksと$k$-system制約の交点の下で,サブモジュラー帯域問題を導入する。 ここで、$k$-システム制約は、濃度制約や$k$ matroid制約の交叉を含む非常に一般的な制約クラスを形成する。 この問題を解決するために,標準あるいは修正された上部信頼境界に適応的に焦点をあてる非学習アルゴリズムを提案する。 近似係数が高速オフラインアルゴリズムの値と一致するような近似後悔の確率の高い上限を与える。 さらに,2つの実世界のデータセットを用いた制約の組み合わせによる実験を行い,提案手法が既存のベースラインより優れていることを示す。

関連論文リスト

• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• Submodular Maximization under the Intersection of Matroid and Knapsack Constraints [23.0838604893412]
  我々は、よく使われる2つの制約、すなわち$k$matroid 制約と $m$-knapsack 制約の交わる部分モジュラー演算の問題を考察する。 我々は、SPROUTOUTが最先端のアルゴリズムを組み込むよりも、SPR時間近似の保証を実現できることを証明した。 映画レコメンデーションと重み付きマックスカットの応用実験は、実際にSPROUT++の優位性を実証している。
  論文  参考訳（メタデータ） (2023-07-18T02:37:14Z)
• 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)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
  本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。 制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-12T06:13:33Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)

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

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