Learning Optimal Admission Control in Partially Observable Queueing Networks
This work addresses efficient policy learning for queueing systems, which is incremental as it builds on existing methods like Norton's theorem and birth-and-death processes to handle partial observability.
The paper tackles the problem of learning optimal admission control in partially observable queueing networks, where only arrival and departure times are observable, and achieves a regret bound that depends sub-linearly on the maximal number of jobs, avoiding exponential dependencies on the network diameter.
We present an efficient reinforcement learning algorithm that learns the optimal admission control policy in a partially observable queueing network. Specifically, only the arrival and departure times from the network are observable, and optimality refers to the average holding/rejection cost in infinite horizon. While reinforcement learning in Partially Observable Markov Decision Processes (POMDP) is prohibitively expensive in general, we show that our algorithm has a regret that only depends sub-linearly on the maximal number of jobs in the network, $S$. In particular, in contrast with existing regret analyses, our regret bound does not depend on the diameter of the underlying Markov Decision Process (MDP), which in most queueing systems is at least exponential in $S$. The novelty of our approach is to leverage Norton's equivalent theorem for closed product-form queueing networks and an efficient reinforcement learning algorithm for MDPs with the structure of birth-and-death processes.