Contextual Search in the Presence of Adversarial Corruptions

Akshay Krishnamurthy (), Thodoris Lykouris (), Chara Podimata () and Robert Schapire ()
Additional contact information
Akshay Krishnamurthy: Microsoft Research, New York, New York 10012
Thodoris Lykouris: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Chara Podimata: School of Engineering and Applied Sciences, UC Berkeley, Berkeley, California 94720
Robert Schapire: Microsoft Research, New York, New York 10012

Operations Research, 2023, vol. 71, issue 4, 1120-1135

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 response model 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, high-dimensional geometry, and convex analysis.

Keywords: Revenue Management and Market Analytics; contextual online decision making; dynamic pricing; learning from revealed preferences (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2365 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:4:p:1120-1135

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().