Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting

We first would like to thank Reviewer q85G for carefully reading our work and providing constructive comments, which significantly help us improve our work. We are also glad to further engage in interactive discussions with the reviewer.

Cmt 1: Why Eq. (55) holds

Re: This is indeed a mis-calculation. After correction, Eq. (55) should be

$\\left| \\widehat{L}\_{t,i} - \\sum_{s=1}^t \\mu\_{s,i} \\right| \\leq \\text{Width}(t)\\cdot t/ \\tau\_i ,$ where basically the original $\text{Width}(\tau_i)$ is now replaced with $\text{Width}(t)$. Eq. (51) now implies that $\\left|\\hat{L}\_{t,i} - \\sum\_{s=1}^t\mu\_{s,i}\\right| \\leq \\mathbb{I}\\{i\\in A\_t\\} \text{Width}(t) +\mathbb{I}\\{i\notin A_t\\} \text{Width}(t)\frac{t}{\tau_i}.$ In other words, before the deactivation ($t\leq \tau_i$), the tightness of our control on $\\left|\\widehat{L}\_{t,i} - \sum_{s=1}^t \mu_{s,i}\\right|$ is unchanged, and after that, it becomes looser (with $\\text{Width}(\\tau\_i)$ replaced by $\text{Width}(t)$).

While this correction leads to changes in tests (6)-(8), we justify that we will still get the claimed regret guarantee (albeit an extra log factor in the adversarial regime). The key intuition is that, to fix this gap, we are replacing $\text{Width}(\tau_i)$ with $\text{Width}(t)$ in some steps, which is the same thing we did in the last step of Eq. (75) in the current proof. In other words, these $\text{Width}(\tau_i)$ in the analysis eventually becomes $\text{Width}(t_{\text{sw}})$, sooner or later.

We provide the complete roadmap below.

A. New tests (6)-(8)

The corrected tests (6)-(8) should be like:

\\text{test (6):} \\exists i\\in[K] \\text{\~such that\~}\\left| \\frac{\\widehat{L}\_{t,i}}{t} - \\widehat{\\mu}\_{t,i} \\right|> 9u\\left(\\log(\\beta/\\zeta)/ N\_{t,i} \\right)^{\\frac{v}{1+v}} + \\mathbb{I}\\{i\\in A\_t\\}\\frac{\\text{Width}(t)}{t} + \\mathbb{I}\\{i\\notin A\_t\\}\\frac{\\text{Width}(t)}{\\tau\_i}, \\text{test (7):} \\exists i\\notin A\_t \text{\~such that\~} (\\hat{L}\_{t,i} - \\min\_{j\\in A_t} \\hat{L}\_{t,j})/t > (c_1 + 4)\\text{Width}(t)/(\\tau_i -1), \\text{test (8):} \\exists i\\notin A\_t \\text{\~such that\~} (\\hat{L}\_{t,i} - \\min\_{j\\in A_t} \hat{L}_{t,j})/t \leq (c_1 - 4)\text{Width}(t)/\tau_i,

B. Stochastic regime

After correcting Eq. (55) and tests (6)-(8), the bound in stochastic regime is unchanged, following the three steps in Sec. 4.2.1 (lines 274-280). That is, we are still able to show that (modified) tests (6)-(8) never fail. Then, steps 2 and 3 are not affected (step 2 is only about the round up to $\tau_i$, not after, and step 3 is only about the sampling strategy), so we get the same bound.

C. Adversarial regime

The key is whether the modified tests will impact the analysis and the guarantee in the adversarial regime, which we will show below is not the case.

C.1. Regret decomposition

To get the regret decomposition in Eq. (13), it is crucial to show that Eq. (66) is still true. With the modified tests, we can still show that (again with $\text{Width}(\tau_i-1)$ replaced with $\text{Width}(t_{\text{sw}}-1)$): $\sum_{s=1}^{t_{\text{sw}}-1} \mu_{s,i} - \sum_{s=1}^{t_{\text{sw}}-1} \mu_{s,I^*_{t_{\text{sw}}-1}} > (c_1-6) \frac{t_{\text{sw}}-1}{\tau_i-1} \text{Width}(t_{\text{sw}}-1) \geq 0.$ Therefore, the regret decomposition in Eq. (13) still holds. The next step is to bound parts A, B, and C therein.

C.2. Parts A and B

