High-Probability Regret Bounds for Feel-Good Thompson Sampling
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 Regret(T)=O(d√Tlog(2T)+√Tlog(1/δ)) 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.
Related
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
- Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
- When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity
- Thompson Sampling for Learning in Zero-Sum Games
BibTeX
@misc{li2026highprobability,
title = {{High-Probability Regret Bounds for Feel-Good Thompson Sampling}},
author = {Xuheng Li and Qingyue Zhao and Quanquan Gu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19513},
eprint = {2610.19513},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19513},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - High-Probability Regret Bounds for Feel-Good Thompson Sampling
AU - Xuheng Li
AU - Qingyue Zhao
AU - Quanquan Gu
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19513
UR - https://arxiv.org/abs/2610.19513
AB - 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 Regret(T)=O(d√Tlog(2T)+√Tlog(1/δ)) 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.
ER -