IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v69y2023i4p2165-2181.html
   My bibliography  Save this article

Active Learning for Contextual Search with Binary Feedback

Author

Listed:
  • Xi Chen

    (Leonard N. Stern School of Business, New York University, New York, New York 10012)

  • Quanquan Liu

    (Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080)

  • Yining Wang

    (Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080)

Abstract

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 O ˜ ( 1 / ε 2 ) 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 Ω ( 1 / ε 3 ) .

Suggested Citation

  • Xi Chen & Quanquan Liu & Yining Wang, 2023. "Active Learning for Contextual Search with Binary Feedback," Management Science, INFORMS, vol. 69(4), pages 2165-2181, April.
    • Handle: RePEc:inm:ormnsc:v:69:y:2023:i:4:p:2165-2181
    DOI: 10.1287/mnsc.2022.4473
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2022.4473
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2022.4473?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Maxime C. Cohen & Ilan Lobel & Renato Paes Leme, 2020. "Feature-Based Dynamic Pricing," Management Science, INFORMS, vol. 66(11), pages 4921-4943, November.
    2. Hamsa Bastani & Mohsen Bayati, 2020. "Online Decision Making with High-Dimensional Covariates," Operations Research, INFORMS, vol. 68(1), pages 276-294, January.
    3. Hamsa Bastani & Mohsen Bayati & Khashayar Khosravi, 2021. "Mostly Exploration-Free Algorithms for Contextual Bandits," Management Science, INFORMS, vol. 67(3), pages 1329-1349, March.
    4. Li, Xiaoou & Chen, Yunxiao & Chen, Xi & Liu, Jingchen & Ying, Zhiliang, 2021. "Optimal stopping and worker selection in crowdsourcing: an adaptive sequential probability ratio test framework," LSE Research Online Documents on Economics 100873, London School of Economics and Political Science, LSE Library.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hamsa Bastani & David Simchi-Levi & Ruihao Zhu, 2022. "Meta Dynamic Pricing: Transfer Learning Across Experiments," Management Science, INFORMS, vol. 68(3), pages 1865-1881, March.
    2. Yinchu Zhu & Ilya O. Ryzhov, 2022. "Optimal data-driven hiring with equity for underrepresented groups," Papers 2206.09300, arXiv.org.
    3. Jingwen Zhang & Yifang Chen & Amandeep Singh, 2022. "Causal Bandits: Online Decision-Making in Endogenous Settings," Papers 2211.08649, arXiv.org, revised Feb 2023.
    4. Rong Jin & David Simchi-Levi & Li Wang & Xinshang Wang & Sen Yang, 2021. "Shrinking the Upper Confidence Bound: A Dynamic Product Selection Problem for Urban Warehouses," Management Science, INFORMS, vol. 67(8), pages 4756-4771, August.
    5. Victor F. Araman & René A. Caldentey, 2022. "Diffusion Approximations for a Class of Sequential Experimentation Problems," Management Science, INFORMS, vol. 68(8), pages 5958-5979, August.
    6. Yining Wang & Boxiao Chen & David Simchi-Levi, 2021. "Multimodal Dynamic Pricing," Management Science, INFORMS, vol. 67(10), pages 6136-6152, October.
    7. Kimia Keshanian & Daniel Zantedeschi & Kaushik Dutta, 2022. "Features Selection as a Nash-Bargaining Solution: Applications in Online Advertising and Information Systems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2485-2501, September.
    8. Max Biggs & Rim Hariss & Georgia Perakis, 2023. "Constrained optimization of objective functions determined from random forests," Production and Operations Management, Production and Operations Management Society, vol. 32(2), pages 397-415, February.
    9. Long He & Sheng Liu & Zuo‐Jun Max Shen, 2022. "Smart urban transport and logistics: A business analytics perspective," Production and Operations Management, Production and Operations Management Society, vol. 31(10), pages 3771-3787, October.
    10. Pourbabaee, Farzad, 2021. "High dimensional decision making, upper and lower bounds," Economics Letters, Elsevier, vol. 204(C).
    11. Masahiro Kato & Shinji Ito, 2023. "Best-of-Both-Worlds Linear Contextual Bandits," Papers 2312.16489, arXiv.org.
    12. Anand Kalvit & Aleksandrs Slivkins & Yonatan Gur, 2024. "Incentivized Exploration via Filtered Posterior Sampling," Papers 2402.13338, arXiv.org.
    13. Jianyu Xu & Yu-Xiang Wang, 2022. "Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise," Papers 2201.11341, arXiv.org, revised Apr 2022.
    14. Zeqi Ye & Hansheng Jiang, 2023. "Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning," Papers 2310.07558, arXiv.org, revised Oct 2023.
    15. Woonghee Tim Huh & Michael Jong Kim & Meichun Lin, 2022. "Bayesian dithering for learning: Asymptotically optimal policies in dynamic pricing," Production and Operations Management, Production and Operations Management Society, vol. 31(9), pages 3576-3593, September.
    16. Claudio Cardoso Flores & Marcelo Cunha Medeiros, 2020. "Online Action Learning in High Dimensions: A Conservative Perspective," Papers 2009.13961, arXiv.org, revised Mar 2024.
    17. Ying Zhong & L. Jeff Hong & Guangwu Liu, 2021. "Earning and Learning with Varying Cost," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2379-2394, August.
    18. Ningyuan Chen & Guillermo Gallego, 2021. "Nonparametric Pricing Analytics with Customer Covariates," Operations Research, INFORMS, vol. 69(3), pages 974-984, May.
    19. Yiwei Chen & Cong Shi, 2023. "Network revenue management with online inverse batch gradient descent method," Production and Operations Management, Production and Operations Management Society, vol. 32(7), pages 2123-2137, July.
    20. Oliveira, Fabio & Kakabadse, Nada & Khan, Nadeem, 2022. "Board engagement with digital technologies: A resource dependence framework," Journal of Business Research, Elsevier, vol. 139(C), pages 804-818.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:69:y:2023:i:4:p:2165-2181. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.