# FraPPE: Fast and Efficient Preference-based Pure Exploration

arXiv: https://arxiv.org/abs/2508.16487 · HTML: https://mlsanity.com/paper/2508.16487/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 73 references that are in the map.
- First posted on arXiv 22 Aug 2025.

## Builds on (most cited first, 28 of 28)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [BeaverTails: Towards Improved Safety Alignment of LLM via a Human-Preference Dataset](https://mlsanity.com/paper/2307.04657/) (2023)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Deep Adaptive Design: Amortizing Sequential Bayesian Experimental Design](https://mlsanity.com/paper/2103.02438/) (2021)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Active Testing: Sample-Efficient Model Evaluation](https://mlsanity.com/paper/2103.05331/) (2021)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Dueling Bandits With Weak Regret](https://mlsanity.com/paper/1706.04304/) (2017)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [Fair Adaptive Experiments](https://mlsanity.com/paper/2310.16290/) (2023)
- [Pareto Set Identification With Posterior Sampling](https://mlsanity.com/paper/2411.04939/) (2024)

## Built on by (most cited first, 4 of 4)

- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (2026)
- [Online Convex Optimization with Dueling Feedback](https://mlsanity.com/paper/2608.15050/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)
- [When More Objectives Make Identification Easier: The Role of Preferences and Feedback](https://mlsanity.com/paper/2610.18577/) (2026)

## Abstract (arXiv)

Preference-based Pure Exploration (PrePEx) aims to identify with a given confidence level the set of Pareto optimal arms in a vector-valued (aka multi-objective) bandit, where the reward vectors are ordered via a (given) preference cone C. Though PrePEx and its variants are well-studied, there does not exist a computationally efficient algorithm that can optimally track the existing lower bound for arbitrary preference cones. We successfully fill this gap by efficiently solving the minimisation and maximisation problems in the lower bound. First, we derive three structural properties of the lower bound that yield a computationally tractable reduction of the minimisation problem. Then, we deploy a Frank-Wolfe optimiser to accelerate the maximisation problem in the lower bound. Together, these techniques solve the maxmin optimisation problem in O(KL2) time for a bandit instance with K arms and L dimensional reward, which is a significant acceleration over the literature. We further prove that our proposed PrePEx algorithm, FraPPE, asymptotically achieves the optimal sample complexity. Finally, we perform numerical experiments across synthetic and real datasets demonstrating that FraPPE achieves the lowest sample complexities to identify the exact Pareto set among the existing algorithms.