Some performance considerations when using multi-armed bandit algorithms in the presence of missing data

Xijin Chen; Kim May Lee; Sofia S. Villar; David S. Robertson

doi:10.1371/journal.pone.0274272

Some performance considerations when using multi-armed bandit algorithms in the presence of missing data

Xijin Chen^*, Kim May Lee, Sofia S. Villar, David S. Robertson

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

When comparing the performance of multi-armed bandit algorithms, the potential impact of missing data is often overlooked. In practice, it also affects their implementation where the simplest approach to overcome this is to continue to sample according to the original bandit algorithm, ignoring missing outcomes. We investigate the impact on performance of this approach to deal with missing data for several bandit algorithms through an extensive simulation study assuming the rewards are missing at random. We focus on two-armed bandit algorithms with binary outcomes in the context of patient allocation for clinical trials with relatively small sample sizes. However, our results apply to other applications of bandit algorithms where missing data is expected to occur. We assess the resulting operating characteristics, including the expected reward. Different probabilities of missingness in both arms are considered. The key finding of our work is that when using the simplest strategy of ignoring missing data, the impact on the expected performance of multi-armed bandit strategies varies according to the way these strategies balance the exploration-exploitation tradeoff. Algorithms that are geared towards exploration continue to assign samples to the arm with more missing responses (which being perceived as the arm with less observed information is deemed more appealing by the algorithm than it would otherwise be). In contrast, algorithms that are geared towards exploitation would rapidly assign a high value to samples from the arms with a current high mean irrespective of the level observations per arm. Furthermore, for algorithms focusing more on exploration, we illustrate that the problem of missing responses can be alleviated using a simple mean imputation approach.

Original language	English
Article number	e0274272
Journal	PLoS ONE
Volume	17
Issue number	9 September
DOIs	https://doi.org/10.1371/journal.pone.0274272
Publication status	Published - Sept 2022

Access to Document

10.1371/journal.pone.0274272

Cite this

@article{3d5927ba037142fe982286567f79aaf7,

title = "Some performance considerations when using multi-armed bandit algorithms in the presence of missing data",

abstract = "When comparing the performance of multi-armed bandit algorithms, the potential impact of missing data is often overlooked. In practice, it also affects their implementation where the simplest approach to overcome this is to continue to sample according to the original bandit algorithm, ignoring missing outcomes. We investigate the impact on performance of this approach to deal with missing data for several bandit algorithms through an extensive simulation study assuming the rewards are missing at random. We focus on two-armed bandit algorithms with binary outcomes in the context of patient allocation for clinical trials with relatively small sample sizes. However, our results apply to other applications of bandit algorithms where missing data is expected to occur. We assess the resulting operating characteristics, including the expected reward. Different probabilities of missingness in both arms are considered. The key finding of our work is that when using the simplest strategy of ignoring missing data, the impact on the expected performance of multi-armed bandit strategies varies according to the way these strategies balance the exploration-exploitation tradeoff. Algorithms that are geared towards exploration continue to assign samples to the arm with more missing responses (which being perceived as the arm with less observed information is deemed more appealing by the algorithm than it would otherwise be). In contrast, algorithms that are geared towards exploitation would rapidly assign a high value to samples from the arms with a current high mean irrespective of the level observations per arm. Furthermore, for algorithms focusing more on exploration, we illustrate that the problem of missing responses can be alleviated using a simple mean imputation approach.",

author = "Xijin Chen and Lee, {Kim May} and Villar, {Sofia S.} and Robertson, {David S.}",

note = "Funding Information: Funding: This research was supported by the NIHR Cambridge Biomedical Research Centre (BRC1215-20014), the NIHR Maudsley Biomedical Research Centre at South London and Maudsley NHS Foundation Trust and King{\textquoteright}s College London. The views expressed in this publication are those of the authors and not necessarily those of the NHS, the National Institute for Health Research or the Department of Health and Social Care (DHCS). SSV received funding from the UK Medical Research Council (MC_UU_00002/15). DSR received funding from the Biometrika Trust and the UK Medical Research Council (MC_UU_00002/14). KML received funding from the National Institute for Health Research (NIHR Research Professorship, Professor Richard Emsley, NIHR300051). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. Publisher Copyright: {\textcopyright} 2022 Chen et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.",

year = "2022",

month = sep,

doi = "10.1371/journal.pone.0274272",

language = "English",

volume = "17",

journal = "PLoS ONE",

issn = "1932-6203",

publisher = "Public Library of Science",

number = "9 September",

}

