A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem
This work addresses sampling inefficiency in high-dimensional bandit problems for applications like recommendation systems, though it is incremental as it builds on prior methods by simplifying assumptions.
The paper tackles the sparse linear contextual bandit problem by using a perturbed adversary with small random perturbations, achieving a regret bound of O(√(kT log d)) even when the ambient dimension d is much larger than the time horizon T.
We investigate the sparse linear contextual bandit problem where the parameter $θ$ is sparse. To relieve the sampling inefficiency, we utilize the "perturbed adversary" where the context is generated adversarilly but with small random non-adaptive perturbations. We prove that the simple online Lasso supports sparse linear contextual bandit with regret bound $\mathcal{O}(\sqrt{kT\log d})$ even when $d \gg T$ where $k$ and $d$ are the number of effective and ambient dimension, respectively. Compared to the recent work from Sivakumar et al. (2020), our analysis does not rely on the precondition processing, adaptive perturbation (the adaptive perturbation violates the i.i.d perturbation setting) or truncation on the error set. Moreover, the special structures in our results explicitly characterize how the perturbation affects exploration length, guide the design of perturbation together with the fundamental performance limit of perturbation method. Numerical experiments are provided to complement the theoretical analysis.