# Nonparametric Stochastic Contextual Bandits

Source: [Nonparametric Stochastic Contextual Bandits](<https://www.sota2.com/research/paper/68fa63eb1e209131cea01742>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:34.947Z

Authors: Melody Y. Guan, Heinrich Jiang

Published: 2018-01-05T13:27:42.000Z

## Abstract

We analyze the $K$-armed bandit problem where the reward for each arm is a noisy realization based on an observed context under mild nonparametric assumptions. We attain tight results for top-arm identification and a sublinear regret of $\\widetilde{O}\\Big(T^{\\frac{1+D}{2+D}}\\Big)$, where $D$ is the context dimension, for a modified UCB algorithm that is simple to implement ($k$NN-UCB). We then give global intrinsic dimension dependent and ambient dimension independent regret bounds. We also discuss recovering topological structures within the context space based on expected bandit performance and provide an extension to infinite-armed contextual bandits. Finally, we experimentally show the improvement of our algorithm over existing multi-armed bandit approaches for both simulated tasks and MNIST image classification.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1801.01750>)

[PDF](<https://arxiv.org/pdf/1801.01750.pdf>)