# Nearly Optimal Algorithms for Level Set Estimation

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 2 Nov 2021.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Bayesian experimental design using regularized determinantal point processes](https://mlsanity.com/paper/1906.04133/) (2019)
- [Robust Super-Level Set Estimation using Gaussian Processes](https://mlsanity.com/paper/1811.09977/) (2018)
- [Adaptive Design of Experiments for Conservative Estimation of Excursion Sets](https://mlsanity.com/paper/1611.07256/) (2016)
- [Multiscale Gaussian Process Level Set Estimation](https://mlsanity.com/paper/1902.09682/) (2019)
- [Bayesian Experimental Design for Finding Reliable Level Set under Input Uncertainty](https://mlsanity.com/paper/1910.12043/) (2019)
- [High Dimensional Level Set Estimation with Bayesian Neural Network](https://mlsanity.com/paper/2012.09973/) (2020)

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

- [Rashomon Capacity: A Metric for Predictive Multiplicity in Classification](https://mlsanity.com/paper/2206.01295/) (2022)
- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling](https://mlsanity.com/paper/2203.04510/) (2022)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [Active Learning for Level Set Estimation Using Randomized Straddle Algorithms](https://mlsanity.com/paper/2408.03144/) (2024)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Robust Transfer Learning for Active Level Set Estimation with Locally Adaptive Gaussian Process Prior](https://mlsanity.com/paper/2410.05660/) (2024)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [High-dimensional Level Set Estimation with Trust Regions and Double Acquisition Functions](https://mlsanity.com/paper/2602.12391/) (2026)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Efficient and Interpretable Bandit Algorithms](https://mlsanity.com/paper/2310.14751/) (2023)
- [Experimental Design for Active Transductive Inference in Large Language Models](https://mlsanity.com/paper/2404.08846/) (2024)
- [An (ε,δ)-accurate level set estimation with a stopping criterion](https://mlsanity.com/paper/2503.20272/) (2025)

## Abstract (arXiv)

The level set estimation problem seeks to find all points in a domain cal X where the value of an unknown function f:cal Xrightarrow ℝ exceeds a threshold α. The estimation is based on noisy function evaluations that may be acquired at sequentially and adaptively chosen locations in cal X. The threshold value α can either be explicit and provided a priori, or implicit and defined relative to the optimal function value, i.e. α = (1-ε)f(x_ast) for a given ε > 0 where f(x_ast) is the maximal function value and is unknown. In this work we provide a new approach to the level set estimation problem by relating it to recent adaptive experimental design methods for linear bandits in the Reproducing Kernel Hilbert Space (RKHS) setting. We assume that f can be approximated by a function in the RKHS up to an unknown misspecification and provide novel algorithms for both the implicit and explicit cases in this setting with strong theoretical guarantees. Moreover, in the linear (kernel) setting, we show that our bounds are nearly optimal, namely, our upper bounds match existing lower bounds for threshold linear bandits. To our knowledge this work provides the first instance-dependent, non-asymptotic upper bounds on sample complexity of level-set estimation that match information theoretic lower bounds.