Thank you for your valuable review and constructive suggestions. Regarding the weaknesses and questions, we provide the following detailed responses:

Weakness: We must acknowledge our oversight: the second half of Lemma 4.1 was indeed incorrect. To address this issue, we have strengthened Lemma 4.2 by removing the assumption $\mu_i \leq \mu$, which eliminates the need for the monotonicity argument used in the original Lemma 4.1.

Lemma 4.2 (modified): For all $\mu\ge0$, $K\ge 1$, $N\ge 3$ and $M\ge 1$, let $\mu_i\in R$ for all $1\leq i\leq M$, and define $H_{N}=\int_0^{+\infty}(x+\mu)^{-N}e^{-\frac{K}{(x+\mu)^2}}\prod_{i=1}^M\left(1-F(x+\mu_i)\right) d x.$ For all $k\in\mathcal{N}^+$, we have $\frac{H_{N+k}}{H_N}\leq C_{N,k}\left(\left(\frac{M}{K}\right)^{k/3}\wedge \mu^{-k}\right),$ where $C_{N,k}$ is a positive constant only depending on $N$ and $k$. Furthermore, if $K\ge M$, then we have $\frac{H_{4}}{H_3}\leq C\left(\left(\frac{M}{K}\log\left(\frac{K}{M}+1\right)\right)^{1/2}\wedge \mu^{-1}\right),$ where $C$ is a positive constant.

Under the more general condition on $\mu_i$, the second part of Lemma 4.2 remains valid (when $K\ge M$), while the first part becomes weaker. As a result, the adversarial regret bound becomes slightly worse than before:

The additional factor $\frac{m^{5/6}}{d^{1/2}}$ is negligible when $d \gg m$.

In the stochastic setting, the logarithmic regret guarantee still holds, though the additive term becomes slightly larger:

$\mathcal{O}\left(\sum_{i,\Delta_i>0}\frac{\log(n)}{\Delta_i}\right)+\mathcal{O}\left(\frac{1}{\Delta}(m^2d\log(d)+m^{11/3}+md^2)\right)$

Therefore, our results still demonstrate that the FTPL algorithm approaches the BOBW guarantee.

We will include the complete proof of the new version of Lemma 4.2 at the end of our response. Since the derivation of the modified regret bound based on this lemma does not differ significantly from the corresponding parts in the original version of the paper, we do not provide the full derivation here. However, we are happy to include it in a follow-up response if necessary.

In addition, we have provided a new lower bound to demonstrate that the newly introduced $\frac{m^{5/6}}{d^{1/2}}$ term is also unavoidable. Please refer to our response to Reviewer 7BAU (Weakness 2) for further details.

Question: Regarding the work of Chen, Botao, and Junya Honda that you mentioned, please allow us to reiterate a few points:

1. Our work is still the first to show that FTPL approaches the BOBW guarantee. We would like to emphasize that our result in the stochastic setting should not be overlooked — it is not a straightforward extension (see Lemma 4.5 for details).

2. Although our result in the adversarial setting is slightly weaker, as an early work studying the BOBW problem for FTPL in the semi-bandit setting, we theoretically demonstrate the limitations of current techniques by providing a matching lower bound. This contribution helps clear the path for future progress.

3. Compared to Lemma 4.1, the proof of Lemma 4.2 plays a more critical role in our analysis. Our careful treatment of the ratio $H_{N+k}/H_N$ allows us to avoid relying on the monotonicity condition in the original Lemma 4.1.

Proof of modified Lemma 4.2: Let $u = \frac{1}{x + \mu}$. By the change of variable in the integral, we obtain

We now consider a random variable $U$ with probability density function $g(u)$ defined as

where $\Lambda$ is the normalization constant. With this, we have

Our plan is to find some $u_0 > 0$ such that $g(u)$ decays rapidly after $u_0$, then we expect that the order of $E[U^k]$ is roughly $u_0^k$. We first show the first result. The upper bound of $\mu^{-k}$ is obvious because $(x+\mu)^{-N-k}\leq \mu^{-k}(x+\mu)^{-N}$ and hence, in the following we assume that $\mu^{-1}\ge C_{N}'\left(\frac{M}{K}\right)^{1/3}$, where $C_{N}'=8\sqrt{N-2}$. Let $\ell(u)=\log g(u)$ and $y_i=\frac{1}{u}+\mu_i-\mu$ for all $1\leq i\leq M$, then when $u\ge 0$, $\frac{d \ell}{d u}(u)=\frac{N-2}{u}-2Ku+2\sum_{i=1}^M\frac{1_{\{y_i\ge 0\}}}{u^2y_i^3\left(e^{\frac{1}{y_i^2}}-1\right)}.$ Then we will show that when $u\ge u_0:=C_{N}'\left(\frac{M}{K}\right)^{1/3}/2$, $\frac{d \ell}{d u}(u)\leq -Ku/2$. Intuitively, this suggests that for $u \ge u_0$, $U$ exhibits a Gaussian tail. Then, by applying Lemma G.10 (which we include at the end), we can conclude that

