論文の概要: Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed
Bandits
- arxiv url: http://arxiv.org/abs/2201.11921v1
- Date: Fri, 28 Jan 2022 03:53:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 06:27:18.072123
- Title: Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed
Bandits
- Title（参考訳）: ヘビーテールマルチアームバンディットのための適応型両世界のベストオブバイザーズアルゴリズム
- Authors: Jiatai Huang, Yan Dai, Longbo Huang
- Abstract要約: 我々は、重尾の多腕バンディットのためのロバストなベスト・オブ・ザ・ワールドスアルゴリズムを開発した。
textttHTINFは、両方の環境と敵環境に最適な後悔を同時に達成する。
textttAdaTINFは、alpha$と$sigma$の両方に適応できる最初のアルゴリズムであり、最適のギャップを逸脱した後悔境界を達成する。
- 参考スコア（独自算出の注目度）: 22.18577284185939
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In this paper, we generalize the concept of heavy-tailed multi-armed bandits
to adversarial environments, and develop robust best-of-both-worlds algorithms
for heavy-tailed multi-armed bandits (MAB), where losses have $\alpha$-th
($1<\alpha\le 2$) moments bounded by $\sigma^\alpha$, while the variances may
not exist. Specifically, we design an algorithm \texttt{HTINF}, when the
heavy-tail parameters $\alpha$ and $\sigma$ are known to the agent,
\texttt{HTINF} simultaneously achieves the optimal regret for both stochastic
and adversarial environments, without knowing the actual environment type
a-priori. When $\alpha,\sigma$ are unknown, \texttt{HTINF} achieves a $\log
T$-style instance-dependent regret in stochastic cases and $o(T)$ no-regret
guarantee in adversarial cases. We further develop an algorithm
\texttt{AdaTINF}, achieving $\mathcal O(\sigma K^{1-\nicefrac
1\alpha}T^{\nicefrac{1}{\alpha}})$ minimax optimal regret even in adversarial
settings, without prior knowledge on $\alpha$ and $\sigma$. This result matches
the known regret lower-bound (Bubeck et al., 2013), which assumed a stochastic
environment and $\alpha$ and $\sigma$ are both known. To our knowledge, the
proposed \texttt{HTINF} algorithm is the first to enjoy a best-of-both-worlds
regret guarantee, and \texttt{AdaTINF} is the first algorithm that can adapt to
both $\alpha$ and $\sigma$ to achieve optimal gap-indepedent regret bound in
classical heavy-tailed stochastic MAB setting and our novel adversarial
formulation.
- Abstract（参考訳）: 本稿では,重畳型マルチアーム付きバンディットの概念を敵環境に一般化し,重畳型マルチアーム付きバンディット (mab) に対して頑健な最善のバイザーワールドアルゴリズムを開発し,損失が$\sigma^\alpha$ で区切られた$\alpha$-th ($1<\alpha\le 2$) モーメントを持つ場合,分散は存在しない。
具体的には、ヘビーテールパラメータ $\alpha$ と $\sigma$ がエージェントに知られている場合、 \texttt{htinf} は、実際の環境タイプ a-priori を知らずに、確率的環境と敵対的環境の両方に対して最適な後悔を達成する。
alpha,\sigma$ が未知の場合、 \texttt{htinf} は確率ケースでは $\log t$-style instance-dependent regret となり、反対ケースでは $o(t)$ no-regret が保証される。
さらに、$\mathcal O(\sigma K^{1-\nicefrac 1\alpha}T^{\nicefrac{1}{\alpha}})$ minimax optimal regret を、$\alpha$ と $\sigma$ について事前の知識を必要とせずに、敵対的設定でも実現できるアルゴリズムである。
この結果は、確率的な環境を仮定した既知の後悔(bubeck et al., 2013)と、$\alpha$と$\sigma$の両方が知られている。
我々の知る限り、提案した‘texttt{HTINF} アルゴリズムは、最良世界の後悔の保証を初めて享受し、‘texttt{AdaTINF} は $\alpha$ と $\sigma$ の両方に適応できる最初のアルゴリズムであり、古典的な重み付き確率的 MAB 設定と我々の新しい逆数定式化において最適なギャップ非依存性の後悔を達成できる。
関連論文リスト
- Fast UCB-type algorithms for stochastic bandits with heavy and super
heavy symmetric noise [45.60098988395789]
マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。
報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
論文 参考訳（メタデータ） (2024-02-10T22:38:21Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。
時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。
また, 動的上界に依存した新しい行列不等式濃度を証明した。
論文 参考訳（メタデータ） (2021-10-15T12:32:33Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Problem-Complexity Adaptive Model Selection for Stochastic Linear
Bandits [20.207989166682832]
2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。
まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。
我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
論文 参考訳（メタデータ） (2020-06-04T02:19:00Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。