Active Learning for Contextual Search with Binary Feedback
研究了上下文搜索中的学习问题，提出一种结合三分搜索和基于间隔的主动学习方法，以最少查询次数学习上下文中的均值函数，显著降低了被动设置所需的样本复杂度。
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 [Formula: see text] 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 [Formula: see text]. This paper was accepted by J. George Shanthikumar, data science. Funding: X. Chen and Q. Liu were supported by the National Science Foundation [Grant IIS-1845444].