Follow-the-Perturbed-Leader for Adversarial Bandits: Heavy Tails, Robustness, and Privacy

We appreciate your time and your feedback.

Comment 1: It would be good to give some intuition behind why the algorithm `skips' losses. Is the skipping of large losses necessary? Or could a more clever analysis remove the need for this step in the algorithm?

Our response: Thank you for the question. Note that the use of "skipping" (i.e., setting zero loss estimates whenever overly-large true losses are encountered under our FTPL framework) is to control the largest possible loss estimate (in terms of absolute value under $O(\sigma (T/K)^{1/\alpha})$) and avoid directly feeding the learning algorithm with unbounded loss estimates (to ensure stability). As one particular way to achieve this goal, "skipping" itself is not the key, and there could be other alternatives. For example, Dorn et al. (2023) used a similar "truncation" technique (i.e., projecting losses to a bounded range $[a,b]$ via $\text{proj}(x) := \text{argmin}_{x'\in [a,b]}|x-x'|$ rather than "skipping") in their FTRL-based design, and the minimax-optimal regret can also be achieved (in a simpler setting where heavy-tailed losses are non-negative). While we do not know whether "skipping" is necessary, we are not aware of any existing work that handles unbounded/negative losses in similar setups without explicit skipping (or truncation).

Comment 2: Claiming Lemma 1 as a key observation seems to be an overstatement of the authors’ results, as Lemma 1 appears in previous work. It would be good if the authors could clarify what exactly is their observation when compared to previous work.

Our response: We agree that Lemma 1 is a technical result from previous work, and we would like to clarify that we did not mean to claim Lemma 1 as our finding. By "key observation", we meant that this existing stability property of FTPL could be leveraged to get around the issue of negative loss estimates suffered by FTRL (with regularizers, e.g., Tsallis entropy or Shannon entropy), as discussed in Section 5. We understand that this statement could be ambiguous and misleading. Therefore, we have improved the presentation in the updated version by emphasizing that Lemma 1 is an existing result rather than our own finding.

Comment 3: Can the results be extended to the adaptive adversary case?

Our response: In the setting with full-information feedback, it has been shown that FTPL can achieve optimal regret even against adaptive adversaries (Hutter & Poland, 2005). In the adversarial bandit literature, one common way to obtain regret guarantee against adaptive adversaries is via deriving high-probability regret guarantees against oblivious adversaries as in Lee et al. (2020) and Zimmert & Lattimore (2022). Since the high-probability regret bound of FTPL has been established in Neu & Bartók (2016) for the standard bounded loss case, we tend to believe that it is indeed a promising future work to extend our results to adaptive adversaries in the heavy-tailed case.

On the other hand, as pointed out by Arora et al. (2012), when adversaries can be adaptive, the intuitive meaning of "regret" no longer applies, as with respect to the original definition of regret, the authors showed that "while an algorithm minimizes regret, it certainly isn’t learning how to choose good actions to respond", and the proposed notion of "policy regret" is a more suitable metric. With this new definition, they show that "no bandit algorithm can guarantee a sublinear policy regret against an adaptive adversary with unbounded memory (i.e., the adversary can adapt to the entire history)". That is, it is impossible to have a no-regret algorithm under this new definition against an adaptive adversary.

References

• Dorn, Yuriy, Kornilov Nikita, Nikolay Kutuzov, Alexander Nazin, Eduard Gorbunov, and Alexander Gasnikov. "Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits." arXiv preprint arXiv:2305.06743 (2023).

• Arora, Raman, Ofer Dekel, and Ambuj Tewari. "Online bandit learning against an adaptive adversary: from regret to policy regret." In Proceedings of the 29th International Conference on International Conference on Machine Learning, pp. 1747-1754. 2012.

• Hutter, Marcus, and Jan Poland. "Adaptive Online Prediction by Following the Perturbed Leader." Journal of Machine Learning Research 6 (2005): 639-660.

• Lee, Chung-Wei, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang. "Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps." Advances in neural information processing systems 33 (2020): 15522-15533.

• Zimmert, Julian, and Tor Lattimore. "Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits." In Conference on Learning Theory, pp. 3285-3312. PMLR, 2022.

• Neu, Gergely, and Bartók Gábor. ”Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits.” (2016).

We appreciate your time and your feedback.

Comment 1: The breakthrough comes from combining known properties/schemes. Our own "new" results should be highlighted more.

Our response: We acknowledge that Lemma 1 (i.e., single-step stability with Laplace perturbation) is a known property and that we leverage the "skipping" scheme from the SOTA work of Huang et al. (2022). While this stability property is not new, as pointed out in our Remark 7, the original analysis has some gaps, and we believe that such a message is informative to the community towards building a better understanding of FTPL.

We would also like to thank the reviewer for appreciating our work from other aspects, especially addressing the challenges in choosing $L_t$ and bounding the GR error; we could not follow the standard trick in the literature that works for non-negative losses only and thus propose a new workaround by leveraging the stability.

Comment 2: It might be better to provide some examples where it is essential to model the problem with negative, heavy-tailed losses like this instead of simply changing the loss models to fit the traditional non-negative loss framework.

Our response: We are glad to know that the reviewer finds our work interesting from a theoretical point of view. Regarding your concern, it is true that one can simply shift all the losses if the effective range is bounded and known in advance, so that they fall into a non-negative range, and then one can apply the traditional framework for non-negative losses (see, e.g., Foster et al. (2020, Algorithm 3)).

However, when the losses are heavy-tailed, there does not even exist such an effective bounded range that allows us to directly obtain non-negative losses via shifting. Moreover, even when the true losses are bounded and non-negative, the fundamental issue of extremely negative loss estimates could still exist in various online learning settings (e.g., due to the privacy mechanism in our private setting, as noted in Remark 12, or some other settings including loss shifting for the best-of-both-worlds (BOBW) guarantee and incorporating exploration bonus in Policy Optimization framework, as pointed out by Dann et al. (2023)).

Comment 3: Our algorithm and results require the knowledge of heavy tail parameters. Is it possible to relax this requirement by assuming the knowledge of the upper bounds on the parameters (and suffer regret guarantee depending on the quantities of parameter upper bounds)?

Our response: The reviewer is correct. Our algorithm design and regret bound require the knowledge of heavy tail parameters $\sigma$ and $\alpha$, and in practice, these quantities may not be exactly known. If the underlying parameters $\sigma$ and $\alpha$ are unknown and we only know some upper (or lower) bounds $\sigma'$ and $\alpha'$, say, $\sigma'\geq \sigma > 0$ and $1<\alpha'\leq \alpha$, then our algorithm with $\sigma',\alpha'$ achieves a regret upper bound of $O(\sigma' K^{1-1/\alpha'}T^{1/\alpha'})$. That is, the optimality gap depends on how tight the upper (or lower) bounds $\sigma'$ and $\alpha'$ are.

Comment 4: The While-Loop could have a large runtime in the worst case (which is equal to $L_t$). Is possible to improve it?

Our response: While the While-Loop could run for $L_t$ times in the worst case, we would like to mention that it only runs at most $K$ (recall that $K$ is the number of actions) times in expectation, regardless of the value of $L_t$ (Neu & Bartók, 2016). Since the idea of GR is indeed based on Geometric distribution (i.e., repeating i.i.d. Bernoulli trials multiple times), we are not aware of any way to improve it by checking multiple new "perturbed leaders" simultaneously.

However, the running time of the GR procedure can be improved slightly as follows: since we are interested in whether the played action $a_t$ is the minimizer of $\left(\tilde{z}\_i + \sum\_{t'=1}^{t-1}\hat{\ell}\_{t',i}\right)$, it is unnecessary to directly compute the minimizer of $\left(\tilde{z}\_i + \sum_{t'=1}^{t-1}\widehat{\ell}\_{t',i}\right)$. Instead, one can first compute $\left(\tilde{z}\_{a_t} + \sum\_{t'=1}^{t-1}\widehat{\ell}\_{t',a_t}\right)$, i.e., the "perturbed (cumulative) loss" of action $a_t$. While one computes the perturbed losses of the other $K-1$ one by one, $a_t$ must not be the minimizer as soon as one finds any action that has a smaller perturbed loss (than $a_t$). Hence, one can move on to the next iteration without evaluating the cumulative losses of the remaining actions (if any).

By doing so, although the worst-case running time remains unchanged, the empirical running time can be better due to the saved calculations in this procedure.

Comment 5: Some simple experiments can help to clear further the comparison with SOTA.

Our response: We agree that it is possible that this technical assumption may purely be an artifact from the analysis for the regret guarantee. Following the suggestion, we will conduct numerical studies and compare our algorithm with the FTRL-based algorithm of Huang et al. 2022. We may not be able to finish the experiments and share the results by the end of the rebuttal period (due to the short time window), we promise that we will include such results in the final version if our paper gets accepted.

Comment 6: Corollary 1 states the results specifically with the (epsilon-DP) mechanism. Does this mean it is not applicable to some situations where the privacy is not Laplace (but still guaranteeing heavy-tailed losses)?

Our response: According to our definition of LDP bandits, it suffices to privatize every true loss by some $\epsilon$-DP mechanisms (which include but are not limited to the Laplace mechanism). Adopting any of these DP mechanisms ensures LDP. However, integrating different mechanisms into the design of the bandit algorithm could possibly lead to different regret analysis and/or guarantee. Given the known tail bounds of Laplace distribution, we chose the Laplace mechanism as the subroutine and presented its corresponding regret upper bound (which is implied by our general result for the heavy-tailed case). Of course, one can choose a different DP mechanism, e.g., the Randomized Response (Warner, 1965). While this mechanism could also result in negative losses for small $\epsilon$, our algorithm can still handle such negative losses and yield similar regret guarantees.

Comment 7: Is it possible to design an adaptive skipping threshold $r$?

Our response: Note that the skipping threshold $r$ is in the form of $r=\sigma (T/K)^{1/\alpha}$, which depends on the heavy tail parameters $\alpha$ and $\sigma$. Since our algorithm already achieves the near-optimal regret when such heavy tail parameters are known, we believe that the reviewer is asking about the adaptive skipping threshold in the case of unknown heavy-tail parameters. In this case, since another reviewer (XopM) asked a similar question, we are adapting our answer there below.

It is indeed not for free to adapt to the unknown heavy tail parameters, and the learner must suffer a (order-wise) worse regret than the known parameter case, due to some negative results from a very recent study by Genalti et al. (2023) (which was posted after the ICLR submission deadline). This paper shows that in stochastic bandits (which is, of course, a special case of adversarial bandits), "in general it is not possible to achieve the same order of performance while being adaptive to the unknown heavy tail parameters ($\sigma$ and $\alpha$)." Specifically, they show that if $\sigma$ or $\alpha$ is unknown, then in the worst case the learner must pay a worse regret (order-wise). Therefore, when heavy-tail parameters are unknown, it is not possible to still enjoy the same near-optimal regret as in the case of known heavy-tail parameters.

References

• Neu, Gergely, and Bartók Gábor. "Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits." (2016).

• Foster, Dylan J., Claudio Gentile, Mehryar Mohri, and Julian Zimmert. "Adapting to misspecification in contextual bandits." Advances in Neural Information Processing Systems 33 (2020): 11478-11489.

• Dann, Christoph, Chen-Yu Wei, and Julian Zimmert. "Best of Both Worlds Policy Optimization." In Proceedings of the 40th International Conference on Machine Learning, 202:6968–7008. Proceedings of Machine Learning Research. PMLR, 23--29 Jul 2023.

• Warner, Stanley L. "Randomized response: A survey technique for eliminating evasive answer bias." Journal of the American Statistical Association 60, no. 309 (1965): 63-69.

• Genalti, Gianmarco, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. "Towards Fully Adaptive Regret Minimization in Heavy-Tailed Bandits." arXiv preprint arXiv:2310.02975 (2023).

We appreciate your time and your feedback.

Comment 1: The heavy-tailed bandits can be trivially solved by an algorithm from an algorithm by Wei & Luo (2018, Theorem 4) (in particular, BROAD-OMD with particular choices of loss estimate, loss correction, and learning rate scheduling).

Our response: Sorry for the confusion. We thank the reviewer for this detailed and sharp comment, which helps us improve the presentation of our work. First, we would like to clarify that we did not mean to claim that FTRL cannot handle negative losses. In fact, we were aware of and did acknowledge the capability of FTRL in handling negative losses with the log-barrier regularizer (as mentioned in Footnote #5 in our original submission).

However, we would like to thank the reviewer for offering the details about how to derive the near-optimal bound using existing results. To emphasize this point, in the updated version, we have highlighted this point in the main paper and also modified other texts on this point (e.g., the discussion on log-barrier in Related Work and Section 5) to avoid confusion. In addition, considering that this point may not be obvious to readers who are not familiar with the FTRL framework and the log-barrier regularizer, we have added the detailed derivations to Appendix F and acknowledged the reviewer.

In the following, we explain that this fact does not weaken the significance of our contributions.

While log-barrier can provably handle negative/heavy-tailed losses, they suffered an extra $\text{polylog}(T)$ factor compared to our results. Moreover, one key advantage of FTPL over FTRL is from the computational perspective: while FTRL requires solving a non-linear convex program over the probability simplex in each round (to determine the action), only a linear optimization problem is needed for FTPL, "this crucial difference between FTRL and FTPL makes the latter algorithm more attractive in practice" (Suggala & Netrapalli, 2020a)). This advantage could be further amplified in non-convex online learning or dealing with adversarial MDPs (Suggala & Netrapalli, 2020a; Dai et al., 2022).

Because of such computational efficiency, the study of the under-explored FTPL framework in various online learning problems has been appreciated by the online learning community, even if the improvement in the theoretical guarantees of FTPL compared to FTRL is marginal or none (see, e.g., Dai et al. (2022), Wang & Dong (2020), Suggala & Netrapalli (2020b), and Honda et al. (2023)). Following this trend in the literature, we aim to investigate the use of FTPL in another important problem setup (namely, heavy-tailed bandits with important applications to the robust setting and the private setting).

Comment 2: It suffices to use the important weighting estimator. The use of Geometric Resampling (GR) is confusing.

Our response: The reviewer is correct that if we simply construct the unbiased loss estimates in FTPL via the standard importance-weighted (IV) estimator as in FTRL, all the analyses and results still hold (and the GR Error is simply 0 since the estimates are unbiased). However, obtaining the closed-form solution of $w_t$ in FTPL is generally a key challenge, as pointed out by Abernethy et al. (2016), and we cannot apply the IV estimator without $w_t$. That is a main reason why we need GR as an alternative to construct the loss estimates as in Neu & Bartók (2016) and Dai et al. (2022), and we have added this to Remark 4 in the revised version.

Comment 3: Any intuition on the extra $\sqrt{\ln K}$ factor in the upper bound? Is it possible to remove it?

Our response: As mentioned in Remark 2, this $\sqrt{\ln K}$ factor is due to the perturbation distribution we choose (i.e., Laplace perturbation). In the standard bounded loss case, it was first conjectured by Kim and Ambuj (2019) that "the optimal perturbation, if it exists, will be of Fréchet-type." Later in the recent work by Honda et al. (2023), the authors show that the optimal regret with Fréchet-type perturbation is $O(\sqrt{KT})$. However, in the heavy-tailed setting we consider, the analysis relies on the specific single-step stability result (which is from and specific to Laplace perturbation), which enables us to handle negative losses and show the final regret upper bound. It is unclear as for how to adopt Fréchet-type perturbation in our framework to address the heavy-tailed losses.

References

• Wei, Chen-Yu, and Haipeng Luo. "More adaptive algorithms for adversarial bandits." In Conference On Learning Theory, pp. 1263-1291. PMLR, 2018.

• Abernethy, Jacob, Chansoo Lee, and Ambuj Tewari. "Perturbation techniques in online learning and optimization." Perturbations, Optimization, and Statistics 233 (2016).

• Neu, Gergely, and Bartók Gábor. "Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits." (2016).

• Kim, Baekjin, and Ambuj Tewari. "On the optimality of perturbations in stochastic and adversarial multi-armed bandit problems." Advances in Neural Information Processing Systems 32 (2019).

• Honda, Junya, Shinji Ito, and Taira Tsuchiya. "Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems." International Conference on Algorithmic Learning Theory. PMLR, 2023.

• Dai, Yan, Haipeng Luo, and Liyu Chen. "Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback." In Advances in Neural Information Processing Systems, 2022.

• Suggala, Arun, and Praneeth Netrapalli. "Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games." Advances in Neural Information Processing Systems 33 (2020a): 22316-22326.

• Wang, Yuanhao, and Kefan Dong. "Refined analysis of fpl for adversarial markov decision processes." Theoretical Foundations of Reinforcement Learning Workshop, ICML, 2020.

• Honda, Junya, Shinji Ito, and Taira Tsuchiya. "Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems." International Conference on Algorithmic Learning Theory. PMLR, 2023.

• Suggala, Arun Sai, and Praneeth Netrapalli. "Online non-convex learning: Following the perturbed leader is optimal." In Algorithmic Learning Theory, pp. 845-861. PMLR, 2020b.

We appreciate your time and your feedback.

Comment 1: Notice that the FTRL algorithm is best-of-both-worlds (see Huang et al. (2022)). Does the proposed algorithm can achieve optimal regret in the stochastic setting?

Our response: Thank you for the question. It is still unclear whether the proposed algorithm can achieve optimal regret in the stochastic setting.

On the one hand, note that in Huang et al. (2022), their best-of-both-worlds (BOBW) guarantee still requires the "truncated non-negativity" assumption. Specifically, this assumption serves two purposes: (1) stability and the regret guarantee in the adversarial setting (which is the focus of our work); (2) self-bounding property and regret guarantee in the stochastic setting (since it is not the focus of our work, it is not discussed in our paper; see Eq. (10) and Lemma A.5 in Huang et al. (2022) for the key steps). Since their analyses heavily rely on this assumption, it is unclear whether their algorithm can still achieve BOBW guarantees without such technical assumptions.

On the other hand, to the best of our knowledge, the only existing result on the BOBW guarantee of FTPL is from a recent study by Honda et al. (2023) (but for the case of standard bounded losses), where they use a different type of perturbation (Fréchet-type perturbation) as mentioned in Remark 2 in our paper. However, their analyses rely heavily on the particular form of the Probability Density Function (PDF) for Fréchet-type perturbation. It remains unclear as for how to combine their work with ours to show BOBW guarantees under the FTPL framework in the heavy-tailed setup.

Comment 2: It would be better if the paper includes some empirical analysis of real world applications.

Our response: Thank you for the suggestion. We will conduct simulations and include empirical results in future versions. Given the short time window, we may not be able to finish it and include the results by the end of the rebuttal period, but we promise that we will include them in the final version if it gets accepted.

Comment 3: Is it possible to design a near-optimal algorithm for bandits with heavy-tailed loss if we don't know the heavy-tail parameters?

Our response: Thank you for the question. The answer is no, due to some negative results from a very recent study by Genalti et al. (2023, Theorems 2 and 3) (which was posted after the ICLR submission deadline). This paper shows that in stochastic bandits (which is, of course, a special case of adversarial bandits), "in general it is not possible to achieve the same order of performance while being adaptive to the unknown heavy tail parameters ($\sigma$ and $\alpha$)." Specifically, they show that if $\sigma$ or $\alpha$ is not known, then in the worst case the learner must pay a worse regret (order-wise). Therefore, it is not possible to still enjoy the near-optimal regret in the known parameter case when heavy tail parameters are unknown.

References

• Huang, Jiatai, Yan Dai, and Longbo Huang. "Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits." In International Conference on Machine Learning, pp. 9173-9200. PMLR, 2022.

• Honda, Junya, Shinji Ito, and Taira Tsuchiya. "Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems." International Conference on Algorithmic Learning Theory. PMLR, 2023.

• Genalti, Gianmarco, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. "Towards Fully Adaptive Regret Minimization in Heavy-Tailed Bandits." arXiv preprint arXiv:2310.02975 (2023).