Learning on the Edge: Online Learning with Stochastic Feedback Graphs
Authors: Emmanuel Esposito
Federico Fusco
Dirk van der Hoeven
Nicolò Cesa-Bianchi
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
feedback graphs
bandits
random graphs

Abstract: The framework of feedback graphs is a generalization of sequential decision-making with bandit or full information feedback. In this work, we study an extension where the directed feedback graph is stochastic, following a distribution similar to the classical Erdős-Rényi model. Specifically, in each round every edge in the graph is either realized or not with a distinct probability for each edge. We prove nearly optimal regret bounds of order $\min\bigl\{\min_{\varepsilon} \sqrt{(\alpha_\varepsilon/\varepsilon) T},\, \min_{\varepsilon} (\delta_\varepsilon/\varepsilon)^{1/3} T^{2/3}\bigr\}$ (ignoring logarithmic factors), where $\alpha_{\varepsilon}$ and $\delta_{\varepsilon}$ are graph-theoretic quantities measured on the support of the stochastic feedback graph $\mathcal{G}$ with edge probabilities thresholded at $\varepsilon$. Our result, which holds without any preliminary knowledge about $\mathcal{G}$, requires the learner to observe only the realized out-neighborhood of the chosen action. When the learner is allowed to observe the realization of the entire graph (but only the losses in the out-neighborhood of the chosen action), we derive a more efficient algorithm featuring a dependence on weighted versions of the independence and weak domination numbers that exhibits improved bounds for some special cases.

