論文の概要: Towards Fully Adaptive Regret Minimization in Heavy-Tailed Bandits

• arxiv url: http://arxiv.org/abs/2310.02975v1
• Date: Wed, 4 Oct 2023 17:11:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 13:48:28.299784
• Title: Towards Fully Adaptive Regret Minimization in Heavy-Tailed Bandits
• Title（参考訳）: 重り付きバンドにおける完全適応レギュレット最小化に向けて
• Authors: Gianmarco Genalti and Lupo Marsigli and Nicola Gatti and Alberto Maria Metelli
• Abstract要約: 適応型ヘビーテールバンディット (adaptive heavy-tailed bandit) は, エージェントに対して$epsilon$と$u$の両方が未知な標準設定のバリエーションである。 適応性はコストがかかることを示し、任意の適応アルゴリズムの後悔に対して2つの低い境界を導入する。 重み付きMAB問題の既知下界に一致する最小化戦略であるAdaptive Robust UCBを提供する。
• 参考スコア（独自算出の注目度）: 29.966828248335972
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Heavy-tailed distributions naturally arise in many settings, from finance to telecommunications. While regret minimization under sub-Gaussian or bounded support rewards has been widely studied, learning on heavy-tailed distributions only gained popularity over the last decade. In the stochastic heavy-tailed bandit problem, an agent learns under the assumption that the distributions have finite moments of maximum order $1+\epsilon$ which are uniformly bounded by a constant $u$, for some $\epsilon \in (0,1]$. To the best of our knowledge, literature only provides algorithms requiring these two quantities as an input. In this paper, we study the stochastic adaptive heavy-tailed bandit, a variation of the standard setting where both $\epsilon$ and $u$ are unknown to the agent. We show that adaptivity comes at a cost, introducing two lower bounds on the regret of any adaptive algorithm, implying a higher regret w.r.t. the standard setting. Finally, we introduce a specific distributional assumption and provide Adaptive Robust UCB, a regret minimization strategy matching the known lower bound for the heavy-tailed MAB problem.
• Abstract（参考訳）: 重細な分布は、金融から電気通信まで、多くの場面で自然に発生する。 ガウス以南のサポーターの報酬に対する後悔の最小化は広く研究されているが、重尾分布の学習は過去10年間にのみ人気を博した。 確率的重み付きバンドイト問題において、エージェントは、分布が最大位 1+\epsilon$ の有限モーメントを持つという仮定の下で学習し、ある$\epsilon \in (0,1)$に対して定数$u$で一様有界である。 我々の知る限りでは、文献は入力としてこれらの2つの量を必要とするアルゴリズムのみを提供する。 本稿では, エージェントに$\epsilon$と$u$が未知の標準設定のバリエーションである, 確率適応重み付きバンディットについて検討する。 適応性はコストがかかることを示し、任意の適応アルゴリズムの後悔に対する2つの低い境界を導入し、標準設定に対する高い後悔を意味することを示す。 最後に,特定分布仮定を導入し,重み付きMAB問題の既知下限に一致する最小化戦略であるAdaptive Robust 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)

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

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