With the modified tests, now we have $\text{part A} = O\left(\left(\frac{\log(\beta/\zeta)}{N_{t_{\text{sw}}-1,i}}\right)^{\frac{v}{1+v}} + \frac{\text{Width}(t_{\text{sw}}-1)}{\tau_i-1} \right),$ and $\text{part B} = O\left(\text{Width}(t_{\text{sw}}-1)/(\tau_i -1) \right).$ Both of them have the original $\text{Width}(\tau_i-1)$ replaced with $\text{Width}(t_{\text{sw}}-1)$.

C.3. Part C

Since part C is related to action $i^*_{t_{\text{sw}}-1}$ only, which is active in round $t_{\text{sw}}-1$ as shown in C.1 above, it is not affected, and we still have $\text{part C} = O\left(\text{Width}(t_{\text{sw}}-1)\right)$ C.4. Final calculation

Combing three terms, now Eq. (75) becomes $\\sum\_{s=1}^{t\_{\\text{sw}}-1}\\mu\_{s,a\_t} - \\sum\_{s=1}^{t\_{\\text{sw}}-1}\\mu\_{s,i^*} = O\\left(\\sum\_{i=1}^K N\_{t\_{\\text{sw}}-1,i} \\cdot u\\left( \\frac{\\log(\\beta/\\zeta)}{N\_{t\_{\\text{sw}}-1,i}} \\right)^{\\frac{v}{1+v}} \\right)+ O\\left( \\underbrace{\\sum\_{i=1}^K N\_{t\_{\\text{sw}}-1,i}\\frac{\\text{Width}(t\_{\\text{sw}}-1)}{\\tau_i -1}}\_{\\text{* term}} \\right) + O\\left( \\text{Width}(t\_{\\text{sw}}-1) \\right).$ The first and third term are the same as original ones (and can be well bounded), and in the second term (* term), the previous $\text{Width}(\tau_i-1)$ becomes $\text{Width}(t_{\text{sw}}-1)$, which will be our focus below.

Applying Lemma 6 to $N\_{t\_{\\text{sw}}-1,i}$ and expanding $\text{width}(\cdot)$, the * term is bounded by

$O\\left( \\sum_{i=1}^K\\left( q_i \\tau_i(1+\\log T)\\right)\\frac{u K^{\\frac{v}{1+v}} (t_{\\text{sw}}-1)^{\frac{1}{1+v}} \\left(\\log(\\beta/\\zeta) \\right)^{\\frac{3v}{3v+1}}}{\\tau_i -1} + \\sum_{i=1}^K\\log(\\beta/\\zeta)\\frac{u K^{\\frac{v}{1+v}} (t_{\\text{sw}}-1)^{\\frac{1}{1+v}} \\left(\\log(\\beta/\\zeta)\\right)^{\\frac{3v}{3v+1}}}{\\tau_i -1}\\right).$

The first part is not new and is bounded using $\\sum_{i=1}^K q_i = O(\\log K)$, and the second part (which used to be a lower-order term) is also under control since $\\tau_i \\geq K+1$ due to the initialization in Algorithm 2.

Finally, now the bound becomes

$\\sum_{s=1}^{t_{\\text{sw}}-1} \\mu_{s,a_t} - \\sum_{s=1}^{t_{\\text{sw}}-1} \\mu_{s,i^*} = O\\left( (\\log K) (\\log T) u K^{\frac{v}{1+v}} (t_{\\text{sw}}-1)^{\\frac{1}{1+v}} \\left(\\log(\\beta/\\zeta)\\right)^{1 + \\frac{3v}{3v+1}} \\right).$

After correction, it has an extra $\\left( \\log(\\beta/\\zeta) \\right)$ factor, which is coming from the second part of the * term.

Cmt 16: Explain more on (63).

Re: According to Line 14 of Algorithm 2, the probability of pulling a deactivated arm keeps decaying since its deactivation, and all active arms equally share the remaining probability mass. For the first action to be deactivated (denoted by $1'$), $q_{1'}$ is exactly $1/K$. For the second one $(2')$, we clearly have $q_{2'}\leq \frac{1}{K-1}$. So in general, we have $q_{i'}\leq \frac{1}{K-i'+1}$, and $\\sum\_{i=1}^K q\_i = \\sum\_{i'=1}^K q\_{i'} \\leq \\sum\_{i'=1}^K \\frac{1}{K-i'+1}.$ We will attach the explanation to it.

Referrences

