A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond

Thank you for your time and helpful suggestions. We address the reviewer’s concerns as follows.

The main concern is the novelty of the algorithm since it is based on BARBAR.

Though our method is based on BARBAR, we want to emphsize the novelty of our BARBAT algorithm. Unlike BARBAR, which sets the epoch length to $N_m = \sum_{k} n_k^m$, our BARBAT algorithm defines the epoch length as $N_m \approx O(K 2^{2(m-1)})$, making it unaffected by the adversary. However, this change introduces challenges in algorithm design and regret analysis since we have $N_m > \sum_{k} n_k^m$ and require addtional pulling of arms. To address this issue, we increase the probability of selecting the estimated best arm $k_m$. However, pulling the estimated optimal arm $k_m$ too many times may lead to additional regret, as $k_m$ could be suboptimal. To mitigate this potential regret, we adopt epoch-varying failure probabilities $\delta_m \approx O(1/(mK2^{2m}))$ and demonstrate that such additional regret will only manifest in the first $O(\log(1/\Delta))$ epochs, thus remaining bounded by a term independent of $T$. Overall, the additional pulls of the estimated best arm in our algorithm, along with the corresponding regret analysis, is novel and nontrivial. By utilizing these techniques, our algorithms achieve better regret bounds than that of BARBAR.

You provided a lower bound in section 4.2 but how about other settings? Is it possible to provide a lower bound for other settings?

Thank you for the valuable suggestions. The following table shows the lower bounds of all extensions. The lower bound for multi-armed bandits comes from Gupta et al. (2019), and their results can be directly extended to d-semi bandits, multi-agent bandits, and strongly observable graph bandits by incorporating the lower bounds for stochastic settings (without corruption). However, the lower bound for batch bandits cannot be directly derived from the results of Gupta et al. (2019), so we provide a proof in our paper. We will include all lower bounds in the revision.

From Table 1, the results seem to be a little outperforming previous work. For example, for $d$-set semmi-bandits, your result is worse than others on the order of $\log(T)$. Please discuss it.

• The optimal regret bound for semi-bandits is achieved using the FTRL framework (Tsuchiya et al., 2023). In Section 7 of their paper, Tsuchiya et al. note that one limitation of their algorithm is its computational complexity, as the sampling probabilities cannot be efficiently computed. In contrast, our approach is computationally efficient, although the regret is slightly worse than state-of-the-art results.

• For the multi-agent setting, our regret improvement is also non-incremental. Notice that the regret bound of DRAA is $O(C/V + K\log^2(T)/(V\Delta))$ while the regret bound of BARBAT is $O(C/V + (1/V)\sum_{\Delta_k>0}\log^2(T)/\Delta_k)$. When the minimal gap $\Delta$ is significantly smaller than other suboptimal gaps $\Delta_k\neq \Delta$, our bound may substantially improves upon DRAA. For instance, consider the senario where mean rewards is $1, 1-\Delta,0,\dots,0$. Then DRAA incurs regret $C/V+K\log^2(T)/(V\Delta)$, while our regret is only $C/V+(1/V)(1/\Delta + K)\log^2(T)$. In particular, when $\Delta \leq 1/K$, the corruporion-independent term in the regret bound of DRAA is effectively $K$ times that of BARBAT.

• For the batched bandits, our work is the first to study batched bandits with adversarial corruptions and achieve near-optimal regret bounds.

You mentioned the different definition of regret: $R(T)$ and $\tilde R(T)$. In the whole paper, you work on $R(T)$, not $\tilde R(T)$. Please discuss the motivation for choosing the definition.

$R(T) = T\mu_{k^*} - \mathbf{E}[\sum_{t=1}^T \mu_{k_t}]$ is a standard regret defnition in stochastic bandits, while the regret definition $\tilde R(T) = \max_{k \in [K]}\mathbf{E}[\sum_{t=1}^T \tilde r_{t,k} - \sum_{t=1}^T \tilde r_{t,I_t}]$ is typically used in adversarial bandits, where $\tilde r_{k}$ represents the corrupted rewards. We think that comparing against the true means, rather than the corrupted rewards, is more natural. Also, $R(T)$ has been employed in all previous works on adversarial corruptions.

