Stochastic Linear Bandits with Parameter Noise

We study the stochastic linear bandits with parameter noise model, in which the reward of action $a$ is $a^\top \theta$ where $\theta$ is sampled i.i.d. We show a regret upper bound of $\widetilde{O} (\sqrt{d T \log(K/\delta) \sigma^2_{\max}})$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $\sigma^2_{\max}$ is the maximal variance of the reward for any action. We further provide a lower bound of $\widetilde{\Omega} (d \sqrt{T \sigma_{\max}^2})$ which is tight (up to logarithmic factors) whenever $\log K \approx d$. For more specific action sets, $\ell_p$ unit balls with $p \leq 2$ and dual norm $q$, we show that the minimax regret is $\widetilde{\Theta} (\sqrt{dT \sigma_q^2})$, where $\sigma_q^2$ is a variance-dependent quantity that is always at most $4$. This is in contrast to the minimax regret attainable for such sets in the classic additive noise model where the regret is of order $d \sqrt{T}$. Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.

Many modern AI systems must learn by trial and error while making decisions under uncertainty. Examples include recommendation systems, online advertising, and adaptive medical treatments. A common mathematical framework for studying this problem is called a “linear bandit,” where the system repeatedly chooses actions and learns from feedback. Most previous research assumes that the world stays essentially fixed, and that uncertainty comes only from noisy or imperfect observations. In our work, we study a different and often more realistic situation: the world itself may vary from one interaction to the next. For example, a user’s preferences, interests, or mood may naturally fluctuate over time. We develop new theoretical guarantees that characterize how difficult learning becomes under this type of variability. For several important classes of decision problems, we show that learning can actually be significantly easier than in the standard setting. We also show that a surprisingly simple algorithm is enough to achieve near-optimal performance. Our results improve the theoretical understanding of learning under changing environments and may help guide the design of more reliable adaptive decision-making systems.