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

The two-armed trial setting is a very common one in clinical trial designs. We denote the control arm by the subscript $k=0$ and the experimental arm by $k=1$, respectively. Assigned patients have missing responses with a probability $p_{k}^{\text{m}}\leq 0.5$, given that it is rare that the majority of patients would be missing in the setting of healthcare. The total number of missing responses, successes and failures on arm $k$ at time $t$ are denoted by $M_{k,t}$, $S_{k,t}$ and $F_{k,t}$.

The observed outcomes $(S_{k,t},\ F_{k,t})$, with a true probability of success $p_{k}$, in turn have an impact on the next allocation due to the response-adaptive nature in bandit algorithms, while missing responses $M_{k,t}$ do not. The Bayesian feature is introduced to the algorithm by a uniform prior ($s_{k,0}=1,\ f_{k,0}=1$), which is the initial state that enables the first patients to be assigned when there are no observations. The uniform prior implies that an equal allocation (as in the fixed design) is initially used, but a different prior could also be used if appropriate.

The current state $x_{k,t}=(s_{k,0}+S_{k,t},\ f_{k,0}+F_{k,t})$ after having observed $S_{k,t}$ and $F_{k,t}$ determines the subsequent patient allocation. Note that for each arm $k$, the number of assigned patients in arm $k$ at time $t$ accounts for both the missing and observed data, namely, $N_{k,t}=S_{k,t}+F_{k,t}+M_{k,t}$. The fixed total trial size is expressed as $n$. The allocation procedure with bandit algorithms in the presence of missing data is attached in Appendix A. The operating characteristics we evaluate are defined as the proportion of patients assigned to the experimental arm ($p^{*}=\frac{N_{1,n}}{n}$) and the observed total number of success ($\text{ONS}=E[S_{0,n}+S_{1,n}]$). In the clinical trial context, we will typically be interested in testing a null hypothesis $H_{0}:p_{0}=p_{1}$ against a one-sided alternative hypothesis $H_{A}:p_{0}<p_{1}$.

We classify several well-known bandit algorithms into three categories according to their exploration-exploitation trade-off. Details of these algorithms are summarized in Table 1, with further details given below.

• •

  Randomized algorithms (TTS, RTS, and RPW): The patient at time $t$ is randomly assigned to arm $k$ with probability $\pi_{k,t}$.

• •

  Deterministic algorithms (CB, GI, and UCB): The patient at time $t$ is deterministically assigned to the arm $k$ with the larger index values $I_{k,t}$, indicating the existence of a ‘priority’ value for sampling from one of the arms [47].

• •

  Semi-randomized algorithms (RandUCB, RBI, and RGI): The patient at time $t$ is deterministically assigned to the arm with the larger index values $I_{k,t}$ as in deterministic algorithms. However, a stochastic element is involved in the computation of the index values $I_{k,t}$.

In the allocation procedure, the first assignment is based on the initial value ($\pi_{k,0}$ or $I_{k,0}$) and is an equal allocation for all algorithms, which is based on the choice of prior. This is achieved by allocation of the first patient via an allocation probability fixed at $\pi_{k,0}=0.5$ in the case of randomized algorithms, or via equal index values $I_{k,0}$ in both arms in the case of deterministic or semi-randomized algorithms.

• •

  Tuned Thompson Sampling (TTS): is not the original version of TS but a variant that has been more generally implemented [63]. TTS randomizes each patient to a treatment $k$ with a probability that is proportional to the posterior probability that treatment $k$ is the best arm given the accrued data. The best arm refers to the arm with the largest $p_{k}$, and it is assumed that in the case of a tie ($p_{0}=p_{1}$), the arm ($p_{0}$) would be considered as the best. The positive tuning parameter $c=\frac{t}{2n}$ is time-varying.

