Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts

arXiv:2606.09802v1 Announce Type: cross 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 personalized 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 oldsymbol{pi}_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 regret scales as ilde{mathcal O}left(frac{kappa}{ilde{Delta}}d^2(log(T)right), where ilde{Delta} is the constraint-aware sub-optimality gap subject to policy pi_0, with variance-aware multiplicative term kappa that we carefully handle using heteroskedastic regression. We further show Dri-MED enjoys ilde{O}(d) expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.

Source: arXiv cs.AI | 2026-06-09