Bayesian adaptive algorithms for locating HIV mobile testing services

We used a computer simulation to compare the performance of three strategies for targeting mobile HIV testing services. We created a hypothetical city consisting of contiguous geographic zones, each with its own (unobserved) prevalence of undetected HIV infection.

Over each of 180 sequential rounds of play, hereafter referred to as days or days of testing, strategies were required to choose a single geographic zone in which to conduct a fixed number of HIV tests. Strategies were permitted to observe and remember the results of their own prior testing activities and to use that information in choosing where to test in subsequent rounds.

We define a ‘tournament run’ as a fixed number of sequential days. In the main analysis, all outcome measures used to evaluate the relative performance of one strategy against another are reported over a tournament run length of 180 days. Stable estimates of these performance measures and their variance are obtained by repeating each 180-day tournament run 250 times.

We constructed a hypothetical city consisting of geographic zones on a n x n grid. For the main analysis, consisting of the base case assumptions, we assumed that there were 36 zones (i ∈ {1, …, 36}) on a 6 x 6 grid. In sensitivity analyses considering alternative data simulation settings, we varied the total number of zones between 16 and 100.

The prevalence of undetected HIV infection, establishing the initial number of infected and uninfected persons, in a given zone was simulated using the following model:

where p_i is the prevalence for zone i, β₀ is an intercept term that describes the center of the distribution of all prevalences, and ϕ_i is a value specific to zone i that determines how much zone i’s prevalence differs from the center of the distribution (large values indicate hotspots while lower values indicate cool spots or non-hotspots). For all data simulation settings, we fixed β₀ to be − 5.00, centering the distribution of prevalences on 0.007. The ϕ_i values were simulated from a multivariate normal distribution, centered at zero, with a covariance matrix that allowed for the possibility of spatial correlation depending on the choice of an associated correlation parameter (large value indicates spatial independence while small value indicates high spatial correlation). Once the ϕ_i values were generated, we standardized them (the vector centered at zero with a standard deviation of one) in order to create a distribution of prevalence values with similar center/variability across all data simulation settings and, therefore, allowing us to more accurately attribute differences in the performance of each method to changes in the underlying data assumptions. We then multiplied each ϕ_i value by an inflation factor in order to create greater/fewer hotspots depending on the data simulation setting. Finally, once ϕ_i and β₀ were selected, we calculated p_i for each zone using the inverse logit transformation and set all prevalences larger than 0.03 (the maximum hotspot value) equal to 0.03. Recognizing that not all persons with undetected HIV infection will be amenable to the offer of HIV testing, we capped the maximum prevalence of detectable HIV infection at 3%. This is slightly below the estimated prevalence of undetected HIV infection in high-risk African settings (e.g., Lusaka, Zambia). A new set of zone prevalences was generated using this framework for each of the 250 tournament runs of a given data simulation setting. Populations for each zone, m_i, were drawn from a lognormal distribution based on the population of districts in the same representative African urban area (Lusaka, Zambia). Based on these final starting values for HIV prevalence of undetected HIV infection for each zone and the populations assigned initially to them, each zone thus began the simulation with a fixed number, rounded up to integer values, of infected (p_i × m_i) and uninfected persons (m_i − [p_i × m_i]) .

The main analysis was run over 180 days of testing and is meant to reflect the real-world potential use of these methods in the daily decision-making of HIV testing providers. We used the following notation to denote some useful population levels:

The yield of HIV testing, X_i(t), follows a binomial distribution with success probability UP_i(t). Implicit in this formulation was the assumption that HIV tests are conducted only on persons with unknown HIV infection. In reality, a great deal of HIV testing takes place among persons whose infection status is already known. Our simplifying assumption could be relaxed to include repeat testing and to produce an across-the-board reduction in the effectiveness of screening; however, this would have no impact on the relative yield of different strategies (our performance measure of interest). We also assumed that the population in a given zone greatly exceeds the number of HIV tests that can be performed in that zone in a single day. This permitted us to make the additional simplifying assumption that sampling for HIV on any given day occurs ‘with replacement’. This assumption too could be relaxed without overly complicating the analysis but would not likely have a material impact on the performance results of interest.

At the end of each day, the prevalence of HIV infection among persons whose status is unknown, UP_i(t), was updated to account for three different considerations. First, ‘shelf life’, where the reliability and relevance of a negative result declines with the passage of time. We assumed that observed uninfected individuals eventually return to the pool of unobserved uninfected individuals. Second, ‘new arrivals’, where, as described above, we permitted the arrival of persons with unobserved HIV infection status (both infected and uninfected). Finally, ‘new HIV testing’, through which, if m HIV tests were conducted in zone i on day t, the unknown prevalence the following day was updated as follows:

