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

Thank you for taking the time to review our paper. We have addressed your questions and comments below.

Q1. How is asymmetric perturbation exactly connected to hybrid regularizer in FTRL

In FTRL, additional regularization terms are often introduced to stabilize the arm-selection probabilities, e.g., to prevent abrupt changes as in Jin et al. [30]. In the FTPL framework, such stabilizing effect can be implicitly controlled by the choice of the perturbation distribution. Asymmetric perturbations can therefore be interpreted as a way to control the behavior of FTPL, where the lighter left tail introduces a stabilizing effect similar to that of an auxiliary regularizer in FTRL, such as Shannon entropy [54]. While similar effects might be reproduced by summing two independent semi-infinite perturbations with different tail indices, we expect that introducing a small probability of negative perturbations can subtly increase the conservativeness of FTPL, without altering its overall structure.

However, it remains open which class of perturbations actually corresponds to hybrid regularizers. This correspondence may be related to either a summation of independent perturbations or a single perturbation with asymmetric tail behavior, as considered in our work. Nevertheless, we believe that asymmetric perturbations, particularly those supported on $\mathbb{R}$ provide a reasonable starting point, motivated by the regularization–perturbation duality from discrete choice theory, as discussed in Section 3.2 and in our first response to Reviewer vYoW.

We thank the reviewer for the constructive feedback. Regarding the impact and implications of our results, we have briefly summarized our contributions in our response to Reviewer zV4p. We are happy to provide any additional clarification if needed.

Thank you for taking the time to review our paper and for your valuable feedback. We will include a summary table or figure (of Venn diagram) in the revised version to provide a clear overview of the position and scope of our results. As pointed out, the term "unbounded distribution" was intended to refer to distributions with support on both the positive and negative real line. We acknowledge that this terminology was unclear and will revise the manuscript to clarify our notation accordingly.

We address your specific questions and comments below. Throughout, by "semi-infinite support" we mean a distribution satisfying $\mathrm{supp} F \subseteq [\nu,\infty)$ for some finite $\nu\in \mathbb{R}$.

Q1. Hybrid regularization and hybrid perturbation (weakness 2)

We agree that summing two independent perturbations with semi-infinite supports and different tail indices $\alpha_1, \alpha_2$ can be a promising and perhaps more accessible starting point. However, it remains unclear what forms of such perturbations can effectively mimic hybrid regularizers that achieve a BOBW guarantee. Hence, it would be more beneficial to find a more systemic approach rather than adhoc approach. In previous hybrid regularization approaches, the regularizer is constructed from two distinct types. To name a few examples, as discussed in Line 82-89:

• Zimmert et al. [54] used Tsallis entropy with Shannon entropy applied to the complement in combinatorial semi-bandits, i.e., $-\sqrt{x} + \gamma (1-x)\log(1-x)$
• Jin et al. [30] used a Tsallis entropy with log-barrier to extend BOBW guarantees of FTRL in the MAB setting $-\sqrt{x} + \gamma \log x$.

In some earlier works (not necessarily in the BOBW context), hybrid regularizers are designed to penalize small probabilities, i.e., $x\to 0$, typically using log-barrier terms like $\log x$. In such cases, summing two positive-support perturbations may capture the desired behavior as you mentioned. However, in the BOBW literature, especially for combinatorial semi-bandits, hybrid regularizers commonly include an additional penalty near $x\to 1$, such as $(1-x)\log(1-x)$ (Shannon entropy to the complement). To the best of our knowledge, all known BOBW hybrid regularizers in combinatorial settings fall into this category [28, 54]. Capturing such effects via FTPL, penalizing both over-exploitation ($x\to 1$) and insufficient exploration ($x \to 0$), likely requires perturbations with support on both positive and negative sides.

