mlsanityData to 7 Oct 2026

Contextual Bandits for Unbounded Context Distributions

arXiv 2408.09655 ↗First posted 19 Aug 2024cs.LG stat.MLcited by 8

Not on the map. Why?

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.

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

Builds on

21 of 57 references.

References · 21

  1. 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
  2. 2014Rates of Convergence for Nearest Neighbor Classificationcited by 45
  3. 2019Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adaptingcited by 42
  4. 2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
  5. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  6. 2020Analysis of KNN Density Estimationcited by 28
  7. 2019Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimescited by 25
  8. 2022Transfer Learning for Contextual Multi-armed Banditscited by 24
  9. 2017Local nearest neighbour classification with applications to semi-supervised learningcited by 17
  10. 2018Nonparametric Stochastic Contextual Banditscited by 17
  11. 2018The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariatescited by 16
  12. 2019Smoothness-Adaptive Contextual Banditscited by 15
9 more
  1. 2016Demystifying Fixed k-Nearest Neighbor Information Estimatorscited by 14
  2. 2019Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regressioncited by 11
  3. 2023Robust Nonparametric Regression under Poisoning Attackcited by 11
  4. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  5. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  6. 2021Finite-time Analysis of Globally Nonstationary Multi-Armed Banditscited by 7
  7. 2019Nonparametric Contextual Bandits in an Unknown Metric Spacecited by 5
  8. 2023Adversarial Rewards in Universal Learning for Contextual Banditscited by 5
  9. 2024Adaptive Smooth Non-Stationary Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 2.

8 papers.

  1. 2025Gated Multimodal Graph Learning for Personalized Recommendationcited by 15
  2. 2026Task-Specific Efficiency Analysis: When Small Language Models Outperform Large Language Modelscited by 15
  3. 2025LLM-Driven E-Commerce Marketing Content Optimization: Balancing Creativity and Conversioncited by 7
  4. 2025Research on Personalized Financial Product Recommendation by Integrating Large Language Models and Graph Neural Networkscited by 6
  5. 2025Deep Learning Model Acceleration and Optimization Strategies for Real-Time Recommendation Systemscited by 3
  6. 2025Batched Nonparametric Bandits via k-Nearest Neighbor UCBcited by 1
  7. 2025Hierarchical Indexing with Knowledge Enrichment for Multilingual Video Corpus Retrievalcited by 1
  8. 2026Taming the Long Tail: Efficient Item-wise Sharpness-Aware Minimization for LLM-based Recommender Systemscited by 0