Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
Year: 2022

Abstract:
We study the online learning with feedback graphs framework introduced by Mannor and Shamir [24], in which the feedback received by the online learner is specified by a graph over the available actions. We develop an algorithm that simultaneously achieves regret bounds of the form: O( √ θ( ))) with adversarial losses; O(θ( ) polylog)) with stochastic losses; andO(θ( ) polylog) + √ θ( ) ) with stochastic losses subject to adversarial corruptions. Here, θ( ) is the clique covering number of the graph . Our algorithm is an instantiation of Follow-theRegularized-Leader with a novel regularization that can be seen as a product of a Tsallis entropy component (inspired by Zimmert and Seldin [27]) and a Shannon entropy component (analyzed in the corrupted stochastic case by Amir et al. [3]), thus subtly interpolating between the two forms of entropies. One of our key technical contributions is in establishing the convexity of this regularizer and controlling its inverse Hessian, despite its complex product structure.

text: √ θ( ))) with adversarial losses;
O(θ( ) polylog)) with stochastic losses; andO(θ( ) polylog) + √ θ( ) ) with stochastic losses subject to adversarial corruptions. Here, θ( ) is the clique covering number of the graph . Our algorithm is an instantiation of Follow-theRegularized-Leader with a novel regularization that can be seen as a product of a Tsallis entropy component (inspired by Zimmert and Seldin [27]) and a Shannon entropy component (analyzed in the corrupted stochastic case by Amir et al. [3]), thus subtly interpolating between the two forms of entropies. One of our key technical contributions is in establishing the convexity of this regularizer and controlling its inverse Hessian, despite its complex product structure.

heading: 1 Introduction
text: Online learning models a repeated interaction between a learner and an environment. In this framework, the learner has to choose an arm (or action) from a set of # arms, iteratively across ) rounds. After choosing an arm the learner incurs an associated loss and receives feedback from the environment. The feedback the learner receives can range between the full-information setting where after choosing an action the learner sees the losses of all # arms, and themulti-armed bandit (MAB) setting where only the loss of the arm chosen at the current round is revealed. Traditionally, the way the losses are generated is either in an adversarial manner (i.e., can be arbitrary in each round), or stochastically (i.e., sampled i.i.d. from an unknown distribution). Recently, online algorithms achieving best-of-both-worlds guarantees have drawn significant attention: these are algorithms that are able to perform optimally in both the stochastic and adversarial settings, without prior knowledge of the regime and its parameters. Recent advances in this line of work [3, 27, 13, 28, 18] have resulted with algorithms that achieve a remarkable best-of-all-worlds guarantee: in a general intermediate adversarially-corrupted regime, where losses are generated stochastically but then may be modified by an adversary in an arbitrary way, these algorithms attain regret that grows with the square-root of the total amount of corruption introduced. Even more, these guarantees significantly outperform those obtained by specialized algorithms designed exclusively for the corrupted stochastic setting [22, 11, 23]. Our goal in this work is to extend these best-of-all-worlds results from the full-information andMAB settings to more general online learning problems and feedback models. We focus on the general framework of online learning with graph-structure feedback, originally introduced by Mannor and Shamir [24] and studied extensively since (e.g., [1, 10, 16, 9, 21, 20, 12]). In this model, feedback is described by an undirected graph over the arms; the set of observations received following each prediction is comprised of the loss of the chosen arm as well as the loss of all of its neighbors in .
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The feedback graphs framework nicely interpolates between online learning with full-information and learning with bandit feedback, and generalizes to settings with more complex side-observation structure. Full-information online learning is captured as an extreme case where the graph is the clique over the # arms; on the other extreme, an empty feedback graph that contains no edges corresponds to the multi-armed bandit problem. The optimal regret in the feedback graphs setting is well understood, both in the adversarial and stochastic regimes. In the former, the state-of-the-art is obtained by Alon et al. [1] who gave an algorithm with regret O( √ α( ))), where α( ) is the independence number of , and also established its optimality up to log factors. In the latter regime, Cohen et al. [10] proposed an algorithm whose regret is roughly O(α( ) log)), which is again nearly optimal. However, it remains unclear whether there exists a single algorithm that attains both bounds simultaneously, without prior knowledge of the regime, considering that the existing optimal algorithms in the two settings are inherently different. Of course, one can always ignore the additional feedback and use an existing best-of-all-worlds algorithm for MAB; however, this would result with a direct dependence on the number of arms # . The challenge is then to improve this dependence by exploiting the structure of the feedback graph.