From this perspective, a natural candidate for hybrid perturbation in more complex settings would be a mixture or composition of Fréchet-type and another perturbation corresponding to a non-Tsallis entropy defined on $\mathbb{R}$. As discussed in Section 3.2, the perturbations on $\mathbb{R}$ correspond to generalized entropies, via the inverse gradient of the potential function, which defines the associated FTRL policy. In this sense, perturbations on $\mathbb{R}$ may offer a more unified and systematic way to study the behavior of FTPL with the regularization–perturbation duality, particularly when leveraging insights from discrete choice theory. For this reason, we view the study of perturbations on $\mathbb{R}$ as a more principled and broadly applicable approach to designing FTPL policies.

Q2. Advantages of hybrid perturbations compared to Zhan et al. (2025) (question 1)

Thank you for pointing out this interesting reference. It is indeed interesting that a simple choice of Fréchet perturbations can achieve the BOBW guarantee.

As far as we understand, one limitation of the result in Zhan et al. (2025) lies in the looseness of the minimax regret bound, where they obtain a near-optimal guarantee of $O(\sqrt{mT}(\sqrt{d\log d}+m^{5/6}))$. While this improves upon the previous FTPL bound with exponential distribution of $O(m\sqrt{dT\log(d/m)})$ by Neu and Bartok [41], especially when $m$ does not scale with $d$, it remains suboptimal compared to the optimal $O(\sqrt{mdT})$ bounds by FTRL methods in Zimmert et al. [54] and Ito [28]. As Zhan et al. (2025) noted, achieving tighter bounds (and BOBW guarantee) are likely to require fundamentally different or more refined techniques. In that context, designing hybrid perturbations could be one of promising directions.

Thank you for taking the time to review our paper and pointing several typos in the current manuscript. We will revise the manuscript accordingly.

Q1. Insights on optimal result only for $\alpha= 2$ in stochastic setting

While $\alpha$ also influences the leading constants in the adversarial setting [37], its role is particularly critical in the stochastic setting, where the logarithmic regret is the goal. The tail index $\alpha$ controls the trade-off between exploration and exploitation in FTPL. A small $\alpha$ induces heavier tails and more frequent large deviations, encouraging exploration (e.g., by selecting arms with large $\hat{L}_t$) but potentially preventing exploitation. Conversely, larger $\alpha$ leads to lighter tails and more exploitative behavior, but with insufficient exploration to correct early misestimates.

This phenomenon is analogous to the role of $\beta$ in $\beta$-Tsallis entropy, which similarly influences the exploration–exploitation balance of FTRL. In particular, Zimmert and Seldin [53] identified $\beta = 1/2$ (corresponding to $\alpha = 2$ in our setting) as a special case that achieves optimality in both cases, and provided an intuitive explanation for its effectiveness in their Section 4.3. They also discussed why $\beta \neq 1/2$ may lead to suboptimality in Section 4.2, which further supports the delicate balance needed in tuning this parameter.

Q2. Further implication on BOBW guarantee with symmetric perturbations

As you mentioned, our current analysis does not formally rule out the possibility of achieving a BOBW guarantee with symmetric perturbations. While we do not provide a concrete counterexample, we conjecture the existence of an adaptive adversary that induces $\Omega(\sqrt{KT\log K})$ regret in this setting.

This conjecture is analogous to that in Abernethy et al. [2], who showed that FTPL achieves $O(\sqrt{KT\log K})$ regret when the hazard function $-\phi_i'/\phi_i$ is uniformly bounded. Their analysis is based on the following decomposition, believed to be tight:

To achieve $O(\sqrt{KT\log K})$ regret, it suffices to uniformly bound $\phi_i'/\phi_i$ under appropriate $\eta_t$. Since this is not possible for Gaussian perturbations (which have unbounded hazard), they conjectured that FTPL with Gaussian perturbations suffers linear regret under an adaptive adversary. In our case, the goal is to achieve the sharper $O(\sqrt{KT})$ regret, which requires $\phi_i'$ to be smaller than $\phi_i^{3/2}$ rather than $\phi_i$. Proposition 5.5 shows that this is not valid under FTPL with symmetric perturbations, which strongly suggests the suboptimality of symmetric perturbations. Although our analysis does not yield a formal lower bound, the level of informality is similar to that of Abernethy et al. [2], as both rely on decompositions regarded as tight and use them to argue that certain perturbations likely fail in adversarial settings.

