On the Minimax Regret for Online Learning with Feedback Graphs
Authors: Khaled Eldowa
Emmanuel Esposito
Tommaso Cesari
Nicolò Cesa-Bianchi
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Online learning
Feedback graphs
Multiarmed bandits
TL;DR: We improve on the upper and lower bounds for the regret of online learning with undirected feedback graphs

Abstract: In this work, we improve on the upper and lower bounds for the regret of online learning with strongly observable undirected feedback graphs. The best known upper bound for this problem is $\mathcal{O}\bigl(\sqrt{\alpha T\ln K}\bigr)$, where $K$ is the number of actions, $\alpha$ is the independence number of the graph, and $T$ is the time horizon. The $\sqrt{\ln K}$ factor is known to be necessary when $\alpha = 1$ (the experts case). On the other hand, when $\alpha = K$ (the bandits case), the minimax rate is known to be $\Theta\bigl(\sqrt{KT}\bigr)$, and a lower bound $\Omega\bigl(\sqrt{\alpha T}\bigr)$ is known to hold for any $\alpha$. Our improved upper bound $\mathcal{O}\bigl(\sqrt{\alpha T(1+\ln(K/\alpha))}\bigr)$ holds for any $\alpha$ and matches the lower bounds for bandits and experts, while interpolating intermediate cases. To prove this result, we use FTRL with $q$-Tsallis entropy for a carefully chosen value of $q \in [1/2, 1)$ that varies with $\alpha$. The analysis of this algorithm requires a new bound on the variance term in the regret. We also show how to extend our techniques to time-varying graphs, without requiring prior knowledge of their independence numbers. Our upper bound is complemented by an improved $\Omega\bigl(\sqrt{\alpha T(\ln K)/(\ln\alpha)}\bigr)$ lower bound for all $\alpha > 1$, whose analysis relies on a novel reduction to multitask learning. This shows that a logarithmic factor is necessary as soon as $\alpha < K$.

