Stochastic contextual bandits with graph feedback: from independence number to MAS number
Authors: Yuxiao Wen
Yanjun Han
Zhengyuan Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: contextual bandits
graph feedback
minimax rate
Primary area: bandits
TL;DR: We (1) prove a regret lower bound through a novel graph quantity that increases with the number of contexts and (2) propose algorithms that achieve tight upper bound under reasonable assumptions and a weaker one in general.

Abstract: We consider contextual bandits with graph feedback, a class of interactive learning problems with richer structures than vanilla contextual bandits, where taking an action reveals the rewards for all neighboring actions in the feedback graph under all contexts. Unlike the multi-armed bandits setting where a growing literature has painted a near-complete understanding of graph feedback, much remains unexplored in the contextual bandits counterpart. In this paper, we make inroads into this inquiry by establishing a regret lower bound $\Omega(\sqrt{\beta_M(G) T})$, where $M$ is the number of contexts, $G$ is the feedback graph, and $\beta_M(G)$ is our proposed graph-theoretic quantity that characterizes the fundamental learning limit for this class of problems. Interestingly, $\beta_M(G)$ interpolates between $\alpha(G)$ (the independence number of the graph) and $\mathsf{m}(G)$ (the maximum acyclic subgraph (MAS) number of the graph) as the number of contexts $M$ varies. We also provide algorithms that achieve near-optimal regret for important classes of context sequences and/or feedback graphs, such as transitively closed graphs that find applications in auctions and inventory control. In particular, with many contexts, our results show that the MAS number essentially characterizes the statistical complexity for contextual bandits, as opposed to the independence number in multi-armed bandits.

Stochastic contextual bandits with graph feedback: from independence number to MAS number
Yuxiao Wen Yanjun Han'
Zhengyuan Zhout."
New York University" Arena Technologies
(yuxiaowen, jaanjunhanJonyu edu zz260stern.nyu.ce nyu. edu
Abstract
We consider contextual bandits with graph feedback, class of interactive learning problems with richer structures than vanilla contextual bandits, where taking an action reveals the rewards for all neighboring actions in the feedback graph under all contexts. Unlike the multi-armed bandits setting where a growing literature has painted near-complete understanding of graph feedback, much remains unexplored in the contextual bandits counterpart. In this paper, we make inroads into this inquiry by establishing regret lower bound 52( (2(1311/ (ar (G)T), where M is the number of contexts, theoretic quantity that characterizes the fundamental learning limit for this class problems. Interestingly. 3M (G) interpolates between (G) (the independence number of the graph) and m(G) (the maximum acyclic subgraph (MAS) number the graph) as the number contexts M varies. that achieve near-optimal regret for important classes of context sequences and/or feedback graphs, such as transitively closed graphs that find applications in auctions and inventory control. In particular, with many contexts, MAS number essentially characterizes the statistical complexity for contextual bandits, opposed to the independence number in multi-armed bandits.
the feedhack graph, and 3ar (G) is our proposed graph-
also provide algorithms
results show that the
Introduction
Contextual bandits encode rich class of sequential decision making problems in reality, including clinical trials. personalized healthcare, dynamic pricing, recommendation systems (Bouneffouf et al.) 2020). However, due to the exploration-exploittii pace of learning for contextual bandits could be slow, and the statistical complexity of learning could be costly for application scenarios with bandit feedback (Agarwal et al. (012)). There are two common approaches to alleviate the burden of sample complexity, either by exploiting the function class structure for the reward (Zhu and Mineiro 2022). by utilizing additional feedback available during exploration.
trade-off and a potentially large context space,
In this paper we focus on the second approach, and aim to exploit the feedback structure efficiently in contextual bandits. The framework of formulating the feedback structure as feedback graphs in bandits has long history (Mannor and Shamir 2011 Alon et al. 2015 2017 Lykouris et al. 2020), where a direct edge between two actions indicates choosing one action provides the reward information for the other. Such settings have also been generalized to contextual cases (Balseiro) et al., 2019) Dann et al.) 2020 Han et al., (024), where counterfactual rewards could be available under different contexts. Typical results in these settings are that, the statistical complexity of bandits with feedback graphs is characterized by some graph-theoretic quantities, such as the independence number the maximum acyclic subgraph (MAS) number of the feedback graph.
To understand the influence of the presence of contexts on the statistical complexity of learning and to compare with multi-arma armed bandits, we focus on the tabular setting where the contexts are treated as
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

general variables determining the rewards. A widely studied alternative is the structured setting that leverages certain structures in the dependence on the context. Examples of the latter include linear contextual bandits (Auer, 2002 Agrawal and Goyal 2013). which assume a linear reward function on the contexts, and their variants (Chu et al. [011 Li al. 2017 Agrawal and Devanur 2016).
Despite the existing results, especially in aamed bandits where a near-complete characterization of the optimal regret is available (Alon et al. 2015 Kocák and Carpentier 2023 Eldowa et [024]
the statistical complexity of contextual bandits with feedback graphs is much less understood. For example, consider the case where there is feedback graph G across the actions and a complete feedback graph across the contexts (termed as complete cross-learning in (Balseiro et al. 2019)). In
this case, for a long time horizon T, the optimal regret scales @( (((()) when there is only one context (Alon et al. 2 but only an upper bound ( mmGT)) is known regardless of the number of contexts (Dann et al. 2020). Here (G) and m (G) denote the independence number and the MAS number of the graph G. respectively; we refer to Section T.T for the precise definitions. While a(G) m(G) for all undirected graphs, for directed graphs their gap could be significant. It is open the change from (G)) to m(G) is essential with the increasing number of contexts, not to mention the precise dependence on the number of contexts.
1.1 Notations
For n E N. let [n] = .1]. For two probability measures P and Q over the same space, let TV(P.Q) Q) = dQ//2 be the total variation (TV) distance, and (L()))Q) I (oloooldPPPdl be the Kullback-Leibs as Ö, ê to denote respective meanings within polylogarithmic factors.
(KL) divergence. We use the standard asymptotic notations O, 52, θ, as well
We use the following graph-theoreds notations. For directed graph G = (V, E), let + v denote that (u,)) E E. For u E V, let Nout (u) = (v E V : u + e be the set of out-neighbors of (including u itself). We will also use (o)((A) = A (v) to denote the set of all neighhigs of vertices in A. The independence number (GG), dominating number 5(G), and maximum acyelic subgraph (MAS) number m m() are defined as
((G) = max [[T I S V an independent set, i.e. u f v, Vu # E T), 8(G) = min
[|]] min[[]]
J C V is dominating set, i.e. Nout (J) V}.
m(G) = max{ : D C V induces an acyclic subgraph of G},
respectively. It is casy to show that max(a(()) ((G) < (G), with a possibly unbounded gap, and probabilistic argument also shows that 8(G) (a log VV) (cf. Lemma A.Ip.
1.2 Our results
In this paper we focus on contextual bandits with both feedback graphs across actions and complete cross-learning across contexts. This setting was proposed in (Han et al. 2024), with applications to bidding in first- auctions. As opposed to an arbitrary feedback graph across all context-action pairs in (Dann et al. 2020), we assume a complete cross-learning because of two reasons. First, in many scenarios the contexts encode different states which only play roles in the reward function; in other words, the counterfactual rewards for all contexts can be observed by plugging different contexts into the reward function. Such examples include bidding in auctions (Balseiro et al.) 2019 Han et al. 2024) and sleeping bandits modeled in (Schneider and Zimmert 2024). Second, this scenario is representative and sufficient to reflect the main ideas and findings of this paper. Discussion and results under more general settings is left to Section 4.1
Throughout this paper we consider the following stochastic contextual bandits. At the beginning of each round E [T] during the time horizon T, an oblivious adversary chooses context e E [M] and reveals it to the learner, and the learner chooses an action a E [K]. There is a strongly observablee directed feedback graph G = ([K], E) across the actions such that all rewards in (Tt,e,a)eg M] F are observable, where we assume no structure in the rewards except that Te,c,a E [0. 1]. In our stochastic environment, the mean reward B|rr,ca] = Pe,a is unknown but invariant with time. We are interested in the characterization of the minimax regret achieved by the
For every E [K]. either
a' + for all a' A a. defined in Alon et al. 2015

---

learne:
RT(G,M) = inf RT ; M) x²
sup sup x
Σ
max (a),a((a) - Mexxe(())) (c)())][
(I)
where the infimum over all admissible policies based on the available observations. In the sequel we might also constrain the class of context sequences to c" E C, and we will use (G, M, C) and (x G, M, C) to denote the respective meanings by taking the supremum over c² EC
Our first result concerns a new lower bound on the minimax regret.
Theorem 1.1 (Minimax lower bound). For T 2 BM (G)², it holds that RG, = B (G)T), where the graph-theoretic quantity BM (G) given by
M
(G) = max
: I1, IIM disjoint independent subsets of [K], and 1; A 1o <
Σ
and T: A 13 means that u A whenever E 1 and v E T
Theorem I.I provides minimax lower bound on the optimal regret, depending both the number of contexts M and the feedback graph G. Note that the independent subsets /,,... , IM are allowed to
be empty if needed. It is clear that B1 (G) = ox(G) is the independence number, and 3rr m(G)
whenever M 2 m()) This leads to the following corollary.
Corollary 1.2 (Tightness of MAS number). For any graph G, if 2 m() and T 2 m()), one has R2 (G, M) = (2( -2(vm(G)))
Corollary 1.2 shows that, the regret change from @(Va(G)T) multi-armed bandits to (G))T) in contextual bandits (Dann et al. 2020) is in fact not superfluous when there are many contexts. In other words, although the independence number determines the statistical complexity of multi-armed bandits with graph feedback, the statistical complexity in contextual bandits with many contexts is completely characterized by the MAS number.
For intermediate values of M E (1, (G)), the next result shows that the quantity (Gr is tight for special class CSA of context sequence called self-avoiding contexts. A context sequence (ci,... .T) is called self-avoiding iff c, a for 8 < / implies C, = C.+1 ... Cz. (or in other words, contexts do not jump back). For example, 113222 is self-avoiding. but 12231 not. This assumption is reasonable when contexts model nonstationary environment changing slowly, e.g. the environment changes from season season.
Theorem 1.3 (Upper bound for self-avoiding contexts). For self-avoiding contexts, there is policy π achieving (m G, M, CSA) = Ō 0M (G)T). This policy can be implemented in polynomial-time and does not need to know the context sequence in advance.
As the minimax lower bound in Theorem 1.1 is actually shown under CSΛ. for large T, Theorem 1.3 establishes tight regret bound for stochastic contextual bandits with graph feedback and self- avoiding contexts. The policy used in Theorem 1.3 is based on arm elimination, where a central step of exploration is to solve a sequential game in general graphs which has minimax value (()x(G)) and could be of independent interest.
For general context sequences, we have a different sequential game in which we do not have a tight characterization of the minimax value in general. Instead, we have the following upper bound, which exhibits a gap compared with Theorem 1.1
Theorem 1.4 (Upper bound for general contexts), For general contexts, there is policy achieving
Ry(m; G, M) = Ō (Viin (3 (3M (G),
where
M
(G) = max
Σ
Lal I1. ... Ins are disjoint independent subsets of [K]
(3)
3

---

Fortunately, additional assumptions on the feedback graph G' can be leveraged to recover the tight regret bound:
Corollary 1.5 (Upper bound for transtively closed or undirected feedback). For any undirected or transitively closed graph G, the policy x in Theorem 1.4 achieves a near-optimal regret
R G. M) = (OLBBM((G)
directed graph G' is called transitively closed if u - v and e -> w imply that u - w. In reality directed feedback graphs are often transitively closed, for directed structure of the feedback typically indicates a partial order over the actions. Examples include bidding in auctions (Zhao and Chen 2019) Han et al. 2024) and inventory control (Huh and Rusmevichientong 2009), both of which exhibit the one-sided feedback structure + j for i J. For general graphs, Theorem [.4] gives another graph-theoretic quantity (G). Note that 3 (G) 2 (G) as there is no acyelic requirement between I ss in (3), which in turn is due to a technical difficulty of non-self-avoidin contexts. Further discussions on this gap are deferred to Section 4.3
Interestingly, the upper bound quantities 3a (G) and (G)) are not explicitly linear in M and are always no larger than MG) Hence our results partially answer an open problem in (Hao et al. 2022, Remark 5.1 1. that if the dependence of regret bound O MTT) on M can be improved.
1.3
Related work
The study of bandits with feedback graphs has a long history dating back to (Mannor and Shamir 2011 For (both adversarial and stochastic) multi-armed bandits, a celebrated result in (Alon et al.
2017) shows that the optimal regret scales as ((Va(T)T) if T 2 (G))²; the case of smaller T was settled in (Kocák and Carpentier 2023), where the optimal regret is a mixture of vT and T2/3 rates. For stochastic bandits, simpler algorithms based on arm elimination or upper confidence bound (UCB) are also proposed (Lykouris et al. 2020, Han et al. 2024). while the UCB algorithm only known to achieve an upper bound of O( TG In addition to strongly observable graphs we primarily focus on, weakly observable graphs have also drawn vast interest (Alon et al. 20155]
2015
Chen et al., 2021 where the optimal regret is characterized by the dominating number (G)) There exploration plays more significant role due to weaker observability of certain nodes, leading an optimal regret O (((G))//TT4//3) We will briefly discuss the regret characterization of our contextual setting with weakly observable graphs in Section 4.1 and 4.2
Recently, the graph feedback was also extended to contextual bandits under the name of "cross- learning" (Balseiro et al. 2019] [Schneider and Zimmert, 2024). The work (Balseiro et al. 2019) considered both complete and partial cross cross-learning, and showed that the optimal regret for stochastic bandits with complete cross learning is θ(VKT). Motivated by bidding in first-price auctions, (Han et al. 2024) generalized the setting to general graph feedback across actions and complete cross-lcarning across contexts, a setting used in the current paper. The finding in (Han al.] 2024) is that the effects of graph feedback and cross-learning could be "decoupled": a regret upper bound mminnaaG)) K T)) is shown, which is tight only for special choice of the feedback graph G. The work (Dann et al. 2020) considered a tabular reinforcement learning setting with adversarial initial states, that their setting with episode length H coincides with our problem with general feedback graph G across all context-action pairs. They showed that the UCB algorithm achieves a regret upper bound Õ(v Mm(G)T)); however, their lower bound was only 2 (2V (a())) when T 2 3 Therefore, tight lower bounds that work for general graphs G are still underexplored in the literature, and our regret upper bounds in Theorems 1.3 and 1.4 also improve or generalize the existing results.
The problem of bandits with feedback is also closely related to partial monitoring games (Bartók) ctt al. 2014). Although this is a more general setting which subsumes bandits with graph feedback, the results in the literature (Bartók et al. 2014 Lattimore] 2022 Foster et al. 2023a) typically have tight dependence on T, but often not on other parameters such as the dimensionality. Similar issues also applied to the recent line of work (Foster al. 2021 2023b) aiming to provide unified complexity measure based on the
coeffcient (DEC); the nature of the two-point lower bound
'The result of Lykouris et al. 2020 was stated using the independence number, but they only considered undirected graphs so that mG) (G)..

