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