Cooperative Online Learning with Feedback Graphs
Authors: Nicolò Cesa-Bianchi
Tommaso Cesari
Riccardo Della Vecchia
Venue: Accepted by TMLR ()

Abstract: We study the interplay between communication and feedback in a cooperative online learning setting, where a network of communicating agents learn a common sequential decision-making task through a feedback graph. We bound the network regret in terms of the independence number of the strong product between the communication network and the feedback graph. Our analysis recovers as special cases many previously known bounds for cooperative online learning with expert or bandit feedback. We also prove an instance-based lower bound, demonstrating that our positive results are not improvable except in pathological cases. Experiments on synthetic data confirm our theoretical findings.

Published in Transactions on Machine Learning Research (06/2024)
Cooperative Online Learning with Feedback Graphs
Nicolò Cesa-Bianchi
nicolo. nicolb.cese-iianchhoonmnni......
Politecnico di Milono & Università degli Studi di Milano, Milano, Italy
Tommaso Cesari
Icesari@uolteweo.c
School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada
Riccardo Della Vecchia
ric. ric.della, ric.della.vecchiaa@@a www.hiiaanncillliccooooo com
Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL
Reviewed on OpenReview: https: openreview. net/ forum? id= PtNyIboDIG
Abstract
We study the interplay between communication and feedback in a cooperalive online learning setting, where a network of communicating agents learn a common sequential decision-making task through a feedback graph. We bound the network regret in terms of the independence number of the strong product between the communication network and the feedback graph. Our analysis recovers special cases many previously known bounds for cooperative online learning with expert bandit feedback. We also prove an instanco-based lower bound, demonstrating that our positive results are not improvable except in pathological cases. Experiments on synthetic data confirm our theoretical findings.
1 Introduction
Nonstochastic online learning with feedback graphs (Mannor and Shamir 2011) is a sequential decision decision-making setting in which, at each decision round, oblivious adversary assigns losses to all actions in finite set. What the learner observes after choosing action is determined by feedback graph defined on the action set. Unlike bandit feedback, where learner choosing action pays and observes the corresponding loss, in the feedback graph setting the learner also observes (without paying) the loss of all neighboring actions in the graph. Special cases of this setting are prediction with expert advice (where the graph is a clique) and multiarmed bandits (where the graph has no edges). The Exp3-SET algorithm (Alon el al.) 2017 is known to achieve a regret. scaling with the square root of the graph independence number, and this optimal up to a logarithmic factor in the number of actions. In recommendation systems, feedback graphs capture situations in which a user's reaction to recommended product allows the system to infer what reaction similar recommendations would have elicited in the same user, see Alon et al. (2017) for more examples.
Online learning has been also investigated in distributed settings, in which a network of cooperating agents solves a common task. At each time step, some agents become active, implying that they are requested to make predictions and pay the corresponding loss. Agents cooperate through a communication network by sharing the foodback obtained by the active agents. The time this information takes to travel the network is taken into account: message broadcast by an agent is received by another agent after delay equal to the shortest path between them. Regret in cooperative online learning has been previously investigated
only in the full-information setting (Cesa- Bianchi et al. 2020 Hsich et al. 2022 and in the bandit setting
(Cesa-Biaas Bianchi et al. 2019 Bar-On and Mansour 2019a).
In this work we provide a general solution to the problem of cooperative online learning with feedback graphs. In doing so, we generalize previous approaches and also clarify the impact on the regret of the mechanism governing the activation of agents. Under the assumption that agents are stochastically activated, our analysis captures the interplay between the communication graph (over the agents) and the feedback graph (over

---

Published in Transactions on Machine Learning Research (06/2024)
the actions), showing that the network regret scales with the independence number of the strong product between the communication network and the feedback graph.
More precisely, we design a distributed algorithm, ExP3-a², whose average regret RT/Q (where Q is the expected number of simultancously active agents) on any commmiictiin network and any feedback graph F (up to log factors)
RT
/
[a(N*BF) Q
+ 1 +1+11 T
(1)
where T is the horizon, is the diffusion radius (the maximum delay after which feedback is ignored), and a<N" & F) is the independence number of the strong product between the n-th power N of the communication network N and the feedback graph F. We also prove near-matching instance-dependens lower bound showing that, with the exception of pathological cases, for any pair of graphs (N, F), no algorithm run with an oblivious network interface can have regret smaller than / /a(NN" E F)/QTT.
Our results hold for any diffusion radius n, which serves as parameter to control the message complexity of the protocol. When n is equal to the diameter of the communication network, then every agent communicate with every other agent. Our protocol is reminiscent of the LOCAL communication model in distributed computing (Linial 1992 Suomela, 2013), where the output of a node depends only on the inputs of other nodes in a constanl-sizz neighborhood of it, and the goal is to derive algorithms whose rumning time is independent of the network size. Although our tasks have no completion time, in our model each node is dircctly influenced only by a constant-size neighborhood around it.
Let |A] and |K] be, respectively, the number of agents and actions. When Q |A| (all agents are always active) and F is the bandit graph (no edges), then a(N" & F) [K] ((V") and recover the bound ((((NN) / ||| + + T of Cesa-Bianchi al. (0019). When
and F the expert graph (clique),
then a(N" X F) = a(N) and we recover the bound / (a(N)/Q + 1)T of Cesa-Bianchi et al. (2020 Interestingly, if all agents were always active in Cesa- Bianchi et al. (2020), the graph topology would become irrelevant in the expert setting, resulting in a simplified regret. bound of ((vT), analogous to the case of a clique graph. This starkly contrasts with the bandit case of Cesa- Biasa-iianchii et al. (2019), where even when all agents are active simultaneously, the graph topology explicitly appears in the regret bound. Finally, in the non-cooperative case (N the bandit graph), we obtain v[A[a(F) TTQQ which, for |A] = and Q = 1, recovers the bound of Alon et al. (2017). Table 1 summarizes all known bounds (omitting log factors and setting, for simplicity, Q and n 0).
NN =
Any N
F clique (experts)
VT K
Freund and Schapire
1997
No(NTT
Disa-Bianchi et al. 2020
F no edges (bandits)
Auer et al.
2002
aNN)IKI
Cesa-Bianchi et al. (this work)
2019
Any F
Q(F)T
(Alon et al.
2017
Table 1: Known bounds in online learning with feedback graphs and cooperative online learning.
Our theory is developed under the so-called oblivious network interface; i.c., when agents are oblivious to the global network topology and run an instance of the same algorithm using a common initialization and a common learning rate for their updates. In this case, the stochastic activation assumption is necessary to not. incur linear regret RT = 2(T)) Cesa- Disa-Bianchi et al. (2020).
Our core and main technical contributions are presented in Lemma and Theorem I for the upper bound, and in Lemma 2 and Theorem 2 for the lower bound. Temma implies that the second moment of the loss estimates is dominated by the independence number of the strong product between the two graphs. The proof of this result generalizes the analysis of (Cesa-Bianchh et al. 2019 Lemma 3), identifying the strong product
This is reformulation of the bound originally proven by Resa-Blanchi et Material for proof.
2020 see Section C of the Supplementary
2

---

Published in Transactions on Machine Learning Research (06/2024)
the appropriate notion for capturing the combined effects of the communication and feedback graphs. In Theorem 1 we present a new analysis, in the distributed learning setting, of the "drift" term arising from the decomposition of network regret. This is obtained by combining Lemma I with a regret analysis technique
developed by Gyorgy and Joulani (2021) p for a single agent. The proof of the lower bound in Theorem 2 builds upon a new reduction to the setting of Lemma 2 that we prove in Appendix [ Lemma 2 contains a lower bound for a single-agent setting with a foodback graph and oblivious adversary where every time step is independently skipped with known and constant probability q. This reduction new and necessary, since it is not enough to claim that the average number of rounds played is qf and plug this in the lower bound for bandit with feedback graphs. In fact, one needs to build an explicit assignment of fi.... fr such that by averaging over the random subset of active time steps it is possible to prove the lower bound under the ionditions detailed in Lemma 2 synthetic data.
In Section G we corroborate our theoretical results with experiments on
2 Further related work
Adversarial losses. A setting closely related to ours investigated by Heersster et al. (2021). However, they assumee that the learner has full knowledge of the communication network a weighted undirected graph-ard provide bounds for harder notion of regret defined with respect. to an unknown smooth function mapping users to actions. Bar-On and Mansour (2019b) bound the individual regret (as opposed to our network regret) in the adversarial bandit setting of Cesa-Bianchi et al. (2019). in which all agents are active at all time steps. Their results, as well as the results of Cesa-Bianchi el al. (2019), have been extended to cooperative linear bandits by [to et al. (2020). Della Vecchia and Cesari (2021) study cooperative linear semibandits and focus on computational efficiency. Dubey et al. (2020a) show regret bounds for cooperative contextual bandits, where the reward obtained by an agent is a linear function of the contexts. Nakamura
et al. 2023) consider cooperative bandits in which agents dynamically join and leave the system.
Stochastic losses. Cooperative stochastic bandits are also an important topic in the online learning community. Kolla et al. (2018) study setting in which all agents are active at all time steps. In our model, this corresponds to the special case where the feedback graph is a bandit graph (no edges) and the activation probabilities q(v) are equal to 1 for all agents v. More importantly, however, they focus on a stochastic multi-armed bandit. problem. Hence, even restricting to the special cases of bandits with simultaneous activation, their algorithmic ideas cannot be directly applied to our adversarial setting. Other recently studied variants of cooperative stochastic bandits consider agent-specific restrictions on feedback (Chen et al. 2021 or access to arms (Yang el al.
2022
bounded communication Rubiio el al. 2019), corrupted heavy-tailed reward distributions (Dubey et al. 2020b), stochastic
communication (Madhushani et al.
2021
cooperation models (Chawla et al.
2020), strategic agents (Dubey and Pentland| (020), and Bayesian agents
Lalitha and Goldsmith| 2021). Multi-agent bandits have been also studied in federated learning settings
with star-shaped communication networks (He et al. 2022 Li and Wang 2022 in the presence of advessarial (as opposed to stochastic) agent activations. Finally, Liu et al. (2021) investigate a decentralized stochastic bandit network for matching markets.
3 Notation and setting
Our graphs are undirected and contain all self-loops. For any undirected graph G (V,E) and all m 2 0, we let (o(u,,) v) be the shortest-path distance (in G) between two vertices u, E V, Gm the m-th power of G (i.e., the graph with the same set of vertices V of G but in which two vertices u, v E V are adjacent if and only if 6,, u) I m), (G) the independence number of G (i.c., the largest cardinality of a subset of V such that óa(u, v) > 1 for all distinct u, v e I), and (+) the neighberhood {u E V :V:66ll dd(uu,) < 1} of a vertex v E V. To improve readability, we sometimes use the alternative notations am (G) for a(G") and N (v) for (w). Finally, for any two undirected graphs G = (V, F)) and G' = =V""F"), we denote by G G G" their strong product, defined as the graph with set of vertices V x V in which (v, v/) is adjacent to (u, u') if and only if (v, v') E (N) No' (u').
An instance of our problem is parameterized by:
3

---

Published in Transactions on Machine Learning Research (06/2024)
1. A communication network N (A, over set A of agents, and maximum communication delay 2 0, limiting the communication among agents.
2. A feedback graph F (K, Ep) over a set K of actions.
An activation probability ((v) > 0 for each agent v E A determining the subset of agents incurring losses on that round. Let Q = Eee ((v) be the expected cardinality of this subset.
4. A sequence L,, f2.2...... K - [0, 1] of losses, chosen by an oblivious adversary.
We assume the agents do not know N (see the oblivious network interface assumption introduced later). The only assumption make is that each agent knows the pairs (v, (c.) for all agents located at distance n or less
The distributed learning protocol works as follows. At each round / = .,, each agent o is activated with a probability q(v), independently of the past and of the other agents. Agents that are not activated at time remain inactive for that round. Let As be the subset of agents that are activated time Each Ar plays an action Ie(v) drawn according to its current probability distributtio pe(: ((, v), is charged the corresponding loss (L)(,, and then observes the losses ((), for any action i E NF (L()) Afterwards, each agent E A broadcasts to all agents the losses observed by v at time t together with its current distribution Pr(-, v); any agent u E NN, (v) receives this message at the end of round I. + (x(u, u). Note that broadcasting a message in the n-neighborhood of an agent can be done when knows only its 1-neighborhood. Indeed, because messages are time-stampes using a global clock, v drops any message received from an agent outside its n-neighborhood. On the other hand, may receive more than once the same message sent by some agent in its n-neighborhood. To avoid making a double update, agent extract from each received message the timestamp together with the index of the sender, and keep these pairs stored for n time steps.
N (v) in its n-neighborhood feedback message containing all
Each loss observed by an agent v (either directly or in feedback message) is used to update its local distribution u)) To simplify the analysis, updates are postponed, i.e., updates made at time involve only losses generated at time { - n - This means that agents may have to store feedback messages for up to n n+1 time steps before using them perform updates.
The online protocol can be written follows.
At each round t 1,2,...
1. Each agent is independently activated with probability q(v);
2. Each active agent draws action Le(v) from K according to its current distribution
pe(s,u), is charged the corresponding loss ls (Ix(w)), and observes the set of losses Lz(2) =
{ (()) : E NT (I(e)))
3. Each agent v broadcasts to all agents E (N) the feedback message
(t, v, (v),,, pe(-v)). where (v(v) Ø if & Ar
4. Each agent v receives the feedback message (1 (8-8, u, Lt fr-s(u), (t-s(;,)) from each agent u)= s, for all E [n]
u such that (v, uv
Similarly to CisncBi et al. (2019), we assume the feedback message sent out by an agent at time contains the distribution v) used by the agent to draw actions at time 1. This is needed to compute the importance iepigtence-weightedd estimates of the losses, be(i, v), see (3)
The goal is to minimize the network regret
Ry max E
ΣV ((((v))
Σ (111(())) 1=1
(2)
VEAA:
We assume without loss of generality that q(e) 0 for all agents E A. The definition of regret and all subsequent results could be restated equivalently in terms of the restriction N' (A',E', (E of the communication network N, where A' (u C A q(v) 0} and for all u, v A', v) Ey if and only if (u, Exx- 3This assumption can be relaxed straightforwardly by assuming that each agent e only knows q(v). which then be broadcast the neighboordood as the process unfolds.
4

---

Published in Transactions on Machine Learning Research (06/2024)
where the expectation is taken with respect to the activations of the agents and the internal randomization of the strategies drawing the actions (v). Since the active agents A are chosen ii.d from a fixed distribution, we also consider the average regret
Ry
E
Σ
T
Σ VEAL
(((e(o))
-min
T Σ 4(1) PEK
Q
where Q = [[]]] > for all
In our sctting, each agent locally runs an instance of the same online algorithm. We do not require any ad-hoe interface between each local instance and the rest of the network. In particular, make the following assumption Cesa-Biianchi et al. 2020).
Assumption 1 (Oblivious network interface). An online algorithm ALG is run with an oblivious network interface if:
1. each agent v locally runs local instance of ALG; all local instances use the same inilialization and the same strategy for updating the learning rales; all local instances make updates while being oblivious to whether or not their host node t was active and when.
This assumption implies that each agent's instance is oblivious to both the network topology and the location of the agent the network. Its purpose is to show that communication improves learning rates even without any network-specific tuning. In concrete applications, one might use ad-hoc variants that rely on the knowledge of the task at hand, and decrease the regret even further.
4 Upper bound
In this section, we introduce ExP3-o2 (Algorithm) D an extension of the EXP3-CooP algorithm by Cesa Bianchi et al. (2019) and analyze its network regret when run with oblivious network interface.
Algorithm 1: ExP3-a² (Locally run by each agent A)
input: learning rates (2), for t == 1,
do
if v active in this round, draw (v) from K uniformly random for t n 2 do
if is active in this round, draw (v) from K according to pe(. v) in
An instance of Exp3-a² is locally run by each agent e A. The algorithm parameterized by (variable) learning rates 17. (v), (p),,.... which, in principle, can be arbitrary (measurable) functions of the history. In all rounds in which the agent active, draws action I+(v) according to distribution pe(. v). For the first n + 1 rounds v)(:,v) is the uniform distribution over K. During all remaining time steps t, the algorithm computes exponential weights using all the available feedback generated up to (and including) round L - n - 1. More precisely, for any action i K,
Pr(i, v) = ui(iiu)/llu((
wr(i, v) exp(-n(vv) (
(,(,.) v) (L.
(3)
B,(i,)) v) -I(Bu E NAY (v) u IN (f(()))
b.(i,)) IIeNNY
q(u) Ejeny (.()
The event (,(,,)) 2) indicates whether an agent in the n-ncighborhood of played at time an action in the 1-neighborhood of i. If (2, v) occurs, then agent can use (i, u) to update the local estimate for the
5

---

Published in Transactions on Machine Learning Research (06/2024)
cumulative loss of i. Note that (i u) proper importance-weightee estimates, as Ez-n (e, e)] = (1)
for all E A, i E K, and 8> The notation I denotes conditioning with respect to any randomness in rounds 1,..., n - Note also that when ((u) = 1 for all u E A and F is the edgeless graph, the probabilitics (e( u) in 3 correspond to those computed by EXP3-COOP (Cesa-Biancha et al. 2019
Before analyzing our cooperative implementation of ExP3-a", we present a key graph-theoretic result. that helps characterize the joint impact on the regret of the communication network and the feedback graph. Our new result relates the variance of the estimates of eq. 33 to the structure of the communication graph given by the strong product of N and F. Lemma 1. Let N = (A, EN) and F = (K, Er) be any two graphs, 2 O, (q(e)) DEA a set of numbers in (0, 11, Q = Evea (()), and (p(t,v))
set of numbers in (0, 1] such that EieR p(i, v) for all
v E A. Then,
(())p(ivv)
ΣΣ 1- II (u) q(u) () p(i,u) S -- (a(N" +Q) VEA IEK
Proof. Let (wo(i, (1o))KX where w(i, v) q(v)p(i, v), and for all (i, K x A set W(i,t) EUSHENN u(j.u). Define also, for all (c(i, GiuJERXA [0, and (
Soli, =1
II
1
Σ c(j.u) u)
uEA (v)
JENT (
Then we can write the left-hand side of the statement of the lemma as
w(i,v)
w(i,v)
w(i, v) fw (2,
Σ
Σ
(x fw((,u)
(u)eKxA:W((.)d (i,
(t.))KKA:: ((.0221
(1)
(1I)
and proceed by upper bounding the two terms (I) and (II) separately. For the first term (1), using the incquality S e= (for all x E R) with x w(j. u), we can write, for any (i,v) E Kx A,
fo (1, 2 exp
Σ Σ NENIN (E)
u) (el--exx-W(ii)
Now, since in (I) only summing over vi, E K A such that W(i,v) < 1,
the inequality
- e (1 (1-e-1)a x) (for all E [0, with x = W(i, v), obtaining (1, u) 2 (1 - ----e-1W6 v), and in turn
w(1 v)
w(i,v) v a NNa MF
(I) < Σ
E
(5,))KXA W(..))) (1 (1-e-1)((ip))
1 e
W(i,v) (x
1 1-e-1
where in the last step we used a known graph-theoretic result see Lemma 3 in the Supplementary Material. For the second term (IT): for all v E A, let r(v) be the cardinality of N (v). Then, for any (i,v) E K A such that Wi, 1,
1 fa v) S max
1 foli, : CE [0, KIIMI
Σ
di.u)21
(6)
<lj.u) = }
II
Σ
d(.u)) : c (0,
ΣΣ
= max
NE.N22 (v)
(E)
(c)
< max
(u)C CC A
Σ
((u)=1
WEAV (v)
MENN (v)

---

Published in Transactions on Machine Learning Research (06/2024)
II
(1- C(u) (0,0,
Σ (1 - (1- (e)
max
NEN (1)
r(b)
Se-1
r(u)
where the first equality follows from the definition of fe(i. and the monotonicity of x ト 1 z, the second-to-last inequality is implied by the AM-GM inequality (Lemma and the last comes from r(o) 2 1 (being E EN (v)). Hence
w(i.v)
w(1,2)
(
E ((.))K ((.6)21
Σ
T-e-1
(1,))KX W(h0)21
Q
ΣΣ u(i,u)
I-e-1 Σ q())
p(i,v)
1 1- ----1
REK
BEA
EKK
For a slightly stronger version of this result, see Lemma in the Supplementary Material. By virtue of
Lemma I we can now show the main result of this section.
Theorem 1. If each agent A uses adaptive learning rates equal to ne(v) 0 for t n + 1, n((v)
be(t.v) for n + 1, the average nelwork regret of ExP3-a2 playing with an oblivious network interface can be bounded as
V /log(K)/E (v(v) with Xx(v) - n + Σiek p=li,e)
Pr σ
a (N"M T
log(K)) n++ 1
Q
Proof. Let i* argmin,ex E (())(()) where the expectation is with respect to the random sequence A S A of agent activations. We write the network regret Rr weighted sum of single agent regrets (r(e):
Rr = (r( E {())E HEA
ΣIn (il, -
201000)
DEA
where the expectation now only with respect to the random draw of the agents' actions, and is separated from the activation probability q(v). Fix any agent A. Exp3-a² plays uniformly for the first n rounds, and each agent, therefore, incurs a lincar regret in this phase. For > 1 borrow docomposition technique from (Gyorgy and Joulani 2021): for any sequence (po(..)) e2at1 of distributions over K, the above expectation can be written as
E Σ (... (1- (1- (t+1(i,0)) 2=n-
T
)
E E Lta++2ik
+
Σ
(5)
pe(1, v)
LiEK
Take now pe(.,0) v) as the (full-information) exponential-weights updates with non non-increasing step-sizes ()-1(v) for the sequence losses ((.,.)) v). That is, (1 v) the uniform distribution over K, and for any time step and action E K, Pet1 (i) r) = (i,1 e)/ [[ e)]l, where ( v) exp(-né Ei ((, With this choice, the first term in 5 is the "look-ahead" regret for the iterates Pt+1(.. (which depend on Ee(s,)) at time f), while the sccond one mcasures the drift of pe(., v) from pe+1(..u)
Using argument from (Joulani et al. 2020 Theorem 3) we deterministically bound the first term in 5
In |K|
Σ
Σ l(li, v) E,(1", v) s ())
(6)
knt2ie
We use
Joulani et al. 2020
Theorem 3) with = 0 for all & [T], ro = (1/wo(v) Σ. In(p)) re(p) = (1/m(v))
(v)) E, Pi In(p:) for all [T.. and dropping the Bregman-divergence due the convexity of rt-
7

---

Published in Transactions on Machine Learning Research (06/2024)
The subtle part is now to control the second term in 5 To do so, fix any >> + 1. Note that for all i K,
we(i,o)= exp (nc(v) レ-R-1
E((h.u)
exp (T((v) Σ (((())) ((+1(i,
(using (.(i 2 00 for all s, v), which in turn, using the inequality ex + x (for all RR, yields
(i,
W++1 (i, exp (-m((0) Ex=e-a (s(1, 21 m((()) (
Pr(i, v)
(i,
Thus, we upper bound the second expectation in by
[-1 E E(l00) smt-n
Σ E (o(U) m(0)) KEK
+
E Σ GEK
= (v) + di 2 (o).
(7)
We study the two terms Di (v) and a1 (c) separately. Let then He - Hv) be the o-algebra generated by the activations of agents and the actions drawn by them at times 1...., 1, and let also indicate E, = E Mi).
(1)
First, we bound 9i ( (v) in using the fact that Pe(-, v), ne(v) and b.( (for all E (t ...... ......... +}) are determined by the randomness in steps 1,...,t- n 1. We the tower rule and take the conditional expectation inside since all quantities apart from Br Bi-n(i, .., ()(i,v) are determined given Hy-ns we rewrite the expression as
G(I) (((1 ==--n be v) b,(
91 (v)
E Σ (())p((( KEK
Σ
B. B [Beli,
Conditional on Hi-n the Bernoulli random variables (, v), and B, v) for independent. This follows because the feedbacks at time missing at time & for s= ny..., and therefore, from the independent activation of agents and the fact that the only other source of randomness is the independent internal randomization of the algorithm, they are independent random variables, implying
n. n..... are
E,-n (i(i, v)] v)).(i)).
for == n, n,..., t- 1. Using (()),,(1)) < 1, we then get
_ (v) E Σ (()))i(i, (ln(())).
With similar argument, we also get
Σ (c(v) peli, Pe)
(v) E
E.-n ((((io)
< E
be(i,))
KEE
Finally, the single agent regret for each agent A is bounded by
In
Poli,e) w) be v)
(v) S
E
+ (n + 1) +
Σ E ((()) n
(v))
(=++2
EE
In | (u)
= E
+ (n + 1) +
E [(m(v)X((()))
(=
where, in the second line, we defined X((v) = I[( > n +1 n+ Σiek peli.e]
be(s.v)
8

---

Published in Transactions on Machine Learning Research (06/2024)
We now take ne(1)) (v)) = Vlog(K) / (u),), and we use a standard inequality stating that for any at > 0,
E a/ VE' as S 2 Ei= as. Applying this inequality for os equal to X²(e) we have
T
T
log( () {)((vv)
RT(()= S (n + 1) +E
log log(K) Ex,(1)
+E
E (1(
s=1
S (n + 1)+ +3E
log(K) K) Σ (z(
Multiplying by q(v), summing over agents v E A we obtain
Σ q(v)
T
Pc (1) by (i, v)
RT= = Σ [(( = Q(n +)++1)++300 3Q
Σ
log(K)
n
iEK
log(K)
peli, beli, v)
S 0Q(n +0(n+1) 1)+++)+33
n + Σ
VEK
a (N" 8 F)
S Q(n + +)+ +3 (og(K)
n n 1+
Q Q(-e-1)) T,
where the first inequality follows from Jensen's inequality and the second from Lemma !
Note that in Theorem 1 every agent tumes the learning rate (e(v) using available information at time t. This allows the network regret to adapt to the unknown parameters of the problems such as the time horizon T, the independence number (N X F), and the total activation mass Q on A. This approach improves over the doubling trick approach used in
et al. (2019) since we do not need to restart the algorithm.
5 Lower bound
In this section, we prove that not only the upper bound in Theorem is optimal in minimaz sense-ias -ic., that it is attained for some pairs of graphs (N, F) but it is also tight in inslance-dependent sense, for all pairs of graphs belonging to a large class.
Definition 1. Let & be the class of all pairs of gruphs (N, such that a(N B) a(N)a(F).
E & are known in the graph theory literature: see, e.g., Hales 1973 Section 3). Acín et al. (2017] Theorem 6), and Rosenfeld 1967 Theorem 2). To the best of our knowledge, a full characterization of &f is still a challenging open problem in graph theory that goes beyond the scope of this paper. It is easy to verify that (either N or) F a clique or an edgeless graph, then F) Eg. S. We remark that these instances cover in particular both the bandit and the full-info case that were previously only studied individually, and analyzed with ad hoc techniques. For some further discussion on 8, we refer the interest reader to Appendix B.I.
Many sufficient conditions guaranteeing that (N, F
The proof of the lower bound in Theorem 2 exploits reduction to a setting we introduce in Lemma 2 In this lemma, we state that in a single-agent setting with a feedback graph, if each one of T time steps is independently skipped with a known and constant probability μ, the learner's regret Skipped rounds do not count towards regret. More precisely, at each round t, there is an independent Bernoulli random variable A, with mean p. A, = O, the learner not required to make any predictions, incurs loss, and receives no feedback information. The (single-agent) regret of possibly randomized algorithm ALG a sequence (4)) of losses is defined as (H, ALG, max RE (n, ALG, Ł, where
((va(F))u))
R
=
Σ
-10))4(()44A 11
9

---

Published in Transactions on Machine Learning Research (06/2024)
and I is the random variable denoting the action played by the learner at time t that only depends on the rounds E (1,...,4) where A, = 1. The expectation in RT is computed over both 1 and A, for & E (T). Note that it is not true, in general, that RTT (p, ALG, ( E |
Lemma 2. For any feedback graph F, for any (possibly randomized) online learning algorithm ALG, for any J > O, and for any T max m0.0000004 a(F)s, }. is each round L E (T' is independently skipped with probability p, then
inf sup R8T (M, ALC, 2 Vo(F)NT
The proof of this lemma can be found in Appendix Now let ALG be possibly randomized online algorithm. Let (g, ALG, be the network regret (2) incurred by ALG run with oblivious network interface, losses
L = -(e)sE and activation probabilities q = (q(v))eEA- We can now prove our lower bound.
Theorem 2. For any choice of any paár of graphs (N", $, and all Q E (N)), we have that for
T 2 max (0.0064 - a(F)), (NN)a(//))))))) the following holds
inf sup Rr (g,q, 2 (Q((NTBF)T E,
where the infimum is over all randomized online algorithms and the supremum is over all assignments of losses (4))et)) and aclivation probabilities (q(v)) such that Q EveA (v)).
n, F) and (0, (nV) as in the statement of the theorem. Then (N F) On (N))(F)) Let I be set of on (N) agents such that (u, v) for all u, u E I. Define the activation probabilities q(v) Q/am (N) < 1 for all E I and ((v) 0 for all E ANI. By construction, no communication occurs among agents in I. Furthermore, each agent in I is activated independently with the same probability q(v)= = P(v E A.) = (N).
Proof. Fix any (N,n,F
Therefore, we can use Lemma 2 to show that there exists a sequence losses that simultaneously lower bounds the regret of all agents. Indeed, for all T 2 max max fox0000004 (N))) we have
inf sup Rr ALC, inf sup max ADG
Σ
E
- -(()) 1LU Ar)
ALG é VEK
inf sup max AUG
(Q/an, ALG,
E KEK
WEI.
= ox)(N) inf sup ReP (Q/aa((),, ALG, ALC
Lemma with P Q/ax
[(a((F)a,,N)) (N)
where (e) is the random variable denoting the arm pulled at time by the instance of ALG run by agent and Lemma invoked on [Z] ar, (N) instances of ALG with feedback graph G F and independent.
randomization.
7
6 Experiments
To empirically appreciate the impact of cooperation, we run a number of experiments on synthetic data. Our code available at Della Vecchia (2024).
For each choice of N and F, we compare Exp3-o² run on N and F against a bascline which runs ExP3-a on N' and F, where N' an edgeless communication graph. Hence, the bascline runs A independent instances the same feedback graph.
10

---

Published in Transactions on Machine Learning Research (06/2024)
In experiments, we fix the time horizon (T 10,000), the number of arms (K 20), and the number of agents (A = 20). We also set the delay dx to 1. The loss of each action is Bernoulli random variable of parameter 1/2, except for the optimal action which has parameter 1/2 v /K/r. The activation probabilities g(o) are the same for all agents e E A, and range in the set {0.05, 0.5, 1}. This implies that Q {1, 10, 20). The leedback graph F and the communication graph N are Erdös Rényi random graphs parameters PN, pr 0.8). For each choice of the parameters, the same realization of N and was kept fixed in all the experiments, see Figure !
(a)
(b)
(c)
(d)
Figure 1: The random instances of (leftmost graphs) and F (rightmost, graphs) used our experiments. The sparse graphs are Erdös Rényi of parameter 0.2, the dense graphs are Erdös Rényi of parameter 0.8.
In each experiment, ExP3-a² and our baseline Hence, the only stochasticity left is the internal randomization of the algorithms. Our results are averages of 20 repetitions of each experiment with respect to this randomization.
the same realization of losses and agent activations.
0.05
PN
PF
2x
Indep.
Ex13-n Ex03-o2/Indep.
PN
PF
Ex
Indep
Exp3-n /Indep.
0.8
0.8
31.7
110.1
29%
0.8
0.8
18.3
47.2
39%
0.8
0.2
94.4
130.5
72%
0.8
0.2
34.1
101.1
34%
0.2
0.8
59.5
110.1
54%
0.2
0.8
22.5
47.2
48%
0.2
0.2
103
130.5
79%
0.2
0.2
77.7
101.1
77%
(a) Results for q = 0.05
(b) Results for q =
q ==
PN
PF
ExP3-a
Indep.
Exr3-a Exr3-a//Indop.
0.8
0.8
18.7
22.6
83%
0.8
0.2
23.2
84.7
27%
0.2
0.8
18.8
22.6
83%
0.2
0.2
41.3
84.7
49%
(c) Results for g
Table Table of the performance of ExP3-a² and independent single agent optimal algorithms with feedback graphs. We summarise the performance in terms of total cumulative regret Rt/Q after 1000 rounds for the two algorithms. The last column of each table is the percentage of the cumulative regret of ExP3-a² with respect to the independent optimal algorithms.
Figure 2 and Table 2 summarize the results of our experiments in terms of the average regret RT/Q. See Appendix D for the actual learning curves. Recall that our upper bound scales with the quantity Vo(N x Q.
11

---

Published in Transactions on Machine Learning Research (06/2024)
140
140
120
120
120
100
100
100
Rt/
40
40
30
0.8
0.8
0.8
0.2
0.2
02
195
0.8
Figure 2: Average regret of ExP3-a² (blue dots) against the baseline (red dots). The X-axis and the Y-axis correspond to the parameters pr and of the Erdös-Rényí graph, the Z-axis is the average regret RT/Q. The three plots correspond to increasing values (from left to right) of activation probability: 0.05 (leftmost plot), = 0.5 (central plot), = (rightmost plot).
than the baseline (red dots). This is consistent. with the fact that N for the baseline is the edgeless graph, implying that a(N X F) Aa(F).
Note that algorithm (blue dots) is
Consistently with (1), the average performance gets worse when Q - 1
By construction, the performance of the baseline each plot remains constant when pN varies in {0.2, 0.8}. On the other hand, our algorithm is worse when N is sparse because a(N M P)) increases.
The performance of both algorithms worse when sparse because, once more, a(N X F) increases.
7 Conclusions
In this work, nearly characterize the minimax regret in cooperative online learning with feedback graphs, showing that the dependence on (N X F) in our bounds is tight in all but few, pathological instances. In bandit setting, when all agents are active at all time steps, previous works showed that communication speeds up learning by reducing the variance of loss estimates. On the opposite end of the spectrum, in full-information settings, updating non-active agents was shown to improve regret. These results left open the question of which updates would help in intermediate settings and why. In this paper, we prove that both types of updates help local learners across the entire seperts-bandiin spectrum (Theorem []. We stress that this strategy crucially depends the stochasticity of the actívations. Indeed, Cesa-Bianchi et al. (2020) disproved the naive intuition that more information automatically translates into better bounds, showing how using all the available data can lead to linear regret in the case of adversarial activations with oblivious network interface.
As we only considered undirected feedback graphs, their extension to the directed case remains open. Using the terminology introduced by Alon al. (2015) for directed graphs, we conjecture our main result (Theorem remains true in the strongly observable case. In the weakly observable case, the scaling parameter of the single-agent regret is a graph-theoretic quantity different from the independence number, and the minimax rale becomes 72/3 In this case, we ignore the best possible scaling parameter for the network regret.
Finally, we leave open the problem of characterizing the minimax regret with stochastic activations but no oblivious network interface. We conjecture that the lower bound Theorem 2 could be extended to the case in which the algorithin run by each agent are not necessarily instances the same online algorithm. In other words, we conjecture that the oblivious network interface is sufficient to achieve minimax optimality.
Also the baseline, whose agents learn in isolation, gets worse when Q decreases. Indeed, when Q = 1 agents get only to play T/|A| time steps each, and together achieve a network regret Ry that scales with / /IA]((F). as predicted by our analysis.
12

---

Published in Transactions on Machine Learning Research (06/2024)
Acknowledgments
NCB is partially supported by the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), funded by the Nex program within the PNRR scheme, the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEUU program within the PNRR-PE-AI scheme, the EU Horizon HL4-2022-HUMAN-02 rescarch and innovation action under grant agreement 1011 10237, project ELIAS (European Lighthouse of AI for Sustainablitty. 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 RGPINN-023-0366 (Discovery Grants Program) and DGECR2023-00208 (Discovery Grants Program, DGECR Discovery Launch Supplement). RDV is thankful for the funding received by the CHIST-ERA Project Causal eXplainations in Reinforcement. Learning CausalXRL.
References
Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. Advances in Neural Information Processing Systems, 24, 2011.
Noga Alon, Nicolo Besa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Non- stochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6): 1785-1826, 2017.
Nicolò
Tommaso Cesari, and Claire Monteleoni. Cooperative online learning: Keeping your neighbors updatod. In Algorithmic Learning Theory, pages 234-250. PMLR, 2020.
Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. Journal of Muchine Learning Research, 23(78): 1-49, 2022.
Nicolò Bosa-Biacchi, Claudio Gentile, and Yishay Mansour. Delay and cooperation in nonstochastic bandits. Journal of Machine Learning Research, 20(17):1-38, 2019.
Yogev Bar-On and Yishay Mansour, Individual regret in cooperative nonstochastic multi-armed bandits. Advances Neural Information Processing Systems, 32, 2019a.
Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on compuling, 21(1):193 201, 1992.
Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):1-40, 2013.
Yoav Freund and Robert E Schapire. A decision-theoreet generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48 77, 2002.
Andras Gyorgy and Pooria Joulani. Adapting to delays and data in adversarial multi-armed bandits. In International Conference on Machine Learning, pages 3988 3997. PMLR, 2021.
Mark Herbster, Stephen Pasteris, Fabio Vitale, and Massimiliano Pontil. A gang of adversarial bandits. Advances in Neural Information Processing Systems, 34, 2021.
Yogev Bar-On and Yishay Mansour. Individual regret in cooperative nonstochastic multi-armed bandits. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-Ichi Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. Advances in Neural Information Processing Systems, 33:4872 4883, 2020.
Riccardo Della Vecchia and Tommaso Cesari. An efficient algorithm for cooperative semi-bandits. Algorithmic Learning Theory, pages 529 552. PMIRR, 2021.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Abhimanyu Dubey et al. Kernel methods for cooperative multi-agent contextual bandits. In International Conference on Machine Learnöng, pages
PMLR, 2020a.
Tomoki Nakamura, Naoki Hayashi, and Masahiro Imuiguchi. Cooperative learning for adversarial multi-armed bandit on open multi-agent systems. IEFE Control Systems Letters, 2023.
Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan. Collaborative learning of stochastic bandits over a social network. IEEE/ACM Transactions on Networking, 26( 26(4):1782 1795, 2018
Yu-Zhen Janice Chen, Stephen Pasteris, Mohammad Hajiesmaili, John Lui, Don Towsley, et al. Cooperative stochastic bandits with asynchronous agents and constrained feedback. Advances in Neural Information Processing Systems, 34, 2021.
Lin Yang, Yu-zhen Janice Chen, Mohammad Hajiesmaili, John Lui, and Don Towsley. Distributed bandits with heterogeneous agents. Xiw preprint or arXiv:2201.0088 2022.
David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 32, 2019.
Cdari Madhushani, Abhimanyu Dubey, Naomi Leonard, and Alex Pentland. One more step towards reality: Cooperative bandits with imperfect communication. Advances in Neural Information Processing Systems, 34, 2021.
Abhimanyu Dubey et al. Cooperative multi-agent bandits with heavy tails. In International Conference on Machine Learning, pages 2730-2739. PMLR, 2020b.
Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. The gossiping insert- eliminate algorithm for multi-agent bandits. In International Conference Artificial Intelligence and Statistics, pages 3471-3481. PMLR, 2020.
Abhimanyu Dubey and Alex Pentland. Private and byzantine-prod cooperative decision-making. In AAMAS, pages 357 365, 2020.
Anusha Lalitha and Andrea Goldsmith. Bayesian algorithms for decentralized stochastic bandits. IEEE Journal on Selected Areas in Information Theory, 2(2):564-583, 2021.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in neural information processing systems, 35: 4762-4775, 2022.
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference Artificial Intelligence and Statistics, pages 6529 6553. PMLR, 2022.
Lydia T Liu, Fong Ruan, Horia Mania, and Michael Jordan. Bandit learning decentralized matching markets. The Journal of Machine Learning Research, 22(1):9612 9645, 2021.
Pooria Joulani, András György, and Csaba Szepesvári. modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 008:108-138, 2020.
R. Stanton Hales. Numerical invariants and the strong product of graphs. Journal of Combinatorial Theory, Series B, 15(2):146-155, 1973.
Antonio Acín, Runyao Duan, David E Roberson, Ana Belén Sainz, and Andreas Winter. A property of the Lovász number and duality relations between graph parameters. Discrete Applied Mathematics, 216: 489-501, 2017.
Moshe Rosenfeld. On a problem of C.E. Shannon in graph theory. Proceedings of the American Mathematical Sociely, 18(2):315 319,, 1967.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Riccardo Della Vecchia. Cooperative online learning with feedback graphs. riccarodtt/CDD--eerming 2024.
https://github..com
Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference Learning Theory, pages 23 35. PMT.R, 2015.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2) 194, 2012.
Francesco Orabona, Koby Crammer, and Nicolò Cesa-Bianchi. A generalized online mirror descent with applications to classification and regression. Machine Learning, 99(3):411 435, 2015.
15

---

a(FF)iz (imm(..)) (m)) We find that the maximum of Published in Transactions on Machine Learning Research (06/2024)
A Proof of Lemma 2
Lemma 2 For any feedback graph F, for any (possibly randomized) online learning algorithm ALG, for any μ > O, and for any T 2 max a(F)², ( } if each round i E [T') is independently skipped with probability μ,, then
inf sup HT (H, ALG, 8) 2 Va(F)pTT
Proof. Let T be the (random) set of times {L E [7) A, = and let TI 72 <.... < 777 the (random) elements of T in increasing order. Fix (possibly randomized) online learning algorithm ALG and sequence = (4)) of losses. For any random variable J (later, J and the corresponding "hard" instance will be those used in the lower bound for online learning with feedback graphs: (Alon et al., 2017 Theorem 5)). Let
N₂ = A1 + +..................... A-1 be the number of rounds actually played up time Then
- 11) 1=1
RI(H, ALG, E) = max E
max E VE[K]
Σ (1.) +EIITTI
KE[K]
2 E
(T)
+E[ITI
ΣE TOC
E
Σ SE[IT]
(c. (r, TT= = To, Tol = n PTT TTo Tol = =n)
WE(T)
To
Then, we recognize that the conditional expectation in the previous formula is the expected regret for single-agent online learning with feodback graph. Therefore, from AAln et al. 2017 Theorem 5) we get that, letting C = (8/100)² and for all T 2 Cia(F)3,
inf sup Rr (u, ALG, AIG {
Σ
Σ
28 o(F)
P PTT Top Tol n)
nE(T]
TaC[T]
17o|=n
Σ
8n
28
n
P ((T) =))
2
(FFF)
nE[T]
Σ nE/T
n
fBin(p.2)(nt))
En
2
V
a(F)
where fRin(Y,T) is the p.m.f. of Binomial random variable with parameters p. T. We want E" (p, that maximizes that expression. Therefore, by defining g(E) = as + be as the following quadratic polynomial in e
g(E) = Σ
EN
1
23
n2 a(FF)
) f (n)
2
nE(T]
33/22
Σ
2 JBm(H.
2 Σ
nE(T]
mE(T]
where a = Enery ( (Bint))r))))) and b = -2 EmE(T] g achieved in 25: which gives the optimal value
m3/22
(p, T) Ener ( ((in(,.7y()))
E E
a(F)17z / Binpp, (m)
m3/
16

---

Published in Transactions on Machine Learning Research (06/2024)
and the function 9 evaluated at the optimal value is equal to g" 46 ie.,
a²
g" = (p) = g EnEwn (2 (Biiuu. (n))
Va(F) (iBentuum)
m8/2 4 ((FF)iz (r)(t
8
Eme(r) (m3/2 3
Therefore, we can lower bound the regrel with 9 and obtain
(Enetry NSBialu, (n))
inf sup (M, Va(F) ALG {
va(F)pit
(μT)) Σ Emern (m3/2 fBlu(u (m))
8
Emeln (m3/2 (Bin(H.))
Va(F)uT
(uT))/2
8
EmElZ (m3/2 [Bin(u.7)
where in the first equality we substituted the expected value of binomial distribution of parameter j.. We now want to prove the existence of constant such that, for every ps 0 and every T 2 ns
(uT))/22
Emery (m0 (Bm(H,)) ce
Emerry (m3/2 (Bin(,,T)(m)) 2 cc, or equivalently
(uT)33/2
We split the sum over m E [T] into two blocks, the first for S S c2l and the second for calNT] <
+1)] and with ej > 0:
m < T for a constant C2 =
aT [.T]]
73/2
+ +
2T
Eme(ri (m3/3 fyinCu, (2T))3/2
Eell (pT)) [
(m3/2 BBm Ty (m))
+ E Emscylary (m frintu.) (WT)a/2
(8)
(μT))//2
The idea is to choose the split point 02 | so that we can upper bound the tail mass using Hoeffding's inequality. Hoeffding's incquality yields the simple bound FRim(H.T)) (m) I cxp (-2T (p ))²) and together with symmetry properties of the binomial distribution 1 - 1 = F Bi (.aul1 (T m) we obtain a bound on the upper tail. This contribution compensates exactly the term 3 left at the denominator for T Z 1/2, lcaving just the constant Ci:
EmzozleT (m²/2 FBi 2T -27((11)) (11(011)--2-t)prrr1111 (uiT)3/2
T3/2
(nT)33/2
(u(cs
+)+))
13/2
C1
(1T))3/2
S 61
For the first term in Equation
88 we upper bound the lower tail simply by one:
ea a
3/2
(Lm))..)(m))
S c22 (alLT] (m) S c2luT]
We conclude by proving that the first term in Equation is bounded by constant. If we take m S 22210T we obtain for T> 2/μu and e₁ 2
EaaTTT (m3 frin(p.Ty(m)) (m))
(c2 LeTT) ( 3/2
<
(1TT)3/2
(1TT)3/2
17

---

Published in Transactions on Machine Learning Research (06/2024)
S 8/2
3/2
1 +
|PT]
nT
(V
2T
In
T3/2
T
+1
+1))
3/3
3/2
(Vlog(T))
2
nVT
3/3
3/2
1
T3/2
3/2
+
HVT
C1
3/2
T
S 4.32
In
NVT
C1
S 4.32 (In T)/34
(1277)8/4
(In 7)3/11
< 4.32 T1/4
S 4.32 1.08 5
where in the third-last inequality we used 2 T
Putting everything together and letting ei = 1 yields
inf sup Rr ALG, Va(F))TT
3
7
B Graph-theoretic results
In this section, we present general version of a graph-theoretic lemma (Lemma G that is crucial for our positive results in Section 4 Before stating it, we recall a few known results.
The first result is a direct consequence (Alon et al. 2017 Lemma 10) specialized to undirected graphs. Lemma 3.
Let G (V,E) be an undivected graph containing all self-loops and (g( its d-th independence number. For all V, let Nº (i) be the d-th neighborhood of i, p(i) 2 0, and P(i) = EjENy p()) 0. Then
Σ p(i) iEV P()
S ag()).
Proof. Initialize V1 = V, fix ji e argmingev, P(), and denote V/2 = V W(1)). For k 2 2 fix ja E
argmin P(j) and shrink V4+1 = Vi (jie) until Vx+1 = Ø. Since g is undirected ja & N(e), therefore the number of times that an action can be picked this way is upper bounded by a. Denoting N"'ix)) V& (ix))) this implies
Σ p(i) P(i
-
Σ
Σ
p(i)
Σ
m
p()) P(N)
Σ
EiENG))
a
P(i)
P(in)
(EN'(L)
kE
concluding the proof.
The following result, known as the inequality of arithmetic and geometric means, simply AM-GM inequality, is used in the proofs of Lemmas and
6
Lemma 4 (AM-GM inequality). For any TI, Er E [0, oo),
01 Fr
(x1
xx) 1/r
18

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. By Jensen's inequality,
Σ x (x!"*)= = a/
24 Σ
2 im1
In (x:)
iml
The second result is proven in CCesa-Bianchi et al. 2019 Lemma 3), but here we give slightly different proof based on the AM-GM inequality.
Lemma 5. Let g = (V.E) be an undirected graph containing all self-loops and (g its d-th independence number. For all V, (odNN((v (w) be the d-th neighborhood of v, c(u) 2 0, and C(v) 1 -w-IwEEN [[[ww)
0. Then
c(u) I Σ EE
aa( + Σ +<dco)))
I-E- ((u)
NEV
Proof.
Set for brevity P(v) = E (o) dw). Then we can write
d(u
c(u)
c(u)
Σ VEV
E
E
+
C(T)
C(v)
C(v) vEV:P(r)<1
VEV: ((V22
(II
and proceed by upper bounding the two terms (I) and (II) separately, Let r(v) be the cardinality of N28 NV(v)). We have, for any given v E V,
Σ c(w) 21 min C(v) Σ c(w) = =1 } wEN(v)
min
C(u)
(E)(2))
1 max
II
(1 - c(w))
Σ wEN(u)
-1- = r(v) -1 (1()
(E
((0)
21
(1 1
11
r(u)
where the first equality follows from the definition of C(v) and the monotonicity of x + 1 x, the first inequality is implied by the AM-GM inequality (Lemma and the last one comes from r(v) 2 1 (for NN (z)). Hence
c(u)
c(v)
(T) S Σ
T- -EV
1-
VEV: P(u)21
As for (TT), using the inequality
- S e x E R. with x c(w), we can write
C(u) 2 1 exp
c(w) exp (-P())
WENS (o)
Now, since (TT) we are only summing over such that P(e) 1, we can use the inequality 6-
(1 e1-e-1)a x. holding when [0, 1], with x P(v), thereby concluding that
C(τ) 2 (1-e
Thus
(1)
Σ
c(u)
c(v) P(v)
<
a
I 1)pv))
1-e-1
e-
JEV
where in the last step we used Lemma
19

---

Published in Transactions on Machine Learning Research (06/2024)
We can now state more general version of our key graph-theoretic result, which can be proved similarly to Lemma 1
Lemma 6. Let Gi EV), and G2 E2) be two undirected graphs containing all self-loops and
aG M G2) the independence number of their strong product G1 X G2. For all (i.5) E Vi V2, let also M (i), (u), and And (i, be the first neighborhoods of (in G1), v (in G2), and (i,0) (in 91 (g2 If w w= (w(j, u)) (ja))Visx, an arbitrary matrix with non-negative entries such that -EjENT (1) w(j, u) 2
for all (i, u) E Vi= x V/2 and =I EjeNp (1) w(j. u)) for all (i, E V1 x V2, then
ΣΣ
v().v)
(( + +E Σ vo(i, u)
S e e-1
1- II (e) (v) (1- EsENpi ((i.u) KEV; VEV2
EVV vEV2
B.1 Further discussion on y
In general, a(N)a(F) I F holds for any arbitrary pairs of graphs N, F. Indeed, the Cartesian product I x J of an independent set 1 of N and an independent set J of is an independent set of N X F. There exist graphs F with ((N))(FF) < (( M F), but these appear to be quite rare and pathological cases. For the sake of completeness, we add an example of such a construction below. This shows that not all pairs of graphs belong $.
Example 1. Take as the first graph G EV,,,,, the cycle Cs over vertices. Then, for any 2 2, build Cs
Gk = (Vk, E&) inductively by replacing each verter v E Va-1 by a copy Os and each edge e E Eg-1 by a copy of K5,5 (the complete bipartile graph with partitions of size 5 and 5) between the two copies of Cs that replaced its endpoints. It can be shown that a(Gx) =2 but a (G& & Gi) 5 > 4 aGt)).
To see why, note first that (CC)) = 2 but a (C & C3) 2, by choosing the independent set containing the 5 vertices (1,1), (2,3), (3,5), (4,2), (5, 4). For k 2 2, aGrx) = 2* but we take the analogous in G2 E G2 of the above independent set in Cs A Cs. This gives 5 sets S2, S4, of 25 vertices each, with no edges between S;, Sj when i + j. The subgraph of Gx & GR induced by each S; is simply the previous iteration Gk-1 of this construction, and proceeding by induction we can find an independent subset of each S wilh 56-1 vertices, giving a total of 5 independent vertices.
C The upper bound of Cesa-Bianchi et al. (2020) for experts
Desa-Bianchi et al. 2020. Theorem 10) gives theoretical guarantees for the average regret over active agents. In this section, we briefly discuss how to convert their statement to a corresponding result for the total regret over active agents that is the focus of our present work.
Before stating the theorem, we recall that the convex conjugate f*: R R of a convex function f: X + R is defined, for any æ E Rd, by (*() suPwex (x- w (e-w-f(ww)) f(w)). Moreover, given a > O, say that f is o-strongly convex on X with respect to a norm ||-|| if, for all u, w E X, we have fw) 2 f(w) (w
l|u- - w|l w| Lemina 2.19 and subsequent.
The following well-known result can be found in (Shalev-Shwarlz al. 2012 paragraph).
Let f: X:X- + R be a strongly convez function on X. Then the convex conjugate f is everywhere differentiable on Rdd.
Lemma 7.
The following result- see, e.g., OOabona el al. 2015 bound (6) in Corollary with F set to zero) shows an upper bound on the regret of Algorithm for single-agent online convex optimization with expert feedback.
Theorem 3. Let g: X + IR a differentiable function o-strongly convex with respect to ||-I1. Then the regret of Algorithm run with 9t
" v4g, for n > 0, satisfies
T
D VT
" T 1 +
Σ (xx))
inf (xx) < mEX t=1
17
20
VE
[=1
20

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 2:
input: or-strongly convex regularizers gr - for 1,
initialization: 0 0 E Rd
for t= ..2.... do choose w, Vii (Or) observe (le(w,) Rd
update Oe+1 0₁ ve((),
where D supg and I1-11. is the dual norm of I1-11- If sup [ S L, then choosing n 22 IL, gives Rr S L//2//o.
We can now present the equivalent of Cesa-Bianchle et al. 2020 Theorem 10) for cooperative online covenx optimization with expert feedback (i.e., F is a clique) where n but the feedback is broadcast to first neighbor immediately after action is played (rather than the following round).
Algorithm with oblivious network interface and Ltt where ll is upper bounded by a constant L> 0, is a learning rale, π and the regularizer g: % + R is differentiable, o o-strongly convex with respect to some norm ||- and upper bounded by a constant M then the network regret satisfies
Theorem 4. Consider network N (A, Ex) of agents. If all agents
(ML
nL
RT S
+
(2((a(N)+Q)))
20
For M/L, we have
RT S (V20LM) + QYT
Proof sketch. For any X, agent v and time t, let (x(1) be the prediction made by at time t, re(v, x) e, (x)(1)) (x))), Qu = Pr (u E UWEA, N (w)) = - -II (1 q(w)), and A' == {w E A g(w) > 0). (Cesa-Bianchi Bianchi et al. 2020
Proceeding as (Cesa-
Theorem 2) yields, for each v A' and a X,
T re(u, x))
2 + 2
n
T
E
Σ
@
Q
(9)
Now, by the independence of the activations of the agents at time and (re(v, æ:) vEA we get
R
sup ØEX DEV'
Σ q(v) Σ B))((,
(10)
Putting Equations g and
10
together and applying Jensen's incquality yields
Ry S
Σ
q(v)
1
(Mr
M
nT2
VT <
Σ Zv
M
+ VT.
nT.
Q
Q
VEV.
The proof is concluded by invoking Lemma
D Learning curves
We also plot the average regret Rr/Q against the number T of rounds. Our algorithu is the blue curve and the baseline is the red curve. Recall that these curves are averages over 20 repetitions the same experiment (the shaded arcas correspond to one standard deviation) where the stochasticity is due to the internal randomization of the algorithms. Experiments are designed to show the difference in performance when we allow agents to communicate and when do not. The strong product captures in mathematical
21

---

Published in Transactions on Machine Learning Research (06/2024)
form this difference in the regret bound for our algorithm, while the experiments here show it empirically. In particular, the bound for the case of no communication is bigger, and performances are worse in our simulations, as expected from theory.
Experiments were run on a local cluster of CPUs (Intel Xeon E5-2623 v3, 3.00GHz), parallelizing the code over four cores. The run took approximately two hours.
01
(a) PER 0.2, PER = 0.2
(b) PER 0.8, PER 0.2
32
(c) PER 0.2, PER 0.8
(d) PER 0.8, PER 0.8
Figure Average regret RT RT/Q against 1000 of rounds. Activation probability q=
22

---

Published in Transactions on Machine Learning Research (06/2024)
100
00
43
260
406
403
660
3366
200
480
6.0
825
1020
(a) N
0.2, PER 0.2
F.
(b) 0.8, F
N
0.2
22
200
400
352
000
3008
230
480
600
830
1000
(c) PER 0.2, F
0.8
(d) PER 0.8, PER 0.8
Figure 4: Average regret Rr/Q against 1000 of rounds. Activation probability q = 0.5.
23

---

Published in Transactions on Machine Learning Research (06/2024)
100
85
42
266
366
402
200
3266
200
460
6.0
835
1030
(a) PER 0.2, F 0.2
(b) N 0.8, PER 0.2
100
63
68-
200
3506 400
152
600
230
420
870
1030
(c) N 0.2, F.
0.8
(d) PER 0.8, PER 0.8
Figure Average regret Ry / against 1000 of rounds. Activation probability q = 0.05.
24


Reviews:
[{"review_id": "RkhUexQMVn", "reviewer": "Reviewer_bqdM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths:\nA simple algorithm that seems to optimally address a relatively clean problem. The analysis requires some algebra, but does not seem overly involved.\n\n# Weaknesses/ Questions:\n\n## First, a few more minor issues:\n\nThe communication model seems oddly limiting here and could do with more motivation: wouldn't we gain much more power if agents were allowed to broadcast something other than their own direct observations/action distributions? What if they could “pass on” messages from other agents? This doesn't seem that unrealistic, and yet it seems that it might significantly improve results. Is the $n$ message distance limitation supposed to factor-in some idea that after $n$ times being passed on a message will become corrupted and unreadable?  I am not an expert in distributed algorithms, but it seems to me that this issue could be more clearly explained.\n\nOn Page 8, regarding the argument that $B_s(i,v)$  and  $B_t(i,v)$  are independent: this point is  more subtle than is provided in the text. It appears that the key  idea is that because we only use \\hat \\ell_1, \\dots,\\hat\\ell_{t-n}  at time t, this means that all actions taken using information from time steps for which there is no “in-flight” information. As written this  was confusing at first because naively it is easy to conceive of an algorithm that acts on information as soon as it is received. For such an algorithm, it might not hold that $B_s(i,v)$ and $B_t(i,v)$ are independent. So, I think some clarification in this part of the proof is warranted.\n\nPage 9 just  before Jensen inequality, it would be clearer if the summation were not on top of the fraction: doesn’t make it  obvious that the square root  is part of the summation\n\n## Last, a more significant issue:\n\nI have a technical concern in Theorem 2, which  I hope the authors can clarify.  In particular, I do not understand how Lemma 2 is being applied here.\n\nMy understanding of the proof is that  the idea is to construct a graph for which the agents cannot communicate, and then argue that since the regret is the sum of the individual agents’ regrets, we apply Lemma 2 to each agent to obtain a regret that is (num agents) * $\\sqrt{\\alpha(F) Q T}$, where here “num algorithms” is really the “effective\" number of agents after we’ve done some manipulation to ensure that no communication is possible.\n\nNow, my concern is that Lemma 2 does NOT say that “for any graph $F$, there is  a sequence of losses such that the regret of  ANY agent is $\\sqrt{\\alpha(F) Q T}$”. Instead, it seems to say “For any graph $F$ and any agent, there exists a sequence of losses such that the regret  of the agent is at least $\\sqrt{\\alpha(F) Q T}$”.\n\nAs a result, I don’t follow how it is applied in the proof of theorem 2: it seems to me that although Lemma 2 can indeed provide losses that lower bound the regret of one of the agents, in doing so it may not be able to simultaneously lower bound the regret of all of the agents. Now, I’m willing to believe that this can be fixed, but it is not so obvious how and so needs some more detail. \n\nFor example, If I am allowed to have # agents > |K|, then I can just have one agent dedicated to playing each action and then clearly it is impossible to force all the agents to have low regret since one of them must have regret 0. Now, obviously this is not actually an algorithm that will have low regret overall, but it IS one that appears to break the argument currently used in the proof of Theorem 2.\n\nPossibly I've misunderstood the way in which Lemma 2 is used, or missed some other subtlety. I have currently marked \"No\" on the \"claims and evidence\" question for this review, but if this concern can be alleviated, I will change to \"yes\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a problem of minimizing regret among  several cooperating agents. In the formal setup, we have a graph $F$ of $K$ possible “actions” and a graph $N$ of “agent connectivity”. In each round, each agent is activated with some probability, and then may take one action. It then receives feedback in the form of a loss for that  action, as well as the  “counterfactual” losses it would have received if it had chosen any action adjacent to the chosen action in $F$. Then it broadcasts this feedback as well as its distribution over actions. Broadcast messages reach nodes in the graph $N$ at distance $k$ from the broadcaster after $k$ rounds for an $k\\le n$ for some given $n$ (and never reach nodes with $k>n$). The goal is to minimize the network regret, which is roughly the sum of all of the individual agent’s regrets with respect to a single shared comparator action.\n\nThis paper generalizes recent results that  consider the case of that $F$ is a clique (which corresponds to the standard “experts”  setting) and the case that $F$ has no edges (which corresponds to the standard  “multi-armed bandits” setting). The final regret is\n\n$\\sqrt{\\alpha(N^n\\boxtimes F) T}$\n\nWhere $\\alpha$ represents the “independence number” (which is roughly like a sphere-packing / covering number generalized to graphs). \n\nThe algorithm is quite simple: each node essentially runs a version of the standard Exp3 MAB bandit algorithm, but uses a loss estimate that is improved by using information from other agents within distance $n$ in the connectivity graph. This improvement is counterbalanced by restricting the algorithm to only use loss estimates that are at least $n$ time steps in the past in order to compensate for potential delays in receiving feedback from other agents.\n\nA lower bound is presented showing the tightess of this regret bound, along with some simulated experiments.\n\nOverall, I think the quality of the results is significant enough to warrant acceptance. I do have two questions, and one more major concern however that I think the authors must address in order for the paper to be acceptable. I will enumerate them in the \"strengths and weaknesses\" section below.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses described above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fURTM8ZGUy", "reviewer": "Reviewer_Mesd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The author proposes an algorithm for multi-agent online learning with general graph feedback that achieves regret dependent on the complexity of the graph. In several special situations, the results match previous findings, suggesting that the proposed algorithm can handle larger regions while providing similar guarantees.\n\n2. The author also provides a lower bound, suggesting that the upper bound is near-optimal.\n\n3. The paper is well-written and easy to follow.\n\n4. Experimental results also support the efficiency of the algorithm.\n\nWeakness:\n\n1. It seems incorrect to claim that the results hold for an oblivious network. In the algorithm, the agent needs to know the network topology for agents within a distance no more than $n$. Otherwise, the agent cannot detect the generated time for a message.\n\n2. The feedback message includes the draw distribution, which significantly increases the communication complexity.\n\n3. For the cooperative learning process, the proposed algorithm requests a fixed participation probability $q(v)$, which seems restrictive. Recently, several works [1,2] have studied the cooperative learning process with asynchronous communication, allowing agents to decide whether to participate arbitrarily. It seems interesting to explore whether the current analysis can deal with this more general setting, and it would be beneficial if the author could include a discussion on this matter.\n\n[1] Asynchronous upper confidence bound algorithms for federated linear bandits.\n\n[2] A simple and provably efficient algorithm for asynchronous federated contextual linear bandits.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work addresses the multi-agent online learning problem with feedback graphs, where agents can observe the losses associated with neighboring actions and receive information from nearby agents in the graph. The author proposes a novel algorithm that achieves regret dependent on the complexity of the graph. In several special situations, the results match previous findings, and an instance-based lower bound demonstrates that the upper bound is near-optimal. Additionally, experimental results support the efficiency of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness.", "broader_impact_concerns": "I do not find any potential negative societal impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cZWV3AhFEe", "reviewer": "Reviewer_6GPK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe that the research question in this paper,\nhow the structure of communication networks and feedback graphs affects the complexity of a problem,\nis a topic of interest to the online learning theory community.\nAlso, from what I could see, no major errors were found in the theoretical analysis or numerical experiments.\nIn light of the above and the evaluation criteria of the TMLR, I support the acceptance of this paper.\n\nOn the other hand, I think this paper has the following weaknesses:\n* The design and analysis of the algorithm are based on a straightforward combination of the existing studies in corporative online learning,\ne.g., by Cesa-Bianchi et al. (2019),\nwith those in graph bandits,\ne.g., by Alon et al. (2017).\nThe obtained upper bound does not look surprising.\n* A gap remains between the upper bound and the lower bound.\nIn fact,\nthe lower bound applies only to the instances such that\n$\\alpha( N \\boxtimes F) = \\alpha(N) \\alpha (F)$,\nwhich means that the lower bound essentially depends on the value of $\\alpha(N) \\alpha(F)$ while\nthe upper bounds depends on $\\alpha( N \\boxtimes F)$.\nI believe that the issue of which is tighter is the non-trivial and interesting question.\n* In the contexts online learning with feedback graphs,\ndirected feedback graphs, graphs without feedback graph, and weakly observable graphs have been considered,\ne.g., by Alon et al. (2017).\nSuch more general graphs are not addressed or even mentioned in this paper.\nNot including them is not a problem in itself,\nbut it would be better to have an explanation as to why they are not included.\n(For example, I would like to know if it is just for simplicity or for technical difficulty.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers a problem setup formulated as a common generalization of online learning with a feedback graph and corporative online earning with a communication graph.\nThis paper proposes an algorithm for this problem,\nwhich achieves a regret upper bound that depends on the independence number of the strong product of the feedback graph and the communication graph.\nThis result is complemented by nearly tight lower bounds and numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not believe that major changes are necessary, but I would appreciate it if you would consider addressing the concerns raised in the above weakness section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work is worthy of publication in TMLR; my recommendation is for the paper to be accepted with minor revision. Regarding the minor revisions, the main thing is to look into the the issue of whether Theorem 2 holds only for deterministic algorithms (which seems likely) and update the theorem statement accordingly. Also, when you first mention your lower bound in the main text (around the top of page 2), I believe you need to add further qualifications (i.e., restrictions) for your result in light of Theorem 2 currently requiring all agents to use the same algorithm.

Below are some minor things (editorial in nature):
 - The table in the center of page 2 is currently an orphan. It should be numbered and I think also equipped with a caption.
 - In the paragraph immediately after the table in the center of page 2, change “is necessary to not incur in a linear regret” by removing “in” (stylistically, better yet, remove "in a").
 - Can you include punctuation in Assumption 1? I raise this point because the writing of the 3rd item makes it feel like some text got truncated ("and when" —> I was left wondering if there was more the authors meant to write here); having a period at the end will ensure the reader that the writing is as intended.
 - I suggest being consistent with punctuation at the end of equations. Sometimes, you do include a period when an equation is at the end of a sentence. Elsewhere, you do not. My recommendation is to always include punctuation when doing so is necessary for grammatical correctness.
 - I don't know if it is just me, and maybe none of the reviewers looked at Figure 2 much, but I have a very difficult time reading these 3D scatter plots. Please do a sanity check and see if there is a clearer way to present the information therein in a way that allows the reader to precisely read the plots. For example, for the red and blue dots closest to (0.8, 0.2) in each of the 3 figures, it's very difficult to read the information in the plot. Given the few data points you have here, maybe there is a non-3D plot way to present the information.
Decision: Accept (poster)