# Contextual Bandits for Unbounded Context Distributions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 19 Aug 2024.

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

- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Analysis of KNN Density Estimation](https://mlsanity.com/paper/2010.00438/) (2020)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Local nearest neighbour classification with applications to semi-supervised learning](https://mlsanity.com/paper/1704.00642/) (2017)
- [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)
- [Smoothness-Adaptive Contextual Bandits](https://mlsanity.com/paper/1910.09714/) (2019)
- [Demystifying Fixed k-Nearest Neighbor Information Estimators](https://mlsanity.com/paper/1604.03006/) (2016)
- [Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression](https://mlsanity.com/paper/1910.10513/) (2019)
- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [Nonparametric Contextual Bandits in an Unknown Metric Space](https://mlsanity.com/paper/1908.01228/) (2019)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)

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

- [Gated Multimodal Graph Learning for Personalized Recommendation](https://mlsanity.com/paper/2506.00107/) (2025)
- [Task-Specific Efficiency Analysis: When Small Language Models Outperform Large Language Models](https://mlsanity.com/paper/2603.21389/) (2026)
- [LLM-Driven E-Commerce Marketing Content Optimization: Balancing Creativity and Conversion](https://mlsanity.com/paper/2505.23809/) (2025)
- [Research on Personalized Financial Product Recommendation by Integrating Large Language Models and Graph Neural Networks](https://mlsanity.com/paper/2506.05873/) (2025)
- [Deep Learning Model Acceleration and Optimization Strategies for Real-Time Recommendation Systems](https://mlsanity.com/paper/2506.11421/) (2025)
- [Batched Nonparametric Bandits via k-Nearest Neighbor UCB](https://mlsanity.com/paper/2505.10498/) (2025)
- [Hierarchical Indexing with Knowledge Enrichment for Multilingual Video Corpus Retrieval](https://mlsanity.com/paper/2510.09553/) (2025)
- [Taming the Long Tail: Efficient Item-wise Sharpness-Aware Minimization for LLM-based Recommender Systems](https://mlsanity.com/paper/2603.12752/) (2026)

## Abstract (arXiv)

Nonparametric contextual bandit is an important model of sequential decision making problems. Under α-Tsybakov margin condition, existing research has established a regret bound of tildeOleft(T^1-fracα+1d+2right) for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving contextual bandit problems with unbounded support is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. In this paper, we solve the nonparametric contextual bandit problem with unbounded contexts. We propose two nearest neighbor methods combined with UCB exploration. The first method uses a fixed k. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive k. By a proper data-driven selection of k, this method achieves an expected regret of tildeOleft(T^1-frac(α+1)βα+(d+2)β+T1-βright), in which β is a parameter describing the tail strength. This bound matches the minimax lower bound up to logarithm factors, indicating that the second method is approximately optimal.