heading: 1.1 Our contributions
text: We make a significant step towards obtaining a best-of-all-worlds guarantee in the feedback graphs model, by giving the first algorithm in this setting that achieves a uniform best-of-all-worlds guarantee and improves over the existing MAB bounds in a non-trivial way. Our algorithm achieves regret roughly of the form θ( )polylog()) when the losses are stochastic i.i.d., and Õ( √ θ( ))) when the losses are fully adversarial; here θ( ) denotes the clique covering number of the graph .1 Furthermore, in an intermediate adversarially-corrupted stochastic setting, where the losses are generated stochastically but then may be corrupted by an adversary, we obtain a bound roughly of the form θ( )polylog()) + Õ( √ θ( ) ) with being the total amount of corruption, that smoothly interpolates between these two extremes. Crucially, the algorithm achieves the aforementioned bounds simultaneously and agnostically, in the sense that it need not be aware of the actual underlying loss generation process, and in particular, of the actual level of adversarial corruption introduced. To state our results more concretely, let+1, . . . , +θ be a minimum clique cover of (here θ = θ( )), and denote by ∆: the minimal gap of a suboptimal arm in +: ; namely, the difference in mean losses (with respect to the stochastic uncorrupted losses) between an arm in+: and the best armwhosemean loss is minimal. Finally, define / = ∑ ::∆:>0 1/∆: (this is the quantity governing the complexity of the learning problem in the purely stochastic case; see [10]). Then, our main result can be stated as:
Theorem (main, informal). There exists an algorithm (see Algorithm 1 in Section 4) which, given a clique covering +1, . . . , +θ of , obtains an expected regret bound of Õ(min{ √ θ), / + √ /}) in the -corrupted stochastic setting. In particular, in the stochastic setting ( = 0) the expected regret of the algorithm is at most Õ( ∑ ::∆:>0 1/∆: ), while in the adversarial setting ( = )) its expected
regret is bounded by Õ( √ θ)).
The above results leverage the graph structure in a non-trivial way and improve the direct dependence on the number of arms # in existing best-of-all-worlds results to a dependence on θ( ), which is potentially significantly smaller than # . On the other hand, our bounds do not feature the optimal dependence on the independence number α( ); we leave it as a main open question whether it is possible to obtain a best-of-all-worlds result with α( ) replacing θ( ) in the bounds. We remark however, as we discuss in more detail below, that obtaining bounds scaling with the weaker θ( ) is already a highly non-trivial task and so we believe that our results form a significant step towards obtaining optimal best-of-all-worlds bounds. Another question we leave open is whether our dependence on ) can be improved toO(log)) andO( √ )) in the stochastic and adversarial cases respectively, removing a few excess logarithmic factors in our bounds. We note that the algorithm achieving the bound above is not adaptive to the best clique covering of the feedback graph for which the quantity / above is minimal. In other words, the algorithm requires a specific minimum clique covering as input, and the regret bounds we show take into account the suboptimality gaps with respect to this given covering, which may be worse than other coverings
1The clique covering number of a graph is the minimum number of cliques that cover its set of vertices; without loss of generality, we can assume that the latter set of cliques is a partition.
with respect to these gaps. Improving the algorithm such that it becomes adaptive to the minimum clique covering could be an interesting direction for future research.

