Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Bandits for Unbounded Context Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies nonparametric contextual bandits with unbounded (heavy-tailed) contexts, proposing a fixed-k and an adaptive-k nearest-neighbor UCB method with a matching minimax lower bound up to logs.
Problem
Nonparametric contextual bandits under Tsybakov margin condition where context distributions have unbounded support and heavy tails, requiring a bias-variance and exploration-exploitation tradeoff.
Approach
Nearest-neighbor UCB where the bias term L*rho (distance to k-th neighbor) is included per context, and an adaptive k chosen per context as the largest j with L*rho_j <= sqrt(ln T / j), so k adapts to local sample density and suboptimality gap.
Key results
- Adaptive kNN-UCB achieves expected regret O~(T^{1-min{(alpha+1)beta/(alpha+(d+2)beta), beta}}), matching the derived minimax lower bound up to logarithmic factors.
- Fixed-k kNN-UCB is minimax optimal under bounded contexts only when d > alpha+1 and is suboptimal otherwise.
- Experiments on synthetic distributions and MNIST show the adaptive kNN method outperforms UCBogram, ABSE and fixed-k kNN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use an improved, context-dependent UCB calculation instead of the prior kNN-UCB calculation | kNN-UCB · Bounded contexts with α > 0 | expected cumulative regret: \tilde{O}(T^\frac{d+1}{d+2}) -> \tilde{O}(T^{1-\frac{\alpha+1}{d+2}}) | Helped |
| select k adaptively instead of using fixed k | kNN-UCB · Bounded contexts, d < α+1 | expected cumulative regret: T^\frac{2}{\alpha+3} -> T|\mathcal{A}|\left(\frac{T}{\ln T}\right)^{-\frac{1+\alpha}{d+2}} | Helped |
| select k adaptively based on sample density and reward gaps instead of using fixed k | kNN-UCB · Heavy-tailed contexts | expected cumulative regret: T^{1-\frac{\beta \min(d,\alpha+1)}{\min(d-1,\alpha)+\max(1,d\beta)+2\beta}} -> T^{1-\min\left\{\frac{(\alpha+1)\beta}{\a | Helped |
| compare adaptive kNN with UCBogram, ABSE, and fixed-k kNN | Adaptive kNN · Synthetic 1D and 2D context distributions | cumulative regret | Helped |
| compare adaptive kNN with standard kNN at various k values | Adaptive kNN · MNIST | cumulative regret | Helped |
Surprising findings
- The fixed-k method is suboptimal in the heavy-tailed regime, with the bias-variance trade-off depending on the tail parameter beta.
Limitations
- Minimax lower bounds derived only for two actions; optimality in number of actions not addressed.
- Requires Lipschitz reward functions and sub-Gaussian noise; Holder extension left open.
- Assumes bounded suboptimality gap (Assumption b) for unbounded support.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST contextual bandit synthetic 1D and 2D context distributions
Metrics: cumulative regret expected regret
Baselines: UCBogram ABSE fixed-k kNN kNN-UCB
Builds on: UCBogram ABSE kNN-UCB Tsybakov margin condition
Closest papers by meaning
- An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits (NeurIPS 2020 · similarity 0.92)
- Nonparametric Stochastic Contextual Bandits (AAAI 2018 · similarity 0.91)
- High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions (ICML 2025 · similarity 0.90)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.90)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.89)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.