An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits

Abstract

In the contextual linear bandit setting, algorithms built on the optimism principle fail to exploit the structure of the problem and have been shown to be asymptotically suboptimal. In this paper, we follow recent approaches of deriving asymptotically optimal algorithms from problem-dependent regret lower bounds and we introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We build on a reformulation of the lower bound, where context distribution and exploration policy are decoupled, and we obtain an algorithm robust to unbalanced context distributions. Then, using an incremental primal-dual approach to solve the Lagrangian relaxation of the lower bound, we obtain a scalable and computationally efficient algorithm. Finally, we remove forced exploration and build on confidence intervals of the optimization problem to encourage a minimum level of exploration that is better adapted to the problem structure. We demonstrate the asymptotic optimality of our algorithm, while providing both problem-dependent and worst-case finite-time regret guarantees. Our bounds scale with the logarithm of the number of arms, thus avoiding the linear dependence common in all related prior works. Notably, we establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits. Finally, we verify that our algorithm obtains better empirical performance than state-of-the-art baselines.

arXiv commentTo appear at NeurIPS 2020. V2: clarified dependencies in the worst-case regret bound

References in corpus (10)

• Thompson Sampling for Contextual Bandits with Linear Payoffs
• A Survey on Practical Applications of Multi-Armed and Contextual Bandits
• Online Learning: A Modern Introduction Using Convex Optimization
• Optimal Best Arm Identification with Fixed Confidence
• Bounded Regret for Finite-Armed Structured Bandits
• Sequential Transfer in Multi-armed Bandit with Finite Set of Models
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• Exploration-Exploitation in Constrained MDPs
• Gamification of Pure Exploration for Linear Bandits
• Structure Adaptive Algorithms for Stochastic Bandits

Cited by in corpus (7)

• An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
• Asymptotically Optimal Information-Directed Sampling
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• High-Dimensional Experimental Design and Kernel Bandits
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
• Experimental Design for Regret Minimization in Linear Bandits
• Chernoff Sampling for Active Testing and Extension to Active Regression