Papers for

ad targeting engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Contextual bandit learning gets safer with high-probability regret bounds

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 $\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.

Wed 14 OctInformation TheoryMachine Learning
The gist
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.
Open → 2610.19513v1