Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts
2026-06-08 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors study a problem where a system must recommend things to different users whose tastes and the context change over time. They transform this into a simpler problem with changing noise patterns and introduce an algorithm called Dri-MED to handle it. Their method makes better recommendations than simple approaches by ensuring each choice is better than a basic strategy while accounting for variability and shifts. They also prove their algorithm learns efficiently and violates constraints only a few times. Finally, experiments show Dri-MED outperforms other methods that ignore changing tastes and contexts.
contextual banditslinear banditsnon-stationary noiseheteroskedasticitymulti-armed banditsregret analysissub-optimality gappolicy constraintsdriftDri-MED algorithm
Authors
Udvas Das, Waris Radji, Debabrota Basu, Odalric-Ambrym Maillard
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 $\boldsymbolπ_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 $\tilde{\mathcal O}\left(\fracκ{\tildeΔ}d^2(\log(T)\right)$, where $\tildeΔ$ 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 $\tilde{\mathcal{O}}(d)$ expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.