Lexicographic Multiarmed Bandit
This work addresses a specific challenge in multiobjective decision-making for learners in bandit problems, but it is incremental as it builds on existing multiarmed bandit frameworks with new regret definitions and settings.
The paper tackles the problem of multiobjective multiarmed bandit learning with lexicographically ordered objectives, where the learner aims to select lexicographic optimal arms without prior knowledge of reward distributions, and shows that the proposed algorithms achieve uniformly bounded or sublinear regret in different settings.
We consider a multiobjective multiarmed bandit problem with lexicographically ordered objectives. In this problem, the goal of the learner is to select arms that are lexicographic optimal as much as possible without knowing the arm reward distributions beforehand. We capture this goal by defining a multidimensional form of regret that measures the loss of the learner due to not selecting lexicographic optimal arms, and then, consider two settings where the learner has prior information on the expected arm rewards. In the first setting, the learner only knows for each objective the lexicographic optimal expected reward. In the second setting, it only knows for each objective near-lexicographic optimal expected rewards. For both settings we prove that the learner achieves expected regret uniformly bounded in time. The algorithm we propose for the second setting also attains bounded regret for the multiarmed bandit with satisficing objectives. In addition, we also consider the harder prior-free case, and show that the learner can still achieve sublinear in time gap-free regret. Finally, we experimentally evaluate performance of the proposed algorithms in a variety of multiobjective learning problems.