Contextual Dynamic Pricing with Unknown Noise: Explore-then-UCB Strategy and Improved Regrets

Dynamic pricing is a fast-moving research area in machine learning and operations management. A lot of work has been done for this problem with known noise. In this paper, we consider a contextual dynamic pricing problem under a linear customer valuation model with an unknown market noise distribution F . This problem is very challenging due to the difficulty in balancing three tangled tasks of revenue-maximization, estimating the linear valuation parameter θ 0 , and learning the nonparametric F . To address this issue, we develop a novel Explore-then-UCB (ExUCB) strategy that includes an exploration for θ 0 -learning and a followed UCB procedure of joint revenue-maximization and F -learning. Under Lipschitz and 2nd-order smoothness assumptions on F , ExUCB is the first approach to achieve the ˜ O ( T 2 / 3 ) regret rate. Under the Lipschitz assumption only, ExUCB matches the best existing regret of ˜ O ( T 3 / 4 ) and is computationally more efficient. Furthermore, for regret lower bounds under the nonparametric F , not much work has been done beyond only assuming Lipschitz. To fill this gap, we provide the first ˜Ω( T 3 / 5 ) lower bound under Lipschitz and 2nd-order smoothness assumptions.