An Optimal Algorithm for Adversarial Bandit Problem with Multiple Plays

In this paper, we study the adversarial bandit problem with multiple plays. We introduce a highly efficient multiple-play bandit algorithm that achieves the minimax optimal performance with high probability. As our performance guarantee holds with high probability, our algorithm provides more robust performance compared to the state-of-the-art. Moreover, since we do not have any statistical assumptions on the bandit arms, the results in the paper are guaranteed to hold in an individual sequence manner. Hence, our algorithm can be used for a wide range of combinatorial applications that require exploration and exploitation at the same time.