論文の概要: CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption

• arxiv url: http://arxiv.org/abs/2309.16563v1
• Date: Thu, 28 Sep 2023 16:19:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-29 13:38:12.334794
• Title: CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption
• Title（参考訳）: クライムド:非拘束的確率的腐敗を伴うバンディットに対する後悔の低水準と上限
• Authors: Shubhada Agrawal, Timoth\'ee Mathieu, Debabrota Basu, Odalric-Ambrym Maillard
• Abstract要約: 任意の汚職を伴う多武装バンディット設定における後悔最小化問題について検討する。 CRIMED(CRIMED)は,既知分散を伴う帯域幅に対する後悔度を正確に低く抑えるアルゴリズムである。 特に、CRIMEDは$varepsilon$値が$frac12$の汚職を効果的に処理できる。
• 参考スコア（独自算出の注目度）: 21.709840199725015
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the regret-minimisation problem in a multi-armed bandit setting with arbitrary corruptions. Similar to the classical setup, the agent receives rewards generated independently from the distribution of the arm chosen at each time. However, these rewards are not directly observed. Instead, with a fixed $\varepsilon\in (0,\frac{1}{2})$, the agent observes a sample from the chosen arm's distribution with probability $1-\varepsilon$, or from an arbitrary corruption distribution with probability $\varepsilon$. Importantly, we impose no assumptions on these corruption distributions, which can be unbounded. In this setting, accommodating potentially unbounded corruptions, we establish a problem-dependent lower bound on regret for a given family of arm distributions. We introduce CRIMED, an asymptotically-optimal algorithm that achieves the exact lower bound on regret for bandits with Gaussian distributions with known variance. Additionally, we provide a finite-sample analysis of CRIMED's regret performance. Notably, CRIMED can effectively handle corruptions with $\varepsilon$ values as high as $\frac{1}{2}$. Furthermore, we develop a tight concentration result for medians in the presence of arbitrary corruptions, even with $\varepsilon$ values up to $\frac{1}{2}$, which may be of independent interest. We also discuss an extension of the algorithm for handling misspecification in Gaussian model.
• Abstract（参考訳）: 自発的腐敗を伴う多重武装バンディットにおける後悔最小化問題について検討する。 古典的な設定と同様に、エージェントは各時間に選択されたアームの分布から独立して生成される報酬を受け取る。 しかし、これらの報酬は直接観察されていない。 代わりに、固定された$\varepsilon\in (0,\frac{1}{2})$で、エージェントは選択された腕の分布から1-\varepsilon$または確率$\varepsilon$の任意の汚い分布からサンプルを観察する。 重要なのは、これらの腐敗分布に前提を課さないことです。 この設定では、潜在的に非有界な汚職を伴って、特定の腕分布の族に対する後悔に基づく問題依存の低い境界を確立する。 CRIMEDは漸近的に最適化されたアルゴリズムで、ガウス分布と既知の分散を持つ帯域に対する後悔の正確な下限を達成する。 さらに,クリミアの後悔行動の有限サンプル分析も行う。 特にcrimindは、$\varepsilon$の値が$\frac{1}{2}$の腐敗を効果的に処理できる。 さらに,任意の汚職の存在下での中央値に対する厳密な集中結果が,独立利害関係にある場合の$\varepsilon$ から$\frac{1}{2}$ までの値であっても開発される。 また,ガウスモデルにおける誤特定を扱うアルゴリズムの拡張についても述べる。

関連論文リスト

• 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)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
  リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。 各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。 解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
  論文  参考訳（メタデータ） (2022-06-24T18:48:35Z)
• Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm [14.214707836697823]
  破損したバンドイット問題、すなわち、$k$未知の報酬分布を持つ多重武装バンドイット問題について検討する。 本稿では,ハマー推定器上に構築した,破損した盗賊に対する新しいUPB型アルゴリズムを提案する。 異なる報酬分布と異なるレベルの汚職に対する腐敗した包帯の解法におけるHubUCBとSeqHubUCBの有効性を実験的に説明した。
  論文  参考訳（メタデータ） (2022-03-07T07:44:05Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• 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)

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

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