  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/\varepsilon^2)$ queries to achieve an $\epsilon$-estimation accuracy.
This sample complexity significantly reduces the required sample complexity in
the passive setting, at least $\Omega(1/\varepsilon^4)$.
