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

Changkun Guan; Mengfan Xu

cs.LGSep 19, 2026

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

Authors: Changkun Guan, Mengfan Xu

Organizations: H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology · Mechanical and Industrial Engineering University of Massachusetts Amherst

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.

Figures & tables

Panel of Figure 1 — Figure 1: The zero-loss construction. The first block is identical in both cases; the remaining rewards determine whether group $A$ or group $B$ contains the zero-loss coordinate and the arm with larger mean reward in the other coordinate.

Scalar method	Knows $L_{0}$ ?	$b$ in $\mathbb{E}[R_{T}^{\mathrm{fs}}]\lesssim\min\{U_{0},b\}$
Poly-INF	Yes	$\sqrt{KU_{0}}$
Modified EXP3	Yes	$\sqrt{KU_{0}\log(3K)}$
Gain-based EXP3	Yes / no	$(K\log K)^{1/3}V^{2/3}$ with $V=U_{0}$ / $T$
Reward-doubling Poly-INF (Ours)	No	$\mathbf{\sqrt{KU_{0}}}$
Poly-INF with $B=T$	No	$\sqrt{KT}$
EXP3.P and adversarial MO-KS	Either	$\sqrt{KT\log(KT)}$

Table 1: Proved upper bounds for a coordinate

d^{\prime}

fixed before play.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

v_{I_{s},s}\leftarrow-\frac{1}{\lambda}\log\!\left(1-\frac{\lambda g_{I_{s},s}}{p_{I_{s},s}}\right).

Appendix

Algorithm 1

\textnormal{{Poly-INF}}(B)

with a logarithmic reward estimator

Explore similar work

Apr 8, 2026

Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?

Multi-objective bandits have attracted increasing attention for their broad applicability, with

d

-dimensional reward vectors inducing Pareto regret. There has been a subtle debate over whether this added structure makes the problem fundamentally harder than single-objective bandits. We answer this by showing that, in terms of Pareto regret, it is surprisingly no harder: Pareto regret scales inversely with

g^\dagger

, the largest objective-wise suboptimality gap, and thus matches the smallest objective-wise classical regret. We formalize this idea via a novel method with upper and lower confidence-bound estimators for every arm-objective pair. It uses top-two races to compare arms within each objective and an uncertainty-greedy rule to allocate exploration toward the largest objective-wise gap

g^\dagger

, until the corresponding Pareto-optimal arm is committed to. We prove that it achieves Pareto regret of

O(\nicefrac{\log T}{g^\dagger})

, where

T

is the horizon, with \emph{no dependence on

d

}. A matching lower bound of

Ω(\nicefrac{\log T}{g^\dagger})

implies optimality. We evaluate the method on synthetic and real-world datasets, confirming the theory and achieving order-of-magnitude reductions in Pareto regret over baselines. Real-world results further show that our method commits to a Pareto optimal arm, possibly at the cost of empirical fairness, suggesting a potential hardness absent in single-objective bandits.

Changkun Guan, Mengfan Xu

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · Mechanical and Industrial Engineering, University of Massachusetts Amherst

Multi-Armed Bandits

Ask PDF

Sep 29, 2026

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

Jul 28, 2026

Top- $k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection

We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of

k

arms and observes their

d

-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an

α

-approximate hypervolume regret with respect to the best size-

k

subset achievable in hindsight, where

α= 1 - 1/e

reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce THV-UCB, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound

\tilde{O}(d\sqrt{nkT})

that holds on every instance, together with a gap-dependent bound

\tilde{O}(nk^{2.5}/Δ_{\min})

that becomes polylogarithmic in

T

once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.

Nicolas Gutowski, Fabien Chhel, Alexandre Letard +1

Université d’Angers, LERIA, SFR MATHSTIC, Angers, France · ESEO, ERIS, Angers, France · AlphaEdge, Saint-Barthélémy-d’Anjou, France +1

Multi-Armed Bandits Combinatorial Multi-Armed Bandits Multi-Objective Optimization Pareto Optimization

Ask PDF

Abstract

Explore similar work

Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

Top-kkk Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection

Top- $k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection