40 research outputs found
Asymptotically optimal priority policies for indexable and non-indexable restless bandits
No full textWe study the asymptotic optimal control of multi-class restless bandits. A restless bandit is a controllable stochastic process whose state evolution depends on whether or not the bandit is made active. Since finding the optimal control is typically intractable, we propose a class of priority policies that are proved to be asymptotically optimal under a global attractor property and a technical condition. We consider both a fixed population of bandits as well as a dynamic population where bandits can depart and arrive. As an example of a dynamic population of bandits, we analyze a multi-class M/M/S+M queue for which we show asymptotic optimality of an index policy.We combine fluid-scaling techniques with linear programming results to prove that when bandits are indexable, Whittle's index policy is included in our class of priority policies. We thereby generalize a result of Weber and Weiss (1990) about asymptotic optimality of Whittle's index policy to settings with (i) several classes of bandits, (ii) arrivals of new bandits, and (iii) multiple actions. Indexability of the bandits is not required for our results to hold. For non-indexable bandits we describe how to select priority policies from the class of asymptotically optimal policies and present numerical evidence that, outside the asymptotic regime, the performance of our proposed priority policies is nearly optimal
Asymptotically optimal priority policies for indexable and non-indexable restless bandits
No full textWe study the asymptotic optimal control of multi-class restless bandits. A restless bandit is a controllable stochastic process whose state evolution depends on whether or not the bandit is made active. Since finding the optimal control is typically intractable, we propose a class of priority policies that are proved to be asymptotically optimal under a global attractor property and a technical condition. We consider both a fixed population of bandits as well as a dynamic population where bandits can depart and arrive. As an example of a dynamic population of bandits, we analyze a multi-class M/M/S+M queue for which we show asymptotic optimality of an index policy.We combine fluid-scaling techniques with linear programming results to prove that when bandits are indexable, Whittle's index policy is included in our class of priority policies. We thereby generalize a result of Weber and Weiss (1990) about asymptotic optimality of Whittle's index policy to settings with (i) several classes of bandits, (ii) arrivals of new bandits, and (iii) multiple actions. Indexability of the bandits is not required for our results to hold. For non-indexable bandits we describe how to select priority policies from the class of asymptotically optimal policies and present numerical evidence that, outside the asymptotic regime, the performance of our proposed priority policies is nearly optimal
QUESTA special volume on ‘Current Trends in Queueing Theory' of the second ECQT conference (Part 2)
No full textInternational audience8 articles in this issu
QUESTA special volume on ‘Current Trends in Queueing Theory' of the second ECQT conference (Part 1)
No full textInternational audience10 articles in this issu
QUESTA special volume on ‘Current Trends in Queueing Theory' of the second ECQT conference (Part 2)
No full textInternational audience8 articles in this issu
Asymptotic Optimal Control of Markov-Modulated Restless Bandits
No full textInternational audienceThis paper studies optimal control subject to changing conditions. This is an area that recently received a lot of attention as it arises in numerous situations in practice. Some applications being cloud computing systems where the arrival rates of new jobs fluctuate over time, or the time-varying capacity as encountered in power-aware systems or wireless downlink channels. To study this, we focus on a restless bandit model, which has proved to be a powerful stochastic optimization framework to model scheduling of activities. In particular, it has been extensively applied in the context of optimal control of computing systems. This paper is a first step to its optimal control when restless bandits are subject to changing conditions, the latter being modeled by Markov-modulated environments. We consider the restless bandit problem in an asymptotic regime, which is obtained by letting the population of bandits grow large, and letting the environment change relatively fast. We present sufficient conditions for a policy to be asymptotically optimal and show that a set of priority policies satisfies these. Under an indexability assumption, an averaged version of Whittle's index policy is proved to be inside this set of asymptotic optimal policies. The performance of the averaged Whittle's index policy is numerically evaluated for a multi-class scheduling problem in a wireless downlink subject to changing conditions. While keeping the number of bandits constant, we observe that the average Whittle index policy becomes close to optimal as the speed of the modulated environment increases
Interpolation approximations for the steady-state distribution in multi-class resource-sharing systems
No full textInternational audienceWe consider a single-server multi-class queue that implements relative priorities among customers of the various classes. The discipline might serve one customer at a time in a non-preemptive way, or serve all customers simultaneously. The analysis of the steady-state distribution of the queue-length and the waiting time in such systems is complex and closed-form results are available only in particular cases. We therefore set out to develop approximations for the steady-state distribution of these performance metrics. We first analyze the performance in light traffic. Using known results in the heavy-traffic regime, we then show how to develop an interpolation-based approximation that is valid for any load in the system. An advantage of the approach taken is that it is not model dependent and hence could potentially be applied to other complex queueing models. We numerically assess the accuracy of the interpolation approximation through the first and second moments
Dynamic fluid-based scheduling in a multi-class abandonment queue
No full textInternational audienceWe investigate how to share a common resource among multiple classes of customers in the presence of abandonments. We consider two different models: (1) customers can abandon both while waiting in the queue and while being served, (2) only customers that are in the queue can abandon. Given the complexity of the stochastic optimization problem we propose a fluid model as a deterministic approximation. For the overload case we directly obtain that the c˜µ/θ rule is optimal. For the underload case we use Pontryagin’s Maximum Principle to obtain the optimal solution for two classes of customers; there exists a switching curve that splits the two-dimensional state-space into two regions such that when the number of customers in both classes is sufficiently small the optimal policy follows the c˜µ-rule and when the number of customers is sufficiently large the optimal policy follows the c˜µ/θ-rule. The same structure is observed in the optimal policy of the stochastic model for an arbitrary number of classes. Based on this we develop a heuristic and by numerical experiments we evaluate its performance and compare it to several index policies. We observe that the suboptimality gap of our solution is small
On a unifying product form framework for redundancy models
No full textInternational audienceIn this paper, we present a unifying analysis for redundancy systems with cancel-on-start () and cancel-on-complete () with exponentially distributed service requirements. With () all redundant copies are removed as soon as one of the copies starts (completes) service. As a consequence, does not waste any computing resources, as opposed to . We show that the model is equivalent to a queueing system with multi-type jobs and servers, which was analyzed in \cite{Visschers12},and show that (under the assumption of i.i.d. copies) can be analyzed by a generalization of \cite{Visschers12} where state-dependent departure rates are permitted. This allows us to show that the stationary distribution for both the and models have a product form. We give a detailed first-time analysis for and derive a closed form expression for important metrics like mean number of jobs in the system, and probability of waiting. We also note that the model is equivalent to Join-Shortest-Work queue with redundancy (JSW()). In the latter, an incoming job is dispatched to the server with smallest workload among randomly chosen ones. Thus, all our results apply mutatis-mutandis to JSW().{Comparing the performance of with that of with i.i.d copies gives the unexpected conclusion (since does not waste any resources) that is worse in terms of mean number of jobs. As part of ancillary results, we illustrate that this is primarily due to the assumption of i.i.d copies in case of (together with exponentially distributed requirements) and that such assumptions might lead to conclusions that are qualitatively different from that observed in practice
Markov-modulated M/G/1-type queue in heavy traffic and its application to time-sharing disciplines
No full textThis paper deals with a single-server queue with modulated arrivals, service requirements and service capacity. In our first result, we derive the mean of the total workload assuming generally distributed service requirements and any service discipline which does not depend on the modulating environment. We then show that the workload is exponentially distributed under heavy-traffic scaling. In our second result, we focus on the discriminatory processor sharing (DPS) discipline. Assuming exponential, class-dependent service requirements, we show that the joint distribution of the queue lengths of different customer classes under DPS undergoes a state-space collapse when subject to heavy-traffic scaling. That is, the limiting distribution of the queue-length vector is shown to be exponential, times a deterministic vector. The distribution of the scaled workload, as derived for general service disciplines, is a key quantity in the proof of the state-space collapse
