論文の概要: Contextual Bandits with Stage-wise Constraints

• arxiv url: http://arxiv.org/abs/2401.08016v1
• Date: Mon, 15 Jan 2024 23:58:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-17 15:36:38.679775
• Title: Contextual Bandits with Stage-wise Constraints
• Title（参考訳）: 段階的制約を伴う文脈的バンディット
• Authors: Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett
• Abstract要約: 段階的制約(各ラウンドにおける制約)の存在下での文脈的包帯について検討する。 本稿では,この問題に対する高信頼度有界アルゴリズムを提案し,それに対するT$ラウンドの後悔を証明した。
• 参考スコア（独自算出の注目度）: 46.412612374393895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study contextual bandits in the presence of a stage-wise constraint (a constraint at each round), when the constraint must be satisfied both with high probability and in expectation. Obviously the setting where the constraint is in expectation is a relaxation of the one with high probability. We start with the linear case where both the contextual bandit problem (reward function) and the stage-wise constraint (cost function) are linear. In each of the high probability and in expectation settings, we propose an upper-confidence bound algorithm for the problem and prove a $T$-round regret bound for it. Our algorithms balance exploration and constraint satisfaction using a novel idea that scales the radii of the reward and cost confidence sets with different scaling factors. We also prove a lower-bound for this constrained problem, show how our algorithms and analyses can be extended to multiple constraints, and provide simulations to validate our theoretical results. In the high probability setting, we describe the minimum requirements for the action set in order for our algorithm to be tractable. In the setting that the constraint is in expectation, we further specialize our results to multi-armed bandits and propose a computationally efficient algorithm for this setting with regret analysis. Finally, we extend our results to the case where the reward and cost functions are both non-linear. We propose an algorithm for this case and prove a regret bound for it that characterize the function class complexity by the eluder dimension.
• Abstract（参考訳）: 制約を高い確率と期待で満たさなければならない段階的制約(各ラウンドにおける制約)の存在下での文脈的バンディットについて検討する。 明らかに、制約が期待されている設定は、高い確率を持つ制約の緩和である。 まず、文脈的帯域問題(逆関数)と段階的制約(コスト関数)の両方が線型である線形ケースから始める。 高い確率と期待設定のそれぞれにおいて,この問題に対する上位信頼バウンドアルゴリズムを提案し,それに対してt$roundの後悔を証明した。 我々のアルゴリズムは、異なるスケーリング要因で報酬とコストの信頼性セットの根源をスケールする新しいアイデアを用いて、探索と制約満足度をバランスさせる。 また、この制約付き問題に対する下限を証明し、アルゴリズムと解析がどのように複数の制約に拡張できるかを示し、理論結果を検証するためのシミュレーションを提供する。 高確率設定では、アルゴリズムを扱いやすいものにするために、アクションセットの最小要件を記述する。 制約が期待されている設定では,複数腕のバンディットを対象とし,後悔解析による計算効率の高いアルゴリズムを提案する。 最後に、報酬関数とコスト関数の両方が非線形である場合に、結果を拡張します。 そこで本研究では,関数クラスの複雑性をエルダー次元で特徴づけるアルゴリズムを提案し,それに対する後悔を証明した。

関連論文リスト

• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
  我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。 私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2024-05-25T08:09:36Z)
• Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
  この仕事の動機は、再現可能な機械学習の需要の増加にある。 特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
  論文  参考訳（メタデータ） (2024-02-12T03:31:34Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。 本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。 本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2022-03-29T14:02:03Z)
• 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)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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