pipette
ESEspañol

High-Probability Regret Bounds for Feel-Good Thompson Sampling

Xuheng Li, Qingyue Zhao, Quanquan Gu

Preprint

In the authors' words

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 -dimensional linear setting, both variants satisfy with probability at least , where 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 . The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 22 pages