  We study the stochastic contextual bandit problem, where the reward is
generated from an unknown function with additive noise. No assumption is made
about the reward function other than boundedness. We propose a new algorithm,
NeuralUCB, which leverages the representation power of deep neural networks and
uses a neural network-based random feature mapping to construct an upper
confidence bound (UCB) of reward for efficient exploration. We prove that,
under standard assumptions, NeuralUCB achieves $\tilde O(\sqrt{T})$ regret,
where $T$ is the number of rounds. To the best of our knowledge, it is the
first neural network-based contextual bandit algorithm with a near-optimal
regret guarantee. We also show the algorithm is empirically competitive against
representative baselines in a number of benchmarks.
