The Nonstochastic Multiarmed Bandit Problem

TLDR

The multi‑armed bandit problem asks a gambler to choose among K nonidentical slot machines to maximize reward, balancing exploration and exploitation; it has attracted attention for illustrating this trade‑off, but past solutions rely on statistical assumptions about machine payoffs. The authors aim to solve the bandit problem without statistical assumptions, treating payoffs as adversarially controlled. They propose an algorithm that, in an adversarial setting, achieves near‑optimal per‑round payoff and extends the analysis to unknown repeated matrix games. The algorithm achieves an optimal O(T⁻¹ᐟ²) regret against the best arm, matches lower bounds, extends to any strategy pool with O((log N)¹ᐟ² T⁻¹ᐟ²) convergence, and attains the minimax payoff in unknown repeated matrix games at the same rate.

Abstract

In the multiarmed bandit problem, a gambler must decide which arm of K nonidentical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to find the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of T plays, we prove that the per-round payoff of our algorithm approaches that of the best arm at the rate O(T-1/2 ). We show by a matching lower bound that this is the best possible. We also prove that our algorithm approaches the per-round payoff of any set of strategies at a similar rate: if the best strategy is chosen from a pool of N strategies, then our algorithm approaches the per-round payoff of the strategy at the rate O((log N1/2T-1/2 ). Finally, we apply our results to the problem of playing an unknown repeated matrix game. We show that our algorithm approaches the minimax payoff of the unknown game at the rate O(T-1/2 ).