Nearest Neighbour with Bandit Feedback
Abstract
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. A side result of this paper is that, when applied to the online classification problem with stochastic labels, our algorithm can, under certain conditions, have sublinear regret whilst only finding a single nearest neighbour per trial - in stark contrast to the k-nearest neighbours algorithm.
Cite
Text
Pasteris et al. "Nearest Neighbour with Bandit Feedback." Neural Information Processing Systems, 2023.Markdown
[Pasteris et al. "Nearest Neighbour with Bandit Feedback." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/pasteris2023neurips-nearest/)BibTeX
@inproceedings{pasteris2023neurips-nearest,
title = {{Nearest Neighbour with Bandit Feedback}},
author = {Pasteris, Stephen and Hicks, Chris and Mavroudis, Vasilios},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/pasteris2023neurips-nearest/}
}