Research map / Bandits and online learning / Multi-armed bandits
Constrained Pareto Set Identification with Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces constrained Pareto Set Identification (cPSI/e-cPSI) with linear feasibility constraints in fixed-confidence bandits, proposing e-cAPE (UCB/LCB-based, near-optimal for explainable variant) and an asymptotically optimal Game-cPSI for the non-explainable case.
Problem
Identifying the Pareto Set of arms whose mean vectors satisfy known linear feasibility constraints in a multi-objective bandit, in the fixed-confidence setting, with optional explanations for rejected arms.
Approach
Jointly balances feasibility detection and Pareto dominance testing using confidence bounds on dominance margins and distance-to-constraint-boundary, with a top-two style sampling rule and a stopping rule over partitions (optimal set, dominated-feasible arms, infeasible arms) that minimizes verification cost rather than running a two-stage feasibility-then-PSI approach.
Key results
- e-cAPE achieves lower empirical sample complexity than the two-stage MD-APT+APE baseline and racing and uniform baselines on both clinical trial simulations, averaged over 500 runs.
- e-cAPE's upper bound on sample complexity scales with C*_M log(K C*_M/delta), and a matching lower bound holds for a class of instances up to a factor 8 (C*_M/8).
- e-cAPE's leading complexity is always no larger than that of the two-stage approach, and can be arbitrarily smaller.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use e-cAPE instead of competing algorithms | Constrained PSI · Secukinumab trial | sample complexity | Helped |
| use e-cAPE instead of competing algorithms | Constrained PSI · CovBoost 19 trial | sample complexity | Helped |
| use the two-stage MD-APT+APE approach instead of e-cAPE | Secukinumab trial dose-finding · Secukinumab trial | sample complexity | Hurt |
| use racing algorithm R-CP instead of e-cAPE | Constrained PSI · Constrained PSI experiments | sample complexity | Hurt |
| use tighter law-of-the-iterated-logarithm confidence bonuses (ablation) | e-cAPE · Constrained PSI experiments | sample complexity | Helped |
| use the two-stage feasible-set-then-Pareto-set approach instead of e-cAPE | Constrained PSI · General constrained PSI instances | sample complexity | Hurt |
Limitations
- Constraints are only guaranteed satisfied in the final recommendation; no controlled constraint violation during learning.
- Game-cPSI computational cost grows with Pareto set size and dimension (exponential in d in part).
Experimental setup
Datasets: Secukinumab phase 2 trial data (simulated Bernoulli bandit) CovBoost 19 trial data (simulated)
Benchmarks: Secukinumab trial simulation CovBoost 19 trial simulation
Metrics: sample complexity
Baselines: MD-APT+APE (two-stage) Uniform sampling Racing algorithm (R-CP)
Builds on: Adaptive Pareto Exploration (APE) LUCB MD-APT
Closest papers by meaning
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.89)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.89)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.88)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.88)
- Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.88)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.