Combinatorial Multi-Objective Multi-Armed Bandit Problem
It addresses the problem of online decision-making with multiple objectives and combinatorial actions for applications such as recommendation systems and network routing, representing an incremental advancement in multi-armed bandit theory.
The paper tackles the COmbinatorial Multi-Objective Multi-Armed Bandit (COMO-MAB) problem, which combines combinatorial and multi-objective online learning, and proposes a fair learning algorithm achieving a Pareto regret of O(N L^3 log T), outperforming existing MAB algorithms in applications like resource allocation.
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.