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

• URL: http://arxiv.org/abs/2604.07096v1
• Date: Wed, 08 Apr 2026 13:48:54 GMT
• Title: Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?
• Abstract summary: Multi-objective bandits have attracted increasing attention because of their broad applicability and elegance, where the reward of each arm is a multi-dimensional vector rather than a scalar.<n>A long-standing question in this area is whether performance is harder to optimize because of this added complexity.<n>We develop a new algorithm that achieves the minimum marginal regret of order (fracKlog Tgdagger)
• Score: 4.452583096196013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-objective bandits have attracted increasing attention because of their broad applicability and mathematical elegance, where the reward of each arm is a multi-dimensional vector rather than a scalar. This naturally introduces Pareto order relations and Pareto regret. A long-standing question in this area is whether performance is fundamentally harder to optimize because of this added complexity. A recent surprising result shows that, in the adversarial setting, Pareto regret is no larger than classical regret; however, in the stochastic setting, where the regret notion is different, the picture remains unclear. In fact, existing work suggests that Pareto regret in the stochastic case increases with the dimensionality. This controversial yet subtle phenomenon motivates our central question: \emph{are multi-objective bandits actually harder than single-objective ones?} We answer this question in full by showing that, in the stochastic setting, Pareto regret is in fact governed by the maximum sub-optimality gap \(g^\dagger\), and hence by the minimum marginal regret of order \(Ω(\frac{K\log T}{g^\dagger})\). We further develop a new algorithm that achieves Pareto regret of order \(O(\frac{K\log T}{g^\dagger})\), and is therefore optimal. The algorithm leverages a nested two-layer uncertainty quantification over both arms and objectives through upper and lower confidence bound estimators. It combines a top-two racing strategy for arm selection with an uncertainty-greedy rule for dimension selection. Together, these components balance exploration and exploitation across the two layers. We also conduct comprehensive numerical experiments to validate the proposed algorithm, showing the desired regret guarantee and significant gains over benchmark methods.

Related papers

• Optimal Regret for Single Index Bandits [10.765936017864766]
  We study the $textitsingle-index bandit$ problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts.<n>We establish the optimal regret for general single-index bandits.
  arXiv  Detail & Related papers  (2026-05-10T10:13:24Z)
• A single algorithm for both restless and rested rotting bandits [65.63283411693489]
  We introduce a novel algorithm, Rotting Adaptive Window UCB, that achieves near-optimal regret in both rotting rested and restless bandit.<n>This is in striking contrast with previous negative results showing that no algorithm can achieve similar results as soon as rewards are allowed to increase.
  arXiv  Detail & Related papers  (2026-04-23T08:48:52Z)
• Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses [24.77915694853164]
  In adversarial multi-armed bandits, two performance measures are commonly used: static regret and dynamic regret.<n>While optimal algorithms are known for each measure individually, there is no known algorithm achieving optimal bounds for both simultaneously.<n>We present an algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary.
  arXiv  Detail & Related papers  (2026-02-07T07:32:31Z)
• A conversion theorem and minimax optimality for continuum contextual bandits [64.9814493154015]
  We study the contextual continuum bandits problem, where the learner sequentially receives a side information vector and has to choose an action in a convex set.<n>The goal is to minimize all the underlying functions for the received contexts, leading to the contextual notion of regret.<n>We show that any algorithm achieving a sub-linear static regret can be extended to achieve a sub-linear contextual regret.
  arXiv  Detail & Related papers  (2024-06-09T10:12:08Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Pareto Regret Analyses in Multi-objective Multi-armed Bandit [22.17126026244685]
  We study optimality in multi-objective multi-armed bandit. We 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 settings simultaneously.
  arXiv  Detail & Related papers  (2022-12-01T21:44:27Z)
• A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
  This work addresses a version of the two-armed Bernoulli bandit problem where the sum of the means of the arms is one. We obtain the leading order terms of the minmax optimal regret and pseudoregret for this problem by associating each of them with a solution of a linear heat equation.
  arXiv  Detail & Related papers  (2022-02-11T17:03:18Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  We consider the Multi-Armed Bandit (MAB) problem, where an agent sequentially chooses actions and observes rewards for the actions it took. While the majority of algorithms try to minimize the regret, i.e., the cumulative difference between the reward of the best action and the agent's action, this criterion might lead to undesirable results. We suggest a new, more lenient, regret criterion that ignores suboptimality gaps smaller than some $epsilon$.
  arXiv  Detail & Related papers  (2020-08-10T08:30:52Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces.<n>A central theme here is the adaptive discretization of the action space, which gradually zooms in'' on the more promising regions.<n>We provide the first algorithm for adaptive discretization in the adversarial version, and derive instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-06-22T16:06:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.