# Batched Nonparametric Bandits via k-Nearest Neighbor UCB

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 15 May 2025.

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

- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [Nonparametric Stochastic Contextual Bandits](https://mlsanity.com/paper/1801.01750/) (2018)
- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [A Batched Multi-Armed Bandit Approach to News Headline Testing](https://mlsanity.com/paper/1908.06256/) (2019)
- [Batched Single-Index Global Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2503.00565/) (2025)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)

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

- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)

## Abstract (arXiv)

We study sequential decision-making in batched nonparametric contextual bandits, where actions are selected over a finite horizon divided into a small number of batches. Motivated by constraints in domains such as medicine and marketing -- where online feedback is limited -- we propose a nonparametric algorithm that combines adaptive k-nearest neighbor (k-NN) regression with the upper confidence bound (UCB) principle. Our method, BaNk-UCB, is fully nonparametric, adapts to the context dimension, and is simple to implement. Unlike prior work relying on parametric or binning-based estimators, BaNk-UCB uses local geometry to estimate rewards and adaptively balances exploration and exploitation. We provide near-optimal regret guarantees under standard Lipschitz smoothness and margin assumptions, using a theoretically motivated batch schedule that balances regret across batches and achieves minimax-optimal rates. Empirical evaluations on synthetic and real-world datasets demonstrate that BaNk-UCB consistently outperforms binning-based baselines.