Stochastic Linear Bandits with Parameter Noise
This work addresses the problem of optimizing regret in bandit algorithms with parameter noise for researchers in online learning and reinforcement learning, providing tight bounds and a simple solution.
The paper tackles the stochastic linear bandits problem with parameter noise, deriving a regret upper bound of O~(√(dT log(K/δ) σ²_max)) and a matching lower bound of Ω~(d√(T σ²_max)) for general action sets, and shows that for specific ℓ_p unit balls, the minimax regret is Θ~(√(dT σ²_q)), which is achievable with a simple explore-exploit algorithm.
We study the stochastic linear bandits with parameter noise model, in which the reward of action $a$ is $a^\top θ$ where $θ$ is sampled i.i.d. We show a regret upper bound of $\widetilde{O} (\sqrt{d T \log (K/δ) σ^2_{\max})}$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $σ^2_{\max}$ is the maximal variance of the reward for any action. We further provide a lower bound of $\widetildeΩ (d \sqrt{T σ^2_{\max}})$ 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Θ (\sqrt{dT σ^2_q)}$, where $σ^2_q$ 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.