Data-driven research in retail operations—A review

2.1.1 Review of popular choice models

Let us consider a set of n products that the retailer can offer. For an offer set S ⊂ {1, …, n} chosen by the retailer, a parametric discrete choice model characterizes the probability that a customer chooses to purchase product i as a function of S, denoted by P_i(S). Here, product 0 denotes the no-purchase option.

• Multinomial Logit model

Under the multinomial logit (MNL) model, customers choose a product (or no purchase) according to randomly realized utility U_i = V_i + ϵ_i with product i, where ϵ_i is the random noise that follows standard Gumbel distribution and V_i is a constant. Then the probabilities that a customer chooses product i from assortment S, and the no purchase option, (denoted by $0$), are

• Mixed Multinomial Logit model

Under the Mixed Multinomial Logit (MMNL) model, in addition to the random noise term, the mean utilities V_i, i = 1, …, n are also modeled as random variables. The mean utilities can follow either discrete or continuous probability distributions. The case that the utility vector V = (V₁, …, V_n) follows a discrete distribution with m different values, denoted by , may represent the existence of multiple customer types with corresponding to the mean utilities of customer type j ∈ {1, …, m}. An example where V follows a continuous distribution is when there are product-independent sensitivities in the form V_i = μ_i + P − Br_i, where μ_i is a deterministic constant, r_i is the price of product i, and P and B are continuous random variables. The random variable B can be assumed to be positive to represent price sensitivity of the customer.

In the MMNL model, P_i is modeled as the conditional probability that a customer chooses product i from assortment S, given both the assortment S and the realization of utility V:

• Nested Logit model

Under the Nested Logit (NL) model, customers first select a subset of product, referred to as a “nest”. The nests form a partition of the product ground set. A customer first chooses a nest (e.g., a cell phone brand), and then choose a specific product (a phone model of the chosen brand). Suppose there are m nests each with n products. We let W_ij and W_0j be the utility weights of product j and the no-purchase option in nest i, respectively. Conditioned on a customer choosing nest i, the probabilities of the customer selecting product j from a sub-assortment S_i (in nest i) and no purchase are given by

where . Furthermore, each nest j is also associated with a parameter γ_j ≥ 0 that characterizes the degree of the dissimilarity of the products in the nest. In the NL model, the dissimilarity parameters (γ₁, …, γ_m) are assumed to be constants and the preference weights W_ij are generated by a random utility that follows a multidimensional generalized extreme value distribution with mean V_ij. Then, the preference weights can be represented in a similar form as in the MNL model:

Then, if the assortment consists of sub-assortments (S₁, …, S_m) for nests 1, …, m, then a customer chooses nest j with probability

where W₀ denotes the preference weight for not choosing any nests (e.g., choosing a brand not carried by the seller).

2.1.2 Learning discrete choice models from data

Given a selected choice model, the model parameters (denoted by a vector θ) can be estimated from data. In the ideal case, choice data is collected from an experiment (Bunch, 1987). Suppose there are n products and let z_i denote the vector of explanatory variables (factors influencing purchase) associated with product i for i = 1, …, n. Then the utility of item i can be represented by a function V_i(θ, z_i). Consider an experiment for estimating the utility parameters, which consists of T independent trials. In each trial t = 1, …, T, a randomly picked subject is asked to make a choice in an offered choice set denoted by S_t (possibly multiple times). Let F_it denote the relative frequency of subject t selecting product i. The choice probability for product j can be written in the form

Then, for trial t, the probability of the subject selecting item i in choice set S_t is P_i(S_t, θ). Then, the model can be estimated through the maximum likelihood estimate (MLE) of θ, denoted by , which can be formulated as

where

Bunch (1987) investigate the particular case where V_i(θ, z_i) = θ^Tz_i, and propose an algorithm for general probabilistic choice models and show that the MLE problem can be written as a problem in generalized regression. More details about algorithms to achieve MLE and comparisons of MLE with other estimators for choice model parameters are stated in Bunch (1988), and Bunch and Batsell (1989).

However, identifying the exact explanatory variable values for each product and implementing the aforementioned independent trials is often impractical. In fact, the customer choice data collected in real-world situations are often very sparse, that is, only a small number of observations are available for each choice set and a small proportion of choice sets are observed among all possible ones. Benefited from recent advances in learning low-rank models, it is possible to learn choice models from data on comparisons and choices.

Negahban, Oh, Thekumparampil, and Xu (2018) investigate the problem of estimating MNL model parameter values that best explain the data. The authors consider different forms of available data: pairwise comparisons, that is, the customer's choice when given two options; higher-order comparisons, that is, the customer's rankings over a given subset of items; customer choices, that is, the customer's choices of the best item out of a given subset; and bundled choices, that is, the customer's choices of bundled items. For the scenario when pairwise comparisons are available, the authors propose a graph sampling method that captures sample irregularity. They also propose a convex relaxation of the MNL learning problem and show that it is minimax optimal up to a logarithmic factor. This proves that the proposed estimator cannot be improved upon other than by a logarithmic factor and identifies how the accuracy depends on the topology of sampling. The authors also extend their framework to the scenario where data includes higher-order comparisons, customer choices, and bundled purchase observations.