To show that $\frac{d \ell}{d u}(u)\leq -Ku/2$, it suffices to note that $\sup_{x\ge0}\frac{1}{x^3\left(e^{\frac{1}{x^2}}-1\right)}<1$, then we have $\frac{d\ell}{du}(u)\leq\frac{N-2}{u}-2Ku+\frac{2M}{u^2}.$ When $u\ge u_0$, clearly, since $C_N$ is large enough, we have $\frac{2M}{u^2}\leq \frac{Ku}{2}.$ Also, since $u_0>\sqrt{\frac{N-2}{K}}$, when $u\ge u_0$, we have $\frac{N-2}{u}\leq Ku.$ Therefore, when $u\ge u_0$, $\frac{d\ell}{du}(u)\leq -Ku/2.$ For the second part ($N=3$ and $k=1$), let $u_0=\left(\frac{M}{K}\log\left(\frac{K}{M}+1\right)\right)^{1/2}.$ When $K\leq 32M$, by the first part, the result holds clearly when $C$ is large enough. Hence we then assume that $K>32M$. Then $u_0<1/3$. Similarly, in the following, we also assume that $\mu^{-1}\ge C'u_0$, where $C'>3$ is a large constant to be chosen and is not depending on $K$ and $M$. For all $s\ge t\ge 1$, we have $\frac{g(su_0)}{g(tu_0)}=\frac{s}{t}\mathrm{e}^{-Ku_0^2(s^2-t^2)}\prod_{i=1}^M\frac{1-F\left(\frac{1}{su_0}+\mu_i-\mu\right)}{1-F\left(\frac{1}{tu_0}+\mu_i-\mu\right)}.$ If $1\leq t\leq 3$, then $tu_0<1$. Hence, by Lemma G.7 (which we include at the end), we have$$ \frac{g(su_0)}{g(tu_0)}\leq \frac{s}{t}\mathrm{e}^{-Ku_0^2(s^2-t^2)}\left(\frac{8}{t^2u_0^2}\right)^M\leq s\mathrm{e}^{-Ku_0^2(s^2-t^2)}\left(\frac{8}{u_0^2}\right)^M

\frac{d\log f}{dx}(x) \leq -x/\sigma^2, \quad \forall \mu'\ge x \ge \mu,