heading: 1.2 Overview of main ideas and techniques
text: Our approach is inspired by recent progress in obtaining best-of-all-worlds guarantees in the two extreme cases of our problem: multi-armed bandits [27] and full-information experts [3]. Somewhat surprisingly, it has been shown in both cases that this type of guarantee can be obtained by simple algorithms based on the canonical Follow-the-Regularized-Leader template, traditionally used exclusively in adversarial online learning. Our primary technical challenge therefore boils down to designing a convex regularizer given the feedback graph , that carefully interpolates between the well-understood regularization schemes in the full-information and bandit cases. In the full-information case, best-of-all-worlds results [3] rely on (a time-varying version of) the negative Shannon entropy '(?) = ∑# 8=1 ?8 log ?8 as regularization. In a nutshell, its crucial properties are an O(log #) uniform upper bound on its magnitude over the probability simplex, and on the other hand, that its Hessian ∇2'(?) = diag(?−11 , . . . , ? −1 # ) satisfies `T (∇2'(?))−1` = O(1) for any loss vector ` ∈ [0, 1]# . (We omit more technical details on third-order conditions and selfbounding properties from this informal discussion.) In the bandit case, on the other hand, the best-of-all-worlds result of [27] relies on a Tsallis entropy (with parameter α = 1/2) regularizer '(?) = − ∑# 8=1 √ ?8 , originally proposed in the context of MAB by [4]. This form of entropy is
bounded uniformly over the simplex byO( √ #), and its Hessian ∇2'(?) = 14 diag(? −3/2 1 , . . . , ? −3/2 # )
satisfies E[ ˜̀T (∇2'(?))−1 ˜̀] = O( √ #) for loss estimators ˜̀ used in MAB. In both cases, the regularizer strikes the “right” balance between the two bounds, which is necessary for optimal regret. Moving to the more complex feedback model induced by a graph, it is natural to expect that an appropriate regularization would emerge as a certain combination of the Shannon and Tsallis entropies. For simplicity, consider a simple graph formed as a union of θ disjoint cliques+1, . . . , +θ, and let ? be a probability vector over its vertices. Then, we are looking for a regularization that would treat the marginal clique probabilities @: = ∑ 8∈+: ?8 as a Tsallis entropy, while behaving within a clique (with respect to the internal conditional probabilities ?8/@: for 8 ∈ +: ) like the negative Shannon entropy. Inspecting the technical conditions more deeply, it turns out that we seek a regularizer ' such that the Hessian at ? is lower bounded by a diagonal matrix with the 8’th diagonal entry corresponding to 8 ∈ +: is ?−18 @−1/2: . A natural candidate would be simply the sum of the Shannon and Tsallis entropies; unfortunately, this regularization lacks the bi-level structure we need, and indeed, its Hessian does not admit the desired lower bound. Our main technical innovation is the design of a new convex regularizer that admits the aforementioned lower bound on its Hessian, and on the other hand, is bounded by O( √ θ log #) over the simplex. Interestingly, we find that the necessary conditions are met for a regularizer produced by the product of a negative Tsallis entropy (over the marginals @: ) and a negative Shannon entropy (over the conditional ?8/@: ), rather than their sum. Of course, such a product need not be a convex function in general, and indeed, the regularization we just described fails to be convex even in simple cases (see Fig. 1). Nevertheless, it turns out that there is a simple fix that makes this bi-level regularization a convex function: a simple linear shift to the Shannon entropy component. Not only that, but the resulting regularizer also admits the stronger Hessian lower bound we require. We refer to this new regularizer by Tsallis-Shannon entropy, and discuss the details of its derivation in Section 3; the remainder of the development takes more standard lines and is described in Sections 4 and 5.

heading: 1.3 Additional related work
text: The online learning with feedback graphs framework we consider here was introduced by Mannor and Shamir [24]. A tight characterization of the minimax regret in this model in the adversarial case was established by [2, 1]. The setting was first considered in the stochastic setting by Caron et al. [9], and was followed by numerous subsequent papers [10, 12, 20]. Cohen et al. [10] considered a setting in which the feedback can change in each time step, and the sequence of feedback graphs is not known to the algorithm, and Lu et al. [20] considered a setting where the loss distribution can change across rounds. Lee et al. [17] assume a hierarchical approach which maintains an explicit probability distribution over the cliques which is updated via OMD steps, whereas the individual arm probabilities within each clique are handled by a dedicated instance of adaptive Hedge. We remark that some of the mentioned work (most notably [1, 10]) analyze directed feedback graphs which are more general than the undirected graphs we consider here, and moreover, do not necessarily contain
self-loops. Such models currently lie beyond our scope, but we believe that our regularization techniques should be extensible to these variants too. The line of work on best-of-both-worlds algorithms in the context of MAB was initiated by Bubeck and Slivkins [6]. Their result was subsequently improved in a sequence of papers [5, 25, 26], culminating in the remarkably elegant recent result of [27]. A number of tricks and techniques we use are borrowed (and sometimes extended) from this line of work, including refined regret bounds for FTRLwith local norms [3, 27, 13], shifted loss estimators and self-bounding regret [26, 27, 3], and augmented log-barrier regularization for inducing stability [7, 17, 13]. The adversarially corrupted stochastic setting had also received considerable attention in recent years across numerous online learning frameworks [22, 23, 11, 14, 15, 19, 27, 13], including a paper by Lu et al. [21] who analyzed this setting in the bandits with graph feedback framework and showed a regret bound which generalizes naturally to the stochastic setting, but not to the adversarial setting. Thus the question of whether it is possible to obtain regret bounds which generalize to best-of-both-worlds type guarantees in the feedback graphs framework, was not resolved in these papers. Finally, we note that the idea of using a hybrid regularization was suggested in a number of previous works. Bubeck et al. [7, 8] explored hybrid regularizers in the context of multi-armed bandits. More recent works include Zimmert et al. [28] who used a hybrid regularization closely related to Tsallis entropy presented in Zimmert and Seldin [27] to obtain best-of-both-worlds type guarantees in the semi-bandit setting. Similarly, Jin and Luo [13] use a form of a hybrid regularizer also related to Tsallis entropy in order to obtain similar guarantees for episodic reinforcement learning. However, to the best of our knowledge, our idea and analysis of a multi-level regularization that mixes together distinct types of entropies, were not previously explored.

heading: 2 Preliminaries
text: We consider an online learning problem where the learner has to repeatedly choose an arm from a set of # arms (or actions) indexed by [#] = {1, 2, ..., #}. In each time step C = 1, 2, ..., ) the learner generates a probability vector ?C from the #-dimensional simplex S# = {? ∈ ℝ#+ : ∑# 8=1?8 = 1} and then chooses an arm C ∼ ?C . Thereafter, a loss vector `C ∈ [0, 1]# is generated, the learner incurs the loss `C , C , and feedback is revealed. Feedback model: The feedback received by the learner at each round C is specified by an undirected feedback graph = ( [#], ), known to the learner in advance, and is comprised of {(8, `C ,8) : 8 ∈ N( C )}, where N( 9) denotes the set of neighbors of node 9 in (which we assume always to contain 9 itself). Moreover, we assume that the learner receives as input a minimum clique covering of , i.e., a minimum cardinality collection of cliques {+1, +2, ..., +θ} which partitions and spans the vertices of , meaning each 8 ∈ [#] belongs to some unique clique +: ⊆ [#]. The number of cliques θ in this minimum clique covering, also denoted by θ( ), is called the clique covering number of .2 Assumption on losses: We consider a general adversarially-corrupted stochastic setting (originally introduced in [22]) that includes stochastic and adversarial online learning as special cases, as well as a range of intermediate problems. In this setting, loss vectors ˜̀1, ˜̀2, ..., ˜̀) are first drawn i.i.d. from a fixed probability distribution, unknown to the learner. We denote the mean loss vector by µ = (µ1,µ2, ...,µ# ) = E[ ˜̀C ], and let 8★ = arg min8 µ8 the best arm, which we assume to be unique. We further let +:★ = + (8★) and denote by δ8 = µ8 − µ8★ the gap between arm 8 and the best arm, and ∆: = min8∈+: ,8≠8★ δ8 the minimal gap of a suboptimal arm which belongs to +: (here, if + (8★) is a singleton thenwe interpret∆:★ = 0). After the stochastic loss vectors ˜̀1, . . . , ˜̀) have been generated, an adversary is allowed to corrupt them and form a final loss sequence `1, . . . , `) ∈ [0, 1]# . The overall (expected) corruption level introduced by the adversary is defined as
= E [ )∑ C=1 ‖`C − ˜̀C ‖∞ ] .
Importantly, we assume that this quantity is unknown to the learner, and the algorithms we design will be oblivious to the value of .
2Computing a minimum clique covering in general graphs is a well-known NP-hard problem; we therefore assume it is given as an input, to avoid dealing with such computational efficiency issues.
Regret: The goal of the learner in the adversarially-corrupted stochastic setting is to minimize the pseudo-regret, defined as follows:
R) , E [ )∑ C=1 `C , C ] − min 8∈[# ] E [ )∑ C=1 `C ,8 ] = E [ )∑ C=1 ?C · `C ] − min 8∈[# ] E [ )∑ C=1 `C ,8 ] .
Here, the expectation is over the internal randomness of the algorithm and over any randomness in the losses. The stochastic setting is obtained for corruption level = 0, where the pseudoregret simplifies to R) = ∑) C=1 ∑# 8=1 E[?C ,8]δ8 . The adversarial setting is recovered by setting
= ) ; with an oblivious adversary (that sets the loss vectors ahead of time), the loss vectors are w.l.o.g. deterministic and the above definition of pseudo-regret matches the usual definition of regret. Additional notation: Given 8 ∈ [#] and a partition +1, . . . , +θ of [#], we denote by + (8) the (unique) partition element which 8 belongs to, i.e., 8 ∈ + (8). For a vector ? ∈ ℝ# and a set of arms ⊆ [#], we use the shorthand ?( ) = ∑ 8∈ ?8 .

heading: 3 The Tsallis-Shannon Entropy
text: In this section we introduce our definition of the Tsallis-Shannon entropy that we use as a regularizer and derive themain properties we require. For that, we first define the notion of the Tsallis-perspective of a convex function, that will be useful for this derivation.

heading: 3.1 Tsallis-perspective of a convex function
text: Let ℎ : [0, 1] → ℝ be twice-differentiable and strictly convex. We define the Tsallis-perspective of ℎ as the following function over ℝ3+ :
(G) , √ ‖G‖1 3∑ 8=1 ℎ ( G8 ‖G‖1 ) . (1)
The namemeans to draw a connection to the classical notion of the perspective of a convex function ℎ, given by 6(G, C) = Cℎ(G/C), which is always convex in the pair (G, C); using this fact, the convexity of the function (G) = ‖G‖1 ∑3 8=1 ℎ(G8/‖G‖1) immediately follows since G ↦→ ‖G‖1 is linear over ℝ3+ . In contrast, for the similarly looking function , that has the leading ‖G‖1 factor under a square-root, an analogous result does not hold in general; see Fig. 1 for an example. Remarkably, however, there is a simple condition on ℎ under which it can be shown that not only is convex, but in fact admits a strong lower bound over its Hessian. This is detailed in the following lemma, whose proof is in the full version of the paper [? ]. Lemma 1. Assume that ℎ : [0, 1] → ℝ is twice-differentiable, strictly convex and satisfies the following condition for some constants 2ℎ ∈ ℝ and λℎ > 0, for all vectors H ∈ . ⊆ S3:
3∑ 8=1 ℎ(H8) + 2 3∑ 8=1
( ℎ′(H8) − 2ℎ )2 ℎ′′(H8) + λℎ ≤ 0.
Then, at any G ∈ ℝ3+ such that G/‖G‖1 ∈ . , the function satisfies
∇2 (G) λℎ 4 ‖G‖− 3 2 1 + 1 2 ‖G‖− 7 2 1 3∑ 8=1 G28 ℎ ′′ ( G8 ‖G‖1 ) I8I T 8 ,
where is the 3-by-3 all-ones matrix and I8 = 13 − (‖G‖1/G8)e8 for 8 ∈ [3].

heading: 3.2 Deriving the Tsallis-Shannon entropy
text: We can now define the Tsallis-Shannon entropy in terms of Tsallis-perspectives and derive its local strong convexity properties that we require for our analysis. For a given α > 0, the Tsallis-Shannon entropy with respect to a partition +1, . . . , +θ of + = [#] is defined for all ? ∈ ℝ3+ as
Ψα(?) = θ∑ :=1 √ ?(+: ) · ∑ 8∈+: ψα ( ?8 ?(+: ) ) , where ψα(H) = H log H − αH . (2)
Namely, Ψα is the sum of the Tsallis-perspectives of ψα with respect to each partition element +: . Observe that ψα corresponds to a single term of a (linearly shifted) negative Shannon entropy. Thus, for a probability vector ?, the function Ψα can be viewed as a bi-level entropy, where the top level amounts to the marginal probabilities ?(+: ) (for : ∈ [θ]) and the bottom level to the conditional probabilities ?8/?(+: ) (for 8 ∈ +: ); for the marginal probabilitiesΨα behaves like a 12 -Tsallis entropy, while on the conditional probabilities it operates as a (negative, shifted) Shannon entropy. It is not hard to show that the magnitude of Ψα(?) is at most O( √ θ log #), which is crucial for our purposes as it avoids a direct polynomial dependence on the dimension # . On the other hand, using Lemma 1, we can prove the following lower bound for the Hessian of Ψα for an appropriate choice of α. We remark that the setting of α is crucial: the linear shift in the Shannon entropy component is essential even just for ensuring the convexity of Ψα (see Fig. 1). Lemma 2. Fix γ > 0, and let ? ∈ ℝ#+ such that ?8/?(+: ) ≥ γ for all 8, : with 8 ∈ +: . Then for α = 2(1 + log2 (1/γ)), the Hessian of Ψα at ? satisfies
∇2Ψα(?) 1 2 diag
( 1
?1 √ ?(+ (1)) , 1 ?2 √ ?(+ (2)) , . . . , 1 ?# √ ?(+ (#))
) .
Proof. For brevity, we omit all α subscripts below. Observe thatΨ is a separable sum of θ functions, each of which is a function of variables ?8 with 8 ∈ +: , thus its Hessian ∇2Ψ(?) is block-diagonal with blocks aligned with+1, . . . , +θ. It therefore suffices to establish the Hessian bound for a function of the form Ψ◦ (G) = √ ‖G‖1 ∑3 8=1 ψ(G8/‖G‖1) corresponding to a set of variables + = {G1, . . . , G3}. To this end, we first show that the function ψ satisfies the conditions of Lemma 1 over the domain . = S3∩{H : H8 ≥ γ, ∀ 8 ∈ [3]}, with constants 2ψ = −(1 + 2 log2 (1/γ)) and λψ = 2. Indeed, twice differentiability and strict convexity are immediate, and for any H ∈ . we have
3∑ 8=1 ψ(H8) + 2 3∑ 8=1
( ψ′(H8) − 2ψ )2 ψ′′(H8) + λψ ≤ −2 log2 1γ + 2 3∑ 8=1 H8 ( log H8 − 1 − 2 log2 1γ − 2ψ )2 = −2 log2 1
γ + 2 3∑ 8=1 H8 log2 H8
≤ 0.
Applying the latter lemma on Ψ◦, we obtain (below denotes the 3-by-3 all-ones matrix):
∇2Ψ◦ (G) 1 2 ‖G‖− 3 2 1 + 1 2 ‖G‖− 7 2 1 3∑ 8=1 G28ψ ′′ ( G8 ‖G‖1 ) I8I T 8
= 1 2 ‖G‖− 3 2 1 + 1 2 ‖G‖− 5 2 1 3∑ 8=1 G8I8I T 8
= 1 2 ‖G‖− 3 2 1 + 1 2 ‖G‖− 3 2 1 − 1 2 ‖G‖− 3 2 1 3∑ 8=1 ( 13eT8 + e81T3 ) + 1 2 ‖G‖− 1 2 1 3∑ 8=1 1 G8 e8eT8
= ‖G‖− 3 2 1 − 1 2 ‖G‖− 3 2 1 (2 ) + 1 2 ‖G‖− 1 2 1 diag ( 1 G1 , 1 G2 , ..., 1 G3 ) =
1 2 √ ‖G‖1
diag (
1 G1 , 1 G2 , ..., 1 G3
) ,
and the result follows.

heading: 4 Algorithm and Main Result
text: In this section we present our best-of-all-worlds algorithm for online learning with feedback graphs. The algorithm, detailed in Algorithm 1, follows the general Follow-the-Regularized-Leader (FTRL) template, and is instantiated by a choice of time-varying convex regularization functions 'C together with a standard loss estimator for graph-structured feedback due to [2].
Algorithm 1: FTRL with feedback graphs Input: clique covering {+1, +2, ..., +θ} of an undirected feedback graph ; let α = 2(log2 (#)) + 1), β = 9, γ = 1/(#)), and step sizes ηC = 1/ √ C;
initialize !̂0,8 = 0 for all 8 ∈ [#]; for C = 1, 2, ..., ) do
update ?C = arg min?∈Sγ
#
{ !̂C−1 · ? + 'C (?) } where 'C (?) = η−1C Ψ(?) + Φ(?) (Ψ and Φ are defined in Eqs. (3) and (4));
pick arm C ∼ ?C , observe feedback { (8, `C ,8) : 8 ∈ N( C ) } and set
∀ 8 ∈ [#] : ̂̀C ,8 = `C ,8 ?C (+ (8)) I{8 ∈ + ( C )};
update !̂C = !̂C−1 + ̂̀C ; end
Our main result regarding Algorithm 1 is given in the following. Theorem 1. Algorithm 1 attains the following expected pseudo-regret bound in the -corrupted stochastic setting:
R) = Õ
( min {√ θ), ∑ ::∆:>0 1 ∆: + √ ∑ ::∆:>0 1 ∆: }) .
The regularizer 'C is formed as a sum of two convex functions,Ψ andΦ, described below. Predictions are computed by the algorithm by minimizing the cumulative estimated loss, regularized by 'C , over a truncated simplex Sγ
# , {? ∈ S# : ∀8, ?8 ≥ γ}. For loss estimation, the algorithm relies on the standard unbiased loss estimators (denoted by ̂̀C ) for the graph-feedback framework. Note however that while the feedback revealed to the algorithm at time step C includes the losses of all the neighbors of C in , it only makes use of the losses of the arms which belong to the same clique as C ; in other words, the algorithm may ignore some of the feedback it receives. The primary regularization function Ψ (whose weight increases with time) is the Tsallis-Shannon entropy Ψα defined in Section 3, given explicitly as
Ψ(?) = −α θ∑ :=1 √ ?(+: ) + θ∑ :=1 1√ ?(+: ) ∑ 8∈+: ?8 log ?8 ?(+: ) . (3)
The second time-invariant regularizer Φ is a log-barrier of the marginal clique probabilities,
Φ(?) = −β θ∑ :=1 log ?(+: ), (4)
and its goal is to further stabilize the algorithm. While the idea of augmenting the regularizer with a log-barrier function for promoting stability is not new, we note that a standard log-barrier of the form − ∑# 8=1 log ?8 would inevitably introduce an additive O(#) to the regret, which is suboptimal for our purposes. For that reason we use a different variant of a log-barrier function that operates on the marginal probabilities of the cliques.

heading: 5 Proof of Theorem 1
text: In this section we provide details on the proof of our main theorem. Our main step towards proving Theorem 1 is the following general regret bound for Algorithm 1. Theorem 2. Algorithm 1 attains the following pseudo-regret bound, regardless of the corruption level:
R) = Õ ©«θ + )∑ C=1 ∑ :≠:★
√ E[?C (+: )]
C + )∑ C=1
√ E[?C (+:★\8★)]
C + )∑ C=1
√ E[?+C (+:★\8★)]
C ª®¬, (5) where ?+C = arg min?∈Sγ
# {!̂C · ? + 'C (?)} for all C.
The focus of this section is on proving Theorem 2, but first we sketch how it implies our main result.
Proof of Theorem 1 (sketch; full proof in the full version of the paper [? ]) Theworst-case bound of Õ( √ θ)) follows immediately from the fact that ∑) C=1 ∑θ :=1 √ E[?C (+: )]/C ≤ 2 √ θ) via Jensen’s inequality, and similarly for the term including ?+C . The bound involving the corruption level requires a more delicate argument due to [27] that makes use of a self-bounding property of the pseudo-regret. In more detail, using Young’s inequality one has for all I > 0:
)∑ C=1 ∑ :≠:★
√ E[?C (+: )]
C ≤ )∑ C=1 ∑ :≠:★
( I
2C∆: + E[?C (+: )]∆: 2I
) ,
and a similar bound can be shown for the other two summations in Eq. (5). Combining these two gives after some simplification the pseudo-regret bound R) ≤ I + I−1 (R) + 2 ), for = O( ∑ ::∆:>0 log())/∆: ), which further simplifies to R) ≤ 2 + (I − 1) + 2 + I−1 . Optimizing the
bound with respect to I then gives R) ≤ 4 + 4 √ , which implies the bound we claimed.
We now set to prove Theorem 2. Our starting point is a general regret bound for FTRL. Applying a variation on the standard FTRL analysis (a similar analysis was used in [27, 13]) to the FTRL instance of Algorithm 1 gives the following regret bound. Lemma 3. For all ?γ ∈ Sγ
# the following holds:
)∑ C=1 ̂̀ C · (?C − ?γ) ≤ Φ(?γ) − Φ(?1) + )∑ C=1 ( 1 ηC − 1 ηC−1 ) (Ψ(?γ) −Ψ(?C )) (6)
+ 2 )∑ C=1 ηC ( ‖ ̂̀C − `C ,8★1‖∗C )2. (7)
Here ‖6‖∗C = √ 6T (∇2Ψ( ?̃C ))−16 is the dual local norm induced by Ψ at ?̃C for some intermediate point ?̃C ∈ [?C , ?+C ], where ?+C = arg min?∈Sγ # {!̂C · ? + 'C (?)}.
For the proof, see the full version of the paper [? ]. The bound above can be seen as a sum of a penalty term and a stability term (RHS of Eqs. (6) and (7) respectively). In order to prove Theorem 2 using this general regret bound, we separately bound the penalty and stability terms. The penalty term is
simpler to handle, and we only provide a brief discussion about how it is bounded. Bounding the stability term requires more work and constitutes the bulk of our analysis and our main contributions. We remark that the stability term contains dual norms of the loss estimators after introducing an additive shift of the form `C ,8★ to each arm. The purpose of such a shift is to exclude the contribution of the best arm 8★ from the regret bound, as can be seen in Eq. (5). More details regarding this shift and its purpose are given in the full version of the paper [? ]. Bounding the penalty term: We present a brief discussion about bounding the penalty term in Eq. (6). The penalty term is handled using bounds on the magnitude of the regularization over the domain Sγ
# .
Lemma 4. The penalty term (RHS of Eq. (6)) is upper bounded by
Õ ( θ +
)∑ C=1 ∑ :≠:★ √ ?C (+: ) C + )∑ C=1 √ ?C (+:★ \ 8★) C ) ,
for ?γ defined by ?γ 8 =
{ γ 8 ≠ 8★
1 − (# − 1)γ 8 = 8★ .
Proof (sketch; full proof in the full version of the paper [? ]) Essentially, we use the fact that the logbarrier component of the regularization is bounded by Õ(θ), and the Tsallis-Shannon component evaluated on the prediction ?C is bounded by Õ (∑θ :=1 √ ?C (+: ) ) , as it can be seen as a weighted sum of entropy functions (bounded in magnitude by log #), each of which corresponds to a clique +: with the respective weight being √ ?C (+: ). The non-trivial part in bounding the penalty term is in omitting the term corresponding to +:★ from the sum. This is accomplished by our specific choice of ?γ described above, as well as carefully bounding the (Shannon) entropy terms within each clique.
Bounding the stability term: The following lemma provides an upper bound on the stability term (RHS of Eq. (7)). This lemma crucially relies on strong convexity properties of the Tsallis-Shannon regularization (Eq. (3)). These properties allow us to obtain highly non-trivial upper bounds on the eigenvalues of the inverse Hessian of Ψ(·) over Sγ
# , and our ability to obtain such bounds turns out
to be critical for us to be able to successfully bound the stability term. Lemma 5. The following holds for all time steps C:
E [ (‖ ̂̀C − `C ,8★1‖∗C )2] = Õ(∑
:≠:★
√ E [ ?C (+: ) ] + √ E [ ?+C (+:★\8★) ] ) .
Proof (sketch; full proof in the full version of the paper [? ]) For simplicity, in this proof sketch we ignore the shift in the loss estimation and only bound E[(‖ ̂̀C ‖∗C )2] as it captures the main challenges and new ideas in the analysis. First, recall that the dual norm is formally defined with respect to the Hessian of Ψ(·) at some intermediate point ?̃C ∈ [?C , ?+C ]. We use the stability properties induced by the augmented log-barrier regularizer to replace ?̃C (+8) terms with ?C (+8) up to constant factors, and within each clique, bound the remaining terms involving ?̃8 by a sum of similar terms with the latter replaced by ?8 and ?+8 . Next, for bounding the relevant dual norm, we require a suitable upper bound on (∇2Ψ(?C ))−1. To this end, we employ Lemma 2, by which ∇2Ψ(?C ) is lower bounded by a diagonal matrix C , in which the 8’th diagonal entry corresponding to 8 ∈ +: is of the form ( 2 √ ?C (+: )?C ,8 )−1 .We now use this crucial fact to obtain the following upper bound on the stability term:
E [ (‖ ̂̀C ‖∗C )2] ≤ 2E[̂̀TC −1C ̂̀C ] = 2E[ θ∑
:=1
√ ?C (+: ) ∑ 8∈+: ?C ,8 ̂̀2C ,8] . We keep bounding this term by using the definition of the loss estimators ̂̀C to obtain E [ (‖ ̂̀C ‖∗C )2] ≤ 2E √ ?C (+ ( C )) ∑ 8∈+ ( C ) ?C ,8 ( `C ,8 ?C (+ ( C )) )2 ≤ 2E [ 1√ ?C (+ ( C )) ] = 2E [ θ∑ :=1 √ ?C (+: ) ] ,
where in the last line we used the fact that the probability that at time step C the algorithm chooses an arm from the clique +: is ?C (+: ). Note that this bound contains a term for ?C ,8★ which we would like to omit from the final bound. As we remarked before, the way we mitigate that is by considering the shifted loss estimators. This is explained in full in the full version of the paper [? ].
Concluding the proof: We can now sketch the proof of Theorem 2 using the bounds we obtained. A formal proof that also takes into account the poly-log factors can be found in the full version of the paper [? ].
Proof of Theorem 2 (sketch; full proof in the full version of the paper [? ]) We first remark that it suffices to bound the expected regret with respect to ?γ given by E [∑) C=1 `C · (?C − ?γ) ] , since
it can only be larger than the pseudo-regret by an additive constant, as shown in the full version of the paper [? ]. In addition, since the loss estimators ̂̀C are unbiased estimators of the loss vectors `C we conclude that it suffices to bound the regret with respect to the loss estimators, i.e. E [∑) C=1 ̂̀ C · (?C − ?γ) ] which is bounded by the sum of the expected penalty and stability terms (Eqs. (6) and (7)). Lemma 4 gives a bound on the penalty term of the form
Õ ( θ +
)∑ C=1 ∑ :≠:★
√ E[?C (+: )]
C + )∑ C=1
√ E[?C (+:★\8★)]
C
) ,
and Lemma 5 gives a bound on the stability term of the form
Õ ( )∑ C=1 ∑ :≠:★ √ E[?C (+: )] C + )∑ C=1 √ ?+C (+:★\8★) C ) .
Adding the two bounds and rearranging, we conclude the proof of Theorem 2.
Acknowledgements and Funding Disclosure This work has received support from the Israeli Science Foundation (ISF) grant no. 2549/19, from the Len Blavatnik and the Blavatnik Family foundation, and from the Yandex Initiative in Machine Learning.

