Abstract
Contextual search is a generalization of binary search in higher dimensions, which captures settings such as feature-based dynamic pricing. Standard formulations of this problem assume that agents act in accordance with a specific homogeneous response model. In practice, however, some responses may be adversarially corrupted. Existing algorithms heavily depend on the assumed response model being (approximately) accurate for all agents and have poor performance in the presence of even a few such arbitrary misspecifications. In the corruption-robust version of the problem, we wish to model misspecifications as corruptions and create algorithms that scale nearly optimally both when corruptions are present and when they are not.
This talk will cover the original formulation of the problem as proposed by Krishnamurthy, Lykouris, Podimata, and Schapire in STOC21/OR22 and the nearly optimal algorithms attained by Paes Leme, Podimata, and Schneider in COLT22.