Markovian Experimental Design under Concept Drift

We study how to optimally select training samples in the presence of concept drift. We propose a Markovian experimental design framework, in which a learner sequentially collects samples and re-estimates a model through Bayesian linear regression. We show that, when model drift is governed by an unknown mean fixed-point coupled with Gaussian deviations, model posterior estimates are determined by a Kalman filter and the system is asymptotically stable. We also show that the steady-state model posterior can be computed as the solution of the so-called Discrete Algebraic Riccati Equation (DARE), and that D-optimal steady-state and myopic sample selection policies can be computed by solving tractable convex optimization problems. We do so by characterizing the curvature of the DARE solution, even though the latter generally has no closed form. Finally, we show that our approach generalizes to the non-linear model setting by replacing the Kalman filter with an extended Kalman filter.