Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
  In this paper, we propose a new multi-objective contextual multi-armed bandit
(MAB) problem with two objectives, where one of the objectives dominates the
other objective. Unlike single-objective MAB problems in which the learner
obtains a random scalar reward for each arm it selects, in the proposed
problem, the learner obtains a random reward vector, where each component of
the reward vector corresponds to one of the objectives and the distribution of
the reward depends on the context that is provided to the learner at the
beginning of each round. We call this problem contextual multi-armed bandit
with a dominant objective (CMAB-DO). In CMAB-DO, the goal of the learner is to
maximize its total reward in the non-dominant objective while ensuring that it
maximizes its total reward in the dominant objective. In this case, the optimal
arm given a context is the one that maximizes the expected reward in the
non-dominant objective among all arms that maximize the expected reward in the
dominant objective. First, we show that the optimal arm lies in the Pareto
front. Then, we propose the multi-objective contextual multi-armed bandit
algorithm (MOC-MAB), and define two performance measures: the 2-dimensional
(2D) regret and the Pareto regret. We show that both the 2D regret and the
Pareto regret of MOC-MAB are sublinear in the number of rounds. We also compare
the performance of the proposed algorithm with other state-of-the-art methods
in synthetic and real-world datasets. The proposed model and the algorithm have
a wide range of real-world applications that involve multiple and possibly
conflicting objectives ranging from wireless communication to medical diagnosis
and recommender systems.