Learning on the Edge: Online Learning with Stochastic Feedback Graphs
Emmanuel Esposito"
Federico Fusco"
Dept. of Computer Science Università degli Studi di Milano, Italy & Istituto Italiano di Tecnologia, Italy emmanuel www.mmeeesspsstoooooo..ooo
Dept. of Computer, Control and Management Enginocring Sapienza Università di Roma, Italy fuscof@diag uniromal. it
Dirk van der Hoeven" Dept. of Computer Science Università degli Studi Milano, Italy dirtedirvanderheevenn.
Nicolò Cesa-Bianchs Dept. of Computer Science Università degli Studi Milano, Italy nicolo.cesa-bias cesa-bianchh Gunimi.
Abstract
The framework of feedback graphs is a generalization of sequential decision- making with bandit or full information feedback. In this work, we study an extension where the directed feedback graph is stochastic, following a distribution similar to the classical Erdös-Rényí model. Specifically, each round every edge in the graph is either realized or not with a dis- tinct probability for each edge. We prove nearly optimal regret bounds of order min ( mine V(az/s)T, (6833 (ignoring logarithmic fac- tors), where ag and 6 are graph-theorete theoretic quantities measured on the support of the stochastic feedback graph 9 with edge probabilities thresh- olded e. Our result, which holds without any preliminary knowledge about G, requires the learner to observe only the realized out-neighborbood of the chosen action. When the learner is allowed to observe the realization of the entire graph (but only the losses in the out-neighborhood of the chosen action), we derive a more efficient algorithm featuring a dependence weighted versions of the independence and weak domination numbers that exhibits improved bounds for some special cases.
1 Introduction
In this work we study an online learning framework for Docision-makinn with partial feedback. In each decision round, the learner chooses an action in a fixed set and is charged a loss. In our setting, the loss of any action in all decision rounds is preliminarily chosen by an adversary, but the feedback received by the learner at the end of each round is stochastic. More specifically, the loss of each action (including Tr, the one selected by the learner at round t) is independently observed with certain probability p(I, i), where the probabilities p(i.j) for all pairs i are fixed but unknown.
This feedback model can be viewed as a stochastic version of the feedback graph model for online learning [Mannor and Shamir, 2011], where the feedback received by the learner at the end of each round is determined by a directed graph defined over the set of actions. In this model, the learner deterministically observes the losses of all the actions in the
Equal contribution.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

out-neighborhood of the action selected in that round. In certain applications, however, deterministic feedback is not realistic. Consider for instance a sensor network for monitoring the environment, where the learner can decide which sensor to probe in order to maximize some performance measure. Fach probed sensor may also receive readings of other sensors, but whether sensor successfully transmits to another sensor depends on a number of environmental factors, which include the position of the two sensors, but also their internal state (e.g,, battery levels) and the weather conditions. Due to the variability of some of these factors, the possibility of reading from another sensor can be naturally modeled as a stochastic event.
Online learning with adversarial losses and stochastic feedback graphs has been studied before, but under fairly restrictive assumptions on the probabilities p(i.j). Let G be a stochastic feedback graph, represented by its probability matrix p(i.j) for i,j E V where V is the action set. When p(i.j) = & for all distinct i,j E V and for some > 0, then G follows the Erdös-Rény Rényi random graph model. Under the assumption that ε is known and p(i,i) 1 for all i E V (all self-loops occur w-p. 1), Alon et al. [2017] show that the optimal regret after T rounds is of order vT/E, up to logarithmic factors. This result has been extended by Kocák et al. [2016a], who prove a regret bound of order (1/E)) when the parameter E of the random graph is unknown and allowed to change over time. However, their result holds only under rather strong assumptions on the sequence E, for 2 1. In a recent work, Ghari and Shen [2022] show a regret bound of order (a/E)vKT KT, ignoring logarithmic factors, when each (unknown) probability p(i,j) in 9 is either zero or at least e for some known > 0, and all self-loops (i, have probability p(i. 2 e. Here a the independence number (computed ignoring edge orientations) of the support graph sUpp ie., the directed graph with adjacency matrix A(i, = (p(i.))00) Their bound holds under the assumption that supp(g) is preliminarily known to the learner.
Our analysis does away with a crucial assumption that was key to prove all previous results. Namely, we do not assume any special property of the matrix G, and we do not require the learner to have any preliminary knowledge of this matrix. The fact that positive edge probabilities
not bounded away from zero implies that the learner must choose a threshold e E (0, I] below which the edges are deemed to be too rare to be exploitable for learning. If e is too small, then waiting for rare edges slows down learning. On the other hand, if is too large, then the feedback becomes sparse and the regret increases.
To formalize the intuition of rare edges, introduce the notion of thresholded graph supp(G.) for any E > 0. This is the directed graph with adjacency matrix A(i,j) = [((k.)))2)) As the thresholded graph is deterministic feedback graph G, we can refer to Alon et al. [2015] for a characterization of minimax regret Ry based on whether G is not observable (Ry of order T), weakly observable (Rr of order 5 81/372/3), or strongly observable (Ry of order VaT). ! Here a and 8 are, respectively, the independence and the weak domination number of G; see Section 2 for definitions. Let ag and & respectively denote the independence number and the weak domination number of supp(G=). As ag and o, both grow when e gets larger, the ratios ag/E and de/e capture the trade-off involved in choosing e. We define the optimal values for e as follows:
= arg min
az {
{
supp(Ge) is strongly observable].
(1)
=E(0,1]
& : supp(Ge) is observable
* = arg min
(2)
rE(0.1]
We adopt the convention that the minimum of an empty set is infinity and the relative arg min is set to O. The arg min are well defined: there are at most K2 values of e for which the support of Go varies, and the minimum is attained in one of these values. For simplicity, we let a" = 0e; and 8' = dec. Our first. result. can be informally stated as follows.
Theorem (Informal). Consider the problem of online learning with an unknown stochastic feedback graph & on T time steps. If supp(G=) is not observable for = @(K3 then any learning algorithm suffers regret linear in T. Otherwise, there erists an algorithm whose
Alll these rates ignore logarithmic factors.
2

---

regret satisfies (ignoring polylog factors in K and T)
VV a*
8**
1/3 T2/3
RT S min
T,
E
Eie
This bound is light (up to polylog factors).
This result shows that, without any proliminary knowlodge of g, we can obtain bound that optimally trades off between the strongly observable rate y/ar///// /Et)T, for the best threshold e for which (up)(Ge) is strongly observable, and the (weakly) observable rate (6 (=t")) for the best threshold e for which supp(Se) is (weakly) observable. Note that this result improves on Ghari and Shen [2022] bound (e//s)/KT who additionally assume that supp(G:) and (a lower bound on the self-loop probabilities) are both preliminarily available to the learner. On the other hand, the algorithm achieving the bound of Theorem 1 need not receive any information (neither prior nor during the learning process) besides the stochastic feedback.
We obtain positive rosults in Theorem 1 via an claborate reduction to online lcarning with deterministic feedback graphs. Our algorithm works in two phases: first, it learns the odge probabilities in a round-robin procedure, then it commits to a carefully chosen estimate of the feedback graph and feeds it to an algorithm for online learning with deterministic feedback graphs. There are Iwo main technical challenges the algorithm faces: on the one hand, it needs to switch from the first to the second phase at the right time in order to achieve the optimal regret. On the other hand, in order for the reduction to work, it needs to simulate the behaviour of a deterministic feedback graph using only feedback from a stochastic feedback graph (with unknown edge probabilities). We complement the positive results in Theorem 1 with matching lower bounds that are obtained by a suitable modification of the hard instances in Alon et al. [2015, 2017] so as to consider stochastic feodback graphs.
Our last result is an algorithm that, at the cost of an additional assumption on the feedback (i.e., the learner additionally observes the realization of the entire leedback graph the end of each round), has regret which is never worse and may be considerably better than the regret of the algorithm in Theorem 1. While the bounds in Theorem are tight up to log factors, we show that the factors /s/s; and 8* 8*/E", can be improved for specific feedback graphs. Specifically, we design weighted versions of the independence and weak domination numbers, where the weights of a given node depend on the probabilities of seeing the loss of that node. On the tochnical side, we design a new importance-weighten estimator which uses a particular version of upper confidence bound estimates of the edge probabilities p(i. j), rather than the true edge probabilities, which are unknown. We show that the cost of using this estimator is of the same order the regret bound achievable had we known p(i,j). Additionally, the algorithm that obtains these improved bounds is more elficient than the algorithm of Theorem 1. The improvement in efficiency comes from the following idea: we start with an optimistic algorithm that assumes that the support of g is strongly observable and only switches to the assumption that the support of G is (weakly) observable when it estimates that the regret under this second assumption is smaller. The algorithm learns which regime is better by keeping track of bound on the regret of the optimistic algorithm while simultancously estimating the regret in the (weakly) obscrvable case, which it can do efficiently.
Additional related work. The problem of adversarial online learning with feedback graphs was introduced by Mannor and Shamir [2011], in the special case where all nodes in the feedback graph have self-loops. The results of Alon et al. [2015] (also based on prior work by Alon et al. [2013], Kocák et al. [2014]) have been recently slightly improved by Chen et al. [2021], with tighter constants in the regret bound. Variants of the adversarial setting have been studied by Feng and Loh [2018]. Arora et al. [2019], Rangi and Francoschetti [2019] and Van der Hocven et al. [2021], who study online learning with foedback graphs and switching costs and online multiclass classification with feedback graphs, respectively. There also a considerable amount of work in the stochastic setting [Liu et al., 2018, Cortes el al., 2019, Li et al., 2020). Finally, Rouyer et al. [2022] and Ito et al. [2022] independently designed different tost-oo-both-worle learning algorithms achieving nearly optimal (up to polylogarithmic factors in T') regret bounds in the adversarial and stochastic settings.
3

---

Following Mannor and Shamir [2011]; we can consider a more general scenario where the feedback graph is not fixed but changes over time, resulting in a sequence Gi...., of leedback graphs. Cohen et al. [2016] study a setting where the graphs are adversarially chosen and only the local structure of the feedback graph is observed. They show that, if the losses are generated by an adversary and all nodes always have self-loop, one cannot do better than VKT regret, and we might as well simply employ a standard bandit algorithm. Furthermore, removing the guarantee on the self-loops induces an ((T) regret. In Section 3, we are in a similar siluation, as we also observe only local information about the leedback graph and the losses are generated by an adversary. However, we show that if the graphs are dlochastically generated with a strongly observable support for some threshold e, there is VaT/E regret bound. As consequence, for not too small, observing only the local information about the feedback graphs is in fact sufficient to obtain better results than in the bandit setting. Similarly, if there are self-loops in the support but the support is weakly observable, then our regret bounds are sublinear rather than linear in T. Alon et al. [2013, 2017] and Kocák et al. [2014] also consider adversarially generated sequences G1, Go.... of deterministic feedback graphs. In the case of directed feedback graphs, Alon et al. [2013] investigate model in which G. is revealed to the learner at the beginning of each round f. Alon et al. [2017] and Kocák et al. [2014] extend this analysis to the case when G. is strongly observable and made available only at the end of each round t. In comparison, in our setting the graphs (or the local information about the graph) revealed to the learner (at the end of each round) may not even be obscrvable, let alone strongly obscrvable. Despite this seemingly challenging setting for previous works, we nevertheless obtain sublinear regret bounds. Finally, Kocák al. [2016b] study feedback model where the losses of other actions in the out-neighborhood of the action played are observed with an edge-dependent noise. In their setting, the feedback graphs G2 are weighted and revealed at the beginning of each round. They introduce edge weights sz(i,j) E [0.1] that determine the feedback according to the following additive noise model: se( (:()) is a zero- mean bounded random variable. Hence, if (i. = 1, then I, = i allows to observe the loss of action j without any noise. If (i. = 0, then only noise observed. Note that they assume st () = 1 for cach i, implying strong observability. Although similar in spirit to our foedback model, our results do not directly compare with theirs.
+ (1 sy ()),, where
Further work also takes into account a Lime-varying probability for the revelation of side- observations [Koeák et al., 2016a]. While the idea of a general probabilistie feedback graph has been already considered in the stochastic setting [Li et al., 2020, Cortes et al., 2020], the recent work by Ghari and Shen [2022] seems to be the first one in the adversarial setting that generalizes from the Erdös-Rényl model to a more flexible distribution where they allow " "odgo-specific" probabilities. We remark, however, that the assumptions of Ghari and Shen [2022] exclude some important instances of feedback graphs. For example, we cannot hope to employ their algorithm for efficiently solving the revealing action problem (see for example [Alon et al., 2015)). In a spirit similar to ours, Resler and Mansour [2019] studied a version of the problem where the topology of the graph is fixed and known a priori, but the feedback received by the learner is perturbed when traversing edges.
2 Problem Setting
A feedback graph over a set == [K] of actions is any directed graph G = E), possibly with self-loops. For any vertex E V. we use Nin = [j E (], E} to denote the in-neighborhood of and (g) = [j E V (i.j) E F} to denote its out-neighborhood (we may omit the subscript when the graph is clear from the context). The independence number (G)) of a feedback graph G is the cardinality of the largest subset S of V such that, for all distinct i,j E S, it holds that (i, and (j,i) are not in E. We also use the following terminology for directed graphs G = (V, E) [Alon et al., 2015]. Any E V is: observable if Nin (i) * 0, strongly observable if i E Ni (i) or V Vi S (1), and weakly observable if it is observable but not strongly. The graph G is: observable if all i E V are observable, songly observable all E V are strongly observable, and weakly observable it is observable but not strongly. The weak domination number 5(G) of G is the cardinality of the smallest subset S of V such that for all weakly observable i E V V.S S there exists j E S such that (j,i) E E.
4

---

In the online learning problem with stochastic feedback graph, an oblivious adversary privately chooses a stochastic feedback graph and a sequence f, l2... of loss functions 4: V [0, I]. At each round 1 == 1,2..... the learner selects an action I, E V to play and, independently, the adversary draws a feedback graph G. from & (denoted by G. ~ 9). The learner then incurs loss le(le) and observes the feedback {i, (i,)((i) : i NG. (4)) In some cases we consider richer feedback, where at the end of cach round the learner also observes the realized graph Gr. The learner's performance is mcasured using the standard notion of regret,
Σ (c,(1)) ((11)-4000) e()))
RT max E REV
where /,,..,, /T are the actions played by the learner, and the expectation is computed over both the sequence G GT of leedback graphs drawn iidd. from g and the learner's internal randomization.
Fix any stochastic feedback graph g {p(i,)) i,j E VJ. We sometimes use e to denote a pair (i,j), in which case we write Pe to denote the probability p(i.j). When G, (V, Fi)) is drawn from G, each pair (i,j) E
independently becomes an edge (i.e., (i.j) E F.)) with probability j). For any E >>> 0, we define the thresholded version Ge of g represented by () i,j E V), where p' (t, = p(i. p(i.))[(p(.))ee) We also define the support feedback graph of G as the graph supp(g)
(V, E) having = {(i.j) V x V p(i.j) 0}. To keep the notation tidy, we write (g)) instead of ((supp(G)) and similarly for 5.
3 Block Decomposition Approach
In this section, we present. an algorithm for online learning with stochastic leedback graphs via a reduction to online learning with deterministic feedback graphs. Our algorithm EdgeCAtCher (Algorithm 3) has an initial exploration phase followed by a commit phase. In the exploration phase, the edge probabilities are learned online in round-robin fashion. carefully designed stopping criterion then triggers the commit phase, where we feed the support of the estimated stochastic feedback graph to an algorithm for online lcarning with (deterministic) feodback graphs.
3.1 Estimating the Edge Probabilities
As first. step we design a routine, ROUNDROBIN (Algorithm 1), that sequentially estimates the stochastic feedback graph until a certain stopping criterion is met. The stopping criterion depends on a nonnegative function together with a time horizon. Let f < T/K K be the index of the last iteration of the outer for loop in Algorithm 1. We want to make sure that, for all 7 I f, the stochastic foodback graphs G are valid estimates of the underlying G up to O(e,) precision. To formalize this notion of approximation, we introduce the following definition.
that takes in input a stochastic feedback graph G
C (s-good approximation). A stochastic feedback graph (pe C C2V is an e-good approzimation of tpe : V23 for some E (0, 1], if the following holds:
Definition
1. All the edges supp(g) with pe 2 2s belong to supp(ś);
2. For all edges e supp(ÿ) with Pv 2 8/2 il holds that lp. Pel S Pc/2;
3. No edge e E 2 with Pe < e/2 belongs to supp(ÿ).
We can now state the following theorem; we defer the proof in Appendix B. The proof follows from an application of the multiplicative Chernoff bound on edge probabilities.
Theorem 2. If ROUNDROBIN (Algorithm 1) is run on the stochastic feedback graph G, then, with probabilily at leust 1 1/T, the eslimale G is an e--yood ayprocimation of G simaltannoussy for all t S 7, where f & T/K is the inder of the last iteration of the outer for loop in Algorithm 1.
5

---

Algorithm 1: ROUNDROBIN
Environment:
stochastic feedback graph 9, sequence of losses l,, l2 .2....,,7 Pr;
Input: time horizon T, stopping function Φ, actions V 2 K];
ne 0, for all E V2:
for each T = 1, 1...... for each i= 1, K do
LT/K] do
Play action and observe NG. (i) from G2 ~ 9; 1/ t is the time step
Th + ne + for all E Ng,((); (i); P. t ne/T for all edges e V
& + (0n(KT)/T;
G. + (V,fee
P. 2 +7)) with weights P.:
// estimated feedback graph
if (T, S 7K then
output Gr, Eri output Gr, Egj
3.2 Block Dccomposition: Reduction to Deterministic Feedback Graph
As a second step, we present REDCCIRD (Algorithm 2) which reduces the problem of online learning with stochastic feedback graph to the corresponding problem with deter- ministic feedback graph. Surprisingly enough, in order for this reduction to work, we do not need the exact edge probabilities: an e-good approximation sufficient for this purpose.
The intuition behind BLOCKREDUCTION is simple: given that each edge e in supp(Se) appears in Gt with probability Pe 2 E at each time step f, we wait for (((1/)) In())) time steps it will appear at least once with high probability. Applying union bound over all edges, we can argue that considering A = ((1/E) (n(K)) realizations of the stochastic feedback graph, then all the edges in supp(Ge) are realized at least once with high probability.
Imagine now to play a certain action a consistently during a block B, of A time steps. We want reconstruct the average loss suffered by a' in By:
c, (a')= = Σ ((aa)
(3)
A
IEB,
and we want to do it for all a' in the out-neighborhood of a. Let Ta.a' be the number of times that the loss of a' observed by the learner; i.e., the number of times that (a, a') is realized in the A time steps. With this notation, we can define the natural estimator é, (a'):
(a') = E(la)) [((an))ER.) IEB,
(4)
((aay)
Conditioning on the event aT that the edge (a, a') in G is observed least once in block B,, we show in Lemma 2 in Appendix B that (a') is an unbiased estimator of e, (a').
construct unbiased estimators of the average of the losses on the blocks as the stochastic feedback graph were deterministic. This allows us to reduce the original problem to that of online learning with deterministic feedback graph given by the blocks. The details of BLOCKREDUCTION are reported in Algorithm 2, while the theoretical properties summarized in the next result, whose proof can be found in Appendix B.
Therefore,
the meta-instance
Theorem 3. Consider the problem of online learning with stochastic feedback graph G, and let & be an e-good upprozimation of G. Let A be an algorithm for online learning with arbitrary deterministic feedback graph G with regret bound RA( over any sequence of N losses in [0. 1]. Then, the regret of BLOCCKEDDCTION (Algorithm 2) run with input (T,e/2, G, A) is at most ARA (supp())) + A, where N = [T/A] and A In(K))]

---

Algorithm 2: BLOCKREDUCTION
..... .., er; Input: time horizon Т, threshold E, estimate & of G, learning algorithm A: A - [n(K))], N + [T/A], G suppp()); Initialize A with time horizon N and graph G; B, < {(T ( 1)A 1..... 7A), for all 7 7= 1.
Environment: stochastic feedback graph 9, sequence of losses l,, l2
for each round = 1, 1,2...., NN do
Draw action a, from the probability distribution over actions output by A; for each round t E B, do
Play action 0, and observe the revealed feedback;
11 G. ~
For all a' e N (a+), compute (a') as in (4), and feed them to A; Play arbitrarily the remaining T AN rounds;
For online learning with deterministic feedback graphs we use the variants of ExP3. G contained in Alon et al. [2015). Together with Theorem 3, this gives the following corollary; the details of the proof are in Appendix B.
Corollary 1. Consider the problem of online learning with stochastic feedback graph G, and let 9 be an E-good approrimation of G for 1/T and with support G.
If is strongly observable with independence number a, then the regret of BLOCKRE- DUCTION run with parameter 8/2 using EXP3. G for strongly observable graphs as base 3/2 where C, > O is constant in the algorithm A satisfies: Rr S (C.T((/))T(((((TTT) regret bound of A.
If G is (weakly) observable with weak domination number 8, then the regret of BLOCKRE- DUCTION run with porameter e/2 using ExP3. G. for weakly observable graphs as base 2/3TT/3 2/3 where Cw > 0 is constant
algorithm A satisfies: Rr 4Cu(6//) (In(KT)) in the regret bound of A.
Note that can explicitly compute valid constants C, 12 + 2v2 and C.,, 8 directly from the bounds in Alon et al. [2015].
3.3 Explore then Commit to a Graph
We are now ready to combine the two routines we presented, ROUNDROBIN and BLOCKRE- DUCTION, our final learning algorithm, EDGECATCHER. EDGECATCHER has two phases: in the first phase, ROUNDROBIN used to quickly obtain an s-good approximation & of the underlying feedback graph G, for suitable e. In the second phase, the algorithm commits to 9 and feeds it to BEDOCTRR,UCTION, The crucial point is when to commit to certain (estimated) stochastic feedback graph. If we commit too carly, we might not observe a denser support graph, which implics missing out on a richer feedback. If we wait for too long, then the exploration phase ends up dominating the regret. To balance this trade-off, we use the stopping function &. This function takes input probabilistic feedback graph together with a time horizon and outputs the regret bound that REDUCTIN would guarantee on this pair. It is defined
(GG,T) min 4C, V T(I(((T))) 3/2 40
a
(II(KT)))))
(8' E
1/3 2//
(5)
for the specific choice of ExP3. G as the learning algorithm A adopted by BLoCcKRDDCTION.
Note that the dependence of & on the foodback graph G contained in the topological parameters a and 8* and the corresponding thresholds et and e;,, defined in Equations (1) and (2); see Appendix A for more details on their compulation. If we apply to stochastic feedback graph that is observable w.p. zero, its value is conventionally set to infinity. Observe that, otherwise, the min achieved for specific e* and a specifie G* g...
In Appendix B, provide sequence of lemmas (Lemmas 3 and 4 in particular) showing

---

Algorithm 3: EDGECATCHER
Environment:
stochastic feedback graph 9, sequence of losses E,, l2 ,,,
Input:
time horizon T and actions V = (1,
Let & defined as in Equation (5);
Run ROUNDROBINT,, 4, V) and obtain & and é; Compute e and ew for graph & as in Equations (1) and (2);
Let e" be the best threshold as in Equation (5):
if é" then Let A be ExP3.G for strongly observable feedback graph;
else Let A be ExP3.G G for weakly observable feedback graph; Let = tK be the remaining time steps;
// $ as ROUNDROBIN
Run BLOCKREDUCTION(T, , /2, A);
Chat, if ROUNDROBIN outputs an s-good approximation of the graph, then the regret is bounded by multiple of the stopping criterion evaluated G. Combined with Theorem which tells us that ROUNDROBIN does in fact output an E-good approximation of the graph with high probability, this proves our main result for this section.
Theorem 4. Consider the problem of online learning with stochastic feedback graph G on T time steps. If supp(Ge(K.T)) is observable for E(K,T) CK (K*(M(()))))) for a given constant C > 0, then there exists algorithm whose regret Rr satisfies (ignoring polylog factors in K and T) Rr S min { [V(ar/Eg)T (8" /Em) (=t))=)))))) 1//3 2
4 Lower Bounds
In this section, we provide lower bounds that match the regret bound guaranteed by EDgeCAtCHER, shown in Theorem 4, up to polylogarithmic factors in K and T. These lower bounds are valid even if the learner is allowed to observe the realization of the entire feedback graph every time step, and knows a priori the "correct" threshold e to work with. Theorem 5 summarizes the lower bounds whose proofs can be found in Appendix C.
Theorem 5 (Informal). Let A be a possibly randomized algorithm for the online learning problem with stochastic feedback graphs. Consider any directed graph G = EV, with [V] and any E 10, There erists a stochastic feedback graph G with supp(g) G and, for sufficiently large time horizon T, there is sequence fi...., fr of loss functions on which the expected regret of A with respect the stochastic generation of GI...., GT ~ G is
((V(((G))EEE)) if G is strongly observable;
(((6(3)))=))/$1113) if G weakly observable; Q(T) if G is not observable.
The lower bound in the non-observable case is the same Alon et al. [2015, Theorem 6] with a deterministic leedback graph. The remaining lower bounds are nontrivial adaptations of the corresponding bounds for the deterministic case by Alon et al. [2015, 2017]. The main technical hurdle is due to the stochastic nature of the feedback graph, which needs to be taken into account in the proofs. The rationale behind the constructions used for proving the lower bounds is as follows: since each edge is realized only with probability e, any algorithm requires 1/c rounds in expectation in order to observe the loss of an action in the out-ncighborhood of the played action, whereas one round would suffice with a deterministic feedback graph. Note that Theorem implics that, if supp(Ge(k,T)) is not observable for e(K, T) as in Theorem 4, then there is hope to achieve sublinear regret, the lower bounds for both strongly and weakly observable supports are linear in T for all < =(K, T).
Refined Graph-Theoretic Parameters
Although the results from Section 3 are worst-case optimal up to log factors, we may find that the factors Va(Ge)/E and (8(G))/e)1/8 for strongly and weakly observable supp(Ge) = G..
8

---

respectively, may be improved upon in certain cases. In particular, we show that, under additional assumptions on the feedback that we receive, we can obtain better regret bounds. To understand our results, we need some initial definitions. The weighted independence number for a graph = (V, F) and positive vertex weights w(() for i E V is defined as
aw(H, w)
max EiEs w(1)
SEI(H)
where [(H denotes the family of independent sets in H. We consider two different weight assignments computed in terms of any stochastic feedback graph 9 with edge probabilities p(i.j) and supp(g) = G. They are defined as " (1) (min)enng()) p(i, i)) and wg (i) = (minjeNg' j)) Then, the two corresponding weighted independence numbers are or (9) (G, w and o (g) (w, The parameter of interest for the results in this section is (g) aw (9) + a (G). For more details on the weighted independence number see Appendix E. We also use the following definitions of weighted weak domination number 6w for a graph and positive vertex weights w, and self-obscrvability paramcter a:
(1,, w)
min ENED w01)
(C)) -mmeenge (p(i,
DED(H)
where D(H) denotes the family of weakly dominating sets in H. In this section, we focus on the weighted weak domination number dG) = 5w(G, wt). To gain some intuition on the graph-theoretic parameters introduced above, consider the graph with only self-loops, also used in Example 1 below. If all p(i, e, the learner needs to pull a single arm 1/e times for one observation in expectation, and K/E times to see the losses of all arms once. However, when the edge probabilities are different we need to pull arms for Σ 1/p(i, i) times. The weighted independence number, weighted weak domination and self-observability generalize this intuition and tell us how many observations the learner needs to see all losses at least once in expectation. We now state the main result of this section.
Theorem 6 (Informal). There erists an algorithm with per-round rumning time of O(K1) and whose regrel is bounded (ignoring logurithmic faclors) by
min T. min (an() supp(Ge) is strongly observable).
min (G.)) + Vo(G.)T supp(G:) is observable) }
The regret bound in Theorem 6 follows from Theorem 11 in Appendix D. The rumning time bound is determined by approximating ow for all K2 possible thresholds. In each of the thresholded graphs, we can compute a (In(K) + 1>-approximation for the weighted weak domination number in O(K2) time by reduction to set cover [Vazirani, 2001]. Doing so only introduces an extra factor of order (In(K))1/3 in the regret bound.
An important property of the bound in Theorem 6 is that it is never worse than the bounds obtained before. The following example shows that the regret bound in Theorem can also be better than previously obtained regret bounds.
Example 1 (Faulty bandits). Consider stochastic feedback graph G for the K-armed bandit setting: p(i, = e E (0, 1] for all E V and p(i,j) = 0 for all j. In this case, the //T//miiina/i regret of EDGECATCHER is Ö(V /KT/TT/// (min, E;)). On the other hand, Theorem 6 provides
the bound ((TEE,)) for some i V while E2 1 for all j i, the regret of EDGECATCHER ÖKKKT))) while Theorem 6 guarantees a Ō(v(K + +//37) regret bound.
aw = 2 E, 1/e,. In the special case when E E (0, I]
To derive these lighter bounds, we exploit the additional assumption that the realized feedback graph G, is observed at the end of each round. This allows us to simallaneously estimate the feedback graph and control the regret, rather than performing these two tasks sequentially as in Section 3. In particular, we use this extra information to construct novel
9

---

importanne-weighred estimator for the loss, which for & > 1 is defined to be
(i( E.(1) - P.(1)
(6)
where P((i) =
= ESENa To (i)po 1) is the estimated probability of observing the loss of
arm i at round t, Te(i) is the distribution we sample I from, and G. is the support of the estimated graph Ge. Note that ignore losses that receive due to missing edges in G.. We show that we pay additive term in the regret for wrongly estimating edge, which is why it is important to control which edges are in G.. Ideally, would use Pi(() = EieNy, (1) (e))p(( i) rather than Pi)),, as this is the true probability of observing the loss of arm i in round However, since we do not have access to p(j. i), we use instcad an upper confidence estimate of p(j.i) for rounds 2 2 given by
p.(j. = () + 2))(3. 1-1 In(3K272) + 1-1 In(3K2T2)
where Pi().)) 1-1 E.sl ((..))). We denote by GuCnn the stochastic graph with edge probabilitics Pe(j, i). Noto that the support of QUCB is a complete graph because (e. i) > 0 for all (),1) V x V. These estimators for the edge probabilities are sufficiently good for our purposes whenever event IC occurs, which we define as the event that, for all t 2 2,
22)( f-1 (3332T3) + t-1 In(3KTT9) V(..)EVVV.
3
-(i.t)
An important property of & can be found in Lemma below. It tells that we may treat & as if event I. is always realized, i.e., i) is always an upper bound estimator on p(j. i). The proof of Lemma is implied by Lemma in Appendix D.
Lemma 1 (Informal). Let en denole the busis vector with ex(1) I(s=k) as i-th entry for each i [K]. The loss estimate & defined in (6) satisfies
K
(me(t)-ex(0)) (x0)) K]] k (7)
RT =Ö E Σ
(i) (t - (1)
IC
+ max E REV
ΣΣ 1=2 i=1
(((i) P(s) additional regret compared to when we know i). Lemma also shows that & behaves nicely in the sense that, conditioned on KC, we have Ee(i) I ((()) ((e)(()))
Lemma shows that we only suffer δ OV
4(i) (iEEN"" (1))- This is crucial property to bound the regret of our algorithm. We show that, with modified version of ExP3.G [Alon et al., 2015], the second sum on the right-hand side of (7) is bounded by a term of order
T.(i) V V EK P(()): meaning that the regret is also bounded similarly. Our final step is to prove that the above term is bounded in terms of the minimum of the weighted independence number and the weighted weak domination number plus self-observabillty.
Acknowledgments and Disclosure of Funding
Nicolò Cesa-Bianchi, Federico Fusco and Dirk van der Hoeven gratefully acknowledge partial support by the MIUR PRIN grant Algorithms, Games, and Digital Markets (ALGADIMA)). Nicolò Desa-Bianchi and Emmanucl Esposito were also supported by the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 951847, project ELISE, and by the project "One Health Action Hub: University Task Force for the resilience of territorial ecosysterss" funded by Università degli Studi di Milano. Federico Fusco was also supported by the ERC Advanced Grant 788893 AMDROMA " "Algorithmic and Mechanism Design Research in Online Markets".
10

---

References
Noga Alon, Nicolò Cesa-Bianchi, Clandio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. In Advances in Newral Information Processing Systems, pages 1610 1618, 2013.
Noga Alon, Nicolò Cesa- Besa-BBancchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pages 23-35, 2015.
Noga Alon, Nicolò Cesa- Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastie multi-armed bandits with graph-structured leedback. SIAM Journal Computing, (6(6):1775-1822))) 2017.
Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. In Advances in Newrol Information Processing Systems, pages 10397-10407, 2019.
Jean- Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International Conference on Algorithmic Learning Theory, pages 150-165, 2007.
Brenda S. Baker. Approsimation algorithms for NP-complete problems planar graphs. Journal of the Association for Computing Machinery, 41(1):153-11 180, 1994.
Houshuang Chen, Zengfeng Huang, Shuai Li, and Chihao Zhang. Understanding bandits with graph feedback. In Advances in Neural Information Processing Systems, pages 24659 206-22466, 2021.
Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feodback graphs without the graphs. In International Conference on Machine Learning, pages 811 819, 2016.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with sleeping experts and feedback graphs. In International Conference on Machine Learning, pages 1370 1378, 2019.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Online learning with dependent stochastic feedback graphs. In International Conference on Machine Learning, pages 2154 2163, 2020.
Zhili Feng and Po-Ling Loh. Online learning with graph-structured leedback against adaptive adversaries. In IEEE International Symposium on Information Theory, pages 931-935, 2018
Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In Conference on Learning Theory, pages 176-196, 2014.
Pouya M. Ghari and Yanning Shen. Online learning with probabilistic feedback. In JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4183-4187, 2022.
Magnús Már Halldórsson and Jaikumar Radhakrishnan. Greed is good: Approximating independent sets sparse and bounded-degree graphs. Algorithmicn, 18:145-163, 1997.
Dirk van der Hoeven, Tim van Erven, and Wojeiech Kotlowski. The many faces of exponential weights in online learning. In Conference Learning Theory, pages 2067-2092, 2018.
Dirk van der Hoeven, Federico Fusco, and Nicolò Cosa-Bianchi. Beyond bandit foedback in online multiclass classification. In Advances in Neural Information Processing Systems, pages 13280 13291, 2021.
Johan Hästad. Clique is hard to approximate within n!-s, Acta Mathematica, 182:105-142, 1999.
Shinji Tto, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-bott--wolldds algorithms for online learning with feedback graphs. CoRR, abs/ 2200000873 2022.
11

---

Tomás Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit exploration bandit problems with side observations. In Advonces in Neural Information 2014.
Processing Systems, pages
Tomás Kocák, Gergely Neu, and Michal Valko. Online learning with Erdös-Rény: side- observation graphs. In Proceedings of the Thirty-Second Conference on Uncertainty in Arlificial Intelligence, 2016a.
Tomáš Kocák, Gergely Neu, and Michal Valko. Online learning with noisy side obscrvations. In International Conference on Artificial Intelligence and Statistics, pages 1186-1194, 2016b.
Shuai Li, Wei Chen, Zheng Wen, and Kwong-Sak Leung. Stochastic online learning with probabilistic graph feedback. In Proceeding of the Thirty-Fourth Fourth AAAT Conference on Artificial Intelligence, pages 4675-4682, 2020.
Fang Liu, Swapna Buccapatnam, and Ness B. Shroff. Information directed sampling for stochastic bandits with graph leedback. Tn Proceedings of the Thirby-Second A AAAT Conference on Artificial Intelligence, pages 9643-3650 2018.
Shic Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. In Advances in Neural Information Processing Systems, pages 684 684-692, 2011.
Michael Mitzenmacher and Eli Upfal. Probobility and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Anshuka Rangi and Massimo Franceschetti. Online learning with feedback graphs and switching costs. In International Conference on Artificial Intelligence and Statistics, pages
2019.
Alon Resler and Yishay Mansour. Adversarial online learning with noise. In International Conference on Machine Learning, pages 5429 5437, 2019.
Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Bianchi. and Yevgeny Seldin. A near- optimal bost-of-bothhworlld algorithm for online lcarning with feedback graphs. CoRR, 0t5/22206005555 2022.
Shuichi Sakai, Mitsunori Togasaki, and Koichi Yamazaki. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics, 126(2-3): 313-322, 2003.
Vijay V. Vazirani. Approzimation Algorithms. Springer, 2001.
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Compuler Science, pages 222 227, 1977.
David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3:103 128, 2007.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] All the results claimed in the abstract have proofs cither in the main body or appendix
(b) Did you describe the limitations of your work? [Yes] For each result we state the parameters under which the result holds.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work is primarily theoretical and we do not foresce any potential negative socictal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

