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. Hamsa Bastani & Mohsen Bayati, 2020. "Online Decision Making with High-Dimensional Covariates," Operations Research, INFORMS, vol. 68(1), pages 276-294, January.
    2. Hamsa Bastani & Mohsen Bayati & Khashayar Khosravi, 2021. "Mostly Exploration-Free Algorithms for Contextual Bandits," Management Science, INFORMS, vol. 67(3), pages 1329-1349, March.
    3. 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.
    4. Maxime C. Cohen & Ilan Lobel & Renato Paes Leme, 2020. "Feature-Based Dynamic Pricing," Management Science, INFORMS, vol. 66(11), pages 4921-4943, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jinglong Zhao, 2024. "Experimental Design For Causal Inference Through An Optimization Lens," Papers 2408.09607, arXiv.org, revised Aug 2024.

    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. Jingwen Zhang & Yifang Chen & Amandeep Singh, 2022. "Causal Bandits: Online Decision-Making in Endogenous Settings," Papers 2211.08649, arXiv.org, revised Feb 2023.
    2. 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.
    3. Yinchu Zhu & Ilya O. Ryzhov, 2022. "Optimal data-driven hiring with equity for underrepresented groups," Papers 2206.09300, arXiv.org.
    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. Estey, Clayton, 2024. "Robust Bellman State Prediction with Learning and Model Preferences," OSF Preprints 75fc9, Center for Open Science.
    7. Pourbabaee, Farzad, 2021. "High dimensional decision making, upper and lower bounds," Economics Letters, Elsevier, vol. 204(C).
    8. Anand Kalvit & Aleksandrs Slivkins & Yonatan Gur, 2024. "Incentivized Exploration via Filtered Posterior Sampling," Papers 2402.13338, arXiv.org.
    9. Zeqi Ye & Hansheng Jiang, 2023. "Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning," Papers 2310.07558, arXiv.org, revised Oct 2023.
    10. Claudio Cardoso Flores & Marcelo Cunha Medeiros, 2020. "Online Action Learning in High Dimensions: A Conservative Perspective," Papers 2009.13961, arXiv.org, revised Mar 2024.
    11. Ningyuan Chen & Guillermo Gallego, 2021. "Nonparametric Pricing Analytics with Customer Covariates," Operations Research, INFORMS, vol. 69(3), pages 974-984, May.
    12. 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.
    13. Jing Xu & Yung-Cheng Hsu & William Biscarri, 2024. "Dynamic Pricing in Securities Lending Market: Application in Revenue Optimization for an Agent Lender Portfolio," Papers 2407.13687, arXiv.org, revised Oct 2024.
    14. Arlen Dean & Amirhossein Meisami & Henry Lam & Mark P. Van Oyen & Christopher Stromblad & Nick Kastango, 2022. "Quantile regression forests for individualized surgery scheduling," Health Care Management Science, Springer, vol. 25(4), pages 682-709, December.
    15. Farzad Pourbabaee, 2021. "High Dimensional Decision Making, Upper and Lower Bounds," Papers 2105.00545, arXiv.org.
    16. Franc{c}ois Bachoc & Tommaso Cesari & Roberto Colomboni, 2024. "A Contextual Online Learning Theory of Brokerage," Papers 2407.01566, arXiv.org.
    17. Raad Khraishi & Ramin Okhrati, 2022. "Offline Deep Reinforcement Learning for Dynamic Pricing of Consumer Credit," Papers 2203.03003, arXiv.org.
    18. Stephen E. Chick & Noah Gans & Özge Yapar, 2022. "Bayesian Sequential Learning for Clinical Trials of Multiple Correlated Medical Interventions," Management Science, INFORMS, vol. 68(7), pages 4919-4938, July.
    19. Nicol`o Cesa-Bianchi & Tommaso Cesari & Roberto Colomboni & Federico Fusco & Stefano Leonardi, 2021. "Bilateral Trade: A Regret Minimization Perspective," Papers 2109.12974, arXiv.org.
    20. Yichun Hu & Nathan Kallus & Xiaojie Mao, 2022. "Fast Rates for Contextual Linear Optimization," Management Science, INFORMS, vol. 68(6), pages 4236-4245, June.

    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.