# A Hierarchical Nearest Neighbour Approach to Contextual Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 14 Dec 2023.

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

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [Nearest Neighbour with Bandit Feedback](https://mlsanity.com/paper/2306.13773/) (2023)
- [Logarithmic-Time Updates and Queries in Probabilistic Networks](https://mlsanity.com/paper/1408.1479/) (2014)

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

- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)

## Abstract (arXiv)

In this paper we consider the adversarial contextual bandit problem in metric spaces. The paper "Nearest neighbour with bandit feedback" tackled this problem but when there are many contexts near the decision boundary of the comparator policy it suffers from a high regret. In this paper we eradicate this problem, designing an algorithm in which we can hold out any set of contexts when computing our regret term. Our algorithm builds on that of "Nearest neighbour with bandit feedback" and hence inherits its extreme computational efficiency.