References:

• Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562–1578. PMLR, 2019.
• Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pages 8117–8144. PMLR, 2023.

Thank you for the reply. We are glad that our response has helped you better understand our paper. We will incorporate your suggestions into the revision.

Thanks for your detailed review of our work. Here are our response to your comments.

The proposed BARBAT algorithm appears structurally similar to BARBAR, with the main change being in the change of epoch lengths. If achieving the improved regret bounds requires nontrivial technical innovations beyond modifying this aspect, I encourage the authors to highlight and clarify them.

Unlike BARBAR, which sets the epoch length to $N_m = \sum_{k} n_k^m$, our BARBAT algorithm defines the epoch length as $N_m \approx O(K 2^{2(m-1)})$, making it unaffected by the adversary. However, this change introduces challenges in algorithm design and regret analysis since we have $N_m > \sum_{k} n_k^m$ and require addtional pulling of arms. To address this issue, we increase the probability of selecting the estimated best arm $k_m$. However, pulling the estimated optimal arm $k_m$ too many times may lead to additional regret, as $k_m$ could be suboptimal. To mitigate this potential regret, we adopt epoch-varying failure probabilities $\delta_m \approx O(1/(mK2^{2m}))$ and demonstrate that such additional regret will only manifest in the first $O(\log(1/\Delta))$ epochs, thus remaining bounded by a term independent of $T$. Overall, the additional pulls of the estimated best arm in our algorithm, along with the corresponding regret analysis, represent a novel and nontrivial contribution.

One of the primary advantages claimed is BARBAT's scalability and parallelizability, which are indeed important. However, these properties are common to many elimination-based methods, and it is unclear whether they stem from novel design choices in BARBAT. If direct generalization is not sufficient for the multiple settings considered, it would be helpful for the authors to elaborate on the challenges involved and the innovations introduced.

Direct generalization of existing approaches is not sufficient for the extensions. Our algorithmic adjustments for each extension are thoughtfully designed to address the specific challenges while maintaining the core advantages of the framework:

• In strongly observable graph bandits, the main challenge is how to leverage the graph-structured feed-back to reduce the regret suffered from exploration. We introduce the novel OODS algorithm (in Appendix A) for action-probability allocation. Specifically, we iteratively compute a minimum dominating set on the communication graph $G$, assigning pulling probabilities accordingly. Once an arm accumulates sufficient observations, we remove it from the graph and recalculate the dominating set. This process repeats until the graph is empty.
• In batched bandits, the main challenge here is that the agent can only observe rewards after each batch is completed (instead of after each pull) and the number of batches is limited. To address this, we introduce a batch-related parameter $a = \max\\{T^{\frac{1}{2(\mathcal{M} + 1)}}, 2\\}$, where $\mathcal{M}$ is the number of batches. This parameter $a$ is used to design the exploration parameter $\lambda_m$, the epoch length $N_m$, and the estimated gap $\Delta_k^m$ in our algorithm for batched bandits.
• In the $d$-set semi-bandit setting, the primary challenge lies in identifying an optimal action composed of $d$ arms, rather than merely a single optimal arm. To address this, we introduce a novel approach: when computing the epoch threshold $r_*^m$, we specifically consider the $d$-th largest empirical reward among arms. This innovation intuitively captures that each arm within the optimal action set can be regarded as an "optimal arm," ensuring effective identification of the optimal $d$-arm combination.
• For the multi-agent setting, we agree that many elimination-based methods also have parallelizability, but our method achieves state-of-the-art regret bounds.

Thanks for your detailed review of our work. Here are our response to your comments.

The main issue is that the regret bound is not tight in $T$. For example, if the algorithm incurs $\log(T)^2$ regret in the stochastic bandit setting, one could instead use Shannon-FTRL, which also achieves $\log(T)^2$ regret and is computationally efficient.