TS is an adaptive algorithm whose actions aim to maximize expected value based on random sampling from prior probability distributions on the prevalence of undetected HIV in each zone. These prior distributions are themselves the ex post result of updates based on previous rounds of observation. The user seeds the algorithm with initial probability distributions for the prevalence of undetected HIV in each zone at time 0. At the start of each day, TS samples randomly from its current probability distribution for each zone. It then elects to conduct testing in whichever zone yields the largest realized value (note that the zone selection process is based on random sampling from prior probability distributions – the algorithm’s ‘belief structure’ – and not from any actual HIV testing in a zone; this indirect selection mechanism ensures that every zone has a non-zero probability of being chosen for testing on any given day while, at the same time, ensuring that a zone will be selected with a probability that is proportional to the strength of the algorithm’s beliefs about how much undetected HIV infection exists in that zone). If a zone is selected for testing on a given day, the results of those testing activities will be employed to update the algorithm’s prior beliefs for that zone; the posterior distribution that results from that updating process will become the sampling distribution for zone selection on the subsequent day.

We used a Beta(α_i, β_i) distribution to describe TS’s beliefs about the prevalence of undetected HIV infection in zone i. The Beta, a continuous distribution on the interval (0, 1), is a natural choice for this purpose; first, because it is conjugate to the binomial distribution (i.e., a Beta prior and Binomial likelihood will yield a Beta posterior) and, second, because its two parameters are easily interpreted as ‘total observed positive HIV tests’ and ‘total observed negative HIV tests’, respectively. Thus, if m new HIV tests yield x new cases detected in zone i, the posterior probability will follow a Beta(α_i + x, β_i + (m–x)) distribution (see Additional file 1 for more details).

Conditional autoregressive (CAR) models are used to account for spatial correlation in areal data when what is observed in neighboring regions is assumed to be more similar than observations occurring at larger distances [6]. They can be incorporated into Bayesian hierarchical models and the Besag York Mollié (BYM) framework used here employs an intrinsic CAR (ICAR) distribution (improper version of the CAR model) for the spatial random effects and exchangeable, normally distributed random effects to account for non-spatial heterogeneity in the data [7].

Similar to TS, our BYM modeling strategy begins the sampling process by assuming independent Beta(α_i, β_i) prior distributions for the prevalence of undetected HIV infection in each of the zones. During an initial ‘learning’ period, the BYM model proceeds in the same way as TS, selecting a zone for testing on a given day by sampling from its current probability distribution for each zone’s prevalence of undetected HIV prevalence and then choosing the zone that yields the largest realized value. Using TS, when the number of completed days is low, zones are selected almost at random. This is because TS assumes an uninformative, independent Beta(1, 1) prior distribution for the prevalence of undetected HIV infection in each zone and little new information across all zones is collected at the beginning of the simulations. As a result, on average, we observe a mix of low and high prevalence zones that are used to fit the BYM model for the first time. At the end of the learning period, the BYM model is fitted to the total set of collected data from each individual zone (number of identified infected individuals versus total number of sampled individuals in each zone). The choice of 10 zones for the initial learning period was made to ensure we had a reasonable number of spatial data points with which to fit the BYM model. For instance, it would be impossible to learn about the spatial correlation in the data using only data from a single spatial region. Once the BYM model is fitted to the current set of observed data, the marginal posterior predictive distribution of the underlying prevalence of undetected HIV cases at each zone is obtained via Markov chain Monte Carlo (MCMC) posterior sampling. We then randomly select a single value from each of these zone-specific distributions and identify the zone that corresponds to the largest value. This zone is selected for sampling on the subsequent day. This process is then repeated until the end of the simulation time period.

Unlike TS, which only gathers information as it visits a given individual zone, the BYM model can leverage inter-zone correlation to take what it observes in one zone and use that information to draw useful inferences about the prevalence of undetected HIV in neighboring zones. The model for the underlying prevalence at each zone is a function of a shared intercept, a spatially correlated random effect (ICAR distribution), and an exchangeable, normally distributed random effect (logistic regression model assumed). Because the intercept is shared across all zones, as data are gathered about a particular zone, the model is simultaneously learning about the value of the intercept and, therefore, about all zone prevalences. Similarly, because the spatial random effect assumes similarity between neighboring zones a priori, as data are gathered on a particular zone, the model is also learning about that zone’s neighbors (and beyond). The exchangeable random effect ensures that all variability in the prevalences is not attributed to spatial similarity and therefore prevents the model from oversmoothing the data. In the case of no spatially correlated variability and complete independence between data from the different zones, the BYM model will collapse to something very similar to TS (see Additional file 1 for more details).

