  Balancing exploration and exploitation (EE) is a fundamental problem in
contex-tual bandit. One powerful principle for EE trade-off isOptimism in Face
of Uncer-tainty(OFU), in which the agent takes the action according to an upper
confidencebound (UCB) of reward. OFU has achieved (near-)optimal regret bound
for lin-ear/kernel contextual bandits. However, it is in general unknown how to
deriveefficient and effective EE trade-off methods for non-linearcomplex tasks,
suchas contextual bandit with deep neural network as the reward function. In
thispaper, we propose a novel OFU algorithm namedregularized OFU(ROFU). InROFU,
we measure the uncertainty of the reward by a differentiable function
andcompute the upper confidence bound by solving a regularized optimization
prob-lem. We prove that, for multi-armed bandit, kernel contextual bandit and
neuraltangent kernel bandit, ROFU achieves (near-)optimal regret bounds with
certainuncertainty measure, which theoretically justifies its effectiveness on
EE trade-off.Importantly, ROFU admits a very efficient implementation with
gradient-basedoptimizer, which easily extends to general deep neural network
models beyondneural tangent kernel, in sharp contrast with previous OFU
methods. The em-pirical evaluation demonstrates that ROFU works extremelywell
for contextualbandits under various settings.