2. If you are inchuding theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Although some proofs may only appear in the appendix.
3. Tf you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g,, data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [//A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/ curaling/releasing reeeeeieegnnggggee new assets...
(a) If your work uses existing assels, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as
URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/cum curratin? [N/A]
(e) Did you discuss whether the data you are using/curatingg contains personally
identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots,
if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "oLnVmI9vp2r", "reviewer": "Reviewer_FkW2", "summary": "This paper provides online learning with stochastic feedback graphs, which is a generalization of vanilla online learning with feedback graphs in the sense that the feedback is stochastic.\nThe authors provide regret upper bound, which is a natural extension of the regret bound in the vanilla setting under milder conditions than the one in many existing works.\nA more efficient algorithm is provided under the assumption that the learner can observe the realization of the entire graph.\nTheir algorithm is based on the idea of reducing the considering problem to the vanilla one by introducing threshold $\\epsilon$.", "questions": "- Is it in most cases that the $\\sqrt{(\\alpha_\\epsilon/\\epsilon) T}$ is much smaller than the other $(\\delta_\\epsilon/\\epsilon)^{1/3} T^{2/3} \\$?\n- The considered setting can also be regarded as online learning with time-varying feedback graphs. Could the authors point out the relation between that setting?", "limitations": "Not applicable", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Assumptions on the underlying graph are largely relaxed.\n- The limitations of existing are well described.\n- The paper is well organized and written.\n\nWeaknesses: \n\n(minor)\n- The notation $\\Delta$ around Eq.(3) is a bit confusing.\n- The definition of $\\Phi$ is given in page 7 while it is used in Algorithm 1 (page 5). I would like to see the definition or reference in page 5.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RATlcT47NbF", "reviewer": "Reviewer_e1KK", "summary": "This paper considers the problem of bandits with stochastic graph feedback. Specifically, each edge of the feedback graph is realized with a fixed probability at each round instead of the deterministic setting. The authors propose a novel algorithm which achieves $O\\left(\\min\\{\\sqrt{\\alpha T/\\epsilon_1}, (\\delta/\\epsilon_2)^{1/3}T^{2/3}\\}\\right)$ regret bound where $\\alpha$ is the independent number of the graph clipped on $\\epsilon_1$ and $\\delta$ is the weak domination number clipped on $\\epsilon_2$. The algorithm contains three components, including one part exploring the structure of the graph,  one part exploiting the graph by picking one action over a period of rounds and one part that decides when to switch from the exploration part to the exploitation part. The authors also show the almost matching lower bound of this problem. Finally, based on a stronger assumption on the observations, the authors derive an algorithm with tighter regret bound.", "questions": "See suggestions in \"Strengths And Weaknesses\".", "limitations": "Yes, the authors addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The problem considered in this paper is well motivated and interesting.\n- The paper is well written. The algorithms are intuitive and nicely explained.\n- The proposed algorithm is novel to me and the authors show that the algorithm achieves the near-optimal regret bound. Although the first exploration part and the second exploitation (block-wise strategy) are very intuitive and classic in the stochastic graph feedback problem, the transition condition between the two parts require some novelty and the authors address this issue by carefully balancing the regret in the exploration phase and the exploitation phase. I checked the proofs for sec 3 and sec 4 and briefly checked the proofs in sec 5 and based on what I have checked, the proofs make sense to me.\n\nWeakness:\n- Overall I do not find any major weaknesses with the current work. There are some minor typos and issues:\n-- line 206 and 208: I think here $\\Delta=O((1/\\epsilon)\\ln(KT))$ should be $\\Delta=\\Omega((1/\\epsilon)\\ln(KT))$ or at least $\\Delta=\\Theta((1/\\epsilon)\\ln(KT))$\n-- Algorithm 4 looks very dense to me. It would be better if there are more explanations in the some lines of the algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "B5fkzkvRBBj", "reviewer": "Reviewer_MMd7", "summary": "The paper considers the online learning problem with adversarial rewards and a stochastic feedback graph. There has been a line of research on this problem, most of them need some assumptions on the graph structure and knowledge about the parameter of the graph. The main contribution of the paper is a minimax optimal algorithm with a less stringent assumption on the graph structure and needs no knowledge about the graph parameter. The main idea of the algorithm is to estimate the graph structure properly and feed the estimated graph to the Exp3.G algorithm (cf. https://arxiv.org/abs/1502.07617). Furthermore, the paper shows that if we observe not only the realized reward but also the realized graph, we can achieve better regret in some problem instances.", "questions": "The related work section could be improved. This section looks like a simple enumeration of existing research, with little discussion about the relationship between this paper and prior work. For example, it says that “Following Mannor and Shamir [2011], we can consider a more general scenario where the feedback graph is not fixed but changes over time, resulting in a sequence G1, . . . , GT of feedback graphs [Alon et al., 2013, 2017, Kocák et al., 2014, 2016b, Cohen et al., 2016].” If the author could elaborate on the similarity and differences between the scenario of their paper and the scenario of this line of work, the related work section will be more informative.", "limitations": "I don't see potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The contribution of the paper is solid. It generalizes existing research in an interesting way. The algorithm only assumes that all edges in the stochastic graph are independent, and needs no more knowledge about the graph structure. \nStrength:\n1. The paper is well written. The idea is clearly presented.\n2. The paper generalizes existing research by relaxing the assumption significantly.\n3. The upper bound has a matching minimax lower bound.\n4. The author reduces the stochastic feedback graph problem to the deterministic feedback graph problem in a nontrivial way.\nWeakness:\n1. The main algorithm is a reduction to the well-known Exp3.G algorithm, thus the novelty is not significant.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0tcX_NMq_Ps", "reviewer": "Reviewer_z5ND", "summary": "The paper studies the online learning framework with stochastic feedback graphs. Unlike previous works, no assumptions are made on the feedback graphs. A regret-minimization algorithm, namely EdgeCatcher, is proposed and its regret bounds are analyzed in 3 cases where the feedback graphs are either strongly observable, observable or not observable. A lower bound is derived matching the upper-bounds guarantees of EdgeCatcher. Tighter bounds are also derived in the case where the entire feedback graph is observed at the end of each round. ", "questions": "What is the complexity of computing $\\varepsilon_s^*$ and $\\varepsilon_w^*$ in (1) and (2)? Is there any better way to compute them  than considering each possible value of epsilon  in a brute-force manner? Similar question for the terms defined in Section 5.\n\nThe stopping criterion $\\Phi$ defined in (5) depends on the constants $C_s, C_w$; so it also depends on the choice of algorithm A (so it should be written as $\\Phi(\\mathcal{G}, T, \\mathcal{A})$. By (1) and (2), in the non-observable case, this $\\Phi$ becomes infinite and then the RoundRobin will be played until $T/K$; then Blockreduction is called upon the remaining rounds. Will this lead to a linear regret?\n\nThe condition on $\\varepsilon$ in Corollary 1 is rather counter-intuitive: as I understand, the smaller epsilon, the better approximation we have from RoundRobin, why do we need to have a lower-bound of $\\varepsilon$ here, i.e., even if one can somehow obtain a better approximation, we cannot use it?\n\nAny motivational examples for the cases considered in Section 5, or is this purely a theoretical question whether one can gets better guarantees? I might be mistaken but the notation $\\hat{H}_t$  (Equation (6)) does not seem to be introduced anywhere. \n\n\n\n\n", "limitations": " the authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper is well-written and easy to follow. The presented results are interesting and relevant to the community. Although the proposed algorithms are based on previously known ideas, the combination of such elements in building up EdgeCatcher is quite elegant and interesting. \n\nWeaknesses: certain parts in the main text requires more discussions (see below). Concrete examples and/or numerical experiments to show the performance of the proposed algorithms will be appreciated. \n\nAfter the rebuttal phase: the authors answer the raised concerns. I am willing to increase the score to 7.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept