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.

arXiv comment26 pages, 2 tables, 5 figures. In ICLR 2021

References in corpus (22)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Weight Uncertainty in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Noisy Networks for Exploration
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Deep Exploration via Bootstrapped DQN
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Finite-Time Analysis of Kernelised Contextual Bandits
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems
• Towards Understanding the Spectral Bias of Deep Learning
• Bootstrapped Thompson Sampling and Deep Exploration
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• A Tutorial on Thompson Sampling
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Scalable Generalized Linear Bandits: Online Computation and Hashing
• Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization
• Deep Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matching

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