Active Learning for Contextual Search with Binary Feedback

• 成果类型: Article
• 署名作者: Chen, Xi; Liu, Quanquan; Wang, Yining
• 署名单位: New York University; University of Texas System; University of Texas Dallas
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2022.4473
• 发表日期: 2023
• 页码: 2165-2181
• 关键词: Active learning; binary feedback; CLASSIFICATION; contextual search

摘要

In this paper, we study the learning problemin contextual search, which ismotivated 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) over tilde (1/epsilon(2)) queries to achieve an e-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 Omega(1/epsilon(3)).