Review summaries:
This paper studies a best-of-all-worlds algorithm for online learning with feedback graphs by incorporating a novel regularizer. The proposed algorithm simultaneously achieves near-optimal regret w.r.t. $T$ in the adversarial setting, stochastic setting and corrupted stochastic setting.

This paper introduces a novel bi-level regularization, namely the Tsallis-Shannon entropy, which is a combination of the two types of entropy with a linear shift. The paper proves the lower bound for the Hessian of the new regularization which is a diagonal matrix with positive entries, and thus convexity. By applying the regularization in the "Follow the Regularized Leader" framework, the paper derives an algorithm for online learning problems with undirected graph feedback, which is a generalization of the Multi-Armed Bandits (MAB) problem and Prediction with Expert Advice (PEA) problem. The algorithm achieves near optimal regret bounds for both bandits and full feedback problems with adversarially-corrupted stochastic loss setting. The paper also proves a bound for online learning problems with general undirected graph feedback, which is a big step towards a best-of-all-worlds guarantee for this setting.

The authors consider the best-of-both-worlds problem in bandits with graph feedback. Similar to [27], they consider stochastic bandits with C adversarial corruption that interpolates between the stochastic setting and the adversarial setting . As a result, they get $\text{polylog}( T)\sum_{k\in K}1/\Delta_{\min,k}$ regret in the stochastic setting and $\sqrt{|K|T}$ in the adversarial setting, where K is a clique cover of G. 

