Nearly Optimal Algorithms for Level Set Estimation

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.