Neural Thompson Sampling

Abstract

Thompson Sampling (TS) is one of the most effective algorithms for solving contextual multi-armed bandit problems. In this paper, we propose a new algorithm, called Neural Thompson Sampling, which adapts deep neural networks for both exploration and exploitation. At the core of our algorithm is a novel posterior distribution of the reward, where its mean is the neural network approximator, and its variance is built upon the neural tangent features of the corresponding neural network. We prove that, provided the underlying reward function is bounded, the proposed algorithm is guaranteed to achieve a cumulative regret of $\mathcal{O}(T^{1/2})$, which matches the regret of other contextual bandit algorithms in terms of total round number $T$. Experimental comparisons with other benchmark bandit algorithms on various data sets corroborate our theory.

26 pages, 2 tables, 5 figures. In ICLR 2021

References in corpus (6)

• Weight Uncertainty in Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Bootstrapped Thompson Sampling and Deep Exploration
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Scalable Generalized Linear Bandits: Online Computation and Hashing

Cited by in corpus (10)

• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits
• Graph Neural Bandits
• Batched Bayesian optimization by maximizing the probability of including the optimum
• Optimal Order Simple Regret for Gaussian Process Bandits
• Neural Bandit with Arm Group Graph
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching
• Quantifying Epistemic Uncertainty in Deep Learning
• Neural Active Learning with Performance Guarantees
• Neural Contextual Bandits without Regret