Debiased Machine Learning and Network Cohesion for Doubly-Robust Differential Reward Models in Contextual Bandits

Thank you for your feedback: we address your mentioned weaknesses and questions.

Weaknesses

1. Thank you, we have revised the paper to incorporate these.
2. The primary technical contribution is the use of double machine learning. By explicitly modeling the baseline reward, the sub-Gaussian variance factor converges to terms that depend only on the model noise and propensity weights, but where the dependence on the mean reward goes to $0$ with the number of stages.

Questions

1. Correct.
2. The theory behind DML requires a condition called "overlap" where the treatment assignment probabilities have to be bounded away from zero and one. This rules out deterministic rule selection (e.g., UCB), so Thompson sampling is a clear choice. Furthermore, in mobile health, it is common to analyze the study results after applying a bandit algorithm. [1] describes the standard analysis. The goal is to estimate "causal excursion effects." These effects quantify what would happen if we followed a policy up until time $t$ and then deviated from it. Estimating them also requires overlap. Otherwise, we would encounter scenarios in which we have no data to estimate deviations from the policy because the policy is followed deterministically.
3. We apologize for lacking clarification on the terms we used, and we added the following to the updated manuscript: "The term baseline reward' refers to the reward observed under arm zero, where individuals are randomized to not receive any treatment." Modeling this baseline reward is crucial because it has the potential to substantially decrease the size of resulting confidence sets for the causal parameter of interest. This, in turn, enhances the precision of information available for decision-making. Intuitively, this reduction occurs because the signal-to-noise ratio effectively decreases; while the signal remains consistently estimated, the residual variance becomes smaller with an accurate baseline model. In response to your follow-up question, it's important to note that the setting we are considering here is not particularly closely related to conservative bandits. In our context, the "baseline reward" is defined under one of the multiple treatment options rather than representing the "worst-case scenario". Consequently, under certain circumstances, it is reasonable to expect a higher reward under no treatment allocation.
4. No quite, we consider the history up until stage k.
5. We agree that this requires further clarification. With sample splitting, there is a chance that the random assignment may lead to reduced predictive capabilities of any single baseline reward model. When building predictions for a particular fold, the training set contains all other samples. Thus, a single split is unlikely to dominate the prediction performance. As the stages grow in size, the number of samples per split is large enough that the issue is not seen empirically in our synthetic and real-world experiments. In the main text, we now re-emphasize the alternative approach of Option 2 where we update predictions in an online manner.
6. The technical challenges are: first, the confidence ellipsoids depend on the sub-Gaussian variance factor of the pseudo-reward and need to be derived for the DML pseudo-reward. Second, two results in (Abbassi-Yadkori et al. 2011) need to be re-proved: the first is Lemma 7, the linear predictor bound used as a key step to derive the final regret bounded. It requires handling the fact that our regularized least squares estimate now uses our DML pseudo-reward instead of the observed reward. The second, proposition $1$, requires care as we are doing weighted regularized least squares. The original version required by (Abeille et al. 2017) requires an upper bound on the sum of squared norms, but applying (Abbassi-Yadkori et al. 2011) only gives us an upper bound on the sum of weighted squared norms. In order to derive the needed bound, we use a standard mobile health assumption that the probability of no treatment is upper and lower bounded (Greenewald et al. 2017) and then apply (Abbassi-Yadkori et al. 2011) to obtain our version of their results that have an upper bound that depends on $c>0$, the lower bound on the weights. Finally, the regret bound itself needs to handle the fact that we have stages with multiple individuals (increasing by one) per stage. This leads to a sum over stages and participants within stages of the difference between RLS and TS (and RLS and true) linear predictors. By some manipulation and an application of Cauchy Schwartz, we see a sum of $\frac{1}{k}$ over stages, which leads to the harmonic number. The dimensionality shows up as the sum of squared norms is bounded by a log ratio of determinants, which is bounded by terms involving the dimensionality.

[1] Boruvka, Audrey, et al. "Assessing time-varying causal effect moderation in mobile health." Journal of the American Statistical Association 113.523 (2018): 1112-1121.

Questions

