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 trade-off. 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.

Fig 1. Allocation procedure of bandit algorithms.

Performance of different bandit algorithms over a single simulation (with p₀ = 0.7, p₁ = 0.7, and n = 200) under the null. The two colors reflect different arms that could be regarded as the same under the null.

Fig 2. Simulation results of E[p*] for TTS, CB and UCB under the null.

Expectations of 10⁴ replications are taken for CB and UCB and 10³ replications for TTS under different combinations of missingness probabilities, with p₀ = p₁ = 0.9 and n = 200.

Fig 3. Simulation results under the null.

Simulation results of E[p*] under the null for different missing data combinations. Grey lines correspond to the case of equal missingness probability in both arms; Blue lines correspond to missingness in the control arm; Red lines correspond to missingness in the experimental arm.

Fig 4. Simulation results under the alternative.

Simulation results of E[p*] under the alternative for different missing data combinations. Grey lines correspond to the case of equal missingness probability in both arms; Blue lines correspond to missingness in the control arm; Red lines correspond to missingness in the experimental arm.

Fig 5. Imputation results under the null.

Imputation results of E[p*] under the null for different missing data combinations with initial value ${\widehat{p}}_{k,0}=0.5$. Grey lines correspond to the case of equal missingness probability in both arms; Blue lines correspond to missingness in the control arm; Red lines correspond to missingness in the experimental arm. Solid lines correspond to the results without mean imputation, while the dashed lines correspond to the results with mean imputation.

Fig 6. Imputation results under the alternative.

Imputation results of E[p*] under the alternative for different missing data combinations initial value ${\widehat{p}}_{k,0}=0.5$. Grey lines correspond to the case of equal missingness probability in both arms; Blue lines correspond to missingness in the control arm; Red lines correspond to missingness in the experimental arm. Solid lines correspond to the results without mean imputation, while the dashed lines correspond to the results with mean imputation.