Bimodal Bandits: Max-Mean Regret Minimization

This paper considers the problem of multi-armed bandits where reward of the arms have a bi-modal Gaussian mixture distribution. We propose a new notion of regret called max-min regret, in which each arm's merit is ranked according to its maximum mean across the mixture components. To achieve sublinear max-mean regret, we propose an upper confidence bound-type algorithm customized to the mixture model setting and a benchmark epsilon-greedy algorithm. We present numerical results, highlighting the cumulative regret of the proposed algorithms against conventional methods devised for unimodal distributions. We also numerically study the efficacy of modeling a bi-modal distribution versus an unimodal distribution when the true distribution has 4 mixture components. We also discuss the limitations of the proposed methods on related metrics and motivate directions for future research.