On the Minimax Regret for Online Learning with Feedback Graphs
Khaled Eldowa"
Emmanuel Esposito"
Università degli Studi di Milano, Milan, Italy khaled. eldowa@umimi.
Università degli Studi di Milano, Milan, Italy & Istituto Italiano di Tecnologia, Genoa, Italy emmanue Gemmanuelespositoo itt
Tommaso Cesari
Nicolò Cesa-Bianchi
University of Ottawa, Ottawa, Canada tcesari Quattaaa.taaacaa
Università degli Studi di Milano, Milan, Italy & Politecnico di Milano, Milan, Italy ni nicolo. cesa- massa-banne bianchi meniiiiuimmmi. it
Abstract
In this work, we improve on the upper and lower bounds for the regret online learning with strongly observable undirected feedback graphs. The best known upper bound for this problem is O D(VaT In K). where K is the number of actions, a is the independence number of the graph, and is the time horizon. The VIn factor is known to be necessary when hand, when K (the bandits case), the minimax rate is known to be O /K)). and lower bound ((vaT) is known to hold for any a. Our improved upper bound ((VaT + In(K/a)) holds for any and matches the lower bounds for bandits and experts, while interpolating intermediate cases. To prove this result, use FTRL with q-Tsallis entropy for carefully chosen value of E [1/2, 1) that varies with a. The analysis of this algorithm requires a new bound on the variance term in the regret. We also show how to extend our techniques to time- varying graphs, without requiring prior knowledge their independence numbers. Our upper bound is complemented by an improved 2 / //n K)/ (/(((n (I) lower bound for all 1, whose analysis relies novel reduction to multitask learning. This shows that a logarithmic factor is necessary as soon as < K.
1 (the experts case). On the other
Introduction
Feedback graphs [29] provide an elegant interpolation between two popular online learning models: multiarmed bandits and prediction with expert advice. When learning with an undirected feedback graph G over K actions, the online algorithm observes not only the loss of the action chosen in each round, but also the loss of the actions that are adjacent to it in the graph. Two important special cases of this setting are: prediction with expert advice (when G is a clique) and K-armed bandits (when G' has no edges). When losses are generated adversarially. the regret in the feedback graph setting with strong observability has been shown to scale with the independence number of G. Intuitively, denser graphs, which correspond to smaller independence numbers, provide more feedback to the learner, thus enabling a better control on regret. More specifically, the best known upper and lower bounds on the regret after T rounds are O ((VaT log K) and ((VaT) [3, 4J. It has been known for three decades that this upper bound is tight for 1 (the experts case, [9, 10]). When K
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(the bandits case), the lower bound (((KK) which has also been known for nearly three decades [7, 8]-was matched by a corresponding upper bound O ((KT)) only in 2009 [5]. These results show that in feedback graphs, the logarithmic factor vlog K is necessary (at least) for the a = case, while it must vanish from the minimax regret as grows from 1 to K, but the current bounds fail to capture this fact. In this work, we prove new upper and lower regret bounds that for the first time account for this vanishing logarithmic factor.
To prove our new upper bound, we use the standard FTRL algorithm run with the g- g-Tsallis entropy regularizer (q-FTRL for short). is well-known [1] that for q = 3 this algorithm (run with appropriate loss estimates) achieves regret O( ((VKy VT) when a K (bandits case), while for q + 1 the same algorithm (without loss estimates) recovers the bound O (VTTlog K) when a = 1 (experts case). When G contains all self-loops, we show in Theorem 1 that, if y is chosen as a certain function ((a, K), then g(a, K)FFRRL, run with standard importance weighted loss estimates, achieves regret P(VaT(1 + (oa))/a))) This is a strict improvement over the previous bound, and matches the lower bounds for bandits and experts while interpolating the intermediate cases. This interpolation is reflected by our choice of g, which goes from 2 to 1 as a ranges from to K. The main technical hurdle in proving this result is an extension to arbitrary values of q E [ 1) of a standard result- see, c.g., [29, Lemma 3]-that bounds in terms of a the variance term the regret of q-FTRL. In Theorem 2, using modified loss estimate, this result is extended to any strongly observable undirected graph [2]. a class of feedback graphs in which some of the actions do not reveal their loss when played. In Theorem 3, we show via doubling trick that our new upper bound can also be obtained (up to constant factors) without the need of knowing (or computing) a. As the resulting algorithm is oblivious to our analysis also applies to arbitrary sequences of graphs Gt. where K' is constant but the independence number oi of G, can change over time, and the algorithm observes G2 only after choosing an action (the so-called uninformed case). In this setting, the analysis of the doubling trick is complicated by the non- non-trivial dependence of the regret on the sequence of az
2
We also improve on the ((VaTT lower bound by proving a new (( log, K) lower bound for all a > 1. This is the first result showing the necessity outside -utesid the experts case-ot of a logarithmic factor in the minimax regret for all a < K. Our proof uses a stochastic adversary generating both losses and feedback graphs via i.i.d. draws from joint distribution. This sequence of losses and feedback graphs can be used to define a hard instance of the multi-task bandits problem, a variant of the combinatorial bandits framework [12]. We then prove our result by adapting known lower bounding techniques for multi-task bandits [6]. Note that for values of a bounded away from and K, the logarithmic factor log, K in the lower bound is smaller than the corresponding factor 1 + log(K /a) in the upper bound. Closing this gap remains an open problem.
1.1 Additional related work
Several previous works have used the q-Tsallis regularizer with g tuned to specific values other than 1
2 and 1. For example, in [35, Section 4], q is chosen as a function of K to prove a regret bound of (V K)3) for any strongly observable directed feedback graph, which shaves off a log factor compared to previous works. This bound is worse than the corresponding bounds for undirected graphs because the directed setting is harder. Specific choices of have been considered to improve the regret in settings of online learning with standard bandit feedback. For example, the choice q 5 was used in [31] to improve the analysis of regret in bandits with decoupled exploration and exploitation. Regret bounds for arbitrary choices of g are derived in [36, 23] for a analysis of bandits, though
å remains the optimal choice. The - Tssllis entropy and the Shannon entropy (g- = 1) regularizers have been combined before in different ways to obtain best-of- titt--of--o--ttee both-worlds guarantees for the graph feedback problem [18, 22]. The idea of using values of E (g. 1) for feedback graphs is quite natural and has been brought up before, e.g., in [32], improved dependence on the graph structure by picking suitable value of has not been, to the best of our knowledge, successfully pursued before. On the other hand, an approach based similar use of the T-Talll regularizer has been employed by [26) for the problem of multiarmed bandits with sparse losses to achieve (VsTIn((/s) regret bound, where s the maximum number of nonzero losses at any round.
best-of-both-wond
but achieving
Our lower bound reminiscent of the 22( / KT log N) lower bound proved in [33] for the problem of bandits with expert advice (with N 2 K being the number of experts); see also [17] and [34]. In
2

---

that problem, at each time step, experts suggest distributions over actions to the learner, whose regret computed against the best expert hindsight. Although the two settings are different, the variant of the multitask bandit problem that our lower bound construction simulates is the same as the one used the proof of [17, Theorem 7].
Problem Setting
For any integer 2 1, let [n] [I,...,nn] We consider the following game played over I rounds between a learner with action set V [K] and the environment. At the beginning of the game, the environment secretly selects sequence of losses (4))ET(T) where e V - [0, 1]. and sequence of undirected graphs (Gz)tejr over the set of actions V, that is, G. (V, Ex). At any time t, the learner selects an arm I, (possibly at random), then pays loss (It) and observes the feedback graph G, and all losses (i) neighbouring actions E No, (T+), where No, (t) {j E V (i,j) E F.) (see Online Protocol 1). In this work, we only focus on strongly observable graphs [2]. An undirected
graph G is strongly observable if for every V, at least one the following holds: i E Na or i No(j) for all * i.
The performance of the learner is measured by the regret
Ry E
Σ (L(
min (K
Σ
40
where the expectation is over the learner's internal randomization.
Online Protocol Online learning with feedback graphs
environment: (hidden) losses é, V - [0, 1] and graphs G, Ex), for all & I....,T T
for tort=1e 1,... T do
The learner picks an action I, E V (possibly at random)
The learner incurs loss (T,)
The learner observes losses (i, (()) : No. (4)) and graph G₁
end for
We denote by ΔK the simplex {p E [0, 1]K |lll, }}. For any graph G, we define its independence number the cardinality of the largest set of nodes such that two nodes are neighbors, and denote it by (G). For simplicity, we use N, to denote the neighbourhood No, the graph G. and use ar to denote the independence number (GG)) of G, at time f.
3 FTRL with Tsallis Entropy for Undirected Feedback Graphs
As a building block, this section, we focus on the case when all the feedback graphs GI...., Gr have the same independence number 02 next section. For simplicity, we start with the assumption that all nodes have self-loops: (i, E E, for all i V and all We later lift this requirement and show that the regret guarantees that provide can be extended to general strongly observable undirected feedback graphs, only at the cost of constant multiplicative factor.
Qr a, whereas the general case is treated in the
The algorithm we analyze is q-FTRL (described Algorithm 1), which is an instance of the follow the regularized leader (FTRL) framework see, e.g., [30, Chapter wi-with the (negative) q-Tsallis entropy
(x
1-Ex00) iEV
VI AK
as the regularizer, whose parameter E (0, 1) can be tuned according to our needs. Since we do not observe all the losses in given round, the algorithm makes of unbiased estimates for the losses. When all self-loops are present, we define the estimated losses in the following standard manner. Let
For notational convenience, we will sometimes treat the loss functions e, V + [0, 1] as vectors with components ls ((())...,,((()..
3

---

I be the action picked at round t, which is drawn from the distribution Pt E AK maintained by the algorithm, the loss estimate for an action E V at round given by
4(0 14 E (())). P:(1)
E00
where Pa(1) P(4 N(()) = ESEN, Pr(j). This estimate is unbiased in the sense that
E. [() (1) for all 1 (T) and all E V, where denote E. [ E. Ti...r Te-1]-
Algorithm 1 9-FTRL for undirected feedback graphs
input: 9 (0, 1). 17 0 initialization: p1 (i) < 1/K for all i = I....,K
=ort=1...... do
Select action I Pt and incur loss (T)
Observe losses {ii, (()) : ]NN(4)) and graph G2
Construct loss estimate & for le
e.g., (1) or (6)
Let Pi+1 & arg minpeax 7 Eeez ts,p) + vp(p)
end for
A key part of the standard regret analysis of q-FTRL (see, e.g., the proof of Lemma 3 in Appendix A) handling the variance term, which, with the choice of estimator given in (1), takes the following form
Be(g) Σ (e(1)=-q (i(
&EV
By Hölder's inequality, this term can be immediately upper bounded by
Bi(g)= S Σ p((1)2-9
Ed((i)
Σ
po(i)
Σ
14/ = K
iEV
LIE
LIV
while previous results on the regret analysis of multiarmed bandits with graph feedback [29, would give
Be(g) S Σ pi( P((i)
<a.
REV
However, the former result would only recover O(V KT) regret bound (regardless of a) with the best choice of q = 1/2, which could be trivially achieved by ignoring side-observations of the losses, whereas the latter bound would only manage to achieve a O(v In K) regret bound, incurring the extra Iln K factor for all values of a. Other results in the literature (e.g.. see [2, 4, 16, 19, 22, 25, 32, 35)) do not bring an improvement this setting when bounding the B,(q) term and, hence, do not suffice for achieving the desired regret bound. The following lemma provides novel and improved bound on quantities of the same form as B,(g) in terms of the independence number a₃ = a of the undirected graph Gr-
Lemma 1. Ler G = (V. E) be any undirected graph with [V| K vertices and independence number aGG)= = a. Let b [0, 1}, p E Ax and consider any nonempty subset C V (N(v)). Then,
p(u)
Σ DEU
2 1-b
EueNo(o)(a p(u)
Proof. First of all, observe that we can restrict ourselves to the subgraph GIU] induced by U, i.e., the graph GIU] = (U, En (U U)). This because the neighbourhoods in this graph are such that Naju (v) Nc(u) for all u e U, and its independence number is (G((T) I (G). Hence, it suffices to prove the claimed inequality for any undirected graph G = (V, E) with all self-loops. any p E [0, 1]A such that |p|| I 1, and the choice U V. We assume this in what follows without loss of generality.

---

For any subgraph H _ G with vertices V(H) S V, denote the quantity we want to upper bound by
p(u)1tb
Q(H)
E
E LuENo(s) p(u)
VEV(H)
Our aim is thus to provide an upper bound to Q(G).
Consider greedy algorithm that incrementally constructs subset of vertices in the following way: at (c p(u)). adds the solution, and
each step, selects a vertex e that maximizes it removes e from G together with its neighbourhood (u( This step is iterated on the remaining graph until no vertex is left.
Let S = {ui...., U S V be the solution returned by the above greedy algorithm on G. Also let GI...., Go+1 be the sequence of graphs induced by the operations of the algorithm, where G1 G and G.+1 is the empty graph, and let (2) = NG.(w) for v E (G,)). At every step r E [s] of the greedy algorithm, the contribution Q(G) of the removed vertices (,, amounts to
p(u)
p(u,)
Q(G.) Q(G++))= (E,.(
Σ p(v)
(v) (()
E EuENi (()) p(u)
(EN,(
E EvEN p(v)
EvENi(e,) p(u) p(v,)* = p(u,)*
where the last incquality is due to the fact that N.(b) (v) for all illij and V,, Therefore, we can observe that
Q(G)
Q(G,+1)) - Σr(o)
vES
The solution is an independent set of G by construction. Consider now any independent set C V of G. We have that
x(v)²
Σ VEA
p(u)* S
max #EAK
Σ
I((1)*
|A|
max zEAK
Σ
[A]
1 Σ x(0)
< |A
max #EAR
S
(3)
A
where the second inequality follows by Jensen's 's inequality and the fact that b [0. 1].
Observe that this upper bound is tight for general probability distributions E Ak over the vertices V of any strongly observable undirected graph G (containing least one self-loop), as exactly achieved by the distribution p* E Ax defined p² (i) [S] T (i E S} for some maximum indepen- dent set S V of G. Using this lemma, the following theorem provides improved upper bound under the simplifying assumptions we made thus far.
Theorem 1. Let GI...., GT be sequence of undirected feedback graphs, where each G, contains all self-loops and has independence number Ot = a for some common value a E [K]. If Algorithm is run with input
2 11+
In(K/o
2qK1-q
q q= 2
1+
VnnK/a)) + 2 E 11/2,1)
and 7= T(1 4)a9
and loss estimates (1), then its regret satisfies Rr S 22/eaT (2 In(K/a)))
Proof. One can verify that for any E V, the loss estimate (1) defined in (1) satisfies E, [2(())2] 1/ (i). Hence, using also that E, (i)] (i),,, Lemma 2 in Appendix A implies that
K' n-
17
T
2
Rr 5 1 9)
E
(4)
2q
Pi(i)
1=1
VIV
K
(5)
1)(1 9)
24
5

---

where the second inequality follows by Lemma I with b = 1 - since all actions i E V are such that i No()). Our choices for q and 17 allow us further upper bound the right-hand side of (5) by
2K1-9a3 ==
1 In(ak) - 2 2V In (K/o))² +4) 1+
V q(1 - 9)
/ 2T exp
2 V (K/a)) +
2
1 / 2eal 2 (Kn/aa)) +4) $2 eaT e (n//a) +4
s
(2 (2+1n(//))
The regret bound achieved in the above theorem achieves the optimal regret bound for the experts setting (i.e., a = 1) and the bandits setting (i.e., = K) simultaneously. Moreover, it interpolates the intermediate cases for a ranging between and K, introducing the multiplicative logarithmic factor only for graphs with independence number strictly smaller than K. We remark that the chosen values of q and y do in fact minimize the right-hand side of (5). Note that we relied on the knowledge of a to tune the parameter q. This is undesirable in general. We will show how to lift this requirement in Section The same comment applies to Theorem 2, below.
We now show how to achieve the improved regret bound of Theorem I in the case of strongly observable undirected feedback graphs where some self-loops may be missing; i.e., there may be actions E V such that i & (i).). Using the loss estimator defined in (1) may lead to a large variance term due to the presence of actions without self-loops. One approach deal with this see, e.g., [35] or [28]- is to suitably alter the loss estimates of these actions.
Define S, {i E V i É N.(1)) the subset of actions without self-loops in the feedback graph Ge at each time step L E (T). The idea is that we need to carefully handle some action i E S, only in the case when the probability p. (i) of choosing at round & is sufficiently large, say, larger than 1 1/2. Define the set of such actions as Jr = (i E S. (1) > 1 1/2]
and observe that [Ja] S 1. Similarly to
[35], define new loss estimates
iFEE J. 460 IfL No(1)++ if
6.0 T (Te E N(()
(1)
=
P.O)
(6)
P(())
for which it still holds that I. [4 = l and that E, [((()))] S 11/P(()) for all & Jr. This change, along with the use of Lemma I for the actions in V \ S, suffices in order to prove the following regret bound (see Appendix B for the proof) when the feedback graphs do not necessarily contain self-loops for all actions.
Theorem 2. Let GI...., GT be sequence of strongly observable undirected feedback graphs, where each Ge has independence number Or = or for some common value a E [K]. If Algorithhm is run with input
q 2 (1+
In(K/a) Vin(K/)2 / +4+2)
1
2g
E 11/2.1)
and
== 3 T(1 9)a9
and loss estimates (6), then its regret satisfies Ry S 6 (2 In(K/a)).
4 Adapting to Arbitrary Sequences of Graphs
In the previous section, we assumed for simplicity that all the graphs have the same independence number. This independence number was then used to tune q, the parameter of the Tsallis entropy regularizer used by the algorithm. In this section, we show how to extend our approach to the case when the independence numbers of the graphs are neither the same nor known a-priori by the learner. Had these independence numbers been known a-priori, one approach is to set q as in Theorem 2 but using the average independence number
T
at T

---

Doing so would allow us to achieve o au(1 + In(K/ár)) regret bound. We now show that we can still recover a bound the same order without prior knowledge of är. For round and any fixed g [0, 1], define
He(g) E
Pr(x)
VEV'S
We know from Lemma I that H))g) S ag. Thus, we can leverage these observations and doubling trick (similar in principle to [3]) to guess the value of or. This approach is outlined in Algorithm 2. Starting with with and set as in Theorem 2 but with 2" replacing the independence number. Then, at t 2 Ty, we increment and restart Algorithm only
and T,
the idea is to instantiate Algorithm at time-step T,
1 T
Σ
> 2"
since (again thanks to Lemma 1) the left-hand side of the above inequality is always upper bounded by ãτ. The following theorem shows that this approach essentially enjoys the same regret bound of Theorem up an additive log2 ār term.
Algorithm 2 g-FTRL for an arbitrary sequence strongly observable undirected graphs
input: Time horizon
define: For each {O...., [log2 KJ},
1 (1 q. =
In(K/2")
24r K1 9- and The 117(1 - (r) (2r)ar
V Vnn(K22r2 2
initialization: To 1, 0, instantiate Algorithm with q qu. 170, and loss estimates (6)
for t 1,..., TT do Perform step of the current instance of Algorithm if
Σ 2==T, Hg(g,) 1/9- 211 then
r ++++1
T, +
Restart Algorithm with = Gr, fr. and loss estimates (6)
end if
end for
Theorem 3. Lei 4/ 2+v4-2m22
Then, the regret of Algorithm 2 satisfies
In2
K [T
RT < C.
Σ
2 In
+ logg हे
Proof sketch. For simplicity, we sketch here the proof for the case when in every round i, all the nodes have self-loops; hence, He(q) = (q).). See the full proof Appendix C, which treats general case in a similar manner. Let n [log2 arl and assume without loss of generality that är 1. Since Lemma implies that for any and Be(g.) I at", we have as consequence that for any t 2 Tr,
Σ a, $ az 2 T Σ Ba < T == T
Hence. the maximum value of r that the algorithm can reach is 1. In doing so, will execute instances of Algorithm 1, each corresponding to value of r E {O...., n - 1}. For every such r. upper bound the instantaneous regret step T,+1 1 (the step when the restarting condition is satisfied) by 1, hence the added log, air term in the regret bound. For the rest of the interval; namely, for E [T,, T T
2), we have via (4) that the regret of Algorithm is bounded by
K1-9-
+
Tre 20r
E
T
Σ
Be(g.)
T/ (1
4r)
t=
7

---

Define Tr Tx+1 - T. 1, and notice that
1++1-2
I++1-2
Σ
B.(g,) 1 Tra+1
1
Σ
1/9.
T Trat+1
t=T,
S TTr++
T
2
4r
3 2T (2))
Tri+11
where the first inequality follows due Jensen's 's inequality since 9, (0, 1), and the second follows from the restarting condition of Algorithm 2. After, plugging this back into (7), we can simply use the definitions of !/, and qr and bound the resulting expression in similar manner to the proof of Theorem 1. Overall, we get that
R S 4v T
2" In (n(cKK--r) + loga är
from which the theorem follows by using Lemma in Appendix A, which shows, roughly speaking. that the the right-hand side is of the same order its last term.
Although Algorithm 2 requires knowledge of the time horizon, this can be dealt with by applying standard doubling trick on T at the cost of larger constant factor. It is also noteworthy that the bound we obtained the form /T (1 + In (n(K/ aā)) and not vE. at + In(K/a,)). Although both coincide with the bound of Theorem when a is the same for all time steps, the latter is smaller via the concavity x(1 + In K /x)) in æ. is not clear, however, whether there is a tuning of E (0, 1) that achieve the second bound (even with prior knowledge of the entire sequence a1:...; Orr of independence numbers).
An Improved Lower Bound via Multitask Learning
In this section we provide a new lower bound on the minimax regret showing that, apart from the bandits case, logarithmic factor is indeed necessary in general. When the graph is fixed over time, it is known that a lower bound of order VaT holds for any value of a [3, 29]. Whereas for the experts case (a = 1), the minimax regret is of order /T K [9]. The following theorem provides, for the first time, lower bound that interpolates between the two aforementioned bounds for the intermediate values of ex.
Theorem 4. Pick any K 2 2 and any a such that 2 S S K. Then, for any algorithm and for all T 2 a log, K [lo({133) there exists a sequence of losses and feedback graphs GI...., , GT such that
(G,) = a for all 1..... T and
RT 18V2 VaT a'T'ooga K.
In essence, the proof of this theorem (see Appendix D) constructs a sequence of feedback graphs and losses that is equivalent hard instance of the multitask bandit problem (MTB) [12], important special case combinatorial bandits with a convenient structure for proving lower bounds [6, 15, 21]. We consider variant of MTB in which, the beginning of each round, the decision- makeer selects an arm to play in each one of M stochastic bandit games. Subsequently, the decision- maker only observes (and suffers) the loss of the arm played in single randomly selected game. For proving the lower bound, we use a class of stationary stochastic adversaries (i.e., environments), each generating graphs and losses in manner that simulates an MTB instance.
Fix 2 S a < K = V and assume for simplicity that M log, K is an integer. We now construct an instance of online learning with time-varying feedback graphs G, (V, E,) with a(G,) that is equivalent to an MTB instance with M bandit games each containing a "base actions". Since K
we uniquely identify each action in V with vector
(a(1), a(M)).....MM))))) (M)) in
As a lower bound, this is known to hold asymptotically K and T' grow. However, it can also be shown to hold conpaoymptti (though with worse leading constants); see [20, Theorem 3.22] or [11, Theorem 3.6].

---

G
G
G
11,
(1,
(1, (,1,) 2)
(2, 2,
(1,2,1) 1)
(2, 2. 1)
C1
C2
C3
(1,1,1)
(1,2,1)
(1, 11
12,
(1,1,1
(2, 1,1)
(2, 1,
(2
(1, 2,,,, 2)
2,,
(1, 2)
(2, 2, 2)
C122
22
C3.2
(2, 1,)
12
(1,2,1) 12)
(1,
(2, 1,)
Figure 1: This figure shows example of the multi-task bandit construction used prove the lower bound. Here, K = 8 and a = 2; thus, the number of games is M = 3. Each action is identified by tuple of three numbers, each corresponding to choice of one out game. Each of the three graphs in the figure corresponds to a game, such that two actions share an edge and only they choose the same base action in the corresponding game. At every round, graph is randomly drawn, and all actions belonging to the same clique suffer the same loss.
pair of "base actions" in each
[a]*M, The action ae V chosen by the learner at round equivalent to a choice of base actions (1)...... ar(M (M) in the M games. The feedback graph at every round is sampled uniformly at random from a of M undirected graphs (G* MM Ri=1 where G (V, E*) is such that (a, a') E E if and only if a(i) = ai).). This means (see Figure 1) that each graph G consists of a isolated l2 cliques {C such that an action a belongs to clique Ct,, if and only if a(i) = j. Clearly, the
independence number of any such graph is a. Drawing feedback graph G. = G corresponds to the activation of game in the MTB instance. Hence, choosing a V with feedback graph G, G' is equivalent to playing base action (t()) in game in the MTB. As for the losses, we enforce that, given feedback graph Gr, all actions that belong the same clique of the feedback graph are assigned the same loss. Namely, if G, = G' and a(i) = d'(i) = j. then (a) = (a'), which can be seen as the loss (j) assigned to base action in game G To choose the distribution of the losses for the base actions, we apply the classic weedle-n----haystade approach of [7] over the M games. More precisely, we construct different environment for each action the losses in each MTB game slightly favors (with a difference of a small > 0) the base action corresponding
in such a way that the distribution of
that game. The proof then proceeds similarly to, for example, the proof of Theorem 5 in [6] or Theorem 7 in [17].
While both upper and lower bounds achieve the desired goal of interpolating between the minimax rates of experts and bandits, the logarithmic factors the two bounds are not exactly matching. In particular, if compare + log,(K3 (K/a) and loga K, can that although they coincide at a = 2 and a = K, the former is larger for intermediate values. It is reasonable to believe that the upper bound is of the correct order, seeing as it arose naturally result choosing the best parameter for the Tsallis entropy regularizer, whereas achieving the extra logarithmic term in the lower bound required somewhat contrived construction.
Conclusions and Future Work
In this work, we have shown that a proper tuning of the q-FTRL algorithm allows one to achieve (
regret for the problem of online learning with undirected strongly ob- servable feedback graphs. Our bound interpolates between the minimax regret rates of the bandits and the experts problems, the two extremes of the strongly observable graph feedback spectrum.

---

Furthermore, we have shown that an analogous bound can be achieved when the graphs vary over time, and without requiring any prior knowledge on the graphs. These results are complemented by our new lower bound of 52 V T K k)/(ln))) which holds for 2 and shows the necessity of a logarithmic factor in the minimax regret except for the bandits case. While our results provide the tightest characterization to date of the minimax rate for this setting, closing the small remaining gap (likely on the lower bound side) is an interesting problem. After the submission of this manuscript, subsequent work [14] showed a lower bound for fixed feedback graphs composed of disjoint cliques that would imply worst-case optimality (up to constant factors) of our proposed algorithm for each pair of K and a-see Appendix E for a more detailed comparison with results therein. Extending results to the case of directed strongly observable feedback graphs is considerably harder task- Appendix F for a preliminary discussion. Better understanding this more general setting is an interesting future direction.
Acknowledgements
KE, EE, and NCB gratefully acknowledge the financial support from the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), funded by the NextGennraaiinnEU program within the PNRR scheme (M4C2, investment 1.1), the FAIR (Future Artificial Intelligence Research) project, funded by the NexIGenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence), and the EU Horizon 114-222-HUMANN action under grant agreement 101 202377 project ELIAS (European Lighthouse of Al for Sustainabil- ity). TC gratefully acknowledges the support of the University of Ottawa through grant GR002837 (Start-Up Funds) and that of the Natural Sciences and Engineering Research Council of Canada (NSERC) through grants 2GPIN-2023--0668 (Discovery Grants Program) and (Discovery Grants Program, DGECR- Discovery Launch Supplement).
research and innovation
References
[1] J. D. Abemnethy, C. Lee, and A. Tewari. Fighting bandits with new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
[2] N. Alon, Desa-Bianchi, O. Dekel, and T. Koren. Online learning with feedback graphs: Beyond bandits. In P. Grünwald, F. Hazan, and S. Kale, editors, Proceedings of the 28th Conference on Learning Theory, volume 40 of JMLR Workshop and Conference Proceedings, pages 23.35. JMLR.org. 2015.
[3] N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, and O. Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6):1785-
1826, 2017.
[4] N. Alon, N. BesacBBincchi, C. Gentile, and Y. Mansour. From bandits to experts: A tale of domination and independence. Advances in Neural Information Processing Systems, 26, 2013.
[5] J.-Y. Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
[6] J.-Y. Audibert, S. Bubeck, and G. Lugosi. Regret in online combinatorial optimization. Mathe- matics of Operations Research. 39(1):31 1-:,,,14,,1000 2014.
[7] Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322-331. IEEF, 1995.
[8] P. Auer, N. Cesa- Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32( 1):48777, 2002.
[9] N. -isnchi, Freund, D. Haussler, P. Helmbold, R. Schapire, and M. K. Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
[10] N. Cesa-Bianchi, Y. Freund, D. P. Helmbold, D. Haussler, R. E. Schapire, and M. K. Warmuth. How to use expert advice. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 382-391, 1993.
[11] N. Cesa- Bisa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press,
2006.
10

---

[12] N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404-1422 2012.
[13] S.-H. Chang, P. C. Cosman, and L. B. Milstein. Chernoff-type bounds for the Gaussian error function. IEEE Transactions on Communications, 59(1 1):2939-2944, 2011.
[14] H. Chen, Y. He, and C. Zhang. On interpolating experts and multi-armed bandits. arXiv preprint arXiv:2307.07266 2023.
[15] A. Cohen, T. Hazan, and T. Koren. Tight bounds for bandit combinatorial optimization. In Conference on Learning Theory, pages 029-642. PMLR, 2017.
[16] C. Dann, C. Wei, and J. Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In The Thirty Sixth Annual Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages $503-5570. PMLR, 2023.
[17] K. Eldowa, N. Cesa-Bianchi, A. M. Metelli, and M. Restelli. Information-theorett regret bounds for bandits with fixed expert advice. In IEEE Information Theory Workshop, pages 30-35. IEFE, 2023.
[18] L. Erez and T. Koren. Towards best-of-all-worlds online learning with feedback graphs. Ad- vances in Neural Information Processing Systems, 14:28511-28522 2021.
[19] E. Esposito, F. Fusco, D. der Hoeven, and N. Cesa- BesacBianchi. Learning the edge: Online learning with stochastic feedback graphs. In Advances in Neural Information Processing Systems, volume 35, pages 34776-34788, 2022.
[20] D. Haussler, J. Kivinen, and M. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, (946:1990-1125 1998.
[21] S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-I. Kawarabayashi. Improved regret bounds for bandit combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[22] S. Ito, T. Tsuchiya, and J. Honda. Nearly optimal
algorithms for online learning with feedback graphs. Advances in Neural Information Processing Systems, 35:28631- 28643, 2022.
[23] T. Jin, J. Liu, and H. Luo. Improved best-of- best-of-both--eee both-woohddsd guarantees for multi- bandits: FTRL with general regularizers and multiple optimal arms, arXiv preprint arXiv:2302.13554 2023.
[24] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Proceedings of a Symposium on the Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.
[25] T. Koeák, G. Neu, M. Valko, and R. Munos. Efficient learning by implicit exploration in bandit problems with side observations. In Advances in Neural Information Processing Systems, volume 27, pages 613-621, 2014.
[26] Kwon and V. Perchet. Gains and losses are fundamentally diffeerent in regret minimization: The sparse case. Journal of Machine Learning Research, 17(227):1332, 2016.
[27] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[28] H. Luo, H. Tong, M. Zhang, and Y. Zhang. Improved brohh-prbbbbilityy regret for adversarial ban- dits with time-varying feedback graphs. In International Conference on Algorithmic Learning Theory, pages 1000-1100. PMLR, 2023.
[29] S. Mannor and O. Shamir. From bandits to experts: On the value of side-observations. Advances in Neural Information Processing Systems, 24, 2011.
[30] F. Orabona. A modern introduction to online learning. CoRR, htts/1912.132111 2019.
[31] C. Rouyer and Y. Seldin. Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits. In Conference on Learning Theory, pages 3227-3249, PMLR, 2020.
[32] C. Rouyer, D. van der Hoeven, N. Basa-Bianchi, and Y. Seldin. A near-optimal best-of-bothh worlds algorithm for online learning with feedback graphs. In Advances in Neural Information Processing Systems, 2022.
[33] Y. Seldin and G. Lugosi. A lower bound for multi-armed bandits with expert advice. In 13th
European Workshop on Reinforcement Learning (EWRL), volume 2, page 7, 2016.
11

---

[34] N. M. Vural, H. Gokcesu, K. Gokcesu, and S. S. Kozat. Minimax optimal algorithms for adversarial bandit problem with multiple plays. IEEE Transactions on Signal Processing. (7(16):4383-4330 2019.
[35] J. Zimmert and Lattimore. Connections between mirror descent, Thompson sampling and the information ratio. Advances in Neural Information Processing Systems, 32, 2019.
[36] J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1):1310-1358, 2021.
12


Reviews:
[{"review_id": "Io2OyMTdxY", "reviewer": "Reviewer_kfEi", "summary": "The paper studies the online learning under partial observations given by an underlying graph structure. This model is a common generalization of the bandit model (where the feed graph just contains self loops) and the full information model (where the graph is a complete graph with self loops). This model has been considered in the literature where it has been shown that the regret (under a technical condition known as strong observability) is $\\tilde{\\Theta} ( \\sqrt{ \\alpha T } )$ where $T$ is the time horizon and $\\alpha$ is the independence number of the graph. Prior to the present paper there was a logarithmic gap in the regret upper and lower bounds. In particular, the previous bound when instantiated in the case of bandits led to an extra $log K$ factor. The present paper addresses this gap by designing an algorithm  that achieves regret $\\sqrt{ \\alpha T (1 + \\log (K/\\alpha)) }$ which gives the optimal bounds in both extremes. Furthermore, the paper presents lower bounds matching their given bounds. \n\nThe algorithm that the paper analyses is a version of FTRL with the Tsallis entropy regularizer. Since the choice of $q=1/2$ is known to be optimal for bandits and $q=1$ is optimal for full information, the natural idea is to interpolate between using a $\\alpha$ dependent choice of $q$. The paper analyses the variance of the natural inverse probability weighted estimator of the loss in a novel way to arrive at the optimal choice to $q$ to get the regret bound. \n\nThe paper extends their analysis to a slightly more general settings (than just graphs with self loops; time varying independence numbers).", "questions": "- Is it immediately clear how the regret behaves when one only has an estimate of the independence number instead of the exact quantity?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As stated in the summary, the main technical novelty is the analysis of the variance of the IPW estimator in the setting of feedback graphs and FTRL. This is itself a rather interesting contribution and I expect this to be useful in various other contexts. The main result presented in the paper resolves an interesting and natural question in the literature.", "weaknesses": "One main drawback of the approach of $\\alpha$ dependent choice of the $q$ is that it makes the algorithm extremely inefficient (in theory at least). In particular, the independence number of a graph is known to (extremely) hard to approximate; in particular, unless $P=NP$ there is no \"non-trivial\" approximation algorithm even. This is to be contrasted with the previous work in the feedback graph setting which are efficient ( polynomial in $N$ the size of the graph/number of bandits). It remains an excellent open question to see if there is an efficient algorithm achieving this bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. It is indeed true that computing, or even approximating, $\\\\alpha$ is computationally intractable in general. Please note that we do address this issue in Section 4, where we not only generalize our approach to time-varying feedback graphs with possibly different independence numbers, but also lift the requirement of knowing these independence numbers. If we specialize this setting to that of a fixed graph, we can avoid requiring knowledge of $\\\\alpha$ altogether. We thank the reviewer for pointing out this possible misunderstanding. We presented the first result assuming the knowledge of $\\\\alpha$ to simplify the presentation, but we will make sure to clarify this important feature of our theory in the revised version."}, {"review_id": "aX1lTKwCI4", "reviewer": "Reviewer_GSpg", "summary": "Two classical learning problems are learning with experts and multi-armed bandits. In both problems, a learner interacts during $T$ rounds with a set of $K$ actions by selecting an action at each round. After each round, the loss/reward at that step is revealed for all actions (resp. only for the selected action) in the expert (resp. bandit) problem. Mannor and Shamir [24] provided a convenient interpolation between the two problems by considering a generalization via feedback graphs. At each step $t$, losses are observed only at neighbor actions to the selected one, according to a graph $G_t$. The expert case corresponds to the clique, while the bandit case corresponds to graphs without edges. In this context, it is known that if the graphs have independence number $\\alpha$, the minimax regret lies between $O(\\sqrt{\\alpha T\\log K})$ and $\\Omega(\\sqrt{\\alpha T})$. Further, the lower (resp. upper) bound is tight for learning with experts (resp. multi-armed bandits) for which $O(\\sqrt{KT})$ regret is achievable (resp. a lower bound $\\Omega(\\sqrt{KT\\log K})$ is known).\n\n\nThis paper investigates the corresponding $\\sqrt{\\log K}$ gap between the case $\\alpha=1$ (clique/experts) and $\\alpha=K$ (multi-armed bandits) and gives interpolating upper bound $O(\\sqrt{\\alpha T(1+\\log K/\\alpha)})$ on the regret provided that the graphs are undirected and strongly observable (each vertex has either a self-loop or neighbor to all other actions), with the same algorithm---FTRL with $q$-Tsallis entropy---run with appropriate parameter $q(\\alpha)$ and loss estimates. Via a doubling trick, they show that one can achieve this bound up to an additive $\\log \\alpha$ term without prior knowledge on $\\alpha$ (and can be further extended to the case when graphs $G_t$ do not share the same independence number).\n\nLast, the authors provide an improved interpolating lower bound $\\Omega(\\sqrt{\\alpha T \\log K/\\log \\alpha})$, which requires the graphs $G_t$ to vary over time (but with same independence number), showing that when $\\alpha$ is sub-polynomial in $K$, learning with feedback graphs requires an extra factor compared to the known lower bound $\\Omega(\\sqrt{\\alpha T})$. This is shown via a reduction to the multitask bandit problem (different tasks are simulated by changing the graph over time).", "questions": "- Does the analysis carry over for adaptive adversaries, or is the oblivious assumption important?\n- l.97 the independence number is the cardinality of such a set, right?\n- What happens if we assume that the graph is constant over time? Would you expect similar lower bounds to hold?", "limitations": "The limitations were very well addressed by the authors, who clearly identify the new bound on the variance (Lemma 3) as the key added technical contribution for the upper bounds.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper is very well-written and pleasant to read. The question is well posed, and motivated by the fact that improving the $\\sqrt{\\log K}$ factor for learning with experts, from $O(\\sqrt{KT\\log K})$ to $O(\\sqrt{KT})$ remained open for a significant amount of time in the literature. Hence, interpolating the regret bounds in terms of the remaining factor $\\sqrt{\\log K}$ between the known bounds $O(\\sqrt{\\alpha T\\log k})$ and $\\Omega(\\sqrt{\\alpha T})$ seems an important question.\n\nThe upper bounds use the same algorithm (FTRL with $q$-Tsallis entropy) with adapted parameters $q$, which also interpolates between known approaches for the extreme cases $\\alpha=1$ or $\\alpha=K$, giving new insights on the impact of this parameter on the learning behavior.", "weaknesses": "Although the paper presents new contributions to interpolate between experts and bandits, the proofs follow classical arguments in the literature and seem to bring limited original ideas. In particular, it was known that the $q$-Tsallis entropy specifically allows achieving the minimax entropy in both end cases. The main difficulty in the generalization to feedback graphs is in a novel bound for the variance term in the FTRL analysis (Lemma 3), which itself is a generalization of known results in the literature for $q=1$. The rest of the proof follows standard analysis.\n\nThe lower bound heavily relies on the fact that graphs are allowed to vary over time. It seems that the approach cannot be extended to the important case of interest of a fixed graph (which seemed to be the main case studied in the previous literature on feedback graph bandits). The paper would also be significantly strengthened if the lower bound could be improved to match the upper bound when e.g. the independence number $\\alpha$ grows as a polynomial in $K$---in that case, the present paper does not provide improvements in terms of rates compared to the existing literature. As such, the gap left by this paper seems to remain quite important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We remark that obtaining the key result of Lemma 1 was an obstacle for prior work in the way of obtaining improved guarantees using $q$-Tsallis entropy with feedback graphs. Although we focused on the case of time-varying graphs in our lower bound construction, we conjecture that the upper bound is tight for all values of $K$ and $\\\\alpha$, even in the case of some fixed graph. In any case, please note that the lower bound we provided is the first such result that hints at the necessity of a logarithmic factor for the minimax regret of this problem (beyond the experts case). To address the question about adaptive adversaries, the analysis does carry over straightforwardly if the adversary adapts to the previous choices of the learner with our current notion of regret, but it would be interesting to investigate the more challenging notions of dynamic or adaptive regret. Finally, we thank the reviewer for pointing out the typo."}, {"review_id": "akg3rqugJl", "reviewer": "Reviewer_TWzC", "summary": "The paper investigates no-regret online learning algorithms performing under the feedback graph model. More precisely, at each round $t$ a learner selects an action (out of set of possible actions) incurring the cost associated with the specific action at the specific round. The actions are additionally vertices of an undirected graph that changes from round to round. Once the action $i$ is selected at round $t$, the learner is also informed on the costs of the neighboring actions at the specific rounds. The latter setting generalizes the bandit setting (the respective graph is composed by isolated vertices) as well as the full-information setting (the respective graph is a clique). Initially the authors consider the special case where every graph at each round admits independence number $\\alpha$ ($\\alpha =1$ for cliques and $\\alpha =K$ for graphs with $K$ isolated edges). The authors first provide a nearly tight regret guarantee ($O(\\sqrt{\\alpha T \\log (k/\\alpha)})$) for the above special case. The authors also provide a nearly matching $\\Omega(\\sqrt{\\alpha T \\log K / \\log \\alpha})$ lower bound on the regret. Finally the authors remove the assumption that all the arriving graphs admit the same independence number and provide an $O(\\sqrt{\\overline{\\alpha} T \\log (k/\\overline{\\alpha})})$ regret bound where $\\overline{a}$ is the time-average independence number of the graphs. ", "questions": "-", "limitations": "N/A", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I think the paper is very interesting both from the perspective of results as well as from the perspective of techniques. I find very interesting the fact that the provided regret bound matches the respective regret bounds for the bandit ($\\alpha = K$) and the full-information case ($\\alpha=1$).  Also the authors provide a nearly matching lower bound that is based on a novel reduction to multitask learning. Both the techniques for the upper and lower bound require no trivial ideas that are nicely illustrated in the current write up. I also liked the fact that the provided algorithm can be modified to handle the case of time-varying independence numbers.\n\nI overall believe that the paper provides very solid results and that will be of great interest of the online learning audience of NeurIPS.", "weaknesses": "The only limitation of the paper that I can find is the assumption on undirected graphs. The latter is also signified by the authors and considering the complexity of the current I think it is more than fair to consider the directed case for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. As mentioned in our answer to Reviewer J2zm, we agree that the directed feedback graphs case is an interesting future direction, which we hope could be addressed by extending the proposed techniques."}, {"review_id": "6l3C60BtcT", "reviewer": "Reviewer_J2zm", "summary": "This paper considers a classic problem of online learning with feedback graphs, which interpolates the full-information feedback and the bandit feedback. Specifically, the authors consider the case where the feedback graph is undirected, meaning that if node $i$ can observe node $j$, then node $j$ can observe node $i$. The best known $T$-dependent upper bound for this problem is $O(\\sqrt{\\alpha T\\ln K})$ by [Alon et al., 2013]. For general strongly-observable graph, the best known $T$-dependent upper bound is $O(\\sqrt{\\alpha T\\ln^3 K})$ proposed in [Zimmert and Lattimore, 2019]. In this paper, the authors propose an FTRL algorithm with q-Tsallis entropy regularization, showing $O(\\sqrt{\\alpha T(1+\\ln \\frac{K}{\\alpha})})$ upper bound. This recovers the minimax regret bound in both bandit $O(\\sqrt{KT})$ regret and full-information setup $O(\\sqrt{T\\ln K})$. Moreover, the authors also propose an improved $\\Omega(\\sqrt{\\alpha T\\frac{\\ln K}{\\ln \\alpha}})$ lower bound compared with the $\\Omega(\\sqrt{\\alpha T})$ lower bound proven in [Alon et al., 2015], though this lower bound does not match the upper bound obtained by the q-Tsallis FTRL algorithm. In addition, the authors also generalize their results to the undirect strongly observable graphs and time-varying graphs.", "questions": "- The current algorithm is an FTRL-based algorithm. I wonder whether a certain type of online mirror descent based algorithm with a time-varying learning rate can also achieve similar results?", "limitations": "See Weakness and Questions.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and the proposed algorithm is easy to follow.\n- The designed algorithm improves upon the best known $T$-dependent regret bound for undirected strongly observable graphs. Specifically, the important technical contribution is Lemma 1, which shows that the stability term of the FTRL can be bounded by $\\alpha^{1+b}$ where $b$ is decided by the parameter choice of Tsallis-entropy, compared to the one with log factors obtained in [Alon et al., 2015] and [Zimmert and Lattimore, 2019]. \n- The lower bound also tries to bridge the previous gap between the full-information case and the feedback graph case, although there is still a gap between the upper and the lower bound and the technical used in the lower bound is very similar to the one used for proving the lower bound for contextual bandit in [Seldin and Lugosi, 2016].", "weaknesses": "I do not find major weaknesses of this paper, except that the current upper bound is only obtained for the undirected strongly observable graph, which is also discussed by the authors in the appendix. Generalizing this technique to the general strongly observable graphs would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. As mentioned in our answer to Reviewer TWzC, we hope the case of directed feedback graphs could be addressed by extending the proposed techniques. Regarding your question, OMD could be used in place of FTRL with the same techniques presented in this work. With regards to the adoption of a time-varying learning rate, we remark that adapting to a sequence of graphs with arbitrary independence numbers would also require the Tsallis entropy parameter to adapt to such a sequence, which poses significant challenges for the analysis. This is why we adopted an approach based on the doubling trick."}]

Author rebuttal:

Meta-review: There is unanimous support for this paper. An important innovation is a technically novel analysis of a key step from the now-standard Tsallis entropy-based regret analysis (specifically, bounding a certain variance-like quantity in such a way as to get dependence on the independence number rather than the number of actions). There initially were concerns about the level of technical innovation, but the from the discussion period with the authors, the concerned reviewers agreed about the technical novelty. While ultimately, this work "only" amounts to refining bounds at the level of log factors, such refinements often are not easy, which makes this contribution impressive. This work will be a welcome contribution to this year's conference.
Decision: Accept (spotlight)