Technical note: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand |
| |
| Authors: | L Jeff
Hong Chenghuai Li Jun Luo |
| |
| Institution: | 1. School of Management and School of Data Science, Fudan University, Shanghai, China;2. School of Mathematical Sciences and School of Data Science, Fudan University, Shanghai, China;3. Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai, China |
| |
| Abstract: | We consider the problem of nonparametric multi-product dynamic pricing with unknown demand and show that the problem may be formulated as an online model-free stochastic program, which can be solved by the classical Kiefer-Wolfowitz stochastic approximation (KWSA) algorithm. We prove that the expected cumulative regret of the KWSA algorithm is bounded above by  where κ1, κ2 are positive constants and T is the number of periods for any T = 1, 2, … . Therefore, the regret of the KWSA algorithm grows in the order of  , which achieves the lower bounds known for parametric dynamic pricing problems and shows that the nonparametric problems are not necessarily more difficult to solve than the parametric ones. Numerical experiments further demonstrate the effectiveness and efficiency of our proposed KW pricing policy by comparing with some pricing policies in the literature. |
| |
| Keywords: | dynamic pricing and learning Kiefer-Wolfowitz algorithm nonparametric pricing policy revenue management stochastic approximation |
|
|
