Saghar Adler

Saghar Adler, Vijay Subramanian

Models of many real-life applications, such as queuing models of communication networks or computing systems, have a countably infinite state-space. Algorithmic and learning procedures that have been developed to produce optimal policies mainly focus on finite state settings, and do not directly apply to these models. To overcome this lacuna, in this work we study the problem of optimal control of a family of discrete-time countable state-space Markov Decision Processes (MDPs) governed by an unknown parameter $θ\inΘ$, and defined on a countably-infinite state space $\mathcal X=\mathbb{Z}_+^d$, with finite action space $\mathcal A$, and an unbounded cost function. We take a Bayesian perspective with the random unknown parameter $\boldsymbolθ^*$ generated via a given fixed prior distribution on $Θ$. To optimally control the unknown MDP, we propose an algorithm based on Thompson sampling with dynamically-sized episodes: at the beginning of each episode, the posterior distribution formed via Bayes' rule is used to produce a parameter estimate, which then decides the policy applied during the episode. To ensure the stability of the Markov chain obtained by following the policy chosen for each parameter, we impose ergodicity assumptions. From this condition and using the solution of the average cost Bellman equation, we establish an $\tilde O(dh^d\sqrt{|\mathcal A|T})$ upper bound on the Bayesian regret of our algorithm, where $T$ is the time-horizon. Finally, to elucidate the applicability of our algorithm, we consider two different queuing models with unknown dynamics, and show that our algorithm can be applied to develop approximately optimal control algorithms.

Saghar Adler, Mehrdad Moharrami, Vijay Subramanian

Motivated by applications of the Erlang-B blocking model and the extended $M/M/k/k+N$ model that allows for some queueing, beyond communication networks to sizing and pricing in production, messaging, and app-based parking systems, we study admission control for such systems with unknown service rate. In our model, a dispatcher either admits every arrival into the system (when there is room) or blocks it. Every served job yields a fixed reward but incurs a per unit time holding cost which includes the waiting time in the queue to get service if there is any. We aim to design a dispatching policy that maximizes the long-term average reward by observing arrival times and system state at arrivals, a realistic decision-event driven sampling of such systems. The dispatcher observes neither service times nor departure epochs, which excludes the use of reward-based reinforcement learning approaches. 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 always admit if room (explore infinitely often), and never admit (terminate learning), so at judiciously chosen times we avoid the never admit recommendation. We prove that our proposed policy asymptotically converges to the optimal policy and present finite-time regret guarantees. The extreme contrast in the control policies shows up in our regret bounds for different parameter regimes: constant in one versus logarithmic in another.