論文の概要: Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm

• arxiv url: http://arxiv.org/abs/2203.03186v1
• Date: Mon, 7 Mar 2022 07:44:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-08 18:29:54.337062
• Title: Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm
• Title（参考訳）: 自然に崩壊した帯域:レグレットとロバスト最適化アルゴリズムの低い境界
• Authors: Debabrota Basu, Odalric-Ambrym Maillard, Timoth\'ee Mathieu
• Abstract要約: 盗賊問題を、未知のヘビーテールと破損した報酬分布や武器で研究する。 我々の設定では、破壊されていない報酬は重く、腐敗した報酬は無拘束であるかもしれない。 破損した包帯や重尾の包帯は、破損していない包帯や軽尾の包帯よりも厳格に硬いことを示す。
• 参考スコア（独自算出の注目度）: 14.214707836697823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the stochastic bandits problem with $k$ unknown heavy-tailed and corrupted reward distributions or arms with time-invariant corruption distributions. At each iteration, the player chooses an arm. Given the arm, the environment returns an uncorrupted reward with probability $1-\varepsilon$ and an arbitrarily corrupted reward with probability $\varepsilon$. In our setting, the uncorrupted reward might be heavy-tailed and the corrupted reward might be unbounded. We prove a lower bound on the regret indicating that the corrupted and heavy-tailed bandits are strictly harder than uncorrupted or light-tailed bandits. We observe that the environments can be categorised into hardness regimes depending on the suboptimality gap $\Delta$, variance $\sigma$, and corruption proportion $\epsilon$. Following this, we design a UCB-type algorithm, namely HuberUCB, that leverages Huber's estimator for robust mean estimation. HuberUCB leads to tight upper bounds on regret in the proposed corrupted and heavy-tailed setting. To derive the upper bound, we prove a novel concentration inequality for Huber's estimator, which might be of independent interest.
• Abstract（参考訳）: 本稿では, 確率的バンディット問題を, 時間不変な汚職分布を持つ未知のヘビーテール, 破損した報酬分布, 腕を用いて検討する。 各イテレーションで、プレイヤーは腕を選択する。 アームが与えられると、環境は、確率1-\varepsilon$と、確率$\varepsilon$で任意に破損した報酬を返される。 我々の設定では、破壊されていない報酬は重く、腐敗した報酬は無拘束であるかもしれない。 腐敗し重い尾の帯状物は、腐敗していない帯状物や軽い尾状帯状物よりも厳格に硬いことを示す後悔の限界が下方にあることを証明した。 我々は,環境を,準最適ギャップ$\delta$,分散$\sigma$,汚職率$\epsilon$に応じて,ハードネスレジームに分類できることを観察した。 次に,Huber の推定器を頑健な平均推定に利用する UCB 型アルゴリズムである HuberUCB を設計する。 HuberUCBは、提案された腐敗した重尾の環境での後悔について、厳しい上限に達した。 上界を導出するために、ハマー推定器の新たな濃度不等式を証明し、これは独立な興味を持つかもしれない。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption [21.709840199725015]
  任意の汚職を伴う多武装バンディット設定における後悔最小化問題について検討する。 CRIMED(CRIMED)は,既知分散を伴う帯域幅に対する後悔度を正確に低く抑えるアルゴリズムである。 特に、CRIMEDは$varepsilon$値が$frac12$の汚職を効果的に処理できる。
  論文  参考訳（メタデータ） (2023-09-28T16:19:53Z)
• Robust Lipschitz Bandits to Adversarial Corruptions [61.85150061213987]
  リプシッツ・バンディット(英: Lipschitz bandit)は、計量空間上で定義された連続アーム集合を扱うバンディットの変種である。 本稿では,敵対的腐敗の存在下でのリプシッツ・バンディットの新たな問題を紹介する。 我々の研究は、両タイプの敵の下でサブ線形後悔を達成できるロバストなリプシッツ・バンディットアルゴリズムの最初のラインを提示する。
  論文  参考訳（メタデータ） (2023-05-29T18:16:59Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs [27.636407641546914]
  実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。 非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-26T17:30:44Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• 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)

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

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