Abstract: Motivated by a long-standing gap between inventory theory and practice, we study online inventory models with unknown cyclic demand distributions. We design provably efficient reinforcement learning (RL) algorithms that leverage the structure of inventory problems. We apply the standard performance measure in online learning literature, regret, which is defined as the difference between the total expected cost of our policy and the total expected cost of the clairvoyant optimal policy that has full knowledge of the demand distributions a priori. This paper analyzes, in the presence of cyclic demands, the lost-sales model with zero lead time, and the multi-product backlogging model with positive lead times, fixed joint-ordering costs and order limits. For both models, we first introduce episodic models where inventory is discarded at the end of every cycle, and then build upon these models to analyze non-discarding models. Our RL policies HQL and FQL achieve ~O(T^(1/2)) regret for the episodic lost-sales model and the episodic multi-product backlogging model, matching the regret lower bound that we prove in this paper. For the non-discarding models, we construct a bandit learning algorithm on top of the previous RL algorithms, named Meta-HQL. Meta-HQL achieves ~O(T^(1/2)) regret for the non-discarding lost-sales model with zero lead time, again matching the regret lower bound. For the non-discarding multi-product backlogging model, our policy Mimic-QL achieves ~O(T^(5/6)) regret bound. Our policies has no regret dependence on the cardinality of the state-action space for inventory problems, which is a significant improvement over existing RL algorithms. We conducted experiments with a real sales dataset from Rossmann, one of the largest drugstore chains in Europe, and also with a synthetic dataset. For both sets of experiments, our policy converges rapidly to the optimal policy and dramatically outperforms the best policy that models demand as i.i.d. instead of cyclic.
Most recent version of the paper: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3637705
Bio: Xiao-Yue Gong is a 5th-year Ph.D. student at the MIT Operations Research Center. She is co-advised by Professors David Simchi-Levi and James Orlin. Her current research interests lie broadly in online algorithms, reinforcement learning, data-driven revenue management and supply chain optimization. Prior to MIT, Xiao-Yue received two bachelor degrees with summa cum laude in Honors Mathematics and Interactive Media Arts from New York University (New York & Shanghai campuses) in 2017.