論文の概要: Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification

• arxiv url: http://arxiv.org/abs/2410.07533v1
• Date: Thu, 17 Oct 2024 18:29:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 16:36:31.293177
• Title: Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
• Title（参考訳）: 破壊・破壊的線形帯域:最小最適性とギャップ依存的ミス種別
• Authors: Haolin Liu, Artin Tajdini, Andrew Wagenmaker, Chen-Yu Wei,
• Abstract要約: 線形バンディットでは、学習者が腐敗した報酬に直面するとき、効果的に学習できるのか? 汚職レベルは学習者が選択した行動に依存するが、汚職レベルは学習者が選択した行動に依存しない。 線形包帯については, 強い汚職と弱い汚職下でのミニマックス後悔のギャップを, 完全に特徴づける。
• 参考スコア（独自算出の注目度）: 17.288347876319126
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In linear bandits, how can a learner effectively learn when facing corrupted rewards? While significant work has explored this question, a holistic understanding across different adversarial models and corruption measures is lacking, as is a full characterization of the minimax regret bounds. In this work, we compare two types of corruptions commonly considered: strong corruption, where the corruption level depends on the action chosen by the learner, and weak corruption, where the corruption level does not depend on the action chosen by the learner. We provide a unified framework to analyze these corruptions. For stochastic linear bandits, we fully characterize the gap between the minimax regret under strong and weak corruptions. We also initiate the study of corrupted adversarial linear bandits, obtaining upper and lower bounds with matching dependencies on the corruption level. Next, we reveal a connection between corruption-robust learning and learning with gap-dependent mis-specification, a setting first studied by Liu et al. (2023a), where the misspecification level of an action or policy is proportional to its suboptimality. We present a general reduction that enables any corruption-robust algorithm to handle gap-dependent misspecification. This allows us to recover the results of Liu et al. (2023a) in a black-box manner and significantly generalize them to settings like linear MDPs, yielding the first results for gap-dependent misspecification in reinforcement learning. However, this general reduction does not attain the optimal rate for gap-dependent misspecification. Motivated by this, we develop a specialized algorithm that achieves optimal bounds for gap-dependent misspecification in linear bandits, thus answering an open question posed by Liu et al. (2023a).
• Abstract（参考訳）: 線形バンディットでは、学習者が腐敗した報酬に直面するとき、効果的に学習できるのか? 重要な研究がこの問題を探求してきたが、様々な対立モデルと汚職対策の全体的理解が欠如しており、ミニマックスの後悔境界の完全な特徴付けが欠けている。 本研究は,学習者が選択した行動に依存する強い汚職と,学習者が選択した行動に依存しない弱い汚職の2種類の汚職を比較した。 これらの腐敗を分析するための統一的なフレームワークを提供する。 確率線形ブレイディットでは, 強い汚職と弱い汚職下でのミニマックス後悔のギャップを, 完全に特徴づける。 また, 汚損した対向線形包帯の研究を開始し, 汚損レベルに依存した上下境界を求める。 次に,Lou et al (2023a) が最初に研究した設定では,行動や政策の誤特定レベルがその最適度に比例する。 本稿では,任意の汚損防止アルゴリズムがギャップ依存的不特定性に対処できる一般還元法を提案する。 これにより、Lu et al (2023a) の結果をブラックボックス方式で復元し、線形MDPのような設定に著しく一般化し、強化学習におけるギャップ依存的不特定性の最初の結果が得られる。 しかし、この一般化はギャップ依存的不特定化の最適速度を達成できない。 そこで我々は,Lou et al (2023a) が提案する開問題に答えるため,線形包帯におけるギャップ依存的不特定化の最適境界を求めるアルゴリズムを開発した。

関連論文リスト

• Enhancing Infrared Small Target Detection Robustness with Bi-Level Adversarial Framework [61.34862133870934]
  本稿では,異なる汚職の存在下での検出の堅牢性を促進するために,二段階の対向的枠組みを提案する。 我々の手法は広範囲の汚職で21.96%のIOUを著しく改善し、特に一般ベンチマークで4.97%のIOUを推進している。
  論文  参考訳（メタデータ） (2023-09-03T06:35:07Z)
• Corruptions of Supervised Learning Problems: Typology and Mitigations [11.294508617469905]
  我々は情報理論の観点から汚職の一般的な理論を発展させる。 ここでは確率分布の変化に注目します。 この研究は、ラベルと属性の両方に対する共同や依存的な汚職から生じる複雑さに光を当てている。
  論文  参考訳（メタデータ） (2023-07-17T16:57:01Z)
• Robust Lipschitz Bandits to Adversarial Corruptions [61.85150061213987]
  リプシッツ・バンディット(英: Lipschitz bandit)は、計量空間上で定義された連続アーム集合を扱うバンディットの変種である。 本稿では,敵対的腐敗の存在下でのリプシッツ・バンディットの新たな問題を紹介する。 我々の研究は、両タイプの敵の下でサブ線形後悔を達成できるロバストなリプシッツ・バンディットアルゴリズムの最初のラインを提示する。
  論文  参考訳（メタデータ） (2023-05-29T18:16:59Z)
• 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)
• Soft Diffusion: Score Matching for General Corruptions [84.26037497404195]
  我々は,任意の線形汚職過程のスコア関数を確実に学習するSoft Score Matchingと呼ばれる新しい目的を提案する。 本研究の目的は, 汚職過程の家族に対して, 適正な規則性条件下での確率の勾配を学習することである。 提案手法はCelebA-64上でのFIDスコアを1.85ドルで達成し,従来の線形拡散モデルよりも優れていた。
  論文  参考訳（メタデータ） (2022-09-12T17:45:03Z)
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions [98.75618795470524]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T17:58:58Z)
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems [27.68461396741871]
  最適ロバスト性は汚損量に対する平方根依存性によって表現できることを示す。 多武装バンディット問題に対しては、対数係数までほぼ狭い下界も提供する。
  論文  参考訳（メタデータ） (2021-09-22T18:26:45Z)
• Using the Overlapping Score to Improve Corruption Benchmarks [6.445605125467574]
  本稿では、汚職ベンチマークの欠陥を明らかにするために、汚職重複スコアと呼ばれる指標を提案する。 汚職間の重複を考慮に入れれば、既存のベンチマークを改善したり、より良いベンチマークを構築するのに役立ちます。
  論文  参考訳（メタデータ） (2021-05-26T06:42:54Z)
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning [43.279169081740726]
  基礎システムの報酬と遷移確率の両方において,未知の敵的腐敗下でのエピソディック強化学習について検討した。 既存の結果と比較して、総汚職の点で厳密により良い後悔の境界を達成する新しいアルゴリズムを提案します。 その結果、汚職防止政策のメタアルゴリズムとプラグインフリーのサブアルゴリズムを組み合わせた一般的なアルゴリズムフレームワークが得られた。
  論文  参考訳（メタデータ） (2021-02-13T07:04:23Z)
• Corruption-robust exploration in episodic reinforcement learning [76.19192549843727]
  本研究は, システムにおける報酬と遷移確率の両面において, 敵対的腐敗下での多段階・多段階・多段階強化学習について検討した。 我々の枠組みは、汚職の欠如をほぼ最適に後悔する効率的なアルゴリズムをもたらす。 特に,本研究は,根本的強化学習のためのBandit-Feedbackモデルにおいて,純粋にI.d.遷移からの逸脱を保証した最初のサブ線形後悔の保証を提供する。
  論文  参考訳（メタデータ） (2019-11-20T03:49:13Z)

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

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