  Level set estimation (LSE), the problem of identifying the set of input
points where a function takes value above (or below) a given threshold, is
important in practical applications. When the function is expensive-to-evaluate
and black-box, the \textit{straddle} algorithm, which is a representative
heuristic for LSE based on Gaussian process models, and its extensions having
theoretical guarantees have been developed. However, many of existing methods
include a confidence parameter $\beta^{1/2}_t$ that must be specified by the
user, and methods that choose $\beta^{1/2}_t$ heuristically do not provide
theoretical guarantees. In contrast, theoretically guaranteed values of
$\beta^{1/2}_t$ need to be increased depending on the number of iterations and
candidate points, and are conservative and not good for practical performance.
In this study, we propose a novel method, the \textit{randomized straddle}
algorithm, in which $\beta_t$ in the straddle algorithm is replaced by a random
sample from the chi-squared distribution with two degrees of freedom. The
confidence parameter in the proposed method has the advantages of not needing
adjustment, not depending on the number of iterations and candidate points, and
not being conservative. Furthermore, we show that the proposed method has
theoretical guarantees that depend on the sample complexity and the number of
iterations. Finally, we confirm the usefulness of the proposed method through
numerical experiments using synthetic and real data.
