Online Learning Algorithms for Stochastic Inventory and Queueing Systems

Abstract

The management of inventory and queueing systems lies in the heart of operations research and plays a vital role in many business enterprises. To this date, the majority of work in the literature has been done under complete distributional information about the uncertainties inherent in the system. However, in practice, the decision maker may not know the exact distributions of these uncertainties (such as demand, capacity, lead time) at the beginning of the planning horizon, but can only rely on realized observations collected over time. This thesis focuses on the interplay between learning and optimization of three canonical inventory and queueing systems and proposes a series of first online learning algorithms.

The first system studied in Chapter II is the periodic-review multiproduct inventory system with a warehouse-capacity constraint. The second system studied in Chapter III is the periodic-review inventory system with random capacities. The third system studied in Chapter IV is the continuous-review make-to-stock M/G/1 queueing system. We take a nonparametric approach that directly works with data and needs not to specify any (parametric) form of the uncertainties. The proposed online learning algorithms are stochastic gradient descent type, leveraging the (sometimes non-obvious) convexity properties in the objective functions. The performance measure used is the notion of cumulative regret or simply regret, which is defined as the cost difference between the proposed learning algorithm and the clairvoyant optimal algorithm (had all the distributional information about uncertainties been given). Our main theoretical results are to establish the square-root regret rate for each proposed algorithm, which is known to be tight. Our numerical results also confirm the efficacy of the proposed learning algorithms.

The major challenges in designing effective learning algorithms for such systems and analyzing them are as follows. First, in most retail settings, customers typically walk away in the face of stock-out, and therefore the system is unable to keep track of these lost-sales. Thus, the observable demand data is, in fact, the sales data, which is also known as the censored demand data. Second, the inventory decisions may impact the cost function over extended periods, due to complex state transitions in the underlying stochastic inventory system. Third, the stochastic inventory system has hard physical constraints, e.g., positive inventory carry-over, warehouse capacity constraint, ordering/production capacity constraint, and these constraints limit the search space in a dynamic way.

We believe this line of research is well aligned with the important opportunity that now exists to advance data-driven algorithmic decision-making under uncertainty. Moreover, it adds an important dimension to the general theory of online learning and reinforcement learning, since firms often face a realistic stochastic supply chain system where system dynamics are complex, constraints are abundant, and information about uncertainties in the system is typically censored. It is, therefore, important to analyze the structure of the underlying system more closely and devise an efficient and effective learning algorithm that can generate better data, which is then feedback to the algorithm to make better decisions. This forms a virtuous cycle.