Learning a Discrete Set of Optimal Allocation Rules in Queueing Systems
  with Unknown Service Rates
  We study learning-based admission control for a classical Erlang-B blocking
system with unknown service rate, i.e., an $M/M/k/k$ queueing system. At every
job arrival, a dispatcher decides to assign the job to an available server or
to block it. Every served job yields a fixed reward for the dispatcher, but it
also results in a cost per unit time of service. Our goal is to design a
dispatching policy that maximizes the long-term average reward for the
dispatcher based on observing the arrival times and the state of the system at
each arrival; critically, the dispatcher observes neither the service times nor
departure times.
  We develop our learning-based dispatch scheme as a parametric learning
problem a'la self-tuning adaptive control. In our problem, certainty equivalent
control switches between an always admit policy (always explore) and a never
admit policy (immediately terminate learning), which is distinct from the
adaptive control literature. Our learning scheme then uses maximum likelihood
estimation followed by certainty equivalent control but with judicious use of
the always admit policy so that learning doesn't stall. We prove that for all
service rates, the proposed policy asymptotically learns to take the optimal
action. Further, we also present finite-time regret guarantees for our scheme.
The extreme contrast in the certainty equivalent optimal control policies leads
to difficulties in learning that show up in our regret bounds for different
parameter regimes. We explore this aspect in our simulations and also follow-up
sampling related questions for our continuous-time system.
