論文の概要: Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits

• arxiv url: http://arxiv.org/abs/2305.06743v3
• Date: Tue, 26 Dec 2023 13:07:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 22:58:11.223448
• Title: Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits
• Title（参考訳）: 線形および非線形重尾多腕バンディットのクリッピングによる暗黙的正規化予測器
• Authors: Yuriy Dorn and Nikita Kornilov and Nikolay Kutuzov and Alexander Nazin and Eduard Gorbunov and Alexander Gasnikov
• Abstract要約: Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
• 参考スコア（独自算出の注目度）: 85.27420062094086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Implicitly Normalized Forecaster (INF) algorithm is considered to be an optimal solution for adversarial multi-armed bandit (MAB) problems. However, most of the existing complexity results for INF rely on restrictive assumptions, such as bounded rewards. Recently, a related algorithm was proposed that works for both adversarial and stochastic heavy-tailed MAB settings. However, this algorithm fails to fully exploit the available data. In this paper, we propose a new version of INF called the Implicitly Normalized Forecaster with clipping (INF-clip) for MAB problems with heavy-tailed reward distributions. We establish convergence results under mild assumptions on the rewards distribution and demonstrate that INF-clip is optimal for linear heavy-tailed stochastic MAB problems and works well for non-linear ones. Furthermore, we show that INF-clip outperforms the best-of-both-worlds algorithm in cases where it is difficult to distinguish between different arms.
• Abstract（参考訳）: Implicitly Normalized Forecaster (INF)アルゴリズムは、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 しかし、INFの既存の複雑さの結果のほとんどは、有界報酬のような制限的な仮定に依存している。 近年,逆向きと確率的重み付きMAB設定の両方で機能する関連アルゴリズムが提案されている。 しかし、このアルゴリズムは利用可能なデータを完全に活用できない。 本稿では,重み付き報酬分布を持つMAB問題に対するクリッピング (INF-clip) を用いた INF の新バージョンである Implicitly Normalized Forecaster を提案する。 報奨分布の軽度な仮定の下で収束結果を確立し, INF-clip が線形重み付き確率MAB問題に最適であることを示す。 さらに,inf-clipは両世界の最良のアルゴリズムよりも優れており,両腕の区別が困難である。

関連論文リスト

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• Log-based Sparse Nonnegative Matrix Factorization for Data Representation [55.72494900138061]
  非負の行列因子化(NMF)は、非負のデータを部品ベースの表現で表すことの有効性から、近年広く研究されている。 そこで本研究では,係数行列に対数ノルムを課した新しいNMF法を提案する。 提案手法のロバスト性を高めるために,$ell_2,log$-(pseudo) ノルムを新たに提案した。
  論文  参考訳（メタデータ） (2022-04-22T11:38:10Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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