Norm-Agnostic Linear Bandits

Research output: Contribution to journalConference articlepeer-review


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 ||θ|| ≤ 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 ||θ|| ≤ S is not true whereas our algorithms enjoy low regret.

Original languageEnglish (US)
Pages (from-to)73-91
Number of pages19
JournalProceedings of Machine Learning Research
StatePublished - 2022
Event25th International Conference on Artificial Intelligence and Statistics, AISTATS 2022 - Virtual, Online, Spain
Duration: Mar 28 2022Mar 30 2022

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Norm-Agnostic Linear Bandits'. Together they form a unique fingerprint.

Cite this