# Adversarial Combinatorial Semi-bandits with Graph Feedback

arXiv: https://arxiv.org/abs/2502.18826 · HTML: https://mlsanity.com/paper/2502.18826/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 26 Feb 2025.

## Builds on (most cited first, 15 of 15)

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Tight Bounds for Bandit Combinatorial Optimization](https://mlsanity.com/paper/1702.07539/) (2017)
- [A Map of Bandits for E-commerce](https://mlsanity.com/paper/2107.00680/) (2021)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)

## Built on by (most cited first, 1 of 1)

- [Optimal Arm Elimination Algorithms for Combinatorial Bandits](https://mlsanity.com/paper/2510.23992/) (2025)

## Abstract (arXiv)

In combinatorial semi-bandits, a learner repeatedly selects from a combinatorial decision set of arms, receives the realized sum of rewards, and observes the rewards of the individual selected arms as feedback. In this paper, we extend this framework to include graph feedback, where the learner observes the rewards of all neighboring arms of the selected arms in a feedback graph G. We establish that the optimal regret over a time horizon T scales as widetildeTheta(S√T+√α ST), where S is the size of the combinatorial decisions and α is the independence number of G. This result interpolates between the known regrets widetildeTheta(S√T) under full information (i.e., G is complete) and widetildeTheta(√KST) under the semi-bandit feedback (i.e., G has only self-loops), where K is the total number of arms. A key technical ingredient is to realize a convexified action using a random decision vector with negative correlations. We also show that online stochastic mirror descent (OSMD) that only realizes convexified actions in expectation is suboptimal. In addition, we describe the problem of combinatorial semi-bandits with general capacity and apply our results to derive an improved regret upper bound, which may be of independent interest.