論文の概要: High-Probability Regret Bounds for Feel-Good Thompson Sampling

• arxiv url: http://arxiv.org/abs/2610.19513v1
• Date: Wed, 14 Oct 2026 03:30:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.937604
• Title: High-Probability Regret Bounds for Feel-Good Thompson Sampling
• Title（参考訳）: Feel-Good Thompsonサンプリングのための高確率レギュレット境界
• Abstract要約: フィールグッドトンプソンサンプリング(FGTS)は、バニラトンプソンサンプリングの後部を、高い予測最適値の報酬関数を求める探索項で強化する。 コンテクスト的包帯における累積FGTSと現在のステップFGTSの両方に対する最初の高い確率的後悔境界を導出する。 期待された信頼の保証とは対照的に、後悔を高い確率で制御するコストは加法項に制限される。
• 参考スコア（独自算出の注目度）: 50.91983233376599
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.
• Abstract（参考訳）: フィールグッドトンプソンサンプリング(FGTS)は、バニラトンプソンサンプリングの後部を、高い予測最適値の報酬関数を求める探索項で強化する。 この修正は、線形文脈的包帯における対数的要因に対する極小最大最適後悔を実現するが、既存の2つの標準変種の分析は、期待する上での後悔の保証を定めている。 本稿では、一般化可能な関数近似を用いた文脈帯域における累積FGTSと電流ステップFGTSの両方に対する最初の高確率後悔境界を導出する。 我々の境界は、対応する疎結合係数と、真の報酬関数に近い前の質量に依存する。 d$-次元線型設定では、どちらの変種も $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ を満たす。 このバウンダリは、アルゴリズムの次元と地平線依存を、対数的要因までの上限値に基づいて一致させる。 期待される信頼の保証とは対照的に、高い確率で後悔を制御するコストは、$\log(1/δ)$に最も線型依存する加法項に制限される。 証明のアイデアは著者の指導の下でGPT-6 Astraによって部分的に開発されている。

関連論文リスト

• Reliable Scale-Free Bandits via Empirical Likelihood [2.5361601273217973]
  ほぼ確実に後悔の保証は、最終的な学習を記述しているが、パフォーマンスや有限実行時の大きな後悔のリスクを期待していない。 我々は,Cowan と Katehakis の $g-Forcing Policy (2020) の任意の経験的拡張である $textttEL-F$ を紹介する。 実験では、挑戦的なインスタンスに対する$g$-Forcingと比較して、長時間の最適部分割り当ての削減が示されている。
  論文  参考訳（メタデータ） (2026-10-13T09:43:54Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling [6.1259398119902]
  我々は、一般化線形帯域問題の解法として、$$-TSと呼ばれるトンプソンサンプリングアルゴリズムの変種について研究する。 分散インフレーションの考え方は、標準後部ではなく分数または$$-posteriorを使用する$-TSを導入することで定式化する。 本研究の主な貢献は, 先行分布および報奨分布の一般規則性条件の同定であり, 後部分布の抽出可能な近似を仮定することなく, 約$-TSの後悔解析を可能にする。
  論文  参考訳（メタデータ） (2026-09-02T02:17:05Z)
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits [54.220839560203096]
  FGTSVA, 変分対応型トンプソンサンプリングアルゴリズムを提案する。 新しいデカップリング係数を$mathrmdc$で表すと、FGTS-VAは$tildeO(sqrtmathrmdccdotlog|mathcalF|$)を後悔する。 文脈線形帯域の設定において、FGTSVAの後悔境界は UCB ベースと一致する
  論文  参考訳（メタデータ） (2025-11-03T23:25:41Z)
• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• 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)
• 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)

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

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