AT Preliminaries

We now present some technical results that will be repeatedly used in the rest of the paper. A direct corollary of the Chernoff-Hoeffding bound (see, e.g. We also use the following variation of Chernoff bound for sampling without replacement. We provide the lower bound proofs for the results in Section 4. We remark that these lower bounds In particular, lower bounds for offline multi-armed bandits are often information-theoretic and does not depend on adversarial instances. By Y ao's minimax principle, it suffices to prove the lower bound for deterministic algorithms over (n 1) ( n 1) ( n 1) We remark that even with the random arrival of arms, the sample lower bound in Theorem 1 still holds.