• •

  Raw Thompson Sampling (RTS): is the ‘raw’ version of TS in its first proposal [64]. RTS is the most commonly used version in the machine learning community, which is different from the commonly used version, TTS, in the biostatistical community in terms of the tuning parameter [63]. The tuning parameter of TTS is fixed at $c=1$ in RTS. When compared to the traditional fixed randomization (FR) with a fixed tuning parameter $c=0$, RTS and TTS have different tuning parameters $c$.

• •

  Randomized Play-the-Winner (RPW): is not a bandit algorithm but an urn-based model [69]. We include it since RPW has a long history in clinical trials methodology, and because its use helps explain why few response-adaptive clinical trials have occurred in practice. Indeed, the infamous Extracorporeal Circulation in Neonatal Respiratory Failure (ECMO) trial [9] used RPW to allocate patients. Due to the extreme treatment imbalance and highly controversial interpretation, the ECMO trial is regarded as a key example against the use of response-adaptive designs in clinical trials [53, 18]. The initial urn composition in this paper is the extreme case of one ball for each treatment. One would expect the allocation proportions to be less extreme when the initial urn composition is increased, as the urn will not favor the better treatment as highly.

• •

  Current Belief (CB): allocates each patient to the treatment arm with the highest immediate estimate of reward $\hat{\mu}^{B}_{k,t}$, which is defined as the current highest mean posterior probability of success. With the only aim of exploitation, this myopic algorithm will tend to ‘select’ an arm before the trial is over. Once one arm is selected, all of the next enrolled patients will be assigned to this arm, and the index value of the unselected arm will not change anymore. One issue with CB is that the algorithm might make a wrong selection and make many allocations to the inferior arm. An early selection within the first few patients could be anticipated when the success probability $p_{k}$ is large.

• •

  Gittins Index (GI): recovers the optimal solution to an infinite (discounted) MABP as obtained by Dynamic programming [67]. There is an upward adjustment in the index value $I_{k,t}$ in GI when compared to CB, referring to the uncertainty about the prospects of obtaining rewards from the arm [29]. This uncertainty corresponds to a decreasing exploration component, which decreases with more observations in the corresponding arm [30]. The value of the initial state $I_{k,0}$ of GI is larger than that of CB as a result of the upward adjustment. It is fixed at $I_{k,0}=0.8699$ for GI in this paper, corresponding to a particular discount factor $d=0.99$, the widely used value in the related bandit literature [67].

• •

  Randomized Belief Index (RBI): is a semi-randomized approach with an index-based part $\hat{\mu}^{B}_{k,t}$ for exploitation and a random perturbation part $Z_{t}\cdot\lambda_{k}(t)$ for exploration. $Z_{t}$ is a random variable and $\lambda_{k}(t)$ is a decreasing sequence of positive constants. This means that most patients are assigned to the (current) superior arm, but some patients will still be assigned to the inferior arm in order to achieve exploration [12]. In other words, there is no aggressive determinism in RBI when compared to CB as a result of the additional perturbation part. The overall pattern of its index values $I_{k,t}$ is decreasing as a result of the decreasing exploitation component, accompanied by some fluctuations representing the random exploration part.

• •

  Randomized Gittins Index (RGI): is a semi-randomized approach, which applies the random perturbation idea to the GI rule [31, 12]. Similar to RBI, the overall index values $I_{k,t}$ and the exploration component of the index values decrease over time.

• •

  Upper Confidence Bound Index (UCB): is based on the principle of ‘optimism in the face of uncertainty’ [5]. It explores the arm with higher uncertainty because of higher information gain represented by the term $\beta\cdot\lambda_{k}(t)$, where $\beta=\sqrt{2\log(t)}$ and $\lambda_{k}(t)=\sqrt{\frac{1}{s_{k,0}+f_{k,0}+S_{k,t}+F_{k,t}}}$ reflects the confidence interval corresponding to the standard deviation in the estimation of reward $\hat{\mu}^{B}_{k,t}$. The more times a specific arm has been engaged before in the past, the greater the confidence boundary reduces towards the point estimate. If there are no observations in the $k$-th term, then $\hat{\mu}^{B}_{k,t}=0$ and $\beta\cdot\lambda_{k}(t)\to\infty$, thus each arm is selected at least once. As evidence accumulates and the term $\beta\cdot\lambda_{k}(t)$ vanishes, the index values have an initial rapid increase for the first few patients but then decrease in both arms. There are many variants of UCB targeting various objectives in different disciplines [38].

