Pareto regret in multi-objective bandits depends on unknown coordinate losses
The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits
Machine Learning
Summary
The paper studies how to measure and minimize regret when making repeated choices that have multiple outcomes, like scores in different categories. They focus on the toughest scenario where the outcomes are set adversarially and how knowing which outcome is easiest to optimize affects performance. Their main finding is that not knowing which outcome is easiest prevents better worst-case guarantees. However, they design algorithms that adapt to unknown information while still achieving optimal regret rates.
What this means in practice
- •For online decision makers: Optimize multi-criteria choices under adversarial conditions by adapting to unknown coordinate losses while ensuring near-optimal regret rates.
- •For automated trading teams: Design trading algorithms that handle multiple objectives without prior knowledge of which metric is easiest to optimize, maintaining strong worst-case performance.
A theory result. No direct application yet.
Authors
Changkun Guan, Mengfan Xu
Abstract
Adversarial multi-objective bandits hold the potential to help us optimize choices (arms) whose reward is a multidimensional vector chosen by an adversary and whose performance is measured by Pareto regret. We define loss as one minus reward and measure the easiness of a coordinate by the smallest cumulative loss of the arms on it, and call the coordinate easier when this quantity is smaller. Existing work suggests that in theory an easier coordinate may reduce Pareto regret. However, in practice, one may not know which coordinate is easier. On the negative side, we show that this lack of information eliminates the possibility: a smaller cumulative loss does not improve the worst-case order of Pareto regret. Precisely, let \(L_d\) be the smallest cumulative loss along coordinate $d$ over $T$ rounds. For \(K\ge4\) arms, \(T\ge6\) rounds, and at least 2 coordinates, we prove that the minimax expected Pareto regret is \(Ω(\min\{T-L_0,\sqrt{K(T-L_0)}\})\). It is monotonically decreasing in \(L_0\), even when \(L_0=\min_d L_d\) itself is known. On the positive side, this result motivates the possibility that other coordinates, not just the easy one, may suffice to attain the optimal rate of Pareto regret. When $L_0$ is known, we apply Poly-INF to a fixed coordinate and obtain an upper bound on Pareto regret that exhibits the same order and thus matches the lower bound. Without such knowledge, we develop a reward-doubling version of Poly-INF that adapts to this unknown quantity while still attaining the matching minimax rate. Another implication is that it has no extra \(\log T\) factor and is independent of the number of coordinates.