Active Learning for Contextual Search with Binary Feedback

Xi Chen (), Quanquan Liu () and Yining Wang ()
Additional contact information
Xi Chen: Leonard N. Stern School of Business, New York University, New York, New York 10012
Quanquan Liu: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080
Yining Wang: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080

Management Science, 2023, vol. 69, issue 4, 2165-2181

Abstract: In this paper, we study the learning problem in contextual search, which is motivated by applications such as crowdsourcing and personalized medicine experiments. In particular, for a sequence of arriving context vectors, with each context associated with an underlying value, the decision maker either makes a query at a certain point or skips the context. The decision maker will only observe the binary feedback on the relationship between the query point and the value associated with the context. We study a probably approximately correct learning setting, where the goal is to learn the underlying mean value function in context with a minimum number of queries. To address this challenge, we propose a trisection search approach combined with a margin-based active learning method. We show that the algorithm only needs to make O ˜ ( 1 / ε 2 ) queries to achieve an ε -estimation accuracy. This sample complexity significantly reduces the required sample complexity in the passive setting where neither sample skipping nor query selection is allowed, which is at least Ω ( 1 / ε 3 ) .

Keywords: active learning; binary feedback; classification; contextual search (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2022.4473 (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:ormnsc:v:69:y:2023:i:4:p:2165-2181

Access Statistics for this article

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