Norm-Agnostic Linear Bandits
This work addresses a practical limitation in linear bandits for applications like recommendation systems, offering a solution that is incremental by removing the need for parameter norm knowledge without sacrificing performance.
The paper tackles the problem of linear bandits requiring prior knowledge of the parameter norm bound, proposing novel algorithms that eliminate this need. The results show that the algorithms achieve regret bounds where the leading term is unaffected, with numerical experiments confirming they avoid catastrophic failures seen in standard methods when the norm bound is violated.
Linear bandits have a wide variety of applications including recommendation systems yet they make one strong assumption: the algorithms must know an upper bound $S$ on the norm of the unknown parameter $θ^*$ that governs the reward generation. Such an assumption forces the practitioner to guess $S$ involved in the confidence bound, leaving no choice but to wish that $\|θ^*\|\le S$ is true to guarantee that the regret will be low. In this paper, we propose novel algorithms that do not require such knowledge for the first time. Specifically, we propose two algorithms and analyze their regret bounds: one for the changing arm set setting and the other for the fixed arm set setting. Our regret bound for the former shows that the price of not knowing $S$ does not affect the leading term in the regret bound and inflates only the lower order term. For the latter, we do not pay any price in the regret for now knowing $S$. Our numerical experiments show standard algorithms assuming knowledge of $S$ can fail catastrophically when $\|θ^*\|\le S$ is not true whereas our algorithms enjoy low regret.