論文の概要: Stability-penalty-adaptive follow-the-regularized-leader: Sparsity,
game-dependency, and best-of-both-worlds
- arxiv url: http://arxiv.org/abs/2305.17301v2
- Date: Tue, 13 Feb 2024 09:23:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 19:54:37.830914
- 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つである。
我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
- 参考スコア(独自算出の注目度): 46.30750729936261
- 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). Despite the fact that sparsity appears frequently in real problems,
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 issue, we first 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 SPA
learning rate and the technique for $s$-agnostic algorithms combined with a new
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 SPA 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の後悔が分解されるアルゴリズムの安定性とペナルティに依存して、共同で後悔をもたらす。
この結果から,空間性,ゲーム依存性,世界最良性(BOBW)の3種類の適応性を持つアルゴリズムを確立した。
スパーシティが現実の問題に頻繁に現れるという事実にもかかわらず、$k$-armsを持つ既存のスパースなマルチアームバンディットアルゴリズムは、スパーシティレベル$s \leq k$が事前に知られていると仮定している。
この問題に対処するために、我々はまず、対数係数まで既存の下限に一致する$t$ラウンドの敵対的レジームにおいて、$\tilde{o}(\sqrt{st})$の後悔の限界で$s$非依存のアルゴリズムを確立する。
一方,BOBWアルゴリズムは,確率的・敵対的両体制において,ほぼ最適に後悔することを目指している。
SPA学習率と$s$非依存アルゴリズムの手法と、正規化器の変更に応じてFTRL出力の変動をバウンドする新たな解析を組み合わせることで、空間依存境界を持つ最初のBOBWアルゴリズムを確立する。
さらに,部分的監視について検討し,提案するスパ学習率フレームワークにより,ゲーム依存のバウンドとbowを同時に達成できることを実証する。
関連論文リスト
- Sparsity via Sparse Group $k$-max Regularization [22.05774771336432]
本稿では,新規かつ簡潔な正規化,すなわちスパース群$k$-max正規化を提案する。
提案手法の有効性と柔軟性を,合成データセットと実世界のデータセットの数値実験により検証する。
論文 参考訳(メタデータ) (2024-02-13T14:41:28Z) - A Risk-Averse Framework for Non-Stationary Stochastic Multi-Armed
Bandits [0.0]
医療や金融のような高ボラティリティの分野では、素直な報酬アプローチは学習問題の複雑さを正確に捉えないことが多い。
非定常環境で動作する適応型リスク認識戦略の枠組みを提案する。
論文 参考訳(メタデータ) (2023-10-24T19:29:13Z) - Best-of-three-worlds Analysis for Linear Bandits with
Follow-the-regularized-leader Algorithm [11.80907528239756]
線形バンディット問題は、双方の相反する環境で長年研究されてきた。
citetLeeLWZ021は、損失タイプを積極的に検出し、特定の設定のために特別に設計された異なるアルゴリズムを切り替えるアルゴリズムを提案する。
FTRL(Follow-the-regularized-leader)は、異なる環境に適応可能な人気アルゴリズムの一種である。
論文 参考訳(メタデータ) (2023-03-13T02:50:59Z) - 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) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳(メタデータ) (2020-07-09T17:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。