論文の概要: Proportional Response: Contextual Bandits for Simple and Cumulative
Regret Minimization
- arxiv url: http://arxiv.org/abs/2307.02108v3
- Date: Fri, 3 Nov 2023 00:54:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 17:42:35.423819
- Title: Proportional Response: Contextual Bandits for Simple and Cumulative
Regret Minimization
- Title(参考訳): 局所応答:単純かつ累積的な回帰最小化のための文脈帯域
- Authors: Sanath Kumar Krishnamurthy, Ruohan Zhan, Susan Athey, Emma Brunskill
- Abstract要約: 本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。
我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
- 参考スコア(独自算出の注目度): 29.579719765255927
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In many applications, e.g. in healthcare and e-commerce, the goal of a
contextual bandit may be to learn an optimal treatment assignment policy at the
end of the experiment. That is, to minimize simple regret. However, this
objective remains understudied. We propose a new family of computationally
efficient bandit algorithms for the stochastic contextual bandit setting, where
a tuning parameter determines the weight placed on cumulative regret
minimization (where we establish near-optimal minimax guarantees) versus simple
regret minimization (where we establish state-of-the-art guarantees). Our
algorithms work with any function class, are robust to model misspecification,
and can be used in continuous arm settings. This flexibility comes from
constructing and relying on "conformal arm sets" (CASs). CASs provide a set of
arms for every context, encompassing the context-specific optimal arm with a
certain probability across the context distribution. Our positive results on
simple and cumulative regret guarantees are contrasted with a negative result,
which shows that no algorithm can achieve instance-dependent simple regret
guarantees while simultaneously achieving minimax optimal cumulative regret
guarantees.
- Abstract(参考訳): 医療や電子商取引など多くの応用において、文脈的盗賊の目標は、実験の終わりに最適な治療の割り当てポリシーを学ぶことであるかもしれない。
つまり、単純な後悔を最小限に抑えることです。
しかし、この目的はまだ未定である。
本稿では,確率的文脈的帯域設定のための計算効率の良い帯域幅アルゴリズムの新たなファミリを提案する。そこでは,累積後悔最小化(準最適最小化)と単純後悔最小化(最先端保証の確立)の重みをチューニングパラメータが決定する。
我々のアルゴリズムは任意の関数クラスで動作し、モデルの誤特定に頑健であり、継続的なarm設定で使用できる。
この柔軟性は、"conformal arm sets"(cass)の構築と依存から生まれる。
CASは、コンテキスト分布にまたがる特定の確率で、コンテキスト固有の最適アームを含む、コンテキスト毎に一組のアームを提供する。
単純かつ累積的後悔保証に対する我々の肯定的な結果は負の結果と対比され、最小限の累積後悔保証を同時に達成しながら、インスタンス依存の単純な後悔保証を達成できないことを示す。
関連論文リスト
- Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳(メタデータ) (2024-09-27T16:46:02Z) - Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
論文 参考訳(メタデータ) (2024-05-25T08:09:36Z) - Batched Nonparametric Contextual Bandits [21.031965676746776]
バッチ制約下での非パラメトリック文脈帯域について検討する。
最適な後悔を実現する新しいバッチ学習アルゴリズムを提案する。
我々の理論的結果は、非パラメトリックな文脈的帯域幅では、ほぼ一定数のポリシー更新が最適な後悔をもたらすことを示唆している。
論文 参考訳(メタデータ) (2024-02-27T18:06:20Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-09-15T16:59:19Z) - 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) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - Constrained regret minimization for multi-criterion multi-armed bandits [5.349852254138086]
リスク制約を条件として,所与の時間的地平線上での後悔の最小化の問題について検討する。
本稿では,対数的後悔を保証するリスク制約付き低信頼境界アルゴリズムを提案する。
我々は,リスク制約付き後悔最小化アルゴリズムの性能に低い限界を証明した。
論文 参考訳(メタデータ) (2020-06-17T04:23:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。