The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits

Abstract

Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case setting, we analyse the asymptotic instance-dependent regret and show matching upper and lower bounds on what is achievable. Surprisingly, our results show that no algorithm based on optimism or Thompson sampling will ever achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even in very simple cases. This is a disturbing result because these techniques are standard tools that are widely used for sequential optimisation. For example, for generalised linear bandits and reinforcement learning.

arXiv comment13 pages

References in corpus (5)

• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Thompson Sampling for 1-Dimensional Exponential Family Bandits
• Refined Lower Bounds for Adversarial Bandits
• Infomax strategies for an optimal balance between exploration and exploitation
• Online Learning with Gaussian Payoffs and Side Observations

Cited by in corpus (4)

• Optimal Best-arm Identification in Linear Bandits
• Differentiable Linear Bandit Algorithm
• Contextual Bandits with Side-Observations
• Learning to Actively Learn: A Robust Approach