Contextual Search in the Presence of Adversarial Corruptions
研究了情境搜索在部分用户响应被对抗性破坏时的鲁棒算法，在无异常时性能接近最优，且随异常数量增加性能平缓下降。
Contextual search is a generalization of binary search, which captures settings such as feature-based dynamic pricing. In this paradigm, a decision maker repeatedly interacts with a set of agents; in the pricing example, the decision maker first observes the context/ features of an item, then sets a feature-dependent price, and the agent responds by either buying or not. 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 (e.g., when some agents exhibit outlier behavior). 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 outliers. We initiate the study of contextual search in the presence of such adversarial corruptions. Our algorithms’ performance is near-optimal in the absence of outliers and degrades gracefully with their number.