Approximate Function Evaluation via Multi-Armed Bandits

We study the problem of estimating the value of a known smooth function f at an unknown point boldsymbolμ ∈ ℝn, where each component μi can be sampled via a noisy oracle. Sampling more frequently components of boldsymbolμ corresponding to directions of the function with larger directional derivatives is more sample-efficient. However, as boldsymbolμ is unknown, the optimal sampling frequencies are also unknown. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least 1-δ returns an ε accurate estimate of f(boldsymbolμ). We generalize our algorithm to adapt to heteroskedastic noise, and prove asymptotic optimality when f is linear. We corroborate our theoretical results with numerical experiments, showing the dramatic gains afforded by adaptivity.