Research map / Bandits and online learning / Contextual bandits and Thompson sampling
From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
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.
Gives an (eps,delta)-PAC algorithm for contextual combinatorial semi-bandits with s-sparse rewards whose sample complexity's leading term scales with sparsity s rather than K, specializing to bandit list classification and improved single-label bounds.
Problem
Contextual combinatorial semi-bandits where contexts map to size-m subsets of K actions with semi-bandit feedback and s-sparse total reward; prior bounds scale polynomially with K, and it is unclear whether sparsity can improve sample complexity and regret.
Approach
Uses importance-sampled empirical convex objective (log-barrier type) over policies, optimized with Frank-Wolfe via an ERM oracle, to find a low-variance exploration distribution whose gradient is bounded by s; a second phase estimates policy rewards with variance O(sm), yielding sample complexity O((poly(K/m)+sm/eps^2) log(|Pi|/delta)).
Key results
- PAC sample complexity O((K^9/m^8 + sm/eps^2) log(|Pi|/delta)) for s-sparse CCSB, with leading term independent of K when s=O(1).
- Single-label case (s=m=1) improves the bound to O((K^7 + 1/eps^2) log(|H|/delta)) from prior K^9.
- Lower bound Omega~(sm/eps^2) for non-contextual combinatorial semi-bandits with s-sparse rewards; regret bound O~(|Pi| + sqrt(smT log|Pi|)) in adversarial setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PAC-COMBAND with exploration tailored to s-sparse rewards | CCSB · CCSB (s-sparse rewards, PAC) | sample complexity: O \brk*{\brk*{\frac{K^9}{m^8} + \frac{s m}{\eps^2}} \log \frac{|\Pi|}{\delta}}; naive approach: \approx K m / \eps^2 | Helped |
| Specialize the approach to single-label classification | Bandit multiclass classification · Single-label bandit multiclass classification (PAC) | sample complexity: O \brk*{\brk*{K^7 + \frac{1}{\eps^2}} \log \frac{|\mathcal{H}|}{\delta}}; prior: O((K^9 + 1/\eps^2) \log(|\mathcal{H}|/\ | Helped |
| Use an empirical Frank-Wolfe optimization algorithm instead of the stochastic variant | Single-label PAC algorithm · Single-label bandit multiclass classification (PAC) | sample complexity dependence on K: K^7; prior bound scales as K^9 | Helped |
| Make the exploration distribution depend on sparse rewards | CCSB regret algorithm · CCSB (adversarial online regret) | regret: \widetilde O(|\Pi| + \sqrt{smT \log |\Pi|}); prior CCSB bound: O(\sqrt{mKT \log |\Pi|}) | Helped |
| Use semi-bandit feedback and the proposed sparse-reward algorithm | Non-contextual combinatorial semi-bandits · Non-contextual combinatorial semi-bandit (s-sparse rewards) | sample complexity: \widetilde \Omega \brk*{sm/\eps^2} | Helped |
Surprising findings
- Bandit feedback in the single-label setting comes at essentially no extra cost asymptotically compared to full feedback, as the leading term is independent of K for s=O(1).
Experimental setup
Metrics: sample complexity regret
Baselines: Naive importance-sampling PAC Bandit PAC single-label classification (K^9 bound) EXP4
Builds on: Bandit PAC single-label classification (Foster et al. style exploration) Frank-Wolfe EXP4
Closest papers by meaning
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.91)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.91)
- Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions (AAAI 2021 · similarity 0.90)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.90)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.89)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · 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.