Categorized Bandits
  We introduce a new stochastic multi-armed bandit setting where arms are
grouped inside ``ordered'' categories. The motivating example comes from
e-commerce, where a customer typically has a greater appetence for items of a
specific well-identified but unknown category than any other one. We introduce
three concepts of ordering between categories, inspired by stochastic dominance
between random variables, which are gradually weaker so that more and more
bandit scenarios satisfy at least one of them. We first prove
instance-dependent lower bounds on the cumulative regret for each of these
models, indicating how the complexity of the bandit problems increases with the
generality of the ordering concept considered. We also provide algorithms that
fully leverage the structure of the model with their associated theoretical
guarantees. Finally, we have conducted an analysis on real data to highlight
that those ordered categories actually exist in practice.