For purposes of benchmarking, we sought to establish a credible upper-bound on the number of new HIV cases that any search strategy could possibly detect. To that end, we developed the Clairvoyance strategy, an algorithm that chooses to test in whichever zone has the greatest underlying prevalence of undetected HIV infection on any given day. Clairvoyance has access to perfect current information about new arrivals/departures, about individuals whose previous test results have exceeded their shelf life, and about the results of its previous testing activities. This permits it to select the most promising zone for testing on any given day. We emphasize, however, that it has no special knowledge about the HIV-infection status of any individuals selected for testing within that zone. Like any other strategy, it samples with replacement within whichever zone it selects.

Initial parameter values as well as those used in the sensitivity analyses are described in Tables 1 and 2. Our goal was to understand the performance of strategies under a broad variety of plausible data simulation settings. We therefore defined parameter ranges that reflected observations drawn from a multiplicity of international settings. Areas differ in terms of population size. Numbers of infected and uninfected persons in a zone were assigned via random realizations from a lognormal distribution (rounded to the nearest integer) that was itself estimated using 2010 census data on the number of adults aged 15–59 years living in urban wards of Lusaka, Zambia [8]. We explored values ranging from less than 0.5% to 3.0%, for the underlying prevalence of undetected HIV infection, reflecting zones with lower numbers of undetected individuals and zones that can be considered hotspots. The prevalence of undiagnosed HIV infection in some settings, including sub-Saharan Africa, can be larger than 3%. For instance, 12.3% of Zambian adults (15–59) are HIV positive, but 32.7% of them do not know their serostatus, and thus 4% of adults are still undiagnosed [9, 10]. However, we chose the 3% ceiling of undetected HIV prevalence in this simulation to represent a fraction of this population, as not all undiagnosed individuals will necessarily come forward for testing.

We considered different rates of population movement, setting in-migration of new HIV-negative individuals at an annual 3.4% of a zone’s population in the main analysis, so that the daily number of new HIV-negative individuals entering a zone was 3.4% times the zone’s population divided by 365 days. The main analysis data simulation setting was derived from projections from the 2010 Zambian census for Lusaka [8]. In the sensitivity analyses, we doubled this number in each zone to reflect fast-growing settings but we also considered a case with half of the base case values and with no in-migration in sensitivity analyses. In the main analysis, zones were assigned HIV incidence rates based on annual incidence rates for Lusaka and daily new infections took the annual incidence figure (0.66%), multiplied it by the population of each zone and divided it by 365 days [9]. In the sensitivity analyses, we doubled this figure to represent faster growing epidemics, and also considered a case with half of the base case values and with no new infections. Finally, we also examined the case where no new HIV-negative and no new HIV infections occurred daily in each zone.

Other HIV testing program parameter ranges were selected to correspond roughly to values reported in the literature. We relied on two South African studies to assume that a mobile testing service could conduct m = 25 tests in a given zone on a given day; daily values ranging from 10 to 40 tests were considered in sensitivity analyses [11, 12]. We further assumed that individuals who are found to be uninfected return to the unobserved uninfected pool after 45 days, with values ranging from 10 to 90 days in the sensitivity analysis [13, 14]. Finally, we conducted the main analysis over 180 days (sensitivity analyses range, 90–365 days), reflecting our assumption that decision-makers might devote a half year to experimenting with new approaches to deploying HIV testing resources.

In the main analysis, the spatial correlation was set in the ‘low’ setting, where we defined ‘low’ as the correlation between prevalences from the two closest zones (i.e., based on distance between zone centroids) equal to 0.20. Spatial correlation was defined as a function of distance between zone centroids, with increasing distance leading to decreasing correlation. In subsequent sensitivity analyses, we varied the spatial correlation as follows:

In addition, for the main analysis, we scaled the ϕ_i value by 1.80 (on average 20% of the zones were hotspots) while, for sensitivity analyses, we increased this value to 2.90 (30% hotspots) to create more extreme prevalence values and decreased it to 1.20 (10% hotspots) to create less variability (i.e., fewer hotspots) in the distribution of prevalences across all zones.

Both the TS and BYM strategies require the user to specify their ‘initial beliefs’ – that is, the probability distributions for the prevalence of undetected HIV infection in each zone at t = 0. For TS, we applied uniform(0, 1), uninformative Beta(1, 1) distributions to all zones. This reflected the highly conservative assumptions that virtually nothing is known about the starting prevalence of HIV infection in any of the zones. For the BYM strategy, we also assumed Beta(1, 1) prior distributions for the zone prevalences at the outset of the learning period. The intercept term was given a N(0, 2.85) prior distribution while the variance parameters associated with the ICAR and exchangeable random effects were each assigned inverse-gamma(3, 2) prior distributions. The prior distribution for the intercept resulted in an approximately uniform(0, 1) prior distribution for zone prevalences under the assumption of no additional variability.

