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

Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear 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.

Proposes SupSplitLog, a K-armed logistic bandit algorithm that splits samples into pilot and estimation sets (initial-point estimator plus one-step Newton correction), achieving Õ(κ√(dT)+κ^2.5 d^2.5) regret without context diversity assumptions.

Problem

Regret of K-armed logistic bandits typically achieves Õ(√(dT)) only under context diversity assumptions (minimum eigenvalue of context covariance bounded below), which exclude contexts concentrated in low-dimensional subspaces and force dimension-dependent exploration.

Approach

Sample splitting: pilot samples produce an initial-point MLE, and a disjoint estimation set drives a single Newton-type one-step correction, so the Hessian is independent of the rewards used in the noise term, enabling scalar Bernstein concentration without diversity assumptions or random-sampling phases.

Key results

• Regret bound Õ(κ√(dT)+κ^2.5 d^2.5) without context diversity assumption, improving d-dependence over SupCB-GLM (d σ0^-8 + κ^8 d^3 σ0^-4) and SupLogistic (d σ0^-8 + κ^2 d σ0^-4) when σ0^-2=Ω(d).
• Data-dependent regret bound replacing d with log det(V_T/(κλI)), which is small when contexts lie in a low-dimensional subspace.
• In synthetic experiments, SupSplitLog performs most favorably against SupCB-GLM, SupLogistic, and DDRTS-GLM in middle and low regimes; DDRTS-GLM is competitive in the high regime.

Surprising findings

• DDRTS-GLM is competitive in the high-dimensional, full-span regime, so SupSplitLog's advantage appears only when effective dimension is much smaller than ambient dimension.

Limitations

• Non-leading term d^2.5 is worse than the leading √(dT) and can dominate when d grows with T.
• Dependence on κ remains a major open issue (κ√(dT) leading term).
• Experiments are limited to synthetic environments with T=2000 and K=5.

Experimental setup

Benchmarks: synthetic logistic bandit environment (T=2000, K=5, d in {3,20,100})

Metrics: cumulative regret log det ratio trajectory

Baselines: SupCB-GLM SupLogistic DDRTS-GLM

Builds on: Auer framework SupLogistic SupCB-GLM DDRTS-GLM

Closest papers by meaning

• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.90)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.89)
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.89)
• Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.89)
• High-dimensional Linear Bandits with Knapsacks (ICML 2024 · similarity 0.89)
• Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.89)