論文の概要: Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms

• arxiv url: http://arxiv.org/abs/2302.13534v1
• Date: Mon, 27 Feb 2023 06:09:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-28 16:41:59.987126
• Title: Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms
• Title（参考訳）: マルチアーマッドバンドのためのベスト・オブ・ボス・ワールド・保証の改善:汎用正規化器と複数の最適アームを備えたFTRL
• Authors: Tiancheng Jin, Junyan Liu, Haipeng Luo
• Abstract要約: 本研究では,適応型マルチアームバンディットアルゴリズムを設計する際の課題について検討する。 FTRLには多種多様な正規化要因と新たな学習率スケジュールが不要であることを示す。
• 参考スコア（独自算出の注目度）: 33.9579032695824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of designing adaptive multi-armed bandit algorithms that perform optimally in both the stochastic setting and the adversarial setting simultaneously (often known as a best-of-both-world guarantee). A line of recent works shows that when configured and analyzed properly, the Follow-the-Regularized-Leader (FTRL) algorithm, originally designed for the adversarial setting, can in fact optimally adapt to the stochastic setting as well. Such results, however, critically rely on an assumption that there exists one unique optimal arm. Recently, Ito (2021) took the first step to remove such an undesirable uniqueness assumption for one particular FTRL algorithm with the $\frac{1}{2}$-Tsallis entropy regularizer. In this work, we significantly improve and generalize this result, showing that uniqueness is unnecessary for FTRL with a broad family of regularizers and a new learning rate schedule. For some regularizers, our regret bounds also improve upon prior results even when uniqueness holds. We further provide an application of our results to the decoupled exploration and exploitation problem, demonstrating that our techniques are broadly applicable.
• Abstract（参考訳）: 本研究では,確率的設定と敵対的設定の両方において最適に動作する適応型マルチアームバンディットアルゴリズムを設計する問題(しばしば両世界最高の保証として知られる)について検討する。 最近の研究の行は、構成と解析を適切に行うと、FTRL(Follow-the-Regularized-Leader)アルゴリズムが元来、対数的設定のために設計され、実際に確率的設定にも最適に適応できることを示している。 しかし、そのような結果は一つの一意的な最適腕が存在するという仮定に批判的である。 最近、伊藤 (2021) は、$\frac{1}{2}$-Tsallis entropy regularizer を用いて、ある特定の FTRL アルゴリズムに対してそのような望ましくない一意性仮定を除去する第一歩を踏み出した。 本研究では,幅広い正規化器群と新しい学習率スケジュールを持つftrlでは,一意性が不要であることを示すため,この結果を大幅に改善し,一般化する。 一部の正則化器では、一意性が保たれたとしても、我々の後悔の限界は以前の結果にも改善される。 我々はさらに,この手法が広く適用可能であることを実証し,非結合な探索・搾取問題に適用する。

関連論文リスト

• Computing Optimal Regularizers for Online Linear Optimization [38.72709491927979]
  FTRL(Follow-the-Regularized-Leader)アルゴリズムはオンライン線形最適化(OLO)のための一般的な学習アルゴリズムである。 本稿では,最良学習アルゴリズムの一定要素内における後悔を実現するFTRLのインスタンス化が存在することを示す。
  論文  参考訳（メタデータ） (2024-10-22T18:10:50Z)
• Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation [58.288682735160585]
  Low-Rank Adaptation (LoRA) は、ファインチューニングモデルの一般的なテクニックである。 LoRAは、フルパラメータの微調整と比較すると、しばしば実行されます。 本稿では,LoRA手法の適応率を厳密に分析するフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-10T18:51:53Z)
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
  FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。 本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-30T16:00:23Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。 我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
  論文  参考訳（メタデータ） (2023-05-26T23:20:48Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• Single-Trajectory Distributionally Robust Reinforcement Learning [21.955807398493334]
  本研究では,分散ロバストRL (DRRL) を提案する。 既存のDRRLアルゴリズムはモデルベースか、1つのサンプル軌道から学習できないかのいずれかである。 単一軌道を用いた分散ロバストQ-ラーニング(DRQ)と呼ばれる,完全モデルフリーなDRRLアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-01-27T14:08:09Z)
• Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
  オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。 我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-01T17:59:19Z)

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

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