1. There are two important characteristics of mHealth settings: 1) The combination of having a baseline `do nothing' action and a non-linear baseline reward (e.g. context outside of the bandit action may affect step count, such as the weather) (Greenewald et al. 2017). Making too many recommendations can lead to burden and habituation for users, and thus in mHealth we would like to not make recommendations at every time step. Our DML based approach allows us to explicitly model the baseline rewards (e.g. how weather affects step count independent of action). 2) Time-varying effects. For instance, at the beginning of a study participants may be more receptive to recommendtations than towards the end. By including a penalty that encourages similarity between time points in addition to the standard similarity between users, we can model these time-varying effects.
2. Thank you for bringing up this concern. In the main text on Page 4, we outlined two approaches for learning the conditional expectation model $f_{t}(s,a)$. Option 1 involves sample splitting across time and participants, assuming additive i.i.d. errors and no delayed or spill-over effects. This assumption is plausible in the mHealth setting, where we do not anticipate an adversarial environment. Option 2 relaxes the i.i.d. error assumption by updating $f_{t}(s,a)$ using observed history data in an online fashion, keeping estimated pseudo-outcomes fixed at each stage. Consequently, the new observations become conditionally independent of the history data. In this context, we can leverage subsampling techniques introduced in (Chen et al. 2022) as an alternative method to estimate pseudo-outcomes, avoiding the need for sample splitting.
3. The main contribution for DML in Theorem 1 is in the $\beta_K$ and $\gamma_K$ terms, which represent the regularized least squares and Thompson sampling high probability ellipsoids, respectively. Each of these depend on the sub-Gaussian variance factor, which is smaller due to using the doubly robust DML pseudo-reward. In the setting of (Greenewald et al. 2017), this variance factor always depends on the mean reward. In our setting, the terms involving the mean reward go to $0$ with the number of stages.

Thank you for your helpful feedback. We address your comments below.

Weaknesses

1. We realize that the introduction may not sufficiently establish the connection between mHealth contextual bandits. We have incorporated the following paragraph into the updated manuscript: "Mobile health (mHealth) and contextual bandit algorithms share a close connection in the realm of personalized healthcare interventions. mHealth leverages mobile devices to deliver health-related services, making it a powerful tool for real-time monitoring and intervention. Contextual bandit algorithms, on the other hand, are a class of machine learning techniques designed to optimize decision-making in situations where actions have contextual dependencies. The synergy arises when mHealth applications deploy contextual bandit algorithms to tailor interventions based on individual health data and context. For example, in a mobile health setting, a contextual bandit algorithm might dynamically adapt the type and timing of health-related notifications or interventions based on the user's current health status, historical behavior, and contextual factors like location or time of day.'
2. We restate the list here: "bandit algorithms must account for (1) the time-varying nature of the outcome variable, (2) nonlinear relationships between states and outcomes, (3) the potential for intervention efficacy to change over time (due, for instance, to habituation as in Psihogios et al. (2019)), and (4) the fact that similar participants tend to respond similarly to interventions (Künzler et al., 2019)." For (1), an example would be that step counts and activity more generally could depend on weather, even when no action is taken [1]. Explicitly modeling the baseline via DML would incorporate this into our model. For (2) the activity dependence on the weather may be non-linear. Using DML allows us to use a non-linear baseline. For (3), we cited an example, but it relates to our penalization encouraging similar effects for similar time points. (4) relates to our penalization encouraging similar effects for similar users.
3. We cite it on the top of page 3, but we agree that it would be helpful to cite it at its earliest reference in the main paper (top of page 2).
4. We mention these papers in the graph bandits section. These use a graph that encourages similarity between similar users, while our approach encourages similarity both between similar users and similar time points.
5. Thank you for pointing this out. Other papers have used doubly robust estimators, but for slightly different purposes. We use a doubly robust estimator that allows us to debias and lower variance from explicitly modeling the mean reward including the baseline. Other papers [2, 3] use a doubly robust estimator to obtain novel regret bounds in the linear and generalized linear settings, respectively. However, they do not treat the mHealth setting where there is the possibility of taking no action. We will add these to our related work section.
6. We thank the reviewer for raising this concern and apologize for the amount of notation. To address the heavy amounts of notation, we will add a notation glossary to the appendix. As Theorem 1 is important for understanding performance of our algorithm, we have added Remark 1. Below find the exact language added.

Remark 1 Observe that the regret bound is sublinear in the number of stages and scales only with the complexity of the differential reward $d$, not the complexity of the baseline reward $g$. As the second term scales with $\sqrt{K}$, for large $K$ we can focus on the first term which scales $O \left( \sqrt{c \cdot d \cdot \log^2(K) K} \right)$. Prior work scales sublinearly with the number of decision times $T$ as they assume either a single contextual bandit ($n=1$) or a fixed number of individuals~$n$. Action centering scales as $O(d^2 \sqrt{T \log(T)})$ while Graph Bandits scale as $O(\sqrt{\tilde d n T \log(T)})$ where $\tilde d$ is the complexity of the joint baseline and differential reward model. Interestingly, at stage $K$ we see $n=K$ individuals over $n=K$ decision times (with different number of observations per individual); however, we do not see a regret scale with $\sqrt{nT} = K$. Instead we only receive an extra $\log(K)$ factor reflecting the benefit of pooling on average regret.

[1] Turrisi, Taylor B., et al. "Seasons, weather, and device-measured movement behaviors: a scoping review from 2006 to 2020." International Journal of Behavioral Nutrition and Physical Activity 18 (2021): 1-26. [2] Kim, Wonyoung, Gi-Soo Kim, and Myunghee Cho Paik. "Doubly robust thompson sampling with linear payoffs." Advances in Neural Information Processing Systems 34 (2021): 15830-15840. [3] Kim, Wonyoung, Kyungbok Lee, and Myunghee Cho Paik. "Double doubly robust thompson sampling for generalized linear contextual bandits." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 7. 2023.

Thank you for your helpful feedback. We address your listed weaknesses and comments.

Weaknesses

• We appreciate the feedback. We noticed that there was a bolding issue for the title, which we have fixed. If there are other specific issues you notice, we would be happy to address them.

• We restate the list of mHealth concerns here and connect them to our model: "Bandit algorithms must account for (1) the time-varying nature of the outcome variable, (2) nonlinear relationships between states and outcomes, (3) the potential for intervention efficacy to change over time (due, for instance, to habituation as in Psihogios et al. (2019)), and (4) the fact that similar participants tend to respond similarly to interventions (Kunzler et al., 2019)." For (1), an example would be that step counts and activity more generally could depend on weather, even when no action is taken (T. B. Turrisi et al. 2021). Explicitly modeling the baseline via DML would incorporate this into our model. For (2) the activity dependence on the weather may be non-linear. Using DML allows us to use a non-linear baseline. For (3), we cited an example, but it relates to our penalization encouraging similar effects for similar time points. (4) relates to our penalization encouraging similar effects for similar users.

• Our major innovations are explicitly modeling the non-linear baseline rewards using double machine learning and encouraging similarity across time points in addition to across users. Yang et al. 2020 showed how to share information across similar users, but do not handle baseline rewards or sharing information across similar times. Tomkins et al. do pooling across users and time, but only allow for a linear baseline reward (we mention this in the related work section). Our DML approach reduces the variance of the sub-Gaussian variance factor that comes up in the regret bound through the terms $\beta_K$ and $\gamma_K$, which are the high probability confidence ellipsoid bounds for the regularized least squares and Thompson sampling estimators, respectively. The DML approach shrinks the upper bound on the size of these ellipsoids.

Questions

• This is important future work: thanks for mentioning this. However, existing approaches such as (Yang et al. 2020) make the same assumption of a known graph. We will work on this going forward.

Thank you for your helpful comments and positive assessment. We address your listed weaknesses and comments.

Weaknesses:

• In Figure 2 (left), the Valentine study outcome, namely step count, is presented after a log transformation. Therefore, the small values in the figure represent the difference between two log step counts. For instance, the DML-TS-NNR-RF algorithm achieves an average 0.035 relative expected reward. This implies that, after im- plementing our proposed algorithm, the step counts increased by $\exp(0.035) − 1 = 3.5\%$ more than what the constant randomization policy achieved. To provide further context, this translates to an additional 35 steps on top of the original 1000 steps under the constant randomization scheme within the hour following the randomized mobile notification. In the context of mobile health applications and our emphasis on the step count in the following hour as the outcome of interest, it’s typical for effect sizes to be on the smaller side. Considering this, the 3.5% increase should be seen as a positive indicator of improvement, highlighting the strong performance of our proposed method compared to other competing algorithms.
• In conjunction with the simulation study, the main text focuses on one of the real-world data applications—the Valentine Study. The results of this case study provide compelling evidence that our proposed algorithm attains significantly higher average rewards compared to the competing algorithms. Given the difference in the outcome of interest, randomization policy, participants’ enrollment scheme, and the graph construction between the IHS study and the Valentine study, we have chosen to defer the discussion of the IHS study results to the appendix for clarity.
• We agree that assessing the uncertainty is important. Since the error bars would be difficult to read in Figure 1 because there are so many methods, we instead performed pairwise comparisons regarding final (stage-125) regret. Table 1 of Appendix D shows the results. In the heterogeneous and nonlinear simulation settings (the challenging ones), our proposed methods achieve a significantly lower regret than the other methods.

Comments:

• In addition to testing whether our method worked well, we were also interested in evaluating how different aspects of the method contributed to its performance; does our method perform well due to (1) user pooling, (2) time pooling, (3) network cohesion, or (4) flexible modeling of the baseline? Including DML-TS-SU-BT allowed us to assess the contribution of user pooling. The results indicate that user pooling is beneficial (see the results for the nonlinear setting)—though, perhaps slightly less so than we expected. In practice, we recommend employing a version of our method that has distinct parameters for each user (such as DML-TS-NNR-BLM or DML-TS-NNR-BT). We recommend selecting a supervised learning algorithm that (1) can be quickly updated in an online fashion (2) performs well in cross-validation and (3) has low sample complexity. When data is being collected in an online manner, the supervised learning method could periodically be re- evaluated via cross-validation.
• Thank you for bringing up this concern. We apologize for any confusion in not clearly explaining the results and connecting them to practical scenarios. Building upon the details provided in our response to your first weakness listed, the observed gap can also be ascribed to the potential simplicity of the baseline generating mechanism, possibly being a linear model or closely resembling one. In such cases, the perceived benefits may not seem to be substantial compared to other competing algorithms. Nevertheless, the significant increase in cumulative reward indicates the robustness of our algorithm and its superior performance in unknown environments