論文の概要: Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
- arxiv url: http://arxiv.org/abs/2510.10730v1
- Date: Sun, 12 Oct 2025 18:05:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-14 18:06:30.088091
- Title: Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
- Title（参考訳）: 非線形コンテキスト帯域における確率的随時アンサンブルサンプリングアルゴリズム
- Authors: Jiazheng Sun, Weixin Wang, Pan Xu,
- Abstract要約: 一般化線形帯域に対する一般化線形アンサンブルサンプリング(textttGLM-ES)とニューラルエンサンブルサンプリング(textttNeural-ES)である。
textttGLM-ESの$mathcalO(d3/2 sqrtT + d9/2)$と、テキストの$mathcalO(widetilded sqrtT)$の高確率頻繁な後悔境界を証明します。
- 参考スコア（独自算出の注目度）: 10.131895986034314
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Ensemble Sampling (\texttt{GLM-ES}) for generalized linear bandits and Neural Ensemble Sampling (\texttt{Neural-ES}) for neural contextual bandits. Both methods maintain multiple estimators for the reward model parameters via maximum likelihood estimation on randomly perturbed data. We prove high-probability frequentist regret bounds of $\mathcal{O}(d^{3/2} \sqrt{T} + d^{9/2})$ for \texttt{GLM-ES} and $\mathcal{O}(\widetilde{d} \sqrt{T})$ for \texttt{Neural-ES}, where $d$ is the dimension of feature vectors, $\widetilde{d}$ is the effective dimension of a neural tangent kernel matrix, and $T$ is the number of rounds. These regret bounds match the state-of-the-art results of randomized exploration algorithms in nonlinear contextual bandit settings. In the theoretical analysis, we introduce techniques that address challenges specific to nonlinear models. Practically, we remove fixed-time horizon assumptions by developing anytime versions of our algorithms, suitable when $T$ is unknown. Finally, we empirically evaluate \texttt{GLM-ES}, \texttt{Neural-ES}, and their anytime variants, demonstrating strong performance. Overall, our results establish ensemble sampling as a provable and practical randomized exploration approach for nonlinear contextual bandits.
- Abstract（参考訳）: 本稿では, 非線形文脈帯域におけるアンサンブルサンプリングのための統一的アルゴリズムフレームワークを提案し, 一般線形帯域に対する一般線形アンサンブルサンプリング (\texttt{GLM-ES}) と, ニューラルアンサンブルサンプリング (\texttt{Neural-ES}) の2つの最も一般的な非線形文脈帯域設定に対して, 対応する後悔境界を開発する。
どちらの手法も、ランダムな摂動データに対する最大推定により、報酬モデルパラメータの複数の推定器を維持できる。
高確率頻繁な後悔的境界を証明し、$\mathcal{O}(d^{3/2} \sqrt{T} + d^{9/2})$ for \texttt{GLM-ES} と $\mathcal{O}(\widetilde{d} \sqrt{T})$ for \texttt{Neural-ES} ここで$d$は特徴ベクトルの次元、$\widetilde{d}$はニューラル接核行列の有効次元、$T$はラウンドの数である。
これらの後悔境界は、非線形文脈帯域設定におけるランダム化探索アルゴリズムの最先端の結果と一致する。
理論的解析では,非線形モデルに特有の課題に対処する手法を導入する。
実際に,我々のアルゴリズムの任意の時間バージョンを開発することで,固定時間地平線仮定を除去する。
最後に,<texttt{GLM-ES} ,<texttt{Neural-ES} およびそれらの常用変種を実証的に評価し,高い性能を示した。
本研究の結果は, ランダムなランダム化探索手法として, アンサンブルサンプリングを確立した。
関連論文リスト
- Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
ニューラルネットワークを利用して非線形ユーティリティ関数を近似する分散認識アルゴリズムを提案する。
十分広いニューラルネットワークに対して,我々のアルゴリズムが次数$bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt)のサブ線形累積平均後悔を達成できることを示す理論的保証を確立する。
論文 参考訳（メタデータ） (2025-06-02T01:58:48Z) - Improved Regret of Linear Ensemble Sampling [9.410437324336275]
アンサンブルサイズを$T$とすると、線形アンサンブルサンプリングは$tildeO(d3/2sqrtT)$の頻繁な後悔境界を達成できる。
本稿では,線形帯域幅アルゴリズムに対する一般的な後悔分析フレームワークを提案する。
論文 参考訳（メタデータ） (2024-11-06T14:09:11Z) - Restless Linear Bandits [5.00389879175348]
未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。
指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
論文 参考訳（メタデータ） (2024-05-17T14:37:39Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。
提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
論文 参考訳（メタデータ） (2021-02-01T23:31:10Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。