# Nearest Neighbour with Bandit Feedback

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 40 references that are in the map.
- First posted on arXiv 23 Jun 2023.

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

- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards](https://mlsanity.com/paper/1902.00819/) (2019)
- [Logarithmic-Time Updates and Queries in Probabilistic Networks](https://mlsanity.com/paper/1408.1479/) (2014)

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

- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [A Hierarchical Nearest Neighbour Approach to Contextual Bandits](https://mlsanity.com/paper/2312.09332/) (2023)
- [Differential Privacy in the Extensive-Form Bandit Problem](https://mlsanity.com/paper/2605.05266/) (2026)
- [Fairness with Exponential Weights](https://mlsanity.com/paper/2411.04295/) (2024)
- [Tracking the Best Strategy in an Extensive-Form Game](https://mlsanity.com/paper/2608.09501/) (2026)

## Abstract (arXiv)

In this paper we adapt the nearest neighbour rule to the contextual bandit problem. Our algorithm handles the fully adversarial setting in which no assumptions at all are made about the data-generation process. When combined with a sufficiently fast data-structure for (perhaps approximate) adaptive nearest neighbour search, such as a navigating net, our algorithm is extremely efficient - having a per trial running time polylogarithmic in both the number of trials and actions, and taking only quasi-linear space. We give generic regret bounds for our algorithm and further analyse them when applied to the stochastic bandit problem in euclidean space. We note that our algorithm can also be applied to the online classification problem.