Timezone: »
Poster
Contextual Pricing for Lipschitz Buyers
Jieming Mao · Renato Leme · Jon Schneider
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 \rightarrow [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 $y_t > f(x_t)$ or $y_t \leq
f(x_t)$. The learner's goal is to minimize their total loss $\sum_t\ell(f(x_t),
y_t)$ (for some loss function $\ell$). The problem is motivated by \textit{contextual dynamic pricing},
where a firm must sell a stream of differentiated products to a collection of
buyers with nonlinear valuations for the items and observes only whether the
item was sold or not at the posted price.
For the symmetric loss $\ell(f(x_t), y_t) = \vert f(x_t)  y_t \vert$, we
provide an algorithm for this problem achieving total loss $O(\log T)$
when $d=1$ and $O(T^{(d1)/d})$ when $d>1$, and show that both bounds are
tight (up to a factor of $\sqrt{\log T}$). For the pricing loss function
$\ell(f(x_t), y_t) = f(x_t)  y_t {\bf 1}\{y_t \leq 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.
Author Information
Jieming Mao (Princeton University)
Renato Leme (Google Research)
Jon Schneider (Google)
More from the Same Authors

2021 Poster: Contextual Recommendations and LowRegret CuttingPlane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider 
2020 Poster: Myersonian Regression »
Allen Liu · Renato Leme · Jon Schneider 
2019 Poster: Secretary Ranking with Minimal Inversions »
Sepehr Assadi · Eric Balkanski · Renato Leme 
2017 Poster: Dynamic Revenue Sharing »
Santiago Balseiro · Max Lin · Vahab Mirrokni · Renato Leme · IIIS Song Zuo