Robust Near-Optimal Arm Identification With Strongly-Adaptive Adversaries

In this work, we study the best arm identification problem in the adversarial multi-armed bandits framework. We define a strongly-adaptive adversarial model in this framework, based on strongly-adaptive adversaries in security and distributed systems. On the negative side, we show the increased strength of the adversarial model by proving that it is impossible for any best-arm identification algorithm to return an arm with rank $\boldsymbol{\leq}\left\lfloor\frac{\boldsymbol{\epsilon}\boldsymbol{K}}{ \mathbf{1}\boldsymbol{+}\boldsymbol{\epsilon}_{\mathbf{0}}}\right\rfloor$, where $K$ is the number of arms, $\epsilon$ is the adversary's budget and $\epsilon_{0}$ is the breaking point of the robust mean estimation subroutine. On the positive side, we construct a novel sequential elimination algorithm which returns a near-optimal arm (with rank $\boldsymbol{\leq}\left\lceil(\mathbf{1}\boldsymbol{+}\boldsymbol{\lambda}) \left\lfloor\frac{\boldsymbol{\epsilon}\boldsymbol{K}}{\boldsymbol{\epsilon}_{ \mathbf{0}}}\right\rfloor\right\rceil$ where $\boldsymbol{\lambda}\boldsymbol{>}\mathbf{0}$ is a function of $\epsilon$ and $\epsilon_{0}$ and tends to 0 for small $\epsilon$) with high probability. We evaluate our algorithm on both synthetic and real-world datasets and empirically demonstrate that our algorithm returns a near-optimal arm under a strongly-adaptive adversarial model.
Source: IEEE Transactions on Signal Processing - Category: Biomedical Engineering Source Type: research