Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems

Follow-the-Regularized-Leader (FTRL) policies have achieved Best-of-Both-Worlds (BOBW) results in various settings through hybrid regularizers, whereas analogous results for Follow-the-Perturbed-Leader (FTPL) remain limited due to inherent analytical challenges. To advance the analytical foundations of FTPL, we revisit classical FTRL-FTPL duality for unbounded perturbations and establish BOBW results for FTPL under a broad family of asymmetric unbounded Fréchettype perturbations, including hybrid perturbations combining Gumbel-type and Fréchet-type tails. These results not only extend the BOBW results of FTPL but also offer new insights into designing alternative FTPL policies competitive with hybrid regularization approaches. Motivated by earlier observations in two-armed bandits, we further investigate the connection between the 1/2-Tsallis entropy and a Fréchet-type perturbation. Our numerical observations suggest that it corresponds to a symmetric Fréchet-type perturbation, and based on this, we establish the first BOBW guarantee for symmetric unbounded perturbations in the two-armed setting. In contrast, in general multi-armed bandits, we find an instance in which symmetric Fréchet-type perturbations violate the key condition for standard BOBW analysis, which is a problem not observed with asymmetric or nonnegative Fréchet-type perturbations. Although this example does not rule out alternative analyses achieving BOBW results, it suggests the limitations of directly applying the relationship observed in two-armed cases to the general case and thus emphasizes the need for further investigation to fully understand the behavior of FTPL in broader settings. * He was affiliated with Seoul National University at the time of submission. 39th Conference on Neural Information Processing Systems (NeurIPS 2025).

in discrete choice theory, a field in economics that models decision-making through probabilistic frameworks to maximize utility over finite alternatives [51]. In particular, FTPL is known as the additive random utility model [5,50], while FTRL corresponds to the representative agent model [4].

Beyond these conceptual analogies, a line of work has formalized the relationship between FTPL and FTRL in discrete choice theory [21,27]. In particular, when the joint perturbation distribution has a strictly positive density on R K , the existence of a corresponding regularizer, along with detailed results on its properties, has been established [19,44]. A classical example is the multinomial logit model [40], known to be equivalent to both FTPL with Gumbel perturbations (also known as Exp3 [7,48]) and FTRL with a Shannon entropy regularizer [4]. In the context of online learning, Abernethy et al. [3] discussed this relationship for general perturbations, where the formal theorem was later established for the independent and identically distributed (i.i.d.) perturbations absolutely continuous with respect to Lebesgue measure by Suggala and Netrapalli [49, Proposition 3.1].

While the above results mainly discuss the transformation of FTPL into FTRL, Abernethy et al. [1,3] demonstrated that (nearly) every instance of FTRL can be viewed as a special case of FTPL in one-dimensional online optimization and more general equivalences are discussed by Feng et al. [19]. Nevertheless, when K ≥ 4, no FTPL counterpart exists for FTRL with log-barrier regularizer [27, Proposition 2.2] and Tsallis entropy regularizer [33, Theorem 8]. These findings indicate that FTRL strictly subsumes FTPL as a special case.

Despite this narrower coverage, FTPL has gained significant attention due to its computational efficiency and simplicity, making it suitable for a variety of problems in online learning, including combinatorial semi-bandits [43], online learning with non-linear losses [17], and MDP bandits [15]. Still, while FTRL policies have achieved optimal results in several problems such as graph bandits [16] and partial monitoring [52], comparable progress for FTPL has been relatively underexplored.

This gap is primarily due to the complexity of expressing arm-selection probabilities of FTPL, which poses significant analytical challenges despite its computational efficiency in practice. In the standard analysis of FTRL and FTPL, a key factor in achieving the optimal adversarial regret is evaluating the stability of the arm-selection probability against the changes in the estimated cumulative loss. Abernethy et al. [2] tackled this challenge by leveraging the hazard function of perturbations, but it only resulted in near-optimal regret of O( √ KT log K). Later, motivated by the observation in twoarmed bandits that FTRL with β-Tsallis entropy roughly correspond to Fréchet-type perturbations with tail index (1 -β) -1 , Kim and Tewari [33] conjectured that FTPL with Fréchet-type distributions could achieve optimal O(