Robust Contextual Pricing

We provide an algorithm with regret O(CdloglogT) for contextual pricing with C corrupted rounds, improving over the previous bound of O(d3Clog2(T)) of Krishnamurthy et al. (2020). 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 +dloglogT)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.