Poster
Sparsity-Agnostic Linear Bandits with Adaptive Adversaries
Tianyuan Jin · Kyoungseok Jang · Nicolò Cesa-Bianchi
West Ballroom A-D #7206
Abstract:
We study stochastic linear bandits where, in each round, the learner receives a set of actions (i.e., feature vectors), from which it chooses an element and obtains a stochastic reward. The expected reward is a fixed but unknown linear function of the chosen action. We study \emph{sparse} regret bounds, that depend on the number of non-zero coefficients in the linear reward function. Previous works focused on the case where is known, or the action sets satisfy additional assumptions. In this work, we obtain the first sparse regret bounds that hold when is unknown and the action sets are adversarially generated. Our techniques combine online to confidence set conversions with a novel randomized model selection approach over a hierarchy of nested confidence sets. When is known, our analysis recovers state-of-the-art bounds for adversarial action sets. We also show that a variant of our approach, using Exp3 to dynamically select the confidence sets, can be used to improve the empirical performance of stochastic linear bandits while enjoying a regret bound with optimal dependence on the time horizon.
Chat is not available.