Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality
Authors: Teodor Vanislavov Marinov
Mehryar Mohri
Julian Zimmert
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandits
Online learning

Abstract: We revisit the problem of stochastic online learning with feedback
graphs, with the goal of devising algorithms that are optimal, up to
constants, both asymptotically and in finite time. We show that,
surprisingly, the notion of optimal finite-time regret is not a
uniquely defined property in this context and that, in general, it
is decoupled from the asymptotic rate. We discuss alternative
choices and propose a notion of finite-time optimality that we argue
is \emph{meaningful}. For that notion, we give an algorithm that
admits quasi-optimal regret both in finite-time and asymptotically.

Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality
Teodor Marinov Google Research
Mehryar Mohri Google Research & Courant Institute mohri cchri@google. com
Julian Zimmert Google Research zimmert wegooreeeeogee..oomommo com
Evmarinev@google.coom com
Abstract
We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite time. We show that, surprisingly, the notion of optimal umite-time regret not a uniquely defined property in this context and that, in general, it is decoupled from the asymptotic rate. We discuss alternative choices and propose a notion of finite-time optimality that we argue is meaningful. For that notion, we give algorithm that admits quasi-optimal regret both in finite-time and asymptotically.
Introduction
Online learning is a sequential decision making game in which, at each round, the learner selects one arm (or expert) out of finite set of K arms. In the stochastic setting, each arm admits some reward distribution and the learner receives a reward drawn from the distribution corresponding to the arm selected. In the bandit setting, the learner observes only that reward [Lai et al., 1985, Auer al., b0.2a,b], while in the full information selling, the rewards of all K arms are observed [Littlestone and Warmuth, 1994, Freund and Schapire, 1997].
Both settings are special instances a more general model online learning with side information introduced by Mannor and Shamir [2011], where the information supplied to the learner is specified by feedback graph. In an undirected feedback graph, each vertex represents an arm and an edge between between arm and indicates that the reward of is observed when is selected and vice-versa. The bandit setting corresponds to a graph reduced to self-loops at each vertex, the full information fully connected graph. The problem of online learning with stochastic rewards and feedback graphs has been studied by several publications in the last decade or so. The performance of algorithm in this problem is expressed in terms of its pseudo-regret, that is the difference between the expected reward achieved by always pulling the best arm and the expected cumulative reward obtained by the algorithm.
The UCB algorithm of Auer et al. [2002a] designed for the bandit setting forms a baseline for this scenario. For general feedback graphs, Caron al. [2012] designed UCB-type algorithm, UCB-N, as well as a closely related variant. The pseudo-regret guarantee of UCB-N is expressed terms of the most favorable clique covering of the graph, that is its partitioning into cliques. This guarantee is always at least as favorable as the bandit one [Auer et al., 2002a], which coincides with the specific choice of the trivial clique covering. However, the bound depends the ratio of the maximum and minimum mean reward gaps within each clique, which, in general, can be quite large.
Cohen et al. [2016] presented an action-climinatioon guarantee depends on the least favorable maximal independent set. While there are instances in which this guarantee is worse compared to the bound presented in Caron et al. [2012], in general it
algorithm [Even-Dar et al., 2006]. whose
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

