Adversarial Combinatorial Semi-bandits with Graph Feedback
Authors: Yuxiao Wen
Venue: ICML 2025 poster (2025)
Keywords: Combinatorial bandits
graph feedback
semi-bandit
adversarial bandits
statistical learning
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We consider combinatorial bandits with graph feedback among the arms and prove tight regret characterization that interpolates nicely between known extreme cases.

Abstract: 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 \emph{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 $\widetilde{\Theta}(S\sqrt{T}+\sqrt{\alpha ST})$, where $S$ is the size of the combinatorial decisions and $\alpha$ is the independence number of $G$. This result interpolates between the known regrets $\widetilde\Theta(S\sqrt{T})$ under full information (i.e., $G$ is complete) and $\widetilde\Theta(\sqrt{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.

Adversarial Combinatorial Semi-bandits with Graph Feedback
Yuxiao Wen
Abstract
(Cesa-Bianchi & Lugosi, 2012; Audibert et al., 2014; Chen et al., 2013). Mathematically, over time horizon of length T and for a fixed combinatorial budget S, learner repeat- edly chooses a (potentially constrained) combination of K individual arms within the budget, i.e. from the following decision set
In combinatorial semi- comi-bandits, a learner repeat- edly 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 feedback graph G. We establish that the optimal regret over a time horizon T scales as @(SVT + VaST), where S is the size of the combinatorial decisions and a is the independence number of G. This result interpolates between the known regrets (TT) under full information (i.e., G is complete) and (T)) under the semi-bandit feedback (i.e., G has only self-loops), where K's is the total num- ber of arms. A key technical ingredient is to real- ize 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 ca- pacity and apply our results to derive an improved regret upper bound, which may be of independent interest.
A AA
:/llll1111111111. = SS}
and receives linear payoff (u,r²) where rd [0, 1] denotes the reward associated to each arm at time t. Af- ter making the decision at time t, the learner observes fuard : E [K]] as the semi-bandit feedback or the en- tire reward vector r" under full information. When $ = 1, it reduces to the multi-armed bandits with either the ban- dit feedback or full information. For > 1, the learner is allowed to select S arms at each time and collect the cumulative reward.
Under the adversarial setting for bandits (Auer et al., 1995), no statistical assumption is made about the reward vectors (r" heem- Instead, they are (potentially) generated by an adaptive adversary. The objective to minimize the ex- pected regrer of the learner's algorithm и compared to the best fixed decision in hindsight, defined as follows:
T
E(((T))
E max U.E.A
Σ
(v.- v. rr)
where of E Ao is the decision chosen by π at time f. The expectation is taken over any randomness in the learner's algorithm and over the rewards, since the reward rf al- lowed to be generated adaptively and hence be random. Note that while the adversary can generate the rewards yd adaptively, i.e. based on the learner's 's past decisions, the re- gret in (1) is measured against fixed decision e, assuming the adversary would generate the same rewards.
1. Introduction
Combinatorial semi-bandits are class of online learning problems that generalize the classical multi-armed bandits (Robbins, 1952) and have a wide range of applications in- cluding multi-platform online advertising (Avadhanula et al., 2021), online recommendations (Wang et al., 2017), web- page optimization (Liu & Li, 2021), and online shortest path (György et al., 2007). these applications, instead of taking an individual action, set of actions is chosen each time
While the semi-bandit feedback has been extensively stud- ied, the current literature falls short of capturing additional information structures on the rewards of the individual arms, except for the full information case. As motivating exam- ple, consider the multi-platform online advertising problem, where the arms represent the (discretized) bids. At each round and on each platform, the learner makes a bid and receives zero reward on losing the auction and her surplus on winning the auction. many ads exchange platforms,
'Courant Institute of Mathematical Sciences, New York Uni- versity, New York, USA. Correspondence to: Yuxiao Wen <yuxi- aowen@ @yven@ny..du>>..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Instead of fixed graph G, Cohen al. (2016) and Alon et al. (2017) study time-varying graphs {G,} and show that Adversarial Combinatorial Semi-bandits with Graph Feedback
the winning bid is always announced, and hence the learner can compute the counterfactual reward for any bids higher than her chosen bid (Han et al., 2024). This additional information is not taken into account in the feedback.
of choosing arm a. ! 'The transition of the optimal regret's de- pendence from VKS S, as the feedback becomes richer, remains curious and important open problem.
Another type of feedback is the bandit or full-bandit feed- back, which assumes only the realized payoff (e, r²) is revealed (rather than the rewards for individual arms). In this case, the minimax optimal regret 6 ((VKS*T) (Au- dibert et al., 2014; Cohen et al., 2017: Ito et al., 2019). This additional S factor, compared to the semi mani-bandit feedback, matches the difference in the observations: in this bandit feedback, the learner obtains a single observation at each time, while in the semi-bande the learner gains 5 observa- tions. When the payoff function is nonlinear in v, Han et al. (2021) shows that the optimal regret scales with Kd where d roughly stands for the complexity of the payoff function. More variants of combinatorial semi-bandits include the knapsack constraint (Sankararaman & Slivkins, 2018), the fractional decisions (Wen et al., 2015), and the contextual counterpart (Zierahn et al., 2023).
Another example is the online recommendation problem, where the website plans to present combination of rec- ommended items to the user. The comi-bandit feedback assumes that the user's behavior the displayed items will reveal no information about the undisplayed items. How- ever, this assumption often ignores the semantic relationship between the items. For instance, suppose two items i and j are both tissue packs with similar prices. If item is dis- played and the user clicks on it, a click is likely to happen if item; were be displayed. On the other hand, if item is a football and item j is wheelchair, then click on one probably means no-click on the other. Information of this kind is beneficial for the website planner and yet overlooked in the semi-bandit feedback.
To capture this rich class of combinatorial additional information, we consider a more general feed- back structure described by directed graph G = =[K], among the K arms. We assume G is strongly observable, i.e. for every E [K], either (a,a) E E or (b,a) E E for all b * a. After making the decision v E Ao at each time, the learner now observes the rewards associated to all neighboring arms of the selected arms in o:
with
In the multi-armed bandits, multiple attempts have been made to formulate and exploit the feedback structure as feedback graphs since Mannor & Shamir (2011). In par- ticular, the optimal regret is shown to be ((vTT) when T 2 a² (Alon et al., 2015; Eldowa et al., 2024) and is a mixture of / and T2/3 terms when T is small due to the exploration-exploitaiion trade-off (Kocák & Carpentier, 2023). When the graph is only weakly observable, i.c. every node a E [K] has nonzero in-degree, the optimal regret is ((8//372/3) (Alon et al., 2015). Here a and ó are the independence and the domination number of the graph G respectively, defined in Section 1.3.
( (mot: 3a E [K] such that v/2 = 1 and (a, E R..
This graph formulation allows us to leverage information that is unexploited in the semi-bandit feedback.
Note that when G is complete, the feedback structure cor- responds to having full information; when G contains only the self-loops, it becomes the semi-bandit feedback. In the presence of general G, the sppooration-xxlooiatii trade-off becomes more complicated, and the goals of this paper are (1) to fully exploit this additional structure in the regret minimization and (2) to understand the fundamental learning limit in this class of problems.
an upper bound δ - at can be achieved. Addi- tionally, a recent line of research (Balseiro et al., 2023; Han et al., 2024; Wen et al., 2024) introduces graph feedback to the tabular contextual bandits, in which case the opti- mal regret depends on complicated graph quantity that interpolates between a and K as the number of contexts changes.
1.1. Related work
1.2. Our results
The optimal regret of the combinatorial semi-bandits has drawn a lot of attention and has been extensively studied in the bandit literature. With linear payoff. Koolen et al. (2010) shows that the Online Stochastic Mirror Descent (OSMD) algorithm achieves opar-optimal regret ((SVT) under full information. In the case of the semi-bandis feed- back, Audibert et al. (2014) shows that OSMD achieves near-optimal regret ((VKST) using an unbiased estimator F. = / [oğ], where vf is the random decision se- lected at time and the expectation denotes the probability
In this paper, we present results on combinatorial semi- bandits with a strongly observable feedback graph G and the full decision set Ao = A. while results on general Ao are discussed in Section 5.1 and 5.2. Our results are summarized in Table 1, and the main contribution of this
Audihert al. (2014) only argues there exists particular decision subset Ao under which the regret is Ω ((KKST). The lower bound for AA is given by Lattimore et al. (2018).
2

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
Table 1. Minimax regret bounds up to polylogarithmic factors. Our results in bold.
Semi-bande (a = K)
General feedback graph G
Full information (a = 1)
Regret
((VKST)
@(SV VaST)
@(SVT)
paper four-fold:
selecting a random decision vector v², In the extreme cases of full information and semi-bandit feedback, the optimal regret is achieved as long ef realizes the convexified action æ in expectation (Audibert et al., 2014). However, this realization in expectation alone is provably suboptimal under graph feedback, as shown later in Theorem 3.4.
1. We introduce the formulation of a general feedback structure using feedback graphs in combinatorial semi- bandits.
2. On the full decision set A. we establish a minimax regret lower bound R(SVT+ + VaST) that correctly captures the regret dependence on the feedback struc- ture and outlines the transition from ((SVT) to (T) as the feedback gets richer.
Under a general graph G, the regret analysis for tight bound crucially requires this random decision vector to have negative correlations among the arms, i.e. Cov(ut, uf) I 0 for i * j. in addition to the realization of x in expectation. Consequently, the following technical lemma is helpful in our upper bound analysis:
3.
We propose a policy OSMD-G (OSMD under graph feedback) that achieves near-optimal regret under gen- eral directed feedback graphs and adversarial rewards. Importantly, we identify that sampling with negative correlations crucial in achieving the near-optimal regret, and that the original OSMD is provably subop- timal.
Lemma 1.2. Fix any S K and E Conv (A). There exists probability distribution p over A that satisfies:
1. (Mean) Vi [K], Eewp/us) Zz-
2. (Negative correlations) Vi # j. Euspleguyl S 24Z,, i.e. any pair of arms (i.5) is negatively correlated.
4. We formulate the problem of combinatorial semi- bandits with general capacity in Section and provide an improved regret by applying our results under graph feedback. This formulation may be of independent interest.
In particular. there is an efficient scheme to sample from p.
This lemma is corollary of Theorem 1.1 in Chekuri et al. (2009), and the sampling scheme is the randomized swap rounding (Algorithm 2). The mean condition guarantees that the convexified action is realized in expectation. The nega- tive correlations essentially allow us to control the variance of the observed rewards in OSMD-G, thereby decoupling the final regret into two terms. Intuitively, the negative corre- lations imply more exploratory sampling scheme; more detailed discussion is in Section 3.1.
When the feedback graphs [Gr]eET] are allowed be time- varying, we can also obtain a corresponding upper bound. The upper bounds are summarized in the following theorem.
Theorem 1.1. Consider the full decision set A. For I S < K and any strongly observable directed graph G = ([K), F), there exists algorithm that achieves regrel
[[R(T)] = Ö(STT+++ VaST)
To show that OSMD-G achieves near-optimal performance, we consider the following minimax regret:
When the feedback graphs (Gelre(T) are time-varying, the same algorithm π achieves
R inf sup E[R(T)]
{r'}
50
[[[()) = SVT+
S
aD
where the inf is taken over all possible algorithms and the sup is taken over all potentially adversarial reward se- quences. The following lower bound holds:
where = aG))) is the independence number of Gr.
Theorem 1.3, Consider any decision subset Ao C A and strongly observable graph G. When T 2 max(S, a² a and S < K/2, holds that
This algorithm is OSMD-G proposed in Section 3. In OSMD-G, the learner solves for an optimal convexified action x E Conv(A) via mirror descent at each time f, using the past observations, and then realizes (in expectation) via
R* = 2( ===(ss ((SS/Tlg((//)) VoST)
3

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
Our lower bound construction in the proof is stochastic, as is standard in the literature, and thus stochastic combinatorial semi-bandits will not be easier.
semi-bandit policy and shows they share the same expected regret. Thus the lower bound of one translates that of the other. As soon as the feedback structure is not full infor- mation, the observations and thus the behaviors of the two policies no longer align.
1.3. Notations
The convex hull of A is denoted by Conv(AA) and the truncated convex hull is defined by
For N. denote [n] = (.., n).
To prove the second part, note that (IVvST only mani- fests in the lower bound when S < a. In this case, we parti- tion an independent subset I S [K] of size a into subsets 1, 1,..... Is of equal size - and embeds an independent multi-armed bandit hard instance in each Im for E [S]. The other arms J = [ may be more informative but will incur large regret. Thus a good learner cannot leverage arms in due to the ppploration-exploittatin trade-off.
CA) = (xr Conv(A) az 2 for all i [K]]
We the standard asymptotic notations 52, O, θ to denote the asymptotic behaviors up to constants, and $2, O θ up to polylogarithmic factors respectively. Our results will concern the following graph quantities:
The learner then needs learn S independent sub-problems with ST total number of arm pulls. If the learner is 'bal- anced' in the sense that for each sub- sub-problem E [S],
a max S [K] is an independent subset in G}, min( D C [K] is a dominating subset in G}.
(T) = Σ E
1a pulled] T, al
In graph G. S [K] is an independent subset if for any i E I, (i.j) & E; and D S [K] is a dominating subset for any u E [K]. there exists E D such that (i, u) E E. For each node a E [K]. denote its out-neighbors G by
then the existing multi-armed bandit lower bound implies that the regret incurred in each sub-problem is 2 D(vall ST) thereby a total regret (2(vSTT) While in our case the learner may arbitrarily allocate the arm pulls over the sub-problems, turns out to be sufficient to focus on the 'balanced' learners via stopping time argument proposed in Lattimore al. (2018). Intuitively, if a learner devotes pulls Tn, (T) > T for some m, then he/she must suffers regret (TT.. (T) - TT) where A is the reward gap in the hard instance, which leads to suboptimal performance.
Nout (a) = {i E [K] : (a, E E}
and its in-neighbors by
(a) = li [K] (i,a)= E E}.
Then for binary vector A that represents an S-arm subset of [K]. we denote its out-neighbors in G by the union Nou((e) = Uw,=1 (a). Let D C Rd be an
3. A near-optimal algorithm
open convex set, 75 be its closure, and F 7 IR be differentiable, strictly convex function. We denote the Bregman divergence defined by F
This section is structured as follows: In Section 3.1, we present our OSMD-G algorithm and highlight the choice of reward estimators and the sampling scheme that allow us to deal with general feedback graphs. Then we show that OSMD-G indeed achieves near-optimal regret Ö(SVT + VoST) in Section 3.2. Finally, we argue in Section 3.3 that if the requirement of negative correlations is removed, OSMD-G would be suboptimal.
Dr(z,y) = F(x) F(y) (VF((VFF))) v).
2. Regret lower bound
In this section, we sketch the proof of the lower bound in Theorem 1.3 and defer the complete proof to Appendix A.
The idea is to divide this learning problem into S indepen- dent sub-problems and present the -exooratio-expliiaattioo trade-off under a set of hard instances to arrive at the final minimax lower bound.
3.1. Online stochastic mirror descent with graphs
The overall idea of OSMD-G (Algorithm 1) is to perform a gradient descent step each time t, based on unbiased re- ward estimators, in a dual space defined by mirror mapping F that satisfies the following: Definition 3.1. Given an open convex set D C Rd. mirror mapping F: D + R satisfies
Under the complete graph G, Koolen et al. (2010) already gives a lower bound ((SVT / log(K/S)) by reducing the full information combinatorial semi-bandits to the full infor- mation multi-armed bandits with rewards ranging in [0, SJ. This reduction argument, however, does not lead to the other 2( (((v)TT) part of the lower bound. It constructs a multi-armen bandit policy from any given combinatorial
F is strictly convex and differentiable on D;
limm-aa [V)())) = +00.

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
While OSMD-G works with any well-defined mirror map- ping, we will prove the desired upper bound in Sec- tion 3.2 for OSMD-G with the negative entropy F(x)- = K
Algorithm I Online Stochastic Mirror Descent under Graph
Feedback (OSMD-G)
Input: time horizon T, decision set A, arms [K], com- binatorial budget S, feedback graph G, truncation rate E (0, 1), learning rate 1) > 0, mirror mapping F defined on a closed convex set D 2 CA)v
Ee (z, 1og(2;) =2) defined on D = R.K For this choice of F, the dual space D' RKK and hence (5) is always valid.
In fact, (5) admits the explicit form
Initialize: x² + arg min ZE (A) F(z).
w++1 x² exp(n)*)-
for t- 1 to T do
Recall at each time t. for selected decision of A. the learner observes graph feedback { E Nour(v')) Based on this, we define the reward estimator for each arm E [K] at time L in (4). As we invoke a sampling scheme to realize x' in expectation, i.c. Epp' [u*] = x², our estimator in (4) is unbiased.
Generate combinatorial decision of by Algorithm 2 with target z². Observe the feedback fr's : a E Nout (oo)( Denote
Mi)) 1/u = 1](1 - -1)
F/ =
(3)
Eie NinN)(()) F!
crucial step in OSMD-G is to sample a decision of each time that satisfies both the mean condition Ee [o*] x and the negative correlation Eyt=p' [ofe]] S a/a0 Thanks to Lemma 1.2, both conditions are guaranteed for all possible target x' E Conv((A) when we invoke Algorithm 2 as our sampling subroutine. 2 The description and details of Algorithm are deferred to Appendix B.
Build the reward estimator for each a E [K]:
Fd = 1 1 Ar.
(4)
if S = then
Denote U2 = fa E [K] : pl S (K-tzc).
Set Ft 1 ++ Enev, I/ahl.
While seemingly intuitive given that ||u$|] = S. we em- phasize that the negative correlations Eytrp' [o]u5] S 2/2/ do not necessarily hold and can be non-trivial to achieve. Consider the case S = 2. When x' x is the uni- form vector, uniform distribution over all pairs satisfies the correlation condition, seeming to suggest the choice of j).,j) x afaa-- However, when x² = (1, 01,, 0.2), the only such solution is to sample the combination {1,2] with prob- ability 0.8 and {1.3] with probability 0.2, suggesting zero probability for sampling (2,3). A general strategy must be able to generalize both scenarios. From the perspective of linear programming, the correlation condition adds (%) constraints to the original K constraints (from the mean condition) in finding p", making it much harder to find a feasible solution.
Set F/. t F/ - for all a [K].
end
Find w+1 E such that
VF(w"t)) = V + nf¹
(5)
Project w to the truncated convex hull Conv, (A):
x 1+1
arg min Dp Dp(z,u(1)) w(1).. .ECouv.(A)
(6)
end
with size S - 1 or S 2, conditioned on the assignment of eg For any j1 E [1, 1], j2 E li + K, and i, any two of them are negatively correlated because, at high level, the presence of one 'reduces" the size budget of the other. The negative correlations among the first half [1, i 1) and ji + 1, K] are guaranteed by the induction hypothesis of the existence of such distributions for solutions with size less than S. Finally, the structure of A ensures that our pieced-together solution is valid, i.c. lies in A.
Now we give an intuitive argument for why such distri- bution p exists under A and how the structure of the lat- ter helps. When S = 1, any distributions possess nega- tive correlations. Inductively, let us suppose such distri- butions exist for 1, 2, ,
1. Then for a fixed target I E Conv(A), we can always find an index E [K] such that Σ z c2; = 1 and Ej=++ my + (1-c)æ;;
S- for some e E [0, 1]. Namely, the target of size S is parti- tioned into two sub-targets with ranges [1, i] and [i, K]. each with sizes 1 and s - 1, and with an overlap on index i. We can then assign e; = 0 with probability
3.2. Regret upper bound
xú, to the first half i1, with probability co,, and to [8, K] with probability (I (1- c) To obtain final size S solution, we draw of supported on [1, 1 1] with size 0 or and v" on [i + K]
In the following theorem, we show that OSMD-G achieves near-optimal regret for strongly observable time-invariant feedback graph. The proof for time-varying feedback graphs (Grhen only takes one-line change in (11). It is clear that Theorem 3.2 implies Theorem 1.1.
The use of Algorithm 2 is not essential as long as one can guarantce the negative correlations Lemma 1.2.
Theorem 3.2. Let the mirror mapping be F(x)
5

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
E (1F log x.). When the correlation condition for p' is satisfied, the expected regret of Algorithm 1 is upper bounded by
nodes with no self-loops. On the set U we have
T
E
Σ
Σ
(Fg))
(lo((K/S)
aEt
E|R(Alg 1)] S <KT+
"
T
EieNi 1l0 = 1](1 =11(1 - r2)
27
E
EieNi. o.
In particular, with truncation e KT and learning rate 1)
dEU
(6S+ log 4o = =0(V [S+a]T] it becomes
58 log( log(K/S)
1
Eiza 1l0 =
27
J/
Σitt x
[[R(Alg 1)] 1 3 (SVT + VaST)
1=1 REU
(6)
T
27
I
for B v
Õ(1)
5 - 1
1=1 DED
Proof. We present the proof for the case $ 2 2 here. The proof for S = 1 is similar and is deferred to Appendix C due to space limit. Now fix any V E A. Let
Blral S 4ST.
(9)
DEU
Here (a) is due to to E |0, 1] and that, a E U, then (i, a) E E for all i * a, and (b) uses Liya x] = S - x 2 S 1. On the other hand, by the choice of o¹ in Algorithm 1, the random variables uf are negatively correlated. Thus for each a E [K], we can upper bound the second moment of the following sum:
Ve arg min ||u 0'112 n' C'CCnov (A)
which satisfies (v- TT S ||u -u--u
-olleeli vella I Ke since
r' E [0, 1jKk We can decompose the regret as
27
Σ
Enperpp (O))
T'
+ (v. - -p
E
0
2
S <TK + E Σ (c.- (') pt
(7)
Σ (m)
Eneingt [u.]]
+ Var
Σ of iaN
Standard OSMD analysis applied to the truncated convex hull (onv,(A) further bounds the second term in (7) as follows (see e.g. Theorem 3 in Audibert et al. (2014)).
Σ
Exinp
[15]]
+
Var(o:) (v:)
(a)
(aN
Σ
Cov(uf,eg)
T
(m))N $5
v ut) Te
E
2
Σ
Σ
x
(10)
S Slog(K/S) +
K
S <TTK+
+ n
(r:))
(8)
iEN (a)
iE
(a)
1
Then on the set U
=
[K],U, we have
To bound the last term, we first use the non-nigativity of fs. defined in (3), to further decompose it:
T
E
Σ
Σ
(F:)2
agt
Σ
T
K
(72)
2
Σ> Σ
K 2 (1 - =2)²
EieNunte) 110 = 1] 27
E
1=1 a=1
EvEN of
[=1 agU
T
K
T K
z 1 + (+t)²)
< ST +
a (Ft)2
(10)
T
1
E
1+
Σ EieNun(o) x.
[=1 aqU
(A)
T
Now we proceed to bound term (A). Recall that G is strongly
E
x
1+
EspUiteNnto 24)
observable, and let U = {a E [K] : (a, a) & F. be the set
t=l agU
6

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
(c) < T
[4K'))
two cases, OSMD with the mean condition (in Lemma 1.2)
S
4a log
(11)
ECt
alone is sufficient achieve the near-optimal regret.
Then, one may naturally ask if the vanilla OSMD-G with only the mean condition still achieves this improved rate, i.e. when it only guarantees Eptrpp [v'] = x'. The answer is negative.
Here (c) uses Σ ny S S, Lemma F.2 on the restricted subgraph Glue, and the fact that a(G (re) = a(G) = a. Combining (9) and (11) yields
K
Theorem 3.4. Fix any problem parameters (K,S,a,) T) with Sa S K, S S K and ' z max a²), and con- sider the full decision set A. There exists a feedback graph G ([K), and sampling scheme p' that satisfies E Eytrp' [o'] =x] such that
4KS
E
(P:)
6TS 4Ta log
(12)
EQ
2.
a=1
Finally, combining (12) with (8), end up with the desired upper bound
E[[gAgg 1)] ScKT + Slog(K/S)
sup B[R(To)] = ((SVaTT) (r*)
"
+ n66 + 4a log( (log((K/////) ((aa))
where To denotes OSMD-G equipped with this p' and mirror mapping F(x) = Ei= (xr, log xq - x.).
Note that at each time t and for each arm E [K], the total number of arms that observe a is random variable due to the random decision v'. In (10) in the proof above, one can naively bound the second moment of this random variable by
Proof. The core idea of this proof is that, for some and p', running the vanilla OSMD-G on this problem instance is equivalent to running OSMD on a multi- bandit with rewards ranging in [0, S]. Without loss of generality, assume K nSS' for E N. By assumption S n.
E
Σ
of
SE
First, we construct the graph G. Let Vi...., Vn partition the nodes [K] each with size S, and let H = ([n). E,,) be an arbitrary graph on n nodes with independence number a = a. Then we let (a, b) E E iff either a, b E V, or a V,, b Vj. and (V,, V2)) En, i.e. each V2 is a clique and H is graph over the cliques.
(a)
LiEN
since ||00 S. S, which leads to an upper bound (S We will see that this rate is sometimes not improvable for certain proper decision subsets Ao S A later in Section 5.1.
To improve this bound for A, we need to further exploit the structures of the full decision set A and the sampling distribution p' of v², which motivates Lemma 1.2. The negative correlations therein allow us to decompose this second moment into the squared mean and a sum of the individual variances, as in (10). By saving on the O(K²) correlation terms, this decomposition shaves the factor in (10) from Sa S+a, yielding the desired result Ö(SVT+ VaST).
For clarity, we denote the mean condition
Bytng' [o"] = x²
(M)
and for vector E R we say q aligns with the cliques if
aa - a = (VV)), ba Vi e
(AC)
Now we consider a sampling scheme p' as follows: (1) af satisfies (AC), then let ot V, with probability x' (V));;; (2) otherwise, use any distribution p' satisfying (M). Note that (I) gives a valid distribution over the cliques and satisfies (M). We will show via an induction that if r" satisfies (AC)
Remark 3.3. turns out that when $ 2 and G is strongly observable, the presence of the nodes with no self-loop can be easily handled in this upper bound analysis, whereas the case S proved in Appendix C requires more care. This matches the intuition that, when S 2 2, the learner always observes the entire subset U at every time I. Therefore, the extension from U = Ø to |U| > 1 does not add to the difficulty in learning.
for all t E [T]. then (2) never happens. As the base case, the OSMD initialization x! k satisfies (AC).
For the inductive step, when xf satisfies (AC), we have v' Vi for some i and thereby satisfies (AC). By construction of G, the reward estimator f also satisfies (AC). Given the negative entropy mapping F, straightforward computation shows that both w'+1 and r'+1 satisfy (AC), completing the induction. Consequently, we have v² = Vi, for some
3.3. The necessity of negative correlations
The previous section shows an improved performance for OSMD-G when of has negative correlations, which is a requirement never seen in either the semi-bandit feedback or the full feedback in previous literature. In either of the
IIf S does not divide K, one can put the remainder nodes in one of the cliques and slightly change the sampling p to draw uni- formly within this clique, while maintaining the mean condition.
7

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
de E [n] when o' satisfies (AC) for all & E [T]. Namely, OSMD-G now reduces policy running on n-armed bandit with feedback graph H, and now the lower bound of the latter can apply.
On the other hand, thanks this special structure, there is feedback graph that consists of K cliques, each with na nodes. Then we can exploit it using Algorithm I proposed in this work. Applying Theorem 1.1 leads to the regret @ (T) (when K 2 S: otherwise it is ( (SST)), which is near-optimal when na = for S((K) arms following Theorem 1.3, Remarkably, although each arm has a different "consumption" capacity, the regret characterization remains the same. This crucially relies on exploiting the feedback structure present in this equivalent formulation.
From the lower bound of the multi-armed bandits with feed- back graphs (see e.g. Alon et al. (2015)), there exists a set of reward sequences (e)) with some index set I and h' (i) [0, S\" such that
E (n- [ (J.MAB(T))) = ((SVaT)
for any policy ग, where (y) denotes the multi-armed bandit regret when the reward sequence is (,,())) Define the clique-averaged reward sequences by r (i)
5. Extension to general decision subsets
5.1. When negative correlations are impossible
AEG) [0, 1] for a E V2 for each j J. Since (AC) is TK
So far, we have shown the optimal regret @(SVT+VaST) on the full decision set A. Our upper bound in Theorem 1.1 fails on general decision subsets Ao S A., because it is not always possible to find distribution p' for the decision o in OSMD-G that provides the negative correlations in Lemma 1.2. For example, when there is pair of arms (a, b) with v/- = up for all v E Ao. it is simply impossible to achieve negative correlations.
guaranteed, we have
sup B [[(())))) 2 Ryy (r*)
((SVaT)
where Ry((T) denotes the regret for this vanilla OSMD-G To under reward sequence {r' (e)))))
We remark that Theorem 3.4 does not directly show the necessity of negative correlations, even though they are suf- ficient as shown by Theorem 1.1. It only says that the mean condition alone is insufficient when dealing with general graph feedback, despite its success in the existing literature. It is possible that imposing extra conditions other than nega- tive correlations can also lead to the near-optimal regret.
This failure, however, is not merely an analysis artifact. In the following, we present an example where moving from the full set A to proper subset Ao S A provably increases the optimal regret to @(min[SvaT, VKST)) when S < K. This argument is very similar to the proof of Theorem 3.4.
2
We first consider the case Sa S K. Assume again S S K and S divides K. We let V1, Vg...., VKyS be a partition of the arms [K] of equal size S. For the feedback graph G. let each V, be clique for i = I...., K....,,KSS. Let H (IVi.... VKys}, }. E) be an arbitrary other graph over the cliques such that (V,, V₁) F H iff (a, F for all Vi and b E V, in G. The independence numbers (GG) ()) are equal. On the full decision set A, Theorem 1.1 and 1.3 tell the optimal regret is @(SVT + VaST).
4. Solving semi-bandits with general capacity
In this section, we introduce a natural extension of combina- torial semi-bandits and show how we derive a near-optimal regret by applying the graph feedback. Specifically, con- feedback where the learner observes (vará a E [K]], but now each arm a can be selected for at most n. 2 1 times, i.c. the decision set becomes
sider the
A {u E [m1] x [nz] x... x [mx]: : ||u||2 = 5).4
Now consider proper decision subset
Existing results do not directly apply to this extension. Instead, one can consider the equivalent problem with N = Σx= na arms by having nh copies of arm a for each a E [K] with the special structure that r a(() = =ral for all t E [T'] and j.j E [Rel. when {a(i) : E [na]}
Apanition = {1 15+1:25. 1K-5+
(13)
where (Iuz)s = 1l: S k S j] is one on the coordinates from i to j and zero otherwise. Namely, the only feasible decisions are the first S arms in V1, the next S arms in V2, ... and the last S arms in V VK/S- It is straightforward to see that this problem is equivalent to a aumti--rmedd bandit with K/S arms and feedback graph H, and the rewards range in [0, From the bandit literature (Alon et al., 2015), the optimal regret on this decision subset Apunitioon is ((Sv which is fundamentally different from the result for the full decision set, even under the same feedback graph.
are the copies of a. If we simply take the upper bound for the bandit feedback from Audibert et al. (2014)
and ignore this structure, we arrive at regret ÖVNNST) =
δ (VV
K ST E* The
'As& a motivation, consider dynamic allocations with S units of resource at each time, and the K arms have different capacities for the amount of resource they can consume and transform to utility. Their capacities can even be vare-narying, by Theorem 1.1.
On the other hand, if So > K, similar construction fol-
8

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
lows, except that some of the grouped nodes V2 are no longer cliques in order satisfy a(G) a, and that the graph H has only self-loops. Then ai a(f)- = - and the regret is ((vKST) To formalize this statement:
In addition, while Chekuri et al. (2009) focuses on matroids. the proof of their Theorem 1.1 only relies on the following exchange property of a decision set Ag: for any v, u E Ao. there exist i E u v and j E v such that u - {z} + [i), - ( + {i) E Ao- Lemma 1.2 remains valid for any such Ag. Here we provide an example of A S A that satisfies this property:
Theorem 5.1. Fix any problem parameters (K, S, T) with Sa < K, S S K and T 2 max(S, a²) There exists 2'
decision subset An & A such that
Consider the problem that the learner operates on S systems in parallel, and on each system he/she has K2 arms to choose from. Then K = SS([ K, and the feasible deci- sions are Ao {(11,..... us) vs E [K,]]- is clear that this Ag satisfies the exchange property above, and hence OSMD-G and Theorem 1.1 apply directly to such problems. The independence number a can be small if there is shared information among the S systems.
R (Ao) 2 (innmiinSaa (ATT,VVKT) VKST))
where R* (Ao) denotes the minimax regret, as defined in (2), on this subset Au.
Given this (counter-Jexampler the following upper bound is of interest:
Theorem 5.2. On general decision subset Ao S A where only the mean condition is guaranteed, the algorithm OSMD-G achieves
5.3. Other open problems
Weakly observable graphs: The results in this work focus on the strongly observable feedback graphs. A natural ex- tension would be the minimax regret characterization when the feedback graph G = ([K), F)) is only weakly observ- able, Recall that when S = 1, Alon al. (2015) shows the optimal regret is 6(5) /372/3)
E[R(Alg 1)] 1 =)]=
In particular, when Sa K, one can ignore the graph feed- back and directly apply OSMD. The combination of OSMD and OSMD-G then guarantees (min(SVaT,
To get taste of it, consider a simple explore-then-commit (ETC) policy under stochastic rewards: the learner first ex- plores the arms in minimal dominating subset as uniformly as possible for To time steps, and then commit to the S em- pirieally best arms for the rest of the time. 5 Its performance is characterized by the following result.
For any target x' E (ony(An), there is always a proha- bility distribution p' such that Ent-pe [u*] = =²,, which is used in earlier works (Koolen al., 2010; Audibert al., 2014). With this choice of p¹, OSMD-G achieves the re- gret in Theorem 5.2. The proof follows from Section 3.2 and is left to Appendix E. Together with the construction of Apartiionn in (13), it suggests that leveraging the negative correlations, whenever the decision subset Ap allows, is crucial to achieving improved regret Ö(SVT + VaST).
Theorem 5.3. With high probability, the ETC policy achieves regret Ö(ST2/3 - -1//32/332/13
When S = 1, this policy is near-optimal. We briefly outline the proof here. When d' 2 S, thanks to the stochastic assumption and concentration inequalities, each one of the S empirically best arms contributes only a sub-optimality of order ((V8/ST,) with high probability. Trading off To in the upper bound STo + 5T/(T/ gives the bound / /3/33/333 When 8 < S, similar analysis yields the bound (SST2/3).
We will see examples of Ao where negative correlations are guaranteed in the next section.
Note on general Au. the efficiency of OSMD-G is no longer guaranteed; see discussions in Koolen et al. (2010); Audib- ert et al. (2014). To compensate, we provide an efficient elimination- based algorithm that is agnostic of the structure of the decision subset Ao and achieves ((SvaT) when the rewards are stochastic. The algorithm and its analysis are left in Appendix D.
Problem-dependent bounds: With the semi-bandit feed- back and stochastic rewards, Combes et al. (2015) proves
5.2. When negative correlations are possible
problem-dependent bound Ö [KVS where Amin denotes Amin
This section aims extend the upper bound in Theorem 1.1 to some other decision subsets Ao S A. First, by Theorem 1.1 in Chekuri al. (2009), Lemma 1.2 and OSMD-G can be generalized directly to any decision subset Ab C {u E {0, 1]K; ||o/|1 < S} that forms matroid. Notably, matroids require that decisions with size less than S are also feasible, hence they are different from the setup Ay S A we consider throughout this work.
the mean reward gap between the best decision and the second-best decision, or equivalently the S-th best arm and the (S + 1)-th under the full decision set A. It would be another interesting question to see how the presence of feed- back graph G helps the problem-dependee bounds.
'Wiile finding the minimal dominating subset is NP-hard, there is an efficient log( K) )apaprooximtte algorithm, which include in Appendix F for completeness.

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
Acknowledgements
Chekuri, C., Vondrák, J., and Zenklusen, R. Dependent ran-
domized rounding for matroid polytopes and applications. arXiv preprint arXiv:0909:4344 2009.
The author is grateful to Yanjun Han for very helpful dis- cussions and pointing the matroid literature. The author also thanks anonymous reviewers for pointing out a flaw in earlier version of the lower bound proof and for the advice to present an impossibility result for OSMD without negative correlations.
Chen, W., Wang, Y., and Yuan, Y. Combinatorial multi- armed bandit: General framework and applications. In International conference on machine learning, pp. 151- 159. PMLR, 2013.
Impact Statement
Chvatal, V. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233-23) 2322,,,,,, 1979.
This paper presents work whose goal advance the field of Machine Learning and the theoretical understanding of Online Learning. There many potential societal con- sequences of our work, none of which we feel must be specifically highlighted here.
Cohen, A., Hazan, T., and Koren, T. Online learning with feedback graphs without the graphs. In International Conference on Machine Learning, pp. 811-819. PMLR, 2016.
Cohen, A., Hazan, T., and Koren, T. Tight bounds for bandit combinatorial optimization. In Conference on Learning Theory, pp. 629-642. PMLR, 2017.
References
Alon, N., Cesa-Bianchi, N., Dekel, O., and Koren, T. On- line learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pp. 23-35. PMLR, 2015.
Combes, R., Talebi Mazraeh Shahi, M. S., Proutiere, A., et al. Combinatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
Alon, N., Cesa-Bianchi, N., Gentile, C., Mannor, S., Man- sour, Y., and Shamir, O. Nonstochastic multi-armed ban- dits with graph- structure feedback. SIAM Journal on Computing, 46(6): 1886-1826 2017.
Eldowa, K., Esposito, E., Cesari, T., and
N. On the minimax regret for online learning with feedback graphs. Advances in Neural Information Processing Sys- lems, 36, 2024.
Audibert, J.-Y., Bubeck, S., and Lugosi, G. Regret in online combinatorial optimization. Mathematics of Operations Research, 39(1):31-444) 2014.
György, A., Linder, T., Lugosi, G., and Ottuesák, G. The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 8(10), 2007.
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pp. 322-331. IEEE, 1995.
Han, Y.. Wang, Y., and Chen, X. Adversarial combinatorial bandits with general non-linear reward functions. In International Conference on Machine Learning, pp. 4030- 4039. PMLR, 2021.
Avadhanula, V., Colini Baldeschi, R., Leonardi, S.,
Han, Y., Weissman, T., and Zhou, Z. Optimal no-regret learning in repeated first-price auctions. Operations Re- search, 2024.
Sankararaman, K. A., and Schrijvers, O. Stochastic ban- dits for multi paalti-platfom budget optimization in online ad- vertising. In Proceedings of the Web Conference 2021, pp. 2805-2817, 2021.
Ito, S., Hatano, D.,, Sumita, H., Takemura, K., Fukunaga, T., Kakimura, N., and Kawarabayashi, K.-I. Improved regret bounds for bandit combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
Balseiro, S., Golrezaei, N., Mahdian, M., Mirrokni, V., and Schneider, J. Contextual bandits with cross-learning Mathematics of Operations Research, 4803):1677-169, 2023.
Kocák, T. and Carpentier, A. Online learning with feedback graphs: The true shape of regret. In International Con- ference on Machine Learning, pp. 17260-17282. PMLR, 2023.
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Desa-Bianchi, N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 7805):1404- 1422, 2012.
Koolen, W. M., Warmuth, M. K., Kivinen, J., et al. Hedg- ing structured concepts. COLT, pp. 93-105. Citeseer 2010.
10

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
Lattimore, T., Kveton, B., Li, S., and Szepesvari, C. Toprank: A practical algorithm for online stochastic rank- ing, Advances in Neural Information Processing Systems, 31, 2018.
Liu, Y. and Li, L. A map of bandits for e-commerce. arXiv preprint arXiv:2 107.00680, 2021.
Mannor, S. and Shamir, O. From bandits to experts: On the value of side-observations. Advances Neural Informa- tion Processing Systems, 24, 2011.
Robbins, H. E. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527-535, 1952.
Sankararaman, K. A. and Slivkins, A. Combinatorial semi- bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, pp. 1760-1770. PMLR, 2018.
Wang, Y., Ouyang, H., Wang, C., Chen, J., Asamov, T., and Chang, Y. Efficient ordered combinatorial remi-bandits for whole-page recommendation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Wen, Y., Han, Y., and Zhou, Z. Stochastic contextual bandits with graph feedback: from independence number to mas number. Advances in Neural Information Processing Systems, 2024.
Wen, Z., Kveton, B., and Ashkan, A. Efficient learning in large-scale combinatorial semi-bandits. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Pro- ceedings of Machine Learning Research, pp. 1113-1122, Lille, France, 07-09 Jul 2015. PMLR.
Zierahn, L., van der Hoeven, D., Cesa- Basa-Bianchi, N., and Neu, G. Nonstochastic contextual combinatorial bandits. In International conference on artificial intelligence and statistics, pp. 8771-8813. PMLR, 2023.

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
A. Proof of Theorem 1.3
Under the full information setup (i.e. when G a complete graph), a lower bound Q(S / log(K/S] was given by (Koolen et al.. 2010), which implies that (G) = D(S//Tlog(K/S)) for any general graph G. Note the assumption S 2 K/2 is used in their proof to reduce the K arms into an instance of multi-armed bandits with full information and | arms, which then gives the desired lower bound.
To show the second part of the lower bound, without loss of generality, we may assume a n.S for some n E N24- Consider a maximal independent I S [K] and partition it into ,,,..,, Is such that |m = n - for m [S]. Index each subset by Im 1.m. Om,n To construct hard instance, let [nx] be parameter and the product reward distribution be p ]aa[ Bern(na) where
A
if a. Om E Im for E [S]:
if a E M ) mE{[s]
if a & I.
The reward gap E (0.1/4) will be specified later. Also let P" " differ from Pa Pa } for all a Ims where u-m (ui,-..: 1m-11 O, - Us) denotes the parameter with m-th entry replaced by 0. Then the following observations hold:
1. For each u E [m]s, the optimal combinatorial decision is va(u) = {amm Jme[s) and any other e E suffers an instantaneous regret least A (u));
2. For each u or u.m. decision E A suffers an instantaneous regret at least 2 n nT];
Fix any policy ı and denote by Us the arms pulled by at time Let (t..(t) be the number of times am.j is pulled the end of time and Nm)()) Σラ= Nms(1) and No(() be the total number of pulls outside / the end of time l. Let be uniformly distributed over [n]S, [( denote the expectation under environment P", and E,[-] denote the expectation over ~ Unif ((n)s)
Define the stopping time by Tm = min min(t: (t) 2 T}}. Note that S (m)) S T + since at each round the learner can pull at most arms in In- Under any u, the regret is lower bounded by:
S
S Σ m==1
((w) [(T)) Z AB
No(T) +
Σ
Nm (T) - Nm.um (T)
= (E(")
T N Nm (T)
m=1
T
Tm Σ
m [(()) > AE(")
1 amss E vel
> AE(")
1 aamms E vel
m=1
1=1
m==1
1=1
S
= (A
Nm (Tm) - Nm,um (Tm)
Together with x + 2 max(# (x, y) we have
A
S
E (w) R(T)
B
mmxx
T
Nm. (T), Nm (Fm))
Nm am (Tm)) H
2
m=1
A
S
T
Nm.um (Tm))
2
12

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
where the second line follows from the definition of Tm- Next, lower bound the worst-case regret by the Bayes regret:
max E wE(n) [
[[())] > E, B [R(T)]
En B Nm. (Tm))
m=1
E
1 [T'
E
Nm, (Tm)l
π
Man
8
E
T
E (1)
[N um (Tm))
(14)
2
m==1
For any fixed m, u-m, and Um E [n], let Fm denote the law of Nm,um (Tm) under environment u, and Pm denote the law of Nm.um (Tm) under environment u Then
E [N um, (Tm) - ((umm) [N um (Tm)
TV
(L (Pm)
2
(b)
32A
TV
E(u m) [No(Tm) Nm. (Tm))
- 4AT B(u [No(T)] E(u-m) [Nm. (Tm)
(
Here (a) uses Pinsker's inequality, and (b) uses the chain rule of the KL divergence, the inequality (L(BBrn())]Beenn// - (p-o)² and A 10)1/4), and the important fact that T Tm. (Tm) is F -measurable. The last fact crucially allows ((1-g)
look at the KI. divergence only up time Tm-
VaST for any m [S), the policy incurs too large regret under this environment u-m and we are done. Now suppose E (No(T) < VaST for every m. By Cauchy-Schward inequality and the definition Tm.
Note that (((=)))((T))) [No So if ((u
E [N um (Tm))
<
E ) [Nm (Tm)) + 4AT
n2 n2VaST +n Σ
m(u-m) [N um (Tm))
< + +
(15)
Plugging (15) into (14) leads to
A
T+S
T+S
max E(") uE(ni =E|n|S
(R(T)
E Bu-m
T
4AT VaST +
n
n
AST
AS(T +
S)
VaST T+S
-242ST
2
2n
(6)
AST
T
4A2ST
where (c) uses the assumptions that 7 2 S, n 2 and 2T > VaST when T > a
Plugging in A 64 /77 and recalling
3 yield the desired bound
max x
(R(T))
2 1024
VaST.
Note that the constants in this proof are not optimized.
B. Randomized Swap Rounding
This section introduces the randomized swap rounding scheme by Chekuri et al. (2009) that is invoked in Algorithm 1. Note that randomized swap rounding not always valid for any decision set A: its validity crucially relies on the exchange
13

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
property that for any u, E A, there exist w'le and a' E c/u such that 1--fen {a} + {a'} E A and c {a'} + {a} E A. This property is satisfied by the full decision set A as well any subset A _ {r E {0, ||l|| S) that forms matroid. However, for general A this can be violated, and as discussed in Section 5.1, no sampling scheme can guarantee
the negative correlations and the learner must suffer ((SvaT) regret.
Algorithm 2 Randomized Swap Rounding
Input: decision set A, arms [K] target = Di i where N= |AA Initialize: t V1- for i 1 to N- 1 do
Denote c + 1i+1 and 3i + Ej=1 W/.
while * do
Pick a u/e and a' E clu such that u - {a] + {a') E and {a') + {a} e A.
With probability 3.t set c t c- {a'} + {a};
Otherwise, set + - {a} + {a'}.
end end
Output u.
C. Case S = in the proof of Theorem 3.2
In this section, present the proof of Theorem 3.2 for the special case S = 1. The overall idea is the same as in Section 3.2 but requires an adaptation of Lemma in Alon et al. (2015) to reward setting.
Proof. Let U = {a E [K] (a,a) & EJ. For the clarity of notation, let Fi be defined as in (4) and recall f* 1 ExEU siaht 2 0. Fix any A and let = arg c ||U - -1'11. The regret becomes
T
T
v vt) e
< cTT
+ E
0e w²) T
cKT
Σ
(ve
(1- -c,1)
for any G. E R when 1, where 1 E K denotes the all-one vector. Recall that F% is an unbiased estimator of r and plug in C2 = Ft, we get
T
Σ Uc w¹) v') (F* 21)
E
Σ v 0')
< EKT +E
Following the same lines in the proof of Theorem 3.2, arrive similar decomposition (8):
S Slog(K/S)
E
Σ (ve
(Ft ( 111)
(16)
11
Now for any time t, it holds that
T
ΣΣ
I (pt +
1=1 aEt'
1=1 aEth
(pt)
Am REU
Laetl
T Σ
(F2)²
(x (F?2)
1=1 1eE
1=1 NEU
ΣΣ (()
1=
14

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
where the inequality is due the non-negativity of x and fg. On the other hand, by definition of U. {a [K] 1/ (K-1Je ) it holds that 7dr I 1 (K- Then
Σ
E agti
71)
Σ Σ sa
(Fa)
agu
since - Pd [k-
0 for each & Up and Ft 2 0. Finally, for every U, it holds that
1)
since ot E Conve (A), and so E Ue for all time t. Substituting back in (16), we get
T
S (Ig((K)))
Uc w²) T (Ft x41)
E
T
T
T
+ r
Σ
Σ
x (1
- (F()
1/ - x
Σ
(Fa) 2
aeU
[=1 aEU, \U
ag
(B)
(C)
(17)
First, we bound the expectation of term (A) follows:
Eijo
1l = 1 r9)
Σija 1/ =
=1]
E
F
E
F
1- x
- x
REU
1EU
T
E
!
ST.
DEU
Note (C) can be decomposed as follows:
T
T
E
Σ Σ
(F())
=
E
2/ (1 - (1)2
S E
Σ
(1+
i=
neU
aE
T
E
+
Σ
agU
[=1
a
Since - o/ E [0, 1] in term (B), we can plug the above bounds back in (17) and get
T
< S Slog(K/S)
E
Σ
0²) T TF+ (ft- (f'==1)]
ST + E
ΣΣ 2 (F!)2
- agu
S (lg((K/S) ST T
4KS
S + 4a log
eak
where the last inequality follows from (11).
D. Arm elimination algorithm for stochastic rewards
As promised in Section 5.1, we present an Llimintiion-aaser algorithm, called Combinatorial Arm Elimination, that is agnostic to the decision subset Ag and achieves regret ((S (oT).. We assume the reward rf [0, 1] for each arm E [K]
15

---

Adversarial Combinatorial Semi-bandits with Graph Feedback
Algorithm 3 Combinatorial Arm Elimination
Input: time horizon T, decision subset Au S A, arm set [K], combinatorial budget S, feedback graph G, and failure
probability& e E (0,1). 1).
Initialize: Active set Aact <- Ao. minimum count N <-
Let (Fa, m() be the empirical reward and the observation count of arm a E [K] time t.
For each combinatorial decision Aact. let F Eaev Fá be the empirical reward and nt minag u ni be the minimum observation count.
for f = to T do
Let AN < {u E Aact n ] be the decisions that have been observed least.
Let Gn be the graph G restricted to set U. = {a [K] 3e E AN with E w} UpEAN v. Let a, Ug be the arm with the largest out-degree (break tie arbitrarily).
Pull any decision tú E AN with dę U2. Observe the feedback {rá E (v:) and update (f:: accordingly.
if mingEAN n > N then
Update the minimum count N +- mingeA.s n..
Let Fr max + ma Fy be the maximum empirical reward in the active set. Update the active as follows:
Anct t { v {Wr Anct v1 2 F
6 log (T ) logi (T//6)
end
end
i.i.d. with time-invariant mean 14- The algorithm maintains active set of the decisions and successively eliminates decisions that are statistically suboptimal. It crucially leverages structured exploration within the active set Aact In the proof below and in Algorithm 3, for ease of notation, we let E An denote both the binary vector and the subset of [K] it represents. So E v S [K] if ea =
Theorem D.1. Fix any failure probability e E (0, 1). For any decision subset Ao S A. with probability at least 1 - e, Algorithm 3 achieves expected regret
E[R(Alg 3)] = Ō( S/log(KTTejj(T)
Proof. Fix any (0, 1). For any n 2 denote A, log(("? log( (KT/e)/) (let Ao 1 for simplicity). During the period of N n, by Lemma F.6, with probability at least e, we have Frr. Mal I An for any individual arm E U, any time f. In the remaining proof, we assume this event holds. Then the optimal combinatorial decision v, is not eliminated at the end of this period, since
PL 2.. - SAn Mmax - SAA, pl max 22SA..
In addition, for any Auct, the climination step guarantees that
t/ 2 pt. SAA, pt 35A, 2 pf. 3SA, Nv. -4SA.-
(18)
Let Ta be the duration of N n. Recall that a, Ue has the largest out-degree in the graph G restricted Us. By Lemma F.1 and Lemma F.3, are able to bound T,;
T, < (1 + loo(oo)(((GG)) < 50log(K)) ()) log(K))a 50
log(K))a (og(k)))))))))))) M.
By (18), the regret incurred during T, bounded by 4SA, Tr. Thus with probability at least e, the total regret upper
16

---

Adversarial Combinatorial Semi-bandiss with Graph Feedback
bounded by
2 [|R(Alg 3) - STo + 44 Σ
AnTa
R=1
T/M
S S.M + 48
Σ A M
- SM + 12SM llgg(T)) (og(KT/e)VTTM
< SM / loT(
< SM + 60 60 (1 + (ogg
E. Proof of Theorem 5.2
The proof of Theorem 5.2 follows that of Theorem 3.2. The only difference is that the correlation condition of of is no longer guaranteed on general Ao- Now we can only bound (10) E becomes
(Eien (a) (f)o))) ot)
< SB Eienu ut] Then (11)
(EieMints) oz)
T
E
T
SE
E 2g
agt
(EieN((a) 15
agu
Σ EveNuiaa 19)
EiENin(a) 21
1= a
[ieNaa(o) 21
xt
S
Σ ZiE Ninaa 2
agU
S
(i
24
4K
4So T log
where (a) by [|u2 1 s and (b) uses Lemma F.2. Plugging this back to (11) in the proof of Thcorem 3.2 yiclds the first
bound. When the feedback graphs are vareing one gets instead δ S /VVLL, 01
F. Auxiliary lemmas
For any directed graph G (V, E), one can find a dominating set by recursively picking the node with the largest out- (break tie arbitrarily) and removing its neighbors. The size of such dominating set is bounded by the following lemma:
Lemma F.1 (CChvatal, 1979)). For any graph G (V, E), the above greedy procedure outputs a dominating set D with
DI < (1 + log V))((G).
Lemma F2 (Lemma 5 in (Alon et al., 2015)), Let G = ([K), E)) be directed graph with i E Nout for all E [K], Let wy be positive weights such that w; 2 e >iE[k] wi for all i E [K] some constant E (0, 1). Then
Σ iE|K]
wi
4ax log
4K
E
ac
17

---

Adversarial Combinatorial Semi-bandiss with Graph Feedback
Lemma F.3 (Lemma 8 in (Alon al., 2015)). For any directed graph G (V, E), one has 8(G) S 50a(G) log V Lemma F.4. Let F - R a convex, differentiable function and C Rdd be an open convex subset. Let Vi O.
arg me F(x). Then for any y D. x.-xx.'VV(
Proof. We will prove by contradiction. Suppose there is y D with (y VF)))) < 0. Let ((t F(x, + + x.)) fort E [0, 1] be the line segment from F(x.) Fly). We have
(1) (y x., x.-.,."'PPL VF, + ((y-xx))
and hence z'(0) = (y) x.) (z. O. Since open and F is continuous, there exists t small enough such that =(t) < =(0) Fxr.), which yields contradiction.
Lemma F.5 (Chapter 11 (Cesa- Bisachi & Lugosi, 2006)). Let F be a functionnn on open convex set D C R Then F F and V F* (VF)-1. Also for any x; D
DF Dr- VFF())
Lemma F.6 (Lemma in (Han al., 2024)). Fix any E (0, 1). With probability least c, it holds that
log(27) (TT) (KT/c)
F/ -Mal S 3/
for all a E [K] and all t [T].
18


Reviews:
[{"review_id": "tXxjOx5Rfh", "reviewer": "Reviewer_nVDS", "summary": "The paper studies the problem of semi-bandits, aiming to generalize bandit feedback and the full-information setup into a single framework. The problem is formulated as follows: Given a graph $G=(K,E)$, where $K$ represents the number of vertices and \n$E$ is the set of edges, consider a $K$-armed bandit problem. If the learner selects an arm \n$a\\in[K]$], they receive all the rewards associated with the neighbors of arm $a$ in $G$. When $G$ is a complete graph, this setting corresponds to the full-information setup, and when $G$ only contains self-loop edges, the feedback procedure corresponds to a standard multi-armed bandit problem.\n\nIn the full-information setup and multi-armed bandits (the two extreme cases), the problem is well understood. The main objective of this paper is to bridge the gap between these two cases by providing upper and lower bounds that characterize the minimax regret based on the properties of $G$. The paper establishes a lower bound and, under the assumption that there exists a probability density function over the decision set with certain correlation properties (outlined in Theorem 3.2), proposes a mirror descent-type algorithm that achieves a matching upper bound. Furthermore, the authors discuss the necessity of the correlation property of the probability density function in the final section of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We truly appreciate the reviewer's review and inspiring questions. Please see the following for our updates in light of the review and our thoughts:\n- We appreciate the review's point on the readability and in our revision, we have added a few sentences on $S$ and the fact that $S>1$ corresponds to enlarging the selection budget of the learner in the classic multi-armed bandit case. We also add the definition of independent and dominating subsets in Section 1.3.\n\n\n- Q1 is an important question and requires answers from 2 aspects:\n1. Suppose the graph $G$ is given. It is known to be NP-hard to find $\\alpha$ for any $G$. However, one can substitute any upper bound of $\\alpha$ into the algorithm and the results remain valid. More importantly, in many applications, $\\alpha$ is (perfectly or approximately) known due to the problem structure. For example, in online advertising with the winner's bid revealed [1] or inventory control, the feedback graph is known to have $\\alpha=1$, and thus the change from $K$ to $\\alpha$ is significant.\n2. If $G$ is not known but fixed. It takes the learner $K$ rounds to pull every node to know $G$ and pay $K$ regret, so our results still hold. Suppose $G$ is not known and is time-varying and $G_1,...,G_T$ are chosen adversarially. When the rewards are adversarial as in our case, [2] shows a lower bound $\\Omega(\\sqrt{KT})$ for $S=1$, i.e. no graph information can be leveraged, so we do not expect an improvement in our $S>1$ case either. When the rewards are stochastic, [2] shows a bound $\\widetilde{O}(\\sqrt{\\alpha T})$, so it is interesting to see if similar improvement is possible for the combinatorial case with stochastic rewards.\n\n- Q2: To the best of our knowledge, first-order bounds in the presence of feedback graphs are still unexplored even in the multi-armed bandit setting ($S=1$), and we do not have much to say in this even harder combinatorial setting for now. Meanwhile, under stochastic rewards, instance-dependent bounds are possible, and how to leverage $G$ there would be an interesting future direction.\n\n- Q3: We choose to work with negative entropy only because it is relatively common. It is yet known that (related to Q2) log-barrier leads to first-order bound in the MAB setting. Thus there may be practical advantages or theoretical advantages if one is interested in the first-order bound.\n\nWe thank the reviewer for the review and welcome any follow-up questions or suggestions.\n\nReferences:\n\n[1] Han, Yanjun and Weissman, Tsachy and Zhou, Zhengyuan. Optimal no-regret learning in repeated first-price auctions. Operations Research 2025.\n\n[2] Cohen, Alon and Hazan, Tamir and Koren, Tomer. Online learning with feedback graphs without the graphs. ICML 2016.", "claims_and_evidence": "All claims in the paper have been completely addressed.", "methods_and_evaluation_criteria": "The method and evaluation criteria make sense.", "theoretical_claims": "I have checked the correctness of the proofs in the main body of the paper. The theoretical claims are well-supported, and the methodology is sound.", "experimental_designs_or_analyses": "The paper is theoretical, so no experimental design has been considered.", "relation_to_broader_scientific_literature": "The contribution of the paper is related to the bandit framework and online machine learning setup, which has been addressed by the authors.", "essential_references_not_discussed": "I do not have in mind any essential references that the authors did not discuss.", "other_strengths_and_weaknesses": "The paper appears theoretically solid. I have some comments regarding the presentation, which I will address in the next section.", "other_comments_or_suggestions": "1. I believe the authors should elaborate more on some definitions that were mentioned in the paper. This would enhance the readability of the paper: $S$ on the first page, defined as the size of the combinatorial decisions.\n\nIt would also be helpful if the authors provided the definition of independent and dominating subsets in Section 1.3.", "questions_for_authors": "1. The algorithm requires knowledge of $\\alpha,$ as it provides the sufficient information the learner needs about the graph \n$G$. Do the authors have any comments or insights on adaptive methods where the learner has no prior information about \n$G$?\n\n2. Do the authors have any comments on problem-dependent bounds, such as a first-order regret bound?\n\n3. Have the authors explored other regularizers for the mirror map, such as Tsallis entropy or the log-barrier function? Is there any advantage to using negative entropy, as stated in the current algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8ondYjjxzd", "reviewer": "Reviewer_bn5t", "summary": "The paper extends the standard combinatorial semi-bandit problem by incorporating a feedback graph $G$ that allows the learner to observe rewards not just from the arms selected in the combinatorial action but also from their neighbors in $G$.\nThe authors show that the optimal regret scales as $S\\\\sqrt{T} + \\\\sqrt{\\\\alpha ST}$ ignoring logarithmic factors, where $S$ is the combinatorial action size, $\\\\alpha$ is the independence number of $G$, and $T$ is the number of rounds.\nThis result interpolates between the full-information and semi-bandit feedback scenarios.\nTo achieve this regret guarantee, the authors propose an algorithm called OSMD-G that adopts online stochastic mirror descent (OSMD) with unbiased reward estimators for graph feedback and sampling distributions that ensure negative correlations among distinct arms.\nThe authors also provide a regret lower bound of the same order.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's detailed comments and, most importantly, for pointing out our error in the lower bound. We have the following updates in our revision in light of the review:\n- We have corrected the lower bound. Specifically, we now construct $S$ independent sub-problems by an $S$ dimension index $u\\in[n]^S$ (while previously they were correlated through single index $u\\in[n]$) and apply the stopping time argument in Theorem 2 of [1] to establish the exploration-exploitation tradeoff for each sub-problem. Regarding the KL chain rule, it is crucial (as in many previous works, e.g. [1, 2]) that our quantity of interest only depends on the observed rewards, so the distribution of the $m$-th sub-problem only differs when the node $a_{m,u_m}$ is observed. This refinement leads to the bound $\\sum_{m=1}^S\\mathbf{1}[a_{m,u_m}\\in N_{out}(v^t)]\\cdot \\Delta^2$ instead of $S\\cdot \\Delta^2$.\n- We have removed the assumption on self-loops for $G$ and extended our results to general strongly observable graphs. The extension is done via an adaptation of the efforts in [3] to our reward setting. Additionally, we have clarified our claim statements to specify that they apply to strongly observable graphs rather than arbitrary graphs.\n- To address concerns about the practical applicability of our results, we will add a section to explain how $\\widetilde{O}(S\\sqrt{T} + \\sqrt{\\alpha ST})$ applies to a subclass of decision sets satisfying this exchange property: for any $v,u\\in\\mathcal{A}_0$ there exist $i\\in v$ and $j\\in u$ such that $v-\\{i\\}+\\{j\\}$ and $u-\\{j\\}+\\{i\\}$ are in $\\mathcal{A}_0$. For example, this subclass includes multi-platform online advertising.\n- While it is true that general $\\alpha$ is NP-hard to compute, in many practical applications, $\\alpha$ (or any upper bound) is known due to the problem structure. For example, in online advertising with the winner's bid revealed [2] or inventory control, the feedback graph is known to have $\\alpha=1$, and thus the change from $K$ to $\\alpha$ is significant. Beyond practical applications, our contribution also includes a theoretical understanding of the optimal regret characterization in the combinatorial setup, including both the $\\widetilde{\\Theta}(S\\sqrt{T}+\\sqrt{\\alpha ST})$ characterization on the above subclass of decision subsets and the impossibility result in Section 4.1.\n- We are grateful to the reviewer for the detailed comments and corrected typos and have carefully addressed them in the revision.\n- The references mentioned by the reviewer are indeed relevant and have been added to the revision.\n- By \"tabular\" contextual bandits, we refer to the contextual bandits without additional structures (e.g. linear contextual bandits) that only treat the contexts as general variables affecting the rewards. \n\nOnce again, we deeply appreciate the reviewer’s insightful feedback, which has helped us refine and strengthen our work.\n\nReferences:\n\n[1] Lattimore, Tor and Kveton, Branislav and Li, Shuai and Szepesvari, Csaba. TopRank: A Practical Algorithm for Online Stochastic Ranking, NeurIPS 2018.\n\n[2] Han, Yanjun and Weissman, Tsachy and Zhou, Zhengyuan. Optimal no-regret learning in repeated first-price auctions. Operations Research 2025.\n\n[3] Alon, Noga and Cesa-Bianchi, Nicolo and Dekel, Ofer and Koren, Tomer. Online learning with feedback graphs: Beyond bandits. COLT 2015.", "claims_and_evidence": "Most claims in the paper are supported.\nHowever, some are stated without providing enough intuition as to why they would be correct.\nFor instance, stating that the results assuming all self-loops in $G$ immediately extend to all strongly observable feedback graphs (e.g., see line 117) is not necessarily true.\nEven for standard (non-combinatorial) bandits with feedback graphs, extending the analysis to general strongly observable feedback graphs is definitely nontrivial and requires specialized technical results for it (Alon et al., 2015).\nOne may therefore be convinced that it is even more nontrivial to have an analogous extension in the combinatorial setting.\nMoreover, throughout the paper the authors often overly generalize their claims by stating they hold for \"general directed feedback graphs\" while, again, they make the assumption of including all self-loops in the graphs considered.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I examined all the theoretical claims of the submission.\nFirst, I would focus on the proof of Theorem 1.3, i.e., the regret lower bound.\nChecking the end of the proof, there seems to be some issue with the computation.\nLine 248 states that the regret $R(\\\\pi)$ of an algorithm $\\\\pi$ satisfies\n$$\n\\\\max\\_{u \\\\in [n]} \\\\mathbb{E}\\_u[R(\\\\pi)]\n\\\\ge \\\\Delta ST (1/2 - 8\\\\Delta S\\\\sqrt{T/(3\\\\alpha)})\n$$\nwhose right-hand side, replacing for the chosen value of $\\\\Delta$, becomes $\\\\frac{1}{32}\\\\sqrt{\\\\alpha ST} (1/2 - \\\\sqrt{S/48})$ which is non-positive, and thus vacuous, for $S \\\\ge 12$.\n\nAdditionally, even before that, line 194 shows a sum where each term presents a KL-divergence $\\\\mathrm{KL}(\\\\mathbb{P}_0(r^t|R^{t-1}) \\\\| \\\\mathbb{P}_u(r^t|R^{t-1}))$.\nThe issue here is that $\\\\mathbb{P}_0(r^t|R^{t-1})$ and $\\\\mathbb{P}_u(r^t|R^{t-1})$ present the entire reward vector $r^t$, and thus their KL-divergence is equal to $S \\\\cdot \\\\mathrm{KL}(\\\\mathrm{Bern}(1/4) \\\\| \\\\mathrm{Bern}(1/4+\\\\Delta))$ (by the chain rule over the coordinates of $r^t$), instead of only over $m \\\\in [S]$ such that $a\\_{m,u} \\\\in N\\_{\\\\mathrm{out}}(v^t)$.\nNonetheless, it is possible that a more careful analysis might avoid this issue.\n\nOther that the proof of the lower bound, the other results seem to hold.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The regret bound for OSMD-G follows directly from the known analysis of OSMD combined with the variance bound for feedback graphs.\nThe only technical contribution here is the design of the distribution $p^t$ to allow a reduction to the standard analysis for the variance with feedback graphs.\nThe applicability of the results also requires quite restrictive assumption that are commonly lifted in the related literature, such as the presence of all self-loops in the strongly observable feedback graph, the knowledge of the independence number (NP-hard to compute) for tuning the learning rate, and considering only the full combinatorial action space $\\\\mathcal{A}$.\nAll of these point seem to underline a rather limited contribution of this submission.", "essential_references_not_discussed": "Most of the relevant references are discussed.\nOther meaningful references on combinatorial bandits to include could be:\n- Richard Combes, Mohammad Sadegh Talebi, Alexandre Proutiere, Marc Lelarge. Combinatorial Bandits Revisited. NeurIPS 2015.\n- Alon Cohen, Tamir Hazan, Tomer Koren. Tight Bounds for Bandit Combinatorial Optimization. COLT 2017.\n- Lukas Zierahn, Dirk van der Hoeven, Nicolò Cesa-Bianchi, Gergely Neu. Nonstochastic Contextual Combinatorial Bandits. AISTATS 2023.", "other_strengths_and_weaknesses": "### Post-rebuttal edit:\n\nI thank the authors for providing detailed responses to address my concerns about the contents of their submission. I am satisfied with the responses. Provided the authors can guarantee to integrate all the modifications required to correct the issues and address the concerns pointed out in my review and the above discussion, I now have no strong reservations about the acceptance of this paper and I have updated my score accordingly.\n\nTo respond to the authors' final question about prior work without assuming knowledge of the independence number, here are a few relevant references:\n- Kocák, Neu, Valko, and Munos. \"Efficient learning by implicit exploration in bandit problems with side observations\". NeurIPS 2014.\n- Alon, Cesa-Bianchi, Gentile, Mannor, Mansour, Shamir. \"Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback\". SIAM Journal on Computing, 2017.\n- Rouyer, Van der Hoeven, Cesa-Bianchi, and Seldin. \"A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs\". NeurIPS 2022.\n- Eldowa, Esposito, Cesari, Cesa-Bianchi. \"On the Minimax Regret for Online Learning with Feedback Graphs\". NeurIPS 2023.", "other_comments_or_suggestions": "- It is good practice to avoid using a parenthesized citation when it is a subject/object of a sentence (e.g., Koolen et al. (2010) instead of (Koolen et al., 2010) in line 91).\n- Another good practice is to place footnote numbers after eventual punctuation (e.g., line 118).\n- A more standard notation for a directed edge uses an ordered pair $(a,i)$ instead of $a \\\\to i$, as $E$ is a subset of ordered pairs of nodes (e.g., in line 74).\n- The self-loops assumption is actually a crucial and important assumption, but is only mentioned as footnotes (namely, footnotes 1 and 2). It would be better to state it in the main body.\n- The type of feedback for which the learner only observed the realized payoff $\\\\langle v^t, r^t\\\\rangle$ is often called \"full-bandit\" feedback.\n- The algorithm from Alon et al. (2015), called Exp3.G, is described as an explore-then-commit algorithm while it is not (see line 71).\n- Line 75: time-varying feedback graphs are also studied in Alon et al. (2015).\n- In the statement of Theorem 1.1, underline that it holds for any directed graph $G$ containing all self-loops instead of an arbitrary one.\n- $\\\\overline D$ (with an overline) is used without being defined. Please, provide a definition for it.\n- In line 243, it would be clearer to specify that (c) holds for the concavity of the square root together with, e.g., Jensen's inequality.\n- The log factors at lines 336, 383, and 675, following from the application of Lemma D.2, is missing an $S$ multiplicative factor in its argument.\n- The square power at the expectation at lines 347, 358, and 665 should be inside the square brackets.\n\nTypos:\n- The multiplicative factor $T$ in the regret bound at line 78 should not be there.\n- Line 147: $\\\\mathcal{A}$ instead of $A$.\n- Line 198: $\\\\Omega$ should actually be $[n]$, right?\n- Line 190: $a\\_{m,u}$ instead of $a\\_{m,u\\_m}$.\n- Lines 252 and 277: occurrences of $x$ are missing a superscript $t$.\n- Line 274: $\\\\mathbb{E}[v] = x^t$ is missing a subscript $v \\\\sim p^t$, as otherwise even $x^t$ is a random variable (as similarly in multiple other places in this paper).\n- Line 348: same as line 274, but with a missing outer expectation too.\n- In the statement of Lemma A.1, quantify $S$ before using it in the definition of $\\\\mathcal{A}$.\n- Line 517: \"basis vector\" instead of \"unit vector\".\n- Line 528: $i>r$ instead of $i \\\\ge r$.", "questions_for_authors": "- Please, address the main concerns pointed out above, if possible.\n- A minor question: could you be more precise on what you mean by \"tabular\" contextual bandits (line 81)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ilQa8ForTI", "reviewer": "Reviewer_TtKB", "summary": "The authors consider the problem of combinatorial semi-bandit with feedback graphs, where a graph over the $K$ actions may provide the learner with side information during the learning process. By presenting appropriate lower and upper bounds, the authors establish a minimax optimal regret bound for graphs containing self-loops of $\\widetilde \\Theta(S \\sqrt{T} + \\sqrt{\\alpha S T})$, where $S$ is the size of a combinatorial action and $\\alpha$ is the independence number of the underlying feedback graph. For the upper bound, the authors design a natural extension of the OSMD algorithm to the feedback graph setting, with the crucial property that the sampling distributions $p_t$ satisfy a negative correlation property, which allows obtaining the optimal dependence on $S$ for this algorithm. Furthermore, the authors consider scenarios where not all combinatorial actions belong to the available action set, and show that in such settings it may not be possible to satisfy the negative correlation property, and in fact the optimal rates in such settings are worse by a $\\sqrt{S}$ factor. The authors also briefly discuss the weakly observable setting and analyze an Explore-Then-Exploit algorithm for this setting with stochastic rewards.\n\n## update after rebuttal:\nGiven the latest response by the authors, they seem to have a reasonably convincing argument showing that if negative correlations are not explicitly enforced in OSMD, the algorithm could incur suboptimal regret. Given the validity of their argument, I think that such a result significantly strengthens the contributions of the paper, and I highly encourage the authors to include it in the final version. I am now inclined to increase my score to \"Accept\".", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thorough review and comments and have done several updates in our revision in light of the review.\n- We appreciate the review spotting the issue of missing a factor $S$ in the log term. We have corrected this in our revision.\n- We agree that the lower bound is not the focus of this work (in fact, its proof was wrong as pointed out by Reviewer bn5t; we have corrected the hard instance construction and proof techniques in our revision). We will move the proof to the appendix and only briefly discuss the construction in the main text, in order to keep our focus on the upper bound ideas. Instead, we provide an intuitive reasoning for why such distributions exist, which is essentially the high-level idea of our proof of Lemma 1.2. Since the revision cannot be posted, we will paste this reasoning here for clarity:\n\nWhen $S=1$, any distributions possess negative correlations. Inductively, let us suppose such distributions exist for $1,2,\\dots, S-1$. Then for a fixed target $x\\in\\mathsf{Conv}(\\mathcal{A})$, we can always find an index $i\\in[K]$ such that $\\sum_{j=1}^{i-1}x_j + cx_i=1$ and $\\sum_{j=i+1}^Kx_j + (1-c)x_i=S-1$ for some $c\\in[0,1]$. Namely, the target of size $S$ is partitioned into two sub-targets with ranges $[1,i]$ and $[i,K]$, each with sizes $1$ and $S-1$, and with an overlap on index $i$. We can then assign $v_i=0$ with probability $1-x_i$, to the first half $[1,i]$ with probability $cx_i$, and to $[i,K]$ with probability $(1-c)x_i$. To obtain a final size $S$ solution, we draw $v'$ supported on $[1,i-1]$ with size $0$ or $1$ and $v''$ on $[i+1,K]$ with size $S-1$ or $S-2$, conditioned on the assignment of $v_i$. For any $j_1\\in [1,i-1]$, $j_2\\in[i+1,K]$, and $i$, any two of them are negatively correlated because, at a high level, the presence of one `reduces' the budget size of the other. The negative correlations among the first half $[1,i-1]$ and $[i+1,K]$ are guaranteed by the induction hypothesis of the existence of such distributions for solutions with size less than $S$. Finally, the structure of $\\mathcal{A}$ ensures that our pieced-together solution is valid, i.e. lies in $\\mathcal{A}$.\n\n- We have removed the assumption on self-loops in $G$ and extended our results to general strongly observable graphs. The extension is done via an adaptation of the efforts in [1] to our reward setting. In the discussion, we will also generalize $\\widetilde{\\Theta}(S\\sqrt{T}+\\sqrt{\\alpha ST})$ to a subclass of decision sets (including the full set) satisfying this exchange property: for any $u,v\\in\\mathcal{A}_0$, there exist $i\\in u$ and $j\\in v$ such that $u-i+j$ and $v-j+i$ remain in $\\mathcal{A}_0$. Examples include that a learner operates $S$ systems in parallel and chooses one action for each system at each time, such as multi-platform online advertising.\n- We agree that a comparison between the algorithms with/without negative correlations will be interesting and have practical value. Our focus is nonetheless on the theoretical understanding on the regret characterization, and thus we have not conducted numerical comparisons. Theoretical analyses of the two algorithms, on the other hand, require precise understandings of the trajectories of $x^t$ in OSMD-G and may be considered in future work.\n- It is definitely possible to adapt EXP3.G to the combinatorial setting for the weakly observable graphs. However, we believe the importance lies in figuring out the lower bound in the combinatorial setting (under full decision set or proper subsets). Straightforward analysis can give bounds like the one we have for ETC in Section 4.2, but they are interesting only if they turn out to be tight. In particular, in our study of the strongly observable case, preliminary results gave the upper bound $\\widetilde{O}(S\\sqrt{\\alpha T})$ and the lower bound $\\Omega(S\\sqrt{T} + \\sqrt{\\alpha ST})$ and we did not know which one was tight. It then turns out they are both tight under different decision set structures. So the interesting question, rather than generalizing EXP3.G, would be the tight characterization under weakly observable graphs, which may again depend on the decision set. We do not have a lower bound beyond the existing $\\Omega(\\delta^{1/3}T^{2/3})$ for now.\n\nAgain, we would like to thank the reviewer for the helpful feedback, and we are more than happy to answer any questions.\n\nReferences:\n\n[1] Alon, Noga and Cesa-Bianchi, Nicolo and Dekel, Ofer and Koren, Tomer. Online learning with feedback graphs: Beyond bandits. COLT 2015.", "claims_and_evidence": "The authors provide formal proofs for all of their results, contributions and technical claims. The analysis in the paper is clear and easy to follow, with many parts being very similar to analysis from previous related work.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I went over some of the proofs of the theoretical claims in the paper, and found one possible issue which probably does not affect the overall claim, but requires the authors' attention. Specifically, in the upper bound analysis, when bounding the second order term, the authors bound a term of the form $\\sum_a \\frac{x^t_a}{\\sum_{i \\to a} x^t_i}$ by an order of $\\alpha$ by referring to Lemma 5 of [1]. However, examining the conditions of this lemma, using it as is requires the sum $\\sum_a x^t_a$ to be bounded by 1, while in the combinatorial semi-bandit setting it is in fact bounded by $S$. This can be mitigated if the authors modify the optimization domain $Conv_{\\epsilon}(\\mathcal{A})$ to $Conv_{S \\epsilon}(\\mathcal{A})$ so that the iterates would satisfy $x^t_a \\geq \\epsilon \\sum_i x^t_i$ as required from the conditions of the lemma. This modification would result in a slightly worse dependence on $\\epsilon$ in the overall bound, which will ultimately affect the additive term ($\\epsilon SKT$ instead of $\\epsilon K T$) and the logarithmic term, and thus would not change the overall claim and contributions. I would appreciate it if the authors could address this issue.\n\nReference:\n\n[1] Alon, Noga, et al. \"Online learning with feedback graphs: Beyond bandits.\" Conference on Learning Theory. PMLR, 2015.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The authors discuss relevant works from both the bandits with feedback graphs literature and combinatorial semi-bandit literature. Specifically, they cite Alon et al. ('15) inwhere optimal regret bounds are established for the non-combinatiral variant of the problem, and Audibert et al. ('14) who presented the OSMD algorithm which achieves optimal regret bounds for combinatorial semi-bandits with no feedback graphs.", "essential_references_not_discussed": "When discussing full-bandit feedback, the authors do not mention previous works that prove that the optimal bounds are of the form $\\Theta(S^{3/2} \\sqrt{KT})$, shown in [1] for a specific combinatorial action set (namely, multitask bandits) and in [2] for the full action set. While the full-bandit variant is not extremely relevant to this work, since the authors mention this variant and cite some related work, they should also mention the aforementioned papers in which the optimal rates are characterized.\n\nReferences:\n\n[1] Cohen, Alon, Tamir Hazan, and Tomer Koren. \"Tight bounds for bandit combinatorial optimization.\" Conference on Learning Theory. PMLR, 2017.\n\n[2] Ito, Shinji, et al. \"Improved regret bounds for bandit combinatorial optimization.\" Advances in Neural Information Processing Systems 32 (2019).", "other_strengths_and_weaknesses": "Strengths:\n\n* The authors study a well-motivated problem which has not been studied in previous works, namely combinatorial semi-bandits with feedback graphs.\n* The authors establish optimal (up to logarithmic factors) regret bounds for this problem under mild assumptions on the feedback graph.\n* The analysis presented by the authors is clear, easy to follow, and in large parts resembles analysis of similar problems from previous works.\n* The key technical observation made by the authors, namely, that using sampling distributions with negative correlation between arms is essential in order to obtain optimal bounds, seems very interesting to me, and I'm not sure that I've seen anything similar in previous works. The fact that such sampling distributions exist also seems nontrivial.\n* The authors support the fact that the negative correlation property is crucial by exhibiting instances with a limited decision set in which this property doesn't hold, and the optimal regret bound is in fact worse by a factor of $\\sqrt{S}$.\n\nWeaknesses:\n* It seems to me that other than the key observation regarding the negatively correlated arms (specifically, Lemma 1.2 and how it is used in the proof of Theorem 3.2), the other parts of the analysis (including the lower bound) uses fairly standard techniques which are very common in related previous work. Therefore, I think perhaps this key observation is not highlighted well enough in the current version of the paper, and it is a bit lost among the other parts of the analysis which are fairly straightforward.\n* The authors mention that extending their results from graphs with self-loops to strongly observable graphs is straightforward without any elaboration. However, in previous works, specifically in Alon et al. ('15), such an extension requires some additional techniques which are not present for graphs with self-loops. I suggest that the authors either elaborate on how such an extension can be performed for their results, or alternatively remove this remark altogether.", "other_comments_or_suggestions": "* I suggest that the authors further highlight their main technical novelty regarding the negatively correlated arms, as it seems highly nontrivial and without it the rest of the techniques are pretty straightforward extensions from previous works. On that regard, I think that less focus should be given to the lower bound in the main text, as it seems pretty straightforward and doesn't include any highly novel techniques. Instead, the authors could provide further intuition and discussion on the negative correlation property, specifically, I would appreciate a high level intuition of why there must exist such a distribution, as the proof of Lemma 1.2 is quite technical and not so intuitive.", "questions_for_authors": "1. I would appreciate it if the authors could comment on the possible issue I mentioned under \"Theoretical Claims\". \n\n2. Do the authors have an example where if their algorithm OSMD.G is run without the negative correlation condition, then this algorithm can incur regret of the form $\\Omega(S \\sqrt{\\alpha T})$ even when the action set is full? I think that such an example can considerably strengthen the results, as it would imply that explicitly requiring this condition is essential for this algorithm. Given such a result, I may consider increasing my evaluation score of the paper.\n\n3. Regarding the weakly-observable case, have the authors attempted an extension of EXP3.G (Alon et al., '15) to the combinatorial setting? If so, can the authors comment on why such an extension is nontrivial?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pjDbPbCoOQ", "reviewer": "Reviewer_R6q4", "summary": "**Edit post-rebuttal: I thank the authors for their feedback, which answered my questions. I maintain my overall positive score.**\n\nThe submission considers adversarial combinatorial semi-bandits, with additional feedback, ranging from no additional feedback to full-information feedback. The two extreme cases were respectively studied by Audibert, Bubeck and Lugosi (2014, no additional feedback) and Koolen, Warmuth, Kivinen, (2010, full-information feedback). The corresponding optimal regret bounds (up to logarithmic factors) are respectively $\\sqrt{K S T}$ and $S \\sqrt{T}$, where $S$ is the number of arms played at each round and $K$ is the total number of arms. The present submission interpolates between these two extremes (both in terms of upper and lower bounds), by suggesting a model of graph-determined feedback and by stating optimal regret bounds in terms of the richness of the graph (quantified by the independence number of the graph). The two extremes are given by a graph with inner loops at each node, and no other edge, and by the complete graph. Note that the regret upper bounds also work for a sequence of adversarial feedback graphs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The detailed review and insightful feedback from the reviewer are deeply appreciated. We have done several updates in light of the review in our revision.\n- It is worth mentioning that our previous lower bound construction did not lead to the desired trade-off and was wrong. We corrected it by constructing $S$ independent sub-problems via multi-index $u\\in[n]^S$ (instead of $u\\in[n]$) and adopted a stopping time argument from [1]. The crux of the lower bound is that the learner has to learn each of the $S$ sub-problems well and independently. As an intuitive reasoning, a good learner tends to pick one arm of each sub-problem, i.e. distributes the pulls roughly evenly, because if he/she picks two, then one of the two must be suboptimal and incurs regret. This new proof will be deferred to the appendix due to space limit and that it is not the particular contribution of this work. We will provide an intuitive sketch of the proof in Section 2 that includes the remark mentioned by the reviewer at the beginning.\n- Regarding the comments on the lower bound: we may assume $\\alpha > 3S$, since otherwise $S\\sqrt{T}=\\Omega(\\sqrt{\\alpha ST})$ and we are done. Then we only need to consider the independent subset with size $\\lfloor \\alpha/S\\rfloor S=nS\\le alpha$. Note since $\\alpha > 3S$, it holds that $nS\\ge \\alpha-S\\ge \\alpha/2$, so the final bound would be the same up to a factor of 2.\n- We apologize for the confusion. $T_0$ was a typo and was meant to be $N_0$, which counts the number of pulls outside of the independent subset $I$. So the regret would be $\\Omega(N_0)$ since any node outside (while they may be more informative) incurs a constant regret.\n- We agree that the beginning of the upper bound proof overlaps with that of the earlier work. Nonetheless, it was included for the sake of rigor because we use an additional truncation on the convex hull.\n- The high probability upper bound may be a nontrivial extension and we will leave it to future work.\n- The comments are carefully addressed in our revision. In particular, there is a surjective mapping from $Conv(\\mathcal{A})$ to the probability distributions over $\\mathcal{A}$, so in this sense it is easy to obtain a distribution with mean $x\\in Conv(\\mathcal{A})$. But the requirement of negative correlations in our case is nontrivial to satisfy and, as shown in Section 4.1, is impossible for some $\\mathcal{A}$.\n\nReferences:\n\n[1] Lattimore, Tor and Kveton, Branislav and Li, Shuai and Szepesvari, Csaba. TopRank: A Practical Algorithm for Online Stochastic Ranking, NeurIPS 2018.", "claims_and_evidence": "The results are theoretical: I could not spot flaws in the proofs---though their clarity could sometimes be improved, and though large parts of the proofs could be made more concise, by using existing results; see details below.", "methods_and_evaluation_criteria": "The setting considered makes sense. The regret is only handled in expectation, and I think that high-probability bounds would have been appreciated.", "theoretical_claims": "I checked in details the main two results: Theorem 1.1 and Theorem 1.3 (based on Lemma 1.2, proved in Appendix A, whose proof I did not check in detail).  I could generally follow the derivations.\n\nTheorem 1.1\n- Could you detail (page 4, column 1, line 182) why this assumption comes with no loss of generality? It would look more satisfactory to me to rather have some of the $I_j$ contain $n$ elements and some others to contain $n-1$ elements, and write the proof in this context\n- Page 4, first two thirds of column 2: the arguments could be made more compact (and would avoir resorting to densities) by using the bound by Ménard, Garivier, and Stoltz (2019)\n- Page 4, Equation (4): first, $T_0$ is not defined (it is the number of pulls in $I$); second, I think that this is the place where you critically use the definition of $I$ as a maximal independent set and this must be detailed and commented. This is the crux of the proof, while earlier manipulations were standard\n- The remarks stated right before Section 3 are nice and should have been stated before the formal proof, as they help navigating it \n\nTheorem 1.3\n- The beginning of this proof (possibly from page 6, column 1, line 317 to page 7, column 1) could be replaced by an appeal to the bound of Theorem 3 of Audibert, Bubeck and Lugosi (2014), which actually holds for all estimators; i.e., the new part consists of the end of the proof, where, in particular, the negativity of the covariance of the $p^t$ is used", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The submission discusses all references I expected to find.", "other_strengths_and_weaknesses": "This submission provides an interesting, elegant, and optimal interpolation between existing optimal regret bounds for combinatorial semi-bandits. Most of the proof techniques were known (lower bound proof structure; pre-regret upper bound in terms of the estimates; Lemma D.2 by Alon et al., 2015) but they are well assembled and there seems to be a new ingredient provided by the representation of Lemma 1.2.\n\nOn a side note, I particularly appreciated the comments and insights throughout the text; e.g., page 3, column 2, lines 117-125, or page 6, column 1, lines 282-295", "other_comments_or_suggestions": "- Page 1, column 1, line 97: I guess this should be $\\mathbb{E}[p_a^t]$ and not $\\mathbb{E}[v_a^t]$?\n- Page 1, column 2, line 64: put the definition of $\\alpha$ and $\\delta$ before using them \n- Page 2, Lemma 1.2: do we agree that, in some sense, Conv($A$) and the probability distributions over $A$ are the same set? \n- Page 2, Section 1.3: the concepts of independent subset and dominating subset should be defined, to make the submission self-complete\n- Page 8: $\\delta$ is only used at this stage, its definition could thus be postponed here", "questions_for_authors": "I have no specific question but feedback from the authors on some points raised above (e.g., whether high-probability bounds are easy to obtain; whether indeed the application of Theorem 3 by Audibert, Bubeck, Lugosi, 2014, would indeed save 1 page, etc.) are welcome.\n\n**Edit post-rebuttal: I thank the authors for their feedback, which answered my questions. I maintain my overall positive score.**", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies adversarial combinatorial semi-bandits with feedback graphs, with the aim to interpolate regret bounds between the standard full-information and semi-bandit settings (similarly to what has been done for non-contextual bandits). 

Some errors were found during the reviewing process, but during the discussion period, the authors gave enough information to convince the reviewing team that the arguments could be fixed. With this issue resolved, I recommend acceptance under the constraints that all points brought up during the discussion period (including but not limited to the correctness of the claims) are addressed in the revised version.
Decision: Accept (poster)