論文の概要: 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) - Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳（メタデータ） (2024-02-12T03:31:34Z) - Zero-Inflated Bandits [11.60342504007264]
ゼロ膨らんだ帯状地について検討し、報酬をゼロ膨らんだ分布と呼ばれる古典的な半パラメトリック分布としてモデル化する。
一般報奨仮定と準ガウス報奨を含む文脈一般化線形報奨を併用した多腕包帯の両面における後悔境界を導出する。
多くの設定において、我々のアルゴリズムの後悔率は、最小限の最適か最先端のどちらかである。
論文 参考訳（メタデータ） (2023-12-25T03:13:21Z) - 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) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。