Will Ma

This paper shows how policy regularizations grounded in classical inventory concepts improve the performance of deep reinforcement learning while reducing hyperparameter tuning effort. Extensive synthetic experiments and deployment on Alibaba’s Tmall platform demonstrate the practical value of incorporating inventory structure into reinforcement learning.

The design of online algorithms for matching markets and revenue management settings is usually bound by the assumption that the demand process is formed by a fixed-length sequence of queries with unknown types, each drawn independently. This notion of serial independence implies that the demand of each type, that is, the number of queries of a given type, has low variance and is approximately Poisson distributed. This paper proposes a nonparametric framework for modeling arrival sequences in online stochastic matching that departs from the serial independent assumption. We propose two models, Indep and Correl, that capture different forms of serial correlations by combining a nonparametric distribution for the demand with standard assumptions on the arrival patterns: adversarial or random order. The Indep model can capture arbitrary serial correlations within each customer type but assumes cross-sectional independence across types, whereas the Correl model captures common shocks across customer types. We demonstrate that fluid relaxations, which rely solely on demand expectations, have arbitrarily bad performance guarantees. In contrast, we develop new algorithms that achieve optimal (constant factor) performance guarantees in each model. Our mathematical analysis includes tighter linear programming (LP) relaxations that leverage distribution knowledge and a new lossless randomized LP rounding scheme for Indep. We test our new LP relaxations and rounding scheme in simulations on real and synthetic data and find that they consistently outperform well-established matching algorithms, especially on real data sequences that exhibit greater demand variance. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2024.05424 .

Problem definition: We study the inventory placement problem of splitting [Formula: see text] units of a single item across warehouses in advance of a downstream online matching problem that represents the dynamic fulfillment decisions of an e-commerce retailer. This is a challenging problem both theoretically, due to the computational complexity of the downstream matching problem, and practically, as the fulfillment team continuously updates its algorithm while the placement team lacks direct evaluation of placement decisions. Methodology/results: We compare the performance of three placement procedures based on optimizing surrogate functions that have been studied and applied: Offline, Myopic, and Fluid placement. On the theory side, we show that optimizing inventory placement for the Offline surrogate leads to an [Formula: see text]-approximation for the joint placement and fulfillment problem under any demand model that admits an [Formula: see text]-competitive fulfillment policy. We assume [Formula: see text] is an upper bound on how many warehouses can serve any demand location. The crux of our theoretical contribution is to use randomized rounding to derive a tight [Formula: see text]-approximation for the integer programming problem of optimizing the Offline surrogate. We further show how to extend this result to a multi-SKU setting, improving upon the best known approximation of [Formula: see text]. We use statistical learning to show that rounding after optimizing a sample-average Offline surrogate, which is necessary due to the exponentially-sized support, indeed has vanishing loss. On the experimental side, we evaluate how different combinations of placement and fulfillment procedures perform on a wide array of synthetic instances. When coupled with a good fulfillment procedure, optimizing the Offline surrogate performs best even compared to computationally-intensive simulation procedures, corroborating our theory. Managerial implications: Theoretical guarantees and extensive numerics both suggest that the placement team should optimize the (optimistic) Offline surrogate, assuming the fulfillment team has a good algorithm. Otherwise, the placement team could optimize the (pessimistic) Myopic surrogate instead.

We study a wholesale supply chain ordering problem. In this problem, the supplier has an initial stock and faces an unpredictable stream of incoming orders, making real-time decisions on whether to accept or reject each order. What makes this wholesale supply chain ordering problem special is its knapsack constraint; that is, we do not allow partially accepting an order or splitting an order. The objective is to maximize the utilized stock. We model this wholesale supply chain ordering problem as an online unit-density knapsack problem. We study randomized threshold algorithms that accept an item as long as its size exceeds the threshold. We derive two optimal threshold distributions, the first is 0.4324-competitive relative to the optimal off-line integral packing, and the second is 0.4285-competitive relative to the optimal off-line fractional packing. Both results require optimizing the cumulative distribution function of the random threshold, which are challenging infinite-dimensional optimization problems. We also consider the generalization to multiple knapsacks, in which an arriving item has a different size in each knapsack. We derive a 0.2142-competitive algorithm for this problem. We also show that any randomized algorithm for this problem cannot be more than 0.4605-competitive. This is the first upper bound strictly less than 0.5, which implies the intrinsic challenge of the knapsack constraint. We show how to naturally implement our optimal threshold distributions in the warehouses of a Latin American chain department store. We run simulations on its order data that demonstrate the efficacy of our proposed algorithms. This paper was accepted by George Shanthikumar, data science. Funding: This work was supported by the Massachusetts Institute of Technology–Accenture Alliance for Business Analytics. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.01577 .

