Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts Udvas Das, Waris Radji, Debabrota Basu, Odalric-Ambrym Maillard [email protected]
arXiv:2606.09802v1 [cs.LG] 8 Jun 2026
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France
Abstract We consider a variant of the linear contextual stochastic multi-armed bandits, where the learner must provide recommendations to a group of users, each having its personalised preference vector, and in the presence of context distributions that are drifting over time. Under practitioner-friendly assumptions, we reduce this setting to linear bandit with stationary mean but heteroskedastic and non-stationary noise. We further study the case when the learner must ensure the mean reward of each decision must exceed that of a baseline strategy π0 at each decision step. We introduce Dri-MED, an algorithm inspired from the linear version of the MED strategy, and carefully adapted to handle the non-stationary heteroskedastic noise. We show that the instance-dependent κ 2 ˜ regret scales as Õ ∆ ˜ d (log(T ) , where ∆ is the constraint-aware sub-optimality gap subject to policy π0 , with variance-aware multiplicative term κ that we carefully handle using heteroskedastic regression. We further show Dri-MED enjoys Õ(d) expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.
1
Introduction
Design of Experiments (DoE) has been an integral component of agricultural research, clinical trials, and natural sciences (Neyman, 1923; Fisher, 1926; Diggle & Chetwynd, 2011; Hoshmand, 2018). Suppose a farmer testing whether a new fertilizer, seed variety, or irrigation protocol outperforms the current standard cannot simply apply the new treatment to one plot and draw conclusions. Numerous factors such as soil fertility gradients, microclimatic variation, pest pressure, might confound any naive comparison (Gomez & Gomez, 1984; Tanner et al., 2023). This fundamental challenge DoE aims to address lies in separating the signal of a treatment effect from the noise of environmental heterogeneity. Pioneered by (Fisher, 1926) at the Rothamsted Experimental Station, DoE provides a principled statistical framework for planning agricultural field trials so that valid, reliable, and efficient conclusions can be drawn from inherently noisy observations (Rangaswamy, 1995). The first and most fundamental objective is Validity, i.e., ensuring that an observed difference between a treated plot and a control plot can be causally attributed to the treatment itself, and not to pre-existing differences between plots. Thus, randomized experiment is at the core of sound statistical validation (Banerjee et al., 2020; Raccuglia et al., 2016; Kohavi & Longbotham, 2015) of a experimental design. Treatments must be assigned to experimental units by a chance mechanism, also referred to as an allocation distribution. Reliability: Validity alone is insufficient in practice. Even a perfectly randomized experiment may fail to be reliable if, in the process of exploring new treatments, some field sites systematically receive practices that perform far worse than the current default. In agriculture, this is not merely a statistical concern but an operational and ethical one. A farmer whose plot is assigned a poorly performing treatment suffers an economically damaging yield loss, potentially threatening food security 1
or livelihood. Thus, it becomes imperative to enforce a performance/safety constraint (Pacchiano et al., 2021; Das & Basu, 2024; Amani et al., 2019), to ensure reliability. Safety constraints are typically imposed by performing a baseline action/policy over a control group in each site. Efficiency: Finally, as real-world experimentation is costly, we want to minimize the suboptimal decisions over time and avoid unsafe decisions underperforming that of default baseline. This common, albeit still idealized situation naturally fits the sequential decision-making (Sutton et al., 1998; Lattimore & Szepesvári, 2020) framework, where one observes the impact of an action or intervention by deploying it in an agricultural site and then adapts the future decisions accordingly. Now, suppose we observe a fixed set of farmers across different season. The change in environmental factors can be modelled as drifts in the decision making contexts over multiple interaction episodes. In addition, a critical but frequently overlooked dimension of agricultural experimentation is that different farmers evaluate the outcomes of a treatment differently (Fisher, 1926; Rangaswamy, 1995). A smallholder farmer may weigh yield stability above raw yield maximization, or a farmer in a water-scarce region may prioritize water-use efficiency over all other metrics. Hence, it calls for a design diverse enough that can adapt to these customised preferences. In this work, we study this problem of designing valid, reliable, and efficient sequential experiments for a finite set of farmers experimenting across multiple agricultural sites with control groups and preferences, and across multiple episodes with plausible context drifts to find out optimal interventions over time. Though we elucidate our problem motivation with the agricultural example, the same problem reoccurs across domains, such as clinical trials for drugs and treatments (Réda et al., 2020; Munro et al., 2021), aircraft design optimisation (Mavrotas, 2009), recommender systems (Feijer et al., 2025; Saha et al., 2026) to name a few. 1.1
Problem Setting
We formalise this problem as a variant of the multi-armed bandit problem with a finite set of arms A, from which a learner must recommend actions to be played to a group of H users (or experimental sites), in L successive rounds called episodes. Contexts. The rewards depend on a context that might evolve over episodes. Precisely, within an episode ℓ ∈ [L], the contexts Ch,ℓ are generated from a context distribution Cℓ for all users h ∈ [H]. But the context distribution is non-stationary, i.e. it varies over the episodes ℓ. Then, the learner must recommend one action for each user h ∈ [H]. Upon recommending the actions Ah,ℓ , the learner receives M -dimensional feedbacks Yh,ℓ , where Yh,ℓ is a random vector of dimension M generated by an unknown distribution, with a specific linear structure (Assumption 2). Preferences. Each user h further has a preference ph ∈ RM over the vectorial feedback. This ⊤ further yields a reward rh,ℓ (a) ≜ Yh,ℓ ph for user h upon receiving an action Ah,ℓ = a. The goal of the learner is to suggest a sequence of actions h{Ah,ℓ } to the users overi multiple episodes that PL PH maximises the expected cumulative reward, i.e., E ℓ=1 h=1 rh,ℓ (Ah,ℓ ) . Baseline policy. To simulate the control group and action, a mixed baseline policy π0 ∈ P(A) is given to the learner. Given π0 and a tolerance level (1 − ϵ) ∈ [0, 1], the learner must ensure to accumulate at least (1 − ϵ)Eπ0 [rh,ℓ ] reward for each user in each round. This additional constraint forces the learner to recommend policies that are at least as good or better than the baseline policy applied on the control group. Performance metrics: In this setting, performance of an algorithm is measured with two metrics: cumulative regret and expected cumulative number of constraint violations. Lower values of both the metrics indicate better performance for an algorithm. Regret. The cumulative regret is defined as # " L H # " L H XX X X Reg = E ∆Ah,ℓ ,h,ℓ = E m⋆h,ℓ − mh,ℓ (Ah,ℓ ) . ℓ=1 h=1
ℓ=1 h=1
2
(1)
Here, the sub-optimality gaps ∆a,h,ℓ ≜ m⋆h,ℓ −mh,ℓ (a), where mh,ℓ (a) denotes the mean of reward rh,ℓ (a) and m⋆h,ℓ ≜ max mh,ℓ (a). Also, ∆0 denotes the minimum sub-optimality gap from π0 . a
Constraint Violation. On the other hand, the safety is enforced by measuring the cumulated constraint violation with respect to a stationary baseline policy π0 ∈ P(A), " L H # o XX n Violation(π0 ) = E 1 mh,ℓ (Ah,ℓ ) < (1 − ϵ)Ea∼π0 [mh,ℓ (a)] . (2) ℓ=1 h=1
We observe that while the works on safe linear bandits need to assume explicitly existence of a safe arm satisfying the constraint (Pacchiano et al., 2021), we do not need such assumption. This is due to existence of a mixed baseline policy and the constraint defined by it. Thus, ∀h ∈ [H], ℓ ∈ [L], there exists at leasts one action a ∈ A satisfying ma,h,ℓ ≥ (1 − ϵ)Ea∼π0 [mh,ℓ (a)] for any ϵ < 1. Now, we elaborate the structural assumptions that we adhere to for the rest of the paper. Assumption 1 (Gaussian feedback signal with context-independent mean). The feedback signal is Gaussian with mean assumed context-independent. Formally, for any h ∈ [H] and ℓ ∈ [L], Yh,ℓ | (Ah,ℓ = a, Ch,ℓ = c) ∼ N (ma , Σa,c ), where ma ∈ RM is constant in c and Σa,c ∈ RM ×M is a positive semi-definite matrix that varies with both arm a and context c. In particular1 E[Yh,ℓ | Ah,ℓ = a, Ch,ℓ = c] = ma ,
Cov[Yh,ℓ | Ah,ℓ = a, Ch,ℓ = c] = Σa,c .
(3)
In particular, under Assumption 1, the mean rewards are ℓ-independent, i.e., ∀ℓ, mh,ℓ (a) = ma ph . Hence, the optimal mean m⋆ℓ and action a⋆h are also episode independent and user dependent. Assumption 1 is prevalent in many real-life settings. For example, in clinical trials mean response for a given dose remains stationary but variance in patients’ responses is heteroskedastic (Legedza & Ibrahim, 2001). In case of recommender systems having arms as content categories (sports, politics), average engagement (click, watch-time) or reward for a category is stable over weeks but per-user variance can vary (Saha et al., 2026; Feijer et al., 2025). Assumption 2 (Linear structure). The mean signal satisfies ma = Φ(a)θ, for some unknown parameter θ ∈ Rd with ∥θ∥2 ≤ S∗ , and a known feature matrix Φ(a) ∈ RM ×d . In particular, the normalized reward r̃h,ℓ (a) = rh,ℓ (a)/σa,h,ℓ satisfies r̃h,ℓ (a) | (Ch,ℓ = c) ∼ N (θ⊤ ϕa,h,ℓ , 1), where ϕa,h,ℓ =
1 Φ(a)⊤ ph ∈ Rd , σa,h,ℓ
2 σa,h,ℓ = p⊤ h Σa,Ch,ℓ ph > 0.
(4)
2 The variance σa,h,ℓ in Assumption 2, is heteroskedastic in three senses simultaneously: it varies across actions a, users h (through ph ), and episodes ℓ (through Ch,ℓ ∼ Cℓ ). We further intro2 2 duce three quantities: (a) maximum variance per step σ̄h,ℓ = max σa,h,ℓ , (b) condition number of a
2 maxa,h,ℓ σa,h,ℓ 2 mina,h,ℓ σa,h,ℓ
covariances over the episodes κ ≜ ≤ ∞, and (c) discounted cumulative variance PL L−ℓ PH 2 ΣLH ≜ ℓ=1 (γdecay ) h=1 σ̄h,ℓ for some discount factor γdecay ∈ (0, 1]. Discussion. Context-independence in Assumption 1 is naturally satisfied in applications where one base action, called the control, is available at each site location h, and the practitioner considers as feedback signal the difference of observed effects of action a and of the control. While we assume Gaussian noise, our theory and algorithm design extend to the general sub-Gaussian noise. 1.2
Outline and Contributions
We consider the problem of linear contextual bandits (LinCB) under non-stationary or drifting context distribution for H users encountered in each of L episodes, where each user comes with a customised preference feedback. We investigate the following questions: 1 This implies independence between sites, since the distribution of Y ′ h,ℓ does not depend on (Ah′ ,ℓ′ , Ch′ ,ℓ )(h′ ,ℓ′ )̸=(h,ℓ)
3
Algorithms OFUL (Abbasi-Yadkori et al., 2011) SpannerIGW (Zhu et al., 2022)
Instance Dependent Regret 2 Õ ∆dmin log3 (T ) √ 1 Ω ∆min T
OPLB (Pacchiano et al., 2021) SOLID (Tirinzoni et al., 2020) LinIMED (Bian & Tan, 2024) LinMED (Balagopalan & Jun, 2024) Dri-MED (This work)
d2 log2 (T ) ∆min 2 κd2 Õ ∆ ˜ log (T )
Õ
Minimax Regret √ Õ d T √ O dT log K √ d T Õ ∆ √min Õ dT √ Õ d T √ Õ d T √ Õ d κT
Context Drift
Safety Constraint
Table 1: Comparison of Regret Upper Bounds of Dri-MED against SOTA methods. Here, T = LH 2 ˜ = min{∆min , ∆0 }, and κ ≜ maxa,h,ℓ σ2a,h,ℓ . and ∆ mina,h,ℓ σa,h,ℓ
1. Can we design an algorithm to solve this problem of safe LinCB under context drifts and customized preferential feedback, and derive an instance-dependent upper bound on its regret? 2. If we have a performance constraint subject to a control-group, or equivalently a safety constraint with respect to a base-policy π0 , can we adapt to it, i.e., can we derive an upper bound on expected number of constraint violations? 3. Can we optimally design sampling probabilities at each step that will be simultaneously constraint-aware and preference divergent (sufficient exploration in all customised preference directions)? We aim to design a randomized strategy that efficiently computes the closed form probabilities of selecting each arm, since they prove to be beneficial in downstream tasks such as offline evaluation via inverse propensity score. In this work, we affirmatively answer the above questions and state them as main contributions below: 1. Context Drift and Customised Preference. In this work, we propose Dri-MED , the first MEDlike algorithm that handles non-stationarity of contexts every episode. We also prove an upper in 2 2 log (LH) . This non-trivial condition bound on the instance dependent regret of order Õ κd ˜ ∆ number captures sensitivity due to strength of drift in contexts across episodes. 2. Safety Constraint. In our setting, we impose a safety constraint with respect to a base-policy (control-group). As we do not know the true mean parameter θ beforehand, this constraint is also stochastic in nature. We show Dri-MED can adapt to this constraint and the instance de˜ We also prove with high probability, pendent regret upper bound involves a constraint-aware gap ∆. Dri-MED enjoys Õ(d) constraint violation. 3. Constraint-aware and Preference Divergent Design. We propose a novel constraint-aware Lagrangian dual penalised version of the G-optimal design (Balagopalan & Jun, 2024) to efficiently compute exact probabilities for each arm at every step. To best of our knowledge, no prior work handles customised preferences per user and propose a preference divergent allocation strategy. We also verify this claim in our experimental analysis, as Dri-MED assigns more allocation on the best arm consistently over baselines. 4. Empirical Performance Gain. We conduct numerical experiments across synthetic datasets with varying types of context drifts, namely abrupt, periodical, gradual or no drift. We observe Dri-MED outperforms the standard baseline algorithm significantly. Additionally, we propose an IMED (Baudry et al., 2023; Honda & Takemura, 2015) version of Dri-MED for empirical comparison, namely Dri-IMED (see Section E). The performance of Dri-IMED proves to be competitive consistently with Dri-MED across all types of drift.
2
Related Work
This problem lies at the crossroad of different settings of bandit literature. While the linear parametrisation of rewards allows us to leverage the rich literature of linear contextual bandits, the 4
Algorithm 1 LinMED (Balagopalan & Jun, 2024) 1: Initialise θ̂0 = 0, V0 = λI 2: for t = 1, 2, . . . do 3: Observe arm set At ; compute ât = arg maxa′ ∈At ⟨θ̂t−1 , a′ ⟩ 4: 5: 6: 7:
ˆ a,t ← ⟨θ̂t−1 , ât − a⟩ for all a ∈ At Compute gaps ∆ Compute weights ft (a) viaP for all a ∈ At p′t (a) ← g(qtopt (a))ft (a) / b∈At g(qtopt (b))ft (b) Bt ← {a ∈ At : ∥a∥2V −1 > 1} t−1
if |Bt | > 0 then pt (a) ← 12 p′t (a) + 21 1{a = Bt }, Bt ∈ Bt arbitrary else pt (a) ← p′t (a) end if −1 Pt 13: Sample At ∼ pt ; observe Yt ; update Vt ← Vt−1 + At A⊤ t , θ̂t ← Vt s=1 As Ys 14: end for 8: 9: 10: 11: 12:
context drifts over episodes are related to non-stationary and heteroskedastic linear bandits. Finally, the baseline policy requires us to bring techniques from bandits with safety constraints and extend them further. Here, we summarise the relevant literature. Since the seminal OFUL (homoskedastic) strategy is proposed by Abbasi-Yadkori et al. (2011), the literature in linear multi-armed bandits has considerably expanded over the last decade (Krause & Ong, 2011; Valko et al., 2014; Lattimore & Szepesvari, 2017; Chowdhury & Gopalan, 2017; Abeille, 2017; Durand et al., 2018), culminating in provably instance-dependent optimal and efficient strategies LinIMED (Bian & Tan, 2024) and LinMED (Balagopalan & Jun, 2024), respectively inspired from the IMED (Honda & Takemura, 2015; Baudry et al., 2023) and MED (aka Maillard sampling) (Honda & Takemura, 2011; Qin et al., 2023; 2025) for unstructured bandits. But the classical linear contextual bandits do not consider non-stationarity of contexts and also assume the variance across contexts and rounds to be static. To mitigate non-stationarity, Russac et al. (2019) and Faury et al. (2021) propose time-discounted regression estimates in (generalized) linear bandits under bounded variation budget. Heteroskedasticity in linear bandits has been studied in (He & Gu, 2025), establishing varianceaware lower performance bounds. Kirschner & Krause (2018); Kim et al. (2026) √ assume known local variance to provide worst-case regret bounds in O((d log(T ) + log(1/δ)) T ), while Brégère et al. (2019) extends to the unknown heteroskedastic variance. Batch bandits have received increasing attention over the past decade (Perchet et al., 2016; Gao et al., 2019; Jin et al., 2021), where the goal is to perform similarly to the pure sequential bandit problem with a minimal number of adaptively chosen batch sizes. Closer to this setting, Zhang et al. (2020) study when constant batch sizes are given as a constraint. This problem is also reminiscent of episodic reinforcement learning and combinatorial bandits, although with simpler structure. Regarding the performance constraint, safety with respect to constraint violation has been studied in Amani et al. (2019), Pacchiano et al. (2021). Finally, we mention the somewhat related notion of satisficing objective Feng et al. (2025), as well as the study of bandits under linear constraints from Das & Basu (2024), for the different pure exploration objective. A Primer on MED and LinMED. MED (Minimum Empirical Divergence) is a family of randomised bandit algorithms based on the probability matching philosophy (Honda & Takemura, 2011). MED-type algorithms pull each arm according to a probability dictating how likely it might be the optimal arm. Though originally proposed for bounded rewards and unstructured bandits, it has been extended to sub-Gaussian rewards, and is often referred to as Maillard sampling (Bian & Tan, 2024). Balagopalan & Jun (2024) extended the MED strategy to the linear bandits and proposed Lin5
MED. At each round t, it identifiesthe empirical best arm ât = arg maxa∈At ⟨θ̂t−1 , a⟩ and computes ˆ 2a,t ∆ ˆ a,t := ⟨θ̂t−1 , ât − a⟩ is , where ∆ exponential weights ft (a) = exp− βt−1 (δt−1 ) ∥ât − a∥2V −1 t−1
the estimated sub-optimality gap and βt (δt ) is a confidence scaling factor. These weights are used to compute an approximate G-optimal design qtopt over At , which is then blended with a mass on the empirical best arm and a uniform component to form the final sampling distribution pt . A saturation check Bt = {a ∈ At : ∥a∥2V −1 > 1} forces uniform exploration of under-sampled arms. The t−1
pseudocode is given in Algorithm 1. For further details, we refer to (Balagopalan & Jun, 2024).
3
Dri-MED: Drift Adaptive Minimum Empirical Divergence Algorithm
Now we are ready to propose our algorithm Dri-MED: drift adaptive minimum empirical divergence for safe linear contextual bandits under customised preference feedback. Dri-MED extends the MED-type algorithms in this setting. We choose MED-type algorithms for two reasons: (a) it yields tight problem-dependent regret bound for both independent arms (Baudry et al., 2023) and linear contextual settings (Balagopalan & Jun, 2024), (b) it allows an experimental design over the actions (Zhu et al., 2022; Balagopalan & Jun, 2024), i.e., it controls a non-zero probability of pulling each action for every user that leads to enough data collection for each of the actions and facilitates downstream evaluation of goodness of different actions against the baseline policy. The main challenges that Dri-MED resolve in addition to the LinMED algorithm (Balagopalan & Jun, 2024) are adapting to heteroskedastic noise across users with preferences, context drifts across episodes, and constraint violations against the baseline policies. We resolve them in three phases. Phase 1: At the beginning of ℓ-th episode, we observe the contexts {Ch,ℓ }H h=1 ∼ Cℓ and preferences ⊤ {ph }H for all the H users. We compute per-user feature vectors Φ(a) ph and then normalise h=1 with their corresponding σa,h,ℓ to tackle heteroskedasticity. i h P H 1 Phase 2: Since the true reward mean of the baseline policy π0 , i.e., µ0 ≜ Ea∼π0 H h=1 r̃h (a) is unknown in the beginning, we construct an optimistic estimate of it at the beginning of each episode ℓ using the observations available till that episode. The optimistic estimate is built in two steps. First, we use the available renormalized rewards and features {r̃h,s , ϕAh,s ,h,s }ℓ−1,H s=1,h=1 to create a ridge estimate of the underlying linear parameter θ. Specifically, θ̂ℓ−1 = arg min θ
ℓ−1 X
ℓ−1−s γdecay
s=1
H X
ℓ−1,H
θ⊤ ϕAh,s ,h,s − r̃h,s
2
h=1
+
X λ γdecay −1 ∥θ∥22 = (Vℓ−1 ) ϕAh,s ,h,s r̃h,s , 2 s,h=1
(5) γdecay where Vℓ−1
≜
Pℓ−1
ℓ−1−s PH ℓ−1 ⊤ s=1 γdecay h=1 ϕAh,s ,h,s ϕAh,s ,h,s + λγdecay I is an episodically discounted
design matrix (aka Gram matrix) to tackle episodic context drifts. We use θ̂ℓ−1 to construct an P PH empirical estimate µ̂0,ℓ ≜ ⟨θ̂ℓ−1 , a π0 (a) h=1 ϕa,h,ℓ ⟩ of the reward of the baseline policy π0 at the beginning of episode ℓ. The proposed estimate extends the homoskedastic weighted linear regression (Russac et al., 2019; Kim et al., 2026) for non-stationary linear bandits to this episodic setting with heteroskedastic noise. γ
decay Second, we compute the confidence width around the empirical estimate µ̂0,ℓ using Vℓ−1 . Then, we inflate the empirical mean estimate µ̂0 using this confidence width and saturation information of arms to get an optimistic estimate X p µ̂+ βℓ (δℓ ) π0 (a)ϕ̄a,ℓ , (6) γdecay 0,ℓ = µ̂0,ℓ +
a
r where the confidence width βℓ (δℓ ) ≜
(Vℓ−1 )−1
decay √ detVℓ−1 log detV + 2 log δ1ℓ + λS∗ 0 γ
!2 . Being optimistic in
terms of base policy mean is being pessimistic about constraint satisficing. This design resonates with the existing safe bandit literature (Pacchiano et al., 2021; Das & Basu, 2024). 6
Algorithm 2 Dri-MED: Drift adaptive Minimum Empirical Divergence Require: Baseline parameters π0 , ϵ, regularization parameter λ, S∗ Require: Discount over drifts γdecay ∈ [0, 1] and confidence levels {δℓ } 1 Require: Initial Lagrangian multiplier ν0 > 0, Lagrangian step size schedule {ηh,ℓ = (ℓh)− 2 } 1: Initialize θ̂0,0 = 0, V0 = λId , C̄0 = 0, and N0 (a) = 0 ∀a 2: for episode ℓ = 1 to L do γ γdecay L−ℓ 1 3: Initialize an episode with V0,ℓdecay = γdecay θ̂ℓ−1 , and νh,ℓ = νℓ−1 Vℓ−1 , θ̂0,ℓ = γdecay Phase 1: Context observation & drift detection H 4: Observe contexts {Ch,ℓ }H h=1 ∼ Cℓ and preferences {ph }h=1 1 5: For all a ∈ A, compute per-user features ϕa,h,ℓ = σa,h,ℓ Φ(a)⊤ ph and mean feature ϕ̄a,ℓ = PH 1 h=1 ϕa,h,ℓ H Phase 2: Episode-specific baseline & constraint r γdecay p √ detVℓ−1 + 2 log δ1ℓ + λS∗ 6: Confidence width on baseline βℓ (δℓ ) = log detV 0 7: 8: 9: 10: 11:
Compute the optimistic baseline µ̂+ 0,ℓ with Equation (6) Set the constraint threshold τℓ = (1 − ϵ)µ̂+ 0,ℓ Phase 3: Within-episode decisions for user h = 1 to H do Play an action Ah,ℓ ← Apply Algorithm 3 Observe Yh,ℓ , ph , and r̃h,ℓ = σA 1 ,h,ℓ p⊤ h Yh,ℓ h,ℓ
12: 13:
Update Lagrangian multiplier, Gram n matrix, and parameter o estimate Constraint violation indicator: ξh,ℓ = 1 ⟨θ̂h,ℓ , ϕAh,ℓ ,h,ℓ ⟩ < τℓ n o ϵ Update the Lagrangian multiplier νh,ℓ ← max 0, νh,ℓ + ηh,ℓ ξh,ℓ − 1−ϵ γ
γ
decay + ϕAh,ℓ ,h,ℓ ϕ⊤ Update Nh+1,ℓ (Ah,ℓ ) = Nh,ℓ (Ah,ℓ ) + 1, Vh,ℓdecay = Vh−1,ℓ Ah,ℓ ,h,ℓ γdecay −1 Ph 15: Compute θ̂h,ℓ = (Vh,ℓ ) ϕ r A ,s,ℓ A s,ℓ s,ℓ s=1 16: end for γdecay γdecay 17: Store episodic statistics Vℓ ← VH,ℓ , θ̂ℓ ← θ̂H,ℓ , C̄ℓ , µ0,ℓ , νh,ℓ 18: end for
14:
Finally, this yields the constraint threshold τℓ = (1 − ϵ)µ̂+ 0,ℓ for the present episode. Phase 3: The baseline adaptive MED step. In beginning of this phase, we play an arm according to Algorithm 3. The sampling strategy uses Minimum Empirical Divergence at its core. The novelty lies in the adaption for our episodic setting with non-stationary contexts and baseline. We first ˆ A ,h,ℓ . We use these estimated gaps to compute the empirical best arm and estimate the gaps ∆ h,ℓ calculate exponential weights over all arms as ˆ 2 / βh,ℓ (αh,ℓ )∥ϕâ ,h,ℓ − ϕa,h,ℓ ∥2 γ −1 (7) fh (a) = exp −∆ a,h,ℓ h,ℓ (Vh,ℓ ) f˜h (a) = fh (a) · exp −νh,ℓ · max{0, τℓ − LCB(a, h, ℓ)} (8) To make the weights constraint-aware, we introduce a Lagrangian dual based penalty with Lagrangian multiplier νh,ℓ . Specifically, we show in Lemma 3 this dual parameter grows at a rate √ O( ℓh). Next, we rescale the arms using normalized features. We introduce a novel baseline-aware ApproxDesign() algorithm (refer Section G) or Copt -optimal design that ensures saturation of the true best arm efficiently, i.e.,
a∗h,ℓ
2 (V (ph )γdecay )−1
≤ Copt O (d log(d)) .
Though the baseline-awareness is adapted in the optimal design via qh (a). While we compute the final design probability in Line 9, we P show in Lemma 10, the denominator is lower bounded by a dual-penalised term. Specifically b qh (b)f˜h (b) > αopt e−νh,ℓ . This prevents unsafe arms from saturating and efficiently discards them. Finally, upon checking the saturation status of each arm and construct the augmented arm set as Bh,ℓ = a : ∥ϕa,h,ℓ ∥2 γdecay −1 > 1 . Any arm in this set (Vh,ℓ
7
)
Algorithm 3 Baseline Adaptive Minimum Empirical Divergence (MED) Step |A|
γ
1/2
∥ϕa,h,ℓ ∥(V γdecay )−1
Require: Episode ℓ ∈ [L], user id h ∈ [H], user’s context {ϕa,h,ℓ }a=1 , θ̂h,ℓ , Vh,ℓdecay , λ. Require: Constraint threshold τℓ , Lagrangian multiplier r νh,ℓ , γαemp , αopt . decay √ detVh,ℓ 1/2 1 + 2 log αh,ℓ 1: Compute confidence radius: βh,ℓ (αh,ℓ ) = log detV + λS∗ 0 2: For each arm a ∈ A: LCB(a, h, ℓ) = ⟨θ̂h,ℓ , ϕa,h,ℓ ⟩ − βh,ℓ (αh,ℓ )
h,ℓ
3: Empirical best action: âh,ℓ = arg maxa∈A ⟨θ̂h,ℓ , ϕa,h,ℓ ⟩
ˆ a,h,ℓ = ⟨θ̂h,ℓ , ϕâ ,h,ℓ − ϕa,h,ℓ ⟩ 4: Empirical gaps: ∆ h,ℓ 5: Compute Constraint-aware pulling probabilities: For every a ∈ A, compute f˜h (a) with
Equation (8). q
f˜h (a) · ϕa,h,ℓ a ∈ A opt 7: qh = ApproxDesign A(h) ← Algorithm 6 opt 1 8: qh (a) = αopt qh (a) + αemp 1[a = âh,ℓ ] + (1 − αopt − αemp ) |A| X 9: Compute final design probabilities: p′ (a) = qh (a) f˜h (a)/ qh (b) f˜h (b)
6: Rescale arms:
A(h) =
h
10: Check saturation event for each arms: Bh,ℓ =
(
1 1 ′ 2 ph (a) + 2 1[a ∈ Bh,ℓ ] p′h (a)
11: ph (a) =
b a : ∥ϕa,h,ℓ ∥2 γdecay −1 > 1 (Vh,ℓ
)
if Bh,ℓ ̸= ∅ otherwise
12: Sample Ah,ℓ ∼ ph
has not been explored enough to be sure of it’s mean parameter, thus we pull this arm with a toss of a fair coin. Otherwise we play by the design probabilities. At the end, we observe the feedback signal, normalize the reward we compute. Then we check whether the constraint has been violated by the playing arm and update the Lagrangian multiplier νh,ℓ accordingly.
4
Regret Analysis of Dri-MED
In this section, we provide upper bounds on both instance dependent regret, and expected constraint violation for the strategy Dri-MED, along with very high-level proof intuitions. Assumption 3 (Boundedness). 1. max ∥ϕa,h,ℓ ∥2 ≤ 1, 2. max ∥ph ∥2 ≤ 1, and 3. max ∆a,h,ℓ ≤ B. a,h,ℓ
h
a,h,ℓ
Standard Regret. We first decompose the original regret in Equation 1 into two parts based on the event Vh,ℓ (Ah,ℓ ) = {mh,ℓ (Ah,ℓ ) < (1 − ϵ)Ea∼π0 [mh,ℓ (a)]} as: " L H # " L H # o n XX XX Reg = E ∆Ah,ℓ ,h,ℓ 1 Vh,ℓ (Ah,ℓ ) + E (9) ∆Ah,ℓ ,h,ℓ 1 {Vh,ℓ (Ah,ℓ )} ℓ=1 h=1
|
ℓ=1 h=1
{z
}
≜Regsafe
|
{z
≜Regviol
}
The novel decomposition in Equation (9) allows to analyze the regret of Dri-MED in two stages: 1. bound on sum of suboptimality over time under the event that we do not pull any truly unsafe arm, 2. under the event we pull arms that are unsafe. Regsafe . We formalize the regret upper bound guaranty under safety constraint below in Theorem 1. Theorem 1 (Instance Dependent Regret Upper Bound under Constraint Satisfaction). Under Assumption 1,2, and 3, Algorithm 2 and 3 jointly satisfies – ! d2 log2 (LH) + log (ΣLH ) safe Reg = Õ κ ∆min
8
Proof Concept. The main challenge while analysing regret in our setting lies in elegantly incorporate the constraint violation event, and also to capture the effect of the episodic drift in context. To prove upper bound on the regret under constraint satisficing, we adapt the proof structure of Balagopalan & Jun (2024) to our episodic interaction setting with known, but shifting reward noise variance. The adaptation comes in two folds: 1. while analysing Regsafe the first challenge is handled by controlling the true gap ∆Ah,ℓ ,h,ℓ using peeling technique around (∆π0 + ϵµπ0 ), instead of the maximum gap B, 2. we realise the effect drifting context comes implicitly through the non-stationary noise variance involved in the feedback signal YAh,ℓ ,h,ℓ . Thus, the log-dependency on sum of variances in hTheorem 1 comes naturally i while we try to bound the saturation event of feature of Ah,ℓ . i.e., E ∥ϕAh,ℓ ∥(V γdecay )−1 > 1 . We prove this by using (Abbasi-Yadkori et al., 2011, Lemma 4) . For h,ℓ
more details, refer to Section B in the supplementary materials. Regviol . This part of the whole regret is about characterising the suboptimality cost of the arms that are unsafe in true sense. We formally state the upper bound for this part below: Theorem 2 (Instance Dependent Regret Upper Bound under Constraint Violation). Under Assumption 1,2, and 3, Algorithm 2 and 3 jointly satisfies – B − ∆π0 2 viol 2 2 d log (LH) + log (ΣLH ) Reg = Õ σmax (∆π0 + ϵµ0 )2 Proof Concept. Existing literature (Bian & Tan, 2024; Balagopalan & Jun, 2024) use peeling technique to leverage a lower bound on true gap that in turn, helps upper bounding the pulling probability of arm Ah,ℓ . From the definition of the event Vh,ℓ (αh,ℓ) , we immediately show ∆Ah,ℓ ,h,ℓ > ∆π0 + ϵµπ0 . Thus, 1. we do not need additional peeling over the value of ∆Ah,ℓ ,h,ℓ , 2. we again leverage this natural lower bound while handling the conditioning event on concentration of θ̂h,ℓ around true parameter θ. For the detailed proof, refer to Section B. Final Regret. We combine Regsafe and Regviol to state the final regret upper bound of Dri-MED: 1 Theorem 3 (Instance Dependent Regret Upper Bound of Dri-MED). Let us denote ∆ ˜ ≜ n o B−∆ π 1 max ∆min , (∆π +ϵµ00 )2 . Under Assumption 1,2, and 3, Dri-MED exhibits 0
1 Reg = Õ κ d2 log2 (LH) + log (ΣLH ) ˜ ∆
.
1 Discussion. 1. While (Balagopalan & Jun, 2024) achieves a regret of Õ κ ∆min d2 log2 (LH) , our bound also depends on the constraint gap ∆0 due to the baseline policy and the condition number of the variances over the episodes due to context drifts. 2. While the safe contextual bandit literature provides a minimax bound on the regret under the assumption of a safe action Amani et al. (2019); Pacchiano et al. (2021), we remove the assumption due to access to a baseline policy while achieving a problem-dependent regret upper bound as well as a minimax regret bound of same order. 3. On the other hand, if we consider the implication of our results for heteroskedastic linear bandits, we observe that we derive a problem-dependent regret bound under heteroskedasticity while the present literature focuses on minimax regret (Kirschner & Krause, 2018; Kim et al., 2026). Constraint Violation. It is imperative for a safe bandit algorithm (Amani et al., 2019; Pacchiano et al., 2021) to have an upper bound on expected number of true constraint violations (defined in Equation (2) for the whole interaction. For Dri-MED, we state this guaranty formally below: Theorem 4 (Expected Constraint Violation of Dri-MED). Under Assumption 1,2, and 3, Dri-MED suffers expected number of constraint violations Violation(π0 ) = Õ (d).
9
Proof Concept. In Lemma 5, we prove under constraint violation, the true gap is lower bounded by the gap subject to base-policy π0 . That means ∆Ah,ℓ ,h,ℓ ≥ ∆π0 . While analysing standard regret, we decompose Regviol into two parts, " L H # " L H # XX XX viol Reg = ∆π0 E 1 {Vh,ℓ (Ah,ℓ )} + E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} ℓ=1 h=1
|
ℓ=1 h=1
{z
Violation(π0 )
}
one of which is the expected constraint violation. We prove upper bound on this by simply using Corollary 1 adapted (Jun & Kim, 2024, Lemma C.2). We discuss it at length in Section B. PL PH 2 Implication. (1) The variance dependency is captured by κ and ΣLH ≜ ℓ=1 γdecay L−ℓ h=1 σ̄h,ℓ P 2 appearing in the logarithmic term. This logarithmic part is reminiscent of the term t ωt appearing in (Russac et al., 2019, Thm.1), further adapted here to the heteroskedastic setup. (2) Our bound is instance-dependent, scaling as polylog of T , contrasting with minimax regret pP 2 bounds. From He & Gu (2025); Kim et al. (2026), the minimax lower bound is of order d t σt 2 where σt is the variance of reward rt . Compare to the simplified setting of Balagopalan & Jun ˜ mainly due to the safety constraint, and (2024), we replace the term 1/∆min with the larger κ/∆, the handling of heteroskedastic variance. We conjecture the dependency on κ might be further reduced. ˜ appears as the constraint induced by π0 does not vanish even (3) The intricate threshold within ∆ as ϵ → 1. Indeed, even in this case, the mean rewards must stay positive. We pay the largest regret when ∆π0 = 0, forcing a maximal factor B/(ϵ2 µ20 ), while as ∆π0 approaches the largest gap B, we recover the leading factor 1/∆min from the unconstrained setup (Balagopalan & Jun, 2024).
5
Numerical Experiments
We evaluate Dri-MED and Dri-IMED, a deterministic variant of our algorithm that we do not theoretically analyse (Appendix E), on a synthetic episodic contextual linear bandit with preference feedback and context drift, focusing on gradual and periodic drift regimes. Full environment details, additional drift regimes, ablation studies, and hyperparameter settings are provided in Appendix F. Baselines. We compare against four stationary linear bandit algorithms that ignore both drift and preference structure: OFUL (Abbasi-Yadkori et al., 2011), LinMED (Balagopalan & Jun, 2024), LinIMED (Bian & Tan, 2024), and LinTS (Agrawal & Goyal, 2013). To our knowledge, no prior algorithm addresses this combined setting. Thus, the baselines serve as the natural reference points2 . Environment. We consider a synthetic environment with H = 10 users, K = 5 arms, and L = 1000 episodes; full parameter details are given in Appendix F (Algorithm 5). We study two drift regimes, both parametrised by magnitude κ = 100: gradual drift, where the context scale grows linearly as f (ℓ) = κ · ℓ/L, producing a smooth and monotone increase in noise; and periodic drift, where f (ℓ) = κ· 12 (1+sin(2πℓ/(L/50))), producing recurring fluctuations that repeatedly challenge the constraint mechanism. All results are averaged over 128 independent seeds. Regret Evolution and Constraint Violation. Figure 1 reports cumulative regret for both drift regimes. Dri-MED and Dri-IMED achieve substantially lower regret than all baselines, with the gap widening as episodes progress. Among the baselines, OFUL performs best yet still incurs regret an order of magnitude larger than that of our methods. LinMED and LinTS perform the worst, confirming that ignoring heteroskedasticity and preference structure is costly. Performance is stable across both drift types, validating that the drift-adaptive discounted regression successfully absorbs the non-stationarity, whether it is smooth or oscillatory. Both Dri-MED and Dri-IMED rapidly drive the true constraint violation rate to zero after an initial exploration phase, while all stationary baselines exhibit persistent violations throughout. 2 Source code can be found on https://github.com/riiswa/context_drift_lin_bandits/
10
Gradual Drift 1.0
1000 500 0
200
400
600
800
Episode
1000
OFUL
Violation rate
Cumulative Regret
500 200
400
600
Episode
0.2 0
200
800 OFUL
1000
400
600
Episode
LinMED
1.0
1000
0
0.4
LinTS
1500
0
0.6
Periodic Drift
Cumulative Regret
2000
0.8
0.0
800
LinIMED
0.4 0.2 0
200
200
400
600
Episode
LinMED
800
LinIMED
1000 Dri-MED
600
Episode
800
1000
800
1000
True Violation Rate
1.0
0.2
400
Dri-IMED
K = 5, H = 10, L = 1000, d = 4
Estimated Violation Rate
0.4
LinTS
0.6
Dri-MED
0.6
0
0.8
0.0
1000
0.8
0.0
True Violation Rate
1.0
Violation rate
0
K = 5, H = 10, L = 1000, d = 4
Estimated Violation Rate
Violation rate
1500
Violation rate
Cumulative Regret
Cumulative Regret
0.8 0.6 0.4 0.2 0.0
0
200
400
600
Episode
Dri-IMED
Figure 1: Cumulative regret (left), estimated violation rate (center), and true violation rate (right) for gradual and periodic drift. Shaded bands show the 5–95% quantile range over 128 seeds. Results for no-drift and abrupt drift are provided in Appendix F. Design Probabilities. The arm allocation analysis (Appendix F, Figure 4) reveals a clear behavioural distinction between algorithms. Dri-MED concentrates almost all pull mass on the oracleoptimal arm a⋆h for every user. In contrast, LinMED spreads significant mass across suboptimal arms, unable to distinguish arm quality under the heteroskedastic preference structure it ignores. For more experimental results and ablation studies, refer to Section F in supplementary materials.
6
Discussions, Limitations, and Future Works
We study a class of sequential experimental problems with a group of users having heterogeneous preferences and temporally evolving context distributions as a linear contextual bandit with heteroskedastic and non-stationary noise but stationary mean. In this context, we propose Dri-MED that achieves (a) validity, i.e. a distribution of scores over its actions, (b) reliability, i.e. improved performance than a baseline action/policy applied over a control group, and (c) efficiency, i.e. low regret. We prove that Dri-MED achieves logarithmic regret while exhibiting better numerical performance than the existing baselines. The main limitation of this work is the stationary reward mean assumption. Though this assumption with heteroskedastic noise holds true for multiple applications, it would interesting to generalise our analysis for non-stationary means. In addition, the present MED strategies work only for subGaussian rewards, whereas in real-life experiments, the noise distribution can exhibit heavy tails. Designing heavy-tail robust MED algorithms in this context, and in general remain open questions.
Broader Impact Statement This work mainly aimed for theoretical advancements in the safe, heteroskedastic contextual bandit literature. The authors does not see any potential negative impact that should be mentioned here. 11
Acknowledgments The authors would like to acknowledge PEPR project FOUNDRY (ANR23-PEIA-0003) for their support. DB and UD would like to acknowledge ANR JCJC project REPUBLIC (ANR-22-CE230003-01). We would also like to acknowledge the anonymous reviewers for their constructive feedback. Authors are members of the Inria team-project Scool.
References Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. Marc Abeille. Exploration-exploitation with Thompson sampling in linear systems. PhD thesis, Université de Lille 1, 2017. Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pp. 176–184. PMLR, 2017. Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127–135. PMLR, 2013. Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019. Kapilan Balagopalan and Kwang-Sung Jun. Minimum empirical divergence for sub-gaussian linear bandits. arXiv preprint arXiv:2411.00229, 2024. Abhijit V Banerjee, Sylvain Chassang, Sergio Montero, and Erik Snowberg. A theory of experimenters: Robustness, randomization, and balance. American Economic Review, 110(4):1206– 1230, 2020. Dorian Baudry, Fabien Pesquerel, Rémy Degenne, and Odalric-Ambrym Maillard. Fast asymptotically optimal algorithms for non-parametric stochastic bandits. Advances in Neural Information Processing Systems, 36:11469–11514, 2023. Jie Bian and ntnt YF Tan. Indexed minimum empirical divergence-based algorithms for linear bandits. arXiv preprint arXiv:2405.15200, 2024. Margaux Brégère, Pierre Gaillard, Yannig Goude, and Gilles Stoltz. Target tracking for contextual bandits: Application to demand side management. In International Conference on Machine Learning, pp. 754–763. PMLR, 2019. Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pp. 844–853. PMLR, 2017. Udvas Das and Debabrota Basu. Learning to explore with lagrangians for bandits under unknown constraints. In Seventeenth European Workshop on Reinforcement Learning, 2024. Peter J. Diggle and Amanda G. Chetwynd. 5 experimental design: agricultural field experiments and clinical trials. In Statistics and Scientific Method: An Introduction for Students and Researchers. Oxford University Press, 08 2011. ISBN 9780199543182. DOI: 10.1093/acprof: oso/9780199543182.003.0005. Audrey Durand, Odalric-Ambrym Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. Journal of Machine Learning Research, 19 (17):1–34, 2018. Louis Faury, Yoan Russac, Marc Abeille, and Clément Calauzènes. Regret bounds for generalized linear bandits under parameter drift. arXiv preprint arXiv:2103.05750, 2021. 12
Diego Feijer, Himan Abdollahpouri, Sanket Gupta, Alexander Clare, Yuxiao Wen, Todd Wasson, Maria Dimakopoulou, Zahra Nazari, Kyle Kretschman, and Mounia Lalmas. Calibrated recommendations with contextual bandits. arXiv preprint arXiv:2509.05460, 2025. Qing Feng, Tianyi Ma, and Ruihao Zhu. Satisficing regret minimization in bandits. In The Thirteenth International Conference on Learning Representations, 2025. Ronald Fisher. The arrangement of field experiments. Journal of the Ministry of Agriculture, 33: 503–515, 1926. Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019. Kwanchai A Gomez and Arturo A Gomez. Statistical procedures for agricultural research. John wiley & sons, 1984. Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157–325, 2016. Jiafan He and Quanquan Gu. Variance-dependent regret lower bounds for contextual bandits. arXiv preprint arXiv:2503.12020, 2025. Junya Honda and Akimichi Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Machine Learning, 85(3):361–391, 2011. Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semibounded rewards. The Journal of Machine Learning Research, 16(1):3721–3756, 2015. Reza Hoshmand. Design of experiments for agriculture and the natural sciences. Chapman and Hall/CRC, 2018. Tianyuan Jin, Jing Tang, Pan Xu, Keke Huang, Xiaokui Xiao, and Quanquan Gu. Almost optimal anytime algorithm for batched multi-armed bandits. In International Conference on Machine Learning, pp. 5065–5073. PMLR, 2021. Kwang-Sung Jun and Jungtaek Kim. Noise-adaptive confidence sets for linear bandits and application to bayesian optimization. arXiv preprint arXiv:2402.07341, 2024. Sanghwa Kim, Junghyun Lee, and Se-Young Yun. A jointly efficient and optimal algorithm for heteroskedastic generalized linear bandits with adversarial corruptions. arXiv preprint arXiv:2602.10971, 2026. Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pp. 358–384. PMLR, 2018. Ron Kohavi and Roger Longbotham. Online controlled experiments and a/b tests. Encyclopedia of machine learning and data mining, pp. 1–11, 2015. Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011. Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pp. 728–737. PMLR, 2017. Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. DOI: 10.1017/9781108571401. Anna TR Legedza and Joseph G Ibrahim. Heterogeneity in phase i clinical trials: prior elicitation and computation using the continual reassessment method. Statistics in Medicine, 20(6):867–882, 2001. 13
George Mavrotas. Effective implementation of the ε-constraint method in multi-objective mathematical programming problems. Applied mathematics and computation, 213(2):455–465, 2009. Alasdair PS Munro, Leila Janani, Victoria Cornelius, Parvinder K Aley, Gavin Babbage, David Baxter, Marcin Bula, Katrina Cathie, Krishna Chatterjee, Kate Dodd, et al. Safety and immunogenicity of seven covid-19 vaccines as a third dose (booster) following two doses of chadox1 ncov-19 or bnt162b2 in the uk (cov-boost): a blinded, multicentre, randomised, controlled, phase 2 trial. The Lancet, 398(10318):2258–2276, 2021. Jerzy Neyman. On the application of probability theory to agricultural experiments. essay on. Statistical Science, 5(4,465-480), 1923. reprinted in 1990. Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International conference on artificial intelligence and statistics, pp. 2827–2835. PMLR, 2021. Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, pp. 660–681, 2016. Hao Qin, Kwang-Sung Jun, and Chicheng Zhang. Kullback-leibler maillard sampling for multiarmed bandits with bounded rewards. Advances in Neural Information Processing Systems, 36: 60514–60526, 2023. Hao Qin, Kwang-Sung Jun, and Chicheng Zhang. Achieving adaptivity and optimality for multi-armed bandits using exponential-kullback leibler maillard sampling. arXiv preprint arXiv:2502.14379, 2025. Paul Raccuglia, Katherine C Elbert, Philip DF Adler, Casey Falk, Malia B Wenny, Aurelio Mollo, Matthias Zeller, Sorelle A Friedler, Joshua Schrier, and Alexander J Norquist. Machine-learningassisted materials discovery using failed experiments. Nature, 533(7601):73–76, 2016. R Rangaswamy. A text book of agricultural statistics. New age international, 1995. Clémence Réda, Emilie Kaufmann, and Andrée Delahaye-Duriez. Machine learning applications in drug development. Computational and structural biotechnology journal, 18:241–252, 2020. Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems, 32, 2019. Aadirupa Saha, Amith Bhat, and Haipeng Luo. One good source is all you need: Near-optimal regret for bandits under heterogeneous noise. arXiv preprint arXiv:2602.14474, 2026. Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction. MIT press Cambridge, 1998. Kari Christine Tanner, Gordon B Jones, and Elizabeth Claire Verhoeven. Experimenting on the Farm: Introduction to Experimental Design. Oregon State University Extension Service, 2023. Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. Advances in Neural Information Processing Systems, 33:1417–1427, 2020. Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. In International conference on machine learning, pp. 46–54. PMLR, 2014. Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in neural information processing systems, 33:9818–9829, 2020. Yinglun Zhu, Dylan J Foster, John Langford, and Paul Mineiro. Contextual bandits with large action spaces: Made practical. In International Conference on Machine Learning, pp. 27428–27453. PMLR, 2022. 14
Supplementary Materials The following content was not necessarily subject to peer review.
A
Notations Notation ℓ h θ θ̂h,ℓ K cℓ Φ(a) Yh,ℓ ph rh,ℓ ϕa,h,ℓ Σa,h,ℓ σa,h,ℓ 2 σh,ℓ 2 σmax 2 σmin ∆a,h,l ˆ a,h,l ∆ π0 ∆π 0 µ0,ℓ µ+ 0,ℓ
Description Episode index ∈ [1, L] User index ∈ [1, H] True reward parameter with ∥θ∥2 ≤ S∗ Estimate of the true parameter θ for h-th user in ℓ-th episode Number of actions Context distribution at episode ℓ M × d feature matrix for arm a ∈ A M -dimensional feedback signal E[Yh,ℓ | Ah,ℓ = a, Ch,ℓ = c] = Φ(a)θ d-dimensional preference vector for h-th user ⊤ Scalar reward for h-th user in ℓ-th episode = Yh,ℓ ph 1 ⊤ d-dimensional context for arm a = σa,h,ℓ Φ(a) ph = Cov[Yh,ℓ | Ah,ℓ = a, Ch,ℓ = c] = Var(ηh,ℓ | Ah,ℓ = a) (Variance of noise in the feedback, if arm a is pulled) 2 = mina∈A σa,h,ℓ 2 = maxa,h,ℓ σa,h,ℓ 2 = mina,h,ℓ σa,h,ℓ = θ⊤ (ϕa∗ℓ ,h,ℓ − ϕa,h,ℓ ) ≥ 0 = θ̂t⊤ (ϕa∗ℓ ,h,ℓ − ϕa,h,ℓ ) Baseline policy = minℓ∈[L] θ⊤ (ϕa∗ℓ ,h,ℓ − ϕπ0 ) PH P 1 Estimated reward of the baseline policy 0 (a)⟨θ̂h,ℓ , ϕa,h,ℓ ⟩ p H h=11 Pa πP Optimistic reward of baseline µ0,ℓ + βℓ (δℓ ) H h a π0 (a)ϕa,h,ℓ (V γ )−1
τℓ τ
Constraint threshold = (1 − ϵ)µ+ 0,ℓ , for ϵ ≥ 0 True constraint threshold = (1 − ϵ)µ n 0 , where µ0 is the true o mean reward for π0
ξh,ℓ Vh,ℓ (Ah,ℓ) µ0
ℓ
Constraint violation indicator = 1 ⟨θ̂h,ℓ , ϕAh,ℓ ,h ⟩ < τℓ True constraint violating event {(h, ℓ) ∈ [h, ℓ] : ⟨θ, ϕAh,ℓ ,h ⟩ < τ } True mean of base-policy = θ⊤ ϕπ0
For the supplementary materials, whenever we write ∆a,h,ℓ , it denotes the feature normalized true suboptimal gap.
15
B
Proof of Regret Upper Bound of Dri-MED (Algorithm 2)
B.1
Good Event: Concentration and Confidence Width
We start by defining the following good events: G1 ≜
∀h ≥ 1, ℓ ≥ 1 : ∥θ − θ̂h,ℓ ∥2V γdecay ≤ βh,ℓ (αh,ℓ )
(10)
h,ℓ
Lemma 1 (Heteroscedastic weighted (h, ℓ)-th confidence set). Following the information acquisiγ γdecay tion rule with action Ah,ℓ = a and it’s rescaled feature vector ϕa,h,ℓ , i.e., Vh,ℓdecay = Vh−1,ℓ + ⊤ ϕa,h,ℓ ϕa,h,ℓ , we define s γ √ detVh,ℓdecay 1 1/2 βh,ℓ (αh,ℓ ) ≜ 2 log + 2 log + λ S∗ , detV0 αh,ℓ where αh,ℓ ∈ (0, 1) is to characterised later on. Then P(G1 ) ≥ 1 −
PL
ℓ=1
PH
h=1 αh,ℓ .
Proof. We apply the self-normalized martingale inequality of (Abbasi-Yadkori et al., 2011, Theorem γ 2) to the Gram matrix Vh,ℓdecay . At round (h, ℓ), the noise involved in the reward signal ηh,ℓ is PL PH 2 σa,h,ℓ -sub-Gaussian and Fh,ℓ -measurable. The weighted process ℓ=1 γ ℓ h=1 ηh,ℓ ϕAh,ℓ ,h,ℓ is a martingale, and the theorem PLyields PHthe stated bound round-by-round. Thus, a union bound over all (h, ℓ) gives P(G1 ) ≥ 1 − ℓ=1 h=1 αh,ℓ . B.2
Regret Decomposition
Definition 1 (Constraint-violating rounds). Let Vh,ℓ (Ah,ℓ ) ≜ ⟨θ, ϕAh,ℓ ,h,ℓ ⟩ < τ denotes whether (h, ℓ) is a true constraint-violating index. We should note, as we are normalising each feature by the noise variance, the gaps are also inherˆ A ,h,ℓ = ently scaled by the noise variance. Thus, we define ∆Ah,ℓ ,h,ℓ = σAh,ℓ ,h,ℓ ∆Ah,ℓ ,h,ℓ , ∆ h,ℓ ˆ σAh,ℓ ,h,ℓ ∆ , and finally ∆ σ ≤ ∆ ≤ ∆ σ . We decompose the total expected π0 Ah,ℓ ,h,ℓ π0 min π0 max regret as– " L H # XX Reg = E ∆Ah,ℓ ,h,ℓ ℓ=1 h=1
# " L H " L H # o n XX XX ∆Ah,ℓ ,h,ℓ 1 {Vh,ℓ (Ah,ℓ )} = σmax E ∆Ah,ℓ ,h,ℓ 1 Vh,ℓ (Ah,ℓ ) + σmax E ℓ=1 h=1
ℓ=1 h=1
≜ Regsafe + Regviol B.3
Part I: Regret Upper Bound under Constraint Violation
Theorem 2. Algorithm 2 and 3 jointly satisfies – Reg
viol
= Õ
2 σmax
B − ∆π0 d2 (∆π0 + ϵµ0 )2
2
log (LH) + log
L X ℓ=1
L−ℓ
(γdecay )
H X
!!! 2 σh,ℓ
h=1
In this section, we provide a complete proof of the regret upper bound under constraint violation, i.e, upper bound on Regviol . The proof structure involves two steps: 1. Then for the upper bound, we first define the conditioning event that will be used to decompose the regret expression further. 2. We bound each part of the decomposition to get a final accumulated upper bound. 16
B.3.1
Defining the Conditioning Events
Definition 2. For any arm a ∈ A, we define the following conditioning events: ∆Ah,ℓ ,h,ℓ ˆ Concentration of gaps: Uh,ℓ (a) ≜ ∆ for c ≥ 0 ≥ Ah,ℓ ,h,ℓ 1+c Saturation of arm features: Eh,ℓ ≜ {|Bh,ℓ | > 0} , where Bh,ℓ = a : ∥ϕa,h,ℓ ∥2(V γdecay )−1 > 1 h,ℓ o n ⊤ ⊤ for ε1 ≥ 0 Concentration of parameter estimate: Jh,ℓ (a) ≜ θ ϕa∗h,ℓ ,h,ℓ − θ̂h,ℓ ϕa∗h,ℓ ,h,ℓ ≤ ε1 n o Partial Saturation of arm features: Fh,ℓ (a) ≜ ∥ϕa,h,ℓ ∥(V γdecay )−1 > ε2 for ε ≥ 0 h,ℓ
(11) The event Uh,ℓ (a) signifies how accurately we are being able to estimate the sub-optimality gaps for arm a, Eh,ℓ measures the saturation level for every arm at index (h, ℓ), Jh,ℓ (a) assigns a precision in estimating the true parameter θ, and finally Fh,ℓ sets a lower bound on the saturation (number of pulls) level of arm a. B.3.2
Decomposition of Regviol
We rewrite ∆Ah,ℓ ,h,ℓ = ∆π0 + (∆Ah,ℓ ,h,ℓ − ∆π0 ) for (h, ℓ) ∈ V. Thus, we have: Reg
constr
" L H # XX =σmax E ∆Ah,ℓ ,h,ℓ 1 {Vh,ℓ (Ah,ℓ )} ℓ=1 h=1
# " L H " L H # XX XX 1 {Vh,ℓ (Ah,ℓ )} +σmax E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} =σmax ∆π0 E ℓ=1 h=1
|
ℓ=1 h=1
{z
≜A1
}
{z
|
}
≜A2
(12) Both the terms in this decomposition are non-negative ashLemma 5 yields a natural lower i bound on PL PH constr the regret due to constraint-violation Reg ≥ ∆π0 E ℓ=1 h=1 1 {Vh,ℓ (Ah,ℓ )} . Step 1: Upper bound on A1 . We further decompose A1 using the conditioning event Uh,ℓ (Ah,ℓ ) as below:
" L H # XX A1 = E 1 {Vh,ℓ (Ah,ℓ )} ℓ=1 h=1
" L H # " L H # XX XX 1 {Vh,ℓ (Ah,ℓ )} 1{Uh,ℓ (Ah,ℓ )} ≤E 1 {Vh,ℓ (Ah,ℓ )} 1{Uh,ℓ (Ah,ℓ )} + E ℓ=1 h=1
ℓ=1 h=1
|
{z
≜B1
}
|
{z
≜B2
} (13)
Upper bound on B1 . We first divide the term B1 in two parts: one under the good event G1 and when G1 is false. We denote them by B1 |G1 and B1 |G1 , respectively. First, we bound B1 |G1 as follows: " L H # XX B1 |G1 = E 1 {Vh,ℓ (Ah,ℓ )} 1{Uh,ℓ (Ah,ℓ )} ℓ=1 h=1
17
" L H # o XX n ∆Ah,ℓ ,h,ℓ ˆ A ,h,ℓ ≥ =E 1 ∆Ah,ℓ ,h,ℓ > ∆π0 + ϵµ0 1 ∆ h,ℓ 1+c ℓ=1 h=1 " L H # XX ˆ A ,h,ℓ > ∆π0 + ϵµ0 =E 1 ∆ h,ℓ 1+c ℓ=1 h=1 " L H # XX (a) ∆π0 + ϵµ0 ˆ ≤E 1 ∆Ah,ℓ ,h,ℓ − ∆Ah,ℓ ,h,ℓ > −B 1+c ℓ=1 h=1 " L H # XX ∆ + ϵµ 0 π 0 =E 1 (θ − θ̂h,ℓ )⊤ (ϕAh,ℓ ,h,ℓ − ϕa∗h,ℓ ,h,ℓ ) > −B 1+c ℓ=1 h=1 " L H # XX (b) ∆π0 + ϵµ0 1/2 −B ≤E 1 βh,ℓ (αh,ℓ ) ∥ϕAh,ℓ ,h,ℓ − ϕa∗h,ℓ ,h,ℓ ∥(V γdecay )−1 > 1+c h,ℓ ℓ=1 h=1 " L H ( XX ≤E 1 ∥ϕAh,ℓ ,h,ℓ ∥2 γdecay −1 + ∥ϕa∗h,ℓ ,h,ℓ ∥2 γdecay −1 (Vh,ℓ
)
1 βh,ℓ (αh,ℓ )
ℓ=1 h=1
>
(Vh,ℓ
∆π0 + ϵµ0 −B 1+c
)
2 )#
" L H ( XX ≤2 E 1 ∥ϕAh,ℓ ,h,ℓ ∥2 γdecay −1 >
2 )# ∆π0 + ϵµ0 1 −B (Vh,ℓ ) 2β1,1 (α1,1 ) 1+c ℓ=1 h=1 " L H ( 2 )# XX ∆π0 + ϵµ0 1 2 1 ∥ϕAh,ℓ ,h,ℓ ∥ γdecay −1 > ≤2 E −B , (Vh,ℓ ) 2λS∗2 1+c
(c)
ℓ=1 h=1
where (a) holds due to the Assumption 3, and the fact that ⊤ θ ϕAh,ℓ ,h,ℓ < τ = θ⊤ ϕAh,ℓ ,h,ℓ < (1 − ϵ)θ⊤ ϕπ0 n o = θ⊤ ϕAh,ℓ ,h,ℓ − θ⊤ ϕa∗h,ℓ ,h,ℓ + θ⊤ ϕa∗h,ℓ ,h,ℓ − θ⊤ ϕπ0 < −ϵµ0 n o = −∆Ah,ℓ ,h,ℓ + θ⊤ ϕa∗h,ℓ ,h,ℓ − θ⊤ ϕπ0 < −ϵµ0 ⊤ ⊤ ∗ ⊆ −∆Ah,ℓ ,h,ℓ + min θ ϕah,ℓ ,h,ℓ − θ ϕπ0 < −ϵµ0 ℓ∈[L] o n = −∆Ah,ℓ ,h,ℓ + ∆π0 < −ϵµ0 n o = ∆Ah,ℓ ,h,ℓ > ∆π0 + ϵµ0 , (b) holds due to the definition of good event G1 in Equation (10), and finally (c) holds because we apply Boole’s inequality, ∀h, ℓ ≥ 1, βh,ℓ (αh,ℓ ) ≥ β1,1 (α1,1 ). It is easy to see if we put λ =
min
∆π +ϵµ0 0 −B 1+c
2S∗2 2 , then 2 B ,(∆π +ϵµ0 − 1+c ) 0
" L H # XX 2 B1 |G1 = E 1 ∥ϕAh,ℓ ,h,ℓ ∥ γdecay −1 > 1 (Vh,ℓ
ℓ=1 h=1
)
Leveraging the elliptical potential count lemma (Lemma 7) and Lemma 6, we get the final bound on B1 as:
2 B1 ≤ B1 |G1 +B1 |G1 ≤ 6d log 1 + λ 18
+
L X H X ℓ=1 h=1
αh,ℓ
Upper Bound on B2 . We again divide the second term B2 in two parts: one under the good event G1 and otherwise. We similarly denote them by B2 |G1 and B2 |G1 , respectively. First, we bound B2 |G1 as follows: " L H # XX B2 |G1 = E 1 {Vh,ℓ (Ah,ℓ )} 1{Uh,ℓ (Ah,ℓ )} ℓ=1 h=1
" L H # o XX n ∆Ah,ℓ ,h,ℓ ˆ A ,h,ℓ < =E 1 ∆Ah,ℓ ,h,ℓ > ∆π0 + ϵµ0 1 ∆ h,ℓ 1+c ℓ=1 h=1 " L H # XX ∆Ah,ℓ ,h,ℓ ˆ A ,h,ℓ − ∆ ≤E 1 ∆ − ∆π0 − ϵµ0 Ah,ℓ ,h,ℓ ≤ h,ℓ 1+c ℓ=1 h=1 " L H # XX B ˆ A ,h,ℓ − ∆ ≤E 1 ∆ − ∆π0 − ϵµ0 Ah,ℓ ,h,ℓ ≤ h,ℓ 1+c ℓ=1 h=1 " L H # XX B ˆ 1 ∆Ah,ℓ ,h,ℓ − ∆Ah,ℓ ,h,ℓ ≥ ∆π0 + ϵµ0 − =E 1+c ℓ=1 h=1 " L H ( 2 )# XX B 1 2 ≤2 E 1 ∥ϕAh,ℓ ,h,ℓ ∥ γdecay −1 ≥ ∆π0 + ϵµ0 − ) (Vh,ℓ 2βh,ℓ (αh,ℓ ) 1+c ℓ=1 h=1 )# " L H ( 2 XX B 1 1 ∥ϕAh,ℓ ,h,ℓ ∥2 γdecay −1 ≥ ∆π0 + ϵµ0 − ≤2 E (Vh,ℓ ) λS∗2 1+c ℓ=1 h=1
Similar to the analysis B1 , we use Lemma 7 with λ =
min
∆π +ϵµ0 0 −B 1+c
2S∗2 to 2 2 B ,(∆π +ϵµ0 − 1+c ) 0
get the final bound on B2 as:
2 B2 ≤ 6d log 1 + λ
+
L X H X
αh,ℓ .
ℓ=1 h=1
Step 2: Upper Bound on A2 . To find upper bound on A2 , we closely follow the proof structure of the standard regret in (Balagopalan & Jun, 2024, Lemma 1 and Theorem 1) but remove the need of the peeling event. Balagopalan & Jun (2024) leverage peeling to lower bound the gap ∆Ah,ℓ ,h,ℓ , since it appears in the denominator of the pulling probability of arm Ah,ℓ . We get the lower bound due to the presence of π0 . We use the event Eh,ℓ to decompose A2 as: " L H # XX A2 = E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} ℓ=1 h=1
" L H # XX ≤E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 {Eh,ℓ } ℓ=1 h=1
|
{z
}
≜C1
+E
" L H XX
#
(∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ
ℓ=1 h=1
|
{z
≜C2
19
}
Upper bound on C1 . Now, we focus on the term C1 :
" L H # XX C1 = E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 {Eh,ℓ } ℓ=1 h=1
# " L H n o XX =E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 ∆Ah,ℓ ,h,ℓ > ∆π0 + ϵµ0 1 {Eh,ℓ } ℓ=1 h=1
As we assign the probability of pulling Ah,ℓ from Bh,ℓ as exactly 12 , upper bound analysis of term C1 closely matches with the analysis for term A2 in (Balagopalan & Jun, 2024). Thus, we have– 2 6(B − ∆π0 )d 2 C1 ≤ 6(B − ∆π0 )d log 1 + ≤ log 1 + λ σmax λ Upper bound on C2 . We further decompose C2 based on the event based on the event Fh,ℓ (Ah,ℓ )–
# " L H XX C2 = E (∆Ah,ℓ ,h,ℓ − ∆π0 1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ ℓ=1 h=1
" L H # XX ≤E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 {Fh,ℓ (Ah,ℓ )} ℓ=1 h=1
{z
|
}
≜D1
+E
" L H XX
(∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ
# n o 1 Fh,ℓ (Ah,ℓ )
ℓ=1 h=1
|
{z
≜D2
}
Upper bound on D1 . Now, we focus on the term D1 –
# " L H XX D1 = E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 {Fh,ℓ (Ah,ℓ )} ℓ=1 h=1
To upper bounding this term, we follow the upper bound formalisation of Term D2 in (Balagopalan & Jun, 2024) without the peeling argument to get–
(B − ∆π0 ) 2 2 log 1 + + 3(B − ∆π0 )d log 1 + ε2 λε2 λ (B − ∆π0 ) 2 3(B − ∆π0 )d 2 ≤3d log 1 + + log 1 + σmax ε2 λε2 σmax λ
D1 ≤3d
Upper bound on D2 . To upper bound this term, we again decompose it by leveraging the event Uh,ℓ (Ah,ℓ )–
" L H # n o XX D2 = E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 Fh,ℓ (Ah,ℓ ) ℓ=1 h=1
20
" L H # o n XX ≤E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 Fh,ℓ (Ah,ℓ ) 1 {Uh,ℓ (Ah,ℓ )} ℓ=1 h=1
|
{z
}
≜E1
# " L H n o n o XX E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 Fh,ℓ (Ah,ℓ ) 1 Uh,ℓ (Ah,ℓ ) ℓ=1 h=1
{z
|
}
≜E2
Upper bound on E1 . This upper bound can be obtained following the steps in (Balagopalan & Jun, 2024) for their term F1 ignoring the peeling steps. Thus, we have– (∆π0 + ϵµ0 )2 E1 ≤ (B − ∆π0 )HL exp − αemp 4ε2 βh,ℓ (αh,ℓ )(1 + c)2 3d(B − ∆π0 ) 1 2 2 + log 1 + + log 1 + 2 αemp ε2 λε2 λ 2 (∆π0 + ϵµ0 ) 1 (B − ∆π0 )HL exp − 2 ≤ σmax αemp 4σmax ε2 βh,ℓ (αh,ℓ )(1 + c)2 2 3d(B − ∆π0 ) 1 2 + + log 1 + log 1 + 2 σmax αemp ε2 λε2 λ 1
Upper bound on E2 . We finally use the event Jh,ℓ (h, ℓ) to decompose the event E2 as– " L H # n o n o XX E2 = E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 Fh,ℓ (Ah,ℓ ) 1 Uh,ℓ (Ah,ℓ ) ℓ=1 h=1
" L H # n o n o XX (∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ 1 Fh,ℓ (Ah,ℓ ) 1 Uh,ℓ (Ah,ℓ ) 1 {Jh,ℓ (Ah,ℓ )} ≤E ℓ=1 h=1
|
{z
}
≜F1
+E
" L H XX
(∆Ah,ℓ ,h,ℓ − ∆π0 )1 {Vh,ℓ (Ah,ℓ )} 1 Eh,ℓ
# n o n o n o 1 Fh,ℓ (Ah,ℓ ) 1 Uh,ℓ (Ah,ℓ ) 1 Jh,ℓ (Ah,ℓ )
{z
}
ℓ=1 h=1
|
≜F2
Upper bound on F1 . It is easy to see that in F1 , if the good event in Equation (10) does not happen, then under G1 , F1 |G1 ≤ (B − ∆π0 )
H X L X
H
αh,ℓ ≤≤
h=1 ℓ=1
L
(B − ∆π0 ) X X αh,ℓ . σmax h=1 ℓ=1
On the other hand, under the event G1 , following (Balagopalan & Jun, 2024), we write " L H # XX c(∆π0 + ϵµ0 ) ⊤ F1 |G1 ≤ E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 (θ̂h,ℓ − θ) ϕAh,ℓ ,h,ℓ > − ε1 1{G1 } 1+c ℓ=1 h=1 " L H ( # 2 ) XX c(∆π0 + ϵµ0 ) 1 2 ≤E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 ∥ϕAh,ℓ ,h,ℓ ∥ γdecay −1 ≥ 1{G1 } (Vh,ℓ ) βh,ℓ (αh,ℓ ) 2(1 + c) ℓ=1 h=1 " L H ( # 2 ) XX (a) c(∆ + ϵµ ) 1 0 π0 1{G1 } ≤E (∆Ah,ℓ ,h,ℓ − ∆π0 )1 ∥ϕAh,ℓ ,h,ℓ ∥2 γdecay −1 ≥ (Vh,ℓ ) λS∗2 2(1 + c) ℓ=1 h=1
21
2 3(B − ∆π0 )d 2 ≤3(B − ∆π0 )d log 1 + ≤ log 1 + , λ σmax λ choosing ε1 =
c(∆π +ϵµ0 ) 0 . 2(1+c)
Thus, final upper on F1 is given by, H L 3(B − ∆π0 )d 2 (B − ∆π0 ) X X F1 ≤ log 1 + + αh,ℓ σmax λ σmax h=1 ℓ=1
Bound on F2 . We follow the analysis of term F3 of (Balagopalan & Jun, 2024) to state the final upper bound on F2 with Hmax = e in our case–
128e(B − ∆π0 )Copt d log d F2 ≤ σmax αopt ε21
λS∗2 + d log 1 + 2
PH
h=1
PL
2 ℓ=1 σh,ℓ
!!
dλ
Hence, putting all the components in Equation (12), we get the final bound on Regconstr as: Reg
constr
!! PH PL 2 128e(B − ∆π0 )Copt d log d λS∗2 h=1 ℓ=1 σh,ℓ + d log 1 + ≤ αopt ε21 2 dλ H X L X 2 + 12(B − ∆π0 )d log 1 + + (B − ∆π0 ) αh,ℓ λ h=1 ℓ=1 1 (∆π0 + ϵµ0 )2 + (B − ∆π0 )HL exp − 2 αemp 4σmin ε2 βh,ℓ (αh,ℓ )(1 + c)2 3d(B − ∆π0 ) 1 2 2 + log 1 + + log 1 + 2 αemp ε2 λε2 λ (B − ∆π0 ) 2 + 3d log 1 + ε2 λε2 L X H X 2 αh,ℓ + 2∆π0 + 12∆π0 d log 1 + λ ℓ=1 h=1 !!! H X L X B − ∆π0 2 2 2 = Õ d log (LH) + log σh,ℓ (∆π0 + ϵµ0 )2 h=1 ℓ=1
(∆π0 +ϵµ0 )2 1 , c = 1, and αh,ℓ = LH . β max h,ℓ (αh,ℓ ) log(LH)
where the last inequality holds due to putting ε2 = 4σ2 2S∗2
Recall, λ = σmax min
∆
π0 +ϵµ0 −B 2
2
,(∆π0 +ϵµ0 − B 2 )
2
.
Thus, Algorithm 2 and 3 jointly satisfies – Reg
B.4
constr
= Õ
2 σmax (B − ∆π0 ) 2 d (∆π0 + ϵµ0 )2
2
log (LH) + log
H X L X h=1 ℓ=1
Part II: Constraint Satisfying Regret Upper Bound
Theorem 1. Thus, Algorithm 2 and 3 jointly satisfies – 22
!!! 2 σh,ℓ
.
P L L−ℓ PH 2 d2 log2 (LH) + log (γ ) σ decay ℓ=1 h=1 h,ℓ Regsafe = Õ ∆min
Proof. In this section, we provide a complete proof of the regret upper bound under constraint satisfaction, i.e, upper bound on Regopt . The proof structure involves two steps: 1. Then for the upper bound, we first define the conditioning event that will be used to decompose the regret expression further down the line. 2. We bound each part of the decomposition step by step to get a final accumulated upper bound. B.4.1
Step 1: Defining the Conditioning Events
To prove upper bound on Regsafe , we recall the events defined in Part I (Definition 2) with additional peeling events. Uh,ℓ (a) ≜
ˆ ∆ Ah,ℓ ,h,ℓ ≥
∆Ah,ℓ ,h,ℓ
1+c
for some c ≥ 0
Eh,ℓ ≜ {|Bh,ℓ | > 0} , where Bh,ℓ = a : ∥ϕa,h,ℓ ∥2(V γdecay )−1 > 1 h,ℓ n o γ Ch,ℓ,k (Ah,ℓ ) ≜ ∥ϕa,h,ℓ ∥(V decay )−1 > εk h,ℓ ¯ A ,h,ℓ < (∆ + ϵµ0 )2−k+1 Dh,ℓ,k (Ah,ℓ ) ≜ (∆π0 + ϵµ0 )2−k < ∆ π0 h,ℓ −K ¯ Dh,ℓ,K (Ah,ℓ ) ≜ ∆Ah,ℓ ≤ (∆π0 + ϵµ0 )2 n o ⊤ Jh,ℓ (a) ≜ θ⊤ ϕa∗h,ℓ ,h,ℓ − θ̂h,ℓ ϕa∗h,ℓ ,h,ℓ ≤ ε2,k , ¯ A ,h,ℓ ≜ max{∆ where we define ∆ Ah,ℓ ,h,ℓ , ∆π0 + ϵµ0 }. h,ℓ B.4.2
Decomposition of Regsafe
We follow the proof structure from (Balagopalan & Jun, 2024) for this part. We use similar peeling technique and decomposition of regret using conditioning events. As we have constraint satisficing in this case, we use (∆π0 + ϵµ0 ) as the upper bound for ∆Ah,ℓ ,h,ℓ . Final Regret Bound under Constraint Satisficing. 1 2 Regsafe ≤18(σmax ∆π0 + ϵµ0 )d log 1 + σmax λ −P + LH(σmax ∆π0 + ϵµ0 )2 1 (σmax ∆π0 + ϵµ0 )2−P > ∆min 2 12d(σmax ∆π0 + ϵµ0 ) log 1 + + 2−P ε λ2−2P ε 1 (σmax ∆π0 + ϵµ0 )2 + 4LH(σmax ∆π0 + ϵµ0 ) exp − αemp 16εβh,ℓ (αh,ℓ ) 1 12d(σmax ∆π0 + ϵµ0 ) 2 + 2 log 1 + αemp 2−P ε λ2−2P ε ! 2 + 6(σmax ∆π0 + ϵµ0 )d log 1 + λ + 2(σmax ∆π0 + ϵµ0 ) log(LH) 23
192βh,ℓ (αh,ℓ )d 32βh,ℓ (αh,ℓ log 1 + (σmin ∆π0 + ϵµ0 )2−P λ(σmin ∆π0 + ϵµ0 )2 2−2P !! PL PH 2 512d log(d)eCopt λS∗ ℓ=1 h=1 σa,h,ℓ + + d log 1 + αopt (σmin ∆π0 + ϵµ0 )2−P 2 dλ
+
Putting ϵ =
(σmin ∆π0 +ϵµ0 )2 16βh,ℓ (αh,ℓ )
Algorithm 2 and 3 jointly satisfy–
P P H 2 d2 log2 (LH) + log σ h=1 a,h,ℓ Regsafe = Õ κ ∆min
maxa,h,ℓ σ 2
where κ ≜ mina,h,ℓ σ2a,h,ℓ . a,h,ℓ
C
Upper Bound on Expected Constraint Violation
In this section, we prove the upper bound guaranty on the expected number of constraint violation of Dri-MED. Theorem 4. Dri-MED enjoys Violation(π0 ) = Õ (d) , Proof. We start from the definition of expected constraint violation– Violation(π0 ) = E [1 {Vh,ℓ (Ah,ℓ )}] From the standard regret analysis in Section B, we know Violation(π0 ) = A1 . Thus, setting λ = min
∆
2S∗2 to get the final bound on B2 as: 2 2 ,(∆π0 +ϵµ0 − B 2 )
π0 +ϵµ0 −B 2
Violation(π0 ) ≤ 12d log 1 +
min
2 ∆π0 +ϵµ0 − B , 2 S∗
24
∆π0 + ϵµ0 − B2
2 + 2 = Õ(d) .
D
Discussion on the Lagrangian Dual Variable ϵ Recall the dual update with ρ ≜ (1−ϵ) in Algorithm 2:
Lyapunov Drift for the Dual Variable.
νh+1,ℓ = max 0, νh,ℓ + ηh (ξh,ℓ − ρ) ,
h i ξh,ℓ := 1 ⟨θ̂h,ℓ , ϕAh,ℓ ,h ⟩ < τℓ ,
(14)
√ with ηh,ℓ = η/ h, η > 0 to be chosen. Note, ξh,ℓ ∈ {0, 1} regardless of the reward distribution. Thus, the dual update depends only on whether the estimated reward crosses the threshold, not on the magnitude of the reward itself. Lemma 2 (Lyapunov drift inequality). For all t ≥ 1: 2 2 2 E[νh+1,ℓ − νh,ℓ | Ft ] ≤ 2ηh,ℓ E[ξh,ℓ | Fh,ℓ ] − ρ νh,ℓ + ηh,ℓ . Proof. Using max{0, x}2 ≤ x2 : 2 νh+1,ℓ ≤ νh,ℓ + ηh,ℓ (ξh,ℓ − ρ)
2
2 2 = νh,ℓ + 2ηh,ℓ (ξh,ℓ − ρ)νh,ℓ + ηh,ℓ (ξh,ℓ − ρ)2 .
Since ξh,ℓ ∈ {0, 1}, we have (ξh,ℓ − ρ)2 ≤ 1. Taking conditional expectation gives the result. √ √ Lemma 3 (Dual variable growth). With ν0 = 0 and ηh,ℓ = η/ ℓh, we have νh,ℓ ≤ 2η ℓh. Proof. Since ξh,ℓ ≤ 1 we have νh+1,ℓ ≤ νh,ℓ + ηh,ℓ , so νh,ℓ ≤
PL
ℓ=1
PH
√
h=1 η/
√ s ≤ 2η LH.
The dual update in Equation (14) is exactly projected online gradient descent (OGD) on the sequence of losses ℓh,ℓ (ν) ≜ −ν(ξh,ℓ − ρ) over ν ∈ [0, ∞). The gradient at νh,ℓ is −(ξh,ℓ − ρ), which lies in (−1, 1] since ξh,ℓ ∈ {0, 1} and ρ ∈ [0, 1). Lemma 4 (OGD regret bound). For any ν ∗ ≥ 0: L X H X ℓ=1 h=1
Lt (νh,ℓ ) −
L X H X
Lt (ν ∗ ) ≤
ℓ=1 h=1
√ ν∗2 + η LH. 2ηLH
Proof. The loss Lh,ℓ (ν) = −ν(ξh,ℓ − ρ) is linear in ν, so it is convex, and its gradient is ∇t = ∇ν Lh,ℓ (νh,ℓ ) = −(ξh,ℓ − ρ). Since ξh,ℓ ∈ {0, 1} and ρ ∈ [0, 1), we have ∇h,ℓ ∈ [−(1 − ρ), ρ] ⊂ (−1, 1], so ∇2h,ℓ ≤ 1. We use (Hazan, 2016, Theorem 3.1) with ν1,1 = 0 to directly get the desired result.
25
E
Dri-IMED: Drift Adaptive Indexed Minimum Empirical Divergence
For empirical evaluation, in this section we provide the implemented pseudocode of the Dri-IMED algorithm, that is an Indexed Minimum Empirical Divergence version of MED strategy used in this paper. The main difference from Algorithm 3 is in Line 4 of Dri-IMED. It computes the Lagrangian dual-augmented IMED index being optimistic about the action, but pessimistic with respect to the constraint. Whenever a pulled arm violates the constraint the IMED index is penalised. At the end it plays the arm that has the minimum index. Algorithm 4 Dri-IMED: Drift adaptive Indexed Minimum Empirical Divergence (IMED) Step |A|
γ
Require: Episode ℓ ∈ [L], user id h ∈ [H], user’s rescaled features {ϕa,h,ℓ }a=1 , θ̂h,ℓ , Vh,ℓdecay , λ. Require: Constraint threshold τℓ , Lagrangian multiplier νℓ . 1: Compute confidence radius and upper and lower confidence bound: For each arm a ∈ A, s βh,ℓ (αh,ℓ ) =
γ
log
detVh,ℓdecay
2 √ 1 + 2 log + λS αh,ℓ
detV0 q UCB(a, h, ℓ) = ⟨θ̂h,ℓ , ϕa,h,ℓ ⟩ + βh,ℓ (αh,ℓ )∥ϕa,h,ℓ ∥(V γdecay )−1 h,ℓ q LCB(a, h, ℓ) = ⟨θ̂h,ℓ , ϕa,h,ℓ ⟩ − βh,ℓ (αh,ℓ )∥ϕa,h,ℓ ∥(V γdecay )−1 h,ℓ
2: Empirical best action: âh,ℓ = arg maxa∈A ⟨θ̂h,ℓ , ϕa,h,ℓ ⟩ 3: Maximum empirical reward: µ̂max (h, ℓ) = maxa∈A ⟨θ̂h,ℓ , ϕa,h,ℓ ⟩ 4: Lagrangian-augmented IMED index: For each arm a ∈ A:
νℓ · max{0, τℓ − LCB(a, h, ℓ)}2 (UCB(a,h,ℓ)−µ̂max (h,ℓ)) aug Ih,ℓ (a) = Nh,ℓ (a) · 2 2σh,ℓ +ν · max{0, τ − LCB(a, h, ℓ)} ℓ
ℓ
aug
5: Pull Ah,ℓ = arg mina∈A Ih,ℓ (a)
26
if a = âh,ℓ if UCB(a, h, ℓ) ≥ µmax (h, ℓ)
F
Experimental Analysis
To assess the performance of Dri-MED and Dri-IMED, we conduct numerical experiments on a synthetic episodic contextual linear bandit with preference feedback and context drift. The environment consists of H users, A arms, and L episodes, with a d-dimensional parameter θ∗ and M -dimensional feedback signals. The mean feedback signal E[Yh,ℓ | a] = Φ(a)θ∗ is contextindependent, while the covariance scales with the observed context norm, inducing heteroscedastic noise. User preference vectors {ph } are drawn from a Dirichlet distribution and held fixed across episodes. Setup. The full environment generation is detailed in Algorithm 5. The baseline policy π0 is set ⋆ as the arm at the median performance quantile for each user, i.e. π0 (h) = arg mina |ϕ⊤ a,h θ − h h ⋆ q0.5 | where q0.5 is the median of {ϕ⊤ a,h θ }a∈[A] . We use the following environment parameters throughout all experiments: feature dimension d = 4, feedback dimension M = 4, number of arms A = 5, number of users H = 10, number of episodes L = 1000, parameter norm B = 1, preference scale s = 2, context dimension D = 2, context noise σC = 1, and reward noise σr = 0.1. Results that are presented in Figure 2 are averaged over 128 independent seeds. Algorithm 5 Environment Generation Require: d, M, A, H, L, f, σC , σr , s, B 1: Draw θ ⋆ ∼ N (0, Id ), normalise to ∥θ ⋆ ∥ = B 2: Draw row-normalised Φ(a) ∈ RM ×d and Σa = Sa Sa⊤ /M for each a ∈ [A] 3: Draw ωh ∼ Dir(s · ph ) with ph ∼ Dir(1M ) for each h ∈ [H] 4: Set κℓ ← 1 + f (ℓ, L) for ℓ ∈ [L] 5: for ℓ = 1 to L do 2 2 κℓ ID ) for each h ∈ [H] 6: Sample Ch,ℓ ∼ N (0, σC ⊤ 7: Set ϕa,h ← Φ(a) ωh for all a ∈ [A], h ∈ [H] 8: Draw Yh,ℓ ∼ N Φ(Ah,ℓ )θ⋆ , σr (1 + ∥Ch,ℓ ∥) ΣAh,ℓ , set rh,ℓ ← ωh⊤ Yh,ℓ 9: end for
Drifting. We consider four drift regimes for the context distribution, parameterized by a magnitude κ > 0 and a shared drift direction v ∈ RC , ∥v∥ = 1, so that µℓ = f (ℓ) · v: • No drift: f (ℓ) = 0, • Gradual drift: f (ℓ) = κ · ℓ/L, 1 2πℓ • Periodic drift: f (ℓ) = κ · 1 + sin , 2 L/50 P • Abrupt drift: f (ℓ) = κ · i i · 1{ℓ ≥ τi }, where τ1 = ⌊L/3⌋ and τ2 = ⌊2L/3⌋ are fixed change-points. Baselines. To the best of our knowledge, no prior algorithm addresses this combined setting of preference structure, heteroscedastic noise, and non-stationary context distributions; Since no existing algorithm is designed for this setting, we evaluate Dri-MED and Dri-IMED against four stationary linear bandit baselines that ignore both the drift and the preference structure: OFUL (Abbasi-Yadkori et al., 2011), LinMED (Balagopalan & Jun, 2024), LinIMED (Bian & Tan, 2024), and LinTS (Agrawal & Goyal, 2013). For all drift types, we set magnitude κ = 100, so the maximumqcontext scale is smax = 1 + κ = 101. The per-arm noise standard deviation is
σa,h,ℓ =
ωh⊤ Σa · σr · (1 + ∥Ch,ℓ ∥) · ωh , which is bounded by r σ̄ =
σr · (1 + σc · smax ·
27
√
D) · max[Σa ]ii a,i
where σr = 0.1 is the reward noise, σc = 1.0 the context noise scale, D = 2 the context dimension, and maxa,i [Σa ]ii the largest diagonal entry across all arm covariance matrices (evaluated once at initialisation). In our experiments this yields σ̄ ≈ 1.92, which we use as the sub-Gaussianity parameter for all algorithms. We report cumulative regret and cumulative satisficing constraint violations, averaged over independent random seeds. All specific hyperparameters used by the algorithm are summarized in Table 3 Table 3: Hyperparameters used per algorithm. Parameters shared by all algorithms: regularisation λ = σ̄ 2 /S 2 , confidence δ = 0.01, S = 1. Algorithm
γdecay
ε
ν0
αopt
αemp
C
OFUL LinTS LinMED LinIMED Dri-MED Dri-IMED
– – – – 0.99 0.99
– – – – 0.1 0.1
– – – – 1.0 1.0
– – 0.99 – 0.99 –
– – 0.005 – 0.005 –
– – – 30 – –
Results. Figure 2 report cumulatieve regret and constraint violation rates across all drift regimes. Dri-MED and and Dri-IMED consistently achieve very low cumulative regret across all settings, outperforming all stationary baselines by a large margin. Among baselines, OFUL performs best but still incurs regret an order of magnitude larger than our methods; LinMED and LinTS perform worst, highlighting the cost of ignoring the preference and heteroscedastic structure. Importantly, both Dri-MED and Dri-IMED maintain near-zero true constraint violation throughout all episodes, whereas baselines show persistent violations. The results are stable across drift regimes: even under abrupt drift with magnitude κ = 100, the performance of our methods is largely unaffected, confirming that the drift-adaptive design successfully absorbs the non-stationarity through the discounted regression and context-scaled normalisation. Figure 4 further illustrates that Dri-MED concentrates pulls on the oracle-optimal arm for every user, while LinMED spreads mass across suboptimal arms, and π0 is always fixed at the median arm. Ablations. Figure 3 examines the sensitivity of Dri-MED and Dri-IMED to the baseline quantile q and satisficing tolerance ε under abrupt drift. As q increases, the baseline policy π0 becomes stronger, tightening the constraint and reducing the feasible arm set; this forces the algorithm to focus on higher-quality arms earlier, yielding lower final regret. Conversely, increasing ε loosens the constraint, allowing more exploration of suboptimal arms and increasing regret. Dri-IMED consistently achieves lower regret and tighter interquartile ranges than Dri-MED across all ablation settings, suggesting it is more sample-efficient under tighter constraints.
28
None Drift
1000 500 600
800
Episode
Violation rate
Cumulative Regret
500 400
600
800
Episode
Violation rate
Cumulative Regret
500 0
0
200
400
600
800
Episode
OFUL
Violation rate
Cumulative Regret
1000 500 0
200
400
600
Episode
800 OFUL
1000
600
Episode
800
LinIMED
200
400
600
Episode
LinMED
800
LinIMED
200
0.2 200
400
600
Episode
LinMED
LinIMED
800
1000 Dri-MED
400
600
Episode
800
1000
800
1000
800
1000
Dri-IMED True Violation Rate
0.8 0.6 0.4 0.2 0
200
400
600
Episode
Dri-IMED True Violation Rate
1.0
0.4
LinTS
0
K = 5, H = 10, L = 1000, d = 4
0.6
1000
0.2
Dri-MED
0.8
800
0.4
0.0
Estimated Violation Rate
600
Episode
0.6
1.0
1000
400
True Violation Rate
K = 5, H = 10, L = 1000, d = 4
Estimated Violation Rate
0.2
0
200
0.8
Dri-MED
0.4
0.0
0
Dri-IMED
0.0
1000
0.6
1.0
0.2
1.0
0.8
LinTS
1500
400
LinMED
0
0.4
K = 5, H = 10, L = 1000, d = 4
Estimated Violation Rate
200
Abrupt Drift
Cumulative Regret
0
0
0.6
Dri-MED
0.2
0.0
1000
LinIMED
0.8
0.0
1000
0.4
1.0
1000
800
0.6
LinTS
1500
600
Episode
LinMED
Periodic Drift
Cumulative Regret
400
0.8
0.0
1000
OFUL
2000
200
1.0
1000
200
0
LinTS
1500
0
0.2
Gradual Drift
Cumulative Regret
0
0.4 0.0
1000
OFUL
0.6
Violation rate
400
0.8
Violation rate
200
True Violation Rate
1.0
Violation rate
0
Estimated Violation Rate
Violation rate
1500
0
K = 5, H = 10, L = 1000, d = 4
1.0
Violation rate
Cumulative Regret
Cumulative Regret
0.8 0.6 0.4 0.2 0.0
0
200
400
600
Episode
Dri-IMED
Figure 2: Cumulative regret (left), estimated violation rate (center), and true violation rate (right) for each drift regime. Shaded bands show the 5–95% quantile range over 128 seeds.
29
Final cumulative regret
Ablation study
Abrupt drift
Baseline policy
K = 5, H = 10, L = 1000, = 0.99
Constraint tightness
150
150
100
100
50
50
0
0.25
0.5
0
0.75
Baseline quantile q
Dri-MED
0.05
0.1
0.2
0.3
Satisficing tolerance
0.5
Dri-IMED
Figure 3: Ablation study on abrupt drift: effect of the baseline policy quantile q (left) and the satisficing tolerance ε (right) on the final cumulative regret of Dri-MED and Dri-IMED.
Pull fraction
Pull fraction
Pull fraction
Pull fraction
Pull fraction
Arm allocation per user User 1
1 0
a1 ¹ (0.45)
a2 (0.62)
a1 ¹ (0.25)
a2 (0.56)
a1 ¹ (0.42)
a2 (0.69)
a1 ¹ (0.42)
a2 (0.66)
a1 ² (0.05)
a2 (0.53)
a3 ² (0.24)
a3 ² (0.35)
a3 ² (0.21)
a1 ¹ (0.37)
a2 (0.63)
a3 ² (0.15)
a3 ¹ (0.32)
a4 (-0.24)
a5 (-0.27)
a4 (-0.40)
a5 (-0.08)
a4 (-0.29)
a5 (-0.12)
a4 (-0.39)
a5 (-0.38)
a4 ² (0.02)
a5 (-0.14)
User 4
a4 (-0.26)
a5 (-0.03)
a1 ¹ (0.40)
a2 (0.66)
a3 ² (0.35)
User 6
a4 (-0.46)
a5 (-0.25)
a1 ¹ (0.42)
a2 (0.59)
a3 ² (0.01)
User 8
a4 (-0.40)
a5 (-0.26)
a1 ² (0.23)
a2 (0.63)
User 9
1 0
a5 (-0.11)
User 7
1 0
a4 (-0.34)
User 5
1 0
a3 ² (0.13)
User 2
User 3
1 0
LinMED vs Dri-MED vs 0
a3 ¹ (0.34)
User 10
a4 (-0.37)
LinMED
a5 (-0.32)
a1 (-0.39)
Dri-MED
a2 ¹ (0.35)
a3 (0.40)
0
Figure 4: Arm pull fraction per user over 1000 episodes on abrupt drift. ⋆ denotes the oracle best arm; (1) and (2) the first and second suboptimal arms. Mean rewards are shown in parentheses.
30
G
ApproxDesign
Algorithm 6 ApproxDesign |A|
Require: Scaled arm matrix A(h) = {ϕ̃a }a=1 1: Project onto active subspace: compute PCA of A(h) , retain eigenvectors with eigenvalue > ϵ0 , obtain low-dimensional matrix X̃ 2: Initialise via volume approximation: select 2d′ arms S0 ⊆ A spanning the subspace by greedily picking arg Pmaxa ⟨ϕ̃a ,⊤bi ⟩ and arg mina ⟨ϕ̃a , bi ⟩ along each basis direction bi 3: Set V ← a∈S0 ϕ̃a ϕ̃a 4: while maxa∈A ∥ϕ̃a ∥2V −1 > 1 do 5: a⋆ ← arg maxa∈A ∥ϕ̃a ∥2V −1 ⋆ 6: V ← V + ϕ̃a⋆ ϕ̃⊤ a⋆ , S0 ← S0 ∪ {a } 7: end while opt 8: qh (a) ← |{i : S0 [i] = a}| / |S0 | opt 9: return qh By the virtue of design of Dri-MED, we retain the exact guaranty of eliminating highly suboptimal arms as same as (Balagopalan & Jun, 2024). By the virtue of design of Dri-MED, we retain every guaranty on arm saturation by scaling both αemp and αopt by exp(−νh,ℓ ) per step. Intuitively, more the√value of the Lagrangian dual, more unsafe is the arm. As the Lagrangian dual grows at a rate O( ℓh) (Lemma 3), it ensures a truly unsafe arm is eliminated while augmentation of the arm set. This is a novel adaptation to make the design constraint-aware. We omit these proofs as they directly follow from (Balagopalan & Jun, 2024) and we do not want to remain repetitive.
31
H
Useful Technical Results
Lemma 5 (Lower bound on gap for violating rounds). For any constraint violating index (h, ℓ), ∆Ah,ℓ ,h,ℓ ≥ ∆π0 . Proof. The proof is straightforward. We decompose the gap as:
∆Ah,ℓ ,h,ℓ = θ⊤ (ϕa∗ℓ ,h,ℓ − ϕAh,ℓ ,h,ℓ ) = θ⊤ (ϕa∗ℓ ,h,ℓ − ϕπ0 ) + θ⊤ (ϕπ0 − ϕAh,ℓ ,h,ℓ ) | {z }
, iff (h, ℓ) ∈ V
≥0
≥ min θ⊤ (ϕa∗ℓ ,h,ℓ − ϕπ0 ) = ∆π0 ℓ∈[L]
Definition 3 (Good event at the end of ℓ-th episode). n o G2 ≜ h = H, ∀ℓ ≥ 1 : ∥θ − θ̂ℓ ∥2V γdecay ≤ βℓ (δℓ )
(15)
ℓ
Note, the index (H, ℓ) denotes end of the episode ℓ. Thus for brevity, we remove the index h for the event G2 . Lemma 6 (Heteroscedastic weighted (H, ℓ)-th confidence set). Following the information acquisiγ γdecay tion rule at the end of episode ℓ ∈ [L], i.e., Vℓ decay = γdecay Vℓ−1 , we define s γdecay √ detVℓ−1 1 1/2 βℓ (δℓ ) ≜ 2 log + 2 log + λ S∗ , detV0 δℓ where δℓ ∈ (0, 1) is to characterised later on. Then P(G2 ) ≥ 1 −
PL
ℓ=1 δℓ .
Proof. For this proof, we again apply the self-normalized martingale inequality of (Abbasi-Yadkori γ et al., 2011, Theorem 2) to the discounted Gram matrix Vℓ decay . At round (H, ℓ), the accumulated PH PH 2 noise over H reward signal ηH,ℓ = h=1 ηh,ℓ is h=1 σA -sub-Gaussian and Fℓ -measurable. h,ℓ ,h,ℓ PL ℓ ¯ The weighted process ℓ=1 γ ηH,ℓ ϕℓ is a martingale, and the theorem yields the stated bound PL round-by-round. Thus, a union bound over all ℓ gives P(G2 ) ≥ 1 − ℓ=1 δℓ . Lemma 7 (Elliptical Potential Count Lemma: Lemma C.2 of (Jun & Kim, 2024)). Let Pt x x⊤ x1 , x2 , . . . , xt ∈ Rd be a n sequence of vectors with ∥x ∥ ≤ 1, ∀s ∈ [t]. Let V = λI + s t s s s=1 o 2 2
for some λ > 0. Let J = s ∈ [t] : ∥xs ∥V −1 ≥ L2 for some L2 ≤ 1. Then, s−1
|J| ≤ 3
d 2 ln 1 + L2 L2 λ
Lemma 8 (Elliptical Potential Lemma: Proposition 2 of (Abeille & Lazaric, 2017)). Let Pt x1 , x2 , . . . , xt ∈ Rd be a sequence of vectors with ∥xs ∥2 ≤ 1, ∀s ∈ [t]. Let Vt = λI + s=1 xs x⊤ s for some λ > 0. Then, t X t 2 ∥xs ∥Vs−1 ≤ 2d log 1 + . dλ s=1 Corollary 1 (Elliptical Potential Lemma for rescaled features). For ∥ϕAh,ℓ ,h,ℓ ∥22 ≤ 1, ∀h, ℓge1, t 2 ∥ϕAh,ℓ ,h,ℓ ∥(V γdecay )−1 ≤ 2d log 1 + dλ h,ℓ 32
Lemma 9 (OFUL confidence bound lemma adapted from Theorem 2 of (Abbasi-Yadkori et al., 2011)). Assume ∀s ∈ [t], ∥as ∥ ≤ 1, and ∥θ∗ ∥2 ≤ S, for some fixed S > 0. We also assume ∆a := maxa′ ∈At ⟨a, θ∗ ⟩ − ⟨a, θ∗ ⟩ ≤ 1, ∀a ∈ A p ≤ βt−1 (δt−1 ) ≥ 1 − δ. ∀t ≥ 1, P θ̂t−1 − θ∗ Vt−1
Lemma 10 (Adapted from Lemma 3 in Balagopalan & Jun (2024)). Let f˜h (a), qh are defined as per Algorithm 3 where Ah,ℓ ̸= a . Then ∀h > 1, X qh (b)ft (b) ≥ αemp e−νh,ℓ 1≥ b∈Bh
Lemma 11 (Adapted from Lemma 5 in (Balagopalan & Jun, 2024)). For Dri-MED, we have– 2 θ̂h,ℓ − θ γdecay Vh,ℓ 2 2 · Copt · d log(d) a∗h,ℓ (V (p )γdecay )−1 ≤ exp h αopt βh,ℓ (αh,ℓ ) where a∗h,ℓ is true best arm at user h in episode ℓ. Lemma 12 ((Balagopalan & Jun, 2024)). 2
a∗h,ℓ (V (p )γdecay )−1 ≤ h
33
2e · Copt · d log(d) αopt