We acknowledge that $\log(T)^2$ regret is not tight, and we believe that finding a way to achieve optimal regret for adversarial corruptions using elimination-based methods is an interesting open problem. We think our work has made significant strides toward addressing this issue.

Though Shannon-FTRL also achieves $\log(T)^2$ regret and is computationally efficient in the stochastic MAB setting, our method outperforms Shannon-FTRL in many extended scenarios. In the strong observation graph bandit setting, Shannon-FTRL achieves only $\log(T)^3$ regret, which is worse than the regret bound attained by our method. In the $d$-sets bandit problem, to the best of our knowledge, there is no computationally efficient FTRL-type robust algorithm. As pointed by Tsuchiya et al. (2023), the computational cost is the main limitation of FTRL framework, especially when the optimization problem does not have a closed form. Additionally, for the batched bandit setting, our work provides the first algorithm that is robust to adversarial corruption.

In the abstract, the authors use $K$ and $C$ without definition. Although the meaning can be inferred, it may be confusing.

Thank you for the comment. We will include the definitions of $K$ and $C$ in the abstract.

References:

• Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs. NeurIPS, 2022.
• Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits. In ICML, 2023.

Thank you for taking the time to review our paper. We hope that our response below addresses your concerns.

The core BARBAT algorithm is closely related to DRAA [2], with the primary distinction being the use of epoch-varying failure probabilities. While this yields slightly improved regret bounds, this improvement is quite incremental.

We do not agree that our regret improvement is quite incremental. Notice that in the MAB setting, the regret bound of DRAA is $O(C + K\log^2(T)/\Delta)$ while the regret bound of BARBAT is $O(C + \sum_{\Delta_k>0}\log^2(T)/\Delta_k)$. When the minimal gap $\Delta$ is significantly smaller than other suboptimal gaps $\Delta_k\neq \Delta$, our bound may substantially improves upon DRAA. For instance, consider the senario where mean rewards is $1, 1-\Delta,0,\dots,0$. Then DRAA incurs regret $C+K\log^2(T)/\Delta$, while our regret is only $C+(1/\Delta + K)\log^2(T)$. In particular, when $\Delta \leq 1/K$, the corruption-independent term in the regret bound of DRAA is effectively $K$ times that of BARBAT.

The multi-agent setting assumes instantaneous, reliable, and cost-free broadcasts. This assumption, while common in theory, limits the practical relevance of the results, especially since the authors claim their method to be highly parallelizable. There is no discussion of asynchronous or faulty communication scenarios, which are common in real-world systems. Could the framework be extended to handle asynchronous message passing?

We believe it is possible to extend our framework to an asynchronous setting, though it may encounter some challenges. Here is a rough outline of our approach: each agent independently executes the single-agent BARBAT algorithm, while incorporating an early-stopping mechanism. Specifically, an agent will enter the next epoch as soon as it has observed sufficient reward samples—either through its own pulls or those received from other agents—to reliably estimate the reward gaps. A key challenge in this approach is determining the optimal timing for broadcasting the agents' local information. Broadcasting too early may result in insufficient data collection, necessitating additional rounds of communication. Conversely, delaying broadcasts might lead to redundant pulls, preventing the agents from fully leveraging the benefits of collaboration.

While a lower bound is provided for batched bandits, no new lower bounds are given for other extensions (e.g., multi-agent or semi-bandits), making it unclear how tight the regret is in these settings. Is it possible to derive lower bounds for these setting?

Thank you for the valuable suggestions. The following table shows the lower bounds of all extensions. The lower bound for multi-armed bandits comes from Gupta et al. (2019), and their results can be directly extended to d-semi bandits, multi-agent bandits, and strongly observable graph bandits by incorporating the lower bounds for stochastic settings (without corruption). However, the lower bound for batch bandits cannot be directly derived from the results of Gupta et al. (2019), so we provide a proof in our paper. We will include all lower bounds in the revision.

References:

• Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562–1578. PMLR, 2019.