Clustered Bandits
  We consider a multi-armed bandit setting that is inspired by real-world
applications in e-commerce. In our setting, there are a few types of users,
each with a specific response to the different arms. When a user enters the
system, his type is unknown to the decision maker. The decision maker can
either treat each user separately ignoring the previously observed users, or
can attempt to take advantage of knowing that only few types exist and cluster
the users according to their response to the arms. We devise algorithms that
combine the usual exploration-exploitation tradeoff with clustering of users
and demonstrate the value of clustering. In the process of developing
algorithms for the clustered setting, we propose and analyze simple algorithms
for the setup where a decision maker knows that a user belongs to one of few
types, but does not know which one.
