論文の概要: Stability-penalty-adaptive Follow-the-regularized-leader: Sparsity,
Game-dependency, and Best-of-both-worlds
- arxiv url: http://arxiv.org/abs/2305.17301v1
- Date: Fri, 26 May 2023 23:20:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 20:33:30.193624
- Title: Stability-penalty-adaptive Follow-the-regularized-leader: Sparsity,
Game-dependency, and Best-of-both-worlds
- Title（参考訳）: 安定-ペナルティ-アダプティブ フォロー-ザ-レギュラー化--スペシャリティ、ゲーム依存性、そして両世界のベスト
- Authors: Taira Tsuchiya, Shinji Ito, Junya Honda
- Abstract要約: FTRL(Follow-the-Regularized-Leader)は、最近、バンドイット問題における様々なタイプの適応性を得るための最も有望なアプローチの1つとして登場した。
我々は、FTRLのためのSPA学習率と呼ばれる、汎用的な適応学習率を開発する。
この学習速度は、アルゴリズムの安定性とペナルティに応じて共同で後悔をもたらす。
- 参考スコア（独自算出の注目度）: 34.37963000493442
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Adaptivity to the difficulties of a problem is a key property in sequential
decision-making problems to broaden the applicability of algorithms.
Follow-the-Regularized-Leader (FTRL) has recently emerged as one of the most
promising approaches for obtaining various types of adaptivity in bandit
problems. Aiming to further generalize this adaptivity, we develop a generic
adaptive learning rate, called Stability-Penalty-Adaptive (SPA) learning rate
for FTRL. This learning rate yields a regret bound jointly depending on
stability and penalty of the algorithm, into which the regret of FTRL is
typically decomposed. With this result, we establish several algorithms with
three types of adaptivity: sparsity, game-dependency, and Best-of-Both-Worlds
(BOBW). Sparsity frequently appears in real-world problems. However, existing
sparse multi-armed bandit algorithms with $k$-arms assume that the sparsity
level $s \leq k$ is known in advance, which is often not the case in real-world
scenarios. To address this problem, with the help of the new learning rate
framework, we establish $s$-agnostic algorithms with regret bounds of
$\tilde{O}(\sqrt{sT})$ in the adversarial regime for $T$ rounds, which matches
the existing lower bound up to a logarithmic factor. Meanwhile, BOBW algorithms
aim to achieve a near-optimal regret in both the stochastic and adversarial
regimes. Leveraging the new adaptive learning rate framework and a novel
analysis to bound the variation in FTRL output in response to changes in a
regularizer, we establish the first BOBW algorithm with a sparsity-dependent
bound. Additionally, we explore partial monitoring and demonstrate that the
proposed learning rate framework allows us to achieve a game-dependent bound
and the BOBW simultaneously.
- Abstract（参考訳）: 問題の難しさへの適応性は、アルゴリズムの適用性を広げるためのシーケンシャルな意思決定問題の鍵となる性質である。
FTRL(Follow-the-Regularized-Leader)は、最近、バンドイット問題における様々な適応性を得るために最も有望なアプローチの1つである。
この適応性をさらに一般化するために,ftrlのためのspa学習率と呼ばれる汎用適応学習率を開発した。
この学習速度は、FTRLの後悔が分解されるアルゴリズムの安定性とペナルティに依存して、共同で後悔をもたらす。
この結果から,3種類の適応性を持つアルゴリズム,空間性,ゲーム依存性,Best-of-Both-Worlds (BOBW) が得られた。
空間性は現実世界の問題にしばしば現れる。
しかし、既存のsparse multi-armed bandit algorithm with $k$-arms はスパーシティレベル $s \leq k$ が事前に知られていると仮定しており、現実のシナリオではそうではないことが多い。
この問題に対処するために、新しいラーニングレートフレームワークの助けを借りて、対数係数に対する既存の下限に一致する$t$ラウンドの敵対的レジームにおいて、$\tilde{o}(\sqrt{st})$の残念な境界を持つ$s$非依存アルゴリズムを確立する。
一方,BOBWアルゴリズムは,確率的・敵対的両体制において,ほぼ最適に後悔することを目指している。
新しい適応学習率フレームワークと、正規化器の変化に応じてFTRL出力の変動をバウンドする新たな分析を活用し、空間依存のバウンダリを持つ最初のBOBWアルゴリズムを確立する。
さらに,部分的監視について検討し,提案する学習率フレームワークにより,ゲーム依存のバウンドとbowを同時に達成できることを実証する。
関連論文リスト
- uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs [33.262918224598614]
本稿では,HTMAB(Heavy-Tailed Multi-Armed Bandits)問題に対する新しいアルゴリズムを提案する。
我々の新しいアルゴリズムユニは、Best-of-Both-Worlds(BoBW)特性を楽しみ、両環境とも最適に機能する。
我々の知る限り、UniINFは重み付きMAB問題に対するBoBW特性を達成する最初のパラメータフリーアルゴリズムである。
論文 参考訳（メタデータ） (2024-10-04T09:55:44Z) - Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。
本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-30T16:00:23Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - A Risk-Averse Framework for Non-Stationary Stochastic Multi-Armed
Bandits [0.0]
医療や金融のような高ボラティリティの分野では、素直な報酬アプローチは学習問題の複雑さを正確に捉えないことが多い。
非定常環境で動作する適応型リスク認識戦略の枠組みを提案する。
論文 参考訳（メタデータ） (2023-10-24T19:29:13Z) - Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL
with General Regularizers and Multiple Optimal Arms [41.06668954462585]
本研究では,適応型マルチアームバンディットアルゴリズムを設計する際の課題について検討する。
FTRLには多種多様な正規化要因と新たな学習率スケジュールが不要であることを示す。
論文 参考訳（メタデータ） (2023-02-27T06:09:10Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - A Blackbox Approach to Best of Both Worlds in Bandits and Beyond [33.13041034490332]
オンライン学習のためのベスト・オブ・ザ・ワールドズ(Best-of-worlds)アルゴリズムは、敵対政権と敵対政権の両方において、ほぼ最適に後悔する。
両世界の長所から、フォロー・ザ・レギュラライズド・リーダー(FTRL)とオンライン・ミラーダネッセンス(OMD)アルゴリズムの幅広いファミリーへの一般化を提案する。
論文 参考訳（メタデータ） (2023-02-20T03:42:31Z) - Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
定常分布補正を用いたオフラインRLアルゴリズムの分散正則化を提案する。
Fenchel双対性を用いることで、分散正規化器の勾配を計算するための二重サンプリング問題を回避することができることを示す。
オフライン分散正規化アルゴリズム(OVAR)は,既存のオフラインポリシー最適化アルゴリズムを拡張できる。
論文 参考訳（メタデータ） (2022-12-29T18:25:01Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳（メタデータ） (2020-07-09T17:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。