E[X^k 1_{{\mu'\ge X \ge \mu}}]\leq 2k!!\cdot\mu^k.

Thank you for your valuable review and constructive suggestions. Regarding the weaknesses and questions, we provide the following detailed responses:

Weakness 1: Though the uniqueness of the optimal action is a common assumption in BOBW problems [Zimmert and Seldin, 2019, Zimmert et al., 2019, Honda et al., 2023], we would like to emphasize that this is primarily for technical convenience (see our response to Question 3 for further discussion). Intuitively, the case where the optimal action is not unique is actually easier for the learner. In the MAB setting, some classical BOBW algorithms based on FTRL have already been shown to achieve logarithmic regret even without the uniqueness assumption, though such results require more delicate analysis (e.g., Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds, Shinji Ito; Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms, Tiancheng Jin, Junyan Liu, and Haipeng Luo).

Our additional experiments (We're sorry, but due to the new NeurIPS policy, we are temporarily unable to upload images.) show that even when the optimal action is not unique, FTPL still achieves logarithmic regret in the stochastic setting. This supports our conjecture that the assumption is not essential. We view this as a promising direction for future work and will include a discussion in the revised version. Thank you for bringing this up.

Weakness 2: We acknowledge that our work does not introduce algorithmic innovations. Our main contribution lies in the theoretical analysis of the FTPL algorithm in the semi-bandit setting, which is technically challenging. Specifically:

1. Our analysis of the ratio $\frac{V_{i,4}}{V_{i,3}}$—where both the numerator and denominator involve complex integrals and summations—is nontrivial. By carefully analyzing the ratio of corresponding terms in the numerator and denominator (including both upper and lower bounds), we obtain a nontrivial result for the first time, and further demonstrate the theoretical limitations of this approach.

2. We would also like to emphasize that our result in the stochastic setting should not be overlooked — it is not a straightforward extension (see Lemma 4.5 for details).

Weakness 3: We demonstrate that this is difficult to avoid within our proof framework by establishing a lower bound. Any further improvement would likely require adopting a different and more challenging line of analysis.

Weakness 4: We believe it is likely that, without modifying the algorithm, FTPL with a Fréchet distribution of shape parameter 2 cannot achieve the optimal performance in the adversarial setting when $m \ge d/2$, and therefore fails to attain the BOBW guarantee. Please refer to our response to Question 2 for details.

Question 1: We provide a detailed explanation of this issue. According to our analysis in Section 4.1, the stability term in round $t$ can be bounded by

The main challenge lies in the fact that $V_{i,N}(\lambda) = \sum_{I,\ |I|<m,\ i \notin I} V_{i,N}^{I}(\lambda)$ is a sum over a collection of complicated integrals, which makes it difficult to directly compute $\frac{V_{i,4}(\lambda)}{V_{i,3}(\lambda)}$. A natural idea is to use the upper bound:

However, our lower bound shows that when $\sigma_i(\hat{L}_t) > 2m$, we have

This implies that, under this approach, the upper bound of the stability term is at least

Question 2: According to the result of "Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously" by Julian Zimmert, Haipeng Luo, and Chen-Yu Wei (Theorem 3), when $m > d/2$, the optimal regret bound in the adversarial setting is

However, if we choose the Fréchet distribution with shape parameter 2 as the perturbation distribution, the resulting penalty term remains

regardless of the relationship between $m$ and $d$. This stems from a simple fact: consider $X_1, \ldots, X_d$ as i.i.d. random variables drawn from the Fréchet distribution with shape parameter 2. Then, the expectation of the sum of the top $m$ among $X_1, \ldots, X_d$ scales as $\sqrt{dm}$.

However, this is too large when compared to $(d - m)\sqrt{\log\left(\frac{d}{d - m} \right)}$ in the optimal bound in the case where $m > d/2$ (when $m=d-1$, for example). Therefore, we believe that, without modifying the algorithm, FTPL with a Fréchet distribution (shape parameter 2) is unlikely to achieve the optimal regret in the adversarial setting when $m \ge d/2$.

It is important to emphasize that the algorithm in "Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously" that achieves the BOBW guarantee even when $m > d/2$ is based on FTRL with a hybrid regularizer. The hybrid regularizer used there is relatively complex and thus can adapt to various values of $m$ and $d$. To modify FTPL to handle more general cases, it may similarly require more sophisticated perturbation distributions.

Question 3: The difficulty of the case where the optimal action is not unique lies in the following aspects:

1. The lower bound used in the self-bounding constraint technique,

no longer holds. This is because, in this case, the $m$-th and $(m+1)$-th arms may have the same expected loss, and both can potentially appear in some optimal action sets. As a result, selecting the $(m+1)$-th arm does not necessarily incur at least $\Delta$ regret. Therefore, a more refined characterization of the lower bound is required, which becomes significantly more cumbersome.

2. Once a new lower bound is obtained, we must correspondingly strengthen Lemma 4.5 to match the upper and lower bounds. This requires more sophisticated analytical techniques from FTRL algorithms (see "Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds", Shinji Ito; and "Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms", Tiancheng Jin, Junyan Liu, and Haipeng Luo).

Thank you for your valuable review and constructive suggestions. Regarding the weaknesses and questions, we provide the following detailed responses:

Weakness 1: We must acknowledge our oversight: the second half of Lemma 4.1 was indeed incorrect. To address this issue, we have strengthened Lemma 4.2 by removing the assumption $\mu_i \leq \mu$, which eliminates the need for the monotonicity argument used in the original Lemma 4.1.

Lemma 4.2 (modified): For all $\mu\ge0$, $K\ge 1$, $N\ge 3$ and $M\ge 1$, let $\mu_i\in R$ for all $1\leq i\leq M$, and define $H_{N}=\int_0^{+\infty} (x+\mu)^{-N}e^{-\frac{K}{(x+\mu)^2}}\prod_{i=1}^M\left(1-F(x+\mu_i)\right) d x.$ For all $k\in\mathcal{N}^+$, we have $\frac{H_{N+k}}{H_N}\leq C_{N,k}\left(\left(\frac{M}{K}\right)^{k/3}\wedge \mu^{-k}\right),$ where $C_{N,k}$ is a positive constant only depending on $N$ and $k$. Furthermore, if $K\ge M$, then we have $\frac{H_{4}}{H_3}\leq C\left(\left(\frac{M}{K}\log\left(\frac{K}{M}+1\right)\right)^{1/2}\wedge \mu^{-1}\right),$ where $C$ is a positive constant.

Under the more general condition on $\mu_i$, the second part of Lemma 4.2 remains valid (when $K\ge M$), while the first part becomes weaker. As a result, the adversarial regret bound becomes slightly worse than before:

The additional factor $\frac{m^{5/6}}{d^{1/2}}$ is negligible when $d \gg m$.

In the stochastic setting, the logarithmic regret guarantee still holds, though the additive term becomes slightly larger:

$\mathcal{O}\left(\sum_{i,\Delta_i>0}\frac{\log(n)}{\Delta_i}\right)+\mathcal{O}\left(\frac{1}{\Delta}(m^2d\log(d)+m^{11/3}+md^2)\right)$

Therefore, our results still demonstrate that the FTPL algorithm approaches the BOBW guarantee.

Sorry for the inconvenience. Due to space limitations, we leave the proof of the revised Lemma 4.2 in our response to Reviewer 1er3.

Since the derivation of the modified regret bound based on this lemma does not differ significantly from the corresponding parts in the original version of the paper, we do not provide the full derivation here. However, we are happy to include it in a follow-up response if necessary.

Weakness 2: We appreciate your interest in the lower bound part of our Lemma C.5. We acknowledge that the current proof of the lower bound may be difficult to follow.

An intuitive understanding of this result is that the pdf of $W$, given by $1 - F(x(w) + \mu)$, is monotonically decreasing on $[0,1]$ and clearly exhibits a sharp drop at $e^{-\frac{K}{\mu^2}}$: the pdf is equal to $1$ before this point and then gradually decays afterward. Our calculation shows that most of the density is concentrated in the first half of the interval, and thus the expectation of $(-\log(W))^{1/2}$ is of a larger order than simply substituting $W = e^{-\frac{K}{\mu^2}}$. Thus, by choosing $\mu = -\sqrt{\frac{2K}{\log(K)}}$, the desired lower bound follows.

Besides, we would like to emphasize that, due to the appearance of the $\frac{m^{5/6}}{d^{1/2}}$ factor in our new results, we have established a corresponding updated lower bound. This shows that the new Lemma 4.2 is tight, and therefore, the extra factors beyond the optimal rate in the adversarial setting are unavoidable under our approach. To achieve the tightest possible rate, one would have to resort to alternative methods.

Lemma C.7: For all $\mu\in R$, $M, K\ge 1$, and $N\ge 3$, define $R_{N}(\mu)=\int_0^{+\infty} x^{-N}e^{-\frac{K}{x^2}}\left(1-F(x+\mu)\right)^M dx.$ Then there exists $C>0$ such that for all $M\ge 2K$, we have $\sup_{\mu\in R}\frac{R_{4}(\mu)}{R_3(\mu)}\ge C\left(\frac{M}{K}\right)^{1/3}.$

This new lower bound is originated from the following simple observation: if a random variable $X$ supported on $[0,1]$ has a probability density function $f$, and there exists $x_0 \in (0,1]$ such that $f$ is non-decreasing on $[0,x_0]$, then it holds that $E[X] \geq x_0/4$. This follows from the fact that $P(0 \leq X \leq x_0/2) \leq P(x_0/2 \leq X \leq x_0)$, so $P(0 \leq X \leq x_0/2) \leq 1/2$, which implies $E[X] \geq x_0/4$.

Proof for Lemma C.7: Let $u = \frac{1}{x}$. By the change of variable in the integral, we obtain

We now consider a random variable $U$ with probability density function $g(u)$ defined as

where $\Lambda$ is the normalization constant. With this, we have

Let $\ell(u)=\log g(u)$, then our plan is to show that that exists $\mu\in R$ and corresponding $C>0$ such that when $0\leq u\leq u_0:=C\left(\frac{M}{K}\right)^{1/3}$, $\frac{d \ell}{d u}(u)\ge 0$. To this end, let $\mu=1>0$ and $y=\frac{1}{u}+1$, then$\frac{d\ell}{du}(u)=\frac{1}{u}-2Ku+\frac{2M}{u^2y^3\left(e^{\frac{1}{y^2}}-1\right)}=\frac{1}{u}+2Ku\left( \frac{M/K}{u^3y^3\left(e^{\frac{1}{y^2}}-1\right)}-1 \right).$ Since $1\leq y$, when $u\leq \left(\frac{M}{K}\right)^{\frac13}(e-1)^{-\frac13}-1$, we have $\frac{M/K}{u^3y^3\left(e^{\frac{1}{y^2}}-1\right)}=\frac{M/K}{(u+1)^3\left(e^{\frac{1}{y^2}}-1\right)}\ge\frac{M/K}{(u+1)^3\left(e-1\right)}\ge 1.$ Take $C=(e-1)^{-\frac13}-2^{-\frac13}>0$ and then one can see that when $M\ge 2K$, $u_0:=C\left(\frac{M}{K}\right)^{1/3}\leq \left(\frac{M}{K}\right)^{\frac13}(e-1)^{-\frac13}-1$. Then when $0\leq u\leq u_0:=C\left(\frac{M}{K}\right)^{1/3}$, $\frac{d\ell}{du}(u)\ge 0$.

Question: We appreciate your suggestion and will include this clarification. This choice is motivated by a sequence of prior studies on the FTPL algorithm in the multi-armed bandit (MAB) setting.

Briefly, according to the decomposition in our Lemma 3.3, consider $X_1, \ldots, X_d$ as i.i.d. random variables drawn from the perturbation distribution $\mathcal{D}$. With a properly chosen learning rate, the penalty term corresponds to the expected sum of the top $m$ values among $\sqrt{n} X_1, \ldots, \sqrt{n} X_d$.

Noting that the optimal regret bound in the adversarial setting is $\sqrt{nmd}$, the intuition is that we want to choose a distribution $\mathcal{D}$ such that the expectation of the sum of the top $m$ among $X_1, \ldots, X_d$ scales as $\sqrt{dm}$. According to our Lemma E.2, the Fréchet distribution with shape parameter $2$ satisfies this condition exactly. As for how we discovered that the Fréchet distribution satisfies such a condition, one can refer to classic results from extreme value theory.

We thank you for your review and suggestions. Regarding the question about Lemma 3.3, we provide the following clarifications.

First, our result is stronger in the sense that, compared to previous work by Honda and Lee et al., we obtain an almost identical penalty term, but with a simpler stability term. Specifically, their stability term takes the form

which they further decompose into two parts:

and control each part separately. However, under our decomposition, the second term is not needed, simplifying the analysis.

Second, we believe this stronger result indeed stems from adopting an FTRL-for-FTPL-style analytical framework. The Bregman-divergence-based argument is more principled, allowing us to apply the Generalized Pythagoras Identity (Lemma G.2). In contrast, the decomposition in Honda and Lee’s work is more ad hoc, and directly based on the update form

We conjecture there are two main reasons why they did not use the FTRL-for-FTPL framework:
(1) The regularization function corresponding to FTPL's dual view does not have a closed-form expression, making it hard to analyze;
(2) Their decomposition is based on the update rule of $A_t$ (i.e., the maximizer of an inner product), which naturally leads to a decomposition where the stability term also takes the form of an inner product. This inner-product form is more convenient for analysis in the context of FTPL algorithms.

As mentioned in Remark 3.1, unlike standard FTRL analyses where the stability term is often approximated by a sum of the form $\eta\_t E[\|\hat{\ell}\_t\|^2\_{\nabla^2 \Phi(-\eta\_t \hat{L}\_t)}]$, this approach does not extend easily to FTPL. This is because $\nabla^2 \Phi(-\eta\_t \hat{L}\_t)$ and $\nabla^2 \Phi(-\eta\_t \hat{L}\_{t+1})$ may differ significantly (we can only control their diagonal entries) — in FTPL, $\nabla^2 \Phi$ is not a diagonal matrix, which is a key difference from typical FTRL algorithms.

In contrast, the inner-product form of the stability term $\langle \hat{\ell}\_t, \phi(\eta\_t \hat{L}\_t) - \phi(\eta\_t \hat{L}\_{t+1}) \rangle$ can be written as

which, according to Lemma D.2, can be upper bounded by

In this way, we only need to consider the diagonal entries of $\nabla^2 \Phi$.

However, in any case, we find that a similar and even stronger form of the stability term can also be easily derived using the FTRL-based analysis framework, which further demonstrates the superiority of this framework.