Dynamic Pricing with Monotonicity Constraint under Unknown Parametric Demand Model

We consider a Continuum-Armed Bandit problem with an additional monotonicity constraint (or “markdown” constraint) on the actions selected. This problem faith-fully models a natural revenue management problem, called “markdown pricing”, where the objective is to adaptively reduce the price over a finite horizon to maximize the expected revenues. Chen ([3]) and Jia et al ([9]) recently showed a tight T 3 / 4 regret bound over T rounds under minimal assumptions of unimodality and Lipschitzness in the reward function. This bound shows that markdown pricing is strictly harder than unconstrained dynamic pricing (i.e., without the monotonicity constraint), which admits T 2 / 3 regret under the same assumptions ([11]). However, in practice, demand functions are usually assumed to have certain functional forms (e.g. linear or exponential), rendering the demand learning easier and suggesting better regret bounds. In this work we introduce a concept, markdown dimension , that measures the complexity of a parametric family, and present optimal regret bounds that improve upon the previous T 3 / 4 bound under this framework.