2021/10/03 by Xi Chen, Chen, Xi, Quanquan Liu +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2110.01072
openalex publication_date 2021/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the learning problem in contextual search, which is motivated by applications such as first-price auction, personalized medicine experiments, and feature-based pricing 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 PAC 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 tri-section 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, at least Ω(1/ε4).