Feel-good Thompson sampling (FGTS) is a variant of the classic Thompson sampling algorithm for sequential decision-making. Instead of relying solely on the posterior distribution over reward functions, FGTS adds an exploration term that biases the sampling toward reward functions with high predicted optimal values. This encourages the algorithm to try actions that could lead to large rewards, even when the posterior is uncertain.
The new paper provides a theoretical analysis of FGTS, deriving regret bounds that hold with high probability rather than only on average. This is a stronger guarantee, as it bounds the risk of the algorithm performing poorly in any given run. The authors show that FGTS attains minimax-optimal regret, meaning its worst-case performance matches the best possible rate for this class of problems.
These results help clarify why the feel-good heuristic works and offer a principled alternative to other exploration strategies in bandit and reinforcement learning settings. The proof techniques may also be useful for analyzing other algorithms that combine posterior sampling with optimism-based exploration.