Abstract: The multiclass many server queue with abandonment (specifically, the multiclass GI/GI/N+GI queue) is a canonical model for service systems. One key operational question is how to schedule; that is, how to choose the customer that a newly available server will serve. The scheduling question is of fundamental importance because scheduling determines which customer classes have longer wait times (relative to their patience when waiting for service), and, therefore, more abandonments. However, even though there is much work on scheduling in queueing systems, there is comparatively less work on scheduling in queueing systems when the model primitives (that is, distributional and parameter information regarding the inter-arrival, service, and patience times) are unknown and may be learned.

Our objective is to determine a scheduling policy that minimizes regret, which is the difference in expected abandonment cost between a proposed policy, that does not have knowledge of model primitives, and a benchmark policy, that has full knowledge of model primitives. The difficulty is that the state space is very complex, because in order for the system to be Markovian, we must track: (i) the time elapsed since the last arrival for each class; (ii) the amount of time each customer in service has been in service; and (iii) the amount of time each customer in queue has spent waiting. We propose a policy that first learns and then schedules following a Learn-then-Schedule (LTS) algorithm that we develop. We analyze the performance of the LTS policy against the benchmark aμ-rule (that prioritizes classes for service in accordance with their cost of abandonment times service rate). The algorithm is composed of a learning phase, during which empirical estimates of the service rates are formed, and an exploitation phase, during which an empirical aμ-rule based on those estimates is applied. We show that the LTS policy has regret of order log T (where T is the system run-time), which is the smallest order achievable.

Bio: Amy is a fellow of the INFORMS Manufacturing and Service Operations Management (M&SOM) Society (elected June, 2023).  Amy is the incoming Editor-in-Chief for the journal Operations Research (term begins 1/1/2024), and the outgoing Editor-in-Chief for the journal Operations Research Letters (term 4/1/2021-12/30/2023).  Prior to that, Amy held the position of Chair of the INFORMS Applied Probability Society (term 11/2016-11/2018). 

Abstract: Motivated by applications in queueing theory, we consider a class of singular stochastic control problems whose state space is the d-dimensional positive orthant. The original problem is approximated by a drift control problem, to which we apply a recently developed computational method that is feasible for dimensions up to d=30 or more. To show that nearly optimal solutions are obtainable using this method, we present computational results for a variety of examples, including queueing network examples that have appeared previously in the literature.

Bio: Baris Ata is the Sigmund E. Edelstone Distinguished Service Professor of Operations Management at The University of Chicago, Booth School of Business. He received the B.S. degree in Industrial Engineering from Bilkent University (TURKEY) in 1997, and MS degrees in Engineering-Economic Systems and Operations Research (1999), Business Research (2000), Mathematics (2001), and Statistics (2002) and a Ph.D. in Operations, Information, and Technology (2003) from Stanford University.

His current research interests include operational aspects of organ transplantation, criminal justice system, global health, as well as theoretical and computational study of stochastic networks and their applications. His research has been recognized by the Best Paper in Service Science Award, INFORMS (2009), William Pierskalla Best Paper Award, INFORMS (2015) and Wickham Skinner Best Paper Award, POMS (2019). He is also a recipient of the Manufacturing and Service Operations Management Young Scholar Prize, INFORMS (2015) and Emory Williams MBA (school wide) Teaching Award at Chicago Booth (2021).

Abstract: Many policy-based reinforcement learning (RL) algorithms can be viewed as instantiations of approximate policy iteration (PI), i.e., where policy improvement and policy evaluation are both performed approximately. In applications where the average reward objective is the meaningful performance metric, discounted reward formulations are often used with the discount factor being close to one which is equivalent to making the expected horizon very large. However, the corresponding theoretical bounds for error performance scale with the square of the horizon. Thus, even after dividing the total reward by the length of the horizon, the corresponding performance bounds for average reward problems go to infinity. Therefore, an open problem has been to obtain meaningful performance bounds for approximate PI and RL algorithms for the average-reward setting. In this paper, we solve this open problem by obtaining the first finite-time error bounds for average-reward MDPs, and show that the asymptotic error goes to zero in the limit as policy evaluation and policy improvement errors go to zero. 

