RoME: A Robust Mixed-Effects Bandit Algorithm for Optimizing Mobile Health Interventions
Authors: Easton Knight Huch
Jieru Shi
Madeline R Abbott
Jessica R Golbus
Alexander Moreno
Walter H. Dempsey
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandit Algorithms
Causal Inference
Supervised Learning
mHealth
Mixed-effects Modeling
Primary area: machine_learning_for_healthcare
TL;DR: The authors propose a robust contextual bandit algorithm for optimizing mobile health interventions that leverages (1) mixed effects, (2) nearest-neighbor regularization, and (3) debiased machine learning (DML).

Abstract: Mobile health leverages personalized and contextually tailored interventions optimized through bandit and reinforcement learning algorithms. In practice, however, challenges such as participant heterogeneity, nonstationarity, and nonlinear relationships hinder algorithm performance. We propose RoME, a **Ro**bust **M**ixed-**E**ffects contextual bandit algorithm that simultaneously addresses these challenges via (1) modeling the differential reward with user- and time-specific random effects, (2) network cohesion penalties, and (3) debiased machine learning for flexible estimation of baseline rewards. We establish a high-probability regret bound that depends solely on the dimension of the differential-reward model, enabling us to achieve robust regret bounds even when the baseline reward is highly complex. We demonstrate the superior performance of the RoME algorithm in a simulation and two off-policy evaluation studies.

RoME: A Robust Mixed-Effects Bandit Algorithm for Optimizing Mobile Health Interventions
Easton Huch Department of Statistics University of Michigan Ann Arbor, MI, USA ekhuch@umich edu
Jieru Shi Statistical Laboratory, DPMMS
Madeline R. Abbott Department of Biostatistics University of Michigan Ann Arbor, MI, USA mrabbott@ume edu
University of Cambridge Cambridge, England, UK js28828cam. ac uk
Jessica R. Golbus Michigan Medicine Ann Arbor, MI, USA jgo busbuuuuumiii ch.mich... edu
Alexander Moreno
Walter H. Dempsey
Independent Researcher" alexander. ff moreno@gmail com
Department of Biostatistics University of Michigan Ann Arbor, MI, USA wdem@umic ch. edu
Abstract
Mobile health leverages personalized and contextually tailored interventions opti- mized through bandit and reinforcement learning algorithms. In practice, however, challenges such as participant heterogeneity, nonstationarity. and nonlinear relation- ships hinder algorithm performance. We propose RoME, Robust Mixed-Effects contextual bandit algorithm that simultaneously addresses these challenges via and time-specific random effects, (2) network cohesion penalties, and (3) debiased machine learning for flexible estimation of baseline rewards. We establish high-probule secbbbbbbbbilitt regret bound that depends solely on the dimension of the differential-rewart model, enabling us to achieve robust regret bounds even when the baseline reward is highly complex. We demonstrate the superior performance of the RoME algorithm in simulation and two off- policy evaluation studies.
(1) modeling the differential reward with
Introduction
Mobile health (mHealth) uses smart devices to deliver digital notification interventions to users. These notifications nudge users toward healthier attitudes and behaviors. Because mHealth applications can monitor and react to users and their environment, they offer the promise of personalized, contextually tailored interventions. In practice, achieving this promise requires bandit reinforcement learning (RL) algorithms that can accurately learn mHealth intervention effects, including how they vary by user, over time, and based on context. In this regard, contextual bandit algorithms are appealing due to strong empirical performance in other settings, their ability to customize intervention decisions based on changing contexts, and their simplicity and extensibility relative to full RL algorithms.
One unique aspect of mHealth (Greenewald et al. 2017) is the presence of a "do-nothing" action in which the mHealth app does not intervene. As mealth rewards typically involve human decision making (e.g., whether the user chooses to exercise), the distribution of the corresponding baseline reward-the reward under the do-nothing action-typically evolves in complex, nonstationary fashion as time progresses and contexts change. In contrast, the /reaiment effects-the difference in the expected value of the reward relative the do-nothing action-tert tend be much more stable
A portion of this work performed while Alexander employed Luminous Computing.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and can be adequately modeled using classical stationary models, such as linear models (Robinson 1988).
Greenewald et al. (017) introduced an action-centered contextual bandit algorithm with sublinear regret in this setting by replacing the observed reward, R₁, with a "pseudo-reward." R, where t indexes the time points. Denoting the binary action A, E {0, 1 with A, = 0 corresponding the do-nothing action, the pseudo-reward for A, can be written as
A Re
1- m
R2 (Ac - m. Te R.)
where Ny is the (known) probability of treatment assignment from the Thompson-sampling algorithm. We took additional step to derive equivalent expression (second equality), which reveals that Rg is proportional to an swverse-robabbiityy. unbiased estimate of the treatment effect regardless of the nonstationarity of the baseline outcome.
(IPW) estimator. Crucially, RG provides an
Although Greenewald et al. (2017)'s ' analysis shows sublinear regret in nonstationary settings, our simulations show that other methods can achieve lower regret over finite time horizons. The reasons include its failure to address treatment effect heterogeneity, pool information across users, and model the baseline outcome, which leads to highly variable pseudo-rewards and slow learning. We propose to generalize their method to overcome these limitations by
1. imposing hierarchical structure in the treatment effect model with shared fixed effects and random effects for users and time (i.e., a mixed-effects model),
2. efficiently pooling across users and time via nearest-neighbor regularization (NNR), and
3. denoising rewards with flexible supervised learning models via the debiased machine learning (DML) framework of ohCChrnnozu et al. (2018).
We name the resulting method ROME to highlight that is a Robust Mixed-Effects algorithm. The primary contributions are (a) the RoME method, (b) a high-probability regret bound that relies solely on the dimension of the diffcrential-rewarr model, which is typically much smaller than that of the complex baseline reward model, and (c) empirical comparisons demonstrating the superior performance of RoME in simulation and two real-world mHealth studics.
2 Related Work
Related work in statistics considers the estimation of treatment effects with longitudinal data. Cho et al. (017)) present a semiparametric random-effects method for estimating subject-specific static treatment effects. Qian et al. (2020) discusses the statistical challenges of applying linear mixed- effects models to mHealth data and shows that the resulting estimates may lack a causal interpretation.
In the bandit literature, several works address the challenge of heterogeneous users. Ma et al. (201T) introduced NNR in recommender systems using homophily principles-ssmilal similar nodes are more likely to be connected than dissimilar ones (McPherson et al. (201)) Cesa-Bianchi et al. (2013) adapted
NNR for bandit settings, improving regret. Subsequent improvements focused on scalability and algorithm modifications for stronger regret bounds (Vaswani et al., 2017 Yang et al. 2020).
Other bandit approaches explicitly address the longitudinal setting in which treatment effects may evolve over time. The intelligentpooling method of Tomkins et al. (201)) employs a Gaussian linear mixed-effects model with both user- and time-specific random effects. Hu et al. (202I) provides related approach based on generalized linear mixed effects models. Unlike approach, both methods require the (generalized) linear conditional mean model to be correctly specified.
Aouali et al. (202)) and Lee et al. 2024) also propose bandit algorithms with mixed effects; method- ologically, however, their use mixed effects differs from the above approaches and our own.
Aouali et al. (2023) employs random effects to relate treatments within categories (e.g.. movies within a genre), and Lee et al. (2024) considers the case which a single, discrete action leads to a multivariate reward that is affected by user-specific random effect. In contrast, the other approaches listed above (and our own) do not assume any relationships among the actions, and they associate each discrete action with single scalar-valuee reward in an iterative fashion.

---

Other work develops semiparametric methods that lead to sublinear regret without requiring correct specification of the conditional mean reward. Krishnamurthy et (2018) and Kim & Paik (2019) propose improvements to the approach of Greenewald et al. (2017) that lead to stronger regret bounds. Kim al. (2021] 2023) develop a doubly robust approach for both linear and generalized linear
contextual bandits. However, in contrast to Tommiiss et al. (202T). Hu et al. (202T), and our approach, these semiparametric methods are not immediately applicable to longitudinal settings.
Setting
3.1 Problem Statement
Recognizing the connection between mHealth policy learning and contextual bandit methods, we now consider contextual multi-armes bandit enviromment with one control arm (the do-nothing action) denoted by a and q non-based non-baseline arms corresponding to different actions or treatments. Users are indexed by i 1, ... 2.... and decision points are indexed by = 1....... For each user at time i, the algorithm observes a context vector St, E S, chooses an action A. E [4] == {O..... g). and receives reward Ra E R. The differential reward describes the difference in expected rewards between choosing non-baseline arm and the control arm, defined as (,, a) E [R,, = s, A a| E
[ S 8, As,t 0].
We denote the observation history up to time t for user as H4, = AAi Ra..... St,). Actions are selected according to stochastic policies, Ti.t Hi, x S - P[q])) We use (als() to denote the probability of action a E [g] given context E S for fixed (implicit) history. As in Greenewald et al. (2017), we assume that the probability of the control action is bounded:
Assumption 1. There exists < Tmin: maax < 1 such that Tmin < (0)a) < Tmax for all i, t, a.
As noted in Greenewald et al. (017)) this assignment probability controls the number of messages that participants receive. ensures that participants receive sufficient messages that they do not disengage, but not so many that they are overwhelmed or fatigued. We now define
Ar, argmax E. [Ra, (Seee As, =], AT, argmax E [R Ar, a) aEly]
aElg/\oo}
the optimal arm (including control) and the optimal non-baseline arm, respectively. Respecting the restrictions in Assumption [.
we can now express the optimal policy, Ti,-- in two cases:
1. A 0: (0)S,e) = max and (A,, = Tmax.
2. A 0: (0)S,,) min and x (A;,) T7,, (4,,,.))))..))) = min--
These cases represent the appropriate boundary condition given the optimal action. We maximize the probability of the control action if A", 0 and minimize it if A * O, selecting the next-best action with the highest possible probability; we set the assignment probabilities for the remaining arms to zero. In Section 5.2) we define regret relative to this optimal policy, Th.
Lastly, we consider a study design that progresses in stages, where users enter the study sequen- tially (Friedman et al. 2010), as illustrated in Figure 1 Staged recruitment serves two purposes in our analysis: it increases the fidelity the theoretical setting by mimicking real-world recruitment strategies, and it allows us to estimate changes in the differential reward over time. Concretely, we first observe user = 1 at time = 1. Then we observe users = 2) at times = (2, 1). Subsequent stages k involve users < k, each having had A - 1 observations, respectively. Define O₂ = {(i, t) < k, t < k- notation summary.
i} as the set of all observations stage k. Appendix provides a
3.2 Doubly Robust Differential Reward
Following Greenewald al. 2017)) we assume that the differential reward is linear: A,, a) x(s, a) Og., where æ(s, a) E _2st feature vector depending on the context and action. We allow the baseline reward, ge (s). to be a nonlinear and nonstationary function of context and time. Combined, these two assumptions imply a partially linear model for the conditional mean reward:
E [Ra, Ar, a) (s()) =ss,a) 0,,da000
3

---

