- Jieming Mao
- Jon Schneider
- Renato Paes Leme
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 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
Research Areas
Learn more about how we do research
We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work