Robust Contextual Pricing
Anupam Gupta, Guru Guruganesh, Renato Paes Leme, Jon Schneider
Abstract
We provide an algorithm with regret $O(C d \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 $\epsilon$-ball losses, for which it is possible to design algorithms where corruptions add only an extra additive term $C$ to the regret.
BibTeX
@inproceedings{
gupta2025robust,
title={Robust Contextual Pricing},
author={Anupam Gupta and Guru Guruganesh and Renato Paes Leme and Jon Schneider},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=eHm1EdLypn}
}