Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

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\le 2^{d/2}$ candidate actions per time period, we (1) show that the minimax expected regret is $\Omega (\sqrt{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 $\sqrt{\log T}$ factors from previous analysis, and our information-theoretical lower bound also improves previous results by one $\sqrt{\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.

References in corpus (10)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Efficient Contextual Bandits in Non-stationary Worlds
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Best-Arm Identification in Linear Bandits
• Contextual Bandit Learning with Predictable Rewards
• Towards Instance Optimal Bounds for Best Arm Identification
• KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints

Cited by in corpus (4)

• A Simple Approach for Non-stationary Linear Bandits
• Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• The Elliptical Potential Lemma Revisited