Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Zero-Inflated Bandits
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 zero-inflated bandits, modeling rewards as a Bernoulli gate times a non-zero component, and proposes UCB and Thompson sampling algorithms (MAB and GLM contextual) with regret bounds and simulation/real-data (loan pricing) experiments.
Problem
Bandits with sparse rewards (zero-inflated) where standard parametric or nonparametric reward assumptions ignore the zero-inflated structure, leading to loose concentration bounds and inefficient exploration.
Approach
Model reward as product of Bernoulli non-zero indicator and non-zero magnitude, build separate confidence bounds for p and mu (product method) with a deterministic-rate bound on mu from observed non-zero samples, and use product-based UCB and TS (clipped Gaussian times clipped Beta) with regret guarantees.
Key results
- Proposed ZI UCB and TS algorithms achieve sub-linear regret across Gaussian, Gaussian-mixture and exponential reward simulations, while most baselines show linear or higher regret.
- The MAB UCB problem-independent regret is O(sqrt(KT log T)+K), matching the minimax lower bound up to sqrt(log T); the TS variant achieves sqrt(KT)+K, minimax optimal for sub-Gaussian MAB.
- Contextual ZI GLM UCB regret is O~((d v q) sqrt(T)), independent of number of arms K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the zero-inflated product structure instead of quantifying uncertainty directly from rewards | Zero-inflated MAB · Gaussian MAB simulation | cumulative regret | Helped |
| Use the zero-inflated product structure instead of quantifying uncertainty directly from rewards | Zero-inflated MAB · Gaussian mixture MAB simulation | cumulative regret | Helped |
| Use zero-inflated UCB rather than the UCB baselines | Zero-inflated MAB · MAB simulations | cumulative regret | Helped |
| Use zero-inflated Thompson sampling rather than MOTS | Zero-inflated MAB · Gaussian and Gaussian mixture MAB simulations | cumulative regret | Helped |
| Use zero-inflated UCB rather than misspecified or integrated UCB | Zero-inflated contextual bandits · Contextual bandit simulation, Probit link and s = 7 | cumulative regret | Helped |
| Use zero-inflated Thompson sampling rather than integrated Thompson sampling | Zero-inflated contextual bandits · Contextual bandit simulation, Probit link and s = 7 | cumulative regret | Helped |
| Model the zero-inflated structure rather than using an integrated model | Zero-inflated contextual bandits · Loan-record real-data experiment | cumulative regret | Helped |
| Use misspecified UCB or Thompson sampling that ignores the zero-inflated structure | Contextual bandits · Contextual bandit simulations | cumulative regret | Mixed |
| Use misspecified UCB or Thompson sampling that ignores the zero-inflated structure | Contextual bandits · Loan-record real-data experiment | cumulative regret | Mixed |
| Use a clipped Beta distribution rather than a standard Beta distribution for sampling the binary component (ablation) | Zero-inflated Thompson sampling · Zero-inflated MAB | overestimation probability for suboptimal arms | Helped |
Surprising findings
- The misspecified UCB and TS baselines may appear to perform well on the real loan dataset but sometimes incur linear regret.
Limitations
- Asymptotic order-optimality is not proven; probability allocation between the two concentration bounds may need adjustment based on p_k.
- Contextual regret analysis relies on regularity assumptions (bounded derivatives, compact parameter spaces, positive definite covariance) and fixed-horizon/random selection period.
- Heavy-tailed and sub-Weibull extensions for contextual bandits are only sketched.
Experimental setup
Datasets: US online auto loan company dataset (loan records)
Benchmarks: simulated zero-inflated MAB simulated zero-inflated contextual bandits real loan pricing dataset
Metrics: cumulative regret upper confidence bound tightness
Baselines: naive sub-Weibull UCB (true size parameter) UCB with estimated variance size parameter MOTS misspecified UCB integrated UCB misspecified TS integrated TS
Builds on: UCB Thompson sampling sub-Weibull concentration MOTS
Closest papers by meaning
- Optimal Gradient-based Algorithms for Non-concave Bandit Optimization (NeurIPS 2021 · similarity 0.86)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.86)
- Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions (ICLR 2026 · similarity 0.86)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.85)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.85)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.85)
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.