  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.
