論文の概要: Regret Bounds for Generalized Linear Bandits under Parameter Drift
- arxiv url: http://arxiv.org/abs/2103.05750v1
- Date: Tue, 9 Mar 2021 22:51:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-11 15:05:47.349635
- Title: Regret Bounds for Generalized Linear Bandits under Parameter Drift
- Title(参考訳): パラメータドリフト下における一般線形帯域のレグレト境界
- Authors: Louis Faury and Yoan Russac and Marc Abeille and Cl\'ement
Calauz\`enes
- Abstract要約: 一般化線形帯域(GLB)は、線形帯域(LB)設定の強力な拡張である。
GLBsの致命的な特徴に対処し、結果に欠陥を与える新しいアルゴリズムを紹介します。
- 参考スコア(独自算出の注目度): 10.858333811448096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Generalized Linear Bandits (GLBs) are powerful extensions to the Linear
Bandit (LB) setting, broadening the benefits of reward parametrization beyond
linearity. In this paper we study GLBs in non-stationary environments,
characterized by a general metric of non-stationarity known as the
variation-budget or \emph{parameter-drift}, denoted $B_T$. While previous
attempts have been made to extend LB algorithms to this setting, they overlook
a salient feature of GLBs which flaws their results. In this work, we introduce
a new algorithm that addresses this difficulty. We prove that under a geometric
assumption on the action set, our approach enjoys a
$\tilde{\mathcal{O}}(B_T^{1/3}T^{2/3})$ regret bound. In the general case, we
show that it suffers at most a $\tilde{\mathcal{O}}(B_T^{1/5}T^{4/5})$ regret.
At the core of our contribution is a generalization of the projection step
introduced in Filippi et al. (2010), adapted to the non-stationary nature of
the problem. Our analysis sheds light on central mechanisms inherited from the
setting by explicitly splitting the treatment of the learning and tracking
aspects of the problem.
- Abstract(参考訳): 一般化線形帯域(GLB)は線形帯域(LB)設定の強力な拡張であり、線形性を超えた報酬パラメトリゼーションの利点を拡大する。
本稿では,非定常環境におけるglbsの研究を行い,変動ブジェット(変分パラメータドリフト)と呼ばれる非定常性の一般的な指標を,$b_t$ で表した。
LBアルゴリズムをこの設定に拡張する以前の試みが行われているが、結果に欠陥があるGLBの重大な機能を見落としている。
本研究では,この難易度に対処する新たなアルゴリズムを提案する。
作用集合上の幾何学的仮定の下では、我々のアプローチは$\tilde{\mathcal{O}}(B_T^{1/3}T^{2/3})$ regret bound である。
一般の場合、それは最大$\tilde{\mathcal{O}}(B_T^{1/5}T^{4/5})$後悔に苦しむことを示しています。
私たちの貢献の核は、Filippi et alで導入された射影ステップの一般化である。
(2010) この問題の非定常性に適応した。
本分析は,学習の処理と追跡の側面を明示的に分割することで,設定から受け継いだ中心的メカニズムに光を当てる。
関連論文リスト
- Logarithmic Regret for Online KL-Regularized Reinforcement Learning [51.113248212150964]
KL正規化は、大規模言語モデルにおけるRL微調整の効率向上に重要な役割を果たしている。
経験的優位性にもかかわらず、KL-正則化RLと標準RLの理論的相違はほとんど未探索のままである。
楽観的なKL正規化オンライン文脈帯域幅アルゴリズムを提案し,その後悔の新たな分析法を提案する。
論文 参考訳(メタデータ) (2025-02-11T11:11:05Z) - $k$-SVD with Gradient Descent [16.57405742112833]
ステップサイズ選択のための単純で普遍的な規則を持つ勾配発振器は、即興で$k$-SVD を求める。
論文 参考訳(メタデータ) (2025-02-01T05:00:28Z) - From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。
本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
論文 参考訳(メタデータ) (2024-10-17T17:59:01Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - On the Sublinear Regret of GP-UCB [58.25014663727544]
ガウス過程上信頼境界 (GP-UCB) アルゴリズムは, ほぼ最適の後悔率を有することを示す。
私たちの改善は、基盤となるカーネルの滑らかさに比例してカーネルリッジ推定を正規化するという、重要な技術的貢献に依存しています。
論文 参考訳(メタデータ) (2023-07-14T13:56:11Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳(メタデータ) (2023-03-05T15:11:14Z) - Bilinear Exponential Family of MDPs: Frequentist Regret Bound with
Tractable Exploration and Planning [0.0]
本研究では,不確実な報酬と遷移を伴う連続状態行動空間におけるエピソード強化学習の課題について検討する。
我々は,未知のパラメータを学習するために,ペナライズされた最大確率推定器を用いたアルゴリズムBEF-RLSVIを提案する。
論文 参考訳(メタデータ) (2022-10-05T08:26:49Z) - Non-stationary Linear Bandits Revisited [26.082923174615495]
非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。
これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
論文 参考訳(メタデータ) (2021-03-09T10:07:17Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。