Research map / Bandits and online learning / Multi-armed bandits
Preference-based Pure Exploration
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.
Studies fixed-confidence exact Pareto-optimal set identification in vector-reward bandits under a known polyhedral preference cone, deriving a KL-based lower bound and the PreTS track-and-stop algorithm with a matching (convexified) upper bound.
Problem
Identifying the exact Pareto optimal set of arms (policies) in multi-armed bandits with vector-valued rewards ordered by a known preference cone, with minimal sample complexity at confidence 1-delta.
Approach
Formulates the problem in policy space and derives a KL-based characteristic-time lower bound where distinguishability depends on projections onto the polar of the preference cone; convexifies the non-convex alternative set via disjunctive programming and tracks it with a Track-and-Stop algorithm (PreTS) using a new vector-valued concentration bound.
Key results
- Derives a KL-based lower bound on expected stopping time for PrePEx, generalizing BAI and known-constraint pure exploration lower bounds.
- Shows PreTS sample complexity matches the convexified lower bound asymptotically as delta goes to 0 (upper bound on E[tau]/log(1/delta)).
- Provides a new concentration inequality for vector-valued rewards with preference-projected confidence radii.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use convex relaxation of the lower-bound optimization | PreTS on non-Gaussian bandits · Preference-based pure exploration | stopping time | Hurt |
| use convex relaxation of the lower-bound optimization | PreTS on Gaussian bandits · Preference-based pure exploration | sample complexity | No clear effect |
| track the convexified lower bound with PreTS | PreTS · Preference-based pure exploration | expected stopping time | Helped |
Surprising findings
- Distinguishability of arms in PrePEx depends on their projections onto the polar cone of the preference cone, unlike in standard BAI.
Limitations
- Convexification may increase the characteristic time, so PreTS is not asymptotically optimal with respect to the non-convex lower bound.
- Empirical evaluation on real-world data is left to future work; the paper is largely theoretical.
- Upper bound relies on a pareto-front distance metric and concentration analysis that is more involved.
Experimental setup
Metrics: expected sample complexity
Baselines: Track-and-Stop-style BAI gap-based Pareto elimination algorithms
Builds on: Track-and-Stop Garivier and Kaufmann lower bound (BAI) Pareto set identification bandits
Closest papers by meaning
- FraPPE: Fast and Efficient Preference-Based Pure Exploration (NeurIPS 2025 · similarity 0.91)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.87)
- Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms (ICML 2025 · similarity 0.87)
- Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts (NeurIPS 2025 · similarity 0.87)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.87)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.87)
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.