TY - JOUR

T1 - Some performance considerations when using multi-armed bandit algorithms in the presence of missing data

AU - Chen, Xijin

AU - Lee, Kim May

AU - Villar, Sofia S.

AU - Robertson, David S.

N1 - Funding Information: Funding: This research was supported by the NIHR Cambridge Biomedical Research Centre (BRC1215-20014), the NIHR Maudsley Biomedical Research Centre at South London and Maudsley NHS Foundation Trust and King’s College London. The views expressed in this publication are those of the authors and not necessarily those of the NHS, the National Institute for Health Research or the Department of Health and Social Care (DHCS). SSV received funding from the UK Medical Research Council (MC_UU_00002/15). DSR received funding from the Biometrika Trust and the UK Medical Research Council (MC_UU_00002/14). KML received funding from the National Institute for Health Research (NIHR Research Professorship, Professor Richard Emsley, NIHR300051). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. Publisher Copyright: © 2022 Chen et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

PY - 2022/9

Y1 - 2022/9

N2 - When comparing the performance of multi-armed bandit algorithms, the potential impact of missing data is often overlooked. In practice, it also affects their implementation where the simplest approach to overcome this is to continue to sample according to the original bandit algorithm, ignoring missing outcomes. We investigate the impact on performance of this approach to deal with missing data for several bandit algorithms through an extensive simulation study assuming the rewards are missing at random. We focus on two-armed bandit algorithms with binary outcomes in the context of patient allocation for clinical trials with relatively small sample sizes. However, our results apply to other applications of bandit algorithms where missing data is expected to occur. We assess the resulting operating characteristics, including the expected reward. Different probabilities of missingness in both arms are considered. The key finding of our work is that when using the simplest strategy of ignoring missing data, the impact on the expected performance of multi-armed bandit strategies varies according to the way these strategies balance the exploration-exploitation tradeoff. Algorithms that are geared towards exploration continue to assign samples to the arm with more missing responses (which being perceived as the arm with less observed information is deemed more appealing by the algorithm than it would otherwise be). In contrast, algorithms that are geared towards exploitation would rapidly assign a high value to samples from the arms with a current high mean irrespective of the level observations per arm. Furthermore, for algorithms focusing more on exploration, we illustrate that the problem of missing responses can be alleviated using a simple mean imputation approach.

AB - When comparing the performance of multi-armed bandit algorithms, the potential impact of missing data is often overlooked. In practice, it also affects their implementation where the simplest approach to overcome this is to continue to sample according to the original bandit algorithm, ignoring missing outcomes. We investigate the impact on performance of this approach to deal with missing data for several bandit algorithms through an extensive simulation study assuming the rewards are missing at random. We focus on two-armed bandit algorithms with binary outcomes in the context of patient allocation for clinical trials with relatively small sample sizes. However, our results apply to other applications of bandit algorithms where missing data is expected to occur. We assess the resulting operating characteristics, including the expected reward. Different probabilities of missingness in both arms are considered. The key finding of our work is that when using the simplest strategy of ignoring missing data, the impact on the expected performance of multi-armed bandit strategies varies according to the way these strategies balance the exploration-exploitation tradeoff. Algorithms that are geared towards exploration continue to assign samples to the arm with more missing responses (which being perceived as the arm with less observed information is deemed more appealing by the algorithm than it would otherwise be). In contrast, algorithms that are geared towards exploitation would rapidly assign a high value to samples from the arms with a current high mean irrespective of the level observations per arm. Furthermore, for algorithms focusing more on exploration, we illustrate that the problem of missing responses can be alleviated using a simple mean imputation approach.

UR - http://www.scopus.com/inward/record.url?scp=85138440894&partnerID=8YFLogxK

U2 - 10.1371/journal.pone.0274272

DO - 10.1371/journal.pone.0274272

M3 - Article

C2 - 36094920

AN - SCOPUS:85138440894

SN - 1932-6203

VL - 17

JO - PLoS ONE

JF - PLoS ONE

IS - 9 September

M1 - e0274272

ER -

Some performance considerations when using multi-armed bandit algorithms in the presence of missing data

Abstract

Access to Document

Other files and links

Fingerprint

Cite this