論文の概要: Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

• arxiv url: http://arxiv.org/abs/2605.25590v1
• Date: Mon, 25 May 2026 08:40:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:19.525183
• Title: Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
• Title（参考訳）: オンラインミラーの非定常一般化線形帯域
• Authors: Joongkyu Lee, Min-hwan Oh,
• Abstract要約: 本研究では,非定常線形計算(GLBs)について検討し,期待される報酬を未知の時間変化パラメータを持つ非線形リンク関数を用いてモデル化する。 本稿では,パラメータ推定に割引オンラインミラー降下(DOMD)を利用する非定常GLBに対する新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 39.805192541498634
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study nonstationary generalized linear bandits (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown time-varying parameter. This framework encompasses a broad class of reward models, including linear, Bernoulli, and binomial rewards. Existing approaches are predominantly based on maximum-likelihood estimation (MLE), using sliding-window, restart, or discounting mechanisms to handle nonstationarity. Although these methods achieve statistically efficient regret guarantees, they generally require revisiting past observations at every round, which leads to computation and memory costs that grow with time; moreover, several of them rely on a non-convex projection step. In this paper, we propose DOMD-GLB, a new algorithm for nonstationary GLBs that utilizes discounted online mirror descent (DOMD) for parameter estimation, thereby incurring only $O(1)$ computation and memory costs per round. We prove dynamic regret bounds of order $\tilde{O} \big(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4}\big)$ in drifting environments and $\tilde{O}\big(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3}\big) $in piecewise-stationary environments, where $d$ denotes the feature dimension, $T$ the time horizon, $P_T$ the path length, $Γ_T$ the number of change points, and $c_μ$ a curvature parameter associated with the link function, while substantially improving computational efficiency over prior work. To the best of our knowledge, this is the first algorithm for nonstationary GLBs with per-round computation and memory costs independent of time.
• Abstract（参考訳）: 本研究では,非定常一般化線形帯域 (GLBs) について検討し,期待される報酬は,未知の時間変化パラメータを持つ非線形リンク関数によってモデル化されることを示した。 このフレームワークは、線形、ベルヌーイ、二項報酬を含む幅広い種類の報酬モデルを含んでいる。 既存のアプローチは主に、非定常性を扱うためにスライドウインドウ、再起動、または割引メカニズムを使用して、最大風速推定(MLE)に基づいている。 これらの手法は統計的に効率的な後悔の保証を実現するが、一般的にはすべてのラウンドで過去の観測を再考する必要があるため、計算とメモリコストは時間とともに増大する。 本稿では,パラメータ推定に割引オンラインミラー降下(DOMD)を利用する非定常GLBの新しいアルゴリズムであるDOMD-GLBを提案する。 ドリフト環境における$\tilde{O} \big(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4}\big)$と、ドリフト環境における$\tilde{O}\big(c_μ^{-1/3} d^{2/3} ^_T^{1/3} T^{2/3}\big) $in piecewise-stationary環境において、$d$は特徴次元を表す。 我々の知る限りでは、このアルゴリズムは単位単位の計算とメモリコストが時間に依存しない非定常GLBのための最初のアルゴリズムである。

関連論文リスト

• Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$ [7.884611719110979]
  グラディエント・Descent (SGD) は、現代のデータ科学における基礎的な手法となっている。 本研究では,オンライン最小二乗 SGD の線型汎函数に対して,非漸近的ベリー-エッセイン境界を確立する。
  論文  参考訳（メタデータ） (2025-10-22T16:25:49Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  データ・ポーア・システマにおける高次元スパース線形包帯問題について検討する。 線形モデルに対するラッソ推定器の新たなオフライン統計的保証を示す。 本稿では,最小限のコストで最適空間パラメータ$k$の知識を必要としない相関に基づくメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-26T01:42:03Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation [25.60689712525918]
  本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。 本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
  論文  参考訳（メタデータ） (2022-06-23T06:04:21Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
  非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究 OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。 我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
  論文  参考訳（メタデータ） (2020-10-24T11:02:45Z)
• Truncated Linear Regression in High Dimensions [26.41623833920794]
  truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。 目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。 我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
  論文  参考訳（メタデータ） (2020-07-29T00:31:34Z)

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

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