In this work, we study how the relevance/quality and quantity of past data influence performance by analyzing a contextual Newsvendor problem, in which a decision maker trades off between underage and overage costs under uncertain demand. We consider a setting in which past demands observed under “close-by” contexts come from close-by distributions and analyze the performance of data-driven algorithms through a notion of context-dependent worst-case expected regret. We analyze the broad class of Weighted Empirical Risk Minimization (WERM) policies which weigh past data according to their similarity in the contextual space. This class includes classical policies such as ERM, k-Nearest Neighbors, and kernel-based policies. Our main methodological contribution is to characterize exactly the worst-case regret of any WERM policy on any given configuration of contexts. To the best of our knowledge, this provides the first understanding of tight performance guarantees in any contextual decision-making problem, with past literature focusing on upper bounds via concentration inequalities. We instead take an optimization approach, and isolate a structure in the Newsvendor loss function that allows us to reduce the infinite-dimensional optimization problem over worst-case distributions to a simple line search. This in turn allows us to unveil fundamental insights that were obfuscated by previous general-purpose bounds. We characterize actual guaranteed performance as a function of the contexts, as well as granular insights on the learning curve of algorithms. This paper was accepted by Victor Martínez de Albéniz, operations management. Funding: This work was supported by the Deming Center for Operations Innovation and Excellence at Columbia Business School [Doctoral Fellowship (O. Mouchtaki)]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.02068 .

Two Prices Unlock Big Gains for Reusable Resources How much sophistication is needed to price reusable resources, like hotel rooms and cloud computing, when usage durations are not memoryless? Surprisingly little. In “Dynamic Pricing for Reusable Resources: The Power of Two Prices,” Balseiro, Ma, and Zhang propose a class of dynamic stock-dependent policies that achieve significant improvements over static pricing by only looking at how many units are busy and ignoring how long they have been busy. Using an “insensitivity” property of loss networks, they show that optimizing within this policy class can be formulated as a tractable convex optimization problem. Better yet, the performance loss of the optimal stock-dependent policy can be achieved by a simple two-price policy: charge a high price when inventory falls below a threshold and a low price otherwise. Extensions to multiple resources and customer classes, together with extensive simulations, confirm that “just a little” dynamicity can go a long way.

Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some “ingenuity.” In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds separately. Our analysis of this optimization problem involves identifying structure in a new “Type Coverage” dual problem. It can be seen as akin to the celebrated Magician and OCRS (Online Contention Resolution Scheme) problems, except more general, in that it can also provide tight ratios relative to the optimal offline allocation, whereas the earlier problems only establish tight ratios relative to the ex ante relaxation of the offline problem. Through this analysis, our paper provides a unified framework that derives new prophet inequalities and recovers existing ones, with our principal results being twofold. First, we show that the “oblivious” method of setting a static threshold due to Chawla et al., surprisingly, is best-possible among all static threshold algorithms, under any number k of selection slots. We emphasize that this result is derived without needing to explicitly find any counterexample instances. This implies the tightness of the asymptotic convergence rate of [ ] for static threshold algorithms from Hajiaghayi et al. Turning to the independent and identically distributed setting, our second principal result is to use our framework to characterize the tight guarantee (of adaptive algorithms) under any number k of selection slots and any fixed number of agents n.

Real-time decisions are usually irrevocable in many contexts of online decision making. One common practice is delaying real-time decisions so that the decision maker can gather more information to make better decisions. For example, in online retailing, there is typically a time delay between when an online order is received and when it gets picked and assembled for shipping. However, decisions cannot be delayed forever. In this paper, we study this fundamental trade-off and aim to theoretically characterize the benefits of delaying real-time decisions. We provide a theoretical foundation for a broad family of online decision-making problems by proving that the gap between our proposed online algorithm (called “delayed Bayesian prophet”) and the offline optimal hindsight policy decays exponentially fast in the length of delay. We also conduct extensive numerical experiments on the benefits of delay, using both synthetic data and publicly available real data. Both our theoretical and empirical results demonstrate an important managerial insight: a little delay is all we need. Finally, we extend our analysis and results to the setting where the arrival distribution is independent but nonidentical, the setting where the arrival distribution is unknown, and the setting where decisions are made in batches. This paper was accepted by Jeannette Song, operations management. Funding: The second author was partially funded by a grant from Amazon.com Inc., awarded through collaboration with the Columbia Center of AI Technology. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.00549 .