論文の概要: Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with
Application to Fairness
- arxiv url: http://arxiv.org/abs/2305.15807v2
- Date: Thu, 26 Oct 2023 11:52:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-28 01:47:41.173440
- Title: Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with
Application to Fairness
- Title（参考訳）: クナプサックの文脈帯域における小さな総コスト制約と公正性への応用
- Authors: Evgenii Chzhen (LMO, CELESTE), Christophe Giraud (LMO, CELESTE), Zhen
Li, Gilles Stoltz (LMO, CELESTE, HEC Paris)
- Abstract要約: 我々は,各ラウンドにおいてスカラー報酬が得られ,ベクトル値のコストがかかる問題であるknapsacks[CBwK]のコンテキスト的帯域幅問題を考える。
予測段階更新に基づく二元的戦略を導入し,多元対数項まで$sqrtT$の総コスト制約を扱えるようにした。
- 参考スコア（独自算出の注目度）: 1.6741394365746018
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider contextual bandit problems with knapsacks [CBwK], a problem where
at each round, a scalar reward is obtained and vector-valued costs are
suffered. The learner aims to maximize the cumulative rewards while ensuring
that the cumulative costs are lower than some predetermined cost constraints.
We assume that contexts come from a continuous set, that costs can be signed,
and that the expected reward and cost functions, while unknown, may be
uniformly estimated -- a typical assumption in the literature. In this setting,
total cost constraints had so far to be at least of order $T^{3/4}$, where $T$
is the number of rounds, and were even typically assumed to depend linearly on
$T$. We are however motivated to use CBwK to impose a fairness constraint of
equalized average costs between groups: the budget associated with the
corresponding cost constraints should be as close as possible to the natural
deviations, of order $\sqrt{T}$. To that end, we introduce a dual strategy
based on projected-gradient-descent updates, that is able to deal with
total-cost constraints of the order of $\sqrt{T}$ up to poly-logarithmic terms.
This strategy is more direct and simpler than existing strategies in the
literature. It relies on a careful, adaptive, tuning of the step size.
- Abstract（参考訳）: 我々は,各ラウンドにおいてスカラー報酬が得られ,ベクトル値のコストがかかる問題であるknapsacks[CBwK]のコンテキスト的帯域幅問題を考える。
学習者は、累積費用が所定のコスト制約よりも低いことを保証しつつ累積報酬を最大化する。
我々は、文脈は連続的な集合から来ており、コストは署名可能であり、期待される報酬とコスト関数は未知であるが、均一に推定されるかもしれないと仮定する。
この設定では、総コスト制約は少なくとも$T^{3/4}$であり、ここでは$T$はラウンドの数であり、通常は$T$に線形に依存すると仮定されていた。
しかしながら、CBwK を用いて、グループ間の平均コストの等化の公正性制約を課す動機がある:対応するコスト制約に関連する予算は、$\sqrt{T}$ の自然偏差にできるだけ近いべきである。
そこで本研究では,予測段階の更新に基づく2つの戦略を導入し,多対数項まで$\sqrt{T}$の総コスト制約を扱えるようにした。
この戦略は文学における既存の戦略よりも直接的で単純である。
ステップサイズの慎重で適応的なチューニングに依存しています。
関連論文リスト
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。
最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。
この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
論文 参考訳（メタデータ） (2024-05-10T16:22:33Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Contextual Bandits with Knapsacks for a Conversion Model [1.8659901274492419]
我々は、報酬生成とコストベクターの間の基盤構造を持つ、クナプサックによる文脈的包帯について考察する。
本稿で紹介する手法は後者にも適用可能であることを示す。
すなわち、各ラウンドで表される適応ポリシーは、変換の確率が$a$と$mathbfx$の上限信頼度推定に基づいて表される。
論文 参考訳（メタデータ） (2022-06-01T08:29:07Z) - On Dynamic Pricing with Covariates [6.6543199581017625]
UCBとThompsonのサンプリングに基づく価格設定アルゴリズムは、$O(dsqrtTlog T)$ regret upper boundを実現できることを示す。
私たちの後悔に対する上限は、対数的要因までの下位境界と一致します。
論文 参考訳（メタデータ） (2021-12-25T16:30:13Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。