Regret of Queueing Bandits
We consider a variant of the multiarmed bandit problem where jobs queue for service, and service rates of different servers may be unknown. We study algorithms that minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by a "genie"-aided matching algorithm that knows exact service rates. A naive view of this problem would suggest that queue-regret should grow logarithmically: since queue-regret cannot be larger than classical regret, results for the standard MAB problem give algorithms that ensure queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, the naive intuition is correct as long as the bandit algorithm's queues have relatively long regenerative cycles: in this case 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, and also exhibits close to optimal switching time from the early stage to the late stage.
The paper considers a variant of the multi-armed bandit problem in which it may take several slots to obtain a reward, and so arriving jobs accummulate in queues. Such problems have been heavily studied in the "queueing theory" field, where long-term performance is analyzed assuming that all the parameters are known. In this paper the authors assume that the "service rate" (i.e. the time it on average takes to obtain the reward) is unknown and needs to be learnt. The paper defines a queue-regret and analyzes its behavior. It establishes an asymptotic lower bound and designs an algorithm that achieves this bound up to a poly log factor. The analysis is non-trivial, as there are two phases: the queues first possibly build up until sufficient learning took place to stabilize them.
While the analytical results are impressive, the paper is not easy to read and confuses the reader. The appendix includes theorems and proofs for a multi-queue setting, while the main body is devoted to a single-queue setting. The introduction and abstract mix both and do not convey properly what the paper is about. Below are my concerns and some suggestions.  1. There is a lot of confusion w.r.t. queueing terminology and setting. I applaud the authors to step outside of their comfort zone, but the paper would hugely benefit from getting more familiar with queueing theory. It is essential to properly explain in the introduction the queueing problem you consider, e.g. do you consider a discrete or continuous time, how many servers you consider, are these pre-emptive, do they serve in parallel, how many queues are there, are the jobs routed immediately after their arrival (to a queue) or when a server becomes idle (to a server), are all the arriving jobs of the same class? In fact, there are a lot of queueing settings, and your single-queue model I believe best fits the problem "routing to parallel servers", which you however not even mention. You consideration of multiple queues is often described as "multi-class" (there are multiple classes of jobs that arrive, each class has a particular set of parameters - in your case \lambda's and \mu's). Other problems, e.g. scheduling, are related but fundamentally different. This will help your paper to have a larger impact as bridging the gap between machine learning and queueing theory.  2. Although catchy, your title is not specific enough. It is not clear what "queueing" means - as there are many queueing settings one could consider. It is not clear what "bandits" means - bandit feedback, bandit algorithm (which?), bandit model (which?).  3. There has been recent research on formulating queueing systems using bandit models. These are of at least 3 kinds: (1) job scheduling problems (see Gittins book 1989, and several papers by Ayesta and his co-authors since 2009), where each server selects which job to serve; (2) congestion control problems (e.g. Jacko & Sanso 2012 and Avrachenkov et al 2013), where users sending TCP packets are trying to learn the optimal transimission rate the Internet allows; (3) routing problems (see several papers by Glazebrook, Nino-Mora and their co-authors) where each job select which server to join. This literature may help you clarify which queueing system you consider in your paper (and perhaps give ideas for future research).   4. There has been recent research on queueing systems with unknown service rate, which you have completely ignored. It is essential that you review those papers and clarify what has already been done and what is different in your paper. E.g., Guo and Matta 2002, Zikos and Karatza 2011, Debo, Veeraraghavan 2014 and the papers citing these.  5. The abstract need to make clear what problem you consider. Is mentioning of the bandit model really essential there? I also don't think the sentence starting "A naive view of this problem would suggest..." is appropriate for an abstract.  6. I would encourage you to describe in the introduction the full problem (with multiple queues). This is because you should also refer to the related literature of the full problem. After you describe the queueing problem in the introduction, make very clear how the bandit model is used to model it: an "arm" could be a single job, or a queue of jobs, or a server (or many other things); how many arms are pulled every time; what happens if there is no job to serve; what what happens if the job is not completed (no reward), what are the possible rewards. In Section 3 you can then limit to case U=1 if you wish to present this problem only.  7. Your Assumption 1 (Initial state) seems very strong to me. In practice it will almost never be satisfied. There needs to be a discussion on whether it is essential for your results and what happens when it is not satisfied.  8. Several references have typos in the titles (e.g. kl-ucb, thompson, c|mu, bayesian)  9. Several unclear phrases are listed below - line 42: "incorporating queueing behavior into the MAB model is an essential challenge" ->  it sounds like it has not been done before, but see the literature listed above - line 48: "reward equals job service" -> "reward is 1 of job service is completed in the current slot, 0 otherwise." - line 50 is correct only in the single server setting - line 57: "formally" - make it more formal (are you interested in finite-time or asymptotic results?) - line 62-64: this is far from obvious, mostly because the model is not clear yet - line 66: "unable to even stabilize" - this will depend on the parameters (for some it may be always stable) - line 77: "below zero" -> why not "negative"? - line 105: "up to a log log t factor" -> maybe more precisely "up to a 1 / log log t factor"  - line 148 (and elsewhere): "arrival rate" and "service rate" are appropriate in a continuous time setting. Here it would be more precise to use "arrival probability" and "service completion probability" - line 154 (and in the appendix): "service offered" - define... what are the possible values? - equation above line 157 is repeated (1) - line 195: Defition 1 is wrongly worded. It is also not clear whether being alpha-consistent is problem-instance dependent - line 205: "bandit algorithms" - which of them do you mean? - line 213 (and lines 261, 284): give a link where the full proof can be found - line 225: it is not clear if you start from t=0 or t=1 - line 238-240: repertitive to 187-189 - line 267: "the the" - line 316: you mention comparison, without linking to where it can be found - "stability region" - define - "crowdsourcing example described in the introduction" - I haven't found one - line 436: the sentence is not finished. - Theorem 16 is different from Theorem 1. It is not obvious how Theorem 1 is obtained, nor it is mentioned that the proof of Theorem 16 is also the proof of Theorem 1. - notation \mu* and \mu_max is used inconsistently - Figure 3 and "Additional discussion" should be moved to the main body if space permits - Please add arrows in Figure 3 to indicate which curve refers to which policy, as it is not clear (I only see 4 curves)