• •

  Randomized Upper Confidence Bound (RandUCB): is similar to RBI and RGI in terms of being a semi-randomized algorithm. RandUCB takes random perturbations [12, 31] for the computation of its index values. RandUCB is different from the UCB algorithm in terms of the exploration term, which is constructed by a random variable $Z_{t}$ sampling from a discrete distribution $f_{X}(x)$ [66]. In addition, exploration in the arm with higher uncertainty is realized by accounting for the confidence interval or standard deviation $\lambda_{k}(t)$ as in the UCB. The discrete distribution is supported on $M$ points over the interval $[L,U]$. Let $\alpha_{1}=L$…, $\alpha_{M}=U$ denote $M$ equally spaced points in $[L,U]$. We recover the UCB if $M=1$ and $[L,U]=[\beta,\beta]$ hold. RandUCB with $M\to\infty$ approaches optimistic TS (one of the different versions of TS) with a Gaussian prior and posterior. In other words, both UCB and TS can be recovered as special cases of RandUCB. In this paper, we take $M=20$ and $[L,U]=[0,1]$ as an example for illustration. More details are discussed in Vaswani et al. [66]. Actually, the idea of RandUCB is the same as that used in RBI and RGI, which can be traced back to around 40 years ago [12].

In general, there is more than one strategy to solve the exploration-exploitation dilemma inherent in the MABP. For algorithms in this framework, the exploitation goal could be achieved with an immediate reward based on current observations. For the aim of exploration, one of the classic strategies is to account for a confidence level in the estimate, namely, optimism in the face of uncertainty [1]. The UCB algorithm is an example using this strategy that has attracted a lot of attention in the field of machine learning. Another common device in optimization problems is randomized allocation, which is widely used in the context of clinical trials. This includes the first well-known attempt at response-adaptive design, RTS. Besides, this stochastic setting has also motivated the ‘Follow the Perturbed Leader’ algorithms, which add random perturbations to the estimates of rewards of each arm prior to computing the current ‘best arm’ [2, 39, 41]. The semi-randomized algorithms, RBI and RGI [67], operate in the same way through randomly perturbing arms that would be selected by a greedy algorithm, which disregards any advantages of exploring. Thus, it allows mixtures of alternative decisions of the selected arms. RandUCB uses randomization to trade off exploration and exploitation, like RBI and RGI, and simultaneously it maintains optimism in the face of uncertainty in a similar way to UCB.

Bandit algorithms work in different ways according to their exploration-exploitation trade-off. Figure 1 demonstrates the sampling behaviour using the results of a single simulation, for a specific scenario under the null. The trial size is fixed at $n=200$, indicating a relatively small confirmatory clinical trial. In the case of a larger trial, the simulation results reflect what could happen at its beginning. The true probabilities of success are fixed at $p_{0}=p_{1}=0.7$, which might arise when testing two similarly efficacious vaccines in clinical trials. The assumption of identical arms also is relevant to some other machine learning applications, such as the problem of online allocation of homogeneous tasks to a pool of agents; a problem faced by many online platforms and matching markets. The regret performance of a bandit algorithm in terms of its arm-sampling characteristics are of great interest, not only in the ‘large gap’ (i.e., ‘well-separated’) instance but also the ‘small gap’ instance (i.e., ‘worst-case’), where the gap corresponds to the small difference between the top two arm mean rewards [37]. The large treatment effects in the example in Figure 1 might not be common in general, but it can provide some intuitive thinking and theoretical perspective. We illustrate a counterpart for a scenario under the alternative in Appendix E because, in general, research in machine learning illustrates bandit performance under the alternative but the null case is rarely displayed.

