  In this paper, we introduce the COmbinatorial Multi-Objective Multi-Armed
Bandit (COMO-MAB) problem that captures the challenges of combinatorial and
multi-objective online learning simultaneously. In this setting, the goal of
the learner is to choose an action at each time, whose reward vector is a
linear combination of the reward vectors of the arms in the action, to learn
the set of super Pareto optimal actions, which includes the Pareto optimal
actions and actions that become Pareto optimal after adding an arbitrary small
positive number to their expected reward vectors. We define the Pareto regret
performance metric and propose a fair learning algorithm whose Pareto regret is
$O(N L^3 \log T)$, where $T$ is the time horizon, $N$ is the number of arms and
$L$ is the maximum number of arms in an action. We show that COMO-MAB has a
wide range of applications, including recommending bundles of items to users
and network routing, and focus on a resource-allocation application for
multi-user communication in the presence of multidimensional performance
metrics, where we show that our algorithm outperforms existing MAB algorithms.
