論文の概要: Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions

• arxiv url: http://arxiv.org/abs/2205.06811v1
• Date: Fri, 13 May 2022 17:58:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-16 12:34:27.398930
• Title: Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions
• Title（参考訳）: 逆破壊を伴う線形文脈バンディットの近似最適アルゴリズム
• Authors: Jiafan He and Dongruo Zhou and Tong Zhang and Quanquan Gu
• Abstract要約: 本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 98.75618795470524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the linear contextual bandit problem in the presence of adversarial corruption, where the reward at each round is corrupted by an adversary, and the corruption level (i.e., the sum of corruption magnitudes over the horizon) is $C\geq 0$. The best-known algorithms in this setting are limited in that they either are computationally inefficient or require a strong assumption on the corruption, or their regret is at least $C$ times worse than the regret without corruption. In this paper, to overcome these limitations, we propose a new algorithm based on the principle of optimism in the face of uncertainty. At the core of our algorithm is a weighted ridge regression where the weight of each chosen action depends on its confidence up to some threshold. We show that for both known $C$ and unknown $C$ cases, our algorithm with proper choice of hyperparameter achieves a regret that nearly matches the lower bounds. Thus, our algorithm is nearly optimal up to logarithmic factors for both cases. Notably, our algorithm achieves the near-optimal regret for both corrupted and uncorrupted cases ($C=0$) simultaneously.
• Abstract（参考訳）: 我々は,各ラウンドの報酬が敵意によって損なわれ,腐敗レベル(地平線上の汚職等級の合計)が$c\geq 0$である,敵対的汚職の存在下での直線的文脈的バンディット問題について検討した。 この設定における最もよく知られたアルゴリズムは、計算量的に非効率であるか、腐敗に対する強い仮定を必要とするか、または彼らの後悔が腐敗のない後悔よりも少なくとも$c$2であるという点で制限されている。 本稿では,これらの制約を克服するために,不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。 アルゴリズムの中核は重み付きリッジ回帰であり、選択された各アクションの重みは、その信頼度をしきい値まで依存する。 既知の$c$と未知の$c$ケースの両方において、ハイパーパラメーターを適切に選択したアルゴリズムは、下限にほぼ一致することを後悔する。 したがって、このアルゴリズムは両方の場合の対数係数にほぼ最適である。 特に, このアルゴリズムは, 破損事例と破損事例の両方に対して, ほぼ最適の後悔を同時に達成する(C=0$)。

関連論文リスト

• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems [27.68461396741871]
  最適ロバスト性は汚損量に対する平方根依存性によって表現できることを示す。 多武装バンディット問題に対しては、対数係数までほぼ狭い下界も提供する。
  論文  参考訳（メタデータ） (2021-09-22T18:26:45Z)
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning [43.279169081740726]
  基礎システムの報酬と遷移確率の両方において,未知の敵的腐敗下でのエピソディック強化学習について検討した。 既存の結果と比較して、総汚職の点で厳密により良い後悔の境界を達成する新しいアルゴリズムを提案します。 その結果、汚職防止政策のメタアルゴリズムとプラグインフリーのサブアルゴリズムを組み合わせた一般的なアルゴリズムフレームワークが得られた。
  論文  参考訳（メタデータ） (2021-02-13T07:04:23Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)

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

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