論文の概要: Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs
- arxiv url: http://arxiv.org/abs/2110.13876v1
- Date: Tue, 26 Oct 2021 17:30:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-27 15:47:58.656532
- Title: Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs
- Title（参考訳）: モーメント・コンディション・バリアを破る:超大型ペイオフバンドの非回帰アルゴリズム
- Authors: Han Zhong, Jiayi Huang, Lin F. Yang, Liwei Wang
- Abstract要約: 実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
- 参考スコア（独自算出の注目度）: 27.636407641546914
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite a large amount of effort in dealing with heavy-tailed error in
machine learning, little is known when moments of the error can become
non-existential: the random noise $\eta$ satisfies Pr$\left[|\eta| > |y|\right]
\le 1/|y|^{\alpha}$ for some $\alpha > 0$. We make the first attempt to
actively handle such super heavy-tailed noise in bandit learning problems: We
propose a novel robust statistical estimator, mean of medians, which estimates
a random variable by computing the empirical mean of a sequence of empirical
medians. We then present a generic reductionist algorithmic framework for
solving bandit learning problems (including multi-armed and linear bandit
problem): the mean of medians estimator can be applied to nearly any bandit
learning algorithm as a black-box filtering for its reward signals and obtain
similar regret bound as if the reward is sub-Gaussian. We show that the regret
bound is near-optimal even with very heavy-tailed noise. We also empirically
demonstrate the effectiveness of the proposed algorithm, which further
corroborates our theoretical results.
- Abstract（参考訳）: 機械学習における重み付きエラーの処理には多大な労力がかかるが、エラーのモーメントが存在しない場合はほとんど知られていない: ランダムノイズ $\eta$ satisfies Pr$\left[|\eta| > |y|\right] \le 1/|y|^{\alpha}$ for some $\alpha > 0$。
我々は,このような超重み付き雑音をバンディット学習問題において積極的に扱うための最初の試みとして,経験的中央値列の経験平均を計算し,確率変数を推定する新しい頑健な統計推定器,中央値平均を提案する。
次に,バンディット学習問題(多腕および線形バンディット問題を含む)を解決するための汎用的還元主義的アルゴリズムフレームワークを提案する。 報酬信号に対するブラックボックスフィルタリングとして,ほぼすべてのバンディット学習アルゴリズムに適用できる。
非常に重い音でも、後悔の限界はほぼ最適であることを示す。
また,提案アルゴリズムの有効性を実証的に実証し,理論的結果をさらに裏付ける。
関連論文リスト
- Learning Constant-Depth Circuits in Malicious Noise Models [9.036777309376697]
我々は、定数深度回路を学習するためのLinial, Mansour, Nisanの準ポリノミカル時間アルゴリズムを証明した。
ノイズ率に最も依存しうることを達成し、最も厳しいノイズモデルの実現に成功した。
論文 参考訳（メタデータ） (2024-11-06T00:19:58Z) - 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) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。
我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-16T00:10:35Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - No Regrets for Learning the Prior in Bandits [30.478188057004175]
$tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。
$tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
論文 参考訳（メタデータ） (2021-07-13T15:51:32Z) - 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) - Learning Multiclass Classifier Under Noisy Bandit Feedback [6.624726878647541]
本研究では,非バイアス推定手法に基づく雑音の多い帯域フィードバックに対処する新しい手法を提案する。
いくつかのベンチマークデータセットに対する広範な実験により,提案手法の有効性を示す。
論文 参考訳（メタデータ） (2020-06-05T16:31:05Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。