# The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2018.

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

- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Nearest Neighbour with Bandit Feedback](https://mlsanity.com/paper/2306.13773/) (2023)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [A Hierarchical Nearest Neighbour Approach to Contextual Bandits](https://mlsanity.com/paper/2312.09332/) (2023)
- [LNUCB-TA: Linear-nonlinear Hybrid Bandit Learning with Temporal Attention](https://mlsanity.com/paper/2503.00387/) (2025)
- [Batched Nonparametric Bandits via k-Nearest Neighbor UCB](https://mlsanity.com/paper/2505.10498/) (2025)
- [Non-Linear Model-Based Sequential Decision-Making in Agriculture](https://mlsanity.com/paper/2509.01924/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Nonparametric Contextual Pricing and Inventory Learning under Censored Demand](https://mlsanity.com/paper/2608.30944/) (2026)

## Abstract (arXiv)

In this paper we propose and explore the k-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates. We focus on a setting where the covariates are supported on a metric space of low intrinsic dimension, such as a manifold embedded within a high dimensional ambient feature space. The algorithm is conceptually simple and straightforward to implement. The k-Nearest Neighbour UCB algorithm does not require prior knowledge of the either the intrinsic dimension of the marginal distribution or the time horizon. We prove a regret bound for the k-Nearest Neighbour UCB algorithm which is minimax optimal up to logarithmic factors. In particular, the algorithm automatically takes advantage of both low intrinsic dimensionality of the marginal distribution over the covariates and low noise in the data, expressed as a margin condition. In addition, focusing on the case of bounded rewards, we give corresponding regret bounds for the k-Nearest Neighbour KL-UCB algorithm, which is an analogue of the KL-UCB algorithm adapted to the setting of multi-armed bandits with covariates. Finally, we present empirical results which demonstrate the ability of both the k-Nearest Neighbour UCB and k-Nearest Neighbour KL-UCB to take advantage of situations where the data is supported on an unknown sub-manifold of a high-dimensional feature space.