Adversarial Multi-armed Bandit

In this chapter, we consider the adversarial MAB problem, a variant of the MAB problems whereby the stochastic assumption about the processes of rewards is removed. We first introduce the problem and define new notations of regret. We then describe a few well-known algorithms for this problem and provide the asymptotic performance results for these strategies. Finally, we generalize the adversarial MAB problem to the multiplayer case and connect it with the repeated game theory, and show that equilibrium can be achieved with certain strategies.