# Active Learning for Contextual Search with Binary Feedbacks

arXiv: https://arxiv.org/abs/2110.01072 · HTML: https://mlsanity.com/paper/2110.01072/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 48 references that are in the map.
- First posted on arXiv 3 Oct 2021.

## Builds on (most cited first, 12 of 12)

- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Dynamic Pricing with Demand Covariates](https://mlsanity.com/paper/1604.07463/) (2016)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Deep Landscape Forecasting for Real-time Bidding Advertising](https://mlsanity.com/paper/1905.03028/) (2019)
- [Diffusion Approximations for a Class of Sequential Testing Problems](https://mlsanity.com/paper/2102.07030/) (2021)
- [Asymptotically Optimal Sequential Design for Rank Aggregation](https://mlsanity.com/paper/1710.06056/) (2017)
- [Optimal Stopping and Worker Selection in Crowdsourcing: an Adaptive Sequential Probability Ratio Test Framework](https://mlsanity.com/paper/1708.08374/) (2017)

## Abstract (arXiv)

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/varepsilon2) queries to achieve an ε-estimation accuracy. This sample complexity significantly reduces the required sample complexity in the passive setting, at least Omega(1/varepsilon4).