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. (2020). The result is based on a reduction that calls the uncor-rupted 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.