This paper considers the problem of online learning with feedback graphs. Feedback graphs tell which losses the learner gets to observe each time an action is chosen.  In particular, special cases include the bandit setting when the graph has no edges, and the full information setting when the feedback graph is a clique.  The authors derive bounds that scale in terms of the clique covering number of the graph. This clique covering number is the number of cliques (fully connected subgraphs) that are appearing in the graph. This number is useful because each time one arm is picked, the learner can observe the losses of all the other arms that are in the same clique.  Reasoning about the problem in terms of cliques is interesting because the exploration vs exploitation trade-off is not the same everywhere on the graph. If we consider each clique as one entity, we have a standard multi-armed bandits exploration vs exploitation trade-off. But then, when considering which action to play within the clique, this is a full information problem as we will get the feedback for all actions within the clique either way.  The authors then provide a FTRL algorithm that combines the Tsallis entropy (optimal for MAB) and the Shannon entropy (optimal for Full info).  They also mix in a log barrier regularizer to help with the stability of the algorithm.   The authors derive a single bound that covers simultaneously the adversarial, the stochastic, and the corrupted setting. That bound is near-optimal because of the consideration of the covering clique number rather than the independence number (which basically means that the edges in the feedback graph that are not part of a clique are not taken advantage of), and because the extra log barrier regularization term leads to extra log factors.