# Learning the Pareto Front Using Bootstrapped Observation Samples

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Doubly robust Thompson sampling for linear payoffs](https://mlsanity.com/paper/2102.01229/) (2021)
- [Multi-Objective Generalized Linear Bandits](https://mlsanity.com/paper/1905.12879/) (2019)
- [Bridging the gap between regret minimization and best arm identification, with application to A/B tests](https://mlsanity.com/paper/1810.04088/) (2018)
- [Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.11612/) (2021)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2110.08627/) (2021)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)
- [Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13791/) (2023)

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

- [A Doubly Robust Approach to Sparse Reinforcement Learning](https://mlsanity.com/paper/2310.15286/) (2023)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)
- [Adaptive Data Augmentation for Thompson Sampling](https://mlsanity.com/paper/2506.14479/) (2025)
- [Experimentation and Commitment under Reward Shifts](https://mlsanity.com/paper/2607.23432/) (2026)
- [Dominant Arm Identification with Mixing and Recycling Observed Samples](https://mlsanity.com/paper/2608.01545/) (2026)

## Abstract (arXiv)

We consider Pareto front identification (PFI) for linear bandits (PFILin), i.e., the goal is to identify a set of arms with undominated mean reward vectors when the mean reward vector is a linear function of the context. PFILin includes the best arm identification problem and multi-objective active learning as special cases. The sample complexity of our proposed algorithm is optimal up to a logarithmic factor. In addition, the regret incurred by our algorithm during the estimation is within a logarithmic factor of the optimal regret among all algorithms that identify the Pareto front. Our key contribution is a new estimator that in every round updates the estimate for the unknown parameter along multiple context directions -- in contrast to the conventional estimator that only updates the parameter estimate along the chosen context. This allows us to use low-regret arms to collect information about Pareto optimal arms. Our key innovation is to reuse the exploration samples multiple times; in contrast to conventional estimators that use each sample only once. Numerical experiments demonstrate that the proposed algorithm successfully identifies the Pareto front while controlling the regret.