  Consider a queueing system consisting of multiple servers. Jobs arrive over
time and enter a queue for service; the goal is to minimize the size of this
queue. At each opportunity for service, at most one server can be chosen, and
at most one job can be served. Service is successful with a probability (the
service probability) that is a priori unknown for each server. An algorithm
that knows the service probabilities (the "genie") can always choose the server
of highest service probability. We study algorithms that learn the unknown
service probabilities. Our goal is to minimize queue-regret: the (expected)
difference between the queue-lengths obtained by the algorithm, and those
obtained by the "genie."
  Since queue-regret cannot be larger than classical regret, results for the
standard multi-armed bandit problem give algorithms for which queue-regret
increases no more than logarithmically in time. Our paper shows surprisingly
more complex behavior. In particular, as long as the bandit algorithm's queues
have relatively long regenerative cycles, queue-regret is similar to cumulative
regret, and scales (essentially) logarithmically. However, we show that this
"early stage" of the queueing bandit eventually gives way to a "late stage",
where the optimal queue-regret scaling is $O(1/t)$. We demonstrate an algorithm
that (order-wise) achieves this asymptotic queue-regret in the late stage. Our
results are developed in a more general model that allows for multiple job
classes as well.