In Figure 1, randomized algorithms (i.e., the first row) allocate patients with a probability $\pi_{k,t}$, while the others allocate patients to the arm with a larger $I_{k,t}$ value. Note that the scales on the y-axis of $I_{k,t}$ of deterministic and semi-randomized algorithms are different, and it is the relative difference between the $I_{k,t}$ in the two arms rather than the absolute value that determines allocation results.

The allocation probabilities $\pi_{k,t}$ of TTS show that it tends to ‘select’ an arm (i.e., allocate to that arm with a much higher probability) by the end of a large cohort of patients, even when there is no treatment difference between these two arms. The random selection of one of these equal arms under the null has been discussed in the related discussion about bandit algorithms [72, 60]. A theoretical explanation of this imbalanced behaviour for Thompson Sampling under the null (i.e., despite the arms being statistically identical), also known as the ‘incomplete learning’ phenomenon, is provided in [37]. When compared with TTS, such a ‘selection’ under RTS happens earlier than that of TTS. RTS is also relatively more ‘deterministic’ than TTS due to the fixed tuning parameter, even though both are randomized algorithms. The urn-based algorithm RPW also illustrates some degree of ‘determinism’ in the first few patients. That is, one arm tends to be ‘selected’ at the beginning of the trial, as a result of the small initial urn size in our setting.

These randomized algorithms have a smaller chance of an early selection and never conduct a real selection in the finite sample size settings. In contrast, deterministic algorithms are more likely to truly select an arm, with patients always assigned to the selected arm from then on. An allocation skew could be anticipated if an early selection occurs. For CB and RandUCB, early selection is particularly noticeable, especially for CB. However, GI, although defined to be a deterministic rule, continues to explore in this instance where CB does not, as shown by the index values of both arms continuing to overlap throughout the trial. Meanwhile, RBI, RGI, and UCB are quite similar in a sense that the index values in both arms are close to to each other, although accompanied by fluctuations as a result of accounting for the uncertainty of the point estimate. This sampling behaviour is also referred to as ‘complete learning’, which was explained theoretically by [37], where UCB is taken as an example. In particular, UCB is able to discern statistical indistinguishability of the arm-means, and induce a ‘balanced’ allocation under the null when there is no treatment difference.

Since the results in Figure 1 are based on a single simulation under the null, a selection is neither incorrect nor correct as both arms are the same and there is no inferior or superior arm (all other costs being equal). A similar illustration of allocation probabilities $\pi_{k,t}$ or index values $I_{k,t}$ in a scenario under the alternative is given in Appendix E. The illustration in Figure 1 gives an insight into the potential consequences of the presence of missing data as shown in Section 3.1. An extensive simulation involving various scenarios follows in Section 3.3.

For simplicity, suppose that missing data only occurs in arm $k$ and not arm $\tilde{k}$. If the outcome at time $t_{1}$ in arm $k$ is missing, the next allocation to arm $k$ at time $t_{2}$ cannot be updated and remains what it was for the last patient ($I_{k,t_{2}}=I_{k,t_{1}}$ or $\pi_{k,t_{2}}=\pi_{k,t_{1}}$). By contrast, since there is no missing data at time $t_{2}$ in arm $\tilde{k}$, the value of $I_{\tilde{k},t_{2}}$ or $\pi_{\tilde{k},t_{2}}$ would be updated as it was supposed to do. Consequently, the subsequent allocations could be affected due to the missing data.

In addition, the impact of missing data on $\pi_{k,t}$ or $I_{k,t}$ is expected to differ across algorithms. For randomized and semi-randomized algorithms, the impact due to missing responses is relatively low as a result of exploration. This applies to both randomized algorithms (i.e., TTS and RTS) and semi-randomized algorithms (i.e., RBI and RGI). Similarly, algorithms taking uncertainty into account for allocations (i.e., UCB and GI) are also less affected by missing data due to their continued exploration.