[1] Huang, Jiatai, Yan Dai, and Longbo Huang. "Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits." international conference on machine learning. PMLR, 2022. https://proceedings.mlr.press/v162/huang22c.html

[2] Genalti, Gianmarco, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. "$(ε, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits." In The Thirty Seventh Annual Conference on Learning Theory, pp. 1882-1915. PMLR, 2024. https://proceedings.mlr.press/v247/genalti24a.html

[3] 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. https://proceedings.neurips.cc/paper_files/paper/2020/hash/b2ea5e977c5fc1ccfa74171a9723dd61-Abstract.html

Cmt 2: Comparision with Huang et al. (2022) and Genalti et al. (2024)

Re: We agree that: these two assumptions (i.e., 1) truncated non-negative losses and 2) the knowledge of $u,v$) are in general incomparable to say which one is weaker. However, we would like to clarify that the setup we study in this work is to achieve the BOBW regret guarantee with the knowledge of $u,v$. Under this setup, [1] achieved the optimal BOBW guarantee with the additional truncated non-negative loss assumption, and the goal in our work is to still achieve the BOBW guarantee, while removing this assumption.

While there are $(u,v)$-adaptive algorithms proposed in [1, 2], they handle one single regime only (adversarial regime in [1] and stochastic regime [2]) and even require the truncated non-negative loss assumption. In other words, there is no result achieving $(u,v)$-adaptive BOBW guarantee. Therefore, these adaptive results are not comparable to ours.

Cmt 3: Proof of Lemma 2 - step 2 (p. 17)

Re: Thanks for catching this. This is indeed a gap in our analysis, as $\\bar{w}_t$, obtained from the OMD update, is not controlled by $\\rho_t$.

We propose a fix to this, which is an update rule change in Line 7 of our Algorithm 1. That is, instead of first performing OMD update over the entire probability simplex to get $\\bar{w}_t$ and then getting $w_t$, we directly perform OMD update over the truncated simplex $\\Omega’$ as in the original paper [3], that is

