論文の概要: Constrained Stochastic Submodular Maximization with State-Dependent
Costs
- arxiv url: http://arxiv.org/abs/2111.06037v1
- Date: Thu, 11 Nov 2021 03:20:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-12 22:40:05.951803
- Title: Constrained Stochastic Submodular Maximization with State-Dependent
Costs
- Title（参考訳）: 状態依存コストによる制約付き確率部分モジュラー最大化
- Authors: Shaojie Tang
- Abstract要約: 制約付き部分モジュラー問題と状態依存コストについて検討する。
我々の目的は、内的制約と外的制約の両方を対象とする目的関数を最大化することである。
- 参考スコア（独自算出の注目度）: 26.171841086317574
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the constrained stochastic submodular maximization
problem with state-dependent costs. The input of our problem is a set of items
whose states (i.e., the marginal contribution and the cost of an item) are
drawn from a known probability distribution. The only way to know the realized
state of an item is to select that item. We consider two constraints, i.e.,
\emph{inner} and \emph{outer} constraints. Recall that each item has a
state-dependent cost, and the inner constraint states that the total
\emph{realized} cost of all selected items must not exceed a give budget. Thus,
inner constraint is state-dependent. The outer constraint, one the other hand,
is state-independent. It can be represented as a downward-closed family of sets
of selected items regardless of their states. Our objective is to maximize the
objective function subject to both inner and outer constraints. Under the
assumption that larger cost indicates larger "utility", we present a constant
approximate solution to this problem.
- Abstract（参考訳）: 本稿では,制約付き確率的極大化問題と状態依存コストについて検討する。
問題の入力は、既知の確率分布から状態(すなわち、アイテムの限界寄与とコスト)が引き出される項目の集合である。
アイテムの実際の状態を知る唯一の方法は、そのアイテムを選択することです。
我々は二つの制約、すなわち \emph{inner} と \emph{outer} を考える。
各項目が状態依存コストを持ち、内部制約は、選択された項目の合計 \emph{realized} コストが付与予算を超過してはならないことを言い換える。
したがって、内部制約は状態依存である。
一方、外部制約は状態非依存である。
状態に関わらず、選択されたアイテムのセットの下位に閉じたファミリーとして表現することができる。
我々の目標は、内外制約の対象となる目的関数を最大化することである。
より大きなコストがより大きな「有効性」を示すという仮定の下で、この問題に対する一定の近似解を提示する。
関連論文リスト
- Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Towards a resolution of the spin alignment problem [1.6317061277457001]
最近導入されたスピンアライメント予想から着想を得た最適化問題のクラスについて検討する。
我々の研究の動機は、最近導入されたスピンアライメント予想である。
論文 参考訳（メタデータ） (2023-07-13T16:47:55Z) - Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with
Application to Fairness [1.6741394365746018]
我々は,各ラウンドにおいてスカラー報酬が得られ,ベクトル値のコストがかかる問題であるknapsacks[CBwK]のコンテキスト的帯域幅問題を考える。
予測段階更新に基づく二元的戦略を導入し,多元対数項まで$sqrtT$の総コスト制約を扱えるようにした。
論文 参考訳（メタデータ） (2023-05-25T07:41:35Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Worst-Case Adaptive Submodular Cover [19.29174615532181]
最悪の場合,適応的部分モジュラー被覆問題について検討する。
タイトな$(log (Q/eta)+1)$-approximationポリシーを開発します。
また、最悪の最大被覆問題も研究している。
論文 参考訳（メタデータ） (2022-10-25T01:38:35Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint [26.171841086317574]
ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。
アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。
私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
論文 参考訳（メタデータ） (2021-04-10T20:11:11Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
2つの平行な均質層からなる構造は、その幅が$l_j$と$l_j$であり、それらの間の距離が$r$を同時に0に縮めるように、極限において研究される。
非自明な有界状態の存在は、ディラックのデルタ関数の微分の形で圧縮ポテンシャルの特別な例を含む、スクイーズ極限で証明される。
有限系の有限個の有界状態から、一個の有界状態が圧縮された系で生き残るシナリオを詳述する。
論文 参考訳（メタデータ） (2020-11-23T14:40:27Z) - Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。
ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
論文 参考訳（メタデータ） (2020-02-29T23:50:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。