A Hierarchical Nearest Neighbour Approach to Contextual Bandits

Stephen Pasteris, Chris Hicks, Vasilios Mavroudis
12/14/2023
cs.LGstat.ML

No official code found. Best implementation: AICD-Research-Centre/nearest-neighbour-contextual-bandits (0 stars, MIT, last commit 2025-10-15).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

AICD-Research-Centre/nearest-neighbour-contextual-banditsCommunity68%
MIT

Code and experiments for A Hierarchical Nearest Neighbour Approach to Contextual Bandits (TMLR 2025)

00Python, Jupyter NotebookOct 13, 20251 years agoMIT

Similar Papers

Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces

87% match1 repo32022

Nearest Neighbour with Bandit Feedback

86% match2023

Online Learning with Off-Policy Feedback

83% match2022

Sparse Nonparametric Contextual Bandits

83% match2025

Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization

83% match2023

Distributed Stochastic Bandit Learning with Delayed Context Observation

83% match2022

Cite this paper

@article{pasteris2023hierarchical,
  title  = {A Hierarchical Nearest Neighbour Approach to Contextual Bandits},
  author = {Stephen Pasteris and Chris Hicks and Vasilios Mavroudis},
  year   = {2023},
  eprint = {2312.09332},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2312.09332v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2312.09332.svg)](https://codeofpaper.com/paper/2312.09332)

Discussion