Robust Contextual Pricing

We provide an algorithm with regret $O(Cd\log \log T)$ for contextual pricing with $C$ corrupted rounds, improving over the previous bound of $O(d^{3}C{\log }^2(T))$ of Krishnamurthy et al. The result is based on a reduction that calls the uncorrupted algorithm as a black-box, unlike the previous approach that modifies the inner workings of the uncorrupted algorithm. As a result, it leads to a conceptually simpler algorithm.

Finally, we provide a lower bound ruling out a $O(C+d\log \log T)$ algorithm. This shows that robustifying contextual pricing is harder than robustifying contextual search with $ϵ$-ball losses, for which it is possible to design algorithms where corruptions add only an extra additive term $C$ to the regret.