Optimal Contextual Pricing and Extensions
  In the contextual pricing problem a seller repeatedly obtains products
described by an adversarially chosen feature vector in $\mathbb{R}^d$ and only
observes the purchasing decisions of a buyer with a fixed but unknown linear
valuation over the products. The regret measures the difference between the
revenue the seller could have obtained knowing the buyer valuation and what can
be obtained by the learning algorithm.
  We give a poly-time algorithm for contextual pricing with $O(d \log \log T +
d \log d)$ regret which matches the $\Omega(d \log \log T)$ lower bound up to
the $d \log d$ additive factor. If we replace pricing loss by the symmetric
loss, we obtain an algorithm with nearly optimal regret of $O(d \log d)$
matching the $\Omega(d)$ lower bound up to $\log d$. These algorithms are based
on a novel technique of bounding the value of the Steiner polynomial of a
convex region at various scales. The Steiner polynomial is a degree $d$
polynomial with intrinsic volumes as the coefficients.
  We also study a generalized version of contextual search where the hidden
linear function over the Euclidean space is replaced by a hidden function $f :
\mathcal{X} \rightarrow \mathcal{Y}$ in a certain hypothesis class
$\mathcal{H}$. We provide a generic algorithm with $O(d^2)$ regret where $d$ is
the covering dimension of this class. This leads in particular to a
$\tilde{O}(s^2)$ regret algorithm for linear contextual search if the linear
function is guaranteed to be $s$-sparse. Finally we also extend our results to
the noisy feedback model, where each round our feedback is flipped with a fixed
probability $p < 1/2$.
