Research map / Bandits and online learning / Multi-armed bandits
FraPPE: Fast and Efficient 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.
Proposes FraPPE, a computationally efficient and asymptotically optimal algorithm for preference-based pure exploration (Pareto set identification) with arbitrary polyhedral preference cones and exponential-family rewards, using structural reductions of the lower bound and Frank-Wolfe allocation.
Problem
Identifying the exact Pareto optimal set of arms in a vector-valued bandit under a preference cone, with sample complexity matching the characteristic-time lower bound, computationally efficiently and beyond Gaussian rewards.
Approach
Reduces the sup-inf-inf-inf characteristic-time problem to a max-min over Pareto basis policies and their neighbours, replaces the non-convex alternative set by a union of convex sets, uses a polar-cone representation of alternative instances, and solves the allocation with Frank-Wolfe plus a tractable stopping rule and C-tracking sampling.
Key results
- On COV-BOOST (delta=0.1), FraPPE averages 3523 samples versus 20456 for PSIPS and 17909 for TnS, roughly 5-6x fewer.
- Solves the max-min optimisation in O(KL^2) time, versus O(K^L) for prior combinatorial methods.
- On correlated Gaussian instances (5 arms, 2 objectives), FraPPE has lower average sample complexity than PSIPS across all correlation coefficients from -1 to 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FraPPE instead of PSIPS | Cov-Boost · Cov-Boost, δ=0.1 | average sample complexity: 20456 vs 3523; ~5-6X less | Helped |
| Use FraPPE instead of TnS | Cov-Boost · Cov-Boost, δ=0.1 | average sample complexity: 17909 vs 3523; ~5-6X less | Helped |
| Use FraPPE instead of PSIPS | Gaussian instance with correlated objectives · Gaussian instance, correlation coefficients from -1 to 1 | average sample complexity | Helped |
| Use FraPPE instead of PSIPS and Uniform | Cov-Boost · Cov-Boost | error probability | Helped |
Limitations
- Assumes the preference cone is known exactly
- Asymptotic optimality holds as delta goes to 0; non-asymptotic bound omitted from main text
- Experiments limited to COV-BOOST, SNW-style and small synthetic Gaussian instances
Experimental setup
Datasets: COV-BOOST SNW
Benchmarks: COV-BOOST synthetic Gaussian instances
Metrics: expected stopping time (sample complexity) error probability runtime complexity
Baselines: PSIPS APE TnS Oracle Uniform
Builds on: Track-and-Stop PreTS Frank-Wolfe
Closest papers by meaning
- Preference-based Pure Exploration (NeurIPS 2024 · similarity 0.91)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.88)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.87)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.87)
- Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap (AAAI 2025 · similarity 0.86)
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.