By contrast, heavily exploitative algorithms (i.e., CB and RandUCB) are expected to be largely affected by missing data in terms of the selection. In the example in Figure 1 with large true probabilities of success ($p_{0}=p_{1}=0.7$), the arm with missing outcomes is less likely to be selected. The reason is that the other arm without missing outcomes is more likely to have successful outcomes under such a large $p_{k}$, and $I_{k,t}$ of this arm will be updated to a larger value for the next allocation. As a consequence, these greedy or deterministic algorithms are less robust to the impact of missing data when compared with algorithms that are more explorative.

Besides, the changing patterns of $\pi_{k,t}$ and $I_{k,t}$ provide some additional insights on the impact of missing data. On the one hand, randomized algorithms (TTS and RTS) keep learning and $\pi_{k,t}$ of both arms change across the trial – starting from $\pi_{k,0}=0.5$, $\pi_{k,t}$ values in these two arms become more distinguishable from each other with more enrolled patients and are always symmetric around 0.5. Consequently, the arm with larger $\pi_{k,t}$ values is more likely to be selected even if there is missing data in this arm. On the other hand, $I_{k,t}$ values generally decrease as the immediate reward $\hat{\mu}^{B}_{k,t}$ or $\mu^{G}_{k,t}$ decreases with more patients. Once the selection of an arm occurs, $I_{k,t}$ of the other arm will remain unchanged as the arm will not be selected anymore, see Figure 1. Consequently, the arm with missing data is more likely to be selected.

Considering both the impact of missing data in one arm and the changing patterns of $\pi_{k,t}$ or $I_{k,t}$ across a trial of different algorithms, it could infer the impact of missing data in one arm on allocation results, as shown in the simulation results in Section 3.2. Intuitively, for algorithms geared towards exploration, missing data in one arm slows down the progress of learning or exploration in randomized algorithms. More patients will thus be assigned to the arm with missing data to continue to explore. For algorithms geared towards exploitation, missing data in one arm impedes the decreasing trend in $I_{k,t}$ of the corresponding arm, which may thus have a larger index value than the other arm without missing data. Consequently, the arm with missing data is less likely to be selected, and fewer patients will be assigned to it.

In this section, we investigate the impact of having different probabilities of missingness in the two arms. Simulation results are based on $10^{4}$ independent replications of each algorithm, except for TTS, which has $10^{3}$ replications for computational reasons. We consider 36 combinations of missingness probabilities for the two arms, where $p_{0}^{\text{m}}$ and $p_{1}^{\text{m}}$ follow a sequence of discrete values ranging from 0 to 50% (0, 0.1, 0.2, 0.3, 0.4, 0.5). Figure 2 shows the simulation results for $E[p^{*}]$ of three representative algorithms from Table 1.

The value of $E[p^{*}]$ in each cell of Figure 2 corresponds to one of the combinations of missingness probabilities. The trial size is fixed at $n=200$, and the true probabilities of success in this example ($p_{0}=p_{1}=0.9$) are unrealistic in a healthcare setting, but are chosen to show the impact of missing data on allocations in an extreme case. A more comprehensive simulation study is given in Section 3.3, including scenarios under the alternative.

As a comparison, fixed randomization always allocates approximately half of the patients to the experimental arm ($E[p^{*}]=0.5$), regardless of the missingness probabilities. Similarly, the values of $E[p^{*}]$ for TTS under different probabilities of missingness are only slightly affected, as shown in Figure 2. However, this is not the case for CB and UCB, where allocations will be largely affected in the presence of missing data. Even though our assumption of MAR means that the missing data is non-informative, the corresponding impact on allocation results seems to be predictable if we know which arm has more available responses (equally fewer missing responses). To be specific, CB selects the experimental arm when this provides relatively more responses. Approximate 63% patients are assigned to the arm $k=1$ when $(p_{0}^{m},\ p_{1}^{m})=(0,\ 0.5)$. In contrast, UCB assigns approximate 34% patients to the arm $k=1$ in the same case with $(p_{0}^{m},\ p_{1}^{m})=(0,\ 0.5)$. One concern is that under the null, this can falsely promote the idea that the experimental arm (e.g., a new drug) is better because more patients are assigned to it and hence it will have relatively more observations (or vice-versa).

