# Combinatorial Multi-Objective Multi-Armed Bandit Problem

arXiv: https://arxiv.org/abs/1803.04039 · HTML: https://mlsanity.com/paper/1803.04039/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2018.

## Built on by (most cited first, 2 of 2)

- [Expected Scalarised Returns Dominance: A New Solution Concept for Multi-Objective Decision Making](https://mlsanity.com/paper/2106.01048/) (2021)
- [Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm](https://mlsanity.com/paper/2506.13125/) (2025)

## Abstract (arXiv)

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 L3 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.