Near-Optimal Bisection Search for Nonparametric Dynamic Pricing with Inventory Constraint

We consider a single-product revenue management problem with an inventory constraint and unknown, noisy, demand function. The objective of the firm is to dynamically adjust the prices to maximize total expected revenue. We restrict our scope to the nonparametric approach where we only assume some common regularity conditions on the demand function instead of a specific functional form. We propose a family of novel pricing heuristics that successfully balance the tradeoff between exploration and exploitation. The idea is to generalize the classic bisection search method to a problem that is affected both by stochastic noise and an inventory constraint. Our algorithm extends the bisection method to produce a sequence of pricing intervals that converge to the optimal static price with high probability. Using regret (the relative revenue loss compared to the optimal dynamic pricing solution for a clairvoyant) as the performance metric, we show that one of our heuristics exactly matches the theoretical asymptotic lower bound that has been previously shown to hold for any feasible pricing heuristic. Although the results are presented in the context of revenue management problems, our analysis of the bisection technique for stochastic optimization with learning can be potentially applied to other application areas