In clinical practice, another key metric of interest is the expected number of successes (ENS), namely, the oracle version based on the observed as well as the missing responses. Since in practice, ENS is the expected value of a quantity that will never be fully observed in the presence of missing data, the actual observed number of successes (ONS) might be more relevant to explore. Appendix F and Appendix G illustrate the simulation results for ONS under the twelve scenarios in Section 3.3. Since large numbers of missing values result in fewer successes, equal missingness always results in lower ONS values than missingness that occurred in one arm.

In scenarios under the alternative, the impact of missing data in the two arms is distinguishable from each other, and missing data in the experimental arm ($p_{1}^{\text{m}}>0$) is a more serious problem. Across different algorithms in a given scenario, the impact of missingness in the experimental arm (the red lines in Appendix G) on the ONS varies across the algorithms. For the explorative algorithms, including randomized (i.e., TTS and RTS), semi-randomized (i.e., RBI and RGI), and deterministic algorithms (i.e., GI and UCB), more assignments to the arm with missing data are expected as discussed above. However, the ONS decreases dramatically with larger probabilities of missing data. In extreme cases with $p_{1}^{\text{m}}=0.5$, we could even see smaller ONS in these algorithms than in FR. This indicates that assigning more patients to the experimental arm (due to missing data in this arm) cannot compensate for the missed observations. On the contrary, exploitative algorithms (i.e., RPW, CB, and RandUCB) will assign fewer patients to the arm with missing data, which is less likely to be incorrectly selected as the superior arm. It is interesting to see that the trend of decline of ONS with larger values of $p_{1}^{\text{m}}$ is far less dramatic than the explorative algorithms and even FR. This is reasonable considering that incorrect selection of the inferior arm as a result of the missing data could also lead to successful outcomes when $p_{0}$ is large. In the extreme case with $p_{1}^{\text{m}}=0.5$, we could even see ONS in these algorithms larger than that in FR. This again encourages us to carefully consider the implementation of bandit algorithms in the presence of missing data.

Figure 5 shows the simulation results of $E[p^{*}]$ for scenarios under the null both with and without mean imputation for missing data. We use solid lines to represent the results without mean imputation, while dashed lines represent the results with mean imputation. For equal probabilities of missing data per arm, the results of $E[p^{*}]$ are hardly affected by missing data. That is, approximately half of the patients are assigned to the experimental arm on average, and the mean imputation approach does not make any differences. In the cases of missingness in only one arm, imputation works differently in terms of the inherent exploitation-exploration trade-off and specific scenarios, as discussed below.

• •

  Exploration: more explorative algorithms, including randomized algorithms (i.e., TTS and RTS), semi-randomized algorithms (i.e., RBI and RGI), and deterministic algorithms (i.e., UCB), assign more patients to the arm with missing data. Mean imputation could largely solve this problem, and this applies across all scenarios (S1 (0.1, 0.1) – S5 (0.9, 0.9)), with the exception of RTS in S5 (0.9, 0.9), where the exploitative nature dominates the explorative nature as explained in Section 3.3.

• •

  Exploitation: In scenarios with small $p_{k}$ (i.e., S1 (0.1, 0.1) and S2 (0.3, 0.3)), there is no early selection. In this case, we observe a similar but limited impact of missingness as in the case of explorative algorithms. That is, there are more allocations in the arm with missing data. Consequently, mean imputation could help with allocation skew in the way it works for the explorative algorithms. However, this is not the case under large $p_{k}$ (i.e., S4 (0.7, 0.7) and S5 (0.9, 0.9)), where an early selection occurs and the algorithms exhibit great determinism in the allocation procedure. In this case, the impact due to missing data cannot be mitigated by mean imputation, and sometimes it even exaggerates this impact. For instance, GI assigns fewer patients to the experimental arm with imputation for $p_{1}^{\text{m}}$ in S5 (0.9, 0.9), which is even worse than without imputation.

