Online Learning and Optimization of (Some) Cyclic Pricing Policies in the Presence of Patient Customers

Problem definition : We consider the problem of joint learning and optimization of cyclic pricing policies in the presence of patient customers. In our problem, some customers are patient, and they are willing to wait in the system for several periods to make a purchase until the price is lower than their valuation. The seller does not know the joint distribution of customers’ valuation and patience level a priori and can only learn this from the realized total sales in every period. Academic/practical relevance : The revenue management problem with patient customers has been studied in the literature as an optimization problem, and cyclic policy has been shown to be optimal in some cases. We contribute to the literature by studying this problem from the joint learning and optimization perspective. Indeed, to the best of our knowledge, our paper is the first work that studies online learning and optimization for multiperiod pricing with patient customers. Methodology : We introduce new dynamic programming formulations for this problem, and we develop two nontrivial upper confidence bound–based learning algorithms. Results : We analyze both decreasing cyclic policies and so-called threshold-regulated policies, which contain both the decreasing cyclic policies and the nested decreasing cyclic policies. We show that our learning algorithms for these policies converge to the optimal clairvoyant decreasing cyclic policy and threshold-regulated policy at a near-optimal rate. Managerial implications : Our proposed algorithms perform significantly better than benchmark algorithms that either ignore the patient customer characteristic or simply use the standard estimate-then-optimize framework, which does not encourage enough exploration; this highlights the importance of “smart learning” in the context of data-driven decision making. In addition, our numerical results also show that combining our algorithms with smart estimation methods, such as linear interpolation or least square estimation, can significantly improve their empirical performance; this highlights the benefit of combining smart learning with smart estimation, which further increases the practical viability of the algorithms.