Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

2019/03/30 by Li, Yingkai, Wang, Yining, Zhou, Yuan
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1904.00242

Abstract

We study the linear contextual bandit problem with finite action sets. When the problem dimension is d, the time horizon is T, and there are n ≤ 2^d/2 candidate actions per time period, we (1) show that the minimax expected regret is Ω(√(dT (log T) (log n))) for every algorithm, and (2) introduce a Variable-Confidence-Level (VCL) SupLinUCB algorithm whose regret matches the lower bound up to iterated logarithmic factors. Our algorithmic result saves two √(log T) factors from previous analysis, and our information-theoretical lower bound also improves previous results by one √(log T) factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic T term is present in minimax regret. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.

Related

• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
• Stochastic Bandits with Linear Constraints
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits
• On the Minimax Regret for Linear Bandits in a wide variety of Action Spaces