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

• arxiv url: http://arxiv.org/abs/2203.03186v2
• Date: Tue, 21 Mar 2023 10:04:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-24 05:04:11.494961
• Title: Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm
• Title（参考訳）: 自然に崩壊した帯域:レグレットとロバスト最適化アルゴリズムの低い境界
• Authors: Debabrota Basu, Odalric-Ambrym Maillard, Timoth\'ee Mathieu
• Abstract要約: 破損したバンドイット問題、すなわち、$k$未知の報酬分布を持つ多重武装バンドイット問題について検討する。 本稿では,ハマー推定器上に構築した,破損した盗賊に対する新しいUPB型アルゴリズムを提案する。 異なる報酬分布と異なるレベルの汚職に対する腐敗した包帯の解法におけるHubUCBとSeqHubUCBの有効性を実験的に説明した。
• 参考スコア（独自算出の注目度）: 14.214707836697823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the corrupted bandit problem, i.e. a stochastic multi-armed bandit problem with $k$ unknown reward distributions, which are heavy-tailed and corrupted by a history-independent adversary or Nature. To be specific, the reward obtained by playing an arm comes from corresponding heavy-tailed reward distribution with probability $1-\varepsilon \in (0.5,1]$ and an arbitrary corruption distribution of unbounded support with probability $\varepsilon \in [0,0.5)$. First, we provide $\textit{a problem-dependent lower bound on the regret}$ of any corrupted bandit algorithm. The lower bounds indicate that the corrupted bandit problem is harder than the classical stochastic bandit problem with sub-Gaussian or heavy-tail rewards. Following that, we propose a novel UCB-type algorithm for corrupted bandits, namely HubUCB, that builds on Huber's estimator for robust mean estimation. Leveraging a novel concentration inequality of Huber's estimator, we prove that HubUCB achieves a near-optimal regret upper bound. Since computing Huber's estimator has quadratic complexity, we further introduce a sequential version of Huber's estimator that exhibits linear complexity. We leverage this sequential estimator to design SeqHubUCB that enjoys similar regret guarantees while reducing the computational burden. Finally, we experimentally illustrate the efficiency of HubUCB and SeqHubUCB in solving corrupted bandits for different reward distributions and different levels of corruptions.
• Abstract（参考訳）: 腐敗したバンディット問題、すなわちk$未知の報酬分布を持つ確率的多腕バンディット問題は、歴史に依存しない敵意や自然によって重く、腐敗している。 具体的に言うと、腕を弾くことで得られる報酬は、確率 1-\varepsilon \in (0.5,1]$ と確率 $\varepsilon \in [0,0.5)$ の任意の非バウンドサポートの腐敗分布から得られる。 まず、腐敗したbanditアルゴリズムの$\textit{a problem-dependent lower bound on the regret}$を提供します。 下限は、腐敗したバンディット問題は、サブガウシアンやヘビーテールの報酬を持つ古典的な確率的バンディット問題よりも難しいことを示している。 続いて,ロバスト平均推定のためにフーバー推定器を基盤とする,破壊バンドイットのための新しいucb型アルゴリズム,すなわち hubucb を提案する。 フーバー推定器の新たな濃度不等式を利用して、HubUCBがほぼ最適の後悔上限に達することを証明した。 フーバー推定器は2次複雑性を持つので、さらに線形複雑性を示すフーバー推定器の逐次バージョンを導入する。 計算負荷を低減しつつ、同様の後悔の保証を享受するseqhubucbの設計に、このシーケンシャル推定器を利用する。 最後に,異なる報酬分布と異なるレベルの腐敗に対する腐敗したバンディットを解決するために,hubucb と seqhubucb の効率を実験的に示す。

関連論文リスト

• 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)

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

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