Bio: Mehrdad Moharrami is an Assistant Professor in Computer Science at the University of Iowa. Previously, he was a TRIPODS Postdoctoral Research Fellow at the University of Illinois at Urbana Champaign. He received his B.Sc. from the Sharif University of Technology, Iran, in Mathematics, as well as Electrical Engineering. He holds an M.Sc. in Electrical Engineering and an M.Sc. in Mathematics from the University of Michigan. He received his Ph.D. in Electrical Engineering in Winter 2020, for which he was awarded the Rackham Predoctoral Fellowship for an outstanding dissertation. His research interests are Markov decision processes, reinforcement learning, and random graph models for economics, learning, and computation.

Abstract: 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 theta from a parameter set Theta, and defined on a countably-infinite state space the d-dimensional lattice of non-negative integers, with finite action space, and an unbounded cost function. We take a Bayesian perspective with the random unknown parameter theta* generated via a given fixed (full-support) prior distribution on Theta. 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 sub-linear upper bound on the Bayesian regret of our algorithm in terms of 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.

Bio: Vijay Subramanian received the Ph.D. degree in electrical engineering from the University of Illinois at Urbana-Champaign,  Champaign, IL, USA, in 1999. He worked at Motorola Inc., at the Hamilton Institute, Maynooth, Ireland, for many years, and also in the EECS Department, Northwestern University, Evanston, IL, USA. In Fall 2014, he started in his current position as an Associate Professor with the  EECS Department at the University of Michigan, Ann Arbor. For the academic year 2022-2023, he was an Adjunct Research Associate Professor in CSL and ECE at UIUC. His research interests are in stochastic analysis, random  graphs, multi-agent systems, and game theory (mechanism and information design) with applications to social, economic and technological networks.

Abstract: Reinforcement learning in continuous time is a suitable learning model for agents interacting with a stochastic environment at ultra-high frequency. However, most of the existing literature on continuous time RL focuses on semimartingale or Markovian environments, which do not accurately represent many real-world ultra-high frequency applications. For example, the volatility of stock market returns can be appropriately modeled as fractional Brownian motion (fBM), and controlled stochastic networks with heavy-tailed service in heavy-traffic are well approximated by reflected fBM processes. These are but two examples across a range of applications in science and engineering.

This talk presents our recent results in developing a theoretical framework for modeling exploration processes in general continuous time stochastic environments using rough path theory. In continuous time, exploration becomes more complex since randomized policies at each time-step cannot be used to explore. Instead, actions must be continuously randomized in some way. Relaxed controls, in the sense of continuous curves of probability measures in Wasserstein space, provide a natural approach to modeling a randomized exploration process in continuous time. Therefore, we propose and analyze a pathwise relaxed control framework to model exploration in continuous-time reinforcement learning in general stochastic environments. Specifically, we establish the existence and uniqueness of the value function as a solution of a rough Hamilton-Jacobi-Bellman equation. This is our first step towards establishing a comprehensive theory of continuous-time reinforcement learning. As an immediate application of the analysis of the value function, we use it to characterize the optimal exploration-relaxed control for an entropy-regularized objective, which emulates maximum-entropy objectives in discrete-time reinforcement learning.

This talk is based on joint work with Prakash Chakraborty at Penn State and Samy Tindel at Purdue. This project is supported by the National Science Foundation through grant DMS/2153915. 

Bio: Harsha Honnappa is an Associate Professor in the School of Industrial Engineering at Purdue University and a J. Tinsley Oden Visiting Faculty Fellow at the Oden Institute at The University of Texas at Austin. His research interests as an applied probabilist encompass stochastic modeling, optimization and control, with applications to machine learning, simulation and statistical inference. His research is supported by the National Science Foundation, including an NSF CAREER award, and the Purdue Research Foundation. He is an editorial board member at Operations Research, Operations Research Letters and Queueing Systems journals.

Abstract: A common technique in reinforcement learning is to evaluate the value function from Monte Carlo simulations of a given policy, and use the estimated value function to obtain a new policy which is greedy with respect to the estimated value function. A well-known longstanding open problem in this context is to prove the convergence of such a scheme when the value function of a policy is estimated from data collected from a single sample path obtained from implementing the policy. We present a solution to the open problem by showing that a first-visit version of such a policy iteration scheme indeed converges to the optimal policy provided that the policy improvement step uses lookahead rather than a simple greedy policy improvement. We provide results both for the original open problem in the tabular setting and also present extensions to the function approximation setting, where we show that the policy resulting from the algorithm performs close to the optimal policy within a function approximation error. Joint work with Anna Winnicki. 

Bio: R. Srikant is a Grainger Chair in Engineering and Professor of Electrical and Computer Engineering and the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. His research interests span applied probability, machine learning and communication networks.