could be much more favorable compared to the clique partition guarantee of Caron et al. [2012]. The algorithm of Cohen et al. [2016] does not require access to the full feedback graph, but only to the out-neighborhood of the arm selected at each round and the results also hold for time-varying graphs. Later, Lykouris et al. [2020] presented an improved analysis of the UCR-N algorithm based on a new layering technique, which showed that UCB-N benefits, in fact, from a more favorable guarantee based on the independence number of the graph, at the price of some logarithmic factors. Their analysis also implied similar guarantee for variant of arm-climination and Thompson sampling, as well as some improvement of the bound of Cohen et al. [2016] in the case of a fixed feedback -tppe algorithm [Even- -ar et al., 2006],
graph. Buccapatnam et al. [2014] gave an UCB-LP, that leverages the solution of a linear- programmogg (LP) problem. The guarantee presented depends only the domination number of the graph, which can be substantially smaller than the independence number. A follow-up publication [Buccapatnam et al., 2017a] presents an analysis for an extension of the scenario of online learning with stochastic feedback graphs.
We will show that the algorithms just discussed do not achieve asymptotically optimal pseudo-regret guarantees and that it is also unclear how tight their finite-time instance-dependen bounds are. Wu et al. [2015] and Li et al. [2020] proposed asymptotically optimal algorithms with matching lower bounds. However, the corresponding finite-time regret guarantees are far from optimal and include terms that can dominate the pseudo-regret for any reasonable time horizon.
We briefly discuss other work related to online learning with feedback graphs. When rewards are adversarial, there has been a vast amount of work studying different settings for the feedback graph such as the graph evolving throughout the game or the graph not being observable before the start of each round [Alon et al., 2013, 2015, 2017]. The setting in which only noisy feedhack is provided by the graph is addressed in Kocák et al. [2016]. First order regret bounds, that is bounds which depend on the reward of the best arm, are derived in Lykouris et al. [2018]. Lee et al. [2020]. The setting of sleeping experts is studied in Cortes et al. [2019]. Cortes et al. [2020] study stochastic rewards when the feedback graph evolves throughout the game, however, they do not assume that the rewards and the graph are statistically independent. Another instance in which the feedback and rewards are correlated is that of online learning with abstention [Cortes et al., 2018]. In this setting the player can choose to abstain from making a prediction. The more general problem of Reinforcement Learning with graph feedback has been studied by Dann et al. [2020]. For additional work on online learning with feedback graphs we recommend the survey of Valko [2016].
We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite time. We show that, surprisingly, the notion of optimal finite-time regret is not a uniquely defined property in this context and that, in general, it is decoupled from the asymptotic rate. Let T denote the time horizon and Reg,x (T) the pseudo-regret of algorithm A after T rounds. When A is clear from the context, we drop the subscript. It is known that c" the value of the LP considered by Buccapatnam et al. [2014], Wu et al. [2015], Li et al. [2020], is asymptotically a lower bound for Reg (T) log(T) We prove that no algorithm A can achieve a finite-tinn time pscudo-regret guarantee of the form Reg (T) S O(c"log(T)) Moreover, we show that there exists a feedback graph G for which any algorithm suffers a regret of at least 2 K& (c' +) where Amin is the minimum reward gap. We discuss alternative choices and propose a notion of finite-time optimality that we argue is meaningful, based on regret quantity d' that we show any algorithm must incur in the worst case. For that notion, we give an algorithm whose pseudo-regret is quasi-optimal, both in finite-time and asymptotically and can be upper bounded by O(c" log(T) + d.).
2 Learning scenario
We consider the problem of online learning with stochastic rewards and a fixed undirected feedback graph. As in the familiar Each arm i E [K] admits a reward distribution, with mean μ4: For all our lower bounds, we assume that the distribution of the reward of each arm is Gaussian with variance 1/V2.. For our upper bounds, we only assume that the distribution of each arm is Gaussian with variance proxy bounded by 1. We assume that the means are always bounded in [0, 1J. For arm i, we denote by A; μ=" pi; its mean gap to the best μ² = max;0 k] (4s- We will also denote by Aia the smallest and by Amax the largest of these gaps. At each round e [T], the learner selects an arm in and receives a reward Te drawn from the reward distribution of arm i, In addition to observing that reward, the learner
bandit problem, the learner can choose one of K 1 arms.

---

observes the reward of some other arms, specified by undirected graph G (V,E), where the vertex set V coincides with [K]: an edge e between vertices i and indicates that the learner observes the reward of arm j when selecting arm and vice-versa. We will denote by N; the set of neighbors of arm in G. N₂ = (j e V: (i. e F). and will assume self-loops at every vertex, that is, we have e N; for all i e V. The objective of the learner A is to minimize its pseudo-regret, that is the expected cumulative gap between the reward of an optimal arm and its reward:
T Σ (m reste)
T Σ r1A
Reg (T) = E
P E
where the expectation taken over the random draw reward from an arm's distribution and the possibly randomized selection strategy of the learner. In the following, we may sometimes abusively use the shorter term regret instead of pseudo-regret. We will denote by I' the set of optimal arms, that is, arms with mean reward μ², and, for any L [T') will denote by r, the vector of all rewards r2,s at time t. When discussing asymptotic or linite-time optimality, we assume the setting of Gaussian rewards.
We will assume an informed setting where the graph G is fixed and accessible to the learner before the start of the game. Our analysis makes use of the following standard graph theory notions [Goddard and Henning, 2013]. A subset of the vertices is independent if no two vertices in are adjacent. The independence number of G, a (G), is the size of the maximum independent set in G. A dominating sel of G is subset S S V such that every vertex not in is adjacent to S. The domination number of G, (G), is the minimum size of dominating set. It is known that for any graph G. we have (G) s GG). The difference between the domination and independence numbers can substantial in many cases. For example, for star graph with vertices, we have (G) 1 and (G))
1. In the following. in the absence of any ambiguity, we simply drop the graph arguments and write a or y. We will denote by D(G") the minimum dominating set of sub-graph G' c. G' and by I(G") the maximum independent set. When the minimum dominating set not unique, D(G') can be selected in an arbitrary but fixed way.
3 Sub-optimality of previous algorithms
In this section, we discuss in more detail the previous work most closely related to ours [Buccapatnam et al., 2014, Wu et al., 2015, Buccapatnam et al., 2017b, Li et al., 2020] and demonstrate their sub-optimality. A summary of our comparison can be found in Table 1. These algorithms all seek to achieve instance-dependent optimal regret bounds by solving and playing according to the following linear program (LP),, which is known to characterize the instance-dependent asymptotic regret for this problem when the rewards follow a Gaussian distribution:
(A.G) min (z. A) DERK
s.t.
Σ JeN;
ViE [K]
(LP1)
A
We note that these prior works' algorithms can work in more general settings, but will restrict our discussion to their use in the informed setting with a fixed feedback graph that we consider this study.
The UCB-LP algorithm of Buccapatnam et al. [2014, 2017b] is based on the following modification of LPI: minzeR& (Ir 1) subject to EjeN, zz 2 1, for all i [K]. in which the gap information eliminated, working with gaps such that Amin O(A max). ) This modified problem is the LP relaxation of the minimum dominating set integer program of graph G.
The algorithm first solves this minimum dominating set relaxation and then proceeds climination algorithm in (log(T)) phases. During the first (log(K)) rounds, their algorithm plays by exploring based on the solution of their LP. Once the exploration rounds have concluded, simply behaves as a bandit ciiiinnnlimiiaionnn algorithm. We argue below that this algorithm is sub-optimal, in at least two ways.
action-
Star graph with equal gaps. Consider the case where the feedback graph star graph (Fig- ure 1(a)): there is one root or revealing vertex adjacent to all other vertices. In our construction, the optimal arm chosen uniformly at random among the leaves of the graph. The rewards are chosen so that all sub-optimal arms admit the same expected reward with gap the best A O(1/K1+)) 0.
3

---

(a) Example 1.
(b) Example 2.
Figure Sub-optimality examples
Table 1: Summary of the regret bounds for Figure (b.)
Caron al. (UCB-N), Cohes (Action elimination),
Lykoorri (UCB-N,
5.2
Ruccapımam Buscaputnam
Thompson Sampling)
Regret bound Example (b.j:
beet2 Sasie
O(VKT)
x log(2)
o
(x)
O
(oad'") Besis
Inof Sheirs
Sai
Saste
In this case, an optimal strategy consists of playing the revealing arm for O(1/A²) rounds identify the optimal arm, and thus incurs regret most O ). On the other hand the UCB-LP strategy incurs regret at least S2( K Klg((T) Even if we ignore the dependence on the time horizon, the dependence on K' is clearly sub-optimal.
Sub-optimality of using the minimum dominating set relaxation. In the second problem instance, given Figure ((b), we consider a star-like graph in which we have a revealing vertex ri, adjacent to all other vertices. We also have an "almost" revealing vertex 72 which is adjacent to all vertices but single leaf vertex (leaves are the vertices with degree 1 and 2 in this case). The optimal arm is again chosen uniformly among the leaves. Rewards are set so that the gap at 71 is Amax and the remaining gaps are Amin- The solution to the I.P of Buccapatnam al. [2014, 2017b] puts all the weights However, the optimal policy for this problem consists of playing 72 and the leaf vertex not adjacent 72 until all arms but the optimal arm are eliminated. The instance optimal regret in this case is O log(T2 ) while UCB-LP incurs regret Ω log(2") Amin
Amin
Next, we discuss [Wu et al., 2015] and [Li et al., 2020J. Their instance-dependent algorithms are based iteratively solving empirical approximations to LP1. For simplicity, only discuss the instance-dependent regret bound in [Li et al., 2020]. A similar bound can be found [Wu et al., 2015]. Let 20 A) denote the solution of LP1 and define the following perturbed solution
(A,,)) (A'):
A, s Vi [K]]
The solution x(A,c) is the solution of LP1 with 6-perturbed gaps. [Li et al., 2020][Theo- rem 4] states that the expected regret of their algorithm bounded as follows: Reg(T)
of Exe(y logT)): ΣL exp(- ((-(())))) e==(xx=-_(k=)) K for any e and (()) = o(I). For
standard bandit problem with Gaussian rewards, we can compute the perturbed solution: x; (A,c) = max (A:+c)= (A,-<)) Thus, for meaningful regret bound, would need O(A If is
much smaller, then the term ΣT_ exp(- ((1)e becomes too large and otherwise we risk making -
x, (A,e) too large. To analyze the second term more carefully, we allow B(t) The first min
terms
of E exp( A(t)ee) are now least and thus this sum at least Σt exp( 3(t)e" KK
K
c
miin
log(T) Thus, the bandit regret bound evaluates at least 52( [ie[K]] A:
K
While this bound is
A
min
asymptotically optimal, since the second term does not have dependence on T, it admits very poor dependence on the smallest gap. We can repeat the argument above with star-graph construction in which the revealing vertex has gap Amin- In this case, the optimal strategy given by the solution to
LPI consists of playing the revealing vertex for A times and incurs regret at most O log(T) The
Amin
regret bound of the algorithm Li et al. [2020], however, amounts to ? log(T)
Amin
A

---

4 Instance-dependent lintee-tmee bounds
In this section, we provide an in-depth discussion of what finite-time optimality actually means. Finite-time bounds are statements of the form (eg(T) S f(T). which hold for any T > O. Specifically, we are considering functions of the type I(T) e² log(T)) + d, which we know to exist from prior work. The question of what the optimal expression of might be seems easy to answer at first. Indeed, for bandits with Gaussian rewards, one can achieve O A,), which in general is much smaller than cº (E;;; 3,) [Lattimore and Szepesvári, 2020], and hence will be dominated by the time-dependent part of the regret for almost all reasonable lengths of the time horizon T. In full information, we obtain a meaningful optimal value d' for a given gap vector by considering the worst-case regret of any algorithm under any permutation of the arms. This leads to d' O In( Amin
[Mourtada and Gaïffas, 2019]. Note that in the full information setting we have = 0.
One might hope for a similar structure for feedback graphs, where the optimal d depends only on the inulmmiformntion structure", that is the gaps of arms neighboring an optimal arm. All other arms contribute to c* and we might assume that their complexity is already captured in the c* log(T) (T) term as it is the case for bandits. However, the situation is more complicated, as we show next.
Theorem 4.1. For any K 32 and Amin ((+R)) there exists graph G with K vertices, such that for any algorithm there exists an instance with unique best arm and minimal gap Amia for which for any T 52( Ka/4 the regret is at least Reg(T) = 5 (0(K3 (c* Amin
Theorem 4.1 shows that there exists a problem instance, in which >> c² dominates the finite time regret for any T O(exp(('))))) k))))). We note that this is not simply due to the full-information structure of the feedback graph G, c is positive. Furthermore, combined with examples shown in Section 7, Theorem 4.1 suggests that there is no simple characterization of d independent of the graph in terms of c², e.g., d = Occ* (Ac"/Amin). While d = θ ((K1/*()) holds for the example instance in Theorem 4.1, there exists a non trivial family of graphs, for which for any rewards instance, we have d= Oc*)), ) so the shape and relevance of d is highly graph depeddee....nt.
Having established that d could be the dominating term in the regret for any reasonable time horizon, we now discuss the hardness of defining an optimal d. Let us first consider a simple two-arm full- information problem and inspect algorithms of the style: "Play arm 1, unless the cumulative reward of arm 2 exceeds that of arm by a threshold of r." This kind of algorithm has small regret (small d) if arm 1 is optimal, and large otherwise. Tuning 7 yields different trade-off's between the two scenarios. The same issue appears in learning with graph feedback on a larger scale. Given two instances defined by gap vectors A and A respectively, an agent can trade off the constant regret part d()) and d( A') in the two instances. Take for example two algorithms A and B and assume the respective values of c' and d for the two instances and algorithms are given by Table 2. As show in Appendix A, there exist a feedback graph and instances that are consistent with the table. Which algorithm is more "optimal", A or BB? B ensures that max
d(6) O(1) and we can
d for Alg. A
d for Alg. B
Instance A Instance A
C/3
C/3
4C/9
4Cs
C/2
4Ca
Table 2: Comparison of e* and d.
write the regret function as S(T) Oce log(T)) without the need of a constant term d at all. This algorithm minimizes the competitive ratio of d and c* A minimizes the worst-case absolute regret A ae(..) max d(ō,a).
Thus, we argue that the notion of optimality is subject to a choice and that there is no unique correct answer. In this paper, we opt for the worst-case absolute regret, minimized by A in the above example, for the following reasons: Theorem 4. shows that a constant competitive ratio is generally unachievable; 2. Optimizing regret in general is different objective than that of competitive
When the problem parameters are clear from the context, we will write e instead of e' (A, G). S(T) c² would be ideal, we settle for optimality While obtaining exact asymptotic optimality limy- log(T)
up multiplicative constant in our upper bounds.
5

---

ratio. Optimizing for mixture implies a counter- intuutr-it preference such as: "In a hard environment where cannot avoid suffering a loss of 1000, it does not matter much if I suffer an additional 1000 on top, as long as I do better easier environments." 3. Moreover, note that, even if one were interested in optimizing the competitive ratio between c* and d, it is unclear if one could achieve that objective computationally efficiently.
We present our final definition for an optimal notion of d' in Section The high level idea is to take all confusing instances, where the means are perturbed by less than A and consider the worst-case regret any algorithm suffers over these instances until identifying all gaps up to As precision.
5 Algorithm and regret upper bounds
Our algorithm works by approximating the gaps (A)) and then solving a version of LP1. First, note that all arms with gaps A, T can be ignored as the total contribution to the regret is at most O(). We now segment the interval [ [ 1], containing each relevant gap, into sub-intervals 3T*,2-e+1, where s (T) The algorithm now proceeds in phases corresponding to each of the [log2 (T)] intervals. During phase s, all arms with gaps A, [2 2- will be observed sufficiently many times be identified as sub-optimal.
For phase 8, let A, = 2 denote the smallest possible gap that can be part of the interval [2 2-1=+11 and define the clipped gap vector A e R A A A, A, Further, define the set , = {i [K]: A; s 2 I, consists of all optimal arms and all sub-optimal arms with gaps small enough, making them impossible to distinguish from optimal arms. Define the following LP
min ( xeR[k]
s.l. Σ JEN,
xz
VieT..
(LP2)
A?
For any arm i such that A, e [2-* 2- observing i for 1 times is sufficient to identify i as A3 sub-optimal arm. Further, information theory dictates that i needs to be observed at least x times to be distinguished as sub-optimal. Thus, the constraints of LP2 are necessary and sufficient for identifying the sub-optimal arms with A; [2 2 2-s+1J, Furthermore, since there is no sufficient information to distinguish between any two arms and j with gaps A, s A < As, we choose to treat all of them as equal in the objective of the LP. Indeed, Lemma 6.1 shows that for any graph G and any algorithm, there exists an assignment of the gaps A, < A, so that the algorithm will suffer regret proportional to the value of LP2.
In practice, it is impossible to devise an algorithm that solves and plays according to LP2 because even during phase 8, there is still no complete knowledge of the gaps A, A,, but, rather only empirical estimators, and so there is no access to A We also replace the constraints by confidence interval term of the order 1og()/6.) This enables us to bound the probability of failure for the algorithm by 6, A;
during phase s. We note that standard choices of 8, such as 5, e (+)) from UCB-type strategies will result in regret bound that has sub-optimal time-horizon dependence. This suggests that more careful choice of d, must be determined.
5.1 Algorithm
To describe our algorithm, we will adopt the following definitions and notation. Let T. denote the last time-step of phase 8. We will denote by (s) the total number of times the reward of arm i is observed up to and including 8, n²(s) ΣL, I(i N.), and by re(s) the average reward observed, fs()) = [ΣA, Te, I(ii e N.)]/n,(s)) (s). We also denote by (s))) lower bound on with a shrinking confidence interval bs(s) and by I's the empirical version of the set I.:
3a log( A, ni(ss)
K
(,(+) A. v max (s) - b,(s) (x))) - b,(s), where (x)))= ]][
f, fie [K]] ( 24,)

---

Algorithm 1: Algorithm based on LP3
Input: Graph G (V, confidence parameter 8, time horizon T
Initialize & = 0, 8 0, (:))) = 0, Vi [K]
Compute (approximate) minimum dominating set D(G)
while s [ do
a' log( rounds
Play each arm i D(G) for
Update t and s.
while t 2 T do
Compute (approximate) solution =ip3 LP3.
Play each action i for (#irs)) rounds and update
Update the phase
Our algorithm solves empirical version of (LP2) at each phase, which is the following LP:
a' log(
min (I. (I, 1)) WER
s.t.
Σ
2
A.-l
Vie T..
A
JeN;
(LP3)
a'
Σ JEN,
Ø 2
VięT..
{7(s-1)
Pscudocode can be found in Algorithm 1. In the first [log( rounds, the algorithm just plays according to the minimum dominating set of G. This because there is not enough information regarding any of the gaps. Denote the approximate solution of LP3 as LiP3 at phase Then every round of phase s we play each arm exactly [<=ips))] many times. Phase then ends after Ej[[k] (xL))); rounds. We note that it is sufficient to approximately solve LP3 that the constraints are satisfied up to some multiplicative factor and the value of the solution bounded by multiplicative factor in the value of the LP.
5.2 Regret bound
The first step the regret analysis of Algorithm is relate the value of LP3 the value of LP4 based on the true gaps given below.
a' log(
K
min (x. A*) xcR
s.t. Σ JeN:
Iz 2
A
VieT.
A?
(LP4)
Σ
2
r
A
JeN,
We do so by showing that F.+1 T, and that ((s) e A+). This allows upper upper bound the value of LP3 by the value of LP4 in the following way.
Lemma 5.1. Let (Lpa(s) be the value of LP3 at phase s and let DIPs($) be the value of LP4 at phase: For any 2 log( K) 10 holds that DLPs(s + 1) S 4DLra(s), with probability at least 1 1-3( A.p++ 2-2 K
Further, for any 2 log([I"1(44Annn)) 1/(4mii)) ) 10 it holds that the regret incurred for playing according to LP3 is at most 16a' c* (G.H) with the same probability.
Lemma 5.1 shows that playing Algorithm is already asymptotically optimal, as the incurred regret during any phase log([1*// Aimn) starts being bounded by O(e*). There are two challenging parts in proving Lemma 5.1. First is how handle the concentration of Âε(s) for actions i & Π. which have been eliminated prior to phase s. This challenge arises because a' needs to be set a time-independent parameter as the time-horizon part of the regret incurred by the algorithm will depend on a'. We notice that for any phase 2 2 the event that the empirical reward, ft(t), concentrates uniformly around its mean μ4 in the interval [s/2, s] be controlled with high probability. This turn guarantees that the empirical gap estimator (1) is small enough and hence action is observed sufficiently many times in phases [s/2,s].
7

---

The second challenge is to analyze the regret of the solution of LP3 directly, for any s log [
so that we can bound this regret by c². The key observation is that there exists a 8" which is feasible (with high probability) for LP1 with the property that ( A())) & O(c²)) and further Eier Fi. (s) & 2 2 & (s). This is sufficient to conclude that DLPS($) & O(e*)
Lemma 5.1 can now be combined with the observation that the constraints of LP2 are subset of the constraints of LP4, up to a logarithmic factor in Aman to argue the following upper regret bound.
Theorem 5.2. Let d' (G, maxxglog((11 /Ami DLP2(S). There exists an algorithm with expected regret (T)(() bounded as
Reg(T) (T) s O log" A
d' log(T)cc + +G) (og)K)))()) )
We note that Algorithm can incur additional regret of order O(K) per phase due the rounding, [xirs] 1. of the solution to LP3. Thus its regret will only be asymptotically optimal in the setting when 4 min & O1)K)) To fix this minor issue, we present an algorithm with more careful rounding in Appendix B.I, which enjoys the regret bound of Theorem 5.2.
Regret lower bounds
Lower bound with d= We are able to show the following result for any algorithm.
Lemma 6.1. Fix any instance μ s.t. #4 S 1-1120 2 I" Let A.(1) be the set of problem instances with means pl E p [0, 21 Then for any algorithm, there exists an instance in (a(u) such that the regret is lower bounded by LP2.
Motivated by Lemma 6,1, the quantity d' (G, (u) is a meaningful definition of finite-time optimality. We note that d' is indeed independent of the time-horizon and only depends the topology of G and the instance The result in Lemma 6.1 is a companion to the upper bound in Theorem 5.2. It shows that for any instance μ and number of observations which are not sufficient to distinguish the arms with smallest positive gaps as sub-optimal, any algorithm will necessarily incur large regret of order d² This happens because the algorithm will not be able distinguish J from some environment μ which is identical to μ except for the reward of a single arm which is only slightly perturbed.
The definition of d' as maximum over different values of might seem surprising. one could expect that the value of LP2 strictly increases when grows, after all this is precisely what happens in the bandit setting. This is not the case for general graphs, where the value can also decrease between phases s and s + 1. Intuitively this happens when the approximate minimum weighted dominating set chosen by the LP's solution increases between phases.
The result in Lemma 6. has a min-max flavor in the sense that all possible instances which are close to y are considered. It is reasonable to ask if d' can be further bounded by favorable instance- dependent quantity. The answer to this question is complicated and certainly depends on the topology of the feedback graph we show next.
Sketch of proof of Theorem 4.1. We now show that any finite time term d has to exceed e* by at least multiplicative polynomial factor in the number of actions K. To do so we exhibit a specific feedback graph G, found in Figure 2, on which any algorithm will have incur regret least Q K e*) for some μ s.t. c² 2 A
A
A
Aa
Formally the graph is defined to have vertex set V = = U.G of 2K arms, with each of M 's disjoint and M₁ = (2i lsisk, N2 {2i 1 : 0 s i K), .gg = {0). The set of edges is defined as follows. Every vertex in N1 is adjacent to the vertex in N/3 and the 2i vertex is adjacent to both 2i + 1 and 2i - in N2 modulo 2K + 1. Finally vertex 2i 1 in 22 is further adjacent to to the next [K2/$| vertices in 22 modulo 2K + 1. The base instance, E, is defined by a scalar u E [0,1] and gap parameter A so that the expected reward of every action in Mr is equal to A, the expected reward of every action in N₂ is equal to K K1/1 A and the expected reward of the action in Ng.
Aa
d2
A
A
A
Figure 2: Reinforced wheel.
8

---

We note that e is well-defined the relation is an equiv- alence relation. The equivalence classes defined by are cliques with the following property. For any in equiv- alence class [v] it holds that u E [v], Vu N,, that is the vertices in the equivalence class clique only have neighbors is / VKA. We assume that all rewards follow a Gaussian with variance 1 We denote by
A 22 K =
The lower bound now fixes an algorithm and considers two cases. First, A could commit to often playing arms in .M. In this case we show that there could be a large gap to the arms in M1 which would not be detectable by A as arms in N2 are not observed often enough. This is indeed the case as A needs to play ((K) actions in Ni to cover N2. This first case corresponds to assuming that the number of arms played from N2 is at most O OKK* /AA) in the first O(K rounds. The second case considers the scenario in which actions in N2 are played for more than 52 K & /A) times the first O O(K/A] /A) rounds. In this case, A would suffer large regret if the gap at actions in Ni is small enough, so that the optimal strategy is to cover N₂ by playing arms in N₁
More formally, we begin by showing that there always exists an arm n² é NN₂ which is observed for only 0(1/A3) times. Next, we change the expected reward of n depending on which of the above two cases occur. In the first case we change the environment by setting the reward of n* to have expectation
A2. We can now argue that the regret of A will be at least 9 ((K//A) as n" will not be played often enough in the new environment. The value of c", however, is at most O(K* / = O(K $
/)), as playing each action in a minimum dominating set over N22 for 1 A3 rounds is feasible for LP1. For the second case, we set the expected reward of n² equal v. The optimal strategy now has regret at most O( ////)) by playing the action in N/ for A and every action in N₁ for 1 xZ rounds. On the other hand A will incur at least S2 K //)/ as again n² is not played often enough. This argument implies the result presented Theorem 4.1.
7 Characterizing the value of d*
Theorem 4.1 suggests that we take into account the topology of G explicitly when trying to bound d', independently of the instance Jr. In this section, first show bound on d' that depends only on independent sets of G. Then, we show a set of graphs G for which d' s O(e)) on any instance μz.
Let us recall the regret bounds presented in [Lykouris et al., 2020]. Denote by I(G) the set of all independent sets for the graph G. Then the regret bounds presented in [Lykouris et al., 2020] are of the order Reg(T) S &0( (maxxes(G) Eiel log" (1) ). Is possible to show, that d' (G, maX)=3(G) Eier A, Thus, what is known for the algorithms studied in [Cohen et al., 2016, Lykouris al., 2020]. The above bound, however, could be very loose as was discussed in the beginning of the paper, especially when considering sarrgraphss, as the bound would just reduce to the bandit case. It turns out, however, that [!'l for a
do in Appendix D.1, algorithm enjoys regret bounds which are better than
A:
d' s (((c) in this case. In fact we can state a sufficient condition on G so that d' sc" + "Amin more general family of graphs. We begin by defining the following operation on G.
Definition 7.1. Let ~ be the equivalence class defined by iff Nu No and let e be the mapping which sends G to the quotient /_. through the operation of collapsing any sub -raph of G into its equivalence class.
in the clique to which they belong. An example can be found in Figure 3, where the graph contains four cliques adjacent to the vertex r. In general, the vertex r can also be clique as well and the graph can have multiple dis- joint components of the type presented in the figure. For any instance y of the problem, this allows us to collapse each equivalence class [v] to vertex v with the maximum expected reward in [w]. The next lemma states sufficient condition on G under which d' bounded.
Figure 3: Generalized star-gras star-graph.
Lemma 7.2. If the graph G is such that e(G) has no path of length greater than two between any two vertices, then, for any instance μ. the following inequality holds: e² 11_ d'
Amin

---

Conclusion
We presented a detailed study of the problem of stochastic online learning with feedback graphs in finite time setting. We pointed out the surprising issue defining optimal finite-time regret for this problem. We gave instance which algorithm c", which characterizes asymptotic optimality. Next, we derived an asymptotically optimal algorithm that is also min-max optimal in finite-time sense and admits more favorable regret guarantees than those given in prior work. Finally, we described a family of feedback graphs for which matching the asymptotically optimal rate possible in finite time.
hope match, in finite time, the quantity
There are several interesting questions that follow from this work. First, while the condition on e(G) in Lemma 7.2 is sufficient, it is not necessary. For example, star-like graph in which two leaf vertices are also neighbors will have the property that d" s O((c') for any instance μ. We ask what would be necessary and sufficient condition on G' for which d' O on any instance uu? Another interesting question is how to address the setting evolving feedback graphs. is unclear what conditions the graph sequence would allow existing independence number results. Further, can we use our approach to show improved results for the setting of dependent rewards and feedback graphs studied in [Cortes al., 2020]? Finally, methodology crucially relies on the informed setting assumption. We ask if it is possible to achieve similar bounds Theorem 5.2 in the uninformed setting.
recover bounds that improve the
10

---

References
Noga Alon, Nicolo Cesa- Bianchi, Claudio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. arXiv preprint arXiv: 2013.
Noga Alon, Nicolo graphs: Beyond bandits. In Conference on Learning Theory, pages 23-35. PMLR, 2015.
Ofer Dekel, and Tomer Koren. Online learning with feedback
Noga Alon, Nicolo Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal Computing, 1666))1785-1826, 2017.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77, 2002b.
Swapna Buccapatnam, Atilla Eryilmaz, and Ness B Shroff. Stochastic bandits with side observations on networks. The 2014 ACM international conference on Measurement and modeling of computer systems, pages 289-300, 2014.
Swapna Buccapatnam, Fang Liu, Atilla Eryilmaz, and Ness B. Shroff. Reward maximization under uncertainty: Leveraging iide-observations on networks. J. Mach. Learn. Res., 18:216:1-21:334 2017a.
Swapna Buccapatnam, Fang Liu, Atilla Eryilmaz, and Ness B Shroff. Reward maximization under uncertainty: Leveraging side-observations on networks. arXiv preprint arXiv:1704.079441 2017b.
Stéphane Caron, Branislav Kveton, Marc Lelarge, and Smriti Bhagat. Leveraging side observations 2012.
in stochastic bandits. arXiv preprint arXiv:/210.444
Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feedback graphs without the graphs. In International Conference on Machine Learning, pages 1-189. PMLR, 2016.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. In international conference on machine learning, pages 1059-1067. PMLR, 2018.
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. PMLR, 2019.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Online learning with dependent stochastic feedback graphs. In International Conference Machine Learning, pages 2154-2163. PMLR, 2020.
Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sckhari, and Karthik Sridharan. Reinforce- ment learning with feedback graphs. Advances in Neural Information Processing Systems, 33: 16868-16878, 2020.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res., 7:1079-1105. 2006.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Wayne Goddard and Michael A. Henning. Independent domination in graphs: survey and recent results. Discret. Math., 313(7):839 854, 2013.
Tomáš Kocák, Gergely Neu, and Michal Valko. Online learning with noisy side observations. In Artificial Intelligence and Statistics, pages 1186-1194, PMLR, 2016.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.

---

Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, pages 2516-2564. PMLR, 2020.
Shuai Li, Wei Chen, Zheng Wen, and Kwong-San Saag-Sak Leung. Stochastic online learning with probabilistic graph feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, 2020.
pages
Nick Littlestoone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-261, 1994.
Thodoris Lykouris, Karthik Sridharan, and Êva Tardos. Small-loss bounds for online learning with partial information. In Conference Learning Theory, pages 979-986. PMLR, 2018.
Thodoris Lykouris, fiva Tardos, and Drishti Wali, Feedback graph regret bounds for Thompson sampling and UCB. Algorithmic Learning Theory, pages 592-614, PMLR, 2020.
Shie Mannor and Ohad Shamir. From bandits experts: the value of side-observations. Advances in Neural Information Processing Systems, 24:684-692 2011.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
Michal Valko. Bandits graphs and structures. PhD thesis, École normale supérieure de Cachan- ENS Cachan, 2016.
Yifan Wu, András György, and Csaba Szepesvári. Online learning with gaussian payoffs and side observations. arXiv preprint arXiv:/510.08:/08, 2015.
Shengjia Zhao, Enze Zhou, Ashish Sabharwal, and Stefano Ermon. Adaptive concentration inequali- ties for sequential decision problems. Advances in Neural Information Processing Systems, 29, 2016.
12

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Both upper and lower bounds are
discussed in the respective sections. We further have a broad discussion about the type of bounds we choose to pursue in Section and Appenidx A.
(c) Did you discuss any potential negative socictal impacts of your work? [N/A] This work theoretical and it is hard judge societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please refer to the results in the stated theorems.
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to the appendix for complete proofs of the main results.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A] There is no code available for this work.
(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 the random seed after running experi- ments multiple times)? [N/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 using existing assets (e-g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, 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 a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing 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 participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wgs1oQ9GyFI", "reviewer": "Reviewer_zGSQ", "summary": "This paper investigates the optimality in the problem of stochastic online learning with feedback graphs.\nThe authors showed that in the problem setting, the vanilla asymptotic optimality and finite-time guarantee cannot be achieved simultaneously.\nThe authors provide a novel notion of finite-time complexity and propose an algorithm with which the quasi-optimal regret bound can be obtained both asymptotically and in finite time.", "questions": "To obtain similar results, can we remove the assumptions of undirectedness of the feedback graph and self-loops at every vertex?", "limitations": "NA", "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- The paper discovered the surprising fact that the vanilla asymptotic optimality and finite-time guarantee cannot be achieved simultaneously, and a good amount of explanation is provided to explain the intuition behind it.\n- The paper is well written, and easy to follow the arguments.\n\n \nWeaknesses: \n- The assumption introduced in this paper might be a bit strong, while a sufficient amount of interesting contribution is provided. For example, if we assume self-loops on the feedback graphs, stochastic online learning with feedback graphs is intrinsically easier than the multi-armed bandits. A more detailed comparison of assumptions against existing work might be desired.\n\n(minor)\nThere are typos:\nline 146, 148: $\\Delta_{min}$ should be $\\Delta_{\\min}$ and same for $\\Delta_{max}$.\nline 162: 1/e should be multiplied?", "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": "nuZMGCRbrqv", "reviewer": "Reviewer_Ur6a", "summary": "The paper considers the problem of stochastic online learning with feedback graphs. This is essentially the classic stochastic multi-armed bandit problem but with a more intricate feedback model that allows for additional side information. Specifically, given a graph whose vertices represent the arms, querying an arm reveals a sample of its reward as well as that of all of its neighbors in the graph. This setting has already seen significant research and the author's contributions are:\n1. Showing that several existing algorithms do not achieve the asymptotic lower bound or have a significant finite time overhead\n2. Showing a graph G for which any algorithm performs much worse than the asymptotic rate\n3. Showing a new quantity $d^*$ that lower bounds the performance of any algorithm\n4. An algorithm with quasi-optimal regret with respect to the quantity $d^*$ and the asymptotic rate.", "questions": "See in the strengths and weaknesses section.", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper considers the issue of finite time guarantees of MAB under graph feedback. The main claims are interesting and point out shortcomings in the existing literature. There are also novel ideas both in the algorithm and the lower bounds. Overall the paper is well-written and has solid contributions.\n\nI do have some comments/concerns:\n1. On the face of it, Theorem 4.1 seems to contradict previous upper bounds. It's supposed to show that finite time performance may be much worse than that of the asymptotic regime. However, there doesn't seem to be a problem applying the result asymptotically to conclude that $c^*$ is not the asymptotic bound but at least $K^{1/8} c^*$. The results cited by the authors achieve the asymptotic rate (maybe under some assumptions?) and so some thing doesn't add up. Can you explain this? This should probably be explained in the paper.\n2. Also regarding Theorem 4.1, Why is the conclusion that the finite time regime is $T \\le O(\\exp(K^{1/8}))$? The $K^{1/8}$ multiplies both terms in the regret.\n3. While there is an extensive comparison to previous works, it is somewhat hard to grasp the larger picture. It seems that previous methods and lower bounds have some advantages and some disadvantages but I found it hard to fully compare. Can you summarize all of these in a table or something similar?\n4. The paper ends by showing some cases where $d^*$ is relatively small and thus the asymptotic rate is relevant even in finite time. However, I did not find any concrete examples where the opposite occurs, i.e., $d^*$ is dominant up to a relatively large horizon. Perhaps Theorem 4.1 is meant to accomplish this? If so, it is not written in terms of $d^*$. Can you give more concrete examples?\n\n\n**Typos:**\n* line 23: different => difference\n* line 116: \"work the\" delete \"the\"\n* line 121: work => works'\n* line 201: delete \"the\" and \"indeed\"\n* line 210: preferences => preference\n* line 358: equivalent => equivalence", "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": "0M3qGUpWG1P", "reviewer": "Reviewer_WHxr", "summary": "This paper considers a general bandit-type learning problem. Arms are represented by nodes. When an arm is played, the feedback is shown for every arm corresponding the vertices adjacent to the vertex that corresponds to the pulled arm. Thus this is more general than full-feedback models as well as bandit models (corresponding to the complete and empty graphs respectively). The authors consider asymptotic regret bounds of the form $c\\log T+d$ and show that for any particular \\textit{finite time}, the bounds are not very meaningful in some cases. The authors propose a new quantity $d^*$ to design algorithms based upon. This quantity is related to the regret incurred by an algorithm when run on an instance when the means are all within $\\Delta$ of each other. A new algorithm is provided whose regret is roughly of the form $c^*\\log T + d^*$, and this $d^*$ is shown to be meaningful via a lower bound. To underscore the point, various other approaches are critiqued.", "questions": "I think the sufficient condition for Lemma 7.2 is not very clear, perhaps some examples of graphs would be helpful.\n\nCan the second set of constraints in LP3 and LP4 be discussed? They are not present in LP2, and I guess they are useful to control the estimates of arms that have been eliminated?\n\nIn page 5: \"In this paper, we opt for the second choice...\", is a little confusing, since one would think Algorithm B is the second one.\n\nCan it be confirmed that this is the idea: \"Different algorithms lead to different parameters $c^*$ and $d$ depending on the instance (for instance, as shown in Table 1). asymptotically, only $c^*$ matters, but for finite time, $d$ matters as well. This paper presents a $d^*$ that is achievable by Alg 1, which only depends on the topology of the graph, and which is necessary for graphs of that topology.\" In this sense, this is an instance dependent min-max bound, where the \"instance\" is not the complete instance, but just the topology.", "limitations": "I am not sure I understand the paragraph starting at line 206. it establishes that this is just one notion of optimality, perhaps it might be reasonable to try and minimize the competitive ratio between $c^*$ and $d$. I do understand that this is not the direction taken by the paper, and I think the contribution is nice anyway.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: the proof sketches are very helpful. The problem considered is nice; I think in the bandit literature it isn't really discussed and not as important. The comparisons with the other LPs are insightful.\n\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": "-ePGS33sz4X", "reviewer": "Reviewer_D2tm", "summary": "The paper considers the important  problem of stochastic bandits on a graph: Given a known graph (V,E), there are unknown reward distributions with each vertex. At each stage, the learner can choose a vertex. Random rewards are then sampled. The learner accumulates the reward associated with their chosen arm (vertex), but also observes the reward of all vertices with an adjoining edge. \n\nThe primary focus of the present paper is on gap-dependent bounds which hold in finite-time, but are also asymptotically optimal.\n\nAfter introducing the problem, the paper turns to addressing concerns regarding existing methods and associated regret bounds. In particular, it is shown that the UCB-LP based approach of Buccapatnam et al. can yield regret which is not asymptotically optimal for certain graphs, such as star graphs, where the method doesn’t optimally take advantage of the structure. Also considered are the more refined approaches of Li et al. 2020 which is asymptotically optimal, but has quite severe dependence on the minimal gap.\n\nThe central result of the next section is Theorem 4.1, which gives an instance dependent lower bound. There is also some discussion of the complexities surrounding optimal bounds in the bandit case compared with the other two extremes of regular bandit and full information.\n\nSection 5 turns to positive results and presents a new algorithm. The algorithm is, broadly speaking, a careful refinement of the UCB-LP methodology. In addition, a regret bound is presented in Theorem 5.2 for the algorithm. The regret bound is asymptotically optimal and has a less severe dependence upon the minimal gap than Li et al.’s bound.\n\nThe regret bound in Theorem 5.2 contains a new quantity “d*”. Section 6 includes a lower bound which shows that this dependence is in some sense necessary. Section 7 continues the comparison with other methods and shows that the quantity d* is always exceeded by key terms in the regret bound of Lykouris 2020, and can be strictly smaller. Section 6 also includes a sketch of the proof of Theorem 4.1.\n", "questions": "Is it possible to say under what regimes the bound in Theorem 5.2 is minimax optimal up to logarithmic factors in the “gap-free” case?\n\nCan you explain the ordering of the quantifiers in Theorem 4.1? It seems as if the regret lower bound is claimed to hold for a single bandit problem, for all sufficiently large times T. This seems to contradict Theorem 5.2 when K\\geq C^8 where C here denotes the constant subsumed in big O notation in Theorem 5.2. \n", "limitations": "The primary limitations are discussed above in the “strengths and weaknesses” section.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem of bandits with feedback graphs is of great interest to the Machine Learning community. Moreover, the task of achieving bounds which are asymptotically optimal and have provably strong finite time performance seems of key importance.\n\nA key strength of the paper is the new methodology and associated regret bound in Theorem 5.2. The regret bound is (1) asymptotically optimal and (2) seems to outperform that of Li et al. in the low gap regime.\n\nThat said, its important to note that the theory in the present paper appears to leave an incomplete picture. It’s not clear if the bounds are both asymptotically and minimax optimal up to polylog factors in the “gap-free” case.\n\nThere also seems to be an issue with Theorem 4.1. It seems as if the regret lower bound is claimed to hold for a single bandit problem, for all sufficiently large times T. This seems to contradict Theorem 5.2 when K\\geq r^8 where r here denotes the ratio of the constants subsumed in big O notation in Theorem 5.2, divided by the constant subsumed in the Omega notation of Theorem 4.1.\n\nThe discussion in Section 4 also seems to be unnecessarily confusing. Ultimately, specifying optimality requires a combination of algorithm independent lower bounds and as well as upper bounds. The former always necessitates specifying an appropriate class of problem instances. This seems true in general, and for bandits on graphs in particular. Perhaps the point being made here is more subtle, but it remained somewhat elusive to me.\n\nOverall the structure of the paper is strange. The discussion of related work appears in several places in a somewhat confusing fashion. The proof sketch of Theorem 4.1 appears in Section 6 rather than 4. Section 5 should be probably be moved towards the front of the paper. The two lower bounds could be placed together in a common section. \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": {}}]

Author rebuttal:

Decision: Accept