Figure 6 illustrates simulation results of $E[p^{*}]$ for scenarios under the alternative both with and without mean imputation for missing data. In general, since more patients are required to make the right allocation decision (i.e., select the superior arm) under the alternative, relatively fewer patients are assigned to the experimental arm in the presence of missing data when compared with results in a same scenario without missing data (as discussed in Section 3.3.3).

• •

  Exploration: the impact of missing data could largely be mitigated for randomized (i.e., TTS and RTS), semi-randomized (i.e., RBI and RGI) and deterministic algorithms (i.e., UCB) as for scenarios under the null in Figure 5. One exception is RTS in scenario S12 (0.8, 0.9), where it exhibits a more exploitative nature due to the fixed tuning parameter.

• •

  Exploitation: mean imputation does not work well to mitigate the impact due to missing data, especially when there is an early selection with larger $p_{k}$. In this case, missing data occurring in the experimental arm is a serious problem with a substantial reduction of assigned patients to this arm. GI is a special case that is less likely to be affected by missing data across all of these scenarios. A particular concern with GI is that mean imputation in a scenario with large $p_{k}$ (S10 (0.6, 0.9) - S12 (0.8, 0.9)) could even greatly exaggerate the impact of missing data. In S12 (0.8, 0.9), with the existence of a large proportion of missing data ($p_{m}=0.5$ or $p_{1}^{m}=0.5$), approximately 90% of patients will be assigned to the experimental arm, while this drops to only 80% after imputation.

  

The implemented mean imputation approach is based on the currently estimated probabilities of success $\hat{p}_{k,t}$, which is known to be biased in the context of adaptive sampling [67, 17, 46, 57]. Villar et al.[67] empirically demonstrate the presence of negative bias of the sample means for a number of multi-armed bandit algorithms in a finite sample setting via a simulation study. Nie et al. [46] formally provide two conditions called ‘Exploit’ and ‘Independence of Irrelevant Options’ (IIO) under which the negative bias of sampling mean exist. Shin et al.[57] provides a more general and comprehensive characterization of the sign of the bias of the sample mean in multi-armed bandits, which discuss the same context as ours (adaptive sampling in finite sample) and some other cases (adaptive stopping and adaptive selection).

To interpret the results of using mean imputation of missing data in this setting, the magnitude of the bias matters more than the sign of the bias. Bowden and Trippa [17] derived an exact formula to quantify the bias for randomised data dependent rules in a finite sample as shown in Eq (1). This simple characterisation indicates that the bias increases in magnitude as the dependency of $\hat{p}_{k,t}$ and $N_{k,t}$ increases. For this reason, FR guarantying a zero covariance between these two is expected to have zero bias of sample mean estimate. In contrast, in the common case where optimistic adaptive randomization is used to direct more allocations towards arms that appear to work well, $N_{k,t}$ will be variable and positively correlated with $\hat{p}_{k,t}$. Notice that the derivation of the bias in [17] applies to randomized algorithms, while [57] then extends this formula to more general cases of MABP (i.e. non-randomized algorithms).

Consequently, we could expect a larger negative bias under the exploitation feature where there is a large covariance between $\hat{p}_{k,t}$ and $N_{k,t}$ because of the rather myopically ‘optimistic’ sampling behaviour. In contrast, algorithms with more exploration features will see relatively smaller bias and be less reactive to current mean estimates. This aligns with the simulation results in Fig 4 in [67]. Similar simulation results for bias of the investigated algorithms in this paper are attached in Appendix L for scenarios under the null and in Appendix M for scenarios under the alternative. It is substantially more complicated to discuss the negative bias of treatment effect estimates accounting for the three different missing data combinations. However, the first intuitive conclusion we can make is that larger bias is expected in algorithms with a great amount of short term exploitation. For instance, CB and RandUCB show large negative bias in all scenarios. RTS and GI seem to be more biased when the treatment effect is larger (e.g., S4 (0.7, 0.7) – S5 (0.9, 0.9) and S9 (0.4, 0.6) – S12 (0.8, 0.9)). The magnitude of the negative bias is relatively small in TS, UCB, RBI, and RGI, which are relatively more explorative within the size of the experiment. Further investigation of how the bias varies between the control and treatment arms (under the alternative), as shown in Appendix M, is another interesting direction for research for in the future.

