Nearest Neighbour with Bandit Feedback
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. We note that our algorithm can also be applied to the online classification problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Hierarchical Nearest Neighbour Approach to Contextual Bandits
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…
Computational EfficiencyMulti-Armed BanditsThe K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates
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, s…
Multi-Armed BanditsLLMs for Bayesian Optimization in Scientific Domains: Are We There Yet?
Large language models (LLMs) have recently been proposed as general-purpose agents for experimental design, with claims that they can perform in-context experimental design. We evaluate this hypothesis using both open- a…
k-Nearest Neighbour Classifiers: 2nd Edition (with Python examples)
Perhaps the most straightforward classifier in the arsenal or machine learning techniques is the Nearest Neighbour Classifier -- classification is achieved by identifying the nearest neighbours to a query example and usi…
ClassificationGeneral ClassificationRetrievalTime Series+1MicroNN: An On-device Disk-resident Updatable Vector Database
Nearest neighbour search over dense vector collections has important applications in information retrieval, retrieval augmented generation (RAG), and content ranking. Performing efficient search over large vector collect…
AttributeInformation RetrievalRAGRetrieval+1