Stage
2
Recnutted
Noc yet recrused
A
Subiect
Figure I: Illustration of the staged recruitment scheme. At each recruitment stage (each time point). a new participant is recruited and observed. the same time, all participants who were recruited prior to the current stage are also observed again. Observations are not collected from participants who have yet be recruited. For simplicity, we assume one participant is recruited at each stage.
where Saso is an indicator a non-baseline action. By incorporating both the linear predictor a18 a) 0,000000 and the nonlinear baseline (s),,, we can maintain interpretability of the action effects while also allowing flexibility in specifying the observed rewards. The individual rewards are then realized according the model
RA (s) + a(8,a) 01,10a50 (r,, +
6it:
where we make the following standard assumption (Abeille & Lazaric 2017) regarding ca.e Assumption 2. The error Ei, is conditionally mean zero (i.e., Ele,, H4,1] = 0) and mub-Gaussian.
Assumption 2 ensures that large errors are sufficiently rare and that RG is proportional an unbiased estimate of (s) However, Rd suffers from high variance, which leads suboptimal perfor- mance in practice. Our proposed algorithm, ROME, relies on an improved estimator, it{ (s, a), that is also unbiased but achieves lower variance by denoising the rewards according working model, fa, a). for the conditional mean Ts, a) = RR,, = 8, Ai, = a):
Rut (1 Ai.e)
(s. a) = fe,(s, - (s.
ÚA, Ti (0(s)
Model prediction
Debiasing lern
where is a preselected non-baseline arm; i.c., we condition on A,, {0, a). The first component is model- based prediction of the differential reward, and the second component is debiasing term that uses IPW to correct for potential errors in the specification of This improved estimator is form of pseudo-outcome, common technique in the causal inference literature (Bang & Robins 2005 Nie Wager| 2021 Kennedy 2023). We refer to it as a Doubly Robust Differential Reward because it produces
unbiased estimate of (s,(s, a) as long as either मi.t Si, is correctly specified (see proof in Appendix [F.T): though, in practice, the benefit stems from (a) the robustness to misspecification of f (because Ti,t known) and (b) the variance reduction introduced by denoising the outcomes (see Remark 1 in Appendix E.2). In the following, we abbreviate R/ a) as R. with the context and action implied.
Algorithm Components
We now construct Ri introduce the weighted least-squares loss function used by RoME to estimate parameters, and use neirhot- regularization to pool information across users.

---

4.1 Debiased Machine Learning
To construct Ri we fit working model fú, for the conditional mean reward. Because R is robust misspecification of fú,, regret bound in Theorem I does not require fi, to be correctly specified. However, we show in Appendix E.2 that the following assumption results in a lower asymptotic variance bound for Re
Assumption 3. The working model, Ji,, satisfies (rce(s, Si,e(8, a)] "33 for all 8, a.
Assumption 3 states that fiLe is strongly consistent estimator of ri,t, but does not impose any specific rate requirement on the convergence. Although our regret bound does not require Assumption 3 does require two standard conditions within the DML framework: (a) Neyman orthogonality and
(b) independence of fi. and the observed rewards. The construction of R/, ensures that (a) holds, making Ri, robust to misspecification of f. We enforce (b) via sample-splitting techniques. We present two such options below.
Option 1:
The first option exploits the fact that outcomes across different users are independent. Consequently, we can perform sample splitting as follows. Step Randomly assign each user to one folds. Let W, denote the set containing user indexes for the j-th fold and let W denote its complement. Step 2: For each fold, use supervised learning algorithm to estimate the working model for (s, a) denoted f(.) (s, a) using W Step 3: Construct the peedooouucomee using (T)
Option 2: Because we do not expect an adversarial environment in mHealth, we may be willing to assume that the errors, C,,t, are independent across time. In this case, we can adapt the procedure given above by randomly assigning data to folds the level of (i, t). In this case, Wj, contains the (i,t) pairs assigned to fold j. This option is more powerful than option I in that it enables us to learn heterogeneity across users in the nuisance function, fi,t, leading to greater variance reduction.
Lastly, we note two strategies that can reduce the computational demands of sample splitting. The first is to employ estimators that satisfy leave-one-out stability condition, such bagged estimators that use subsampling (Chen et al., 2022); these estimators eliminate the need to perform sample splitting. The second is to fit ft.t in an online fashion.
4.2 Estimation via Weighted Least Squares
Having formed R (s, a), we explain how to estimate the parameters, 0g E Rd. determining the differential reward, (i, a). We assume that 0,,, consists of three components:
Assumption 4. 0.E- = Gohared + 0.ter + t for all i,
The parameter gahared is fixed effect shared across all i, In contrast, 0 and @time random effects specific to a given user and time point, respectively. We place these parameters in a single column vector, 0, vec(Oehared @user ..... 0K O ...., (.me), ), where K is the total number of stages. We then form a corresponding feature vector, 6i,e p(21,)) I22K+1)d where ó inserts Fi, into the positions corresponding @shured guver and Olime with zeros all other locations; i.c., ((x2,) C, where
C2a [1, 0,,,, 1, oz O 1, 0 @ Ta
so that C₁ [dd(22+1)dd We could then estimate Oi,, via a weighted least squares (WLS) regression that minimizes the following objective function:
n K-it1
(WLS Σ
Σ
(
-
where -. = (0.((0
(0 (1) However, (w is over-parameterized and does
not take advantage of available network information. The next section modifies (0))(0) by adding regularization, producing the final loss function used in ROME.
5

---

We assume access to network information relating neighboring users and time points. These networks are defined by graphs Guser = (Vuser. Euser) and Güme (Vime: Emme), where V denotes vertices and E, edges. In practice, these networks can be formed via known clusters (e.g.. shared schools, companies, geographic locations) or similar covariates. In the case of Grime. a reasonable choice is to construct a graph of neighboring sequential time points; i.e., t= <> 2 ++ ..... Because we expect neighboring users and time points to have similar parameters, we may be able to improve 4.3 Nearest-Neighbor Regularization
our estimates of by regularizing neighboring values of ffaer and 6fime toward each other. This can be accomplished by using L Laplacian penalty. We illustrate the idea using Guseri the application to Grime is similar.
First, we form the incidence matrix, Q, with the entry Qu.e corresponding to the e-th vertex (user) and the e-th edge. Denote the vertices of this edge as U2 and ey with j. Qu.e is then equal to 1 04 -1 if Uy, and 0 otherwise. The Laplacian matrix is then defined as QQ" E _ Similar to Yang et al. (2020), we form a network cohesion penalty across users as follows:
tr( tr(O user Tuser user))
Σ
110
Ou 2
E
where Ouee = (Ouser ..... Quser) T RKxdd and Tewser is the Laplacian matrix for users. The penalty is small when ouser and guser are close for connected users. We employ a shared regularization hyperparameter X, for Guser and Grime and include a standard L penalty on 0 with hyperparameter y. The full penalization matrix Vo E R22K (1)x is
Vo diag(>Ia, KK + AL user
.Ik + AL
time
(2)
where Lige == Luser & La the Kronecker product of Luser with la (Lim is defined similarly). We then adapt (WLs(() to include a corresponding penalty term:
K-1+1
(())
-
+ +
In Section 5 we show that
3 leads to Thompson sampling algorithm for action selection.
5 Thompson Sampling Algorithm
We now describe the Thompson sampling procedure and provide high-probabilityy regret bound.
5.1 Algorithm Description
The minimizer of the weighted regularized least squares loss in (3) is -= V-1b,
where
K-i+1
K-it1
V Vo
a L
Σ
Σ
In analogy to Bayesian linear regression, the penalized and weighted Gram matrix, V. plays the role of a (scaled) posterior precision matrix under a multivariate Gaussian prior for 0. This motivates an algorithm in which we randomly perturb the point estimate, Ô. Specifically, we define V =
C.,V--C., and set o.,, = C2, + (,) v,, where r) a mean-zero random variable and
2K(K + 1)
det((V + (max(log3/4(A))) (K), 1) log (c
(r,(5)==
v1 r log
(4)
8
In the above expression, AQ,- = CV.V-'VVV VoV-IC and K is the total number of stages. The value o is the sub-Gaussian factor for Ri,,, and ( is defined in Remark 2 in Appendix E, both can be set to sufficiently large constants. The hyperparameter determines the probability with which the regret bound holds. The random deviate, 17, is drawn from distribution DJS satisfying the

---

technical conditions in Definition 1 in Appendix D In practice, we recommend setting DJS to multivariate Gaussian distribution or t-distribution to simplify calculations. Given ii, we then compute At, argmax 2 21, and randomly select A,, = 0 with probability
(0, A,,)) = max Tminn min maax: Pr(xTT0.. < <
(5)
or A,,t As, with probability TT,e (0)A A.t). The action selection is summarized in Algorithm
Algorithm 1 Action selection
input V. b, Ci (5), Zi,,, Tmin+ maxx
Set 0 V-1 and Vi, Ci,
Sample 17 ~ D
Set 0., = Ci + Br, (o)
Set A,, = argmax fo) 07,
Calculate TT.. (O),())) according to 5
With probability nT, (O)A,)) play action O; otherwise, play action A,,
Having detailed the action selection algorithm, we now summarize RoME in Algorithm _ The algorithm includes an outer loop that iterates through the stages from k = 1 to k = K. Within each stage, handle users sequentially, iteratively selecting actions according Algorithm observing rewards, and updating V and b accordingly.
Algorithm 2 ROME
Initialize Vo according to
V Vn
b-0
for k 1..... K do
for (i = (1, k), (2, 1)..... ........k, 1k do
Choose an arm according to A V and b Observe reward, Ri,
Construct pseudo-reward, R4 explained in Section 4.1
Set di,: = C,
Update weighted Gram matrix: V V +0
Update feature-outcome products: + ++ 57 Rd 0r,t
end for end for
Regret bound
We first define regret, Regret,, in terms of the following average across stages:
Σ
(A,,(Ai, (SS., At,) m.. aSS,, A
k= (,,))
The inner sum calculates regret (the difference between the expected reward of the optimal action and the chosen action) weighted by the probability of the action, following Greenewald et al. (2017) for all users at stage We then average these values to account for the growing number pairs (z, t) as the stages progress. The cumulative regret is the sum of these averaged values over all stages.
The rewards associated with the baseline action excluded since (S,,S form of pseude-regret because eliminates the randomness due to {c,, |r (Audibert et al. 2003) The regret bound requires additional technical assumptions:
Regret, x is
Assumption 5. For all and a, [| a)ll < 1.
Assumption 6. There exists known value M Bt such that (gc(s)), M for all i, t, and
7

---

Assumption 7. Let eK == # #E" + #E denote the total number of edges. Then ex = O(K))
for some [0, 00).
Assumption 8. Let 0% represent the vector of true parameter values al stage k: = i and Vir!
=0p (1p(202/1( 10)
the matrix V prior to decision point (i,t), t). Then ( [Vo8%
Assumption 9. The matrix Vi, is bounded below as follows: Vi, / a min(i, far some > that may depend on d.
Assumption 5 is standard assumption that simplifies the proof (Abeille & Lazaric 2017 Assump- tion 0 ensures that the (estimated) baseline rewards are bounded. Assumption 7 ensures that the number of edges grows faster than a polynomial rate. Assumption Seseereessneeeeeeeeee random effects to the regret bound. Lastly, Assumption Saatimmptooonnenuuueeee Jensures sufficient exploration of the context space. See the proof of Theorem T in Appendix E.3 for additional discusion of Assumptions 8 and 9 We now state the regret bound.
& limits the contribution of the
Theorem 1. Under Assumptions
7
9
with probability at least 1 - 8, Regret is of order
O
dv K log( log( (K2d)
{vā 1ogg/////////////// (1gg/((())))))))))))))) [k)}]
The exact bound (including constants) and proof are given in Appendix E Following Greenewald (et al.] (2017), we decompose the regret into two terms. The first term depends on summation of terms of the form (T",,(AA,,,s - (A,,(A,, Jar Au,)) 10,,-- We employ a novel technique based on Markov's inequality to bound this term (see Lemmas 12 2and T3 in Appendix
We bound the second term using the high-level proof technique of Abeille & Lazaric (2017). The primary difficulty in bounding this term is that the classical theory for the estimation error of RLS estimates (Theorem 2 in [Abbasi- Yadkori et al. (2011)) ) is not directly applicable to our setting due to the increasing dimensionality. Lemma 6 in Appendix
E generalizes this theory our setting. This Lemma produces a bound involving C, Vofglly,, which we subsequently bound
by |Vo0 l|v, in Lemma 7 This section of the proof requires Assumption g to ensure that the contribution of the new parameters to this bound is small enough that we incur no more than a logarithmic penalty.
The overall bound scales like 4/2) to log factors, matching the standard rate given in Agrawal & Goyal (0122) and Abeille & Lazaric (2017) for linear Thompson sampling with fixed dimension. In particular, the bound depends solely on the dimensionality of the differential reward- not the baseline reward, which may be much more complex.
6 Experiments
This section presents results from applying ROME in a simulated mHealth study with staggered recruitment and off-policy comparison study for cardiac rehabilitation mHealth interventions. The simulations were implemented using Python and the results were generated using individual compute nodes with two 3.0 GHz Intel Xeon Gold 6154 processors and 180 GB of RAM. Case studies were implemented using R 4.2.2 and results were generated on cluster composed of individual compute nodes with 2.10 GHz Intel Xeon Gold 6230 processors and 192 GB of RAM.
6.1 Competitor Comparison Simulation
In this section, we compare RoME to four competing methods in simulation. We implemented RoME using Option 2 with a bagged ensemble of stochastic gradient trees (Gouk et al. 2019 Mastelini ct al. 202T) trained online via the River library (Monticl et al. 202I). We programmed the linear algebra operations using SuiteSparse (Davis & Hu 2011 to take advantage of the sparse nature of
the Laplacian matrices and Φi., from Algorithm?? 2
Our competing baselines are (a) Standard: Standard Thompson sampling for linear contextual bandits, (b) AC: the Centteee contextual bandit al algorithm (Greenewald et al. 2017]. (c) IntelPooling: The intelligentpooling method of Tomkins et al. (202T) fixing the variance parameters close to their true values, and (d) Neural-I Linear: a method that uses a pre-trained neural network to transform the feature space for the baseline reward (similar to the Neural Linear method of Riquelme et al. (2018))
8

---

We compare these methods under three settings: Homogeneous Users, Heterogeneous Users, and Nonlinear. The first two involve linear baseline model and homogeeeuus parameters, with the second setting having distinct user parameters. The third setting, designed to mirror the challenges of mHealth studies, includes a nonlinear baseline and both user- and time-specific parameters. For each setting, we simulate 200 stages following the staged recruitment regime depicted in Figure | and we repeat the full 200-stage simulation 50 times. Appendix A. provides details on the setup and a link to our implementation.
(a) Homogeneous Users
(b) Heterogeneous Users
(c) Nonlinear Setting
140
Cunulative Regret
120
130
Neural-Lirea
IntelPocling
Lumulative Regret
120
100
Cumulattive Regret
120
100
Standard
90
60
40
0-
0
50
150
200
Stage
Stage
Stage
Figure 2: Cumulative regret in the (a) Homogeneous Users, (b) Heterogeneous Users, and (c) Nonlinear settings. RoME performs competitively in the first setting (the simplest), and it substantially outperforms the next-best method (IntePPooling) in the others.
Figure 2 displays the average cumulative regret for each method. RoME and IntelPooling have similar performance in the Homogeneous Users setting, but RoME excels in the Heterogeneous Users and Nonlinear settings, with significantly lower cumulative regret by stage 200. This is expected as RoME can utilize network information and model nonlinear baselines in these settings. However, in the Homogeneous Users setting, where network information is available and a linear baseline is used, RoME does not outperform IntelPooling.
Appendices A.2 A.2.A.3 A.5 offer more results, including additional method comparisons, rectangular data array simulation, hyperparameter sensitivity analyses, and pairwise statistical comparisons. The latter show that RoME outperformed each competitor in at least 48 of 50 repetitions in the Nonlinear setting, indicating even higher statistical confidence than Figure 2 suggests. RoME substantially outperforms the competing algorithms in the additional comparisons and is several orders of magnitude faster than would be required a standard mHealth study, producing over 20,000 decisions in as little as 95 seconds (see Table 2 in Appendix A.2
6.2 Valentine Study Analysis Results
In this section, we compare RoME the above algorithms via off-policy evaluation using data from the Valentine Study (Jeganathan et al. 2022), a prospective, randomized-comtrollee remotely administered trial designed to evaluate an mHealth intervention to supplement cardiac rehabilitation for low- and moderate-rist patients. In the analyzed dataset, participants were randomized to receive or not receive contextually tailored notifications promoting low-level physical activity and exercise throughout the day. The left panel of Figure 3 shows the estimated improvement in the average reward over the original constant randomization, averaged over stages (K = 120) and participants (N=108). We see that RoME achieved the highest average reward; its average performance (across bootstrap replications) is higher than the 75th percentile all other methods.
To further analyze the improvement of RoME relative to the other methods, we test whether the proposed algorithm significantly improves cumulative rewards using paired t-tests with one-sided alternative hypotheses. The null hypothesis (Ho) for these tests is that the two algorithms being compared achieve the same average reward. The alternative hypothesis (H₂) is that the algorithm listed in the column achieves higher average rewards than the algorithm listed in the row. The right of Figure 3 displays the p-values obtained from these pairwise t-tests. The dark shade of the last column indicates that the proposed RoME algorithm achieves significantly higher rewards than the other five competing algorithms (p S 0.01 for all pairwise comparisons). The results imply that RoME would have achieved 3.5% increase in step count relative to the constant randomization policy that was

---

Unbloaed Estimate of Relative Expected Rewards
RoME
0.06
0.04
Neural-Linear
0.02
IntePPocling
ps0001
p.00.05
0.00
Standard
Standard
IntalPooling Neural-Linear RoME
Standard
AC IntelPoaling
Nourat- Linear
Rob HE
Figure 3: (left) Boxplot of unbiased estimates of the average per-trial reward for all five competing algorithms, relative to the reward obtained under the pre-specified Valentine randomization policy across 100 bootstrap samples. Within each box, the asterisk (*) indicates the mean value, while the mid-bar represents the median. (right) Heatmap of p-values from the pairwise paired t-tests.
actually implemented in this study. This effect translates to an increase of 140 steps per day, given baseline of 1,000 steps per hour and four one-hour measurement windows. See Appendix Bor additional implementation details.
We performed additional off-policy comparison using data from the Intern Health Study (IHS) (NeCamp et al. 2020), as shown Figure Tigure[iijn Appendix CC22 The results further demonstrate the competitive performance of the RoME algorithm, with the AC algorithm also showing comparable performance in this dataset. Further details on the analysis can be found in Appendix C
7
Discussion
This paper introduces ROME, robust mixed-effects contextual bandit algorithm for mHealth studies. RoME adapts DML and network cohesion penalties to dynamic settings, enabling researchers to efficiently pool information across users and over time. addition to the methodological contribution, we also prove high-probability regret bound in asymptotic regime that involves growing pool of users and time points. Our implementation would be required in practice and could easily be adapted for use in future mHealth studies.
RoME several orders of magnitude faster than
We see several promising directions for improving RoME in future work. One such direction might consider improvements in the algorithm and theoretical analysis that enable us to replace Assumptions aand with weaker and more primitive assumptions. In particular, these assumptions may not be because most arm selections will be restricted to the same two arms (for large K). Other interesting directions include data-adaptive strategies for hyperparameter selection and addressing long-term impacts of mHealth treatments, such as accumulating treatment fatigue. Future work could also consider computational improvements that would enable large-scale deployment of ROME, which would be especially relevant in nonclinical settings.
plausible for
Acknowledgements
The authors gratefully acknowledge the contributions of the researchers, administrators, and par- ticipants involved in the Valentine Intern Health (https:// :/cp:n///ciiii cal trialsllas..lr... gow///tudy//cToo/722202
wow.souudy///TO45555555 NNC004587802 and
studies. This work was supported in part by grant P50 DA054039 provided through the NIH and NIDDK and by grant R01 GM152549 through the NIH and NIGMS. Dr. Golbus receives funding from the NIH (4300L 1K23HL168222 Initially while working this paper, Dr. Moreno supported by Luminous Computing, Inc.
10

---

References
Abbasi-Yadken Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
Abeille, M. and Lazaric, A. Linear Thompson sampling revisited. Electronic Journal of Statistics, 11(2):5165 - 5197, 2017. doi: 10.1214/1-EES133111. URL https::/dooo http::///dooooo//////ooooo 10. 1214/ I7-EJS1341SI
Agrawal, S. and Goyal, N. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference Learning Theory, pp. 39-1, JMLR Workshop and Conference Proceedings, 2012.
Aouali, I., Kveton, B., and Katariya, S. Mixed-effect Thompson sampling. In International Confer- ence on Artificial Intelligence and Statistics, pp. 2087-2115. PMLR, 2023.
Audibert, J.-Y., Biermann, A., and Long, Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 3734)263,, 2003.
Bang, H. and Robins, J. M. Doubly robust estimation in missing data and causal inference models. Biometrics, 61(4)9962-973, 2005.
Resa-Bianchi, N., Gentile, C., and Zappella, G. A gang of bandits. Advances in Neural Information Processing Systems, 26, 2013.
Chen, Q., Syrgkanis, V., and Austern, M. Debiased machine learning without sample-splittigg for stable estimators, Advances in Neural Information Processing Systems, 35:3096-3 3109, 2022.
Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E.,, Hansen, C., Newey, W., and Robins,
J. Doublc/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21()):C1-668, 01 2018. ISSN 1368-4221. doi: 10.111 1/ectjj URL https //doi.org/ 10. wwt111111eee11000
Cho. H., Wang. P., and Qu, A. Personalize treatment for longitudinal data using unspecified random- effects model. Statistica Sinica, pp. 187-206, 2017.
Davis, T. A. and Hu, Y. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS), 38)1:112 2011.
Friedman, L. M., Furberg, C. D., and DeMetsR., D. L. (eds.). Machine Learning: An Artificial Intelligence Approach, Vol. I. Springer, New York, NY, 4 edition, 2010.
Golbus, R., Gupta, K., Stevens, R., Jeganathan, V. E., Luff, E., Shi, Dempsey. W., Boyden, T., Mukherjee, B., Kohnstamm, S., et al. A randomized trial of mobile health intervention to augment cardiac rehabilitation. NPJ Digital Medicine, 6(1):173, 2023.
Gouk, H., Pfahringer, B., and Frank, E. Stochastic gradient trees. In Asian Conference on Machine Learning, pp. 1094 1109. PMLR, 2019.
Greenewald, K., Tewari, A., Klasnja, P., and Murphy, S. Action centered contextual bandits. Advances in Neural Information Processing Systems, 30, 2017.
Hu, X., Qian, M., Cheng, B., and Cheung, Y. K. Personalized policy learning using longitudinal mobile health data. Journal of the American Statistical Association, 116(533):410-44 2021.
Jeganathan, V. S., Golbus, J. R., Gupta, K., Luff, E., Dempsey, W., Boyden, T., Rubenfire, M., Mukherjee, B., Klasnja, P., Kheterpal, S., et al. Virtual application-supprrte environment to increase exercise (VALENTINE) during cardiac rehabilitation study: Rationale and design. American Heart Journal, 248:53-62, 2022.
Kennedy, E. H. Towards optimal doubly robust estimation of heterogeneous causal effects. Electronic Journal of Statistics, 170))3008-3009, 2023.
Kim, G.-S. and Paik, M. C. Contextual multi-armed bandit algorithm for semiparametric reward model. In International Conference on Machine Learning, pp. 3389-3397. PMLR, 2019.

---

Kim, W., Kim, G.-S., and Paik, M. C. Doubly robust Thompson sampling with linear payoffs. Advances in Neural Information Processing Systems, 34:15830-15840, 2021.
Kim, W., Lee, K., and Paik, M. C. Double doubly robust Thompson sampling for generalized linear contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8300-8307, 2023.
Kingma, D. and Ba, J. Adam: method for stochastic optimization. arXiv preprint 1412,994 2014.
Krishnamurthy, A.. Wu, Z. S., and Syrgkanis, V. Semiparametric contextual bandits. In International Conference on Machine Learning, pp. 2776-2785. PMLR, 2018.
Lee, K., Paik, M. C., Oh, M.-h., and Kim, G.-S. Mixed-effects contextual bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 13409-13411 2024.
Li, L., Chu, W., Langford, J., and Schapire, R. A contextual- approach personalized news article recommendation. Www, pp. 661-670, 2010.
Ma, H., Zhou, D., Liu, C., Lyu, M. R., and King, I. Recommender systems with social regularization. In Proceedings of the Fourth ACM International Conference Web Search and Data Mining, pp- 287-296, 2011.
Mastelini, S. M., de Leon Ferreira, A. C. P., et al. Using dynamical quantization to perform split attempts in online tree regressors. Pattern Recognition Letters, 145:37-42. 2021.
McPherson, M., Smith-Lovin, L., and Cook, J. M. Birds of feather: Homophily in social networks. Annual Review of Sociology, 27(1):415 444, 2001.
Montiel, J., Halford, M., Mastelini, S. M., Bolmier, G., Sourty, R., Vaysse, R., Zouitine, A., Gomes, H. M., Read, J., Abdessalem, T., al. River: Machine learning for streaming data in Python. 2021.
Nair, V. and Hinton, G. E. Rectified linear units improve restricted Boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning, pp. 807-814, 2010.
NeCamp, T., Sen, S., Frank, E., Walton, M. A., lonides, E. L.., Fang, Y., Tewari, A., and Wu, Z. Assessing real-time moderation for developing adaptive mobile health interventions for medical interns: raddo-randomized trial. Journal of Medical Internet Research, 22(3):e15033, 2020.
Nie, X. and Wager, S. Quasi-oracle estimation of heterogeneous treatment effects. Biometrika, 108 (2):299-313) 319,,,3192000111 2021.
Qian, T., Klasnja, P., and Murphy, S. A. Linear mixed models with endogenous covariates: Modeling sequential treatment effects with application mobile health study. Statistical Science, 35(3): 375, 2020.
Riquelme, C., Tucker, G., and Snoek, J. Deep Bayesian bandits showdown: An empirical comparison of Bayesian deep networks for Thompson sampling. arXiv preprint 102.011 2018.
Robinson, P. M. Root-n-consistent semiparametric regression. Econometrica: Journal of the Econometric Society, pp. 931-954, 1988.
Snoek, J., Rippel, O., Swersky, K., Kiros, R., Satish, N., Sundaram, N., Patwary, M., Prabhat, M., and Adams, R. Scalable Bayesian optimization using deep neural networks. In International Conference on Machine Learning, pp. 2171-2180. PMLR, 2015.
Tomkins, S., Liao, P., Klasnja, P., and Murphy, S. Intelligentpooling:: Practical Thompson sampling for mhealth. Machine Learning, 10(0))2685 272277777 2021.
Vaswani, S., Schmidt, M., and Lakshmanan, L.. Horde of bandits using Gaussian Markov random fields. In Artificial Intelligence and Statistics, pp. 690-699, PMLR, 2017.
Yang, K., Toni, L., and Dong, X. replacian-regularizee graph bandits: Algorithms and theoretical analysis. In International Conference on Artificial Intelligence and Statistics, pp. 3133-3143. PMLR, 2020.
12

---

A Additional Details for Simulation Study
This appendix provides details regarding the setup of our simulation study, additional results not presented in the main paper, and results from additional simulations employing different competitors and/or simulation designs. We summarize the differences between the competing algorithms Table
i
Enforces
Enforces
User-
Time- specific
Pools
Allows Nonlinear Baseline
Nonlinear
User
specific Parameters
Across
Baseline
Network
Network
parameters
Users
Cohesion
Cohesion
Model
ROME
VV
V
JAME-BLM
V
RoME-SU
X
VVKV
V
VVV
N/A
V
V
ONR-Liness
V
N/A
IntelPooling
Neural-Linear
N/A
N/A
V
Standard
X
N/A
N/A
X
AC
N/A
N/A
Table 1: This table compares the methods tested in the simulation study based the design components listed in the columns, with / indicating that the method includes the component listed in the column, X indicating that it does not, and N/A indicating that the component is not applicable. This table can be used to investigate the effect of certain model components on cumulative regret; for example, comparing RoME and RoME- BLM helps understand the impact of modeling the nonlinear baseline the only column that differs between these two methods.
A.1 Setup Details
The code for the simulation study is fully containerized and publicly available at htttps://githii com/ htt///astonncccheee RoME. The simulation study involves generative model of the following form for user at time l:
Rst = g(St,) + x(S,,, Ar.)) O + Est. 6xt ~ No
Here St, (81, 82) R² is context vector, with both dimensions did U(-1,1). We r(s, a) (1, $1 $2). For simplicity, we set to a time-homogeneour function. The specific nature of the function varies across the following three settings mentioned in Section 6.T
Homogeneous Users: Standard contextual bandit assumptions with a linear baseline and no user- or time-specific parameters. The linear baseline g(S...) = 281 + 382, and the causal parameter is 0₂ (1, 0.5, -4) such that the optimal action varies across the context space.
Heterogeneous Users: Same as the above but each user's causal parameter has iid W(0 1) noise added to it.
Nonlinear:
The general setting discussed in the paper with a nonlinear baseline, user-specific parameters, and time-specific parameters. The base causal parameter and user-speeific parameters are the same as in the previous two settings. The nonlinear baseline and time- specific parameter are shown in Figure
We assume that the data observed via staged recruitment scheme, as illustrated in Figure For computational convenience, we update parameters and select actions batches. If, for instance. observe twenty users at given stage, update estimates of the relevant causal parameters and select actions for all twenty users simultaneously. This strategy offers a slight computational advantage with limited implications in terms of statistical performance.
For simplicity, we assume that the nearest-neighbor network known and set the relevant hyperpa- rameters accordingly. We took care to set the hyperparameters such that RoME performs similar
13

---

amount of shrinkage compared to other methods, especially IntelPooling, which effectively uses separate penalty matrix for users and time. To accomplish this, we used the same penalty matrices for RoME and IntelPooling, effectively generalizing the scalar penalty discussed in the main paper. We use neighbors within the DML methods and set the other hyperparameters follows: 5 = 0.01, 1, and Ç 10.
For the Neural-Linea method, we generate a 200 200 array of baseline rewards to train the neural network prior to running the bandit algorithm. Consequently, the results shown in the paper for Neural-Linear are better than would be observed practice because we allowed the Neural-Linear method to leverage data that we did not make available to the other methods. This setup offers the computational benefit of not needing to update the neural network within bandit replications, which substantially reduces the necessary computation time.
Aside from the input features used, the Neural-Linear method has the same implementation the Standard method. The Neural-Linear method uses the output from the last hidden layer of a neural network model the baseline reward. However, we use the original features (the state vectors) to model the advantage function because the true advantage function is, in fact, linear in these features.
Our neural networks consisted of four hidden layers with 10. 20, 20, and 10 nodes, respectively. The first two employ the ReLU activation function (Nair Hinton 2010) while the latter two employ the hyperbolic tangent. We chose to the hyperbolic tangent for the last two layers because (noek ctt al. (2013) found that smooth activation functions such as the hyperbolic tangent were advantageous their neural bandit algorithm. The loss function networks' output and the baseline reward on a simulated data set. We trained our networks using the Adam optimizer (Kingma & Ba 2014) with batch sizes of 200 for between 20 and 50 epochs. We simulated separate validation data set to check that our model had converged and was generating accurate predictions.
the mean squared error between the neural
Figure 5 compares the true baseline reward function in the nonlinear setting (left) to that estimated by the neural network (right). We that the neural network produced accurate approximation of the baseline reward, which helps explain the good performance of the Neural-Linear method relative to other bascline approaches, such Standard.
We include the Neural-LLinear method primarily to demonstrate that correctly modeling the baseline is not sufficient to ensure good performance. In the mHealth, algorithms should also be able to (a) efficiently pool data across users and time and (b) leverage network information. The Neural-Linear method satisfies neither of these criteria. Note that neural network could be used to model the baseline rewards as part of our algorithm. Future work could consider allowing the differential rewards themselves to also be complex nonlinear functions, which could be accomplished by combining our method with Neural-Linead We leave the details to future work.
10.
e/0)
3.2
0.4
wm
0.6
-2
488
1.0
1.0
0.8 0.6
04
02 on
02
04
06
na
1.0
100
125
150
200
Figure 4: (left) The baseline reward function (S (constant across time in this case) used in the simulation study. The proposed method allows this function to be nonlinear function of the context vectors. The baseline was generated using a combination of recursive partitioning and by summing scaled, shifted, and rotated Gaussian densities. (right) The time-specific parameters used in the simulation study. These parameters cause the advantage function to vary over time. We set them such that the advantage function changes quickly the beginning of the study then stabilizes.
14

---

A.2 Additional Method Comparisons
Our results in the main paper indicate that RoME outperforms existing methods, especially in the complex longitudinal setting that we are targeting. These positive results beg the question: What aspects of RoME contribute most its superior performance?
In this section, we describe an additional simulation study designed to answer this question. In it, compare RoME (as implemented in the main paper) three additional comparison methods: BLMM-BLM, RoME-SU, and NNR-Linear. Each comparison isolates particular aspects of our algorithm to understand its contribution RoME's performance.
RoME-BLAN MMME-BMMMAE a version of RoME that employs Bagged Linear Models as the baseline supervised learning algorithm. Unlike the method implemented in the main paper (which uses bagged stochastic gradient trees), this baseline model misspecified the nonlinear setting; i.c., it cannot accurately model the nonlinear baseline reward function. Consequently, this comparison will allow us to gauge the impact of the supervised learning method used in our method. In particular, should allow us to validate whether the algorithm is robust baseline misspecification as the theory suggests.
RoME-SU is Single- Useer version of our algorithm. Rather than having separate 6; for each user, this method estimates single advantage function that is shared across all users. It does, however, employ DMI,, time effects, and nearest-neighhor regularization (for the time effects). Consequently, this comparison will help us understand the impact of the user-specific parameters in our simulation.
NNR-Linear is similar the existing network-cohesion bandit algorithms described in the main paper. It includes a distinct 0, for each user and regularizes them toward each other using Laplacian penalty. It does not, however, use DML time effects. As a result, this comparison isolates the impact of these two factors and should provide evidence that RoME is more broadly applicable than existing network-cohesion bandit algorithms.
Figure displays the cumulative regret as a function of the stage for these methods across the three settings used in the main paper. We see that all methods perform similarly in panel (a), the setting with homogeneous users. However, in panel (b) we see that the regret achieved by RoME-SU begins to resemble straight upward-sloping line because it cannot appropriately model the user-specific advantage functions.
In panel (c), observe much wider spread of performance, with RoME and RoME-BLM per- forming similarly and substantially outperforming the other methods. The fact that ROME and RoME-BLM perform similarly indicates that our algorithm is, in fact, robust misspecification pected. The comparison to NÑR-Lineal Linear reveals that the DML and time effects the new components of our method compared to existing to RoME's superior performance. We found in additional simulations studies not reported here that the gap between NNR-Linear and method widens the magnitude of the time effects increases.
bandit algorithms- do contribute meaningfully
Table displays the average computation time for each method across all three settings. Each run of the simulation produces 200 x 201/2 20, 100 decisions. RoME and RoME-SU require the longest computation time at about seven minutes. RoME-BLM requires only 95-110 seconds, indicating
1.0
-7
6
5
0.0
0.0
0.2
0.2
3
0.4
0.4
2
4.8
0.8
0.8
0.8
1.0
1.0
0.8
0.2
0.0
0.6
0.8
0.6
0.4
1.0
Figure 5: (left) The baseline reward function ge (S.,) used in the simulation study compared to (right) the estimated baseline reward from our neural network in the nonlinear setting.
15

---

(a) Homogencous Users
(b) Hcterogencous Users
(c) Nonlincar Sctting
RnNF
20
RaNC-OLM
Curulaatve Regnet
Curulaative Regret
Curulaatvv Regret
88
1.-
NNR--Inaar
5
10
30
20
3-
10
3
100
150
100
150
100
130
200
Szage
Stage
Stage
Figure Cumulative regret in the (a) Homogeneous Users, (b) Heterogeneous Users, and (c) Nonlinear settings for the additional comparison methods. The fact that RoME outperforms RoME-SU demonstrates the importance of the user-specific parameters. The fact that RoME outperforms NNR- Linear shows that previous network cohesion approaches do not adequately address the nonlinear nature of the baseline reward and presence of time effects. The comparable performance of RoME- BLM to RoME highlights how our algorithm is robust to misspecification of the baseline reward model.
Homogeneous Users
Heterogeneous Users
Nonlinear
ROME
394.5
406.4
420.1
RoME-BLM
94.6
96.8
109.9
RoME-SU
383.5
390.5
396.5
NNR-Linear
29.7
31.3
31.5
IntelPooling
46.6
42.1
45.0
Neural-Linear
0.7
0.8
0.9
Standard
0.2
0.2
0.3
AC
0.1
0.1
0.3
Table 2: Average computation time across all methods and settings in the main simulation.
that the computational bottleneck for RoME is the ML model fitting. The required computation time for IntelPooling about half that of BLM at 42-47 seconds. NNR-Linear requires 30-32 seconds, and the remaining methods run in less than one second. Because most clinical mHealth studies require fewer than 1,000 decisions per day, the speed of RoME is orders of magnitude faster than is required in practice. However, large-scale commercial deployment of RoME may require computational adjustments and approximations.
A.3 Pairwise Comparisons
Table shows pairwise comparisons between methods across the three settings. The individual cells indicate the percentage of repetitions (out of 50) in which the method listed the row outperformed the method listed in the column. The asterisks indicate p-values below 0.05 from paired two-sided t- tests on the differences in final regret. The Avg column indicates the average pairwise win percentage.
shows
RoME and RoME- BoME-BLM perform well across all three settings and the difference between them is statistically indistinguishable. These methods perform about equally well compared IntelPooling and NNR Linear in the first setting, but they perform better in the other two. In the Nonlinear setting in particular, RoME and RoME- BLM substantially outperform all other methods, and the pairwise differences are statistically significant at the 5% level.
A.4 Simulation with Rectangular Data Array
The main simulation involves simulating data from triangular data array. At the 200-th (final) stage, the algorithm has observed 200 rewards for user 199 rewards for user 2, and so on.
16

---

Homogeneous Users
2
3
4
5
8
Avg
1. RoME
58%
46%
66%
40%
100%
100%
100%
73%
RoME-BLI
42%
36% *
44%
32% "
100%
100%
100%
65%
RoME-SU 54%
64%
58%
44%
100% *
100%
100% *
74%
NNR-Linear
34%
56%
42%
32%
100% *
100%
100%
66%
5. IntelPooling
60%
68%*
56%
68%*
100%
100%
100%
79%
6. Neural-Liness
0%
0%
0%
0%
0%%
100%
100%
29%
Standard
0%.
0% *
0%
0% *
0%
0%*
100
14%
0%.
0%*
0%.*
*
0%
0%
0%
0%
Heterogeneous Users
2
5
6
7
Avg
- 1000
+.85 10001
+ 1000
2. RoME-BLM
ROME
42%
58%
80%* *
72%
52%
56%
100%
10098
1000
03000
* 23000
1000000
233000
23000
*%000 03000 10000
+ 23000
81%
85%
4. NNR-Linear
3. RoME-SU
44%
20%
48%
28%
78% x
22%*
92%
100%
200000
20000
10000
10000 500000
81%
66%
IntelPooling
0%.*
0% *
8%
0%
43%
Neural-
0%6*
0%
0%%
0% *
6%%
9888
100%
29%
7. Standard
0%6
0% *
0%%
0% *
0%%*
2%
100%
15%
8. AC
0%.
0%
0%
0%*
0%%*
0%
0%
0%
Nonlinear
3
4
8
Avg
ROME
56%
100%
96% *
98%*
100% *
100%
100%
93%
RoME-BLM
44%
96%*
98%
100% *
100% *
100%
100%
91%
RoME-SU
0%.
4%
40%
80%*
100%
100%
100%
61%
4. NNR-Linear
4%,*
2%
60%
82%
100%
100%
100%*
64%
5. IntelPooling
29.*
0%
20%*
18%
98%
100%
100%*
48%
Neural-Linear
0%.*
0%
0%
0% *
2%
98% *
1
29%
Standard
0%.*
0%
0%
0%
0%
2%
100%
15%
8. AC
0%6*
0%
0%
0%
0%
0%
0%
0%
Table 3: Pairwise comparisons between methods in the three settings of the main simulation. Each cell indicates the percent of repetitions (out of 50) in which the method listed in the row outperformed the method listed in the column in terms of final regret. Asterisks indicate p-values below 0.05 from paired two-sided t-tests on the differences in final regret. RoME and HOME-BLM perform well in all three settings, and their final regret is statistically indistinguishable. They substantially outperform all other methods in the Nonlinear setting.
17

---

In this section, we simulate actions and rewards under a rectangular array with 100 users and 100 time points. Although we still follow the staged recruitment regime depicted in Figure [ stage 100 we stop sampling actions and rewards for user 1; at stage 101 we stop sampling for user 2; and so on until we have sampled 100 time points for all 100 users. Aside from the shape the data array, the setup is the same for this simulation as for the main simulation.
Hor ageneous Users
(b) Heterogeneous Users
Nonlinear Setting
Cumulattvv Regret
IntelPooling
Cumulatton latve Regret
Cumulattiv Regret
Neural- Linear
40-
30
20
20
10
10
3
0
20
40
65
80
100
0
20
40
60
80
100
20
40
60
50
100
Figure 7: Cumulative regret in the (a) Homogeneous Users, (b) Heterogeneous Users, and (c) Nonlinear settings using rectangular array of data in which observe 100 time points for 100 users in a stagewise fashion as depicted in Figure ! Similar to Figure RoME is competitive in the first setting and substantially outperforms the competitors in the other settings.
Homogenecus Users
(b) Heterogeneous
Nonlinear Setting
D
22
Cumu attve Regret
RaME-SI.
Cumu Catullatie Regret
10.
Cumulative Regret
20
NKR Linear
15
10
0
20
40
60
80
100
0
20
40
60
80
100
20
40
60
80
100
Figure 8: Cumulative regret in the (a) Homogeneous Users, (b) Heterogeneous Users, and (c) Nonlinear settings using rectangular array of data in which observe 100 time points for 100 users in a stagewise fashion as depicted in Figure T We observe the same performance ordering as in Figure 6 but here the relative differences even larger.
The cumulative regret for these methods function of time not stage is shown in Figure 7 Qualitatively, the results are nearly identical to those from the main simulation (compare to Figure 2 The differences in final regret even larger in this simulation than they were in the main simulation, presumably because this study exhibits greater variation in time effects due to the balance across time.
Figure g displays comparisons similar to those shown in Figure for the rectangular simulation. We again see that the results qualitatively similar to the main simulation. The methods perform similarly in the Homogeneous Users setting. RoME-SU performs poorly in the Heterogeneous Users setting, but the other methods perform similarly. Finally, RoME and RoME-BLY substantially outperform the other methods in the nonlinear setting. Again, the differences in performance are even larger in this simulation than in the main simulation.
Table displays results from pairwise method comparisons, similar to those shown Table Again, the results are qualitatively similar to but slightly more exaggerated than those from the main simulation. In particular, in this simulation study, RoME and RoME-BLM outperform all other methods in 100% of repetitions in the Nonlinear setting.
18

---

Homogeneous Users
3
4
5
7
8
Avg
1. RoME
58%
44%
54%
48%
100%
100% *
100%
72%
RoME-BLM.
42%
42%
48%
40%
100% *
100% *
100% *
67%
RoME-SU
56%
58%
60%
54%
100% *
100% *
100%* *
75%
NNR-Linear
46%
52%
40%
52%
100%
100% *
100%
70%
5. IntelPooling
52%
60%
46%
48%
100%
100% *
100%
72%
6. Neural-Lines
0%
0%
0%%
0% *
0% *
100% *
100%
29%
Standard
0%.
0%
0%
0%
0% *
0% *
100% *
14%
0%.
0%
0%
0%**
0% =
0%
Heterogeneous Users
5
Avg
ROME
52%
100%
52%
100%
100%
100%*
100%*
86%
2. RoME-BLM
48%
100%
52%
100%
100%
100% *
100%
86%
3. RoME-SU
0%-
0%
2%
92%
100%
100%: *
100% 8
56%
100% *
4. NNR-Linear
48%
48%
98%* *
100%
100%
100% *
85%
IntelPooling
0%.*
0%
8%
0%
88%*
100%
100% " 42%
Neural-
0%6*
0%
0%%*
0%%*
12%
100%
100%
30%
7. Standard
0%6
0%
0%
0%%
0%
0% *
100%
14%
8. AC
0%.
0%
0%*
0%
0%
0% *
0%%
0%
Nonlinear
2
5
6
7
8
Avg
ROME
56%*
100%
100%
100%
100% *
100%
9000
100%
100%
100% *
94%
RoME-BLM
44%*
100%
100%
100%
92%
RoME-SU
0%.
0%*
28%
76%*
100%
100%
100%
58%
4. NNR-Linear
0%.*
0%*
72%
86%*
100%
I 100%
100%
65%
5. IntelPooling
0%6
0%
24% R
14%*
98%*
I 100%
100%
48%
6. Neural-Linear
0%.*
0%
0%
0%.
2%
100%
100%
29%
Standard
0%.*
0%*
0%
0%*
0%.
0%*
100%
14%
8. AC
0%.*
0%
0%
0%
0%
0%*
0%
0%
Table 4: Pairwise comparisons between methods in the three settings of the simulation with rectangular array of data. As in Table each cell indicates the percent repetitions (out of 50) in which the method listed in the row outperformed the method listed in the column in terms of final regret. Asterisks indicate p-values below 0.05 from paired two-sided t-tests on the differences in final regret. The qualitative results are similar those of Table RoME and RoME-BLM perform well across all three settings and substantially outperform all other methods the Nonlinear setting.
19

---

A.5 Hyperparameter Sensitivity
In the simulation study, we chose hyperparameters for the fairest comparison possible, employing the same regularization parameters across methods. To assess robustness, we performed seven sensitivity analyses that alter hyperparameters for our methods while fixing those of the other methods; this approach gives the competing algorithms an advantage. Under these alternative hyperparameters, RoME and RoME-BLM still substantially outperform the other methods in the Nonlinear Setting.
Two of the sensitivity analyses led to no significant changes to Figure 2 and Table 3 setting 8 = 0.05 and e 10. Below, we summarize the changes in the remaining analyses:
Rescaling 7 by factor of ten: This change resulted in RoME and RoME-BLM performing relatively better compared to the other methods in the Heterogeneous setting. In particu- lar, RoME and RoME-BLM outperformed NNR-Linear 70% and 72% of replications. compared to 56% and 52% using the original value of y.
Rescaling À by a factor of ten: Similar to the above results, this changed improved the performance of RoME and RoME-BLM compared to the other methods (especially RoME- SU and NNR-Linear) in the Heterogeneous Users setting.
Adding (low and medium) noise to the nearest-neighbor network: RoME significantly outperformed RoME-BLM in the Nonlinear setting.
Increasing the number of neighbors to 10: The performance gap between the full RoME algorithms (RoME and RoME-BLM) and RoME-SU increased to 88%, 76% compared 80% and 72% under the original configuration, presumably due increased network cohesion.
The results for the À sensitivity analysis are displayed in Table Results for the remaining sensitivity analyses are available with our code.
B Additional Details for Valentine Study
Personalizing treatment delivery in mobile health a common application for online learning algorithms. We focus here the Valentine study, prospective, cellomizzed-conrrollee remotely administered trial designed to evaluate an mHealth intervention to supplement cardiac rehabilitation for low- and moderate-risk patients (Jeganathan al. 2022) Golbus et al.. (003).. We aim to smartwatch data (Apple Watch and Fitbit) obtained from the Valentine study to learn the optimal timing of notification delivery given the users' current context.
B.1
Data from the Valentine Study
Prior the start of the trial, baseline data was collected from each of the participants (e.g., age, gender, baseline activity level, and health information). During the study, participants are randomized to either receive notification (A, = 1) or not (A, = 0) at each of daily time points (morning, lunchtime, mid-afternoon, evening), with probability 0.25. Contextual information was collected frequently (e.g., number of messages sent prior week, step count variability in prior week, and pre-decision point step-counts).
Since the goal of the Valentine study is to increase participants' activity levels, define the reward, RG, as the step count for the 60 minutes following decision point (log-transformed to eliminate skew). Our application also uses a subset of the baseline and contextual data; this subset contains the variables with the strongest association with the reward. 6 the features available to the bandit the Valentine study data set.
For baseline variables, we use the participant's 's device model (Z,, Fitbit coded as 1), the participant's step count variability in the prior week (Zz), and measure of the participant's pre-trial activity level based on an intake survey (Zg, with larger values corresponding to higher activity levels).
At every decision point, before selecting action, the learner sees two state variables: the partici- pant's previous 30-minute step count (S1, log- (og-traasformed) and the participant's 's phase of cardiac rehabilitation (S2, dummy coded). The cardiac rehabilitation phase is defined based on participant's
20

---

Homogeneous Users
3
4
6
7
8
Avg
RoME
58%
48%
64%
38%
100%
100%
100%
73%
36001 8 100%
2. RoME-BLM
42%
38%*
42%
38%
100%
66%
960001 * 100% *
3. RoME-SU
52%
62%
58%
46%
100%
74%
1000 *
ANR-Lineer
36%
58%
42%
32%
100% *
10001 -
100% *
67%
IntelPooling
62%
62%
54%
68% *
100%
100%*
78%
6. Neural-Linear
0%6
0%
0%**
0%
0%
98%
100%
28%
7. Standard
0%-
0%
0%**
0%
0%
2% +
100% 8
15%
AC
0%.
0%
0%-*
0%
0%
0% *
0%
0%
Heterogeneous Users
2
5
6
7
8
Avg
a 200000 1001
#: 22%00 1001
86001
RoME-BLM
RoME
48%
52%
78%
92% x
72%*
68%*
100% &
100%
1001
10800 1000
000000
22800 1001
22000
85% + 10000
1000
88%
3. RoME-SU
8%
22%
20%*
92%
1000
1000
040000
1001
10090
63%
4. NNR-Linear
5. IntelPooling
0%.
28%*
0% *
32%
8%
80%
0% *
4 69%6
8600
* 10001
20000
43%
77%
99%6
Leural-Linear
0%.*
0% *
0%%
0%
4%
29%
Standard
0%.*
0%
0%%*
0% *
0%
4%
100%
15%
8. AC
0%.
0%*
0%
0%*
0%*
0%
0%*
0%
Nonlinear
2
3
4
5
6
7
8
Avg
3 09860
4000
23000
10096
2. RoME-BLL -LM
1. ROME
48%
52%
96%*
92% *
96% *
96%
90%0
" 8886
200000
1010
80000
10000
100%0
00000
90%
92%
3. RoME-SU
NNR-Linear
4%
4%,*
4%
8%
40%
60%
82%
100%
100%
1300000
100%
66%
%
5. IntelPooling
2%.*
4%
10%
18%
98%
100%
47%
6. Neural-Linena
0%6
2%
0%
0%6*
2%%
98%6
100%
29%
7. Standard 0%.*
0%
0%
0%.*
0%
2%
100%
15%
0%6
0%
0%
0%6*
0%
0%*
0%**
0%
Table 5: Pairwise comparisons between methods in a sensitivity analysis in which we scale À by a factor of ten. As Table 3 each cell indicates the percent of repetitions (out of 50) in which the method listed in the row outperformed the method listed in the column in terms of final regret. Asterisks indicate p-values below 0.05 from paired two-sided t-tests on the differences in final regret.
Feature
Description
Interaction
Baseline
Phase II
1 if in Phase II, o.w.
Phase III
1 if in Phase II, o.w. log transformed log transformed
Steps in prior 30 minutes
Pre-trial average daily steps
Device
I if Fitbit, 0 o.w.
Prior week step count variability
SD of the rewards in the previous week
Table 6: List of features available to the bandit in the Valentine study. The features available to model the action interaction (effect of sending an anti-sedentary message) and model the baseline (reward under no action) are denoted via "v" in the corresponding column, otherwise x.
21

---

Df
Sum Sq
Mcan Sq
F value
Pr(>F)
Participamldentffer
107
264
2.464
8.09
<2--16
##*
Week
25
17
0.683
2.24
4e-04
Residuals
2265
690
0.305
Table 7: ANOVA analysis of the pseudo-outcomes in the Valentine study. The small p-values constitute strong evidence that the treatment effects differ by participant and over time.
time in the study: month represents Phase I, month 2-4 represents Phase II, and month 5-6 represents Phase III.
B.2 Justification of Assumption 4
The motivation for Assumption 4 arises from an exploratory analysis we performed using data from the Valentine study. We constructed the pseudo-reward for each observation as suggested by Equation ① and then conducted an ANOVA test. The results show clear heterogeneity between users and across time, motivating the adoption of user- and time-specific random effects. The results of the ANOVA test are displayed in Table Figure shows the shape the heterogeneity the treatment effects over time.
0.1
Oetoomes
0.
Week Study
Figure 9: The time heterogeneity in the pscudo-outcomes. We calculated the pseudo-outcomes using (L). then averaged them across participants and plotted them over time. This exploratory analysis shows evidence that the causal effects vary substantially over time.
B.3
Evaluation
The Valentine study collected the sensor-based features at 4 decision points per day for each study participant. The reward for each message was defined to be log(0.5 x)). where x the step count of the participant in the 60 minutes following the notification. As noted in the introduction, the baseline reward (the expected step count of subject when no message sent), not only depends on the state in complex way but is likely dependent large number of time-varying observed variables. Both of these characteristics (complex, time-varying baseline reward function) suggest using our proposed approach.
We generated 100 bootstrap samples and ran our contextual bandit on them, considering the binary action of whether or not to send a message at a given decision point based on the contextual variables S and Sz. Each user is considered independently and with a cohesion network, for maximum personalization and independence of results. To guarantee that messages have a positive probability of being sent, we only sample the observations with notification randomization probability between 0.01 and 0.99. In the case of the algorithm utilizing NNR, we chose four baseline characteristics (gender, age, device, and baseline average daily steps) to establish a measure "distance" between users. For this analysis, the value of l representing the number of nearest neighbors was set to 5. To utilize bootstrap sampling, we train the Neural-L.inaar method's neural network using out-of-bag samples. The neural network architecture comprises single hidden layer with two hidden nodes.
22

---

The input contains both the baseline characteristics and the contextual variables and the activation function applied here the softplus function, defined as softplus(z) = log(1 + exp (z)).
We performed an offline evaluation of the contextual bandit algorithms using an inverse propensity score (IPS) version of the method from Li al. (2010), where the sequence of states, actions, and rewards in the data are used to form near-unbiased estimate of the average expected reward achieved by each algorithm, averaging over all users.
0873
ROME
Unbiazed Estimate
0.800
Relativv Expecied
p Vaka
0.05
0.00
NNR-Linear
NNR-Linear
RoME-SU
RoME
NNR NNR-Linear
RoME-SU
RaME
Figure 10: (left)) Unbiased estimates of the average per-trial reward for all three ablation algorithms. relative to the reward obtained under the pre-specified Valentine Study randomization policy across 20 multiple-imputed data sets. And (right) p-values from the pairwise paired t-tests.
B.4 An ablation study
We further investigate the primary contributors to the algorithm's performance, we conducted parallel ablation study using real-world data analysis. In this study, we compared RoME (as detailed in the main paper) with two additional methods for reference: RoME-SU and NNR-Linear. Each comparison focuses on specific elements our algorithm to discern their impact on RoME's overall performance.
The differences between these methods are illustrated in Figure. TO In this particular dataset, NNR plays a more significant role in driving the overall superior performance of our algorithm.
B.5 Inverse Propensity Score (IPS) offline evaluation
In the implemented Valentine study, the treatment was randomized with constant probability Pt = 0.25 at each time conduct off-policy evaluation using our proposed algorithm and the competing variations of the TS algorithm, outline the IPS estimator for unbiased estimate of the per-trial expected reward based on what has been studied in Li al. (2010).
Given the logged data D = {ss St. A; = aq R₁ = re)T=1 collected under the policy {pt )T and the treatment policy being evaluated π = { the objective this offline estimator is to reweight the observed reward sequence RR ) to assign varying importance to actions based on the propensities of both the original and new policies selecting them.
Lemma (Unbiasedness of the IPS estimator). Assuming the positivity assumption in logging, which states that for any given and a, (((aas) O. then we also have <<(a|s) > we can obtain an unbiased per-trial expected reward using the following IPS estimator:
1
Te(aelss)
Rips
T (a(e)))))
As mentioned in the previous section, we restrict our sampling to observations with notification randomization probabilities ranging from 0.01 0.99. This selection criterion ensures the satisfaction of the positivity assumption. The proof essentially follows from definition, we have:
23

---

Proof.
Te(ael (r(e)(1))
B[Ris
Ep
Ri Bac st)
T
1
1
me(ao(s))
Re(as, st) x pr(aolse)
T
po(aelst)
1
Tee Te Re st)
T
En
Re Re st)
T
To address the instability issue caused by reweighting some cases, we use a Self-Normalized Inverse Propensity Score (SNIPS) estimator. This estimator scales the results by the empirical mean of the importance weights, and still maintains the property of unbiasedness.
(ails)) Pe (oa) I'
RipS
RSNIPS
(6)
(ail))) Palar
(a,ss)
T
C Additional Details for the Intern Health Study (IHS)
To further enhance the competitive performance of our proposed RoME algorithm, we performed an additional comparative analysis using real-world data set from the Intern Health Study (IHS) (NeCamp et al. 2020 This miero-randomized trial investigated the use of mHealth interventions aimed at improving the behavior and mental health of individuals in stressful work environments. The estimates obtained represent the improvement in average reward relative the original constant randomization, averaging across stages (K = 30) and participants (N = 1553). The available IHS data consist of 20 mulliple-imputer data sets. We apply the algorithms each imputed data set and perform a comparative analysis of the competing algorithms. The results presented in Figure 11 shows proposed RoME algorithm achieved significantly higher rewards than the other three competing ones and demonstrated performance comparable to the AC algorithm. These findings further support the advantages of our proposed algorithm.
C.1 Data from the IHS
Prior to the start the trial, baseline data was collected on each of the participants (e.g., institution, specialty, gender, baseline activity level, and health information). During the study, participants randomized to either receive a notification (A; = 1) or not (A, = 0) every day, with probability 3/8. Contextual information was collected frequently (e.g., step count in prior five days, and current day in study).
We define the reward, R,, as the step count the following day (cubic root). Our application also uses subset of the baseline and contextual data; this subset contains the variables with the strongest association to the reward. Table Sable shows the features available the bandit in the IHS data set.
At every decision point, before selecting an action, the learner sees two state variables: the partici- pant's 'ss' previous 5-day average daily step count (S1, cubic root) and the participant's day in the study (S2, an integer from to 30).
C.2 Evaluation
We run our contextual bandit the IHS data, considering the binary action of whether or not to send a message at a given decision point based on the contextual variables S₁ and S2. Each user is considered independently and with cohesion network, for maximum personalization and

---

Feature
Description
Interaction
Baseline
Day in study
an integer from to 30 cubic root cubic root
Average daily steps in prior five days Average daily sleep prior five
X
days
Average daily mood in prior five days
a Likert scale from 1 10
X
Pre-intern average daily steps
cubic root
X
Pre-intern average daily sleep
cubic root a Likert scale from 1 10 Gender
X
Pre-intern average daily mood Sex
X
Week category
The theme of messages in a spe- cific week (mood, sleep, activity, or none)
X
PHQ score
PHQ total score
X
Early family environment
higher score indicates higher
X
level of adverse experience
Personal history of depression Neuroticism (Emotional experience)
X
higher score indicates higher level of neuroticism
X
Table 8: List of features available to the bandit in the IHS. The features available to model the action interaction (effect of sending mobile prompt) and to model the baseline (reward under no action) denoted via "v" in the corresponding column, otherwise x.
independence of results. To guarantee that messages have a positive probability of being sent, we only sample the observations with notification randomization probability between 0.01 and 0.99. For the algorithm employing NNR, we defined participants in the same institution as their own "neighbors". This definition enables the flexibility for the value of kt representing the number of nearest neighbors, to vary for each participant based on their specific institutional context. Furthermore, in our study setting, we assume that individuals from the same institution enter the study simultaneously group. Due to the limited access prior data, we are unable to build the neural linear models as in the Valentine Study.
We utilized 20 multiple-impen imputed data sets and performed an offline evaluation of the contextual bandit algorithms on each data set. The result presented below in Figure II] Similar Section B.4 here we also compared RoME (as detailed in the main paper) with RoME-SU and NNR-Linear, The differences between these methods are illustrated in Figure. 12 In this specific dataset, both NNR and DML exhibit comparable performance individually, but their combined effect significantly enhances the overall performance of the algorithm.
D Additional Details for Algorithm
This appendix briefly discusses two details of Algorithm T The first efficient computation of V-1, Because V is large matrix, a full matrix inversion is expensive. Fortunately, however, we can dramatically reduce the necessary computational requirements because each additional (i, t) involves rank-one perturbation to V. Consequently, we can apply the Sherman-Morrison formula to speed up computations. We leveraged this trick in our implementation of RoME for the simulation study by using efficient rank-one updates available in the SuiteSparse library (Davis & Hu 2011).
The second detail is the requirements for the distribution, DTS
Definition 1. TS is multivariate distribution on Rd absolutely continuous with respect to Lebesgue measure which satisfies: (anti-concentraaion)) that there exists strictly positive probability p such that for any E IRd with ||u|| = 1, P(u r 1) 2 p; 2. (concentration) there exists c, c' positive constants such that 46 E (0, 1), P(]y]] < V codle(d)// 2 8; and 3. it possesses a finite
second moment, El m where DS.
25

---

Unblased Estimato Relstivv Expected Rewards
RaME
IntelPooling
P Value
AC
p>
Standard
Standard
IntelPooling
Standard
InteiPooting
ROME
Figure 11: (left) Unbiased estimates the average per-trial reward for all four competing algorithms, relative to the reward obtained under the pre-specified Intern Health Study randomization policy across 20 multiple-imputer
data sets, And (right) p-values from the pairwise paired t-tests. The dark shade in the last column indicates that the proposed RoME algorithm achieved significantly higher rewards than the other three competing algorithms while demonstrating comparable performance to the AC algorithm.
Unblased Estrmate of Relalive Expected FRewards
0.04
RoME
Value
NNR-Uneer
2.00
NNR-Linear
RoME-SU
RoME
NNR- Linear
RoME su
ROME
Figure 12: (left) Unbiased estimates of the average per-trial reward for all three ablation algorithms, relative to the reward obtained under the pre-specified Intern Health Study randomization policy across 20 multiple multiple-imputed imputed data sets. And (right) p p-values from the pairwise paired t-tests.
While a Gaussian prior satisfies Definition I this approach allows to move beyond Bayesian posteriors generic randomized policies. discussed the main paper, we recommend setting DTS to multivariate Gaussian distribution or multivariate t-distribution. These choices simplify computations because the probability computation in (5) simplifies to an evaluation of the CDF of either (a) univariate Gaussian or (b) univariate t-distribution. The mean and variance of corresponding univariate distribution can easily worked out using the moments linear combination of random variables.
E
Regret Bound
E.1
Double Robustness of Pseudo-Reward
Going forward, we use the notation (f, fr, a) (s, 0) to denote the prediction of the differential reward. In the computations in this section, we implicitly condition on Hi, and Ai, {0, a).
Lemma 2. If Wethhe Pt, Ti,t or fi,t ri,t. then
E () (s) A.,(s,a)
That is, the pseudo-rewand is an unbiased estimator of the true differential reward.
26

---

Proof. Recall that
Rit Se,(88 Ai,)) (s,,a))))
R
- - (0(s)
Case I: I's are correctly specified
Then
Rig
E
8,
= =rii(s, @) -s,,
(0
= -1,((8,
and
(s, A1,1)
E
f(,(s, (s,
OA (0|s(
= (,,
so that
E
Rai li, Ai,t)
(,((,,))
(ir(s, (s, (s,
ÚA (0|s)
as,(s,ūa)
Case II: of correctly specified
Rs:
pi.r
(i.r(O]s)
8,
t0, ()) Ti
(,,
(00s) Ti, (8.0) 0)
AA. (0(8)
and
[i,(5,
- s0
(0
(5,
fi, (s, 0)
ô ÓA,,= TT,
=
1 (0|s)
(00s)
1 (0(s)
(0
(0|s) (s,
(0,((0(s) (s, 0)
and
2/((s,0)s, 8, (s,()
E
Rut - fie(s, Ai,t)
+ Al,(5,a) 8, = (s,(s,))
B ŌA..=ā (00s)
E.2 Preliminaries
Lemma 3. Let X be mean-zero sub-Gausee Gaussian random variable with variance proxy v² and Y be bounded random variable such that [Y| < B for some 0 < B < oc. Then XY is sub-Gaussian with variance proxy 2 B².
Proof. Recall that X being mean-zero ub--Gaussian means that
P([X) 2) S exxp
2v
27

---

Now note that so that if XX| > 6, then | > t. Thus by monotonicity
|X|| |
P(JXY| 1 P(X
=P (XX B
12
1 2xxp
2B2
as desired.
Lemma 4. Y are sub- Sab-Gaassian with variance proxies ui by. respectively, then aX + BY is Sub-Gaussian with variance proxy o² + Boyy,, B E IR.
Proof. Recall the equivalent definition of uub-Gaussianity that X, Y are sub-Gaussian iff for some a, b > 0 and all À > 0
Eexp (A(X- Ex)) S exp (22//))))
E Exxp (A(Y -E)) & exp(1 (xppA>2,7/00 222
Then
Eexp (MaX + BY - - (BY)) s Eexp (202(X EX)) Eexp (233(Y EY))
S @exp(202>2r)) /xx
exp(2222213)
= exp((a 20 + xZ))))
The following Lemma gives the Gabssiaasiintty and variance of the difference between the pseudo- reward and its expectation. We see that in the variance, all terms except those involving the inverse propensity weighted noise variance vanish as fi, becomes a better estimate of ri,t-
Lemma 5. The difference between the pseudo-reward and its expectation (taken wrt the action and noise) is mean zero sub-Gaussian with variance
Var [R], (R,,(s,a)) (ri,((,,)) fs, (Olss) + Var(er.)
1 1 (0]ss
(rr,css, 0) - frils, 0)) T0,((0|s)] Var(er,)
(0(s)
2((r,((s - -f.ss - fs,(s,
Proof. We need to show that it is sub-Gaussian and upper bound its variance. We write the difference
as
-EiR)) = R,, -i,(saaa
Rst fs,((s, Aid)
- SA - {0,s(0)s) - (s,
Trals, Av.)) fi. Ar,)) t + (s, (s,(s,))
- (0|s)
Note that (rce(s, A.d) < max ((ri,e(s, a)l. (r, (s,0)) 0)) & M and [fie(s, A.d)l S max (l,r, ()). 0)) < M. Thus, since // (0)s) upper bounded (be- cause (0|s) E [iin mmax)). ), we have that (s.A) -L. (s..) is bounded and thus (not nec- essarily mean zero) sub-Gaussian. Since 6,, is Sub-Gaussian, its denominator is bounded, and the
04, (U)s)
28

---

remaining terms are deterministic, the entire difference between the pseudo-reward and its mean is sub-Gaussian. Now
as) - (B] - Var (3,0a)
=E - - a))
(7)
since E[R 18, a] is not random. Now we expand the first term on the rhs.
(s, Ai,1) - (s, Ai,)) + Cit + (s,
2
E
R (s, a)2
=E
θA,,== - Ti, (0]s)
(s, Ar.)) - fr, As,1) t
E
ÓAL,I=a - -;, (0|s)
ri, - fr,e(s, AI,)) + t.,
2E
(s, + (s,
8AC,= - (0,)(01)))
(r, Ar.)) (5, As.e) EL.1 27
A - (0(s)
+ 2( a) - (s, a)) ()) ()) (s)
(8)
For the first term the rhs of 8
ri, Ac,)) (8, Ai,t) + Cift
)
27
E
ŚA,,=ā - Tz, (0|s)
(s, A,,)) fi,0 Ar.)) 27
27
C221
E
+
8A - (0|s)
ÓA - (0,s(
(ri,(0, a) [1,1(8 (.)(,,a))2=2 Ele7,e
(ri,(s, (1, 0)) +
(0|s))
(0(s)
that plugging this into (8 have
(re,(s, a) - Si, a))² El2d
(ria(8, (s. 0)) + F[C
E RC [
m0,
(0)()
+ ((A,,((8
())a + (s)(),))
and plugging this into 7 we obtain the variance.
Var [ ()),(,,a)
(ri,((s, a) - (s, a))² + Var(es.)) (rr,e(s, 0) - fi,(s, 0))² + Var(er.)
(0|s())s)
(0|s)
(9)
Note that
2(Ain(8,0) - (4.66000-AM.s)))0((((00+14414,4 -A,
a))
=2(AAu(8,)) ((, -00 (Au(s, (A,(s,)
((,
(A,, a) (,,, -s,,))
(s, a) a))
and plugging this into
Var (R,,(s,a)) (s, a) (i a))² + Var(es,)) + (rir(s,0) - fra(s, 0))² + Var(er))
1 1-T
(0|s)
- (A,)(,,ā) - (s,
29

---

as desired. Now note that
(Au((, a)) = (Fi,(,, (s 0) (fi,(s, f,,(s,0))) 0)))
(ric(s,a) f1((s, a) - (mi(ss fir(s, 0)))
(ri,(s, f (m,(ss (mnu(s) - (s, 0))
- -2(ri,(8, - fi.ls 1 0))
so that
(s,)( (ri((s, fi,1 (T, - Var(eu.) 1 T
Var RR
(Fr,((s,)) 0) - (s, 0)) n.. (0|s]] Var(er,)
(0(s)
0) fa,(ss)) 0))
Corollary 1. Let = min(Amin. Tmaxx and 0² VVr((G,)) Then
Var (Rt (RL(
20 + 4M
+&M² =: vz.
Proof. Substitute 0² = Var(Ci,t) in Lemma and apply the bounds M, Tmin. and Tmax to obtain
TM, + o 4M Ti,(00s)) +
Var (R),(s,a)
8.M2
20 + 4M2 -.M2
We now show that Assumption 3 resultss in lower asymptotic variance bound. Corollary 2. The asymptotic variance of R (8, a) is no greater than
0²
#(1 7)
Proof. By Assumption 3 the terms involving ra, (s, a) - (s, a) and (s, fi. converge almost surely to zero. Dropping these terms from the expression in Lemma S] the asymptotic variance then less than or equal to
0²
o²
1 T2.
(0|s)
N.,
(0)s T.,
7 +
Remark 1. Comparing of and vg we see that of 2 vzz if
20
1-
1/22 n.
which must hold by the definition of R. Consequently The effect of the DML is lower the variance bound.
30

---

E.3
Derivation of Confidence Sets
To facilitate the developments below, we define the following quantities:
Vo Vi,; bi,a, :e.:: The quantities Vo, V, b, 0 V-1b in Algorithms point t).
| and decision
Oi,: The set of time pairs up to but excluding (i,t); we express O as {(1, 1), (1, (2, 1), 1)....,.. (L,)),
00 = Oshared + 0. + Ofime C,,0% E
0,,
ER.
AG. Cr. VoN. E R((xd)
= = Ci,Vi [EG.]]ED..
A ViL e g(dxd)
K,, = + + (C C. E Raxd
In the proof below, we allow the dimension of 0% to increase stages progress so that 6g bi, dar R(2++1)d and Vo,k, Vi, (22 However, the proof is also applicable (with minor modifications) to settings where the final dimension of 0% is known and set in advance (as in Algorithm 2)
In analogy to Bayesian linear regression, Vi, plays the role of a posterior precision matrix for 0j Similarly, V plays the role of a posterior covariance matrix. Assumption 9 ensures that V is "decreasing" sufficiently fast. Proving that this assumption holds under more primitive conditions an interesting area for future work. We conjecture that the following condition is sufficient provided that y is set to a sufficiently large constant.
Assumption 10. Let O a set of (i,t) pairs containing at least K* E elements, and let w > Then the following ordering holds:
Σ (GA)E0
23,10 (#O)wla
where #O denotes the cardinality of O.
This assumption ensures that we continue acquiring information about all elements of Ti, at a linear rate progress through stages. We now adapt the classical theory on RLS estimation error to setting.
Lemma 6 (Adapted from Theorem 2 in Abbasi-Yadkori et al. 201 20). Let Òz,, be the regularized least squares (RLS) estimate from Algorithm for the i-th user at the t-th time point, corresponding to stage = i and let 07, be the true parameter value. For any 8 0, with probability at least 1 - the estimates (G.DEE satisfy
1
dV (A
110 0f,,,,,,,
2log
V
8
where is the variance proxy for the difference between the pseudo-reward and its mean.
Proof. Let ō,,o((((S,,, Ar,)) and Pt.: let
Ar,)). Further
E,, = Σ
MjaPjju 18 (2k+1))d
(Ha)eO,,
31

---

8,1 Vh biL
Viee (ELt + Wi,
VIT Siee + Vi, 1b W ii
Sit + VV,e 1 (0 W Bi, + Vo, Vo
ViT Sce + 0% - 1, Vo vo
and thus
òc, 0% Veit Vo,a0%)
Premultiplying, we can then obtain
(0.--00 1 0t) C.I.K,
02) 10., - -0)) CiakkssCCC (Et. V%,
Simplification yields
110,e I. = -T,) C. C.. Vo,
We can then apply the Cauchy- Schwar- inequality to bound the right-hand side.
|| V. 4.6
I || ll.. VI (Es, Vo, Volv,,lll,.
Dividing by ||0,. 0 Il,. and applying the triangle inequality gives
11 v. S 11C,, EtalK,. + 1ICC,, Vo.
We can show that
(A + A
V..Vi.VVo.V C,,, (lu)EO.)
Σ
CieVe mj T jiu ie C.T
Vo,k +
Σ
0² Labg,uo
V Vir
(iu)EO,,
Veal (T. (G.VVT Kie.
Combined with the fact that Pt. sub- Gaussinn with variance proxy v², the above result allows us to apply Theorem of Abbasi- Yadkori et al. (211)). Specifically, to match their notation (setting aside our definition of S₁, for the moment), let S Ci, Ei, = Eiinneo, Ci. Va P and
Vi, Ci, 'Vo. CT, + CieVi E(i.u)EOs, myamnJ.) ViL CT have
)
S..clp $ 2v log det((A)
(1 1
det (V
C So v 2 2
8 V det(A
Adding this bound to ||C,, Vo, completes the proof.
32

---

In the above inequality, we will need to bound II 1, Vo,t& in order to obtain useful confidence sets. so, we first define a new matrix, Ci Definition 1.
Let Ci (g3dx(22+11)) be a (2k + 1) block matrix where all blocks are d zero matrices except the blocks at entries (1, 1), (2, i), and (3, 1 t) which are equal la-
Note that C,2 selects the components of 0% that are relevant to (i, t): gshared, 6uter, and 0time, We also have the relationship Ct22 (13 Ta)C which we leverage below.
Lemma 7.
I IVo,
Proof. To simplify the proof, we reorder the rows and columns of V,,, such that the rows and columns corresponding to gshared, Queer and flime appear first. The matrices C., and Ca, are similarly reordered, resulting in C., - [Tad 03d,2d(x-1)]- Ci,t Vi, as follows:
[(1g @ Ia) 0p.2d(t-11]- We now partition
Z11
Z12
V4,
Z21
Z22.
Using the x 2 Block-matrix inversion identity, it then follows that
p-1
-P-1 1P-1/12 Zo2 Znp
1, =
221 P-1 Zzgz
Zr Z21 p- Z12 Zo
where P == Z11 Z12Za22 Z21.
Consequently, have Ci,e i,t
P-1 [Iad
-Z12Zz2 and C., V..VV.... Ci p-1 Letting
G = [Tad - 722 we can write the squared norm as
1C Vo
= -6% = Vo. P- @ IMM @ 1a) 11) & GV
< V..TT
where we have used the fact that P-1/2 8 (0) @ 1 because the former is projection matrix and thus its maximum eigenvalue is one. We can further simplify and bound this quantity as follows:
--) 3 Ia
05 T GV'.Vo
Iad
= Vo.
p-1 [Iad -Z12Zzz Vo.4
-7,2 721
P-1
-p-1 7ry2
oF Vo.k
Vo.4
Zz3 Zzz
P-1
Zzz Zzz p- 2I2
- - Vo.k To.k
Viri
0
0
Vo.4
0
Zmp
< &11V,,
Remark We can apply Lemma 7 and Assumption bound ||C,, Vo.0fily Assumption
8 implies that there exists a function ((5) (0, such that
[|Cr, Vo. S sup [Vo,0flly.- ((6) ((() max) 3/4 (KC).)))))))))))))) (i.1)eOx
(K,))EOx
with probability least - This function corresponds with the hyperparameter Ç given the main paper. The purpose of the max operation is to avoid having bound of zero for K = 1.
33

---

We confirmed in simulation that Assumption 8 assumption is reasonable. The left panel of Figure 13 provides empirical evidence that Vo V // log (K) is bounded in probability in simulation with values of ranging from to 200. We ran 400 repetitions with an intercept-only model. Similarly, the right panel suggests that ())))))) |1V6,00 log" (K) is bounded as assumed. We conjecture that the following assumption sufficient condition (in combination with the other assumptions listed in the main paper) for Assumption to hold.
4.5
Mean
[V60, lvzt log
4.5
Mean
80% Confidence
80% Confidence
1V60, Iva /log3it
4.0
4.0
3.5
3.5
3.0
2.5
sup
2.0
2.0
150
200
Figure 13: (left) Simulated values of | /log log 2/gg/4(6) (Kk). (right) Simulated values of ())(),)) [Vo, (X)). The plots show evidence that these terms are bounded as required by Assumption
Assumption 11. The random effects 0ueer Ofime for i, t 1,2,... are distributed such that
K
Op()),
time Op(1).
K
So, in other words, would be sufficient for the normalized sums above converge in distribution. This effectively requires these normalized sums to be approximately mean zero. This requirement is reasonable given the presence of gehared in the model.
We now bound the first term from Lemma 6
Lemma 8. Assuming y 2 1, we have:
3
det V
Proof. By definition, we have:
V -c. C..Vi
Taking the determinant of both sides:
det(V det(Cr, Vi CTT.)
Using the property that the determinant of a matrix is less than or equal to the product of its cigenvalues, and letting (-) denote the j-th largest eigenvalue, we have:
d det < II Ay C.,))
3=1
Amax ( (C.VV CT.Y
Now letting di be the largest singular value of matrix,
Amax (C.,, Vir CTT)) (1(CC,)) Xmax 22 (Viz²)
34

---

Since Ci = =(1g @ 1a) i, we have that
o1(C,,) 01((43 @ (a)
S L @ (C,,)
= 1--1-1
v3
so that 01 (Ci,)) == =3. Therefore,
Ama (Ci, i,t 1 I 3 (Vizt)
3
Amin (Vit)
3
?
and thus
(3)
3
det(VT,)) S
7
Lemma 9.
Xanin (Vo.k) Amax (Vi,))
der(A 2 3d
Proof.
det(A),) 2
II minn (13 la) (Ci, VoN C.,)) j=1
3 Amin (V Vo, V
Amin (Vok)) Amaxx Vi,e)
2 3d
Lemma 10. Assuming Y 2 1.
det dct((V log dct(A
3k(k +1
< 2d log
+ 7h: + 2dex
8
Proof.
del (V log det(Ag,)
3 7
< d dlog dlogg 3 + 2d log Amax (Vo,)) d dlogg Amii (Vo,k)
< 2d(log (laax(Vs.)) log
Now we need to upper bound A )mnx.(Vi,e) Note that Amaae (V,,) S tr (Vi.)
Σ Ro(
Vo,
(L.)0xx
Σ
of) + 7k + 2λex
(.,00xx
3 kkk
+ 1)
+ yk + 2AE
4
2
35

---

This then gives us
det (Vi.)) log det(A
3k(k 1)
S 2d log
+ 77 2Xex -log
[3i(k:: + 1)
8 + t + 2AeN }
2 2d
Note that produces more than a logarithmic contribution to the above bound due to Assumption 7 We now define term, ( 62). that corresponds with the term (6) from the main paper, setting 8 = 261 with sufficiently large However, here we make explicit that the term depends on two probabilities, ò1 and 62.
Definition 2. Let B5,(( 52) be defined follows:
1 8,
det det(V det(
(6, (2)0::)):00)) oN
u 2log
+ log
+ ((02) max 3/4 3/o (K), 1}.
Note that by Lemma 6 and Assumption 8 we have 1|0,, 0f, S (i,,(00,0 with probability at least 1 51 - -2.
Lemma 11. Let 8/ 51/(K(( (K(K + 1)}. Then
sup (K.))eOk
|10... 0t, S sup (1,))xxx
Br, 82)
with probability at least 1 - 61/2 2 8g. Further SuP(LA)EOx B,,16%, 82) s (x(()162), where (x16 82) is defined as
K(K + 1)
3K(K +1) + 7K + 2λeK + ((82) max/
" log
2d 2d
(KK)))"""//KK))))))))))")) 1}. 3/4 (K),
81
8
Proof. The first statement follows from applying Lemma 6 with union bound. Note that the second term in Lemma can be bounded uniformly using Lemma aand Assumption g as follows:
||Ci, V
V, Vo, Ily,, <
11Vo,
((52) max (logg)///(()))
with probability at least 82. The second statement follows from bounding the first term in (,, 52) using Lemma 10
K(K + 1)
det(V(Tt)
U 2
+ log det(A
81
K(K 1)
3K(K +1)
$ U// 2og
+ 2d log
+ + + 2Xek
81
8
Lastly, we define several events and bound the probabilities with which they occur. Proposition 1. Let
81 = =5/((K(K+))
Fx = (V(i.) E Exx, 110,. - 0i, $ Bii,(6,
mell1, 62) = 3,,((1,, 52) V.. /cdlog('d/(0)
=x= (V(i.) E Ox, 110,. - 0,,lly,, S n. (8, 52)}
36

---

EK = EK n EK
Then Pr(Ek) 21 21-6, 81 82.
Proof. First, Lemma 11 shows that Pr(Pa) 21 81/2 2 82.
Next, applying the TS sampling distribution and 0z,t Oz.t drawn i.d. from DS we have
Ba 52),,
1/2
Thet
where Tett is
c'd
Pr
11 - -.,lll,. S (Pio(81,52)
cd
c'd
Pr
||m,ell s v cdllog
81
2 8
by the concentration property in Definition ! A union bound then gives Pr(Ex) 2 1 - 61/2. Applying a union bound to ÉR and ER yields the conclusion.
E,4 Treatment Probability Estimation Errors
The proof relies on bounding terms the form (Tr,,(Ai, (A,, (a,)) A,,)) Toi To simplify the proof, we denote these terms as (Ti,e - ,,, We begin by defining two filtrations.
Definition 2. We define the filtration F.S. as the information accumulated up to decision point (i. I) including the sampled context, that is, F = (Fi, o A1, AI,1, 12,1S22 Sta)). Similarly, we define the filtration Fi, as the information accumulated up to decision point (i,t) before sampling Si, Thus, Fis can be expressed in the same form as that of F above, removing the term Sit-
We now leverage F. conditionally bound (Tx,e - T2,)) m.,
Lemma 12. Conditional on F the term (ITS 0i, nonnegative and bounded
||0,e 02 V.ely.,, V,, + (6, 62) m|l min 1 Tmax aa min
(mi. -0mmm,,)a Ti,)
Proof. We begin by conditioning on F& that oT, is nonrandom. There are three cases.
Case 1: vT 0.
this simple case, we have (T. - ,t,)0,,,00 =
Case 2: TT 0.
In this case, the optimal policy is to apply the control arm with probability nH, Tmin because the treatment arm has positive expected effect on the reward. Because Ti. [Tiin Fmax by
construction, we have Ti, 2 Tmin = ni. which implies that ,,,t कं, 2 0, proving the first statement in the proof for this case.
37

---

Now the probability Ti. is based on the following probability calculation:
Pr(xx,,00 F,,
Pr
File 00 (0,,r - 07₂)) B1, 82) 1122
78
Fit
Pr
Fizt (0., - 0 (,, 52) VV 1/2
1h.11
< < 0
Fi.
< Pr
b (0.. - 02,)) (6, 82. 1/2 111t11 }
2 02,
< Pr
| { {0l. - -(,,) + (,,, 82)
1/2
Thit }|1.
2
x
F
1,
= Pr
(0L. - 07,0) + (e, 82) 1/2
2
F.S
V.
||aa,el V.r
2it
|
|10.. 0(,,) + (,,1(61,8))) 1is1
$ E
7/,1
Fi
V.
(m 0T,)
$ E (0., 07,)) + Br, 62)
FS 1.t
78.6
I..
min(itt))
where the last two lines follow from Markov's inequality and Assumption 9 the expectation, show that
Working directly with
1/2 1/2 E (1 07,,) + Br,((1,, 82)V
2
F
Vie
< E [1θ.. 0i.lle... ( E (115,1(01 02)
nh,1
Figt
Ii.
|10.. 02 02llle.. + pi,(0r, 62) ||
This result implies that
|10, - 07, V... + (5, 82) meel
Prix,,0,, 0} s
Mc.
(x,, )a min(i,
Provided Mi. S Tmins we have (Ni. (., because The = The = Tmin- Alternatively. when Mi, > Tmin. we have
0 0z 01. + +3, 82) |n..ell
TT
miin min(i,
Thus, in both cases we have
| 8% ll V. + (61,01522) |lmeell
(Te. - m,,)),
Tiin a min
Case 3:
This case is essentially identical Case except both क,,t कH, and oT,0r, are negative. The resulting bound is
|1,.
0i. liell, V. + Ral 52) ||
(TTEA 10-Tm,,) T..
(1 Tmax) ) min(i,t)
Conclusion:
38

---

Combining the three cases yields
|18.. 07,0 | Yr,, + (7, 62) mlll
(Te -1,,),,,,
min(Tumin 1 mmaxx )a min(i,
Lemma 13. Under event Ek, the following bound holds for all (i,t) E Oz,e:
(Tie - -,, T8x 02)
1 + E ma
===
/min(i,t)
a min (Tins
Tmax
Proof. Let (i*, 1*) denote the final decision point stage K and let 84 = 8./(K(K + +1). Condi- tional on F . Lemma 12 implies that
110,e 0 V. 62,
52) ||
(T. T <
min( (Tiin; Tmax ) min(i, ()
We can then apply Lemma 11 to argue that for all ti, E Ox because F. i,t f
S FS
(ō1, 82) + 32 (61, 52) ||v,, min Tiiu:
(mi - =1,,0,,0000,,,
mmxx )a min(i,
8x (61, 82) /min(i,
1 + E ||
ammin( Tiin Tmxx)
under event F. for all (i,t) E Out-
E.5
Proof of Theorem I
We first decompose the regret
Σ
It,, AW,) m,.(A,,15,) A.,)
(i.t)EOx \0a-1
Σ
(1, - -,,,1,,,,, A 67
(L))EOn(On-1
+ + (A,,
x(S Ar,)) T 07
K
Σ
(mta(Att,lsa))) - Te (.. T 07,]]
k=
(O
Σ
At, (S.,,, Tri.).
k=1
39

---

We can bound the (absolute value of) the first term using Lemma 13
E
=..(AA.15,.))) A.,) 07,e
(0x))
78x(01,82)
V /min(i,t)
k/2 2 du
<T 62)
Vu
K
2V2
= =T3x(61,02)
VT.
k=
(18x(61,8))2V)
Vuu du
=T3x (51, (2))
under event Ex-
The proof for the second term follows closely from Abeille & Lazaric (017)) with several adjustments.
Assumption 5 implies that only need consider the unit ball X x IRd the second term of the regret can be decomposed into
||= s 1}. Then
K
K
Σ
(TiTo - 2T,
Σ
TT,,Br,e - -
k
ko
k=
(3.1) \
RT)(K)
BRLS(K)
where xi,, .(St,r Ah,) and 24.e x(SS,, A,r)) The first term is the regret due to the random deviations caused by sampling 6,e and whether it provides sufficient useful information about the true parameter 87,,. The second term the concentration of the sampled term around the true linear model for the advantage function.
Bounding RRLS (T). We decompose the second term into the variation of the point estimate and the variation of the random sample around the point estimate:
Σ
Σ
(IT, xI,,0t,.)
(O
The first term describes the deviation of the TS linear predictor from the RLS one, while the second term describes the deviation of the RLS linear predictor from the true linear predictor. The first term is controlled by the construction of the sampling distribution DTS, while the second term is controlled by the RLS estimate being a minimizer of the regularized cumulative squared error in (3). In particular, the first term will be small when the TS estimate concentrates around the RLS one, while the second will be small when the RLS estimate concentrates around the true parameter vector. Under event Ex. we can bound R.LS (K) by leveraging Lemma 6
and decomposing the error via
K
K
RLS KK) <
Σ
ITT, - 0zw0l
Σ
ITTT 02
h
h
(1.))
k=
(o,)
Under event Ex, we have
(,,, 0..0) 5 1
[TT, 0f,0 S 1 62),
40

---

where YK (x(61,60) 62) = 3x (ő1, 02)
+ 1)c'd/613 and Bx (61, 62) is defined in Lemma
Then, from Assumption we have
k
Σ
101
h
(K.))EO
(O
K
Σ
I -10 - 02.
h
km
(1,))Exx
K
(x101100) I is
k
k=
(KA)EO, 1ON-1
K
= (k 62)
k
(1,))Ex
< <>x(01, 02)
Σ
k
Vaminn(i 1)
(i.DEON
Tx (2)
kk/2 2 du
Va
Ju=D Vu
1k(61, 82) Va
VV
<2)221,6))2//) 62)22//aa
du
Vu
= 7x (xx(618)))4 /, 2K/a
under event Ex. Using similar derivation for the 3x 9x(61,00 62) case, the following inequality holds under event Eg:
RRLS (3x(01, 82) + 7 82)) 4 2/2Ko
(x1( 52) log K K(K 1)cd/813 4/2K/a
Bounding (T). Leveraging Abeille & Lazaric RT'S (K) under the event Ex:
2017
pages 6-7), Definition lets us bound
TT (T)(K) E 47k (f1, 82)
K
Σ
Σ
aargmax .E x (B..lll.
k
(1.1)E0, 10--1
We can bound the expectation under Assumption as
E
argmax x 0 (.
Vaminii, t)
Using derivation similar to that of RRLS (K), it then follows that
RTS(K) (7x( 52) 4/2K/a
p
under event Eg-
Overall bound. Composing the three bounds yields the following upper bound:
4v2K (xx(0 62) (T (++ [a)
1 7K (81,
(2)
1 1 }
}
Va
41

---

with probability at least - 61 - 82. With á = 281 and sufficiently large the bound holds with probability least 1 stated in Theorem The rate in the main paper follows by noting that
Bk( 62) O V [l) + log (LK)
7k (61, (2) = 3x (81, 02) ( (2²
O(Vd).
V@
F Notation Guide
For convenience, summarize below some key notation used in the main paper.
0: Control action
Number of non-baseline treatment arms
= 1,2....: Index for users
1,2,..... Index for time points
St,t S: Context vector observed for user at time point
Ai, E {O..... g}: Action chosen for user at time point
Ri, E R: Reward observed for user i at time point t
(t, a) = E [R,, St, = 8, A = a]: Conditional mean for the observed reward given the state and context
(s, = ra,e(s, a) (i, 0): Linear differential reward for any action >> O and state
Hi, History up time point / for user
Ts,((ass): Probability of action [K] given context E S for fixed (implicit) history
Tmin, Tmaxx Lower and upper limits for (0)s() respectively
A E [K]: The optimal arm
At, [K]] The optimal non-baseline
Ar, E [K]]()} chosen
Potential non-baseline arm that may be chosen if the baseline arm is not
The set of observed time points across all users at stage the sequential requirement setting
O₂ (ii,t) i k i}:
z(s, a) E Rd: Feature vector depending on the state and action
02, TR.: Vector of parameters that may depend on the user and time point Later 0,,, is written as 0g,, gehared + geser + gtime, where guser the user-specific but time-invariant term and gfime is shared time-specific
gs(: Baseline reward function (conditional mean) that is observed when random-
ized to receive no treatment
da>o: Indicator function that takes the value if
otherwise
Eigi Conditionally mean-zero, sub-Gaussian error
a)) Working model for the true conditional mean (s,
(x, Pseudo-reward given state Si, s and potential arm a, which has the same
expectation as the differential reward, (,,,,,, āc,:); this term is written as Re in some points in the main paper, with the state and action implied
Wy: The j-th fold, of J total folds for sampling splitting
desi The enlarged feature vector with wi, placed in positions corresponding to @shared Juser and gfiee di.t ((x4,e) C.
42

---

oe (0,,00)),,)) {1 (0),,)) Weights used in the penalized regression estimation, which are inversely proportional to Var(R
Cr,e: Matrix defined [1, 0,-1, 1, 0x-itt-1: 1, x @
Guser = (Vuser; Fuweer; Güiee (Vimes Frime): Graphs for the nearest-neighhor networks across users and time, respectively
Q: Incidence matrix where the element Qu corresponds to the w-th vertex (user) and e-th edge
Luver: Lime:
Laplacian matrices for users and time, respectively
A: Hyperparameter for Laplacian penalization
Hyperparameter for ridge penalization
(6)( Term used to scale confidence sets; see
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract offers a brief summary of the paper's motivation and contribu- tion, while the introduction delves deeper into background details and highlights the key components of our proposed algorithm.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: the Discussion section (Section 7), we reflect on limitations related to computation, modeling assumptions, hyper-parameter tuning, and practical implementation.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
44

---

Answer: [Yes]
Justification: We present all assumptions clearly, each numbered for reference, and we provide the full set of assumptions in Theorem Additionally, the proof is available in the Appendix, and within the main text, we indicate where the corresponding proof can be found.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: In the manuscript, we provided clear description of the proposed algorithm in Algorithm Additionally, we elaborated on the key components of the algorithm in Section Furthermore, in Section 6.I we outlined the simulation setup, with detailed information
available in Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
45

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
The primary simulation results can be entirely reproduced using the provided code on Github. However, the Valentine study data, used for our real-world analysis, is not publicly accessible.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.co... ctsipss.c/pubbic/guuiic wewpgeeeeeeeeeeuubaiiiiiaeaaaaae soi.siubiiiiiiooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Algorithm Dreuuiresss data splits, and devoted two paragraphs on Page 5 to discussing options for this split. Additionally, we clearly listed all of the hyperparameters involved in forming objective functions and provided guidance how to make suitable choices for them.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Section 6.2
the experiment results include hypothesis testing, and we have clearly indicated the p-values in the Figure legend to denote statistical significance.
46

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: At the start of Section offer paragraph outlining the computer resources required to reproduce the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics /thhes/hhhh/////rrrrs.../o////b/ wtwp:/tehiicuuudeeeeeeeeee..
Answer: [Yes]
Justification: The author has obtained permission to access both the Valentine study and the Intern Health Study dataset. It's important to note that the experiments conducted in this paper are purely numerical simulations and offline evaluation of existing data, which do not involve any human research subjects participants.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
47

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This paper is driven by the current challenges in mobile health policy learning. aiming to enhance policy learning maximize the benefits of mobile interventions. As result, we emphasize the societal impacts, focusing on how the algorithm has the potential improve public health.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
48

---

We have cited the associated papers that produced the code package and dataset in 6
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com /daaaset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The Appendix includes a link to our GitHub repository that contains the code to reproduce our simulation study.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
49

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
50


Reviews:
[{"review_id": "BMT8p85MxN", "reviewer": "Reviewer_cFGH", "summary": "The paper introduces a novel robust mixed-effects bandit algorithm, named \"DML-TS-NNR\", designed to optimize mobile health (mHealth) interventions. mHealth aims to deliver personalized and contextually tailored notifications to promote healthier behaviors. The proposed algorithm addresses key challenges in mHealth, such as participant heterogeneity, nonstationarity, and nonlinearity in rewards. The main contributions of the paper are:\n- Modeling Differential Rewards: Incorporates user- and time-specific parameters.\n- Network Cohesion Penalties: Uses penalties to pool information across users and time.\n- Debiased Machine Learning: Employs this technique for flexible baseline reward estimation.\n\nThe algorithm's high-probability regret bound is solely dependent on the differential reward model's dimension. The effectiveness of DML-TS-NNR is demonstrated through simulations and two off-policy evaluation studies.", "questions": "- How robust is the algorithm to violations of the assumptions regarding the network structure and hyperparameters? Can the authors provide guidance on tuning these parameters in practice?\n- How can the algorithm be extended to consider long-term effects and treatment fatigue? Are there plans to address these aspects in future work?", "limitations": "While the authors have made strides in addressing some key limitations, such as computational demand and network assumptions, there are still areas that may need further attention:\n- The high computational demand due to log-determinants and matrix inverses is a limitation. Future work should explore more efficient computational methods or approximations.\n- The algorithm focuses on immediate rewards and does not consider long-term effects or treatment fatigue. Addressing these aspects is crucial for real-world applicability and effectiveness.\n- The need for correctly specified hyperparameters can be challenging in practice. Providing more robust methods for hyperparameter tuning and addressing potential misspecifications would improve the algorithm's robustness and ease of use.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The integration of user- and time-specific incidental parameters for modeling differential rewards.\n- The novel application of network cohesion penalties and debiased machine learning in the context of mHealth interventions.\n- The empirical validation through simulations and real-world mHealth studies demonstrates the practical applicability and effectiveness of the proposed algorithm.\n - The paper is well-structured and clearly explains the problem, the proposed solution, and the results.\n - The algorithm addresses significant challenges in mHealth, potentially improving the effectiveness of personalized health interventions. By achieving robust regret bounds and superior empirical performance, the algorithm can contribute to advancements in personalized healthcare technologies.", "weaknesses": "- The algorithm's reliance on complex calculations, such as log-determinants and matrix inverses, may limit its scalability for large datasets.\n- The assumption of a known network with binary edges may not always be practical. Real-world networks can be more complex, and this assumption might limit the algorithm's applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Weaknesses & Hyperparameters\n\nThank you for raising these concerns. Other reviewers asked about them as well. Our main rebuttal contains a detailed discussion of all three. Below, we include a brief summary of the main points and a few additional details for your specific questions:\n\n1. **Computation:** We made our implementation extremely efficient using sparse rank-one updates to Cholesky factors. In its current form, DML-TS-NNR is about three orders of magnitude faster than is required for a typical mHealth research study. Several optimizations and approximations could be used to speed up the algorithm even more for large data sets.\n2. **Known Network:** This limitation is shared with all or nearly all of the related work in graph bandits. Our new sensitivity analysis shows that the algorithm is fairly robust to specification of the network. The algorithm can easily be extended to include edge weights; the only required change is scaling the corresponding entries in the Laplacian matrix.\n3. **Hyperparameters:** We added eight sensitivity analyses showing that the simulation results are robust to variations in the hyperparameters. While hyperparameters do affect the performance of DML-TS-NNR, the differences between methods are much larger than the differences due to changing the hyperparameters. Empirical Bayes strategies can be used to set the hyperparameters. The penalty hyperparameters ($\\lambda, \\gamma$) can also be interpreted as prior precisions (inverse variances), which can provide some intuition on an appropriate order of magnitude.\n\n# Long-term Treatment Effects\n\nWe see two main approaches to address long-term effects.\n\nThe first approach is specifically designed to address treatment fatigue. It involves modifying the observed rewards by subtracting a penalty from rewards at treated time points (i.e., when $A_{i,t} > 0$). Or, equivalently, we could modify the algorithm such that individuals are treated with probability equal to the “posterior” probability that the differential reward is above a positive threshold as opposed to zero; see Equation (10). The threshold could be set based on a moderation analysis using the weighted, centered least squares method of Boruvka et al., 2018 [2]. Specifically, we would estimate treatment moderation according to a model including a linear term for the number of previous treatment occasions (perhaps over some moving window, such as the last 10 time points). Then we would set the threshold equal to the corresponding estimate for this linear moderation term, effectively anticipating the impact of current treatment on future outcomes.\n\nThe second approach would be to generalize some of the ideas from this paper to more flexible RL methods, such as Q-learning. These methods directly model long-term effects, but uncertainty quantification is generally more challenging relative to bandits and may require some form of Markovian assumption, which would likely be unrealistic in mobile health.\n\nWe do not have immediate plans to pursue these directions. However, we are actively involved in designing and analyzing mobile health studies, and we plan to use DML-TS-NNR to optimize online decision making in these studies. If we observe empirically that DML-TS-NNR consistently sacrifices long-term performance for small short-term improvements, then we will revisit this problem and the approaches outlined above.\n\n[2] Boruvka, A., Almirall, D., Witkiewitz, K., & Murphy, S. A. (2018). Assessing time-varying causal effect moderation in mobile health. Journal of the American Statistical Association, 113(523), 1112-1121.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HmucmWE16H", "reviewer": "Reviewer_SKyx", "summary": "The authors propose a novel contextual bandit algorithm that addresses individual heterogeneity, nonstationarity, and nonlinearity of the reward function. This algorithm involves three distinct steps to manage these challenges.", "questions": "I found the comments on page 4 about the doubly robustness concerning. As the methods discussed in Section 4.1 are all nonparametric estimators (hence, the model misspecification is not an issue), the benefit of incorporating DML is to improve estimation efficiency.", "limitations": "not noted.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The current paper is easy to follow and addresses a complicated scenario that has not been frequently discussed in the literature.\n\nThe methods are well organized and the theoretical discussions are helpful.", "weaknesses": "The selection of tuning parameters plays a crucial role but is not discussed in the proposed method. It is unclear whether the promising performance of the proposed algorithm is due to the choice of a specific tuning parameter. Providing some robustness checks would enhance the soundness of the simulation experiments.\n\nI also need some motivation for Assumption 4. For example, how well does the dataset under investigation support this assumption? In its current form, Assumption 4 appears to be arbitrary.\n\nI also found the assumption of a known network structure to be quite restrictive, as network structures are typically unknown in practice. This limitation hinders the practicality of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments. We address the outlined weaknesses and questions below.\n\n# Hyperparameter Tuning\n\nHyperparameter selection plays an important role in the performance of bandit algorithms. While virtually all such algorithms require specification of some hyperparameters (at a minimum, a “prior” mean and variance), DML-TS-NNR does require more than a basic parametric bandit algorithm (e.g., the Standard method in our simulations). As detailed in the main rebuttal above, we added 8 sensitivity analyses to assess the impact of our method’s hyperparameters on its performance. The main finding is that DML-TS-NNR consistently outperforms the other methods in the Nonlinear Setting (the most realistic) even when we specify poor hyperparameters. The reason for the superior performance is that DML-TS-NNR is the **only one that accounts for all of the important problem structure**, including heterogeneity across users and time, explainable variation in baseline rewards, and network information. These results suggest that correctly accounting for the problem structure is relatively more important than hyperparameter tuning. This is analogous to the fact that out-of-the-box ML models often outperform tuned linear models (e.g., ridge regression / LASSO) on nonlinear regression tasks.\n\nWe also re-emphasize that there are adaptive strategies that could be explored for setting many of the hyperparameters. The primary challenge with these strategies is that the regret bound is not guaranteed to apply when the hyperparameters are not specified in advance. This is an interesting and important avenue for future research.\n\n# Assumption 4\n\nAssumption 4 is best understood by comparing it to corresponding assumptions made by competing approaches. We provide this context below, beginning with simple bandit algorithms:\n\n- **Standard / AC:** Were we to apply Standard / AC to the mHealth setting, we would effectively be assuming that $\\theta_{i,t} = \\theta^{\\text{shared}}$ for all $i, t$. This assumption is clearly very limiting and partially explains the poor performance of these methods in the simulation / case studies.\n- **NNR-Linear:** Graph bandit approaches, such as the NNR-Linear method from our simulation, allow all users to have their own parameters, effectively assuming $\\theta_{i,t} = \\theta_{i}^{\\text{user}}$. By regularizing these parameters toward each other and zero (i.e., including penalties analogous to $\\lambda$ and $\\gamma$, respectively), we are essentially expressing a prior belief that the $\\theta_{i}^{\\text{user}}$ values are small and similar between neighbors. A slight improvement to this approach is to set $\\theta_{i,t} = \\theta^{\\text{shared}} + \\theta_{i}^{\\text{user}}$ so that estimates are regularized toward the (learned) shared parameter instead of zero. These graph bandit approaches are much more effective than the Standard / AC approach in heterogeneous settings; however, they still assume constant effects over time, which is why NNR-Linear is not competitive in our Nonlinear simulation setting.\n- **Mixed Model Approaches:** A common solution to this problem in mixed modeling is to assume a random slopes model: $\\theta_{i,t} = \\theta_{i0}^{\\text{user}} + t \\cdot \\theta_{i1}^{\\text{user}}$; i.e., we assume a subject-specific linear trend over time. This assumption improves on the static assumption of graph bandit approaches, but it is still highly parametric and likely to be misspecified.\n\nWith this information as background, we can see that Assumption 4 improves on simpler (and commonly used) alternatives by allowing for variation across both users and time. Unlike the random slopes model, we allow for non-parametric trends over time by including a separate parameter for all members of the (infinitely increasing) set of time points. We also note that IntelPooling employs a version of Assumption 4 by including both user- and time-specific random effects.\n\nWe conducted an exploratory analysis of the Valentine Study to motivate the user-level and temporal effect heterogeneity. For this analysis, we formed pseudo-rewards according to Equation (3) and conducted an ANOVA test. The results (Table 2 of the rebuttal PDF) show strong evidence of both forms of heterogeneity. Figure 1 in the rebuttal PDF shows a Loess fit of the causal effects over time, indicating strong nonstationarity in the causal effects.\n\n# Network Structure Assumptions\nSee our main rebuttal for a discussion of this point. To the best of our knowledge, all work in this literature, including Cesa-Bianchi et al. 2013, Herbster et al 2021, Vaswani et al. 2017, Choi et al. 2023 and many other papers use the same assumption of a known network structure. In many cases where contextual bandits are useful, such as in social networks, there are known relationships between users.\n\nThat said, learning the network structure is a potentially important avenue for future work: thank you for mentioning this.\n\n# Double Robustness and DML\n\nWe see the point being raised. The regret bound does indeed require the ML model to be a consistent estimator of $f$ (Assumption 3); hence, a nonparametric estimator of $f$ is needed in general for the regret bound to apply.\n\nIn the proof of the regret bound, however, the only impact of consistently estimating $f$ is that it reduces the size of certain confidence sets, resulting in a tighter regret bound. As long as $f$ converges to a bounded function, DML-TS-NNR still produces a regret bound with the same asymptotic order, but the constants in the regret bound could be improved by consistently estimating $f$. Thus, the robustness to misspecification of $f$ in the pseudo-reward (lines 136 – 137) does have important theoretical implications when Assumption 3 fails. It is for this reason that we listed parametric models in lines 151-152. This is a subtle point that we could briefly explain in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ltxrCZXKpJ", "reviewer": "Reviewer_HodX", "summary": "The paper \"A Robust Mixed-Effects Bandit Algorithm for Assessing Mobile Health Interventions\" introduces the DML-TS-NNR (Debiased Machine Learning Thompson Sampling with Nearest-Neighbor Regularization) algorithm. This novel contextual bandit algorithm is designed to address challenges in mobile health (mHealth) interventions, such as participant heterogeneity, nonstationarity, and nonlinearity in rewards. The algorithm incorporates user- and time-specific incidental parameters, network cohesion penalties, and debiased machine learning to flexibly estimate baseline rewards.", "questions": "1. Can the authors elaborate on why specific baseline methods (e.g., Standard Thompson Sampling, Action-Centered contextual bandit) were chosen for comparison? What advantages do these techniques offer for evaluating the effectiveness of the DML-TS-NNR algorithm in mHealth interventions?\n\n2. How does the DML-TS-NNR algorithm perform in more diverse and dynamic real-world settings, such as different health conditions or treatment modalities? Are there plans to test the approach in more varied environments, including chronic diseases or mental health applications?\n\n3. What potential challenges could arise regarding the scalability of the DML-TS-NNR algorithm for very large datasets or real-time applications? How does the algorithm handle computational and communication overhead in such scenarios?\n\n4. Can the authors provide more details on the optimization process for debiased machine learning and its impact on overall performance and accuracy of reward estimation?\n\n5. What are the potential ethical considerations or privacy concerns associated with the proposed method, particularly in using sensitive health data for mHealth interventions? How does the DML-TS-NNR algorithm address these concerns?", "limitations": "1. Potential challenges and mitigation strategies for deploying the DML-TS-NNR algorithm in real-world settings, particularly regarding data diversity and environmental variability.\n2. Discussing the ethical implications and privacy concerns related to continuous monitoring and intervention in high-stakes healthcare applications. This includes addressing the implications of using sensitive patient data and the potential impact of intervention decisions on different demographic groups.\n3. Further exploring the trade-offs between computational efficiency and intervention accuracy, particularly in scenarios where rapid decision-making is crucial for clinical outcomes.", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "### Originality:\n\nThe DML-TS-NNR algorithm introduces a novel approach by combining debiased machine learning, network cohesion penalties, and Thompson sampling to address the unique challenges in mHealth interventions. The use of user- and time-specific incidental parameters and the flexible estimation of baseline rewards via debiased machine learning are innovative contributions that enhance the adaptability and robustness of the algorithm.\n\n### Quality:\n\nThe methodology is rigorously developed, with comprehensive theoretical analysis and detailed proofs provided for the high-probability regret bounds. Extensive experimental validation includes simulations and real-world mHealth studies, demonstrating the algorithm's effectiveness and practical viability.\n\n### Clarity:\n\nThe paper is well-structured, with clear explanations of the problem statement, related work, methodology, experimental setup, and results. Figures and tables effectively illustrate the proposed method and its performance improvements. Technical terms and concepts are explained thoroughly, ensuring accessibility to a broad audience, including those not deeply familiar with contextual bandit algorithms or mHealth interventions.\n\n### Significance:\n\nBy addressing critical challenges in mHealth, such as participant heterogeneity and nonstationarity in rewards, the DML-TS-NNR algorithm has significant implications for improving personalized treatment strategies and patient outcomes.", "weaknesses": "### Novelty:\n\nWhile the combination of debiased machine learning, network cohesion penalties, and Thompson sampling is innovative, a more detailed comparison with existing methods, particularly in terms of theoretical and practical advantages, would further highlight the unique contributions of the proposed DML-TS-NNR algorithm.\n\n\n### Experimental Validation:\n\nThe experimental validation primarily relies on controlled datasets. Including more diverse real-world testing scenarios, such as various health conditions or treatment modalities, would provide a more comprehensive assessment of the DML-TS-NNR algorithm's effectiveness and generalizability.\n\n\n### Technical Details:\n\nSome aspects of the algorithm, such as the optimization process for debiased machine learning and the derivation of the network cohesion penalties, could be explained in greater detail to enhance clarity and understanding. The choice of evaluation metrics and their suitability for different types of mHealth interventions could be discussed more extensively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and questions. We address the latter below.\n\n# Q 1\n\nWe included a wide variety of competing algorithms (see appendix for the full set) to (1) assess how well DML-TS-NNR performs relative to simple baselines and (2) understand which aspects of DML-TS-NNR contribute most to its performance.\n\n1. The comparison to Standard and AC shows that there is a large benefit to pooling data across users.\n2. The comparison to NNR-Linear shows that the benefit of DML-TS-NNR is not entirely due to the additional regularization (though, it is helpful).\n3. The comparison to DML-TS-SU shows that ignoring participant heterogeneity leads to suboptimal performance.\n4. The comparison to DML-TS-NNR-BLM (which uses bagged linear models instead of an ensemble of online decision trees) shows that DML-TS-NNR is robust to the choice of supervised learning algorithm but that a more flexible algorithm can lead to better performance when the baseline rewards are nonlinear.\n5. The comparison to IntelPooling, the most relevant previous method, shows that there is additional benefit to the new components of our method: NNR and DML (IntelPooling uses neither).\n6. The comparison to Neural-Linear shows that the performance of DML-TS-NNR is not entirely (or even largely) due to the flexible baseline model; the time effects and NNR also play an important role.\n\n# Q 2\n\nThe appendix includes an additional off-policy evaluation study for the Intern Health Study (IHS). IHS is a mental health study for medical interns. Similar to the case study in the main paper, we again found that DML-TS-NNR outperformed competing algorithms.\n\nThus, to answer your question, we have applied DML-TS-NNR to two different areas already and DML-TS-NNR achieved state-of-the-art performance in each. We are involved in applied collaborations in multiple sub-areas of medical and behavioral science and plan to use DML-TS-NNR across these domains. While we do not foresee any particular difficulties for specific domains, we expect that these collaborations will lead to an improved understanding of when DML-TS-NNR performs particularly well (or poorly) and how to address practical issues, such as specification of the context and reward variables.\n\n# Q 3\n\nOur main rebuttal addresses this point. In its current form, we think the algorithm could be used without modification/approximation up to about 1,000 stages—much more than most academic mobile health studies. At that point, some of the strategies suggested in the main rebuttal could be used to enable scaling to even larger data sets.\n\nReal-time implementation of the algorithm across many mobile devices would require communication between each user’s device and a central server. While this carries numerous engineering difficulties, the methodological difficulties are fairly limited. The system could be set up such that devices send information to the server each time a decision is required, which would require essentially no methodological changes. Alternatively, the algorithm parameters ($V, b$ in particular) could be updated in batches, and the mobile devices would make decisions using the most up-to-date cached parameter values available to them. In this case, the mechanics of the algorithm would remain essentially unchanged; however, the regret bound would need to be adapted to account for the batched updates.\n\n# Q 4\n\nOne of the benefits of the DML-TS-NNR algorithm is that it remains agnostic to the choice of the specific supervised learning model and its corresponding optimization algorithm. The only theoretical requirement is the consistency condition of Assumption 3. In fact, as pointed out in our response to reviewer cFGH, we could still obtain a regret bound of the same asymptotic order as that given in Theorem 1 (albeit with larger constants) under violations of Algorithm 3, provided the supervised learning model converges to a bounded function.\n\nThat said, we generally expect highly predictive supervised learning models to produce the lowest regret. Consequently, it would be reasonable to select a supervised learning algorithm via standard cross validation techniques (though, adaptive strategies like this are not necessarily compatible with our regret bound).\n\nWe also note that our additional simulations in Appendix B include a comparison of two supervised learning algorithms: an ensemble of online decision trees (used in the main paper) and a bagged ensemble of linear models. The former performed slightly better in the Nonlinear Setting (beating DML-TS-NNR in 30/50 simulations), presumably because it is flexible enough to model the nonlinear baseline rewards.\n\n# Q 5\n\nTo address these privacy considerations, we would need to ensure that data is transmitted from mobile devices to the server in a secure fashion. We would also need to ensure that the server meets the relevant requirements (e.g., HIPAA in the United States) for collecting, storing, and processing that data. The data transmission from the server to the devices would be less of a concern because the data is aggregated (in fact, we would not need to send the parameters for user $i$ to user $j$ [with $i \\neq j$]).\n\nRegarding the treatment of different demographic groups, we believe the personalized, network-based nature of DML-TS-NNR has the potential to ameliorate these concerns. Allowing users to have their own parameters means that decisions will be directly adapted to users’ own actions—not the conglomerate of some larger population. If practitioners believe that treatment effects will vary substantially by demographic group, then demographic information could be used to design the network structure. The result would be that the algorithm would suggest treatments that are effective for “similar” (based on the network) users rather than treatments that are effective for the “average user,” particularly in the early stages for a given user when subject-specific data is minimal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KVNZSLPww8", "reviewer": "Reviewer_JBD9", "summary": "The paper introduces a robust contextual bandit algorithm to optimize personalized mobile health interventions. The proposed algorithm leverages Thompson sampling, mixed-effect models, debiased machine learning, and nearest-neighbor regularization techniques to address the problems of user and time heterogeneity, information pooling, and complex baseline rewards. The paper establishes a high-probability regret bound and demonstrates the algorithm’s effectiveness compared to existing methods through a simulation and two off-policy evaluation studies.", "questions": "-\tIt is mentioned in the appendix that the nearest neighbor network is assumed to be known in the simulation study, and that the number of nearest neighbors k is set to 5 in the Valentine Study. Could the authors provide details on how the nearest neighbor network is defined in the simulation study and how the number of nearest neighbors is chosen in the Valentine Study? Is the algorithm's performance sensitive to the construction of the nearest neighbor network?\n-\tThe paper lists several feasible choices for the working model f_{i,t}. However, its construction in the simulation and real data analysis was not detailed. It would be helpful if the authors could discuss how the working model is chosen in practice.\n-\tAssumption 1 ensures that the randomization probability for action 0 is always positive, but it does not specify this for other actions. Is a positivity assumption required for all actions in the proposed method? If so, the authors should discuss how this is ensured for other actions.\n-\tComputational efficiency is crucial for online algorithms. It would be beneficial if the authors could provide the computation time of the proposed method, e.g., in the simulation study or the Valentine Study. How does it compare with the baseline methods? \n-\tIn the single-column vector \\theta, user-specific parameters are numbered from 1 to K. Should they instead be numbered from 1 to N, as in the \\Theta_{user} matrix? Besides, it seems that N has not been defined in the main text.", "limitations": "The authors have discussed the limitations of the proposed method.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "-\tThe paper proposes a method to effectively address three common issues in mobile health: treatment effect heterogeneity across users and time, the need to pool information across users, and the possibility of complex baseline rewards.\n-\tThe simulation and real data study sufficiently demonstrate the advantages of the proposed method in the presence of heterogeneous users and nonlinear baseline rewards, and discuss its limitations when users are homogeneous.\n-\tThe paper is well-organized and easy to follow.", "weaknesses": "The proposed method combines several existing techniques, including Thompson sampling, mixed-effect models, debiased machine learning, and nearest-neighbor regularization. Could the authors elaborate on the specific challenges associated with the proposed method, whether in terms of methodology, computation, or theoretical proof?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We address the listed weaknesses and questions below.\n\n# Weaknesses\n\nYes, there are three primary challenges. We will include these descriptions below in the final revision.\n\nThe first is the methodological challenge of figuring out how to bring all of the pieces together. DML, for instance, requires independent subsets of data, so we had to develop a data-splitting technique that is appropriate for dynamic settings. As another example, NNR is typically applied to distinct users in stationary settings, so we had to adapt the technique to handle nonlinear time trends.\n\nThe second challenge is extending the standard proof techniques for bandit regret bounds to handle (a) the nonlinear baseline reward and Graph Laplacian regularization and (b) our method’s growing number of parameters. For (a), we need to adapt the standard proof bounding the regularized least squares (RLS) linear predictor error to handle the use of weighted least squares, the non-linear baseline and Laplacian regularization (our Lemma 6). This requires careful analysis of how the RLS estimator relates to the double robustness of the pseudo-reward and bounding the variance of the pseudo-reward. For (b), our final regret bound involves a sum of such regularized least squares linear predictor errors, which is bounded by a sum of weighted norms of feature vectors inverse scaled by stages. Bounding this requires a simple but non-obvious application of Cauchy-Schwarz to decouple the weighted feature norms from inverse stage scaling, which allows us to apply standard techniques to the sum of norms and bound the sum of inverse stages by the harmonic number.\n\nThe third challenge was creating an efficient implementation. Re-computing inverses and log determinants at every stage would have been prohibitively slow, so we had to experiment with efficient rank-one update procedures (implemented via the SuiteSparse package).\n\n# Question 1: Network\n\nOur main rebuttal contains a discussion of these points, including some recently added sensitivity analyses. To summarize, the quality of the network and number of neighbors does influence the performance, but these differences are small relative to the differences between methods.\n\nTo form the network, we created a distance metric using four baseline covariates: gender, age, device, and baseline average daily steps. Then we connected users to their 5 closest neighbors. We had to move this information to the appendix due to space restrictions.\n\n# Question 2: Supervised Model Selection\n\nBecause the simulation required many repetitions over three settings and eight methods (including those in the Appendix), our goal was to find a nonlinear regression method that had an easy-to-use and computationally efficient online implementation. The River library contains several regression methods that meet these criteria. We chose an ensemble of decision trees (essentially a random forest) because we have found that random forests typically perform well with limited tuning.\n\nWe also used a random forest model for the case study, largely for the reason stated above. However, the computational demands were lower, so we were actually able to refit it at each stage using standard (not online) decision trees.\n\nIn general, we recommend using nonlinear regression methods. When computation time is not a large concern, we recommend choosing a method with high predictive accuracy for the problem, which could be assessed using previous studies or in an adaptive fashion via cross validation. When computation time is a major concern, we recommend selecting methods that have efficient online updates. In particular, linear models with flexible basis functions (e.g., splines) are particularly well suited because they have efficient rank-one updates.\n\n# Question 3: Assumption 1\n\nThis is somewhat of a subtle point. We sample actions in a hierarchical fashion. We first select a non-baseline action and then we randomize between that action and the baseline (“do-nothing”) action. The regret bound is based only on the second randomization. It bounds the regret of a policy that is restricted to two actions: the baseline action and the given non-baseline arm. Consequently, the $K$ appearing in the regret bound is really the number of stages in which the given non-baseline arm is selected. Our analysis mimics that of the action-centered (AC) paper in this regard (Greenewald et al., 2017).\n\nTo summarize, we do not list a positivity assumption for other actions because we define and bound the regret in a way that restricts the randomization to a single non-baseline arm. In practice, however, introducing more arms will generally lead to higher overall regret (with a fixed total study length) because less data will be available for each arm.\n\n# Question 4: Computation Time\n\nThank you for the good suggestion. We reported these timings in the main rebuttal.\n\n# Question 5: $N$ vs. $K$\n\nThank you for catching this. In our asymptotic regime, $N = K$, so either is correct. For consistency and simplicity, however, we have replaced the $N$’s with $K$’s in the main text. The algorithm could still be applied under a more realistic regime in which $N \\neq K$, but the matrices would need to be resized based on the number of users ($N$) and time points ($T$).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their helpful and positive comments, including “the paper is well-structured and clearly explains the problem, the proposed solution, and the results” and “The methodology is rigorously developed, with comprehensive theoretical analysis and detailed proofs.” Here we address points made by several reviewers, and we provide individualized responses to comments that are unique to specific reviewers.

# Hyperparameter Tuning & Robustness

In the paper’s main simulation study, we chose hyperparameters for the fairest comparison possible, employing the same regularization parameters across methods. To assess robustness, we recently added 8 sensitivity analyses that alter hyperparameters for our methods while fixing those of the other methods; this approach gives the competing algorithms an (arguably unfair) advantage. Our proposed algorithm, DML-TS-NNR (and the variant DML-TS-NNR-BLM) still dramatically outperform the other methods in the Nonlinear Setting. We provide detailed results below.

Three analyses led to no meaningful changes to Figure 1 or Table 2. These involved rescaling (1) $\gamma$, (2) $\lambda$, (3) and the bounds $B, D$ by a factor of 10: . The remaining simulations resulted in minor performance differences, especially in the Heterogenous Setting. Below, we summarize these five analyses:

- **Adding (low and medium) noise to the network:** NNR-Linear slightly outperforms our methods in the Heterogeneous Setting, winning 50-60% of simulations (compared to 40-42% without noise) because NNR-Linear has access to a higher quality network. Table 1 of the attached PDF displays pairwise comparisons for the medium noise level.
- **Increasing to 10 neighbors:** DML-TS-NNR, DML-TS-NNR-BLM perform much better than DML-TS-SU (the Single-User ablation) in the Heterogeneous Setting, presumably because this change enforced stronger network cohesion among highly similar users.
- **Rescaling $\sigma$ by 10:** NNR-Linear outperforms our methods in the Heterogeneous setting. NNR-Linear and IntelPooling outperform DML-TS-SU (but not DML-TS-NNR) in the Nonlinear Setting. Both occur because NNR-Linear and IntelPooling use the true value of $\sigma$.
- **Setting delta to 0.05:** NNR-Linear outperforms DML-TS-SU in the Nonlinear Setting, likely because this change led to insufficient exploration; see line 220 and Equation (8).

A heuristic strategy to set $\lambda, \gamma, \sigma$ is to use an empirical Bayes approach like that of the IntelPooling paper (Tomkins et al., 2021). Similarly, we could adaptively set the bounds $B, D$ using the parameter estimates. Deriving a regret bound under these techniques is an interesting future challenge.

# Scalability

Several reviewers expressed concern about computational efficiency when computing matrix inverses and log-determinants over a large parameter space. As suggested by Reviewer JBD9, we timed the algorithms in the simulation study. The average wall times (in seconds) in the Nonlinear setting were as follows (in increasing order):
- **AC:** 1.45
- **Standard:** 4.90
- **DML-TS-NNR-BLM (Bagged Linear Models):** 52.46
- **IntelPooling:** 66.15
- **NNR-Linear:** 71.39
- **DML-TS-SU:** 403.69
- **DML-TS-NNR (online decision trees):** 452.57
- **Neural-Linear:** 3013.04

As the simulation involved 200 stages, the timings produced 200 * 201 / 2 = 20,100 decisions for each method. Neural-Linear was the most time consuming because it requires neural network predictions for each reward (without a GPU). As expected, our methods were generally slower than the competitors. However, the difference between DML-TS-NNR-BLM and DML-TS-NNR indicates that much of the additional computation time is due to ML model fitting. From a computational standpoint, the reason that our method remained competitive is that (1) V is sparse and (2) we used efficient rank-one updates to Cholesky factors to avoid recomputing large matrix inverses and determinants. Real scientific mHealth applications typically require fewer than 1,000 decisions per day, so the computation time above is $\frac{20,100 / 452.57}{1,000 / (24 * 60 * 60)} \approx 3,837$ times faster than necessary.

In a large-data setting, the performance could be further optimized by:
- Updating $V, b$ in batches
- Parallelization
- Taylor approximations for the matrix inverse (see Yang et al. 2020)
- Fast approximate log-determinant computation [1]
- Forming networks with “closed” clusters, which would allow us to compute the inverse and determinant in blocks

# Known Network Assumption

Assuming a known network can indeed be limiting in practice. However, this limitation is shared with all or nearly all of the graph bandit literature, including Cesa-Bianchi et al. (2013), Vaswani et al. (2017), and Yang et al. (2020).

We assessed the importance of this assumption in our sensitivity analyses by adding noise in the network construction. We originally set the network structure by connecting users / time points to the 5 other users / time points with the most similar parameter values. In the sensitivity analyses, we added artificial noise to the parameter values before network construction, resulting in a lower quality network. As explained above, this modification resulted in only a slight decrease in performance.

In some cases, as in the Intern Health Study in our Appendix, there is an a priori known network structure. In other cases, it may be reasonable to propose a distance metric using baseline covariates (or proximity of time points). An interesting future direction would be to set the network in an adaptive fashion, perhaps using some form of sample splitting. Again, a primary challenge with an adaptive strategy like this is showing that the regret bound (or a modified version of it) is still valid.

[1] Boutsidis, Christos, et al. "A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix." Linear Algebra and its Applications 533 (2017): 95-117.

Meta-review: The paper proposes a new contextual bandit algorithm, namely DML-TS-NNR, for mHealth which can effectively incorporate the nonstationarity, nonlinearity and user heterogeneity of the health outcomes.
DML-TS-NNR allows the baseline outcome (outcome under "no action") to be highly complex and imposes a parametric structure only to the differential reward. The differential reward model parameter includes user specific and time specific parameters, with minimum assumptions that parameters of proximal users (according to a known network) and proximal time are similar. Laplacian regularization is employed to efficiently pool information across users and time. Finally, debiased machine learning methods are employed in the construction of a doubly robust estimate of the differential reward, which reduces the variance of existing IPW estimates. The paper also provides a regret upper bound which solely depends on the dimension of the differential reward model. 

The paper is well-motivated from mHealth applications and provides a novel algorithm that is robust to the frequently occurring challenges such as nonstationarity, heterogeneity, and complexity of baseline rewards. These points are well supported by theory and extensive experiments.

Some concerns raised by reviewers were as follows,
- robustness to hyperparameters
- scalability
- the fact that the network structure should be known.

As for the first point, authors have provided in their rebuttal an extensive sensitivity analysis to show the robustness of the algorithm to the hyperparameter values, and also suggested to use the Empirical Bayes method to set the hyperparameters in practice.

As for the second point, authors provided the exact computation time in their rebuttal, showing that the speed is competitive to other existing methods and is fast enough in mHealth scenarios.

As for the third point, as authors claimed, it is true that there exist cases where the network structure is known, and most existing works exploiting the network structure assume the knowledge of the network. Authors also provided some experiments for the case where the network is not known perfectly and showed robustness of their method.
Decision: Accept (poster)