Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Active Context Selection Improves Simple Regret in Contextual Bandits

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 0 citations (OpenAlex)

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 contextual bandits with finite contexts under context-weighted simple regret, showing active context selection with allocation proportional to p_j^{2/3} beats passive sampling by up to k^{1/4}, and proposes EETC for unknown context distribution.

Problem

Contextual multi-armed bandits with finite subpopulations where the learner recommends a best treatment per context; the goal is to minimize context-weighted simple regret, and it is unclear when and how much actively choosing contexts helps over passive sampling.

Approach

Derives tight minimax simple-regret rates showing the optimal history-free active allocation over contexts is proportional to p_j^{2/3} (versus passive p_j), extends to a budgeted active fraction with a threshold-structured allocation, and proposes EETC that explores passively to estimate p and then commits to active allocation.</p_core_idea>

Key results

• Active allocation proportional to p_j^{2/3} achieves rate sqrt(n/T)||p||_{2/3}, improving over passive sqrt(n/T)||p||_{1/2}^{1/2} by a factor up to Theta(k^{1/4}).
• On MovieLens 1M with T=15000, Known-p Active + UCB achieves 0.31 ± 0.07 (x100) simple regret vs 0.47 ± 0.11 for Passive + UCB, while EETC + UCB achieves 0.33 ± 0.10.
• EETC matches the known-p active rate up to constants for sufficiently large horizon T.

Surprising findings

• Uniform allocation across contexts is minimax-suboptimal when p is known, and passive sampling is worse than active sampling by up to k^{1/4}.

Limitations

• Results are worst-case over rewards and do not give gap-dependent guarantees.
• EETC guarantees hold only for sufficiently large horizons.
• Evaluation is limited to a single real-world MovieLens 1M instance with a small number of arms and contexts.

Experimental setup

Datasets: MovieLens 1M

Benchmarks: MovieLens 1M

Metrics: simple regret

Baselines: Passive + Uniform Passive + UCB Known-p Active + Uniform Known-p Active + UCB

Builds on: MOSS Explore-Then-Commit

Closest papers by meaning

• Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces (ICML 2022 · similarity 0.92)
• High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions (ICML 2025 · similarity 0.91)
• Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.90)
• Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.90)
• Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.90)
• Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.90)