However, the richness of the MMNL model presents substantial difficulties for learning. In fact, Ammar, Oh, Shah, and Voloch (2014) show that for any integer k, there exist pairs of MMNL models with n = 2^k + 1 items and m = 2^k mixing components where the samples generated by both models with length l = 2k + 1 would be identical in distribution. Therefore, it is impossible to uniquely distinguish MMNL models in general. Oh and Shah (2014) investigate sufficient conditions under which it is possible to learn MMNL models efficiently (in both statistical and computational sense), and provide an efficient algorithm for cases with partial preference data (higher and pairwise comparisons). Given, for example, pairwise comparison observations, the goal is to learn the mixing distribution over m different MNL submodels and the parameters of each. They consider data in the following form: Each observation is generated by first selecting one of the m mixture components, and then observing comparison outcomes for l pairs of products therein. Their proposed algorithm consists of two phases. The first involves tensor decomposition to learn the pairwise marginals of mixing components. Then, the second phase makes use of these pairwise marginals to learn parameters for individual mixture components. The authors also identify conditions under which the model can be learned with sample sizes polynomial in n (number of products) and m (number of mixing components).

Chierichetti, Kumar, and Tomkins (2018) study the problem of learning a uniform mixture of two MNLs from a more realistic oracle that returns the distribution of choosing products in a given slate. In particular, the uniform 2-MNL model (a,b) assigns to item i in subset S ⊂ {1, …, n} the probability , where a(⋅) and b(⋅) denote the preference weights generated by two different MNL models. Their algorithm builds on a reconstruction oracle that returns the probabilities that each item in a given slate will be chosen. They show that slate sizes of two are insufficient for reconstruction, and thus their oracle with slate size of at most three is optimal. They propose to achieve this oracle by approximating it by sampling over choice processes. Moreover, the authors provide algorithms that makes O(n) and O(n²) queries when the oracle can be queried adaptively and non-adaptively, respectively, and show that they are optimal.

2.1.3 Assortment optimization with parametric discrete choice models

Once parameters of choice models are estimated, the optimal assortment can be determined by solving an optimization problem. A significant stream of literature deals with such optimization problems under settings with different discrete choice models and additional (e.g., capacity) constraints. The literature generally investigates assortment problems with either static or dynamic formulations. In the former case, given the choice model of purchase behavior, the decision maker decides the optimal assortment that maximizes the expected profit in one shot. In the dynamic setting, the inventory of products is taken into consideration over multiple periods.

Suppose there are n products and each product i is associated with revenue r_i. The seller aims to choose a subset S ⊂ N ≔ {1, …, n} to offer. Recall that P_i(S) and P₀(S) denote the choice probabilities of product i and of no purchase, respectively, when assortment S is offered. In the static assortment problem, one seeks the optimal assortment S that maximizes the expected profit where the expectation is taken over the randomness of customer choice. The objective function can be formulated as the following:

When the customer choice probabilities P_i(S) follow the MNL model with known utility parameters, the problem can be solved efficiently by considering only revenue-ordered assortments. In other words, one can start with the empty set and incrementally construct S by sequentially adding a product that results in the maximum increase in revenue at a time. This elegant result is a special case of the nested offer set property of Talluri and Van Ryzin (2004) (although this article originally investigates a more general setting). Motivated by this result, Aouad, Farias, Levi, and Segev (2018) and Berbeglia and Joret (2020) provide performance guarantees of the revenue-ordered assortments. Aouad et al. (2018) consider a general choice model where customer choices are characterized by a distribution over ranked lists of products and Berbeglia and Joret (2020) investigate customer choice models with the assumption that P_i(x) does not increase when S is enlarged.

This simple optimal solution no longer holds when there is a capacity constraint on the assortment, that is, |S |  ≤ C, due to (for example) limits on shelf space. Rusmevichientong, Shen, and Shmoys (2010) investigate the problem:

Rusmevichientong et al. (2010) develop a simple algorithm for computing a profit-maximizing assortment based on a connection between the MNL model and the geometry of lines in the two-dimensional plane, and derive structural properties of the optimal assortment. Jagabathula (2014) study the same problem and propose an easy-to-implement local search heuristic. The authors show that it efficiently finds the global optimum for the MNL model and derive performance guarantees under general choice model structures.

Rusmevichientong and Topaloglu (2012) study the robust assortment problem under the MNL model when some of the parameters of the choice model are unknown. Wang (2012) considers the problem of jointly finding an assortment of products to offer and their corresponding prices when the customers choose under the MNL model. Davis, Gallego, and Topaloglu (2013) investigate the assortment optimization problem with a set of total-unimodularity constraints when customers make purchase decisions according to the MNL model. The authors show that this problem can be formulated as a linear program. Wang (2013) considers the joint problem of assortment and price optimization with a capacity constraint and they assume that customer purchase behavior follows the MNL model with general utility functions. The author simplifies this problem to one of finding a unique fixed point of a single-dimensional function and propose an efficient solution algorithm.

