Online Learning and Matching for Multiproduct Systems with General Upgrading

We consider the joint optimization of ordering and upgrading decisions in a dynamic multiproduct system over a finite time horizon of $T$ periods. Multiple classes of demand arrive in each period stochastically following stationary distributions. Demand can be satisfied with supply of the same or higher class but generates the same revenue. In this paper, we assume the firm does not know the demand distributions a priori and makes adaptive inventory replenishment and upgrading decisions based on the historical demand observations. We first characterize the structure of the clairvoyant optimal joint ordering and allocation policy, had the demand distributions been known to the firm. The optimal ordering decision is a quantile solution, whereas the optimal allocation decision is based on a ranked list of demand and supply pairs. When the demand distributions are unknown, based on the structure of optimal policies, we propose an online learning algorithm, termed perturbed sample average approximation (PSAA for short), and prove that the algorithm admits a cumulative regret upper bound of $O(\sqrt{T\log T})$, which matches the lower bound for any learning algorithms, up to a logarithmic factor. The novelties lie in two aspects: (a) We introduce a perturbed quantile approach to buffer for estimation errors, thereby ensuring that the estimated quantile does not overshoot the optimal target with high probability. (b) We keep track of the real-time imbalance between supply and demand to carry out the allocation decisions. We also extend the model to a nested censored demand scenario and propose another stochastic gradient descent based algorithm (GRAD for short). We demonstrate the efficacy of the proposed algorithms in numerical experiments