arXiv：cs.LG· Xuheng Li, Qingyue Zhao, Quanquan Gu·· 10 小时前
Feel-Good Thompson Sampling 的首个高概率遗憾界
High-Probability Regret Bounds for Feel-Good Thompson Sampling
AI 导读
研究者为 contextual bandits 中两种标准 Feel-Good Thompson Sampling（FGTS）变体（累积型与当前步型）推导出首个高概率遗憾界，适用于一般可实现函数逼近。
正文
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/\delta)\big)$ with probability at least $1-\delta$, 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/\delta)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.
| Comments: | 22 pages |
| Subjects: | Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.19513 [stat.ML] |
| (or arXiv:2610.19513v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19513 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Qingyue Zhao [view email]
[v1]
Wed, 14 Oct 2026 03:30:45 UTC (28 KB)
来源：arXiv：cs.LG · arxiv.org