We consider the problem of customer equilibrium strategies in an M/M/1 queue under dynamic service control. The service rate switches between a low and a high value depending on system congestion. Arriving customers do not observe the system state at the moment of arrival. We show that due to service rate variation, the customer equilibrium strategy is not generally unique, and derive an upper bound on the number of possible equilibria. For the problem of social welfare optimization, we numerically analyze the relationship between the optimal and equilibrium arrival rates as a function of various parameter values, and assess the level of inefficiency via the price of anarchy measure. We finally derive analytic solutions for the special case where the service rate switch occurs when the queue ceases to be empty. © 2016 Elsevier B.V. All rights reserved.

We consider the multi-armed bandit problem under a cost constraint. Successive samples from each population are i.i.d. with unknown distribution and each sample incurs a known population-dependent cost. The objective is to design an adaptive sampling policy to maximize the expected sum of n samples such that the average cost does not exceed a given bound sample-path wise. We establish an asymptotic lower bound for the regret of feasible uniformly fast convergent policies, and construct a class of policies, which achieve the bound. We also provide their explicit form under Normal distributions with unknown means and known variances. Copyright © Cambridge University Press 2016