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

arXiv:2609.23092v1 Announce Type: new 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 $\Omega(\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.

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 $\Omega(\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.

Machine Learning (cs.LG)

arXiv:2609.23092 [cs.LG]

(or arXiv:2609.23092v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.23092 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

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

Related coverage