Consequently, for more explorative algorithms, a single success or failure does not have a large impact on the value of $I_{k,(t+1)}$ or $\pi_{k,(t+1)}$ of the subsequent allocation. Besides, the negative bias of $\hat{p}_{k,t}$ is relatively small for these algorithms. Thus, mean imputation based on $\hat{p}_{k,t}$ could work to mitigate the impact due to missing data. In contrast, for the exploitative algorithms, an early selection could be substantially affected by a single success or failure. In addition, the negative bias of $\hat{p}_{k,t}$ is relatively large in these cases. As a consequence, imputation based on an inaccurate estimate $\hat{p}_{k,t}$ may fail to mitigate the impact of missing data on exploitation. In other words, mean imputation with missing data replaced by a single value does not work for more short term exploitative algorithms that are highly sensitive to the success or failure of each allocation.

We also tried conducting imputation in two settings: 1. with a large initial value $\hat{p}_{k,0}=0.9$ (see Appendix H and Appendix I); and 2. only after the first observation (see Appendix J and Appendix K). In either of these cases, the problem of biased estimates lead to undesirable characteristics of $E[p*]$.

Since the simple mean imputation based on biased estimates works differently under exploitation and exploration features, some adjustments of the balance of the exploration-exploitation trade-off might help. For instance, imputation for missing data might work for RandUCB with a different turning parameter (e.g., using a larger value of $M$), which could introduce more ‘randomization’. Besides, the idea of an additional perturbed component to the current estimate of the reward provides a similar way of thinking about exploration. In this sense, a randomized version of deterministic algorithms (i.e., RBI to CB, RGI to GI and RandUCB to UCB) should be amenable to an imputation approach. Apart from this, taking uncertainty into account in the computation of $I_{k,t}$ also supports exploring both arms, and the idea of deterministic algorithms GI and UCB aligns with this when compared with the myopic and greedy algorithm CB. In these cases, a simple mean imputation could work for the impact of missing data. This idea of more exploration in deterministic algorithms has gained popularity in related domains [61, 2, 39].

Given the problem of negative bias of the treatment effect estimates, there have been a number of proposals in the literature showing to obtain unbiased or bias-reduced estimates. Nie et al. [46] explore data splitting and a conditional MLE as two approaches to reduce this bias, using considerable information about (and control over) the data generating process. Meanwhile, Deshpande et al. [25] use adaptive weights to form the ‘W-decorrelated’ estimator, a debiased version of OLS. They attempt to use the data at hand, along with coarse aggregate information on the exploration inherent in the data generating process. In addition, Dimakopoulou et al. [26] propose the Doubly-Adaptive Thompson Sampling, which uses the strengths of adaptive inference to ensure sufficient exploration in the initial stages of learning and the effective exploration-exploitation balance provided by the TS mechanism. In this paper, we did not try these novel debiasing approaches to obtain unbiased estimates for imputation. However, these proposals provide natural future directions to improve the performance of imputation in the presence of missing data.

In conclusion, mean imputation could reduce the problem of oversampling the arm with more missing data, which is a result of the explorative nature of some algorithms. However, it does not work for the problem of undersampling the arm with more missing data in the case of short term exploitative algorithms. The reason is that for these algorithms that perform differently in various scenarios, the impact of missing data varies according to this sampling behaviour. Since information about the true scenario is not accessible in reality, it is hard to use a simple mean or some other single imputation approach to mitigate the impact of missing data.