Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-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.
Proposes two covariance-adaptive algorithms for stochastic combinatorial semi-bandits: deterministic OLS-UCB-C (optimal gap-free rate) and sampling-based COS-V (first sqrt(T) gap-free sampling algorithm).
Problem
Stochastic combinatorial semi-bandits where the learner selects subsets of base items; existing covariance-adaptive methods lack a gap-free O(sqrt(T)) regret bound and are computationally costly, and semi-bandit feedback is not shown to help when P <= d.
Approach
Online estimation of the item covariance matrix yields coefficient-wise upper confidence bounds and ellipsoidal confidence regions giving closed-form UCBs (OLS-UCB-C); a Thompson-sampling-style variant (COS-V) samples item means from normals biased toward the positive orthant using the same estimators, avoiding the Delta_min^{-m} term.
Key results
- OLS-UCB-C achieves a gap-free regret of order sqrt(T) times sqrt(sum_i max_a sigma_{a,i}^2) (up to log factors), matched by a stated lower bound up to constants.
- COS-V is the first sampling-based combinatorial semi-bandit algorithm with O(sqrt(T)) gap-free regret (up to poly-logs), avoiding the Delta_min^{-m} term of prior TS analyses.
- Theoretical comparison claims OLS-UCB-C improves on CUCB and UCBV bounds, including in the P <= d regime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use covariance-adaptive OLS-UCB-C instead of CUCB | Stochastic combinatorial bandit · Stochastic combinatorial bandit | gap-free regret upper bound | Helped |
| Use covariance-adaptive OLS-UCB-C instead of UCBV | Stochastic combinatorial bandit with nonnegative covariances · Stochastic combinatorial bandit | gap-free regret upper bound | Helped |
| Use OLS-UCB-C with diagonal covariance | Stochastic combinatorial bandit · Stochastic combinatorial bandit with diagonal covariance | gap-free regret upper bound: a factor at least √m | Helped |
| Use OLS-UCB-C instead of bandit-feedback approaches | Stochastic combinatorial bandit under some covariance conditions · Regimes of P/d | regret upper bound | Helped |
| Use COS-V sampling with variance estimates | Sampling-based combinatorial semi-bandit · Stochastic combinatorial bandit | gap-free regret upper bound | Helped |
| Use COS-V, which does not leverage off-diagonal covariances, rather than a covariance-aware method | Stochastic combinatorial bandit · Stochastic combinatorial bandit | regret upper bound | Hurt |
| Use COS-V rather than deterministic semi-bandit algorithms when constraints allow efficient linear optimization | Combinatorial semi-bandit · Large action sets with matroid structure | time complexity | Helped |
| Use ellipsoidal confidence regions with closed-form action bounds instead of convex-set linear programs | OLS-UCB-C · Stochastic combinatorial bandit | computational complexity | Helped |
Limitations
- COS-V's gap-dependent bound is suboptimal since it ignores off-diagonal covariances and assumes worst-case correlations.
- Only positive covariance coefficients are used in the bounds; negative correlations are left to future work.
- OLS-UCB-C's estimated covariance matrix is not guaranteed positive semi-definite and its per-round cost grows badly for very large P.
Experimental setup
Metrics: pseudo-regret
Baselines: UCB UCBV CUCB OLS-UCB ESCB-C CTS-Gaussian
Builds on: OLS-UCB ESCB-C CTS CUCB
Closest papers by meaning
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.91)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.91)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.90)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.90)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.89)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · 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.