論文の概要: Linear Ensemble Sampling with Smaller Ensembles

• arxiv url: http://arxiv.org/abs/2609.13954v1
• Date: Sat, 12 Sep 2026 13:54:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.625413
• Title: Linear Ensemble Sampling with Smaller Ensembles
• Title（参考訳）: より小さなアンサンブルを用いた線形アンサンブルサンプリング
• Abstract要約: 正規化グラム行列が実質的に変化したときのみアンサンブルをリフレッシュするアンサンブルサンプリングアルゴリズムを提案する。 このメカニズムは、制御されたグラム行列ドリフトを持つエポックに解析をローカライズし、十分なアンサンブルサイズを$(dlog d+dloglog T)$に下げる。 アーム集合が濃度$K$の有限であるとき、提案アルゴリズムはよりシャープな後悔境界である$tilde O(dsqrtTlog K)$を達成する。
• 参考スコア（独自算出の注目度）: 38.66646896933269
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ensemble sampling offers a practical approach to randomized exploration by maintaining a collection of models, but how small an ensemble can be while retaining strong regret guarantees remains unresolved. In particular, the existing guarantees use an ensemble size of $Θ(d\log T)$, leaving a logarithmic gap in the horizon $T$ relative to the intrinsic $Ω(d)$ ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to $Θ(d\log d+d\log\log T)$, while preserving the state-of-the-art $\tilde O(d^{3/2}\sqrt T)$ regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality $K$, the proposed algorithm achieves the sharper regret bound $\tilde O(d\sqrt{T\log K})$. To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms: the $\tilde O(d^{3/2}\sqrt{T})$ rate for arbitrary bounded arm sets and the $\tilde O (d\sqrt{T\log K})$ rate for finite arm sets. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.
• Abstract（参考訳）: アンサンブルサンプリングは、モデルの集合を維持することでランダム化探索に実践的なアプローチを提供するが、強い後悔の保証を維持しながらアンサンブルがどれほど小さいかは未解決のままである。 特に、既存の保証は、内在的な$Ω(d)$ アンサンブルサイズ障壁に対して、地平線上の対数的ギャップを$T$に残して、$(d\log T)$ アンサンブルサイズを使用する。 我々は,正規化グラム行列が実質的に変化する場合にのみアンサンブルをリフレッシュするアンサンブルサンプリングアルゴリズムを提案することで,このギャップを狭めることを目指している。 このメカニズムは、制御されたグラム行列ドリフトを持つエポックへの摂動解析をローカライズし、十分なアンサンブルサイズを$(d\log d+d\log T)$に減らし、任意の有界なアームセットを持つアンサンブルサンプリングに対する後悔を保ちながら、最先端の$\tilde O(d^{3/2}\sqrt T)$保存する。 さらに、アーム集合が濃度$K$の有限であるとき、提案アルゴリズムはよりシャープな後悔境界$\tilde O(d\sqrt{T\log K})$を達成する。 我々の知る限り、これはランダム化された線形バンディットアルゴリズムで知られている標準的後悔のスケーリングを同時に回復する最初のアンサンブルサンプリング保証である:$\tilde O(d^{3/2}\sqrt{T})$ 任意の有界なアーム集合のレートと$\tilde O(d\sqrt{T\log K})$ 有限なアーム集合のレートである。 このアルゴリズムは過去のデータをリセットすることなく、いつでも実装可能であることも認めており、実験により、かなり小さなアンサンブルを使用しながら、ベースラインと競合することを示す。

関連論文リスト

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Parameter-Free Dynamic Regret for Unconstrained Linear Bandits [21.35587581980097]
  直交線形帯域問題における動的後悔について検討した。 順序の最適後悔保証を達成するために,線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-26T21:16:18Z)
• On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits [15.93884263655552]
  非定常線形包帯における固定予算ベストアーム識別問題について検討する。 学習者は、最大累積報酬$x_* = argmax_xを高い確率でxtopsum_t=1T _t$で識別することを目的とする。
  論文  参考訳（メタデータ） (2026-03-11T02:34:29Z)
• Improved Regret of Linear Ensemble Sampling [9.410437324336275]
  アンサンブルサイズを$T$とすると、線形アンサンブルサンプリングは$tildeO(d3/2sqrtT)$の頻繁な後悔境界を達成できる。 本稿では,線形帯域幅アルゴリズムに対する一般的な後悔分析フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-11-06T14:09:11Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Ensemble sampling for linear bandits: small ensembles suffice [75.4286948336835]
  アンサンブルサイズは$d log T$ incurs regrets the most of the order $(d log T)5/2 sqrtT$。 アンサンブルのサイズが$T$で線形にスケールする必要がなくなるような構造化された設定の最初の結果です。
  論文  参考訳（メタデータ） (2023-11-14T18:41:28Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)

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

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