Research map / Bandits and online learning / Online convex optimization and games
Adversarial Combinatorial Semi-bandits with Graph Feedback
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.
Establishes the minimax regret of combinatorial semi-bandits with feedback graphs as Θ~(S√T + √(αST)) and gives OSMD-G, which samples negatively correlated decisions to achieve it.
Problem
Combinatorial semi-bandits in the adversarial setting where the learner observes rewards of neighbors of selected arms in a feedback graph, rather than only the selected arms; the optimal regret as a function of the feedback graph's independence number is unknown.
Approach
Mirror descent (OSMD-G) with a graph-based unbiased reward estimator, combined with a randomized swap rounding sampler that yields negatively correlated decision vectors; this variance control interpolates the regret between full-information S√T and semi-bandit √(KST) rates.
Key results
- OSMD-G achieves regret Õ(S√T + √(αST)) on the full decision set for any strongly observable directed feedback graph, interpolating between full-information and semi-bandit rates.
- A matching lower bound Ω(S√(T log(K/S)) + √(αST)) holds under T ≥ max{S, α^3/S} and S ≤ K/2.
- Vanilla OSMD-G that only satisfies the mean condition suffers Ω(S√(αT)) regret on a constructed instance, so negative correlations are necessary for the improved rate in the analysis.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use negative-correlated sampling when realizing convexified actions | OSMD-G on the full decision set · Combinatorial semi-bandits with strongly observable graph feedback | regret: \widetilde{O}(S\sqrt{T} + \sqrt{\alpha ST}) versus \Omega(S\sqrt{\alpha T}) | Helped |
| Remove the negative-correlation requirement and guarantee only the mean condition (ablation) | OSMD-G on the full decision set · Combinatorial semi-bandits with strongly observable graph feedback | regret: \widetilde{O}(S\sqrt{T} + \sqrt{\alpha ST}) versus \Omega(S\sqrt{\alpha T}) | Hurt |
| Exploit the graph of cliques among copies of each arm | Combinatorial semi-bandits with general capacity · General capacity | regret: \widetilde{O}(\sqrt{ST\sum_{a=1}^K n_a}) versus \widetilde{\Theta}(\sqrt{KST}) | Helped |
| Restrict the full decision set to the partition decisions (ablation) | Combinatorial semi-bandits with graph feedback · Proper decision subset | minimax regret: \widetilde\Theta(S\sqrt{T}+ \sqrt{\alpha ST}) versus \widetilde\Theta(S\sqrt{\alpha T}) | Hurt |
Surprising findings
- Realizing the convexified action only in expectation (standard OSMD) is provably suboptimal under graph feedback; negative correlations are needed.
- On general decision subsets, the optimal regret can rise to Θ~(min{S√(αT), √(KST)}), showing a gap from the full decision set.
Limitations
- Results focus on strongly observable graphs; weakly observable case is open (only ETC upper bound sketched for stochastic rewards).
- For general decision subsets, OSMD-G is not efficient and the sampling scheme may not exist with negative correlations.
Experimental setup
Metrics: expected regret
Baselines: OSMD semi-bandit OSMD
Builds on: OSMD randomized swap rounding feedback graphs for bandits
Closest papers by meaning
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.91)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.91)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.91)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.90)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.90)
- Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems (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.