論文の概要: Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates

• arxiv url: http://arxiv.org/abs/2606.00984v1
• Date: Sun, 31 May 2026 03:46:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:29.012959
• Title: Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
• Title（参考訳）: 希少なパラメータ更新を伴う線形帯域の実用的および最適アルゴリズム
• Authors: Sanghoon Yu, Min-hwan Oh,
• Abstract要約: 稀なパラメータ更新の下で線形文脈帯域について検討した。 パラメータ更新を$O(loglog T)$で行う2つの実用的なアルゴリズムを提案する。 その結果,$O(loglog T)$パラメータ更新による統計的に最適なアルゴリズムが得られた。
• 参考スコア（独自算出の注目度）: 33.46701416812218
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only $O(\log\log T)$ parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in $T$) simultaneously in both the small-$K$ and large-$K$ regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step -- a dominant computational bottleneck in prior strictly batched static-grid methods -- yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield statistically optimal algorithms under $O(\log\log T)$ parameter updates that are also computationally efficient in practice.
• Abstract（参考訳）: 学習者は少ない更新時間でのみ報酬フィードバックをパラメータ推定に組み込むことができ、オンライン上でコンテキストを観察し、順次行動を選択することができる。 この視点は、文献でしばしばぼやけている実践的な区別を明らかにしている: 多くの「制限されたバッチ化」手法は、内部の文脈適応性をさらに制限し、つまり、間隔内のアクションルールはその間隔内で実現されたコンテキスト/アクションのシーケンス(現在のラウンドのコンテキストに加えて)に依存できないことを意味する。 線形文脈帯域に対して,パラメータ更新を$O(\log\log T)で行う2つの実用的なアルゴリズムを提案する。 我々の最初のアルゴリズムBLCE-Gは、静的なスケジュールの下で、小額のK$と大額のK$レジームの両方で同時にミニマックス最適後悔(T$のポリ対数係数まで)を達成する。 第2のアルゴリズムBLCEは,従来の厳密な静的グリッド法における計算ボトルネックである近G最適設計のステップを除去するが,最小の最大最適後悔を保ち,最適アルゴリズムの中で最小のランタイム複雑性を実現する。 さらに、これらの稀な更新と計算の原理を一般化された線形文脈帯域に拡張する。 総じて, 計算効率のよい$O(\log\log T)$パラメータ更新による統計的に最適なアルゴリズムが得られた。

関連論文リスト

• Optimal and Practical Batched Linear Bandit Algorithm [8.087699764574788]
  本稿では, 線形バンドイット問題(バッチ化線形バンドイット)について, 限定適応性の下で検討する。 我々は,腕の除去と正規化G-最適設計を統合した新しいバッチアルゴリズムBLAEを提案する。 BLAEは、全てのレジームにおける証明可能なミニマックス最適性と、バッチ化された線形帯域における実用上の優位性を組み合わせた最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2025-07-11T09:29:28Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Practical Performance Guarantees for Pipelined DNN Inference [3.493620624883548]
  グラフを$k$のステージに分割することで、ディープニューラルネットワーク(DNN)推論のためのパイプライン並列性を最適化する。 改良された下限が最適性ギャップを9.855xで閉じていることが示される。
  論文  参考訳（メタデータ） (2023-11-07T03:55:39Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration [22.621710838468097]
  無限ホライゾンマルコフ決定過程(mdps)における学習アルゴリズムを関数近似を用いて検討する。 まず、ほぼ同一の仮定の下で、Politexアルゴリズムの後悔解析を$O(T3/4)$から$O(sqrtT)$にシャープできることを示す。 その結果、計算効率の良いアルゴリズムに対して、最初の高い確率の$o(sqrtt)$ regretバウンドが得られる。
  論文  参考訳（メタデータ） (2021-02-25T00:55:07Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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