Contextual Pricing for Lipschitz Buyers

We investigate the problem of learning a Lipschitz function from binary feedback. In this problem, a learner is trying to learn a Lipschitz function f : [0, 1] d → [0, 1] over the course of T rounds. On round t, an adversary provides the learner with an input x t , the learner submits a guess y t for f (x t ), and learns whether P y t > f (x t ) or y t ≤ f (x t ). The learner’s goal is to minimize their total loss t (f (x t ), y t ) (for some loss function). The problem is motivated by contextual dynamic pric- ing, where a firm must sell a stream of differentiated products to a collection of buyers with non-linear valuations for the items and observes only whether the item was sold or not at the posted price. For the symmetric loss (f (x t ), y t ) = |f (x t ) − y t |, we provide an algorithm for (d−1)/d this problem achieving total loss O(log T ) when d = 1 and O(T ) when √ d > 1, and show that both bounds are tight (up to a factor of log T ). For the pricing loss function(f (x t ), y t ) = f (x t ) − y t 1{y t ≤ f (x t )} we show a regret bound of O(T d/(d+1) ) and show that this bound is tight. We present improved bounds in the special case of a population of linear buyers