論文の概要: On Optimal Robustness to Adversarial Corruption in Online Decision Problems

• arxiv url: http://arxiv.org/abs/2109.10963v1
• Date: Wed, 22 Sep 2021 18:26:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-24 15:14:31.460270
• Title: On Optimal Robustness to Adversarial Corruption in Online Decision Problems
• Title（参考訳）: オンライン決定問題における逆転破壊に対する最適ロバスト性について
• Authors: Shinji Ito
• Abstract要約: 最適ロバスト性は汚損量に対する平方根依存性によって表現できることを示す。 多武装バンディット問題に対しては、対数係数までほぼ狭い下界も提供する。
• 参考スコア（独自算出の注目度）: 27.68461396741871
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers two fundamental sequential decision-making problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus on stochastic regimes in which an adversary may corrupt losses, and we investigate what level of robustness can be achieved against adversarial corruptions. The main contribution of this paper is to show that optimal robustness can be expressed by a square-root dependency on the amount of corruption. More precisely, we show that two classes of algorithms, anytime Hedge with decreasing learning rate and algorithms with second-order regret bounds, achieve $O( \frac{\log N}{\Delta} + \sqrt{ \frac{C \log N }{\Delta} } )$-regret, where $N, \Delta$, and $C$ represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide a matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi-armed bandit problem, we also provide a nearly tight lower bound up to a logarithmic factor.
• Abstract（参考訳）: 本稿では,専門家のアドバイスによる予測問題とマルチアームのバンディット問題という2つの基本的な意思決定問題について考察する。 我々は,敵が損失を損なう確率的体制に着目し,敵の腐敗に対してどのようなレベルの堅牢性が達成できるかを検討する。 本論文の主な貢献は, 汚損量に対する平方根依存性により, 最適ロバスト性を表現することができることを示すことである。 より正確には、学習率を下げるHedgeと、2階の後悔境界を持つアルゴリズムの2つのクラスが$O( \frac{\log N}{\Delta} + \sqrt{ \frac{C \log N }{\Delta} } )$-regretに達し、$N, \Delta$, $C$はそれぞれ専門家の数、ギャップパラメータ、汚職レベルを表す。 私たちはさらに、この後悔のバウンドが定数に密接であるような、一致する下限も提供します。 マルチアームのバンディット問題に対しては,対数係数までほぼ厳密な下限を提供する。

関連論文リスト

• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• 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)
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions [98.75618795470524]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T17:58:58Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• 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)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)

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

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