  This paper studies regret minimization in a multi-armed bandit. It is well
known that side information, such as the prior distribution of arm means in
Thompson sampling, can improve the statistical efficiency of the bandit
algorithm. While the prior is a blessing when correctly specified, it is a
curse when misspecified. To address this issue, we introduce the assumption of
a random-effect model to bandits. In this model, the mean arm rewards are drawn
independently from an unknown distribution, which we estimate. We derive a
random-effect estimator of the arm means, analyze its uncertainty, and design a
UCB algorithm ReUCB that uses it. We analyze ReUCB and derive an upper bound on
its $n$-round Bayes regret, which improves upon not using the random-effect
structure. Our experiments show that ReUCB can outperform Thompson sampling,
without knowing the prior distribution of arm means.
