Chen-Yu Wei's new paper gives the first Follow-the-Perturbed-Leader (FTPL) algorithm for adversarial linear bandits that achieves sqrt(T) regret over general action sets. Previous FTPL methods, such as Dani and Hayes (2006), were stuck at T^(2/3) regret for these settings, while sqrt(T) results existed only for special cases like the hypercube and Euclidean ball.
The key idea is a perturbation distribution that adapts to past reward estimators. In its simplest form, an adaptive Gaussian perturbation is straightforward to implement and already yields the improved regret bound. The author also extends the approach to random-weighting and elliptical perturbations, covering both light-tailed (Gaussian) and heavy-tailed (Student-t_2) distributions.
On the technical side, the paper develops a systematic stability analysis for FTPL using the Fisher information of the perturbation distribution. This provides a general framework that goes beyond earlier tools such as hazard-rate analysis and the FTRL-FTPL duality. Compared with oracle-efficient continuous exponential-weight algorithms, the FTPL approach is simpler to implement and generally more computationally efficient.