Contextual bandit learning gets safer with high-probability regret bounds
High-Probability Regret Bounds for Feel-Good Thompson Sampling
Information TheoryMachine Learning
Summary
Imagine you’re trying to pick the best option repeatedly, learning from past results, but want to be confident not to make many mistakes. The paper studies a method called Feel-good Thompson Sampling (FGTS), which helps balance trying new options and sticking to good ones. The authors show for the first time that FGTS can guarantee good performance not just on average but almost always, providing reliable safety bounds. This adds more certainty to using FGTS in settings where learning with contextual hints guides decisions.
What this means in practice
- •For online recommendation teams: Ensure recommendation algorithms safely learn effective choices with fewer unexpected failures over time using FGTS with high-probability regret guarantees.
- •For ad targeting engineers: Design ad delivery systems that balance exploring new user segments and exploiting known preferences while keeping strong confidence guarantees on performance.
Authors
Xuheng Li, Qingyue Zhao, Quanquan Gu
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.