Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

• URL: http://arxiv.org/abs/2606.18785v1
• Date: Wed, 17 Jun 2026 07:56:51 GMT
• Title: Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits
• Abstract summary: We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem.<n>We demonstrate its practical utility in a challenging multi-objective molecular discovery setting.<n>We complement these empirical findings with a theoretical proof of the algorithm's correctness.
• Score: 0.37515646463759694
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Identifying Pareto optimal solutions is critical to support multi-objective decision-making. We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem, taking a Bayesian approach: Top-Two Pareto Front Thompson Sampling (TTPFTS). We benchmark TTPFTS against state-of-the-art fixed-budget Pareto Set Identification algorithms on synthetic environments. Next, we demonstrate its practical utility in a challenging multi-objective molecular discovery setting by efficiently exploring an ultra-large synthesis-on-demand molecular library. Furthermore, we introduce a novel uncertainty quantification metric that estimates our algorithm's confidence in the predicted Pareto set. We demonstrate that this metric effectively proxies true performance, yielding a robust methodology for monitoring learning progress in complex settings. Finally, we complement these empirical findings with a theoretical proof of the algorithm's asymptotic correctness.

Related papers

• Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation [49.86232017439639]
  We introduce Multi-Output Augmented Behavioral Cloning (MA-BC)<n>MA-BC partitions divergent expert data while pooling state-action pairs where no behavior conflict is observed.<n>We establish a novel lower bound for multi-objective imitation learning, demonstrating that MA-BC is minimax optimal.
  arXiv  Detail & Related papers  (2026-05-12T11:49:08Z)
• Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach [25.475842473998906]
  We reformulate max-min multi-objective reinforcement learning as a two-player zero-sum regularized continuous game.<n>Our approach simplifies the policy update while ensuring global last-iterate convergence.<n>Our implementation for deep reinforcement learning significantly outperforms previous baselines in many MORL environments.
  arXiv  Detail & Related papers  (2025-10-23T05:39:26Z)
• Constrained Pareto Set Identification with Bandit Feedback [10.967572582187014]
  Given a $K$-armed bandit with unknown means, the goal is to identify the set of arms whose mean is not uniformly worse than that of another arm.<n>Our focus lies in fixed-confidence identification, for which we introduce an algorithm that significantly outperforms racing-like algorithms.
  arXiv  Detail & Related papers  (2025-06-09T18:29:28Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Divide and Conquer: Provably Unveiling the Pareto Front with Multi-Objective Reinforcement Learning [5.897578963773195]
  We introduce Iterated Pareto Referent optimisation (IPRO)<n>IPRO decomposes finding the Pareto front into a sequence of constrained single-objective problems.<n>By leveraging problem-specific single-objective solvers, our approach holds promise for applications beyond multi-objective reinforcement learning.
  arXiv  Detail & Related papers  (2024-02-11T12:35:13Z)
• Adaptive Algorithms for Relaxed Pareto Set Identification [12.326452468513228]
  We revisit the fixed-confidence identification of the Pareto optimal set in a multi-objective multi-armed bandit model. We propose a single sampling strategy, called Adaptive Pareto Exploration, that can be used in conjunction with different stopping rules. We analyze the sample complexity of these different combinations, quantifying in particular the reduction in sample complexity.
  arXiv  Detail & Related papers  (2023-07-01T20:43:12Z)
• Pareto Navigation Gradient Descent: a First-Order Algorithm for Optimization in Pareto Set [17.617944390196286]
  Modern machine learning applications, such as multi-task learning, require finding optimal model parameters to trade-off multiple objective functions. We propose a first-order algorithm that approximately solves OPT-in-Pareto using only gradient information.
  arXiv  Detail & Related papers  (2021-10-17T04:07:04Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.