論文の概要: Linear Contextual Bandits with Adversarial Corruptions
- arxiv url: http://arxiv.org/abs/2110.12615v1
- Date: Mon, 25 Oct 2021 02:53:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-26 14:42:07.314186
- Title: Linear Contextual Bandits with Adversarial Corruptions
- Title（参考訳）: 敵対的腐敗を伴う線形文脈的バンディット
- Authors: Heyang Zhao and Dongruo Zhou and Quanquan Gu
- Abstract要約: 本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
- 参考スコア（独自算出の注目度）: 91.38793800392108
- 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 interaction between the player and a possibly infinite
decision set is contaminated by an adversary that can corrupt the reward up to
a corruption level $C$ measured by the sum of the largest alteration on rewards
in each round. We present a variance-aware algorithm that is adaptive to the
level of adversarial contamination $C$. The key algorithmic design includes (1)
a multi-level partition scheme of the observed data, (2) a cascade of
confidence sets that are adaptive to the level of the corruption, and (3) a
variance-aware confidence set construction that can take advantage of
low-variance reward. We further prove that the regret of the proposed algorithm
is $\tilde{O}(C^2d\sqrt{\sum_{t = 1}^T \sigma_t^2} + C^2R\sqrt{dT})$, where $d$
is the dimension of context vectors, $T$ is the number of rounds, $R$ is the
range of noise and $\sigma_t^2,t=1\ldots,T$ are the variances of instantaneous
reward. We also prove a gap-dependent regret bound for the proposed algorithm,
which is instance-dependent and thus leads to better performance on good
practical instances. To the best of our knowledge, this is the first
variance-aware corruption-robust algorithm for contextual bandits. Experiments
on synthetic data corroborate our theory.
- Abstract（参考訳）: 各ラウンドにおける最大の報酬変更の合計によって測定された損失レベル$C$までの報酬を汚すことができる敵によって、プレイヤーと潜在的に無限の判定セットとの相互作用が汚染されるような、敵の汚職の存在下での線形文脈的包帯問題について検討する。
本研究では, 逆汚染レベル$c$に適応した分散認識アルゴリズムを提案する。
鍵となるアルゴリズム設計は、(1)観測データの多レベル分割スキーム、(2)腐敗のレベルに適応した信頼セットのカスケード、(3)低分散報酬を活用可能な分散認識信頼セット構成を含む。
さらに、提案アルゴリズムの後悔は$\tilde{O}(C^2d\sqrt{\sum_{t = 1}^T \sigma_t^2} + C^2R\sqrt{dT})$であり、$d$は文脈ベクトルの次元、$T$はラウンドの数、$R$はノイズの範囲、$\sigma_t^2,t=1\ldots,T$は即時報酬の分散であることを示す。
また,提案アルゴリズムはインスタンス依存であり,より実用的なインスタンスの性能向上に繋がる,ギャップ依存の後悔を証明した。
我々の知る限りでは、このアルゴリズムは文脈的盗賊のための初めての分散対応汚職処理アルゴリズムである。
合成データの実験は我々の理論を裏付ける。
関連論文リスト
- Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - 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) - Minimax Rates for Robust Community Detection [19.229475414802213]
逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。
我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。
アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
論文 参考訳（メタデータ） (2022-07-25T04:45:16Z) - Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial
Corruptions [98.75618795470524]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-13T17:58:58Z) - 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) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。