Another extension of the static assortment optimization problem with the MNL model explores the consideration sets of customers. In this model, there are multiple customer types, and a particular type is interested in purchasing only a particular subset of products (the consideration set). A customer observes which of the products in her consideration set are actually included in the offered assortment and makes a choice from among only those products, according to the MNL model. Feldman and Topaloglu (2018) study capacitated assortment problems when the consideration sets are nested. The authors show that this assortment problem is NP-hard, even when there is no restrictions on the total space consumption of offered set. They also provide a fully polynomial time approximation scheme (FPTAS) for the problem. Recall that FPTAS refers to a family of algorithms that for any ϵ > 0, the algorithm is ϵ-optimal with polynomial running time with respect to the input size and 1/ϵ.

The authors also provide an approximation guarantee for the revenue-ordered assortment policy for general MMNL models. Bront, Méndez-Daz, and Vulcano (2009) show that the same problem is NP-hard and Méndez-Daz et al. (2014) develop a brand-and-cut algorithm to find the optimal assortment.

To circumvent computational difficulties, Mittal and Schulz (2013) propose a FPTAS for assortment optimization problem with MMNL model and NL model. Désir, Goyal, and Zhang (2014) consider the capacity-constrained version of the assortment optimization problem under MNL, MMNL, and NL models and provide FPTAS by exploiting connections with the knapsack problem. It is worthwhile pointing out that the running time of their algorithm depends exponentially on the number of mixture components in the MMNL model, and such exponential dependence is necessary for any (1 − ϵ)-approximation algorithm. Instead of developing approximation schemes such as FPTAS, Şen, Atamtürk, and Kaminsky (2018) reformulate the constrained assortment optimization problem under the MMNL model as a conic quadratic mixed-integer program. Making use of McCormick inequalities that exploit the capacity constraints, their formulation enables solving large instances using commercial solvers.

