NIPS 2018
Sun Dec 2nd through Sat the 8th, 2018 at Palais des Congrès de Montréal
Paper ID: 2713 Contextual Pricing for Lipschitz Buyers

### Reviewer 1

This submission is pretty out of my expertise. I just carefully read the intro part and find it is well written and very clear.

### Reviewer 2

This paper studies the problem of learning a Lipschitz function $f(x)$ from binary feedback. Two types of loss are considered, the symmetric ell-1 loss and the unsymmetric and discontinuous pricing loss. To minimize the losses, four algorithms are proposed. Alg. 1 maintains a set $S = { (X_j, Y_j) }$, where $X_j$ is a partition interval of feasible set $[0,1]$ and $Y_j$ contains the lower and upper bounds of $f(x)$. At each iteration, an adversary queries a point $x_t$. The learner response with estimate $y = mid(Y_j)$, where $X_j$ is the interval containing $x_t$. Base on the feedback, the learner shrinks $Y_j$ by intersecting itself with a set derived from Lipschitz property of $f(x)$. The iteration is finalized by splitting $X_j$ into two new intervals when the length of $Y_j$ can hardly be reduced. Alg. 2 encodes the upper bound and lower bound of $f(x)$ in sets $S+$ and $S-$ respectively. At each iteration, the learner receives a query $x_t$, composing an interval containing $f(x_t)$ by solving a linear optimization constrained on $S+$ and $S-$. And it uses the mid-point of the interval as the current guess. The $S+$ and $S-$ are updated based on the binary feedback. Alg. 3 and Alg. 4 are extensions of Alg. 1 to the case of multi-dimensional Lipschitz functions. The author proves that Alg. 3 and Alg. 4 can learn $f(x)$ with sublinear regret for the ell-1 loss and the pricing loss respectively. The two algorithm are optimal by giving the lower bound of Lipschitz learning problem. The problem is similar to learning a Lipchitz function from binary feedback with ell-1 loss and pricing loss by showing the optimality of their methods. The following questions need to be clarified. 1) All the proposed algorithms depend on the Lipschitz constant $L$. However, in practice, $L$ may not be satisfied. How to adapt the proposed methods when the condition is not meet ? 2) Alg. 2 only supports the one-dimensional learning problem. How to extend it to the multi-dimension learning problem ? 3) No empirical studies are performed. Though the author argues that the model can be used in dynamic pricing problem, no empirical evidence validates the performance.