To ensure we could statistically differentiate the performance of each of the methods, the tournament was run 250 times for each of the data simulation settings. Performance statistics reported in the Results section below represent averages across these 250 tournament runs as well as an examination of the absolute number of new diagnoses (minimum, first quartile, median, third quartile, and maximum) detected during these 250 tournament runs by each strategy. A strategy was deemed to have outperformed another in a head-to-head comparison if it detected a greater number of new cases in at least 55.25% of the 250 tournament runs. This significance value represents the threshold for a difference in proportions with p < 0.05 in a one-sided Z-test. We also examined the difference in the mean number of cases detected by each strategy, assessing significance with a one-side Welch’s t test.

Figure 1 shows a representative 6 × 6 grid from the main analysis, consisting of 36 zones with low spatial correlation in the data and with 30% of the zones being hotspots. Across the 250 tournament runs, the average proportion of hotspots was roughly 20%. While a new grid of prevalences for the zones is generated for each set of 250 tournament runs of a given data simulation setting, Fig. 1 is meant to offer an example of what the underlying structure of probabilities looks like at t = 0 before the 180 days of testing begin. In each of the 250 tournament runs, all strategies begin with the same underlying grid of prevalences. Figure 2 shows the estimated prevalence of undetected HIV infection assumed by each strategy in the main analysis at five time-points (t = 5, 45, 90, 135, and 180 days). Figure 2 shows that the TS and BYM estimates of the underlying prevalence of undetected HIV infection shifts over time but in different ways. BYM’s estimation of the underlying prevalence of undetected HIV infection among the zones declines over time, but the algorithm maintains estimates that are higher than those of TS across all 180 days of testing in more zones than TS. With TS, estimates of prevalences among the zones, particularly non-hotspots, declines earlier on. This can be seen in the shift from reds to blues in the top panel (TS) of Fig. 2 in contrast to the middle panel where reds still predominate (BYM) as the number of days of testing in the simulation mounts. The Clairvoyance strategy in Fig. 2 has perfect information on the prevalence of undetected HIV infection on each day and thus its ‘estimate’ represents the actual values on the grid and impact over time of new, incident HIV infections, new HIV-negative in-migration, the ‘shelf life’ of HIV-negative test results, and its own success at finding new cases of HIV infection. Figure 3 shows the aggregate visits to each zone up until each of the same five time-points for all strategies. BYM visits and exploits hotspots more often than TS over time (conversely spending less time in non-hotspots than TS), while TS continues to explore more zones, even those that are non-hotspots, over the course of the 180 days. Clairvoyance visits all the hotspots of 3.00% prevalence in rotation throughout the 180 days and spends no time elsewhere. Clairvoyance does not even visit hotspots with slightly lower prevalence values (e.g., 2.70%). We provide versions of these three figures for data simulation settings with medium and high spatial correlation as additional files for readers interested in seeing the performance of the three strategies under these conditions (Additional file 2: Figure S1–S6).

Figure 4 shows the key results for the main analysis, indicating the absolute number of new diagnoses detected by each strategy over 180 days (minimum, first quartile, median, third quartile, and maximum) in 250 tournament runs of the simulation. Clairvoyance outperformed all other strategies in overall mean number of new HIV diagnoses detected, identifying 141.87 (SD 11.83) new cases over the course of the 250 tournament runs, while TS uncovered 78.24 (SD 11.44) and BYM found 92.59 (SD 12.37). These results are also shown in Table 3 and Additional file 3: Table S1. The differences in the mean number of cases detected over 250 tournament runs between TS and BYM, TS and Clairvoyance, and BYM and Clairvoyance were all significant by Welch’s t test (p < 0.0001). This indicates that TS and BYM identified 55.1% and 65.3%, respectively, of the total infections detected by the Clairvoyance strategy. Finally, over the course of 250 tournament runs in the main analysis in pairwise head-to-head competition, BYM won 80% of the time over TS, with Clairvoyance winning 100% of the time against TS and BYM. These results are significant by a one-sided Z-test of a difference in proportions (p < 0.0001).

We re-evaluated all findings using the settings specified in Tables 1 and 2. The mean number (and SD) of new diagnoses detected by TS and BYM in the main analysis and in all sensitivity analyses are described in Table 3. Under every scenario we examined in sensitivity analysis, Clairvoyance detected the greatest number of new HIV-positive cases (see Additional file 3: Table S1 for mean number of new diagnoses detected by Clairvoyance in the main analysis and in all sensitivity analyses). BYM almost always outperformed TS. TS narrowly defeated BYM when we considered a smaller grid size (e.g., 4 × 4) but this margin of victory (i.e., differences in the number of new diagnoses) was not statistically significant.

Sensitivity analysis revealed that the margin of victory between TS and BYM remains small under almost all circumstances. Averaging across all sensitivity analyses, the difference in the number of cases detected between TS and BYM was just over 12 cases. By contrast, Clairvoyance’s average margin of victory over its competitors exceeded 50 cases.