Davis, Gallego, and Topaloglu (2014) study the assortment optimization problem under the two-level NL model with an arbitrary number of nests. They show that the problem is polynomially solvable when the nest dissimilarity parameters (γ_j's in Section 2.1.1) of the NL model are less than one and customers always make a purchase within the selected nest. The problem becomes NP-hard if either assumption is relaxed. To deal with the NP-hard cases, they also develop parsimonious collections of candidate assortments with worst-case performance guarantees and formulate a convex program that provides an upper bound on the optimal expected revenue. Gallego and Topaloglu (2014) then extend the setting to accommodate constraints on the total number of products and the total shelf space used by the offered assortment.

Li, Rusmevichientong, and Topaloglu (2015) investigate the assortment optimization problem under a more general d-level NL model. In their setting, the taxonomy of the product is described by a d-level tree where each node corresponds to a set of products, and each leaf node denotes a single product. Then the customer choice probability can be formulated as a walk from the root node to one of the leaf nodes where at each of the non-leaf nodes, children nodes are chosen following probability generated by preference weights (Q_is defined in Section 2.1.1). With this formulation, the authors give a recursive characterization of the optimal assortment and provide an algorithm that achieves the optimal assortment with complexity O(dnlogn). Wang and Shen (2020) also adopt the d-level NL model and investigate the assortment optimization problem with the no-purchase option in every period of the customer choice process, with cardinality constraints imposed on the lowest level. The authors show that the optimal assortment can be obtained in O(nmax{d,k}) operations (where k denotes the capacity), which is faster than the result for unconstrained case developed in Li et al. (2015). Other studies on the NL case include Mittal and Schulz (2013), who propose a FPTAS for the problem, and Désir et al. (2014), who consider the capacity constrained version of the problem and provide a FPTAS.

In contrast to the static problem, the dynamic assortment optimization problem considers a multi-period setting where inventory can be carried over (though usually not replenishable). This setting arises naturally in revenue management applications. Talluri and Van Ryzin (2004) consider an assortment optimization problem that involves multiple time periods and a capacity constraint on inventory. The setting is motivated by the problem of an airline offering different fare products with a fixed aircraft capacity. In their setting, the different fare products consume the same capacity (seats on the flight) and differ in terms of revenues and conditions (e.g., cancellation policies). They assume that demand arrives with probability λ at each period. The seller chooses a subset S ⊂ N ≔ {1, …, n} to offer. Under this setting, the value function W_t(x) is defined as the maximum expected revenue obtainable from periods t = 1, …, T, given that there are x units of inventory (unsold seats) remaining at the start of time t. Then, the Bellman equation for W_t(x) is

where P_i(S) is the probability that product i is sold when assortment S is offered. Similarly, P₀ is defined as the probability of no purchase when customer is offered S. When P_i(S) and P₀(S) takes the form of the MNL model with know utility weights, Talluri and Van Ryzin (2004) show that the optimal policy is the so-called nested allocation policy based on the order of revenue of product.

Liu and Van Ryzin (2008) investigate a more general multi-period network revenue management problem. The network has l legs and provides n products with initial capacities c₁, …, c_l. The incidence matrix A = {a_ji} indicating whether leg j (∈{1, …, l}) is used by product i (∈N) in which case a_ji = 1, and zero otherwise. They also assume that in each period, the probability of a customer arrival is λ. The decision maker controls the set of offered products (S) in each period to maximize expected total profit over a finite horizon. Similar to the setting in Talluri and Van Ryzin (2004), the problem can be formulated as a dynamic program with the following Bellman equation:

(1)

where A_i denotes the i-th column of the incidence matrix A and x ∈ ℝ_l is the vector of unsold capacities of the l legs. The authors then generalize the analysis of efficient offer sets, proposed by Talluri and Van Ryzin (2004), to the network case. The authors show that, with the MNL model, the optimal assortment can be found based on sorting the products in a descending order of marginal profits. They propose a choice-based deterministic linear program that determines the set of efficient assortments and demonstrate their asymptotic optimality. They also proposed heuristics that convert efficient sets into control policies. Bront et al. (2009) also study the same problem and extend the analysis and decomposition heuristics proposed in Liu and Van Ryzin (2008) to a MNL model where customers belong to discrete segments with different, but possibly overlapping consideration sets. They make use of integer programming formulations and column generation techniques to solve the resulting problem. To solve the same problem as Liu and Van Ryzin (2008), Zhang and Adelman (2009) adopt a different approach that approximates W_t(x), the value function defined in (1), with affine functions of the state vector x. The authors then develop a column generation algorithm to solve the resulting problem and construct associated policies. The authors show that, empirically, their proposed policies can outperform those of Liu and Van Ryzin (2008) by up to 50%.

Rusmevichientong and Topaloglu (2012) study the dynamic assortment optimization problem from the robust optimization perspective, where the true parameters of the choice model are assumed to be unknown and fall within an uncertainty set. In their setting, there is a limited initial inventory to be allocated over time. The authors show that offering revenue-ordered assortments in each period is still optimal. This leads to a method that computes robust optimal policies as efficiently as non-robust approaches.

Other multi-period assortment problems that differ from the aforementioned dynamic formulation include Gallego, Ratliff, and Shebalov (2015), Rusmevichientong et al. (2010), Liu, Ma, and Topaloglu (2020). Gallego et al. (2015) investigate the multi-period network revenue management problem under a more general customer choice model, known as the general attraction model, which includes the MNL model as a special case. Besides the static assortment optimization problem with capacity constraints, Rusmevichientong et al. (2010) also study an online learning version the problem. In particular, the authors consider the setting where the parameters of MNL models are initially unknown and are adaptively learned over time. The authors formulate this problem as a multiarmed bandit problem, provide a policy, and establish an O(log²T) upper bound on the regret. Liu et al. (2020) consider assortment optimization problems where the choice process of a customer takes place in multiple stages. In each stage, customer choice is captured by the MNL model, and the offered assortment is assumed not to overlap with the those offered in the previous stages. The authors prove the NP-hardness of this problem and develop a FPTAS. They also show that, if there are multiple stages, then the union of the optimal assortments to offer in each stage is nested by revenue, though there is no efficient method to determine the stage in which each product should be offered.

3.2.1 Joint fulfillment and pricing or inventory management models

In smart retail supply chains, it is best to integrate decisions on fulfillment and pricing (which determines demand) and inventory management (which determines supply). Govindarajan, Sinha, and Uichanco (2018) investigate the joint problem of inventory management and fulfillment optimization for omni-channel retailers. They consider a multi-period, multi-location setting with no replenishment lead time. The authors provide heuristics for different fulfillment settings and show the advantages of their methods using numerical experiments on real-world data. Lim, Jiu, and Ang (2020) investigate the joint problem of inventory replenishment, allocation, and order fulfillment for online retailers. The authors formulate this problem as a multi-period stochastic optimization problem and solve it with a two-phase approach that based on robust optimization.

Lei, Jasin, and Sinha (2018) consider a similar joint pricing and order fulfillment problem for e-retailers. The authors formulate this as a stochastic control problem with random demand. They propose a tractable deterministic approximation of the problem and two practical heuristics. Lei, Jasin, Uichanco, and Vakhutinsky (2018) then move further to consider a dynamic, multi-period joint display, pricing, and fulfillment optimization problem faced by e-retailers. They provide an approximation of the stochastic control problem using its deterministic relaxation and reformulate it as a tractable linear program. They then develop a randomized heuristic policy based on the idea of hierarchical matrix decomposition and propose a novel iterative algorithm based on finding augmenting paths in a graph representation of the display assignment. Using numerical experiments with synthetic and real-world data, they show that their proposed heuristic is very close to optimal.

Harsha, Subramanian, and Uichanco (2019) examine the joint problem of pricing and order fulfillment for an omni-channel retailer instead of an e-retailer. This adds a new dimension to the problem—in the omni-channel setting, the retailer can charge different prices at different brick-and-mortar stores and online channels at the same time. Motivated by constraints encountered by retailers in practice, the authors consider the omni-channel fulfillment pattern (e.g., the proportion of online customers choosing to pick up in store) to be uncertain and exogenous and focus on optimizing the pricing strategy. The authors propose two pricing policies based on the idea of “partitions” of store inventory for online and offline demand. With partitions, inventory at a store can be used for online fulfillment as long as there is enough inventory to exceed the threshold implied by the partition. Once the inventory drops below this level, no more online orders would be fulfilled from this store. The concept is similar in spirit with the setting of booking limits of different fare classes in revenue management.

The proposed solution approach is based on controlling channel prices to adjust demand to meet the inventory partitions. The authors formulate the problem as a mixed-integer program with a tractable number of binary variables, and suggest a scheme to reduce the number of binary variables when demand follows the MNL model. Such a strategy is computationally tractable at a practical scale and the authors describe a successful implementation at their partner firm, where the partitions are implied from network-level pricing strategies.

3.2.2 Flexibility design in fulfillment optimization

Another extension of the fulfillment problem is to investigate the flexibility structure of the fulfillment network. In manufacturing, the long-chain strategy has been shown to be a very effective flexibility structure, in that a long chain with a small degree of flexibility can perform almost as well as a fully flexible system in meeting uncertain demand (Jordan and Graves (1995), Simchi-Levi and Wei (2012)). The effectiveness of this structure is also investigated by Asadpour, Wang, and Zhang (2020) in an online resource allocation problem with inventory considerations, which is closely related to online fulfillment problem. The authors show that the long-chain structure is effective in hedging against demand uncertainty and mitigating supply–demand mismatch. In their work, the performance of an allocation policy is measured by the expected total number of lost sales in the system and their work aims to provide an upper bound on . The authors assume a total of T demand requests of n possible types will arrive, where the types of requests are stochastic with known probabilities. They propose a simple and practical policy, known as the modified greedy policy, and show that the expected lost sales under the long-chain design is finite and does not diverge as T increases. In the regime when T is significantly larger than the number of types n, the upper bound being independent of T implies that the expected lost sales as a function of total demand is very small.

The authors then investigate the fulfillment optimization problem as a potential application. They consider an online retailer that operates n warehouses and customers are also segmented into n regions (demand types) according to geographic proximity. However, the long-chain concept, which would suggest that each customer region can only be fulfilled by two warehouses (in the case of a 2-chain), does not directly apply well to the online fulfillment problem. In practice, even if the preferred (chain-connected) warehouses run out of stock, the retailer would rather incur higher shipping cost from the n − 2 non-preferred warehouses than lost sale. The authors adapt their proposed policy to account for this. Under this policy, fulfillment is made from one of the chain-connected warehouses if there is stock, and from other non-connected warehouses otherwise. Then, the relevant performance metric is the total outbound shipping cost. The authors compare the performance of their method with Acimovic and Graves (2015) and Jasin and Sinha (2015). Their numerical experiments show that their method outperforms that of Jasin and Sinha (2015) in all parameter settings and outperforms Acimovic and Graves (2015) when n is small.

Xu, Zhang, Zhang, and Zhang (2018) extend the work of Asadpour et al. (2020) and investigate online resource allocation problems involving sparsely connected networks with arbitrary numbers of resources and request types, and positive generalized capacity gaps (GCGs). The GCG concept formalizes a notion of “effective chaining” and measures the effectiveness of a given flexibility structure. It is first introduced by Shi, Wei, and Zhong (2019) when discussing the process flexibility of a multi-period make-to-order system. Xu et al. (2018) show that positive GCGs are both necessary and sufficient for sparse network structures to achieve bounded performance gap compared with full-flexibility networks.

Jehl, Shi, Wu, and Shen (2020) investigate the product placement problem for a fulfillment network with the long-chain structure. Instead of investigating inventory allocation of the fulfillment problem, the authors focus on the allocation of SKUs in different warehouses to maximize the number of orders that can be fulfilled. The authors simplify the problem by assuming that an order can be fulfilled by a warehouse if all SKUs involved in the order are placed in the warehouse, and formulate the resulting product placement problem as a mixed-integer program. The authors use a Lagrangian relaxation solution approach, and show that the Lagrangian dual function can be evaluated by solving a minimum cut problem. They also conduct numerical experiments to show that the performance of the long-chain structure achieves over half of the performance of a fully flexible network.

4.1.1 Models without contextual information

In the era of digitalization and e-retailing, inventory management is supported by the availability of high-quality data. Endowed with this richness of data, researchers begin to explore purely sample-based, data-driven approaches as an alternative to the conventional parametric approaches. We first consider approaches that do not make use of contextual information, that is, rely only on historical data on demand.

Levi et al. (2015, 2007) analyze the sample average approximation (SAA) approach for the data-driven newsvendor problem under the case where the only information available is an independent and identically distributed (i.i.d.) demand sample, . To be more specific, they consider the problem with the following formulation:

for which the solution is the b/(b + h)-quantile of the random sample, which is random due to the randomness of sample. Thus, a critical issue is to quantify and guarantee the performance of the solution , which is a function of historical data, when applied to future decisions. In general, these out-of-sample performance guarantees, also known as generalization bounds, are often achieved by proving probability bounds on expected test-set performance of the solution. Levi, Roundy, and Shmoys (2007) introduce the concept of ϵ-optimality of a solution , which suggests that its relative regret, denoted by , is no more than ϵ (where q^* is the true optimal solution, and C(⋅) denotes the expected cost under the true demand distribution). Using Hoeffding's inequality (see Hoeffding (1994) for a reference), they derive a bound on the probability that the SAA solution solved with a sample size N (denoted by ) has one-sided derivative bounded by , and use this boundedness property to prove ϵ-optimality of the solution using the piece-wise linear structure of the newsvendor cost function. In particular, Theorem 2.2 of Levi et al. (2007) shows that is ϵ-optimal with probability at least

Using Bernstein's inequality instead of Hoeffding's inequality, Levi et al. (2015) further tightened the bound to

(6)

The key difference between these two bounds is in the constants within the exponential terms, vs . For an illustration, to achieve an ϵ-optimal solution with probability 1 − 2δ with min{b,h}/(b + h) = 0.1, the bound provided in Levi et al. (2007) suggests a sample size of ; whereas the result of Levi et al. (2015) suggests . When min{b,h}/(b + h) = 0.01, the former suggests and the latter suggests . Therefore, the latter is a significant improvement when min{b,h}/(b + h) is small, which is often the case in real-world problems. Later on, Cheung and Simchi-Levi (2019) prove a lower bound on the number of samples needed for an ϵ-optimal solution that matches the upper bound (6), which implies that the upper bound is indeed tight.

Besides the improved bound based on Bernstein's inequality, the authors also introduce a property of the demand distribution known as the weighted mean spread (WMS) and show that it is the key property of a distribution that determines the accuracy of the SAA method when solving newsvendor problems. The WMS is defined as f(q^*)Δ(q^*), where f(q^*) is the probability density at q^*, and q^* is the quantile of D. The authors show that, by choosing , and biasing the SAA solution to , is ϵ-optimal with probability at least . The authors show that this bound is tighter than previously stated ones and matches the empirical accuracy of the SAA observed in many computational experiments. Although this bound is tighter, it requires extra information on the demand distribution; whereas the previously stated bound based on Bernstein's inequality only requires knowledge of the Lipschitz constant of the newsvendor cost function.

4.1.2 Models with contextual information

When contextual information is available, it is possible to improve the solution by taking into account observable contextual information in decision making. In the newsvendor problem, this involves finding the optimal mapping from observable features to ordering decision q ∈ ℝ₊ that minimizes the conditional expected cost function with respect to the distribution of the random demand D. Therefore, problem (5) would be replaced by

(7)

where q(⋅) is the policy that maps the feature space to decision space ℝ₊. Available data takes the form of a historical sample of both features and demand, denoted by .

Following a machine learning approach, one can treat the policy q(⋅) as a hypothesis, that is, a function mapping from , to be learned through a learning algorithm. A natural way to obtain such hypothesis, given sample S, is through empirical risk minimization (ERM):

(8)

where ℋ denotes the hypothesis set, that is, a set of that mapping features to the ordering decision. Often, a regularization term, for example, ‖q‖₁ or , is added to to avoid overfitting. It is interesting to note that the data-driven contextual newsvendor problem is equivalent, up to scaling, to the conditional quantile prediction problem. Therefore, multiple machine learning models, including linear regression, kernel methods as well as deep neural networks, can be applied to provide order policies (Beutel & Minner, 2012; Ban & Rudin, 2018; Cao & Shen, 2019; Huh, Levi, Rusmevichientong, & Orlin, 2011; Oroojlooyjadid, Snyder, & Takáč, 2020).

Beutel and Minner (2012) propose linear programming models to deal with the case when demand is a linear combination of some exogenous variables and a random shock. Sachs (2015) extends the Beutel and Minner (2012) study to the case where demand observations are censored. In both papers, the goal is to minimize an objective of in-sample cost, following ERM.

Ban and Rudin (2018) consider a linear hypothesis class with ERM and regularization and provide performance guarantees for these methods under certain conditions. Oroojlooyjadid et al. (2020) use deep neural networks to fit the policy map and conduct numerical experiments on real-world data. Cao and Shen (2019) use a deterministic polynomial feed-forward neural network for the newsvendor problem with stationary and non-stationary time series demand.

To get a data-driven solution for (7), Beutel and Minner (2012), Ban and Rudin (2018), Huh et al. (2011), Oroojlooyjadid et al. (2020), and Cao and Shen (2019) choose to fit a map between feature and decision using machine learning techniques, based on the idea of SAA/ERM. A different approach to tackle (7) is to approximate the conditional distribution of D | x using nonparametric methods (Ban & Rudin, 2018; Bertsimas & Kallus, 2019; Ho & Hanasusanto, 2019; Lin, Chen, Li, & Shen, 2020; Meller & Taigel, 2019). In particular, given a feature x and historical observations , machine learning methods can be utilized to assign weights w_N,i(x) for each data point (x_i, d_i) based on the similarity between x_i and x. For instance, both Ban and Rudin (2018) and Bertsimas and Kallus (2019) investigate a method motivated by kernel regression which sets the weights as

where K(⋅) is a kernel and γ > 0 is a constant known as the bandwidth. Besides using kernel regression, Bertsimas and Kallus (2019) also propose other methods for constructing weights, based on k-nearest-neighbors (KNN), local linear regression (LOESS), classification and regression trees (CART), random forests (RF), and so on.

With the weights computed, the conditional distribution of demand given feature x can be approximated by empirical distribution of weighted by w_N,i(x). Then, problem (7) can be rewritten as:

(9)

Ban and Rudin (2018) investigate the out-of-sample performance guarantee for the case where weights are generated by kernel estimation. Bertsimas and Kallus (2019) propose a more general framework that is applicable to not only the newsvendor problems, but to general convex optimization problems, and provide guarantees on consistency and generalization bounds.

The method described in (8) directly applies the supervised learning framework to obtain a mapping from features to decision. The advantage is that the mapping q(⋅) directly yields a new decision given a new set of feature values x. On the other hand, the method described in (9) approximates the conditional distribution of D with an empirical distribution with weights dependent on feature values. Given a feature vector x, one has to first obtain the weights w_N,i(x) by inputting x into a nonparametric model (e.g., the kernel regression model), and then solve an (convex) optimization problem to obtain a decision q. Thus the former approach has an advantage in terms of computational effort. Yet, (9) enjoys another significant advantage in that it is able to accommodate side constraints on decision q. Such constraints may come from business and operational requirements, such as capacity, minimum order quantity, and so on. To accommodate such constraints (denoted by ), one simply needs to solve for

instead of (9).

Other works that adopt similar settings include Meller and Taigel (2019), Ho and Hanasusanto (2019), Lin et al. (2020). Meller and Taigel (2019) propose to use the quantile loss function when learning the tree structure for the weights and compare the joint estimation-optimization method with traditional separated estimation and optimization methods. Ho and Hanasusanto (2019) propose a kernel-based approach with regularization and provide performance guarantees. Lin et al. (2020) investigate a risk-averse newsvendor problem subject to a value-at-risk constraint.

4.2.1 Models without contextual observation

As with single-period models, we first discuss studies without considering the availability of contextual information. While the multi-period inventory management problem is difficult in general, under certain conditions, it is well-known that the optimal policy takes the form of base-stock policy, when there is no fixed order cost, or (s,S) policy, when there is a fixed order cost (see Snyder and Shen (2011), for details). Therefore, various data-driven algorithms have been proposed to seek data-driven decisions restricted to one of these policies. Kunnumkal and Topaloglu (2008) consider settings where base-stock policies are known to be optimal and propose stochastic approximation methods to compute the optimal base-stock levels. Given samples of demand, they show that their method will converge to the optimal base-stock levels. Ban (2020) develops a nonparametric procedure to estimate the (s,S) policy when given historical demand data. The cost at each period consists of ordering cost in the form:

in addition to the newsvendor cost function C_t(q,d) ≔ b_t(d − q)⁺ + h_t(q − d)⁺. The available demand data consists of observations for N previous selling seasons, each with T periods. Demand in each period is assumed to fall within support . Then, the optimal are estimated by , where:

and

where and

and α_t denotes the discount rate of cash. The author then shows that these proposed estimators are asymptotically consistent, that is, and converge to the optimal values s_t and S_t as t → ∞. The author also provides confidence intervals by first proving the central limit theorem for with the property of “M-estimators.” Then, confidence intervals can be constructed based on asymptotic normality. The author also extends the method to the case of censored demand.

Some other works focus on the SAA method. Levi et al. (2007) study the multiperiod extension of Newsvendor problem (i.e., without fixed ordering costs), where the optimal policy is the base-stock policy. Similar to the single-period Newsvendor setting, the authors describe a sampling-based algorithm that provides 1 + ϵ-base-stock level with any given confidence level δ. Cheung and Simchi-Levi (2019) then consider the multi-period inventory management problem with a constraint on the order quantity in each period. The authors investigate the minimum number of samples required by the SAA method to achieve a near-optimal base-stock policy with any given confidence level. In particular, it is sufficient for the SAA method to achieve near-optimal solution with polynomially many (w.r.t. T and ϵ) samples.

Another stream of research seeks to learn the inventory management policy in an adaptive manner. Huh and Rusmevichientong (2009) investigate the multi-period inventory management problem over a fixed horizon, assuming demand in each period are i.i.d. random variable. The authors consider the case with instantaneous replenishment (zero lead time), and develop an adaptive inventory policy ϕ = (q_t| t ≥ 1) where each q_t only depends on the observed historical sales during the previous t − 1 periods. To quantify the performance of their policy, the authors use the newsvendor optimal order quantity as a benchmark. The policy ϕ is optimized to minimize average expected regret:

where V(q_t) is the single-period newsvendor cost function with order quantity q_t, and is the optimal Newsvendor quantity. By proposing gradient descent based algorithms, the authors provide a policy achieving the average expected regret .

Huh, Janakiraman, Muckstadt, and Rusmevichientong (2009) propose algorithms for finding the optimal order-up-to levels in lost-sales inventory systems with deterministic, positive lead time. They prove that the T-period running average expected cost under their algorithm converges to the cost of the best base-stock policy with a convergence rate . Later, Zhang, Chao, and Shi (2020) close the gap between upper and lower bounds of the regret by providing an algorithm that achieves regret that matches the theoretical lower bound. Agrawal and Jia (2019) further provide an upper bound of the regret that depends linearly on the lead time L. This result improves the bound provided in Zhang et al. (2020) that depends exponentially on the lead time L. Huh et al. (2011) apply the Kaplan-Meier estimator to develop nonparametric adaptive data-driven policies for the multiperiod distribution-free newsvendor problem with censored demand. Later, Shi, Chen, and Duenyas (2016) propose a data-driven, stochastic gradient descent type algorithm for solving the periodic review multi-product inventory management problem over a finite horizon, under capacity constraints. They show that the average regret converges to zero at the rate of .

4.2.2 Models with contextual observation

Bertsimas and McCord (2019) extend the prescriptive learning framework to solve finite-horizon multi-period optimization problems, including the inventory management problem. For a T-period problem, let z_t denote the key uncertain factors (e.g., demand) and x_t denote the feature values that can be used to guide decision y_t (e.g., order quantity). Bertsimas and McCord (2019) consider the presence of a sample of N observations, each containing the values of (x_t, z_t) for all periods t = 1, …T. They consider the setting where uncertainty z_t (e.g., demand) is revealed prior to the decision and system update at time t. Therefore, without loss of generality, the cost and transition function can be represented as C_t(y_t) and f_t(y_t) that only depend on the decision variable y_t. They consider the following problem:

(10)

where denotes the feasible region of decision variable y_t in period t, which may depend on state variable I_t (such as the inventory level) and the realization of z_t, and W_t denotes the cost-to-go function defined recursively as:

for t = 1, …, T − 1 and .

With training data , weights are learned and the recursion of W_t can be approximated by approximating the conditional expectation by:

From the perspective of computational tractability, this method still requires solving a dynamic programming problem (10), which requires exact or approximate solution techniques. Note that (10) is no more difficult to solve, yet often leads to significant improvements, compared with sample average approaches that ignore covariates.

Qi et al. (2020) propose a practical framework that builds upon supervised machine learning. The authors investigate the multi-period inventory replenishment problem with uncertain demand and vendor lead time (VLT), assuming that a large quantity of historical data is available. In their setting, the planning horizon consists of periods t = 1, …, T. The demand sequence {D₁, …, D_T} is uncertain. The planner may place orders in M pre-specified periods, denoted by {t₁, …, t_M}. Such a setting can arise in scenarios such as the periodic review. For each order m ∈ {1, …, M}, the VLT L_m is a random variable. The problem involves selecting order quantities a₁, …, a_M for the M orders, to minimize the expected cost during the planning horizon, that is

(11)

where S_t(⋅) is single period cost function defined as

and the updates of inventory level I_t follows

Note that the expectation is taken over the joint distribution of the demand and the VLTs .

Qi et al. (2020) propose a one-step end-to-end (E2E) framework that uses deep-learning models to output replenishment quantities directly from input features without any intermediate steps. To apply deep learning methods, it is necessary to construct a training data set consisting of paired features and label values. As the available data consists of historical observations of demand, VLT, and contextual information, the label, that is, the target decision variables, are not directly known. The ideal target decision would be the optimal solution of the stochastic multi-stage optimization problem (11). However, this is not an option since the joint distribution of multi-period demand and VLTs is unknown. To overcome this difficulty, the training dataset is labeled with the optimal dynamic programming solutions under observed trajectories.

To be more specific, each observation in the data corresponds to a T-period episode during which M orders were placed. Let τ_m denote the period in which the m-th order arrived, that is, the VLT was τ_m − t_m, and let d_[s,t] denote the total realized demand in the time [s,t]. Then, the authors solve the following (deterministic) problem for each observation:

where is the optimal cost overtime interval [τ_m, τ_m + 1 − 1], . The authors show that this problem admits a closed-form solution , where . Therefore, labeling observations with serves as an efficient method even with enormous data.

Then, a multi-quantile recurrent neural network (MQRNN) is trained with the training objective:

where N is the total number of training data, L is the loss function that is defined based on the difference between the output of function f(⋅) and the optimal order quantity . By conducting a series of thorough numerical experiments including a field experiment from a leading e-commerce company, the authors demonstrate the numerical advantages of the proposed framework.

It is interesting to note that, thus far, much of the success of data-driven research in retail operations stems from the availability and clever use of demand-side data, such as contextual information that influences demand and sales. Qi et al. (2020) provide an interesting example of incorporating both demand- and supply-side data (on VLT) in an E2E framework. We believe the integrated use of data from both ends of the supply chain is a promising direction for future research.