論文の概要: Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits

• arxiv url: http://arxiv.org/abs/2511.02123v1
• Date: Mon, 03 Nov 2025 23:25:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:05.706876
• Title: Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
• Title（参考訳）: 文脈帯域に対する可変型フェル・グード・トンプソンサンプリング
• Authors: Xuheng Li, Quanquan Gu,
• Abstract要約: FGTSVA, 変分対応型トンプソンサンプリングアルゴリズムを提案する。 新しいデカップリング係数を$mathrmdc$で表すと、FGTS-VAは$tildeO(sqrtmathrmdccdotlog|mathcalF|$)を後悔する。 文脈線形帯域の設定において、FGTSVAの後悔境界は UCB ベースと一致する
• 参考スコア（独自算出の注目度）: 54.220839560203096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Variance-dependent regret bounds have received increasing attention in recent studies on contextual bandits. However, most of these studies are focused on upper confidence bound (UCB)-based bandit algorithms, while sampling based bandit algorithms such as Thompson sampling are still understudied. The only exception is the LinVDTS algorithm (Xu et al., 2023), which is limited to linear reward function and its regret bound is not optimal with respect to the model dimension. In this paper, we present FGTSVA, a variance-aware Thompson Sampling algorithm for contextual bandits with general reward function with optimal regret bound. At the core of our analysis is an extension of the decoupling coefficient, a technique commonly used in the analysis of Feel-good Thompson sampling (FGTS) that reflects the complexity of the model space. With the new decoupling coefficient denoted by $\mathrm{dc}$, FGTS-VA achieves the regret of $\tilde{O}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^T\sigma_t^2}+\mathrm{dc})$, where $|\mathcal{F}|$ is the size of the model space, $T$ is the total number of rounds, and $\sigma_t^2$ is the subgaussian norm of the noise (e.g., variance when the noise is Gaussian) at round $t$. In the setting of contextual linear bandits, the regret bound of FGTSVA matches that of UCB-based algorithms using weighted linear regression (Zhou and Gu, 2022).
• Abstract（参考訳）: 変量依存的後悔境界は、近年の文脈的包帯の研究で注目されている。 しかしながら、これらの研究の多くは、上位信頼境界(UCB)に基づくバンドイットアルゴリズムに焦点を当てているが、トンプソンサンプリングのようなサンプリングに基づくバンドイットアルゴリズムはまだ検討されていない。 唯一の例外はLinVDTSアルゴリズム(Xu et al , 2023)であり、これは線形報酬関数に制限されており、その後悔境界はモデル次元に関して最適ではない。 本稿では,最適後悔境界を持つ一般報酬関数を持つ文脈的包帯に対する分散を考慮したトンプソンサンプリングアルゴリズムであるFGTSVAを提案する。 モデル空間の複雑さを反映したFeel-good Thompson sample (FGTS) の解析によく用いられる手法であるデカップリング係数の拡張である。 FGTS-VA は $\tilde{O}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^T\sigma_t^2}+\mathrm{dc})$ という新たなデカップリング係数を持つ。 文脈線形帯域の設定において、FGTSVAの後悔境界は重み付き線形回帰(Zhou and Gu, 2022)を用いたUTBベースのアルゴリズムと一致する。

関連論文リスト

• Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits [10.131895986034314]
  一般化線形帯域に対する一般化線形アンサンブルサンプリング(textttGLM-ES)とニューラルエンサンブルサンプリング(textttNeural-ES)である。 textttGLM-ESの$mathcalO(d3/2 sqrtT + d9/2)$と、テキストの$mathcalO(widetilded sqrtT)$の高確率頻繁な後悔境界を証明します。
  論文  参考訳（メタデータ） (2025-10-12T18:05:53Z)
• Efficient and Adaptive Posterior Sampling Algorithms for Bandits [5.050520326139362]
  我々は,有界報酬を持つ帯域幅に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。 本稿では2つのパラメータ化トンプソンサンプリングに基づくアルゴリズムを提案する。 両方のアルゴリズムが$O left(Klnalpha+1(T)/Delta right)$ regret bound, ここで$K$はアームの数、$T$は有限学習地平線、$Delta$はサブ最適アームを引っ張る際のラウンドパフォーマンス損失を表す。
  論文  参考訳（メタデータ） (2024-05-02T05:24:28Z)
• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。 われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。 我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
  論文  参考訳（メタデータ） (2024-04-09T04:45:18Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
  本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。 提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
  論文  参考訳（メタデータ） (2021-02-01T23:31:10Z)
• 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)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)

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

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