Thank you for taking the time to review our paper.

Comment: The contribution of this paper feels incremental.

We believe our contribution goes beyond distributional extensions in Section 4 as explained below. By considering perturbations fully supported on $\mathbb{R}$, it becomes possible to clearly connect FTPL to discrete choice theory (Section 3, Appendix A.3), which offers a more principled approach for understanding and designing FTPL. In addition, Section 5.2 proves the first BOBW guarantee under symmetric heavy-tailed perturbations for $K=2$, building on the FTPL–FTRL duality discussed in Section 5.1. Section 5.3 then establishes a new negative result for $K\geq 3$, revealing the fundamental limitations of current analysis techniques. Taken together, these contributions go beyond simply showing that “another distribution works,” as they advance theoretical understanding and suggest new directions for FTPL design grounded in duality and tail behavior.

A more detailed explanation is summarized below:

A1. FTPL–FTRL correspondence and regret analysis beyond known cases

One motivation of our work is to explore when the recent successes of FTRL, particularly with Tsallis entropy and hybrid regularizers, can be replicated by FTPL policies, which are simpler and optimization-free. In this regard, we revisit the relationship between regularization and perturbation and investigate under what conditions such design is possible in Section 3, which may inspire the future design of FTPL.

In the two-arm setting, we show that FTRL with Tsallis entropy corresponds to FTPL with symmetric Fréchet-type tails, which numerically resemble symmetric Pareto distributions (Section 5.2). We then establish the first BOBW guarantee for this symmetric unbounded case not covered in previous FTPL work.

A2. Revealing limitations for symmetric perturbations in the general case

In contrast to the positive two-arm result, Section 5.3 shows that FTPL with symmetric perturbations fails to achieve BOBW guarantees for $K\geq 3$ under very widely used framework. Proposition 5.5 shows that key stability terms can be unbounded in this case, revealing a concrete limitation of current analysis techniques. This suggests that perturbation designs effective in two-arm settings may not generalize to larger action spaces, revealing the limitation on the approach that relies on the FTRL–FTPL correspondence established in the two-arm case [3, 32].

As briefly discussed in Section 1 and Remark 5.7, Abernethy et al. [2] analyzes FTPL using $-\phi_i'/\phi_i$ term, showing near-optimal $O(\sqrt{KT\log K})$ regret for perturbations with bounded hazard functions. Since their regret decomposition is quite tight, they conjectured that FTPL with Gaussian perturbations, whose hazard functions are unbounded, could suffer linear regret under an adaptive adversary. In our case, where the goal is $O(\sqrt{KT})$ regret, the analysis relies on the term $-\phi_i'/\phi_i^{3/2}$ as done in recent BOBW studies for FTRL and FTPL [27, 30, 37, 53]. Proposition 5.5 thus strongly suggests the existence of such adversary that forces FTPL with symmetric perturbations to suffer $\Omega(\sqrt{KT\log K})$ regret. Since the current decomposition is already almost tight (up to minor refinements), our results at least show that the current technique fails to obtain optimal regret even though the current decomposition is already almost tight. Please also see the response to Q2 of Reviewer QAp1.

A3. Bridging to discrete choice theory

We also see our results as contributing to a broader unification of FTPL design and discrete choice models extensively studied in econometrics and operations research. While prior FTPL analyses in the ML literature were often focused on perturbations with nonnegative support, our generalization to perturbations on $\mathbb{R}$ aligns more naturally with well-established (discrete choice) models like the multinomial logit or nested logit. This connection enables the application of insights and techniques from those mature fields, which may inspire future FTPL design in online learning contexts.