Stochastic Linear Bandits with Parameter Noise
Abstract
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 $\tO \brk{\sqrt{d T \logKdelta \sigmax}}$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $\sigmax$ is the maximal variance of the reward for any action.
We further provide a lower bound of $\tOmega \brk{d \sqrt{T \sigmax}}$ which is tight (up to logarithmic factors) whenever $\log \brk{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 $\tTheta \brk{\sqrt{dT \vsigq}}$, where $\vsigq$ 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.
We show a regret upper bound of $\tO \brk{\sqrt{d T \logKdelta \sigmax}}$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $\sigmax$ is the maximal variance of the reward for any action.
We further provide a lower bound of $\tOmega \brk{d \sqrt{T \sigmax}}$ which is tight (up to logarithmic factors) whenever $\log \brk{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 $\tTheta \brk{\sqrt{dT \vsigq}}$, where $\vsigq$ 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.