---

used there often leaves a gap. We also point to some recent work (Zhang et al. 2024) which adopted the DEC framework and established regret bounds for contextual bandits with graph feedback, but no cross-learning across contexts, based on regression oracles.
2 Hard instance and the regret lower bound
In this section we sketch the proof of the minimax lower bound (G. CSA)
for T' 2 MM (G)2 and general (G, M), implying Theorem 1.1 We first identify a hard instance that corresponds the graph-theoretin quantity Bar (G)) and then present the core exploration-explotaaeee tradeoff in the proof to arrive at the fundamental limit of learning under this instance. This approach has been widely adopted in the bandit literature. The complete proof deferred Appendix
The proof uses the definition 2 of Ba (G) to construct M independent sets II.... IM such that I, f I for i j; by definition, the independent sets I1, IM are disjoint. We then construct hard instance where the best action under context c E [M] is distributed uniformly over I since Ig an independent set, this ensures that the learner must essentially explore all actions in Ie under context c. Moreover, the context sequence c" is set to be ... 122... ... M, i.e. never goes back previous contexts. This order ensures that the exploration in Te during earlier rounds provides no information to the exploration in Leg during later rounds, whenever < c2. Naively, if the learner only explores in each Le under context then learning under each context becomes a multi-arme if
bandit problem (because Le is itself an independent set), and we can show lower bound V
c= [
with appropriate context sequence c².. Maximizing over all possible constructions gives the desired result.
It is possible, however, for the learner choose actions outside Le to obtain information for the later rounds. To address this challenge, we use delicate show that this pure exploration must incur too large regret be informative when T 2 Bax (G)². Specifically, consider the regret incurred by this pure exploration:
tradeoff argument to
Rexplore Σ
Σ cET
(a1 & Ic)
where To = {t E [T] c, cJ. Then for some absolute constants ci and c2, the tradeoff can be formulated as two lower bounds of the regret RT:
Ry 2avB/r (G)T exp( Bas (G) Raplone /T) and Ry c2 Rexplore
The first bound is decreasing in the amount of pure exploration, while the second one is increasing. Balancing this tradeoff gives the desired lower bound R 22 [VVBBu for T BM (G)3.
In summary, the key structure used in the proof is that I; A In for < j: we remark that this does not preclude the possibility that 1; 1; for j i, which underlies the change from a(G) to m(G) as the number of context increases.
3 Algorithms achieving the regret upper bounds
This section provides algorithms that achieve the claimed regret upper bounds in Theorems 1.3 and 1.4 The crux these algorithms to exploit the structure of the feedback graph and choose a small number of actions to explore. Depending on whether the context sequence is self-avoiding above problem can be reduced to two different kinds of sequential games on the feedback graph. Given solutions to the sequential games, Sections 3.2 and 3.3 will rely on the layering technique to use these solutions on each layer, and propose the final learning algorithms via arm climination.
not,
3.1
Two sequential games on graphs
In this section we introduce two sequential games on graphs which are purely combinatorial and independent of the learning process. We begin with the first sequential game.
5

---

Definition (Sequential game 1). Given directed graph G = (V, and positive integer M, the sequential game consists of M steps, where at each step c 1. M:
1. the adversary chooses a strongly observable subset A. S V disjoint from Nout (e
2. the learner chooses Dr S Ag such that De dominates Ac, i.e. Ac S Nout (Da)
The learner's goal is to minimize the total size Σ Dee of the sets De-
The above sequential game is motivated by handit learning under self-avoiding contexts. Consider a self-avoiding context sequence in the order of 1, 2...... M. For e [M], the set A₂ represents the "active set" of actions, i.e. the set all probably good actions, yet to be explored when context e first occurs. Thanks the self-avoiding structure, "yet to be explored" means that A. must be disjoint from Nuu ce The learner then plays a set of actions De C Ae to ensure that all actions in Ag have been explored at least once; note that a good choice of D, of Ac. but also tries to observe as many actions as possible outside A, and make the complement of Nout (e small. The final cost >e DDel characterizes the overall sample complexity to explore every active action once over all contexts.
only aims observe all
It is clear that the minimax value of this sequential game is given by
max U1 (G,
min
Σ Del
(4)
A
Av UM Amt Au Naa (Dac)
Da
A Non
The following lemma characterizes the quantity (G, M) up Ollog (V)
factor.
Lemma 3.1 (Minimax value sequential game I). There exists an absolute constant 0 that
3m S (G, S Cäsr (G) log [V]-
Moreover, the learner can achieve a slightly larger upper bound ((3 log" [V] using polynomial-time algorithmm.
The second sequential game motivated by bandit learning with an arbitrary context sequence.
Definition 2 (Sequential game II). Given directed graph G = (V, E) and positive integer M, the sequential game starts with an empty set Do = 2, and at time 1,2, ....
1. the adversary chooses an integer E [M] (and a set Ac, C V if at does not appear before). The adversary must ensure that Ac, /outt (Dz-1) non-empty;
2. the learner picks vertex Ut E Ac, and updates D D U (wr)
The game terminates time T whenever the adversary has no further move (i.e. UcAc S Nout (Dr)). and the learner's 's goal is to minimize the duration T of the game.
The new sequential game reflects the case where the context sequence might not be self-avoiding, so instead of taking a set actions at once, the learner now needs to take actions non non-consecutivel. Clearly the sequential game II is more difficult for the learner subsumes the sequential game I when the context sequence is self-avoiding: the set D. in Definition iis simply the collection u in Definition 2 whenever e
Consequently, the minimax values satisfy Ug (G, M) 2 U1 MG. The following lemma proves an upper bound on U2 M).
Lemma 3.2 (Minimax value of sequential game II). There exists polynomial-tinn time algoritium for the
learner which achieves
(G, M) S 3aom (G, .) S
log² [V]]
where C' > 0 is an absolute constant, 3 (G) is given in B and
M
Bdom (G, .M) max
Σ
Bel: U acyelic, B. S V. dominates some V.
with disjoint Vi.... VM S V, and B.l S 8(V.) + log (V).
Both sets (Ac, De) allowed to be empty.

---

3.2 Learning under self-avoiding contexts
Given a leamner' 's algorithm for the first sequential game, we are ready to provide an algorithm for bandit learning under any self-avoiding context sequence. The algorithm relies on the well-known idea of arm elimination (Even-Dar et al., 2006): for each context e [M.], we maintain an active set Ag consisting of all probably good actions so far under this context based on usual confidence bounds of the rewards. To embed the sequential games into the algorithm, we further make use the layering technique in [Lykouris et al. 2020 Dann et al. 2020): for e E N, we construct the set Ac, as the active set on layer such that all actions in A have been taken for least ? times. In other words, the active set Ac, is formed based on e- reward observations of all currently active actions. As higher layer indicates higher estimation accuracy, the learner now aims to minimize the duration of each layer which is precisely the place we will play an independent sequential game.
Algorithm I: Arm climination algorithm for self-avoiding contexts
Input: time horizon T, action set [K], context set [M]. feedback graph G, a subroutine A for the sequential game failure probability 5 E (0, 1).
Initialize: active sets A + [K] for all contexts c E [M] on layer 1.
for c to M do
for 8= 1,2 .... do compute De,t NoueVNo according to the subroutine A, based past plays
(Ae,e' (i, and (De,))e
choose each action in De, once (break the loop if # cort > T during this process), and update accordingly;
compute the empirical rewards Fe,a for all actions based on all historic reward observations; choose the following active set on the next layer:
Ac,t41 { a {ae Ac,e Fe.a 2 max Fe,a' - 2/
log Jog(2MKT/5)
(5)
d'E
move to the next layer E +- 1. end end
The description of the algorithm is summarized in Algorithm D and we assume without loss of gener- ality that the self-avoiding contexts comes in the order of ,.....M M (the duration of some contexts might be zero). During each context, Algorithm [[squenntilly constructs a shrinking sequence of active sets Ac,1 2 Ac 2 ..., and on each layer Ł, the algorithm plays the sequential game I based on the current status (past plays (Ae or equivalently (Aer,e (Noue (Uice' Pe's))ssss of the adversary, and past plays (Dete)e of the learner) ( After the rewards of all actions of A have been observed once, the algorithm constructs the active set Ac,t41 for the next layer based on the confidence bound (5) and sample size é.
The following theorem summarizes the performance of the algorithm.
Theorem 3.3 (Regret upper bound of Algorithm I.. Let the subroutine for the sequential game
I be the polynomial- timm algorithm given by Lemma 3.1 Then with probability at least 8, the regret of Algorithm [ upper bounded by
(VTVV (K) log(M
RT (Alg
G, MsCs -0
On high level, by classical confidence bound arguments, each action chosen on layer é suffers from an instantaneous regret Ö(1/VZ). Moreover, Lemma 3.1 shows that the number of actions chosen on a given layer is at most ((3M(G) A combination of these two observations leads to the
Ö(v BM (G)T) upper bound in Theorem 3.3 and a full proof is provided in Appendix
'It is possible that, at some layer é and for some context every action active under e has been explored, i.c. Ac,e (ooe) Di.e) 2. In this case, the learner simply skips next layers by choosing D. Ø.
7

---

3.3 Learning under general contexts
The learning algorithm under a general context sequence is described Algorithm 2 Similar to Algorithm | for each context we break the learning process into different layers, construct active sets Ac, for each layer, and move to the next layer whenever all actions in Ae, have been observed once on layer f. The only difference lies in the choice of actions on layer e, where the plays from the sequential game II are now used. The following theorem summarizes the performance of Algorithm 2 whose proof is very similar to Theorem 3.3 and deferred to Appendix C
Algorithm 2: Arm climination under general contexts
Input: time horizon T, action set [K], context set [M]. feedback graph G, a subroutine A for the sequential game II, failure probability 5 E (0, 1).
Initialize: active sets Ac, < [K] for all contexts E [M]] and layers f > 1; set of actions Dj Ø chosen on layer the current layer index {(c) + 1 for all [M]]
for f = to I"' do
receive the context Cr, and compute the current layer index & f(c)); according to subroutine A, choose an action ag E Ae,,e based on the active sets (Ac,t.)rg(M) and previously taken actions De, on the current layer;
update the set of actions on layer la via Dr. < Dr. U {at):
for c C [M] do
compute the new layer index (c) min Ac, & Nout (Dt)):
if (c) > E(c) then
compute the empirical rewards Fe,a for all actions based on all historic observations; choose the following active set on the new layer:
Accomale) + {a
log (0g(2KT//0
EE Accle)) Fe 2 max Fagal d'EAe,
2V
fnew (c)
update the layer index E(c) &- Enew(c).
end
end
end
Theorem 3.4 (Regret upper bound of Algorithm 2.
Let the subroutine for the sequential game
II be the polynomial-tine -ime algorithm given by Lemma 3.2 Then with probability at least - ô, the regret of Algorithmm
upper bounded by
RA(A 2 G, 0
(vT (VT Baom (G, M) log
By the second inequality in Lemma
3.2
Theorem
3.4 implies Theorem Corollary L.5 then
follows from the following result. Lemma 3.5. For undirected transitively closed graph G, it holds that Baom (G) O(Bss (G) log [V]).
Discussions
4.1 Weakly observable feedback graphs
Naturally, may ask what results we would get under weaker assumption / general feedback structure. If the feedback graph G is instead weakly observable then under complete cross-learning, an explore-then-comee exploring the minimum dominating se Juniformly for time 1/3/2/3 and then committing the empirically best action that has suboptimality bounded by ((8(G) 133--133 with high probability. This matches the existing lower bound in (Alon et al. 2015) and is hence near-optimal.
(ETC) policy can achieve regret (68(G)1/T2/33 by first
0(8(G)1/3T-1/3
'In language (Alon et al. 2015 graph G weakly observable N (a) for all a [K]. and
there exists og E [K] such that {oo [ Mao) } & N₁, (ao).
"Note that log K) -pprrxxiiat minimum dominating be found efficiently by Lemma A.2

---

4.2 Incomplete cross-learning
possible to further relax the assumption of complete cross-learning. Suppose the feedback across contexts is characterized by another directed graph GiMI (and denote G[K] across actions respectively), and consider a product feedback graph Gkk] Glwj over the context-action pairs such that (a), c1) + (a2, 02) if a1 + a2 in G[k] and e₁ C2 in G[M- Then we can get the following generalized results.
4.2.1 Weakly observable feedback graphs on actions
When the feedback graph G(K] is weakly observable, following the argument in Section 4. can achieve regret δ (5(G )m(G T/222 by running an ETC subroutine for each context follows: for every context c E [M]. we keep "exploration" counter fee- At each time t with are in the "exploration" stage and continue to uniformly explore the minimum dominating set of GiK]- Then we increase the counter for all observed contexts, i.c. ne f n. + for all c Nout (ct) GIM). Otherwise, we "commit" to the 1/3 with
context Ct. if ne. ((Gr)) k)) ()))m 2
empirically best action that has suboptimality bounded by Ö high probability.
The key observation that the number of times we are in the "'exllration" stage is o (((()))))((())) (122233) This can be seen from a layering argument, similar to the one in Section 3.2 that the number of actually played contexts on each layer is most m(Gag) To- gether with the bounded rewards and the bounded suboptimality in the "commit" stage, this proves the regret upper bound.
Combining the context sequence construction in Section 2 and the lower bound argument in (Alon
also prove matching lower bound Ω (((()) 1/3 72233).
al. 2015
4.2.2
Strongly observable feedback graphs on actions
When G[K] is strongly observable, it is straightforward to generalize our upper (for self-avoiding contexts) and lower bounds in Theorem 1.1 and 1.3 with 9A5 (G1K) replaced by
M
Bas (G x G(n) = max Σ c=1
Lel Ie independent subset of [K] x {c}, and Ie A Ie for <
and Bdom (GKK] in Theorem by
M Bel U is acyclic in G G[M),
Boom (G[x) x GIM)) = max
Σ c=1
B. is (1+ log K) -approx min dominating set of some subsets Vo S GiK x fe}
where the new graph quantities are defined on the product graph G X G(My) For general contexts, this gives a tight upper bound ((vTTTs((1k) x G(M))) when Gik] and G[M] are ei- ther both undirected or both transitively closed Most generally, we have a loose upper bound
Ö( T mii((m(G(K) x G(M)), (G MTT)
4.3 Gap between upper and lower bounds
Although provide tight upper and lower bounds for specific classes of context sequences (self- avoiding in Theorem I.3) or feedback graphs (undirected or transitively closed in Corollary [15). (.5). in general the quantities 3 (G) Theorem 1.1 and min (G), mG)) in Theorem 1.4 exhibit gap. The following lemma gives upper bound this gap.
Wee prove this statement in Appendix C.7 due to space limit.

---

Lemma 4.1. For any graph G, it holds that
M(G) M .1 1 Bas (G),
Bas S min (B m()) S max
where p(G) denotes the length of the longest path in G.
Lemma 4.1 shows that if G does not contain long paths or M is large, the gap between 3 (G) and 3ar (G) is not significant. We also comment on the challenge of closing this gap. First, we do not know a tight characterization of the minimax value of the sequential game II (cf. Definition 2), and the upper bound (dom FdommG, M) in Lemma 3.2 could be loose, as shown in the following example.
and edges (i, J') if either i < E and + j', or i i' and j < j', and all self-loops. By choosing B. = V. = {(i,c): : [ [K]] in the definition of 9dom (G, MM) in Lemma 3.2 it is clear that 3dom (G, M) = KM However, we show that the minimax value is U. (G, M) K M 1. The lower bound follows from UG, M) 2 (G, M) 2 (G) 2 K + M - 1, as I {(i,
Example 1. Consider an acyclic graph G (V, with K M vertices (E(K))
})} for 2 c S M satisfy the constraints in the definition of (G) in (2) For the upper bound, we consider the following strategy for the learner in the sequential game II: Ut = (is, Jt) is the smallest element (under the lexicographic order over pairs) in Aca Noott (D.-1). To show why U22 (G.M) M) S K + M - 1, let D. be the final set of vertices chosen by the learner under context c. By the lexicographic order and the structure G. each De can only consist of vertices in one column. Moreover, for different + d, the row indices of De must be entirely no smaller or entirely no larger than the row indices of De. These constraints ensure that I IDel= S K + M 1.
i E [K]] and Ie {11,
This example shows the importance of non- non-greedy approaches when choosing Ut In the special case where A. = {(i. c) E [K]} is the c-th column, within Ag this is an independent set, so any greedy approach that does not look outside As will treat the vertices in Ag indifferently. In contrast, the above approach makes use of the global structure of the graph G.
The second challenge lies in the proof of the lower bound. Instead of the sequential game where the adversary and the learner take turns to play actions, the current lower bound argument assumes that the adversary tells all his plays to the learner ahead of time. We expect the sequential structure to be equally important for the lower bounds, and is interesting to work out an argument for the minimax lower bound to arrive at sequential quantity like U2 (G, M).
4.4 Other open problems
Performance of the UCB algorithm. The UCB algorithm under feedback graphs has been analyzed for both multi-armed (Lykouris et al. 2020) and contextual bandits (Dann et al. (020). However, both results only show a regret upper bound Õ m(G)T), even in the case of multi-armed bandits (i.e. M = 1). is interesting to understand for algorithms without forced exploration (such as UCB), if the MAS number m(G) (rather than aG) or 8M (G)) turns out to be fundamental.
Regret for small T. Note that our upper bounds hold for all values of T, but our lower bound requires T > (x)(G)3, This is not an artifact of the analysis. as the optimal regret becomes fundamentally different for smaller T. The case of multi-armed bandits has been solved completely in recent work (Kocák and Carpentier] 2023), where the regret is a mixture of VT and 72/3 terms. We anticipate the same behavior for contextual bandits, but the exact form is unknown.
Stochastic contexts. In this paper we assume that the contexts are generated adversarially, but the case of stochastic contexts also draws some recent attention (Balseiro et al.) 2019: Schneider and Zimmeri, 2024), and sometimes there is a fundamental gap between the optimal performances under stochastic and adversarial contexts (Han et al. 2024). It is an interesting question whether this is the case for contextual bandits with graph feedback.
Acknowledgement
This work is generously funded by the NSF grant CCF 2106508.
10

---

References
Alekh Agarwal, Miroslav Dudik, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances Neural Information Processing Systems, 29, 2016.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135. PMLR, 2013.
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
Noga Alon, Nicolo Resa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. Conference on Learning Theory, pages 23-35. PMLR, 2015.
Noga Alon, Nicolo Cesa-Biand Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6):1785-1826, 2017.
Peter Auer. Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 422, 2002.
Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Con- textual bandits with cross-learning. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Gábor Bartók, Dean P Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial monitor- ing classssiiiiicnnnnn regret bounds, and algorithms. Mathematics of Operations Research, 39(4): 967-997, 2014.
Djallel Bouneffouf, Trina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 IEEE Congress Evolutionary Computation (CEC), pages 1-8. IEEE, 2020.
Houshuang Chen, Shuai Li, Chihao Zhang, al. Understanding bandits with graph feedback. Advances in Neural Information Processing Systems, 34:24659-24669, 2021.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011.
Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233-235, 1979.
Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Reinforce- ment learning with feedback graphs. Advances in Neural Information Processing Systems, 33: 16868-16875 2020.
Khaled Eldowa, Emmanuel Esposito, Tom Cesari, and Nicolò Cesa-Bianchi. On the minimax regret for online learning with feedback graphs. Advances in Neural Information Processing Systems, 36, 2024.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the mulli--rmed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Approximating clique almost up-complete. In /199// Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 2-12. IEEE Computer Society, 1991.
11

---

Dean Foster, Dylan J Foster. Noah Golowich, and Alexander Rakhlin. On the complexity of multi- agent decision making: From learning games to partial monitoring, In The Thirty Sixth Anmaal Conference on Learning Theory, pages 2678-2792 PMLR, 2023a.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
Dylan Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference Learning Theory, pages 3969-4043. PMLR, 2023b.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou, Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Fabrizio Grandoni. A note on the complexity of minimum dominating set. Journal of Discrete Algorithms, 4(2):209-214, 2006.
Yanjun Han, Tsachy Weissman, and Zhengyuan Zhou. Optimal no-regret learning in repeated first-price auctions. Operations Research, 2024.
Botao Hao, Tor Lattimore, and Chao Qin. Contextual information-directed sampling. In International Conference on Machine Learning, pages 8446-8464. PMLR, 2022.
Woonghee Tim Huh and Paat Rusmevichientong, A nonparametric asymptotic analysis of inventory planning with censored demand. Mathematics of Operations Research, 34(1):103-123, 2009.
Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
Tomáš Kocák and Alexandra Carpentier. Online learning with feedback graphs: The true shape of regret. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17260-17282. PMLR, 23-29 Jul 2023.
Tor Lattimore. Minimax regret for partial monitoring: Infinite outcomes and rustichini's regret. In Conference on Learning Theory, pages 1547-1575. PMLR, 2022.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
Thodoris Lykouris, Éva Tardos, and Drishti Wali. Feedback graph regret bounds for thompson sampling and ueb. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 592-614. PMLR, 08 Feb-11 Feb 2020.
Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. In J. Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, Curran Associates, Inc., 2011.
Jon Schneider and Julian Zimmert. Optimal cross-learning for contextual bandits with unknown context distributions. Advances in Neural Information Processing Systems, 36, 2024.
Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical contextual bandits with feedback graphs. Advances in Neural Information Processing Systems, 36, 2024.
Haoyu Zhao and Wei Chen. Stochastic one-sided full-information bandit. In Joint European Con- ference on Machine Learning and Knowledge Discovery in Databases, pages 150-166. Springer, 2019.
Yinglun Zhu and Paul Mineiro. Contextual bandits with smooth regret: Efficient learning in continu- ous action spaces. In International Conference on Machine Learning, pages 27574-27590. PMLR, 2022.
12

---

A
Auxilary Lemmas
Lemma A.1 (Lemma of (Alon al. 2015)). For any directed graph G (V, E), one has 5(G) S (Go(G) log [V]
For a directed graph G. there is well- approximate algorithm for finding the smallest dominating set: starting from D 85, recursively find the vertex v with the maximum out-degree in the subgraph induced by V", Nout (D), and update D) <- D U {v). The following lemma summarizes the performance of this algorithm.
Lemma A.2 (Chvatal (979)), For any graph G = (V,E). the above procedure outputs dominating set D with
DI (1 log V))
Lemma A.3 (A special case of Lemma 3 in Gaa et al. 2019)). Let Q1,... On be probubility measures on some common measure space (Ω, F), with 2, and + [n]] any measurable test function. Then
exp(-KL(QQ)lQ.)).
B Deferred Proof for the Lower Bound
In this appendix, give the complete proof of the minimax lower bound Rý M, 0(yBas (G)T) for T 2 (G)3 and general MG, implying Theorem 1.1
Let I,.... .IM be the independent sets achieving the maximum in (2. by removing empty sets, combining (Is, I++1) whenever [ 1, and possibly removing the last set IM if [f 1, arrive at disjoint subsets Jn, ... Jm K] such that the following conditions hold:
m S M, K. A JJl for all E [m], and J; / J, for <
the only possible non-self-loop edges among Je {ac,,, Oe,Ke } can only point to ac,15
Ee= Ke 2 M [el - = (G) 2 Brr (2) whenever Bal (G)
Given sets JI,..., Jm. we are ready to specify the hard instance. Let u = (...... um) EQ:- = [K]] x [km] be parameter vector, the joint reward distribution pa of (Ft,,,)ee([M] product distribution pa [eee[M]aE[I Bern(pã,)) where the mean parameters for the Bernoulli distributions are 1º whenever m, and
is
A
if a dc,1, if a ac,u, and ue F 1, for [m]. if JaMaaa if & Je:
+2A
Here A E (0, 1/4) is gap parameter to be chosen later. We summarize some useful properties from the above construction:
1. under context e [m]) the best action under Pu is aesu and all other actions suffer from an instantaneous regret at least A;
2. under context e E [m], actions outside Jg suffer from an instantaneous regret at least 1 1/4;
3. for (u,,... , (m and ut == (u1.-.. Me-1, 1, Me+1, um)) the KL divergence between the observed reward distributions (a(a) and pa (a) when choosing the action is (L((Brn1//4)]Bem// 22)) if - ac otherwise
KL(P" (a)llP"(a)) (a)
0
64A
1(a & Jsc((ac...)).
3
'When 3xd (G) 1, the (((T()(()))))) regret lower bound is trivially true even under full information feedback and M 1.
13

---

Here (a) follows from our construction of p" that the only difference between PM and Pu is the reward of action Oc,a. which observed iff a + Oc, (b) is due to the property of (J1.-.. Jm) that any action in Jge (a..) does point de where ==::=uegoee
Finally, we partition the time horizon [T] into consecutive blocks T1, ,,.... Tm (whose sizes will be specified later), and choose the context sequence as for all E T.. For a fixed policy, let Ry be the worst-case expected regret of this policy. By the second property of the construction, it clear that for all Ω
m Σ
R 2
E Bep & Je)..
(6)
TET
When u uniformly distributed over Q, we also have
(a)
RT
Ey
E(pw)au-- + aes..)l
NET.
(6)
Beel }
Eu T (Ppjee 1n (at # ael
T...
(c)
K.
exp KL (P
Bullfee
2K M2=2
E...
Kr -1
KL KL (L ((P))
En Eu)(
exp
2
Kg
LET.
641²
K
BuMaal
exp
E pa (1(a, & Jgo JgoMaac
3(K,
1)
c=1 TET.
Me ect
where (a) lower bounds the minimax regret by the Bayes regret, with the help of the first property; (b) decomposes the expectation over uniformly distributed into u w'{ (uc} and ue E [Ka]: (c) follows from Lemma (d) uses the convexity of x e- (e) results from the chain rule of KI. divergence, the third property of the construction, and that Ke 2 2 for all c E [m].
Next we upper bound the exponent in (7)
( JaoN(annn)))
set
Ke
Ke
E E(pucjoco [1(a, $ Je)l + (1 $ Jsc) + 1(a, = ac.u.))
u,=2 el CoSETy
SET, sxc
Ke
Ke
E Eipucyoo-n $ J2)]+
Σ
((pueyoton ac,ue)l
Me 2 c' C'ScsET
the
eET
4(Ke 1)RT
E Espno jo [1aa = de,ue)l.
We 2ET
Plugging it back into 77. we get
64A2
K.
RT >
Euy(uct
exp
4(Ka - 1))R +
Σ
E po (a, = (ccae))
3(K.
1I)
TET.
2c=2.ET.
( A M
64A²
TTol
))
2 Σ
Ey (
exp
|Rr +
3
K.
c= IET
14

---

where (f) crucially uses that u" = (w1, Me-11 1, Me-1, Um does not depend on Me, so that the sum may be moved inside the expectation to get Σ
u. 1(a ac,u,) 1. Now choosing
K=
Ke S
2KoT
BM)(C)
1
Td
A
0,
Ee=1 K2
(G)
16T
we arrive at the final lower bound
/Byr
4BM((G)
4T
Rr 2
16
exp
3T
ART
BAd
(G)
(GTT
(6
/MMTG)T
16Rr
exp
RT
exp
16
37
16
3 BMB (G)T
where the last inequality is due the assumption T BM( Now we readily conclude from ( the desired lower bound Ry (M)T).
C Deferred Proofs for the Upper Bounds
Throughout the proofs, will use (AA) - (G) (resp. 8(A), m(A)) to denote the independence number (resp. dominating number, MAS number) of the subgraph induced by A C V when the graph G is clear from the context.
C.1 Proof of Lemma 3.1
The lower bound UT (G, .)) 2 (Gr(G) is easy: let ....... . IM be M independent sets with I; A I for all i < j. Then the choice A = Ie is always feasible for the adversary, for Ie is disjoint from Nout (Ue ). For the learner, the only subset D. S Le which dominates Ia is Dr = Ics hence (G,
Een Hel. Taking the maximum then gives MG) Z (G) by (2).
To prove the upper bound UI (G, M) S CB (G) log VV, the learner chooses De as follows. Given Ac. the learner finds the smallest dominating set Je S A. and the largest independent set Ie S Ac- and sets D. = Le Je. Clearly this choice of D. is feasible for the learner, and since I, f A, for i < j. we have I f I as well. Consequently,
Af
A
M
UTG S
Σ
Del
<
Je +
Tc))
(
Σ
T log [V]
(G) log [V]),
1=1
c=1
where (a) uses IJe = 5(A.) = (a(AA) log [V] = ( log V)) Lemma A.1 and (b) follows from the definition of (G) in 2
Since NP-hard to find either the smallest dominating set or the largest independent set (Karp) 2010 Grandoni 2006), the above choice of D. is not computationally efficient. To arrive at polynomial-tin time algorithm, we may use greedy algorithm to find an Oloog -y)--ppprxi smallest dominating set Je such that |Jal ((8(A.) log VV) (cf. Lemma A.2p. For le, although finding the largest independent set APX-hard (Feige al. 1991). the constructive proof of (Alon et al. 2015 Lemma 8) gives a polynomial-tine time randomized algorithm which finds Te Aa such that [e| = ((((A))/ log Vl) and the average degree among T, is at most O(1). The learner now chooses D. = T. U J.. By the average degree constraint and Turán's 's theorem (Alon and Spencer 2016 Theorem 3.2. 1), each Ie contains an independent subset 4. with [/c| R(Me)) Since
[Ja| ((((A))))))))))))))) log IV) O(TTa log" |V[) = ((44) log VD),
M we conclude that ΣM [D_ O log2 [V]) = (83rs (G) log" [V)..
C.2
Proof of Lemma
The second inequality is straightforward: 3aom (G, M) < m(G) since U.B. is acyclic, and the other inequality follows from Bal O(8(V.) log [V] ((a(V)) log" [V]) in Lemma A.1 A.1
To
15

---

prove the first inequality, we consider a simple greedy algorithm for the learner, where Ac. the vertex with the largest out-degree in the induced subgraph by Acs (D-r) Intuitively. Ac, \ (Nout (D--) is the set of nodes in Ac, that remain unexplored by the learner by time l. Under this greedy algorithm, for e [Mf] define
Ve U (Nuu((e)) A(Ae, /Nout (Non(D(-))) (Dr-)))
Bg [we: = c
We claim that Vo pairwise disjoint and [Bll 8(V.) [V), and thereby complete the proof of >x' [Bll S Bdom (G,M), M). The first claim simply follows from the pairwise disjointness of the sets Nout (vt) M(Ac,' \Nour (ouu(Di-1) (Di-)) .) for different t. For the second claim, let t1 < <.. < t, be all the time steps where Ct = c, and
Ve, 2
U (NNon((Ve)) ( (De i E [n]. j=i
It is clear that Vo,i411 = Ve, Vei/Nout (v:,). Since ve, has the largest out-degree in the induced subgraph by A /Nou (Dt,-1) 2 Ve,s and Nout (V,, n NNut (D(, (V,, Ve,.. this is also the vertex with the largest out-degree in Ve,5. Therefore, the sets { (Ve,s 1n+1 evolve from V2,1 = Ve to Ven+1 Ø follows:
recursively picks the vertex with the largest out-degree in Ve,i, and removes its out-neighbors to get Vo This is well-known approximate algorithm for computing 5(V.), described above Lemma with
Be = n < 8(V)) log [V]) s 6(V)) + log [V],,
as desired.
C.3 Proof of Lemma 3.5
If G is undirected, then Sdom(G) (G) S m(G) = aG) (G) easily holds. It remains to consider the case where G is transitively closed.
Note that in transitively closed graph, every vertex set has independent dominating subset (by tracing to the ancestors). Therefore, for the maximizing sets B,,... BM in the definition Bdam. may the above procedure find independent dominating subsets ...... Jas of Vi,--., VM respectively, with Le C Bg and
M E14
M
M log Σ
8(V)
2
Bel.
Now consider the induced subgraph G' by Ucle. Clearly G' is acyclic, and the length of longest path in G' is at most M (otherwise, two points on path belong to the same Ic, and transitivity will violate the independence). Invoking Lemma [. now gives
M
Lal T < p(G')
Σ
M BM (x (G') (M),,,
and combining the above two inequalities completes the proof.
C.4 Proof of Theorem 3.3
The proof is decomposed into three claims: with probability at least 1 --8,
1. for every c E [M] and f N, when the confidence bound (5) is formed, either every action in Ac, has been observed for at least & times or |Ar,x! 1;
2. for every e E [M] and E N. the best action a" (c) under context e belongs to A and every action in Ac, has suboptimality gap at most min(1, 4A,-1,, with A, e /log(2MKT/6)///
3. for every e E N, the total number N₂ of actions taken on layer l in those subsets Act with Acd 1 is O(3M(G) log² K).
16

---

The first claim simply follows from (1) when G is strongly observable, any subset of size > is strongly observable, and (2) S e each layer l' E [e] there is at least one action which observes E Ac,, S A..r. . For the second claim, the first claim, the usual Hoeffding concentration, and union bound imply that Fe, - Meaaa X & in () for all E [M] and a E Ac,s, when |Ac,el 1 and with probability at least 5. Conditioned on this event:
required by the sequential game I, so that on
The best arm a" (c) is not eliminated by E He,a" De 2 max Te,a'
(5) because (c) 20g
Meea" Ae N
The instantaneous regret of choosing any action E Ac.4+1 is at most min(1,44, for
Me, 2 Fee.a - D. 2 (c) - 3 2 (e,a" - 42c, and |Ma, - (eja trivially holds.
Consequently the second claim holds for AAcel > For the case |Ac,el = 1, note that starting from eliminated until |Ac,er 1
A [K], the above argument implies that the best arm is some layer < & conditioned on the high probability event, which implies the single action in A is the best action and incurs regret. The last claim is simply the reduction the sequential game I,
where Lemma 3.1 shows that N₂- = ΣM |De.el O (G) log? K).
Combining the above claims and that we incur 0 regret whenever |Ac,el = 1, with probability at least 1 8, we have
(Alg 1 G, CsA) <
N2 mini m1in1,,4,), Σ 8=1
where N₂ S N (O log K), and Di= N₂ choice N1 ... Nm N and Nm+1 T sum, and the maximum value is the target regret upper bound Theorem 3.3
It is straightforward to see that the Nm for suitable E N maximizes the above
C,5 Proof of Theorem
The proof follows verbatim the same lines in the proof of Theorem 3.3 except that the total number Ne actions taken on layer is now at most 3aom (G, M) in the third claim, by Lemma 3.2
C.6 Proof of Lemma 4.1
Let V1 C V be maximum acyclic subset, then p(Glv) p(G). Consider the following recursive process: at time f = 1, ......... let J, be the set vertices in Vi with in-degree zero (which always exist as Vú is acyclic), and V V, Jr. This recursion can only last for most p(G) steps, for otherwise there a path of length larger than p(G). Then each Jr is an independent set, for every vertex of Je has in-degree in V, 2 Je. For the same reason also have Jr f Jj for This means that
JJl S max ((GG) M .1 Bar
m(G) Vi
Ban
where the last inequality follows from picking M largest sets among (Jr).
C.7 Proof of the statement in Section 4.2.2
In this section, we show that when Gik] and G[Mr] are either both undirected or both transitively closed, the product graph quantities 8dom = Bdom (G(K) x G(M) and Bas = BM (G[K) x GPM) satisfy
Bdom 0(3M log K).
Combining with the Q(VBNT) T lower bound, this shows the tightness of the upper bound Ö(VBaomT) The idea here similar Section C.3
When GΙK] and GJMj are both undirected, the union set B, the definition of Baom is an independent set thanks to the acyclic requirement. Thus Baom 8M.
17

---

When G and GiM are both transitively closed, for the maximizing sets Bı..... Bar in the definition of Saoms we can again find independent dominating subsets Le S B, (by transitive closure of ((K)) with
Σ 1 lo K
Σ Bel Colog K
Bdom.
Now it suffices to find independent subsets S [K] x {c} that satisfy Je A Je when d' and Ee |Jll = Ee Iel. Toward this end, we first suppose there are and e' such that the - te and 2ec f Ver for uhe ve E Ie and ue, Ver Ic. This implies e ++ c' in Glan by the product graph structure, Then
[e] and [e][ are disjoint since U. Lo is acyclic;
by transitive closure of GiK] and that Le, Lor are independent, Le [uK] U Ler [ay] has path length most
from above, there exist disjoint and independent sets S and S2 such that S U S2
[e|p)] U [ and S f S2.
where we denote the projection
S| = {a [K] (a,c) E S for some E [M]).
Without loss of generality, assume < c'. In this case. S x {e} and Jer = S2 x {c'), so Je A Je. Now suppose there a loop on the set level, i.e. there Ci...., Cm [M] with Le, form clique in G[M]- Te, ([]),....... Tem [Λ]] disjoint in Gix). and the path length in U Tep is at most m. Then we can again "rearrange" them and get independent sets Je, A Je, for Cj < ck and j, E [m]. and Σ==1 Jey1-
"rearrange" them by letting Je
+ Icm Le,- Similarly,
must have that fci..... Cm }
Σラ= Le other cases, we simply let Je = Ie and arrive at JI....,JJy Juy that are acyclic on the set level, i.c. up to reordering of the indices, we have Je A de when < d' Together with Eq (9) we have
Boom log K Σ Lel C' Colog K Σ Jel C' log K.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims the abstract and introduction include a lower bound and upper bounds (and algorithms achieving them) for the considered setup, which are the contributions of this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The gap between the lower bound and the upper bound under the most general
assumptions is discussed with an example in Section 4.3
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification: The complete proof for the lower bound is in Appendix B and those for the upper bounds are in Appendix C
Auxilary lemmas are collected and referenced in Appendix A The problem setup is in Section 1.2 Assumptions are stated in the theorem statements.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This work does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
This work does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. htcp//blccggudeeeeeeeeeeeeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
This work does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This work does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This work does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The authors have reviewed the NeurlPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work aims to understand the theoretical limits of family of contextual bandit problems and has no direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work is theoretical and has no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This work does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
23

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve include such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve include such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.


Reviews:
[{"review_id": "G1WTxEFn4a", "reviewer": "Reviewer_6nrr", "summary": "This paper investigates the problem of stochastic contextual bandits with graph feedback, in which a graph over actions models the feedback structure. The learner selects an action after observing the current context, and then receives the losses of the actions that are neighbors of the selected one in the feedback graph.\nThis work proposes a novel graph-theoretic quantity $\\\\beta\\_{M}(G)$ to characterize the statistical complexity of learning in this problem setting.\nThe authors establish a minimax regret lower bound $\\\\Omega(\\\\sqrt{\\\\beta\\_{M}(G)T})$, where $\\\\beta\\_{M}(G)$ interpolates between the independence number $\\\\alpha(G)$ and the maximum acyclic subgraph (MAS) number $m(G)$.\nSpecifically, $\\\\beta\\_{M}(G) = \\\\max \\\\{\\\\sum\\_{c=1}^{M} |I\\_c| : I\\_1, \\\\dots, I\\_M \\\\text{ are independent sets in } G, I\\_i \\\\nrightarrow I\\_j \\\\text{ for } i < j\\\\}$.\nThis result implies that, while $\\\\alpha(G)$ dictates the complexity in multi-armed bandits (i.e., $M=1$), $m(G)$ becomes the relevant parameter as the number of contexts increases.\nThe paper further provides algorithms that achieve near-optimal regret bounds $\\\\tilde{O}(\\\\sqrt{\\\\beta\\_{M}(G)T})$ for self-avoiding context sequences and $\\\\tilde{O}(\\\\sqrt{\\\\min\\\\{m(G),\\\\bar\\\\beta\\_{M}(G)\\\\} T})$ for general context sequences (where $\\\\bar\\\\beta\\_{M}(G)$ is a larger but similarly defined graph parameter than $\\\\beta(G)$), leveraging carefully designed arm elimination techniques.\nThese algorithms are polynomial-time and demonstrate tight regret bounds for special families of context sequences and feedback graphs, namely undirected or transitively closed graphs.", "questions": "- Please, address any relevant doubt that might have arisen from what is written above.\n- Can the results be extended to the other strongly observable feedback graphs (i.e., the ones not containing all self-loops)? What could be the technical limitations, if you see any?\n- Do you think it could be possible to adapt the algorithmic techniques in this work for time-varying graphs?\n\nMinor comments/typos:\n- Throughout the paper, use “domination number” instead of “dominating number”\n- Line 84: “In what follows” instead of “In the sequel”\n- Some references mention the arXiv, while they might already be published in some conference or journal\n- I think the introduction would benefit from a more thorough comparison with the literature on bandits with feedback graphs. For instance, detailed studies on the minimax regret for bandits with feedback graphs have been pursued in:\n  - Chen, Huang, Li, and Zhang. “Understanding bandits with graph feedback”, NeurIPS 2021\n  - Eldowa, Esposito, Cesari, and Cesa-Bianchi. “On the minimax regret for online learning with feedback graphs”, NeurIPS 2023\n  - Chen, He, and Zhang. “On interpolating experts and multi-armed bandits”, ICML 2024\n- Lines 157-159: the following paper also fits with that description:\n  - Zhang, Zhang, Luo, and Mineiro. “Efficient contextual bandits with uninformed feedback graphs”, ICML 2024", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The most interesting contribution of this work is probably the connection between the learnability of the problem and the novel (at least to the best of my knowledge) graph-theoretic parameter $\\\\beta_{M}(G)$.\nThanks to this, the authors are able to provide further insights into the contextual bandit problem with feedback graphs (with complete cross-learning and under the assumption), showing that the number of contexts can influence the dependence of the regret on the structure of the feedback graph $G$, interpolating between the independence number $\\\\alpha(G)$ (when $M=1$) and $m(G)$ (e.g., when $M \\\\ge m(G)$.\nThe way the regret analysis shows the dependence on such a parameter, via the computation of the value of the sequential game described in Section 3, is also interesting and nontrivial.", "weaknesses": "What the authors consider in this work is not the entire family of strongly observable feedback graphs (the one known to correspond with minimax regret of order $\\\\sqrt{T}$ in the non-contextual case), but only a subset of those graphs, i.e., that contain all self-loops. This excludes relevant feedback graphs such as the loopless clique and the apple tasting one. I think a discussion about these missing graphs, e.g., in Section 4.1 would give a clearer picture of the contributions of this work and how they compare with previous relevant work.\n\nMore importantly, the only nearly tight bounds for the regret are provided for self-avoiding contexts.\nMoreover, the setting of complete cross-learning studied in this work seems quite restrictive as it imposes the assumption of observing the reward of the chosen action under any context.\nThis feels like a somewhat limiting assumption, as in real-world scenarios such a reward is often observed for the current context only, and the same context could reappear in non-contiguous time steps.\nThe applicability of the results is nevertheless sufficient, especially given some applications of interest and the extension of their results for the more general setting, albeit lacking a nearly optimal characterization for general context sequences and any strongly observable feedback graphs.\n\nA further limitation of the applicability of the results is the fact that the feedback graph is assumed to be fixed.\nThis might not be the case generally speaking, as feedback graphs could be time-varying (as assumed in most of the recent literature on bandits with feedback graphs).\nTime-varying feedback graphs could also be found in applications such as repeated first-price auctions (e.g., see “The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations” by Cesa-Bianchi, Cesari, Colomboni, Fusco, and Leonardi, STOC 2024), which is one of the applications mentioned in the related work within this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough review and insightful questions.\n1. It is indeed a great question about extending to the class of all strongly observable graphs, and it turns out that the extension is straightforward.\n\nUpper bounds: A key implication of strongly observable graphs is that for any subgraph with size > 1, there is a dominating subgraph. In Sec. 3 we may safely assume the subgraphs are larger than 1 because having a singleton active subset in arm elimination means it is the optimal arm with high probability. In addition, Lemma A.1 and A.2 still hold for strongly observable graphs. Therefore, the minimax quantities in Section 3 remain to hold.\n\nLower bound: The same lower bound still holds, after adding an additional requirement that $I_1, …, I_M$ are disjoint in the definition of $\\beta_M(G)$ in (2). In fact, for strongly observable nodes with no self loop, they cannot appear in $I_2, …, I_M$, and if they appear in $I_1$ we must have $|I_1| = 1$. Therefore, our lower bound analysis still works through. \n\n2. We agree that the assumption of self-avoiding context is often restrictive in applications, and we include it as a mathematically interesting case. However, we wish to point out that our bound is also tight under the assumption of undirected or transitively closed graphs (Theorem 1.4) with the easier-to-implement Algorithm 2. We believe this assumption finds a wider range of applications, such as bidding in auctions where the feedback graphs are transitively closed (e.g. Han et al. 2020) and also possess complete cross-learning. \n\n3. We agree that an incomplete cross-learning is an interesting open question, and discuss it partially in Section 4.1 with weakly observable context-action product graphs. We define product graphs as $(a_1, c_1)\\rightarrow (a_2,c_2)$ if $a_1\\rightarrow a_2$ and $c_1\\rightarrow c_2$ in their respective graphs (we'll make this definition clearer in text). When the action graph is strongly observable, we may extend our Theorem 1.1 and 1.3 with the following graph quantity (defined by both the action graph and the context graph) that shares the same spirit:\n$$\n\\beta' = \\max \\lbrace\\sum_{c=1}^{M}|I_c| : I_c\\subseteq V_c \\textnormal{ independent and } I_j\\not\\rightarrow I_k \\textnormal{ if } j<k \\rbrace\n$$\nand Theorem 1.4 with\n$$\n\\bar\\beta' = \\max\\lbrace \\sum_{c=1}^{M}|I_c| : I_c\\subseteq V_c \\textnormal{ independent} \\rbrace\n$$\nwhere $V_c=\\lbrace (a,c): a\\in[K] \\rbrace$.\n4. We agree and appreciate the reviewer for pointing out our inapplicability to time-varying graphs. The high-level reason is that although the graph feedback is helpful for multi-armed bandits even in the adversarial setting, it is typically not helpful for adversarial contextual bandits. For example, it was shown in (Balserio et al. 2019) that when the rewards are adversarial, even with cross learning it is optimal to handle each context separately, with the optimal regret scaling with the number of contexts. Therefore, while previous literature handles time-varying graphs in an adversarial framework using EXP3-type algorithms, we do not know of the counterpart for arm-elimination-based algorithms.\n5. We will fix the typos and update the references pointed out by the reviewer.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "NQhNcXveIc", "reviewer": "Reviewer_mcAY", "summary": "In this work, the authors consider the problem of contextual bandits with feedback graphs and aim to achieve a tighter dependency on graph-dependent quantities.\nFiguring out the correct dependency on graph-dependent quantities is a notably challenging problem in the standard MAB framework, as aspects such as whether the feedback graph is directed, whether it has self-loops, or whether the time horizon is large compared to the size of the graphs are crucial components to figure out how much information can be extracted from the feedback graph.\\\\\n\nIn this work, the authors consider a contextual MAB problem where there is a feedback graph across actions and cross-learning between contexts. The authors propose a minimax lower bound for this context, which depends on a quantity $\\beta_M(G)$, where $M$ is the number of contexts. \nThe authors then show that this lower bound is tight for certain classes of problems such as self-avoiding contexts, which is a problem setting where the environment regularly switches from one context to the next but doesn't ever come back to contexts that have already been seen in the past. \nThe authors also derive an upper bound in the general setting using a different algorithm.", "questions": "See weaknesses.\n\nYou propose a specific algorithm for the setting with self-avoidant contexts, but do you think it is a realistic assumption to make ahead of time?\nDo you think that it would be possible to get some sort of best-of-both-worlds guarantees, where the same algorithm could achieve tight bounds if we are in the self-avoidant setting while still ensuring worst-case guarantees in the general case?", "limitations": "Theoretical work, NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose a detailed characterization of the challenges of contextual MAB with feedback graphs by focusing in deriving a lower bound and gaining a good sense of how challenging the problem is. They then provide both an algorithm in a setting where they can achieve a tight bound as well as a general algorithm.\n\nThe proofs are well detailed, and the authors properly study and discuss the gap between upper and lower bounds as well as possible extensions.", "weaknesses": "While the gap in terms of upper and lower bounds may be tight in terms of the graph-dependent quantities in settings with self-avoidant contexts, the upper bounds contain some superfluous logarithmic dependencies. (In particular the $log^2 K$ term in Theorem 3.3). Do you think that this could be avoided?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and the insightful questions.\n1. While we agree it is possible to improve the logarithmic $\\log(MKT)$ term with a more careful concentration argument, it is less obvious how to avoid the $\\log^2K$ term when we use a practical algorithm: if we are allowed access to the dominating subset of the active set of arms, as mentioned in Lemma 3.1, we are only left with $\\log K$ term. This term comes from Lemma A.1 and that we include both dominating subsets and independence subsets in the subroutine of Algorithm 1 in order to relate our exploration sets to independent sets. We are not sure this can be removed in our approach.\n2. While we include it more as a mathematically interesting case, we wish to point out that our bounds are also tight when the graph is undirected or transitively closed (Theorem 1.4), which is an often more realistic assumption. It is achieved by the more straightforward Algorithm 2 which just greedily picks the active arm with most out-going edges in the subroutine. As an example, in bidding in auctions where the winning bid is revealed, the feedback graph is transitively closed across the learner’s actions (e.g. Han et al. 2020 in our reference).\n3. This is a great question. In our Example 1, while the quantity $\\beta_{dom}$ used in bounding Algorithm 2 (Lemma 3.2) is loose, Algorithm 2 itself actually achieves the optimal regret under appropriate tie-breaking strategy. It is open whether we can arrive at a tighter bound for Algorithm 2 directly or with modifications, such as exploring an extra small independence subset as we did in Algorithm 1 (details in Appendix C.1).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Nk6pOA5k9N", "reviewer": "Reviewer_5kFj", "summary": "This paper studies contextual online learning when the feedback received by the learner is regulated by a feedback graph. The setting is as follows: the actions constitute the nodes of a directed graph $G$, and playing action $a$ at time $t$ when the context is $x_t$ reveals not only the loss incurred by that action at that time, for that context but the losses of all the neighboring actions, for all possible $m$ contexts. While the contexts are generated adversarially, the losses are i.i.d.. \n\nThe non-contextual problem is well understood, with tight minimax regret guarantees holding for both the adversarial and stochastic settings. These rates depend on both the time horizon $T$ and some graph parameters. In particular, for strongly observable graphs (as the ones studied in this paper), the rate is known to be $\\sqrt{T \\alpha}$, where $\\alpha$ is the independence number of the feedback graph. \n\nPrevious results achieve a regret bound of $O(\\sqrt{T m})$ for the contextual problem, where $m(G)$ is the maximum acyclic subgraph number, which is complemented by the abovementioned $\\Omega(\\sqrt{T \\alpha})$ lower bound. This paper investigates the gap in the graph-dependent parameter in the minimax rate. Note, $\\alpha$ = $m$ for undirected graphs. \n\nThe contribution of the paper are as follows: \nwhen the number of contexts is large ($\\ge m$), then the $\\sqrt{T m}$ rate is tight\nin general, a lower bound of $\\Omega(\\sqrt \\beta_m)$ is proved, where $\\beta_m$ is a new graph parameter which crucially depends on the number $m$ of contexts and gracefully interpolates between $\\alpha$ and $m$. \nimproved upper bounds are then proved for special context sequences and the general problem", "questions": "What is the relationship between your graph parameter and the ones in Eldowa et al ”On the Minimax Regret for Online Learning with Feedback Graphs”. NeurIPS 2023?", "limitations": "No potential negative societal impact", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Online learning with feedback graphs is a relevant problem with a long literature in NeurIPS and ICML\n2. Studying this problem with contexts is fairly natural, and has already been studied\n3. the paper presents a consistent set of results and manages to present them nicely in the intro. Due to space constraints, the technical parts are, however, only roughly sketched.", "weaknesses": "- the problem is not closed: there is still a significant gap in the right graph theoretic parameter\n- the result only holds in the stochastic setting. What can be said in the adversarial setting?\n- the lower-bound construction is fairly natural (at a high level)\n- the graph theoretic parameter introduced is artificial and way less natural than the ones present in the non-contextual settings.\n\nMinor comments\n- please update the references: e.g., Schneider and Zimmert and Zhang et al have been published\n- please consider adding some further references to the learning with feedback graph literature. (see also questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and the insightful questions.\n1. Our work assumes adversarial context. When the reward is also adversarial, as shown in (Balseiro et al. 2019), cross-learning is not helpful and the optimal minimax regret is proved to be $\\sqrt{M\\alpha T}$: this essentially corresponds to dividing the horizon into $M$ different subproblems each with duration $T/M$. Then the minimax regret for each (single-context) subproblem is known to be $\\sqrt{\\alpha T/M}$.\n2. (Eldowa et al. 2023) studies the non-context (or single-context) setting and arrives at the independence $\\alpha$ number. Our proposed quantity $\\beta_M$ can be seen as an extension of $\\alpha$ under the assumption of adversarial context, as it sequentially takes the max independent subset and its neighbors. The information-flow constraint in Eq (2) then naturally arises from this adversarial assumption too.\n3. We agree that the idea behind the lower bound construction is natural, but we’d also like to make two remarks. First, this natural construction proves the tightness of the MAS number when the context space is large, an observation overlooked in the literature even when the upper bound using the MAS number was obtained. Second, the proof technique requires to achieve a careful balance between exploration and exploitation, and the two-inequality approach (below Line 182) could be of general interest when proving interactive lower bounds. \n4. Although our graph-theoretic quantity $\\beta_M$ is not as natural as the independence number and the MAS number, our lower bound shows that this is the right quantity for contextual bandits (at least under self-avoiding contexts). In addition, this quantity exhibits the desired interpolation between the independence number and MAS number. \n5. We appreciate the reviewer for mentioning these references and shall include them and further discussion in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "4tzYnki2zW", "reviewer": "Reviewer_iUw4", "summary": "In this paper, the authors consider the problem of contextual bandits with a feedback graph, for finite context space.  In the presented setting, taking an action reveals the rewards for all neighboring actions in the feedback graph for all contexts. The authors propose $\\beta_M(G)$, a theoretical quantity in which $M$ is the number of contexts and $G$ is the feedback graph, with the goal of characterizing the hardness of learning for this class of problems. The authors prove a lower bound of  $\\Omega(\\sqrt{\\beta_M(G)T})$ where $T$ is the number of rounds.  The authors also present a near-optimal upper bound of $\\widetilde{O}(\\sqrt{\\min (\\bar{\\beta}(G),m(G))T})$.", "questions": "1.\tSee weakness 1.\n\n2.\tCan you please explain the conclusions to corollary 1.2? Specifically, the dependency of $I_c$ in the context is unclear to me, and why it implies that $\\beta_M(G) = m(G)$.\n\n3.\tCan you please provide some more intuition regarding the behavior of $\\beta_M(G)$, and an example for a calculation of it for simple graphs?", "limitations": "-", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe insights in the paper are interesting, it characterizes the difference between MAB with graph feedback and Contextual MAB with graph feedback, for small and finite context space.\n\n2.\tThe authors present upper and lower bounds for the problem.\n\n3.\tThe algorithmic approach taken to produce both results is elegant, especially the use of the arm elimination technique.", "weaknesses": "1.\tIn contextual MAB literature, the main difficulty is that the context space is large, and in each episode, the feedback is revealed only for the current context. In the discussed setting, the feedback is revealed for all contexts. This significantly reduces the inherent difficulty of the contextual influence. Hence,\n\n(a)\tCan you please explain how having a context made the learning harder w.r.t the non-contextual MAB with feedback graph in this setting, conceptually?\n\n(b)\tHave you considered the standard Contextual setting in which only the feedback of the current context is released? Can you adjust your results to this setting as well? \n\n2.\tIt would benefit the reader if an additional explanation of equation (4) will be given. So is for the result stated in Lemma 3.1.  \n\n3.\tTypos - A comment that was left in the text: line 20: \"to name a few\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and the insightful questions.\n\n1.(a). In general, the oracle we compare in contextual bandits to is able to take different optimal actions under different contexts, so it is a stronger benchmark. Also, our work assumes adversarial context, so intuitively, a larger number of contexts increases the adversary’s ability to break the learner’s exploration plans and to craft a “harder” problem instance. The latter corresponds to increasing $M$ in the lower bound quantity $\\beta_M$ and thereby including extra independent subsets in the hard instance.\n\n1.(b). Yes it is straightforward to extend to the case with no information across contexts (by running $M$ instances of the single-context algorithm), which essentially becomes $M$ separate subproblems and leads to an optimal regret $\\widetilde{O}(\\sqrt{M\\alpha T})$.\n\n1.(c). It is however an interesting question when the feedback across contexts is not complete. Section 4.1 discusses the product graph case for weakly observable action graphs. We define product graphs as $(a_1, c_1)\\rightarrow (a_2,c_2)$ if $a_1\\rightarrow a_2$ and $c_1\\rightarrow c_2$ in their respective graphs (we'll make this definition clearer in text). When the action graph is strongly observable, we may extend our Theorem 1.1 and 1.3 with the following graph quantity (defined by both the action graph and the context graph) that shares the same spirit:\n$$\n\\beta' = \\max \\lbrace\\sum_{c=1}^{M}|I_c| : I_c\\subseteq V_c \\textnormal{ independent and } I_j\\not\\rightarrow I_k \\textnormal{ if } j<k \\rbrace\n$$\nand Theorem 1.4 with\n$$\n\\bar\\beta' = \\max\\lbrace \\sum_{c=1}^{M}|I_c| : I_c\\subseteq V_c \\textnormal{ independent} \\rbrace\n$$\nwhere $V_c=\\lbrace (a,c): a\\in[K] \\rbrace$.\n\n2. One can think of Eq (2) of $\\beta_M$ as sequentially taking out one independent subset (and its out-neighbors) as the hard instance for a context. Note those $I_c$’s are allowed to be empty. By the constraint of $I_j \\not\\rightarrow I_k$ for $j<k$, they form a DAG on the set level, so their total size cannot exceed the MAS number $\\mathsf{m}(G)$. Then when $M\\ge \\mathsf{m}(G)$, one can simply take the max acyclic subgraph and put one node for each $I_c$, while leaving $(M-\\mathsf{m}(G))$ of them empty. This shows $\\beta_M=\\mathsf{m}(G)$ when $M$ is sufficiently large, hence Corollary 1.2.\n\n3. As an example, consider a “monotone” graph across the actions: for actions in $[K]$, there is an edge $i\\rightarrow j$ iff $i<j$. With cross-learning among $M$ context, the quantity $\\beta_M=\\max\\lbrace M, \\mathsf{m}(G)\\rbrace$ increases from $\\alpha=1$ to $\\mathsf{m}(G)=K$ as $M$ grows. This example shows up in bidding in auctions (see Han et al. 2020 in our reference) with actions modeling the bidding values and contexts the values of the presented items.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "jwDfF6vgsO", "reviewer": "Reviewer_DvmA", "summary": "The authors consider the problem of contextual bandits with finitely many contexts, stochastic rewards and a directed feedback graph (assumed to contain all self loops) across actions. They study the setting of \"complete cross-learning\" where the reward feedback of the chosen action is observed across all contexts. In this setting, the authors establish a lower bound of $\\Omega(\\sqrt{\\beta_M(G) T})$ where $\\beta_M(G)$ is a graph-dependent quantity which lies between the independence number and the maximum acyclic subgraph of the feedback graph, and prove that this lower bound is tight for a specific class of context sequences by designing an efficient algorithm with a matching regret bound. Furthermore, the authors provide an upper bound for general context sequences with a graph dependence that improves upon the maximum acyclic subgraph, but in general may not be tight.", "questions": "I would appreciate it if the authors could address my main concern under \"Weaknesses\" and provide a more careful comparison with the work of [1].", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The authors establish regret upper and lower bounds that constitute a considerable step towards characterizing the minimax regret in contextual bandits with feedback graphs in the complete cross-learning framework.\n* The authors provide an overview of the hard instance construction which helps the reader understand the difficulty of minimizing regret in this setting.\n* The idea of incorporating a sequential graph-theoretic zero sum game in a bandit algorithm seems novel and very interesting.\n* Even though the authors close the gap completely only for specific types of context sequences, they also provide an upper bound for general sequences which improves upon the known upper bounds in the literature.", "weaknesses": "* My main issue with the presentation of the main results is with the comparison with the previous related work of [1] (lines 147-148). While the authors do mention that this work considers the setting of feedback graphs over the contexts as well as over the arms, it should be mentioned that it is not how the problem is presented in [1]. Rather, they consider a tabular RL problem in which the states correspond to the contexts, with the crucial difference that the transition between states is governed by some stochastic process. Since in the authors' work there is no assumption regarding the transition between contexts (that is, it could be adversarial), it seems not quite fair to compare their results to those of [1], specifically the regret lower bound. Indeed, the lower bound described by the authors is easily seen to be inapplicable in the setting of [1] as they vary the contexts (or states) in a very controlled adversarial manner. Therefore, I think the authors should emphasize that their lower bound does not provide a strengthening of the lower bound given in [1] for the RL setup.\n\n\n\nReferences:\n[1] Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Reinforcement learning with feedback graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for highlighting the difference between [1] and our work. Indeed [1] primarily studies the RL setting so their upper bound is more general than ours; however, our lower bound instance could be embedded into the tabular RL setting of [1]. Consider an episodic tabular RL with $H = 1$, so that the initial state at every episode is the context. Since the initial state can be adversarially chosen in [1], our lower bound construction is legitimate in this setting and could lead to better dependence on the graph structure. The general H can also be handled using an absorbing state. We will provide a more detailed comparison in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We appreciate the insightful reviews and questions from the reviewers and would like to highlight points that have drawn most attention here.
1. In addition to self-avoiding context (Theorem 1.3), Theorem 1.4 shows that our results are also tight for arbitrary context when the feedback graphs are either undirected or transitively closed (i.e. extra assumptions on the information structure between actions rather than context). The latter appears to find more realistic applications including bidding in auctions and inventory control.
2. While we assume self-loops in the current work, as pointed out by one reviewer, our results actually apply to all strongly observable graphs. The only difference is to add an extra constraint that $I_1,...,I_M$ are disjoint in definition (2) of $\beta_M$.
3. It is an interesting question to look beyond complete cross-learning over contexts. We partially discuss this in Section 4.1 on context-action product graphs when the action graph is weakly observable, where product graphs are defined as $(a_1,c_1)\rightarrow (a_2,c_2)$ if $a_1\rightarrow a_2$ and $c_1\rightarrow c_2$ in their respective graphs. It is straightforward to extend our results to the case of product graphs when the action graph is strongly observable too.

Meta-review: Reviewers find that the new graph theoretic quantity $\beta_M(G)$ to be interesting and are happy with how it is able to interpolate between the independence number and the MAS number of $G$ depending on the number of contexts. Reviewers are also happy with the fact that in  the setting of self-avoiding contexts the bounds appear nearly tight for most graphs. Reviewer 6nrr, however, correctly notes that the current bounds hold only for strongly observable graphs that have all self-loops and not for the entire set of strongly observable graphs. Further, multiple reviewers have expressed concerns about how realistic the self-avoiding contexts setting is. Reviewer 6nrr has also expressed concerns about the fact that the proposed algorithms will only work in the setting of a fixed feedback graph and can not easily be extended to time varying feedback graphs. However, all reviewers agree that the current work advances the study on what is the right graph theoretic quantity to characterize the regret in the stochastic CMAB problem with graph feedback.
Decision: Accept (poster)