Abstract

 We investigate the problem of learning a Lipschitz function from binary feedback. In this problem, a learner is trying to learn a Lipschitz function over the course of T rounds. On round t, an adversary provides the learner with an input , the learner submits a guess yt for f ( ), and learns whether P or . The learner’s goal is to minimize their total loss (for some loss function). The problem is motivated by contextual dynamic pricing, 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 , we provide an algorithm for  this problem achieving total loss when d > 1, and show that both bounds are tight (up to a factor of . For the pricing loss function we show a regret bound of and show that this bound is tight. We present improved bounds in the special case of a population of linear buyers.