Contextual Search in the Presence of Adversarial Corruptions

Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, Robert Schapire

Research output: Contribution to journalArticlepeer-review

Abstract

We study contextual search, 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 responsemodel being (approximately) accurate for all agents and have poor performance in the presence of even a few such arbitrary misspecifications.We initiate the study of contextual search when some of the agents can behave in ways inconsistent with the underlying response model. In particular, we provide two algorithms, one based on multidimensional binary search methods and one based on gradient descent. We show that these algorithms attain near-optimal regret in the absence of adversarial corruptions and their performance degrades gracefully with the number of such agents, providing the first results for contextual search in any adversarial noise model. Our techniques draw inspiration from learning theory, game theory, highdimensional geometry, and convex analysis.

Original languageEnglish (US)
Pages (from-to)1120-1135
Number of pages16
JournalOperations Research
Volume71
Issue number4
DOIs
StatePublished - Jul 1 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • contextual online decision making
  • dynamic pricing
  • learning from revealed preferences

Fingerprint

Dive into the research topics of 'Contextual Search in the Presence of Adversarial Corruptions'. Together they form a unique fingerprint.

Cite this