$w\_{t+1} = \\text{argmin}\_{x\\in \\Omega'} \\left( \\langle x,\\hat{\\ell}\_t \\rangle + D\_{\\phi\_t} (x, w_t)\\right),$ where $\\Omega’:=\\{x\\in \\Omega: x(i) \\geq \\lambda/K, \\forall i\\in [K]\\}.$

By doing this, the $\bar{w}\_t$ in the the analysis will become $w\_t$ (which is controlled by $\rho\_t$) and the entire proof will become the same as that of [3], where there’s no longer mismatching between $w\_t$ and $\bar{w}\_t$, and the additional regret due to truncating the simplex in the update can be bounded as in our Lemma 3 (line 588), given that $\lambda$ is small enough. One potential disadvantage of doing so is that it’s unclear to us how to perform the efficient implementation (as mentioned in line 219) when the OMD update is over the truncated simplex $\Omega’$ (which was also our motivation to modify the original update rule in [3]).

Cmt 4: Proof for adversarial setting (Alg. 2)

Re: Thanks for catching this typo. The $\leq$ in Eq. (6) (Line 12 in Algorithm 2) should be $>$.

Cmt 5: What is $\\widehat{L}_{t\_{\\text{sw}-1}}'$?

Re: It should be $\\widehat{L}\_{t\_{\\text{sw}-1}}$, the cumulative IW estimate.

Cmt 6: The bounds do not match between Eq. (64) and Theorem 2.

Re: Thanks for catching this. The correct bound should follow Eq. (64) from the proof, which has an additional logarithmic factor.

Cmt 7: $\\hat{y}_t$ in (2)

Re: It should be $\hat{\ell}_t$, the loss estimate sequence.

Cmt 8: $t_{\text{quit}}$ in (13)

Re: $t_{\text{quit}}$ was meant to be $t_{\text{sw}}$.

Cmt 9: Why Eq. (59) holds for all actions in $[K]$

Re: According to lines 657-658, for any action $i$ deactivated at round $\\tau\_i$, test (5) must fail in round $\\tau\_i-1$ (and is satisfied in round $\\tau\_i$). To derive Eq. (59), we are looking at round $\tau_i-1$ for each action $i$, not round $t$. We will improve the writing of this part.

Cmt 10: $c\_1=6$ seems unnecessary

Re: Our intention was to separate free constants (namely, $c\_1\\geq 6$ which can be freely chosen) from the others (some “2” coming from the proof). As a revision in Alg. 2, we will write $c\_1 \\geq 6$ in the "Input:" rather than $c\_1 = 6$ in the "Define:"

Cmt 11: Line 629: first some -> first fix some?

Re: Yes, thanks for spotting this typo.

Cmt 12: Line 631: why $w\_{s,i}$ is non-decreasing?

Re: Correct. $w\_{s,i}$ is non-decreasing only up to round $s =\\tau\_i$. We will refine this statement. The proof after it does not rely on increasing $w\_{s,i}$ after round $\tau\_i$.

Cmt 13: unfinished log term appears in (48).

Re: Thanks for catching this. It was meant to be $\log(2T/\zeta)$ according to the last line in Page 22.

Cmt 14: It would be better to specify that Lemma 8 (resp. (62)) is applied to derive (50) (resp. (64)).

Re: Thanks for the suggestion. We will expand the explanations of key steps in our proof (including these two and more) to improve the readability.

Cmt 15: Some notations are not well-defined in Algorithm 1. $K\leq T$ is not specified.

Re: Thanks for the suggestions. Yes, initializing $\\bar{w}\_1$ is necessary in the current Algorithm 1, and we assume that $K\\leq T$. We will explicitly specify this assumption when we introduce the problem setup.

We are glad to see that our responses successfully addressed the concerns and questions raised in the initial review, and we thank the reviewer again for carefully reading our submission (as well as the rebuttal) and providing valuable feedback. Please feel free to let us know if there are any other questions/comments.

Regarding the computational efficiency of the new update rule over the truncated simplex (i.e., the one proposed in [3]), we would like to clarify that it can still be solved efficiently (i.e., in polynomial time): since both the objective function and the domain (namely, the truncated simplex) are convex, the update is (still) a convex optimization problem, for which there are well-developed solvers.

What we meant in the initial response to Comment 3 is that, when the simplex is not truncated, there is an even more efficient way to perform the OMD update (which is to find the Lagrangian multiplier corresponding to the equality constraint via line search), which (to our understanding) is no longer applicable due to the additional constraints/multipliers introduced by the simplex truncation. We didn't mean that updating over the truncated simplex becomes "computationally inefficient" in the general sense.

We hope this addresses your concern.

Comment 1: The proposed algorithm requires prior knowledge of the parameters $u$ and $v$. This is a weakness when compared to algorithms that are adaptive to these parameters, e.g., by Huang et al.(2022) and Genalti et al. (2024).

Re: While there are $(u,v)$-adaptive algorithms proposed in [1, 2], they handle one single regime only (adversarial regime in [1] and stochastic regime [2]) and hence are not directly comparable to our BOBW result. Moreover, these adaptive algorithms require the truncated non-negative loss assumption.

The setup we consider in this work is the BOBW setting with the knowledge of $u$ and $v$. Under this setup, the only existing result is from [1], which is optimal in both regimes and requires the truncated non-negative loss assumption. Compared to that, we still achieve BOBW guarantee but try to get rid of the additional assumption.

Comment 2: There is a lack of mention or analysis of intermediate settings between stochastic and adversarial settings, e.g., corrupted environments. A number of best-of-both-worlds algorithms are also effective in these settings (e.g., (Lee et al., 2020), (Zimmert and Seldin, 2021), (Dann et al., 2023)).

Re: That is a good point. Online Learning-based algorithms naturally ensure regret guarantee in the corrupted regime through advanced and elegant analysis, and there is no existing result on achieving regret guarantee in the corrupted regime using the detect-switch framework. It is unclear whether/how the detect-switch framework can do that (by, e.g., explicitly detecting the degree of corruption $C\in[0, \Theta(T)]$). This is indeed an informative remark we may consider adding to future versions.

Comment 3: How tight is the bound of the proposed algorithm in terms of its dependence on $\log T$? Are there any known comparable lower bounds?

Re: There are two main sources of $\log T$ factors in our work, including 1) the log-barrier regularizer and 2) high-probability guarantees (from concentrations). For the latter one, we mean that the $\log T$ factor is inevitable for a high-probability guarantee, even considering the adversarial regime only, as shown in [3].

In terms of in-expectation regret, the worst-case lower bound in the adversarial regime is $\Omega(u K^{\frac{v}{1+v}} T^{\frac{1}{1+v}})$, and the gap-dependent lower bound in the stochastic regime is $\Omega(\sum_{i\neq i^*}\frac{\log T}{(\Delta_i)^{1/v}})$ as we mentioned in the paper.

