High-Probability Regret Bounds for Feel-Good Thompson Sampling
Feel-Good Thompson Sampling (FGTS) addresses slow exploration in vanilla TS by adding an optimism term to the posterior. This paper proves the first high-probability regret bounds for both cumulative and current-step FGTS under general realizable function approximation, showing that in linear contextual bandits the regret scales as $O(d\sqrt{T}\log(2T)+\sqrt{T}\log(1/\delta))$ with probability at least $1-\delta$. The core technique is applying Markov's inequality to exponential quantities derived from the posterior normalizer, avoiding explicit confidence-set constructions.
The paper makes a meaningful theoretical advance by closing the gap between expected and high-probability analysis for FGTS, recovering the linear-bandit minimax rate up to logarithmic factors. The distinction between the telescoping normalizer argument for cumulative exploration and the pathwise noise-coupling argument for current-step exploration is elegant. However, the work offers no empirical validation, the hyperparameter recipes depend on unknown problem quantities, and the authors' admission that proof ideas were partially generated by GPT-6 Astra raises serious concerns about attributable novelty and rigorous human verification.
The exponential-inequality framework is technically sound and elegantly sidesteps the need for explicit confidence sets for posterior draws. The telescoping bound for Type A—where successive normalizers cancel contributions conditional on history—and the joint treatment of shared noise in the Type-B posterior ratio are strong, non-trivial adaptations of existing decoupling ideas to the high-probability regime.
Three issues stand out. First, practical deployability is weak: Theorems 4.3 and 4.4 require setting hyperparameters based on the unknown decoupling coefficient $d_c$ and the prior mass $p_0(\mathcal{F}_{1/T})$, and no adaptive tuning procedure is provided. Second, the paper contains no experiments; even a toy linear simulation would help verify that the improved confidence dependence translates into better finite-sample behavior than standard TS or UCB.\nThird, the disclosure that the proof ideas were partially developed by GPT-6 Astra under the authors' guidance is an unprecedented transparency statement. While the authors claim to have verified details, this admission undermines confidence in human novelty and raises accountability concerns that the current peer-review process is not equipped to adjudicate.
The theoretical evidence is internally consistent and the positioning against related work is fair. The linear specialization correctly attains the $O(d\sqrt{T})$ minimax rate up to logarithmic factors, and the authors honestly note that their $\delta$ dependence differs from that of OFUL and SupLinUCB. The decoupling coefficients naturally generalize the linear covariance and elliptical-potential arguments. That said, the absence of any empirical baseline means there is no evidence that the bound's superior confidence scaling actually translates into improved realized regret in practice.
The proofs are detailed in the appendices with explicit lemmas and hyperparameter settings, so an expert could in principle verify the chain of inequalities. However, several barriers block independent reproduction: no code, data, or finite-dimensional algorithmic instantiation is provided; the normalizing integrals $Z_t^A$ and $Z_t^B$ involve expectations over general function classes whose computation is unspecified; and the reliance on LLM-generated proof ideas introduces an unverifiable dependency that complicates step-by-step human reconstruction. The paper would benefit enormously from a small open-source simulation to ground the abstract bounds.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.