1 May 2020 in Management Science
We consider a periodic-review, single-product inventory system with lost sales and positive lead times under censored demand. In contrast to the classical inventory literature, we assume the firm does not know the demand distribution a priori and makes an adaptive inventory-ordering decision in each period based only on the past sales (censored demand) data. The standard performance measure is regret, which is the cost difference between a learning algorithm and the clairvoyant (full-information) benchmark. When the benchmark is chosen to be the (full-information) optimal base-stock policy, Huh et al. [Huh WT, Janakiraman G, Muckstadt JA, Rusmevichientong P (2009a) An adaptive algorithm for finding the optimal base-stock policy in lost sales inventory systems with censored demand. Math. Oper. Res. 34(2):397–416.] developed a nonparametric learning algorithm with a cubic-root convergence rate on regret. An important open question is whether there exists a nonparametric learning algorithm whose regret rate matches the theoretical lower bound of any learning algorithms. In this work, we provide an affirmative answer to this question. More precisely, we propose a new nonparametric algorithm termed the simulated cycle-update policy and establish a square-root convergence rate on regret, which is proven to be the lower bound of any learning algorithm. Our algorithm uses a random cycle-updating rule based on an auxiliary simulated system running in parallel and also involves two new concepts, namely the withheld on-hand inventory and the double-phase cycle gradient estimation. The techniques developed are effective for learning a stochastic system with complex system dynamics and lasting impact of decisions. This paper was accepted by Yinyu Ye, optimization.
21 October 2008 in Naval Research Logistics (NRL)
1 May 2021 in Mathematics of Operations Research
We consider a joint pricing and inventory control problem in which the customer’s response to selling price and the demand distribution are not known a priori. Unsatisfied demand is lost and unobserved, and the only available information for decision making is the observed sales data (also known as censored demand). Conventional approaches, such as stochastic approximation, online convex optimization, and continuum-armed bandit algorithms, cannot be employed, because neither the realized values of the profit function nor its derivatives are known. A major challenge of this problem lies in that the estimated profit function constructed from observed sales data is multimodal in price. We develop a nonparametric spline approximation–based learning algorithm. The algorithm separates the planning horizon into a disjoint exploration phase and an exploitation phase. During the exploration phase, a spline approximation of the demand-price function is constructed based on sales data, and then the corresponding surrogate optimization problem is solved on a sparse grid to obtain a pair of recommended price and target inventory level. During the exploitation phase, the algorithm implements the recommended strategies. We establish a (nearly) square-root regret rate, which (almost) matches the theoretical lower bound.
1 October 2018 in Operations Research
We develop the first nonparametric learning algorithm for periodic-review perishable inventory systems. In contrast to the classical perishable inventory literature, we assume that the firm does not know the demand distribution a priori and makes replenishment decisions in each period based only on the past sales (censored demand) data. It is well known that even with complete information about the demand distribution a priori, the optimal policy for this problem does not possess a simple structure. Motivated by the studies in the literature showing that base-stock policies perform near optimal in these systems, we focus on finding the best base-stock policy. We first establish a convexity result, showing that the total holding, lost sales and outdating cost is convex in the base-stock level. Then, we develop a nonparametric learning algorithm that generates a sequence of order-up-to levels whose running average cost converges to the cost of the optimal base-stock policy. We establish a square-root convergence rate of the proposed algorithm, which is the best possible. Our algorithm and analyses require a novel method for computing a valid cycle subgradient and the construction of a bridging problem, which significantly departs from previous studies. The e-companion is available at https://doi.org/10.1287/opre.2018.1724
1 September 2020 in Operations Research
Pricing and inventory replenishment are important operations decisions for firms such as retailers. To make these decisions effectively, a firm needs to know the demand distribution and its dependency on selling price, which is usually estimated using sales data at various testing price levels. Although more testing prices can lead to a better estimation of the demand–price relationship, frequent price changes are costly and come with adverse effect such as customers’ negative perception. In this article, data-driven algorithms are developed that learn the demand structure with constraints on the number of price changes. These algorithms are shown to converge to the optimal clairvoyant solution, and the convergence rates are the best possible in terms of profit loss.
1 November 2018 in Management Science
Managing perishable inventory systems with positive lead times and finite ordering capacities is important but notoriously difficult in both theory and computation. The optimal control policy is extremely complicated, and no effective heuristic policy has been proposed in the literature. In this paper, we develop an easy-to-compute approximation algorithm for this class of problems and prove that it admits a theoretical worst-case performance guarantee under independent and many commonly used positively correlated demand processes. Our worst-case analysis departs significantly from those in the previous studies, requiring several novel ideas. In particular, we introduce a transient unit-matching rule to dynamically match the supply and demand units, and the notion of associated demand processes that provides the right future demand information to establish the desired results. Our numerical study demonstrates the effectiveness of the proposed algorithm. This paper was accepted by Yinyu Ye, optimization.