# Approximate Function Evaluation via Multi-Armed Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 18 Mar 2022.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits](https://mlsanity.com/paper/1902.00197/) (2019)
- [Adaptive Estimation for Approximate k-Nearest-Neighbor Computations](https://mlsanity.com/paper/1902.09465/) (2019)
- [Learning Nearest Neighbor Graphs from Noisy Distance Samples](https://mlsanity.com/paper/1905.13267/) (2019)
- [Query Complexity of k-NN based Mode Estimation](https://mlsanity.com/paper/2010.13491/) (2020)
- [Adaptive Learning of Rank-One Models for Efficient Pairwise Sequence Alignment](https://mlsanity.com/paper/2011.04832/) (2020)

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

- [AcTracer: Active Testing of Large Language Model via Multi-Stage Sampling](https://mlsanity.com/paper/2408.03573/) (2024)
- [MABSplit: Faster Forest Training Using Multi-Armed Bandits](https://mlsanity.com/paper/2212.07473/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Adaptive Data Depth via Multi-Armed Bandits](https://mlsanity.com/paper/2211.03985/) (2022)

## Abstract (arXiv)

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.