Executive Summary : | Queueing theory is a sub-field in Operations Research that focusses on performance modeling and analysis of congestion based service systems. A key objective in queueing theory is to design control policies for congestion based service systems such that a desired level of quality of service (measure by statistics such as average delay or average queue lengths) is mantained in the system. To control the performance level of such queues, one must use tools such as routing, scheduling or admission control to regulate the arrival rates, ordering of jobs and load balancing of workloads across multiple servers. To identify optimal control policies when the model parameters (such as server speeds, arrival rates and service requirement characteristics) are known, one resorts to theoretical tools such as Markov decision processes and stochastic optimization. When it comes to controling queues in practice, a key bottleneck however is that for many service systems, the underlying parameters of the system may not be known apriori. For example, the arrival rates of jobs to a queueing systems or the service rates of the servers may not be known or may even change over time. Similarly, the service requirement distribution for arriving jobs may not be known. In the absence of such crucial information, controlling such queues optimally is not possible and practitioners often resort to heuristic policies. One possible scientific theory however at ones disposal is to make use of reinfocement learning (R.L.) algorithms to perform optimal control of queues with properties such as low regret and asymptiotic optimality. Application of RL to queueing theory is something which has been largely overlooked but is becoming of increasing interest to the queueing theory community. The objective of the proposal is to make theoretical contrbutions towards application of RL algorithms to queueing systems .The key objective of the proposal is to consider two important yet open problems in this area. In the first problem, under uncertainty in the service time distribution, we want to provide RL algorithms to identify optimal scheduling policy minimizing the mean delay in a single server queue. In the second problem, we want to identify RL algorithms that identify optimal routing rules to assign jobs to hetergeneous servers, especially when the server speeds are not known. For both this problems, we aim to provide RL algorithms that not only are asymptotically optimal, but also have low finite time regret. The theoretical analysis required to prove these objectives is particularly challenging due to the fact that queues are continuous time systems while most RL algorithms have been extensively analyzed in discrete time. One therefore has to resort to uniformization to convert the continuous time dynamic to a discrete time one to perform meaningful analysis. |