Skip to yearly menu bar Skip to main content


Poster

Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits

Avishek Ghosh · Abishek Sankararaman · Ramchandran Kannan

Keywords: [ Learning Theory and Statistics ] [ Decision Processes and Bandits ]


Abstract: We consider the problem of model selection for two popular stochastic linear bandit settings, and propose algorithms that adapts to the unknown problem complexity. In the first setting, we consider the KK armed mixture bandits, where the mean reward of arm i[K]i[K] is μi+αi,t,θμi+αi,t,θ, with αi,tRdαi,tRd being the known context vector and μi[1,1]μi[1,1] and θθ are unknown parameters. We define θθ as the problem complexity and consider a sequence of nested hypothesis classes, each positing a different upper bound on θθ. Exploiting this, we propose Adaptive Linear Bandit (ALB), a novel phase based algorithm that adapts to the true problem complexity, θθ. We show that ALB achieves regret scaling of ˜O(θT)˜O(θT), where θθ is apriori unknown. As a corollary, when θ=0θ=0, ALB recovers the minimax regret for the simple bandit algorithm without such knowledge of θθ. ALB is the first algorithm that uses parameter norm as model section criteria for linear bandits. Prior state of art algorithms achieve a regret of ˜O(LT)˜O(LT), where LL is the upper bound on θθ, fed as an input to the problem. In the second setting, we consider the standard linear bandit problem (with possibly an infinite number of arms) where the sparsity of θθ, denoted by dddd, is unknown to the algorithm. Defining dd as the problem complexity (similar to Foster et. al '19), we show that ALB achieves ˜O(dT)˜O(dT) regret, matching that of an oracle who knew the true sparsity level. This methodology is then extended to the case of finitely many arms and similar results are proven. We further verify through synthetic and real-data experiments that the performance gains are fundamental and not artifacts of mathematical bounds. In particular, we show 1.531.53x drop in cumulative regret over non-adaptive algorithms.

Chat is not available.