論文の概要: 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では,一意性が不要であることを示すため,この結果を大幅に改善し,一般化する。
一部の正則化器では、一意性が保たれたとしても、我々の後悔の限界は以前の結果にも改善される。
我々はさらに,この手法が広く適用可能であることを実証し,非結合な探索・搾取問題に適用する。
関連論文リスト
- Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter
Lesson of Reinforcement Learning [15.615763010305514]
我々は60以上の異なる非政治エージェントを実装し、それぞれが最新の最先端アルゴリズムから確立された正規化技術を統合する。
2つのシミュレーションベンチマークから14のタスクにまたがってこれらのエージェントをテストした。
その結果、特定の正規化設定の有効性はタスクによって異なるが、特定の組み合わせは一貫して堅牢で優れた性能を示すことがわかった。
論文 参考訳(メタデータ) (2024-03-01T13:25:10Z) - 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) - Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
定常分布補正を用いたオフラインRLアルゴリズムの分散正則化を提案する。
Fenchel双対性を用いることで、分散正規化器の勾配を計算するための二重サンプリング問題を回避することができることを示す。
オフライン分散正規化アルゴリズム(OVAR)は,既存のオフラインポリシー最適化アルゴリズムを拡張できる。
論文 参考訳(メタデータ) (2022-12-29T18:25:01Z) - On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [7.23389716633927]
我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。
また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
論文 参考訳(メタデータ) (2022-11-30T16:46:41Z) - Versatile Dueling Bandits: Best-of-both-World Analyses for Online
Learning from Preferences [28.79598714109439]
両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。
まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。
提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
論文 参考訳(メタデータ) (2022-02-14T13:37:23Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。