Pareto Regret Analyses in Multi-objective Multi-armed Bandit
This work addresses the challenge of optimizing multiple objectives simultaneously in bandit problems, which is relevant for applications like resource allocation and recommendation systems, and it extends existing analyses to adversarial settings, though it builds incrementally on prior stochastic frameworks.
The paper tackles the problem of Pareto optimality in multi-objective multi-armed bandits by formulating an adversarial setting and defining Pareto regrets that apply to both stochastic and adversarial contexts, without relying on scalarization functions. It presents new algorithms that are shown to be optimal in adversarial settings and nearly optimal up to a logarithmic factor in stochastic settings, as supported by established upper and lower bounds on Pareto regrets.
We study Pareto optimality in multi-objective multi-armed bandit by providing a formulation of adversarial multi-objective multi-armed bandit and defining its Pareto regrets that can be applied to both stochastic and adversarial settings. The regrets do not rely on any scalarization functions and reflect Pareto optimality compared to scalarized regrets. We also present new algorithms assuming both with and without prior information of the multi-objective multi-armed bandit setting. The algorithms are shown optimal in adversarial settings and nearly optimal up to a logarithmic factor in stochastic settings simultaneously by our established upper bounds and lower bounds on Pareto regrets. Moreover, the lower bound analyses show that the new regrets are consistent with the existing Pareto regret for stochastic settings and extend an adversarial attack mechanism from bandit to the multi-objective one.