論文の概要: $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits

• arxiv url: http://arxiv.org/abs/2310.02975v2
• Date: Mon, 12 Feb 2024 10:39:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-13 22:20:29.465579
• Title: $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits
• Title（参考訳）: ヘビーテールバンディットにおける$(\epsilon, u)$-adaptive regretの最小化
• Authors: Gianmarco Genalti and Lupo Marsigli and Nicola Gatti and Alberto Maria Metelli
• Abstract要約: 我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
• 参考スコア（独自算出の注目度）: 29.966828248335972
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Heavy-tailed distributions naturally arise in several settings, from finance to telecommunications. While regret minimization under subgaussian or bounded rewards has been widely studied, learning with heavy-tailed distributions only gained popularity over the last decade. In this paper, we consider the setting in which the reward distributions have finite absolute raw moments of maximum order $1+\epsilon$, uniformly bounded by a constant $u<+\infty$, for some $\epsilon \in (0,1]$. In this setting, we study the regret minimization problem when $\epsilon$ and $u$ are unknown to the learner and it has to adapt. First, we show that adaptation comes at a cost and derive two negative results proving that the same regret guarantees of the non-adaptive case cannot be achieved with no further assumptions. Then, we devise and analyze a fully data-driven trimmed mean estimator and propose a novel adaptive regret minimization algorithm, AdaR-UCB, that leverages such an estimator. Finally, we show that AdaR-UCB is the first algorithm that, under a known distributional assumption, enjoys regret guarantees nearly matching those of the non-adaptive heavy-tailed case.
• Abstract（参考訳）: 重細な分布は、金融から通信まで、いくつかの場所で自然に発生する。 subgaussian や bounded rewards の下での後悔の最小化は広く研究されているが、ヘビーテール分布での学習は過去10年間で人気を博しただけである。 本稿では、ある$\epsilon \in (0,1]$に対して、報酬分布が最大位 $1+\epsilon$ の有限絶対な生モーメントを持つような条件を、定数$u<+\infty$ で一様有界に考える。 本稿では,学習者に対して$\epsilon$と$u$が未知であり,適応しなければならない場合の,後悔の最小化問題を考察する。 まず,適応はコストがかかることを示し,不適応の場合の同じ後悔の保証が,それ以上の仮定で達成できないことを示す2つの負の結果を導出する。 そこで我々は,完全データ駆動型トリミング平均推定器を考案,解析し,そのような推定器を利用する新しい適応的最小化アルゴリズムAdaR-UCBを提案する。 最後に, adar-ucbは, 既知の分布的仮定の下で, 非適応重項の場合とほぼ一致した後悔の保証を享受する最初のアルゴリズムであることを示す。

関連論文リスト

• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
  論文  参考訳（メタデータ） (2024-06-10T23:23:52Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions [14.959412298776199]
  我々は、従来のネットワーク収益管理(NRM)問題について、意思決定を受理/退避し、IIDの到着を$T$で検討する。 本モデルでは,O(log2 T)$ regret を実現するオンラインアルゴリズムを開発した。 2階成長の仮定を追加して、$O(log T)$ regretを達成する2番目の結果を得る。
  論文  参考訳（メタデータ） (2022-10-14T17:52:19Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Regret Minimization in Heavy-Tailed Bandits [12.272975892517039]
  マルチアームバンディット設定における古典的後悔最小化問題を再考する。 本稿では,1次項における下界を正確に一致させる最適アルゴリズムを提案する。 我々の指数は、よく知られたトリミングまたはトリミングされた経験的平均推定値よりも速く集中していることを示す。
  論文  参考訳（メタデータ） (2021-02-07T07:46:24Z)
• Minimax Policy for Heavy-tailed Bandits [10.203602318836444]
  我々は、飽和経験平均を用いて、ガウス以下の報酬分布に対するミニマックスポリシー MOSS を修正し、ロバスト MOSS と呼ばれる新しいアルゴリズムを設計する。 報酬分布に対する1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1。
  論文  参考訳（メタデータ） (2020-07-20T21:43:57Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)

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

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