Combinatorial Neural Bandits
Taehyun Hwang Kyuwook Chai Min-hwan Oh
We consider a contextual combinatorial bandit problem where in each round a
learning agent selects a subset of arms and receives feedback on the selected
arms according to their scores. The score of an arm is an unknown function of
the arm's feature. Approximating this unknown score function with deep neural
networks, we propose algorithms: Combinatorial Neural UCB ($\texttt{CN-UCB}$)
and Combinatorial Neural Thompson Sampling ($\texttt{CN-TS}$). We prove that
$\texttt{CN-UCB}$ achieves $\tilde{\mathcal{O}}(\tilde{d} \sqrt{T})$ or
$\tilde{\mathcal{O}}(\sqrt{\tilde{d} T K})$ regret, where $\tilde{d}$ is the
effective dimension of a neural tangent kernel matrix, $K$ is the size of a
subset of arms, and $T$ is the time horizon. For $\texttt{CN-TS}$, we adapt an
optimistic sampling technique to ensure the optimism of the sampled
combinatorial action, achieving a worst-case (frequentist) regret of
$\tilde{\mathcal{O}}(\tilde{d} \sqrt{TK})$. To the best of our knowledge, these
are the first combinatorial neural bandit algorithms with regret performance
guarantees. In particular, $\texttt{CN-TS}$ is the first Thompson sampling
algorithm with the worst-case regret guarantees for the general contextual
combinatorial bandit problem. The numerical experiments demonstrate the
superior performances of our proposed algorithms.