The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

In adversarial multi-objective bandits, each arm’s reward is a vector chosen by an adversary, and performance is measured by Pareto regret. Measure how easy a coordinate is by the smallest cumulative loss of any arm on it. Earlier work suggested that an easier coordinate can reduce Pareto regret. In practice, though, the learner may not know which coordinate is the easy one.

Negative result. Without that knowledge, a smaller cumulative loss does not improve the worst-case order of Pareto regret. For at least 4 arms, at least 6 rounds, and at least 2 coordinates, we prove a minimax lower bound of Ω(min{T − L₀, √(K(T − L₀))}) on expected Pareto regret, where K is the number of arms, T the number of rounds, and L₀ = min_d L_d is the smallest cumulative loss over all coordinates. The bound holds even when L₀ itself is known.

Positive result. Coordinates other than the easiest one can still achieve the optimal rate. When L₀ is known, running Poly-INF on a fixed coordinate gives a matching upper bound. When it is unknown, a reward-doubling version of Poly-INF adapts to it and still attains the minimax rate, with no extra log T factor and no dependence on the number of coordinates.

This is the adversarial companion to our paper on stochastic multi-objective bandits.

Paper on arXiv