Multi-objective bandit algorithms with Chebyshev scalarization.

Abstract

In this paper we analyze several alternatives for Chebyshev scalarization in multi-objective bandit problems. The alternatives are evaluated on a reference bi-objective benchmark problem of Pareto frontier approximation. Performance is analyzed according to three measures: probability of selecting an optimal action, regret, and unfairness. The paper presents a new algorithm that improves the speed of convergence over previous proposals at least by one order of magnitude.