In terms of high-probability regret, when heavy tails are involved, (to our knowledge) there is no regret lower bound showing the refined dependency on $\log T$.

References

[1] Huang, Jiatai, Yan Dai, and Longbo Huang. "Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits." international conference on machine learning. PMLR, 2022. https://proceedings.mlr.press/v162/huang22c.html

[2] Genalti, Gianmarco, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. "$(ε, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits." In The Thirty Seventh Annual Conference on Learning Theory, pp. 1882-1915. PMLR, 2024. https://proceedings.mlr.press/v247/genalti24a.html

[3] Gerchinovitz, Sébastien, and Tor Lattimore. "Refined lower bounds for adversarial bandits." Advances in Neural Information Processing Systems 29 (2016). https://proceedings.neurips.cc/paper_files/paper/2016/hash/2f37d10131f2a483a8dd005b3d14b0d9-Abstract.html

Comment 1: Is it possible to bound the expected regret of the proposed algorithm? What is the limitation?

Re: We believe that the reviewer is asking whether it is possible to bound the stronger regret $\mathbb{E}[\bar{R}_T]$ defined in line 147 in the adversarial regime. We now state the challenge of that in heavy-tailed bandits.

By definition, we would like to bound $\\mathbb{E}[\\bar{R}\_T] = \\mathbb{E}[ \\mathbb{E}[\\sum\_{t=1}^Y \\langle w\_t - y\_{i^*}, \\ell\_t \\rangle]|\\ell\_1,\\dots,\\ell\_T].$

Note that here $i^*:=\\text{argmin}\_i \\sum\_{i=1}^T \\ell\_{t,i}$, which depends on the realization of loss sequence. Looking at the inner expectation, the quantity $\sum_{t=1}^Y \langle w_t - y_{i^*}, \ell_t \rangle$ depends on not only the policy ($w_t$), but also the realization (the scale of losses). In other words, as long as the losses have large scale, the absolute quantity of regret is also large, even if the learning algorithm is good.

Therefore, one potential solution is to bound $\mathbb{E}[\bar{R}_T]$ hopefully thanks to the outer-level expectation (i.e., the realizations cannot be always very large due to the heavy tail definition). It is unclear to us whether this can be well bounded. Notably, this was also our intuition for why it is reasonable to consider pseudo-regret in heavy-tailed bandits: strong regret could be no longer meaningful as a performance metric.

Comment 2: As mentioned in Section 2, there are two possible definitions of regret in the adversarial setting. The author(s) should clarify which definition is used in the related works.

Re: Thanks for the suggestion. We will clarify this in future versions. Roughly speaking, in the heavy-tailed case, both [1] and us consider pseudo-regret (as we explained in our Remark 2), and in the bounded-loss case, the stronger regret is typically considered and can be handled.

Comment 3: A table comparing all results is appreciated.

Re: We thank the reviewer for the suggestion. We will consider adding a table to summarize the existing results for a clear comparison between our work and previous ones.

References

[1] Huang, Jiatai, Yan Dai, and Longbo Huang. "Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits." international conference on machine learning. PMLR, 2022. https://proceedings.mlr.press/v162/huang22c.html

Comment 1: Both the detect-switch method and FTRL with log barrier are known to be suboptimal in the standard BOBW MAB problem with bounded losses, which means that improving upon the existing results might require a completely different approach.

Re: We agree that both log-barrier (for adversarial bandits) and detect-switch method (for BOBW) do not achieve the optimal regret (i.e., suffering extra $\\log T$ factors) even with bounded losses, although to our knowledge, currently they are the only known approaches that are promising to handle heavy-tailed bandits in BOBW (and previous approaches need additional assumptions), and how to narrow the gap towards the optimal regret is still largely open, for which a totally different algorithm design seems to be necessary.

Comment 2: Do you think that the detect-switch framework is necessary to achieve these BOBW methods or whether some more straightforward method (like FTRL with 1/2 Tsallis-Inf for the standard BOBW MAB with bounded losses)?

Re: As we discussed in the last paragraph in the main body, it is largely unknown whether purely online algorithms (e.g., FTRL) alone can achieve BOBW regrets in heavy-tailed bandits. Even considering the adversarial regime only, log-barrier seems to be necessary, so one promising direction is to show that OMD/FTRL alone (without detect-switch framework) with log-barrier can achieve BOBW guarantee, although involved theoretical analysis is expected.