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

Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

NeurIPS 2024 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 1 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.

Introduces the Local Anti-Concentration (LAC) condition on context densities and proves that exploration-free greedy (LinGreedy) linear contextual bandits achieve O(poly log T) expected regret for LAC distributions, including Gaussian, exponential, uniform, Cauchy, and Student's t.

Problem

Greedy (exploration-free) linear contextual bandits have been shown to achieve sublinear or logarithmic regret only for a few context distributions (mainly Gaussian and uniform), and it was unclear which broader class of context distributions enables efficient greedy learning.

Approach

Define a distributional condition bounding the sup-norm of the gradient of the log-density by a polynomial in the context norm (LAC). Under this condition, the minimum eigenvalue of the greedy-selected Gram matrix grows linearly and the suboptimality gap is bounded probabilistically, yielding poly-log regret without assuming a margin condition.

Key results

• Under the LAC condition, the expected cumulative regret of LinGreedy is bounded by O(poly log T), with a d^2.5 dependence (tilde-O) for unbounded contexts.
• The LAC class includes Gaussian, exponential, uniform, Cauchy, Student's t, Laplace, and truncated variants of these distributions.
• Experiments show LinGreedy achieves lower regret than LinUCB and LinTS on Gaussian, Laplace, uniform, and truncated Cauchy contexts.

Measured effects reported in the paper

Surprising findings

• The Gibbs distribution fails the diversity condition when K >= 3 arms, despite satisfying it in the two-armed case in prior multi-parameter work.

Limitations

• Results for bounded contexts depend on d and K in ways detailed only in the appendix; the unbounded-context bound scales as d^2.5.
• Requires context sets to be independent across time (not identically distributed) and bounded psi_1 norm for unbounded contexts.

Experimental setup

Datasets: synthetic contexts from Gaussian, Laplace, uniform, and truncated Cauchy distributions

Benchmarks: synthetic linear contextual bandit simulations

Metrics: cumulative expected regret

Baselines: LinUCB LinTS

Builds on: LinUCB Thompson sampling for linear bandits greedy linear contextual bandit analyses (Gaussian/uniform contexts)

Closest papers by meaning

• Breaking the $\sqrtT$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits (ICML 2022 · similarity 0.93)
• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.91)
• Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.90)
• Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.90)
• Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.90)
• Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.89)