IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2106.14077.html
   My bibliography  Save this paper

The Role of Contextual Information in Best Arm Identification

Author

Listed:
  • Masahiro Kato
  • Kaito Ariu

Abstract

We study the best-arm identification problem with fixed confidence when contextual (covariate) information is available in stochastic bandits. Although we can use contextual information in each round, we are interested in the marginalized mean reward over the contextual distribution. Our goal is to identify the best arm with a minimal number of samplings under a given value of the error rate. We show the instance-specific sample complexity lower bounds for the problem. Then, we propose a context-aware version of the "Track-and-Stop" strategy, wherein the proportion of the arm draws tracks the set of optimal allocations and prove that the expected number of arm draws matches the lower bound asymptotically. We demonstrate that contextual information can be used to improve the efficiency of the identification of the best marginalized mean reward compared with the results of Garivier & Kaufmann (2016). We experimentally confirm that context information contributes to faster best-arm identification.

Suggested Citation

  • Masahiro Kato & Kaito Ariu, 2021. "The Role of Contextual Information in Best Arm Identification," Papers 2106.14077, arXiv.org, revised Feb 2024.
    • Handle: RePEc:arx:papers:2106.14077
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2106.14077
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jinyong Hahn & Keisuke Hirano & Dean Karlan, 2011. "Adaptive Experimental Design Using the Propensity Score," Journal of Business & Economic Statistics, Taylor & Francis Journals, vol. 29(1), pages 96-108, January.
    2. Gilles Stoltz & Sébastien Bubeck & Rémi Munos, 2011. "Pure exploration in finitely-armed and continuous-armed bandits," Post-Print hal-00609550, HAL.
    3. Aurélien Garivier & Pierre Ménard & Gilles Stoltz, 2019. "Explore First, Exploit Next: The True Shape of Regret in Bandit Problems," Mathematics of Operations Research, INFORMS, vol. 44(2), pages 377-399, May.
    4. Imbens,Guido W. & Rubin,Donald B., 2015. "Causal Inference for Statistics, Social, and Biomedical Sciences," Cambridge Books, Cambridge University Press, number 9780521885881, September.
    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. Masahiro Kato & Masaaki Imaizumi & Takuya Ishihara & Toru Kitagawa, 2022. "Best Arm Identification with Contextual Information under a Small Gap," Papers 2209.07330, arXiv.org, revised Jan 2023.
    2. Masahiro Kato & Masaaki Imaizumi & Takuya Ishihara & Toru Kitagawa, 2023. "Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds," Papers 2302.02988, arXiv.org, revised Jul 2023.

    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. Pedro Carneiro & Sokbae Lee & Daniel Wilhelm, 2020. "Optimal data collection for randomized control trials," The Econometrics Journal, Royal Economic Society, vol. 23(1), pages 1-31.
    2. Aufenanger, Tobias, 2017. "Machine learning to improve experimental design," FAU Discussion Papers in Economics 16/2017, Friedrich-Alexander University Erlangen-Nuremberg, Institute for Economics, revised 2017.
    3. Masahiro Kato & Masaaki Imaizumi & Takuya Ishihara & Toru Kitagawa, 2023. "Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds," Papers 2302.02988, arXiv.org, revised Jul 2023.
    4. Yusuke Narita, 2018. "Toward an Ethical Experiment," Cowles Foundation Discussion Papers 2127, Cowles Foundation for Research in Economics, Yale University.
    5. Jinglong Zhao, 2024. "Experimental Design For Causal Inference Through An Optimization Lens," Papers 2408.09607, arXiv.org, revised Aug 2024.
    6. Yusuke Narita, 2018. "Experiment-as-Market: Incorporating Welfare into Randomized Controlled Trials," Cowles Foundation Discussion Papers 2127r, Cowles Foundation for Research in Economics, Yale University, revised May 2019.
    7. Masahiro Kato, 2021. "Adaptive Doubly Robust Estimator from Non-stationary Logging Policy under a Convergence of Average Probability," Papers 2102.08975, arXiv.org, revised Mar 2021.
    8. Yichong Zhang & Xin Zheng, 2020. "Quantile treatment effects and bootstrap inference under covariate‐adaptive randomization," Quantitative Economics, Econometric Society, vol. 11(3), pages 957-982, July.
    9. Masahiro Kato & Takuya Ishihara & Junya Honda & Yusuke Narita, 2020. "Efficient Adaptive Experimental Design for Average Treatment Effect Estimation," Papers 2002.05308, arXiv.org, revised Oct 2021.
    10. Masahiro Kato & Masaaki Imaizumi & Takuya Ishihara & Toru Kitagawa, 2022. "Best Arm Identification with Contextual Information under a Small Gap," Papers 2209.07330, arXiv.org, revised Jan 2023.
    11. Yuehao Bai & Azeem M. Shaikh & Max Tabord-Meehan, 2024. "A Primer on the Analysis of Randomized Experiments and a Survey of some Recent Advances," Papers 2405.03910, arXiv.org.
    12. Masahiro Kato & Akihiro Oga & Wataru Komatsubara & Ryo Inokuchi, 2024. "Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choices," Papers 2403.03589, arXiv.org, revised Jun 2024.
    13. Sven Resnjanskij & Jens Ruhose & Simon Wiederhold & Ludger Wößmann, 2021. "Mentoring verbessert die Arbeitsmarktchancen von stark benachteiligten Jugendlichen," ifo Schnelldienst, ifo Institute - Leibniz Institute for Economic Research at the University of Munich, vol. 74(02), pages 31-38, February.
    14. Marie Billaud Friess & Arthur Macherey & Anthony Nouy & Clémentine Prieur, 2022. "A PAC algorithm in relative precision for bandit problem with costly sampling," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 96(2), pages 161-185, October.
    15. Alexandre Belloni & Victor Chernozhukov & Denis Chetverikov & Christian Hansen & Kengo Kato, 2018. "High-dimensional econometrics and regularized GMM," CeMMAP working papers CWP35/18, Centre for Microdata Methods and Practice, Institute for Fiscal Studies.
    16. Dimitris Bertsimas & Agni Orfanoudaki & Rory B. Weiner, 2020. "Personalized treatment for coronary artery disease patients: a machine learning approach," Health Care Management Science, Springer, vol. 23(4), pages 482-506, December.
    17. Clément de Chaisemartin & Jaime Ramirez-Cuellar, 2024. "At What Level Should One Cluster Standard Errors in Paired and Small-Strata Experiments?," American Economic Journal: Applied Economics, American Economic Association, vol. 16(1), pages 193-212, January.
    18. Clément de Chaisemartin & Luc Behaghel, 2020. "Estimating the Effect of Treatments Allocated by Randomized Waiting Lists," Econometrica, Econometric Society, vol. 88(4), pages 1453-1477, July.
    19. Bruno Ferman & Cristine Pinto & Vitor Possebom, 2020. "Cherry Picking with Synthetic Controls," Journal of Policy Analysis and Management, John Wiley & Sons, Ltd., vol. 39(2), pages 510-532, March.
    20. Bonesrønning, Hans & Finseraas, Henning & Hardoy, Ines & Iversen, Jon Marius Vaag & Nyhus, Ole Henning & Opheim, Vibeke & Salvanes, Kari Vea & Sandsør, Astrid Marie Jorde & Schøne, Pål, 2022. "Small-group instruction to improve student performance in mathematics in early grades: Results from a randomized field experiment," Journal of Public Economics, Elsevier, vol. 216(C).

    More about this item

    Statistics

    Access and download statistics

    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:arx:papers:2106.14077. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.