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

• arxiv url: http://arxiv.org/abs/2305.06743v1
• Date: Thu, 11 May 2023 12:00:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-12 15:00:46.093197
• Title: Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits
• Title（参考訳）: 線形および非線形重尾多腕バンディットのクリッピングによる暗黙的正規化予測器
• Authors: Yuriy Dorn and Kornilov Nikita and Nikolay Kutuzov and Alexander Nazin and Eduard Gorbunov and Alexander Gasnikov
• Abstract要約: 暗黙的に正規化されたフォアキャスターは、敵の多重武装問題に対する最適アルゴリズムとして知られている。 報酬に対する重み付き分布を持つMAB問題に対してクリッピングを施したImplicitly Normalized Forecasterを提案する。
• 参考スコア（独自算出の注目度）: 105.54048699217668
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Implicitly Normalized Forecaster (online mirror descent with Tsallis entropy as prox-function) is known to be an optimal algorithm for adversarial multi-armed problems (MAB). However, most of the complexity results rely on bounded rewards or other restrictive assumptions. Recently closely related best-of-both-worlds algorithm were proposed for both adversarial and stochastic heavy-tailed MAB settings. This algorithm is known to be optimal in both settings, but fails to exploit data fully. In this paper, we propose Implicitly Normalized Forecaster with clipping for MAB problems with heavy-tailed distribution on rewards. We derive convergence results under mild assumptions on rewards distribution and show that the proposed method is optimal for both linear and non-linear heavy-tailed stochastic MAB problems. Also we show that algorithm usually performs better compared to best-of-two-worlds algorithm.
• Abstract（参考訳）: 暗黙的正規化予測器(tsallisエントロピーをプロキシ関数とするオンラインミラー降下)は、逆マルチアームド問題(mab)の最適アルゴリズムとして知られている。 しかし、複雑さのほとんどは、制限付き報酬やその他の制限付き仮定に依存する。 近年, 対数的および確率的重み付きMAB設定に対して, 近縁なBest-of-both-worldsアルゴリズムが提案されている。 このアルゴリズムは両方の設定で最適であることが知られているが、完全にデータを活用できない。 本稿では,報酬に対する重み付き分布を持つMAB問題に対するクリッピングを用いたImplicitly Normalized Forecasterを提案する。 報酬分布の軽度仮定の下で収束結果を導出し,本手法が線形および非線形重み付き確率的mab問題に対して最適であることを示す。 また,2世界最高のアルゴリズムと比較して,アルゴリズムの性能がよいことを示す。

関連論文リスト

• 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)

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

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