Technical Summary: Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

Problem Definition

The paper addresses the Multi-Objective Multi-Armed Bandit (MOMAB) problem, specifically focusing on Pareto Set Identification (PSI). Unlike standard single-objective bandit problems that aim to maximize cumulative reward (regret minimization) or identify a single best arm, MOMAB involves optimizing multiple, potentially conflicting objectives simultaneously. In this setting, no single arm is optimal across all criteria; instead, there exists a set of Pareto optimal arms ($P^\star$) representing the optimal trade-offs.

The specific challenge tackled is the Anytime PSI formulation. While existing literature has extensively covered fixed-budget (minimizing error after a set number of samples) and fixed-confidence (minimizing samples to reach a target accuracy) settings, there is a gap in algorithms that can provide a valid, continuously updated estimate of the Pareto set after every observation without a predefined stopping rule. This is critical for real-world applications where decision-makers need to monitor progress and potentially terminate experiments dynamically based on confidence levels rather than rigid resource constraints.

Methodology: Top-Two Pareto Front Thompson Sampling (TTPFTS)

The authors introduce Top-Two Pareto Front Thompson Sampling (TTPFTS), the first Bayesian anytime algorithm designed for the MOMAB PSI problem. The algorithm extends the principles of Top-Two Thompson Sampling (TTTS) from single-objective best-arm identification to the multi-objective domain.

Core Mechanism

Instead of scalarizing objectives with a preference vector (which would reduce the problem to a single objective), TTPFTS operates directly on the Pareto fronts. At each time step $t$:

1. Posterior Sampling: The algorithm samples mean reward vectors $\tilde{\theta}^{(t)}_a$ for all $K$ arms from their respective posterior distributions conditioned on the history $H(t-1)$.
2. Front Identification: Based on these samples, it identifies the First Pareto Front ($F^\star_1$), consisting of arms that are not dominated by any other sampled arm.
3. Stochastic Selection: A Bernoulli trial with probability $\rho$ determines which front to explore:
   • With probability $\rho$: An arm is selected uniformly at random from the First Front ($F^\star_1$). This focuses on verifying arms currently believed to be optimal.
   • With probability $1-\rho$: The algorithm removes $F^\star_1$ and identifies the Second Pareto Front ($F^\star_2$) from the remaining arms. An arm is then selected uniformly at random from $F^\star_2$. This promotes exploration of the most promising suboptimal arms (challengers) to test if they have been underestimated or to solidify their suboptimal status.
4. Update: The selected arm is pulled, the reward is observed, and the history is updated. The algorithm maintains a recommendation set $\hat{P}^\star_t$ (the Pareto set of the posterior means) at all times.

Theoretical Guarantees

The paper provides a proof of asymptotic correctness (Theorem 1). Under standard assumptions (finite arms, consistent posteriors, strict Pareto gaps, and sufficient exploration), the algorithm's estimate $\hat{P}^\star_t$ converges to the true Pareto set $P^\star$ with probability 1 as $t \to \infty$. The proof relies on Lemma 1, which establishes that TTPFTS ensures infinite exploration of all arms almost surely, preventing any arm from being permanently "frozen" out of the sampling process.

Key Contributions

1. First Anytime Bayesian Algorithm for MOMAB PSI: TTPFTS fills the gap in the literature regarding anytime algorithms for Pareto set identification, offering a flexible alternative to fixed-budget and fixed-confidence approaches.
2. Novel Uncertainty Quantification (UQ) Metric: The authors introduce a ground-truth-independent metric to estimate the algorithm's confidence in its current Pareto prediction. This metric calculates the Bhattacharyya overlap between the posterior densities of arms in the estimated first front ($\hat{P}^\star_1$) and the second front ($\hat{P}^\star_2$).
   • High overlap indicates high uncertainty (difficulty distinguishing optimal from suboptimal arms).
   • Low overlap indicates high confidence (clear separation between fronts).
   • This metric serves as a real-time proxy for identification performance, enabling dynamic stopping criteria.
3. Real-World Application in Molecular Discovery: The algorithm is validated in a challenging, ultra-large synthesis-on-demand molecular library setting (94 million candidates), demonstrating its utility in identifying molecules that optimize conflicting properties (Structural Similarity and LogP).

Empirical Results

Synthetic Benchmarks

TTPFTS was evaluated against state-of-the-art fixed-budget algorithms (Successive Rejects and Successive Halving variants of Empirical Gap Elimination, EGE) across eight synthetic environments with varying Pareto front geometries and dimensions.

• Performance: TTPFTS consistently outperformed Uniform Sampling and the EGE-SH algorithm. It achieved performance parity with EGE-SR (the strongest fixed-budget baseline) across all environments, despite the stricter anytime constraint.
• Scalability: In environments with large action spaces (e.g., $K=200$), TTPFTS significantly outperformed EGE variants, suggesting that its posterior-driven allocation is more effective than rigid gap-based elimination in large-scale problems.
• Robustness: The algorithm performed well even with weak prior assumptions (uniform priors).

Molecular Discovery Case Study

In the exploration of a 94-million compound library:

• Efficiency: TTPFTS identified molecules perfectly coinciding with the ground-truth Pareto front (52 molecules) while evaluating only 0.05% of the database.
• Comparison: It significantly outperformed both Random Search (which found zero optimal molecules) and the state-of-the-art active learning method MolPAL.
• Uncertainty Correlation: The proposed UQ metric showed a strong negative correlation with the Jaccard metric (accuracy). As the algorithm improved its Pareto set estimate, the uncertainty metric decreased, validating its use as a reliable, ground-truth-free indicator of convergence.

Significance and Claims

The paper claims that TTPFTS provides a robust methodology for monitoring learning progress in complex, multi-objective settings without requiring knowledge of the true Pareto front. By combining an anytime exploration strategy with a novel uncertainty quantification metric, the work transforms the Pareto set identification problem from a static sampling task into a dynamic decision-support system.

The authors emphasize that this approach allows decision-makers to:

• Dynamically determine when the Pareto front is sufficiently resolved to terminate an experiment.
• Optimize the trade-off between computational resources and discovery confidence.
• Apply these benefits to real-world scenarios like drug discovery, where exhaustive screening is infeasible and preferences may not be known a priori.

The paper remains modest regarding finite-time error bounds, acknowledging that while asymptotic correctness is proven, deriving explicit finite-time rates remains a challenge similar to that faced by standard Thompson Sampling in the past. However, the authors argue that the combination of asymptotic soundness, strong empirical performance, and the practical utility of the uncertainty metric establishes TTPFTS as a significant advancement in multi-objective decision-making.