Bandits with Abstention under Expert Advice
Authors: Stephen Pasteris
Alberto Rumi
Maximilian Thiessen
Shota Saito
Atsushi Miyauchi
Fabio Vitale
Mark Herbster
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-armed bandits
Expert advice
Abstention
Contextual bandits
Primary area: bandits
TL;DR: We study bandits with expert advice when given an option to abstain from making any action, and achieve novel reward bounds for confidence rated predictors.

Abstract: We study the classic problem of prediction with expert advice under bandit feedback.  Our model assumes that one action, corresponding to the learner's abstention from play, has no reward or loss on every trial. We propose the CBA (Confidence-rated Bandits with Abstentions) algorithm, which exploits this assumption to obtain reward bounds that can significantly improve those of the classical Exp4 algorithm. Our problem can be construed as the aggregation of confidence-rated predictors, with the learner having the option to abstain from play. We are the first to achieve bounds on the expected cumulative reward for general confidence-rated predictors. In the special case of specialists, we achieve a novel reward bound, significantly improving previous bounds of SpecialistExp (treating abstention as another action). We discuss how CBA can be applied to the problem of adversarial contextual bandits with the option of abstaining from selecting any action. We are able to leverage a wide range of inductive biases, outperforming previous approaches both theoretically and in preliminary experimental analysis. Additionally, we achieve a reduction in runtime from quadratic to almost linear in the number of contexts for the specific case of metric space contexts.

Bandits with Abstention under Expert Advice
Stephen Pasteris
Alberto Rumi
Maximilian Thiessen'
Shota Saito
Atsushi Miyauchi
Fabio Vitale²
Mark Herbster
The Alan Turing Institute "TU Wien
Uniiveriity of Milan SCENTAI Institute
UUniversity College London
sspsterisstuuring ac.uk
Abstract
We study the classic problem of prediction with expert advice under bandit feedback. Our model assumes that action, corresponding the learner's abstention from play, has no reward or loss on every trial. We propose the confidence-rutie bandits with abstentions (CBA) algorithm, which exploits this assumption obtain reward bounds that can significantly improve those of the classical EXP4 algorithm. Our problem can be construed the aggregation of confidence-rated predictors, with the learner having the option to abstain from play. We are the first to achieve bounds on the expected cumulative reward for general confidence-rai special case of specialists we achieve novel reward bound, significantly improving the previous bounds of SPECIALISTExP (treating abstention as another action). We discuss how CBA can be applied to the problem of adversarial contextual bandits with the option of abstaining from selecting any action. We are able leverage a wide range of inductive biases, outperforming previous approaches both theoretically and preliminary experimental analysis. Additionally, we achieve a reduction in runtime from quadratic to almost linear in the number of contexts for the specific case of metric space contexts.
predictors. In the
Introduction
We study the classic problem of prediction with expert advice under bandit feedback. The problem is structured sequence of trials. During each trial, each expert recommends probability distribution over the set of possible actions. The learner then selects an action and observes and incurs the (potentially negative) reward associated with that action that particular trial. In practical applications, errors often lead to severe consequences, and consistently making predictions is neither safe nor economically practical. For this reason, the abstention option has gained a lot of interest in the literature, both in the batch and online setting [Chow) 1957 1970 Hendrickx et al.) 1021 Cortes et al. 2018). Similarly to previous works, this paper is based on the assumption that one of the actions always has zero reward: such an action is equivalent to an abstention of the learner from play. Besides the rewards being bounded, we make no additional assumptions regarding how the rewards or expert predictions are generated. In this paper, we present an efficient algorithm CBA (Confidence-ratte bounds that can be dramatically higher than those of ExP4 [Auer et al. 22022]. In the worst case, our reward bound essentially matches that of ExP4 so that CBA can be seen as strict improvement, since the time-complexities of the two algorithms are, up factor logarithmic in the time horizon, identical the general case.
Bandits with Abstentions) which exploits the abstention action to get reward
Our problem can also be seen as that of aggregating confidence-rated predictors [Blum and Mansour 2007| Gaillard al.) 2014 Luo and Schapire 2015) when the learner has the option of abstaining from taking actions. When the problem is phrased in this way, at the start of each trial, each predictor recommends probability distribution over the actions (which now may not include an action with
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

zero reward) but with a confidence rating, A low confidence rating can mean that either the predictor thinks that all actions are bad (so that the learner should abstain) or simply does not know which action is the best. Previous works on confidence-rated experts measure the performance of their algorithm in terms of the sum of scaled per-trial rewards. In contrast to previous algorithms, our approach allows for the derivation of bounds on the expected cumulative reward of CBA.
This formulation enables us to extend our work the problem of adversarial contextual bandits with the abstention option, which has not been studied before. Previous work has considered the abstention option in the standard (context-free) adversarial bandit setting or in stochastic settings [Cortes et al. 2018 [220 Neu and Zhivotovskiy, 2020), but not in the contextual and adversarial case. Moreover, their results and methods cannot be applied to confidence-rated predictors. To get more intuition on this setup, we can think of any deterministic policy that maps contexts into actions. Any such policy can be viewed as a classifier, with foreground classes associated with each action and a background class associated with abstaining. Our learning bias is represented by set of information we refer to as the basis, which we formally define later. It encodes contextual structural assumptions that hold exclusively for the foreground classes and are provided to the algorithm priori. A particular type of basis is generated by a set of potential clusters that can overlap. Alternatively, a basis can also be created using balls generated by any kind of distance function, which groups contexts believed to be close together. For this latter family of basis, we can also achieve a significant speedup in the per-trial time complexity of CBA. This result is very different (and incomparable) to other results about adversarial bandits in metric spaces [Pasteris et al. (2033b a].
1.1 Additional related work
The non-stochastic multi-armed bandit problem, initially introduced by Auer et al. 22022] J. has been subject of significant research interest. Auer et al. [200]] also considered the multi-armed bandit problem with expert advice, introducing the ExP4 algorithm. ExP4 evolved the field of multi- armed bandits to encompass more complex scenarios, particularly the contextual bandit [Lattimore and Szepesvári] 2020). Contextual bandits are an extension of the classical multi-armer bandit framework, where an agent makes a sequence of decisions while taking into account contextual information. Our work is also related to the multi-class classification with bandit feedback, called weak reinforcement [Auer and Long 1999]. An action in our bandit setting corresponds to class in the multi-class classification framework.
As discussed in the introduction, a key aspect of this work is the option to abstain from making any decision. In the batch setting [Chow] 1957 1970). this option is usually referred to as "rejection". These works study whether use or reject a specific model prediction based on specific requests (see Hendrickx et al. [2021) for survey). In online learning, "rejection" can be the possibility of abstention by the learner. These works usually rely on a cost associated with the abstention action. Neu and Zhivotovskiy [2020] studied the magnitude of the cost associated with abstention in an expert setting with bounded losses. They state that if the cost lower than half of the amplitude of the interval of the loss, it is possible to derive bounds that are independent of the time. In Cortes et al.) [2018). a non-contextual and partial information setting with the option of abstention is studied. The sequel model [Cortes et al. 2220) regards this model as special case of their stochastic feedback graph model. [Schreuder and Chzhen [02T]] studied the fairness setting when using the option of abstaining as it may lead to discriminatory predictions.
One specific scenario where prior algorithms can establish cumulative reward bounds is as follows: on any given trial, the predictors are specialists [Freund et al. 1997]. having either full confidence (a.k.a. awake) or no confidence (a.k.a. asleep). The SPECIALISTEXP algorithm by Herbster et al. 20211. bandit version of the standard specialist algorithm, achieves regret bounds with respect to any subset of specialists where exactly one specialist is awake on each trial. We differ from this work as abstention is an algorithmic choice. Instead of sleeping in the rounds where the specialist is not active, the specialist will vote for abstention, which is a proper action of our algorithm. In Section 5.2 we present an illustrative problem involving learning balls in a space equipped with a metric. This example demonstrates our capability to significantly improve on SSECIAL For this problem, we also present subroutines that significantly speed up CBA.
2

---

2 Problem formulation and notation
We consider the classic problem of prediction with expert advice under bandit feedback. In this problem we have K + actions, E' experts, and I trials. On each trial t:
1. Each expert suggests, to the learner. probability distribution over the K + 1 actions.
2. The learner selects action de-
3. The reward incurred by action or on trial /. (which is in [-1, 1)) is revealed to the leamnr.
We note that the experts' suggestions and the rewards (associated with each action) are chosen a- a-priori and hence do not depend on the learner's actions. The aim of the learner is to maximize the cumulative reward obtained by its selected actions. As discussed in Section I we consider the case in which there is an action (the abstention action) that incurs zero reward every trial.
We denote our action set by [ U { where D the abstention action. For each trial f E [T) we define the vector r, E [- such that for all [K], Tr,o is the reward obtained by action on trial Moreover, we define f == 0 which is the reward of the abstention action D.
It will be useful for us to represent probability distributions over the actions by vectors in the set:
A = {s E [0, 1] |||||| S 11)-
Any vector E A represents the probability distribution over actions which assigns, for all E [K]. a probability of s, to action a, and assigns a probability of 1 - || to the abstention action D. where |//|/ denotes 1-norm of s. We write distribution s. We will refer to the elements of the set A as stochastic actions.
to represent that action
drawn from the probability
policy any element of A (noting that any such policy E AA defines a stochastic sequence of actions: on every trial E [2] an action a E [K] U (D) being drawn as a et. Note that if the learner plays according to a policy trial t it obtains an expected reward of T et. where the operator denotes the dot product. Note that each expert equivalent Hence, at the start of each trial t E [T], the learner views the sequence (e) [E]}.
matrix in [o, 1]T*X), Any policy
AL, then on each
policy. Thus, for all E [E] we denote the i-th expert by e' AT.
We also view the experts confidence-ree t E [T], the vector e; can be viewed as suggesting the probability distribution e ///leella over [K]. but with confidence | We denote this confidence by Cτ, ||e] [1 and write C == (Ct,1,.... C.E).
predictors
the set [K] for each i [E] and
In this work, we will refer to the unnormalized relative entropy defined by:
A uu, v) == Σ
In
||0]|]
+ ||0]||
SE[E]
for any u, u E E. We will also use the Iverson bracket notation [[RED] as the indicator function, meaning that it is equal to if PRED is true, and O otherwise. All the proofs are in the Appendix.
3
Main result
Our main result is represented by bound the cumulative reward of our algorithm CBA. We note that any weight vector e RF induces matrix T(u)= RT* K defined by
ग (w) = Σ u,e'
EE[F]
which is the linear combination of the experts with coefficients given by u. However, only some of such linear combinations generate valid policies. Thus, we define
V == {u E R T E A²)
as the set all weight vectors that generate valid policies. Particularly, note that u V if and only if, on every trial f, the weighted sum of the confidences u C, is no greater than one. Given some
u E V, we define
p(u)= = Σ (..T((U)) (4),
[E[T]
3

---

which would be the expected cumulative reward of the learner if it was to follow the policy π (u)) We point out that the learner does know V the function π a-priori.
The following theorem (proved in Appendix A allows us to bound the regret of CBA with respect to any valid linear combination u of experts.
Theorem 3.1. CBA takes parameters E (0,1) and wi E TR For any E V the expected cumulative reward of CBA is bounded below by:
Elyr... B[p(u)] A(u, w1) (12K + 2)T, NE[T]
Σ
?
where the expectations are with respect to the randomization of CBA's 's strategy. The per-trial time complexity of CBA is in O(KE)
We now compare our bound those of previous algorithms. Firstly, ExP4 can only achieve bounds relative to и E V/ with ||e]| = 1. in which case it essentially matches our bound but with 12K + 2 replaced by 8K + 8. Hence, for any u E V the ExP4 bound essentially replaces the term p(u) in our bound by m/2u//1///l. Note that || la could be as high as the number of experts which implies we can dramatically outperform ExP4
Secondly, when viewing our experts as confidence-rate predictors, we note that previous algorithms for this setting only give bounds trial is u c2 for some u E V. This is only a cumulative reward bound when u C2 = 1 for all E [T). and finding such is typically impossible. When there does exist that satisfies this constraint, the reward relative to u is essentially the same as for us [Blum and Mansour [007]. However, there will often be another value of that will give much better bound, as we show Section
weighted sum of the per-trial rewards where the weight each
4 The CBA algorithm
The CBA algorithm is given in Algorithm 1. In this section, we describe its derivation via modification of the classic mirror descent algorithm.
Our modification of mirror descent is based on the following mathematical objects. For all t E [T] first define:
V := {o E R [T)|l s 1)},
which is the of all weight vectors that give rise linear combinations producing valid stochastic actions at trial t. Given some t E [T], we define our objective function Pt Vi + [-1, as
pr(u) T ((v) for all Ve.
Like mirror descent, CBA maintains, on each trial f E [T]. a weight vector w, E R. However, unlike mirror descent the simplex, we do not keep w; normalized, but we will instead project into V; at the start of trial t, producing vector Wt Also, unlike mirror descent, CBA does not use the actual gradient (which it does not know) of pa w. but (inspired by the ExP3 algorithm) uses an unbiased estimator instead. Specifically, on each trial t E [T). CBA does the following:
1. Set wt argmin A(U, (.,w.)).
2. Randomly construct vector 9t E E such that Ejg,] = (w,(
3. Set Wt+1 argmin (WI, (w: v) Al),w.))
This naturally raises questions: how is az selected and how is 9, constructed? On each trial t E [T] we define
8t Σ W
SE[E]
which is the stochastic action generated by the linear combination w., and select at ~ 8t. Note that:
E Err,, (())))
Preeisseyy, for each expert there exists a trial in which the confidence 1, then we have 0 S |Mila S Otherwise can be high 0 & ||u|]] & E/c", where e* maxiery ct.

---

Algorithm 1 CBA(
For
I.2,...,77 T do:
1. For all i [E] receive eq
2. For all i [ set or ||e|l1
3. If ||c, I I then:
(a) Set w. f- wt
4. Else:
(a) By interval bisection find À > 0 such that:
Σ
=
(b) For all E [E] set W + wi,
5. Set:
T
iE[E]
6. Draw de ~ St
7. Receive Tt.a,
8. For all a E [K] set:
11 ail(1 r2,0r)/81.0r
9. For all i [E] set ((1+1) i exp(net (t)
which confirms that Pt is our objective function trial Once rt,a, revealed to proceed to construct the gradient estimator 9t. It is important that we construct this estimator in a specific way. Inspired by ExP4 we first define reward estimator A, such that for all E [K] have:
fta
[a uel(1 T/,04)/51,00
This reward estimate is unbiased as:
Ef 1 Pr(a azl(1 Te,0)/8r,a Ttaa
We then define, for all [E], the component:
ge.s == et fz.
Note that for all E [E] we have:
Elg,a] = et B(P.]] ei .r, @,pe(w.))
so that [[g.]] Upr (w,) as required.
Now that defined the process by which CBA operates we must show how compute w, and Wi+1- First we show how to compute w; from wi If ||cl]a < it holds that E V so we immediately have et ws Otherwise we must find w R that minimizes A(w, we) subject to the constraint:
Σ W1,4 = 1,
E
which is equivalent to the constraint that || (TwW))ll 1. Hence, by Lagrange's theorem there exists such that:
V wr A(wi, w;) +
Σ
3r,5 = 0
SE[B]
which is solved by setting, for all i [E]:
Wt, Wh,s explexppooooo Aer,))
5

---

The constraint is then satisfied if À is such that:
Σ EE
Ct exp(-Act,)) =
Since this function is monotonic decreasing, À can be found by interval bisection. For this computation step, we treat our numerical precision constant in our time complexity. In Appendix A.I] show that, even if the numerical precision is unbounded, we incur a time complexity equal to that of ExP4, up to factor logarithmic in T, adding only to the regret.
Turning to the computation of w++1 1+ since is unconstrained it found by the equation:
V me (g. Wi+1 + +1- + ((W++1, (.,+1,;,))) 0. which is solved by setting, for all [E]:
W(++1) := Wt,i exp(11e.;)
(2)
5 Adversarial contextual bandits with abstention
One main application of CBA is in the problem of adversarial contextual bandits with finite context set. In this problem, we have a finite set of contexts X. A A-priori nature selects a sequence:
(( rz) E X' |-
(T]),
but does not reveal it to the learner. For all E [7'] we define Tu == 0. On each trial E [?' the following happens:
1. The context o, is revealed the learner.
2. The learner selects an action o E [K] U {M}.
3. The learner sees and incurs reward rt.a, E [-11.]]
We will assume that we are given, a-priori, a set B C 2 that we call the basis. We call each element of B a basis element (which set of contexts). We will later introduce various potential bases, determined by the nature of the context's structure: points within metric space, nodes within graph, and beyond. Importantly, our method is capable of accommodating any type of basis and, thus, any potential inductive bias that might be present in the data.
Given our basis run our algorithm CBA with each expert corresponding a pair (B, k) Bx B The expert corresponding to each pair (B, k) will deterministically choose action when the current context 2, B, and abstain otherwise.
Corollary 5.1. Given any basis B of cardinality N and any M N can implement CBA such that for any sequence of disjoint basis elements (B, jj E [M] with corresponding actions (b, [K] Íj j [M] we have:
Σ E(rra,
ΣΣ
Ia B,JrE,, 2 2M) + 1)T.
NE(T]
tE|T JE[M]
The per-trial time complexity of this implementation of CBA is in O(KN).
Proof. The choice of experts for CBA that leads to Corollary 5.1 is defined by the set of pairs so that E K and for each B and action a E [K] there exists an unique i [E'] such that for all
e [T] and E [K] we have:
c = [z, B a]
By choosing W1, == M/NK for all i e [E]. and choosing
= (M (M (n( + +1)2)
Theorem 3.1 implies the reward bound Corollary 5.1 The per-trial time complexity direct implementation of CBA for this set of experts would be OKN).
D

---

(a) Two foreground classes and background as abstained.
(b) Two foreground classes and the background as another one.
Figure I: Illstrative example of abstention where we cover the foreground and background classes with metric balls. We consider two clusters (blue and orange) as the foreground and one background class (white), using the shortest path da metric. Using abstention, we can cover two clusters with one ball for each and abstain the background with balls required (Fig. [(a] In contrast, if treat the background class as another class, it would require significantly more balls to cover the background
class, seen by the 10 gray balls in Fig. [[b] If the number of balls to cover significantly increases
like in this case, the bound involving the number of balls also gets significantly worse
We briefly comment on the term:
Σ Ix E B JE[M]
that appears in the theorem statement. If x4 does not belong any of the sets in (B, Ij [M]) then this term is equal to zero (which is the reward of abstaining). Otherwise, since the sets are disjoint, H, belongs to exactly one of them and the term is equal the reward induced by the action that corresponds to that set. In other words, the total cumulative reward is bounded relative to that of the policy that abstains whenever z; is outside the union of the sets and otherwise selects the action corresponding to the set that re lies in.
Note the vast improvement of our reward bound over that of SPECIALISTEXP with abstention one of the actions. Let's assume our context set a metric space and our basis is the set of all balls. In order get reward bound for SPECIALISTEXP. the sets in which the specialists are awake must partition the set X. This means that we must add to our M balls a disjoint covering (by balls) of the complement of the union of the original M balls. Note that the added balls correspond the sets in which the specialists predicting the abstention action are awake. Typically this would require huge number balls so that the total number of specialists is huge (much larger than M); this huge number of specialists essentially replaces the term M in our reward bound (we illustrate an example in Figure
we show that the same implementation of CBA is capable of learning a weighted set of overlapping basis elements, as long as the sum of the weights of the basis elements covering any context is bounded above by one, which SPECIALISTEXP cannot do in general.
Furthermore, in Appendix D
As we will see below, the practical bases propose have moderate size of B ( leading to per-step runtime of O(K (2)2)) for CBA in this contextual bandit problem. In Section 5.2 we show how significantly improve the runtime for broad family of bases.
5.1 A lower bound
In this section, we show that CBA is, up an (In((B))) factor, essentially best possible on this contextual bandit problem:
Proposition 5.2. Take any learning algorithm. Given any basis B and any M for any sequence of disjoint basis elements (B, li [M] there exists a sequence of corresponding actions (b, [K] j [M]) such that an adversary can force:
Σ Σ
Irg E B
Σ :E(T]
Blra E (VMKT)
JE[M]

---

X10
x19
x10
x16
GABA
CeSm
17.5
EXP3
6.0
5.0
Mistakes
12.5
4.0
10.0
3.0
2.0
5.0
2.0
2.5
1.0
0.0
0.0
2.5
5.0
7.5
10.0
0.9
5.0
10.0
15.0
20.0
0.0
10,0
20.6
0.0
2.0
4.0
5.0
8.0
Time
x10
Time
x10'
Time
X10'
Time
x10
(a) Stochastic Block Model
(b) Gaussian graph
(c) Cora graph
(d) LastFM Asia graph
Figure 2: Results regarding the number of mistakes over time, the four main settings are presented
from left to right: the Stochastic Block Model, Gaussian graph, Cora graph and LastFM Asia graph. In this context, D1, D2, and D-INF represent the p-norm bases, LVC represents the community detection basis, and INT represents the interval basis. The baselines, EXP3 for each context, Contextual Bandit with similarity, and GABA-II, are denoted as EXP3, CBSim, and GABA, respectively, and represented with dashed lines. All the figures display the data with 95% confidence intervals over 20 runs, calculated using the standard error multiplied by the z-score 1.96.
5.2 Efficient learning with balls
In practice we can often quantify the similarity between any pair of contexts. That is, the contexts form metric space, equipped with distance function d A' x X' + R4 known to the learner a-priori. For example, contexts could have feature vectors in R (and the metric is the standard Euclidean distance or cosine similarity) or be nodes in graph with the metric given by the shortest- path distance. A natural basis for this situation the set metric balls. Specifically, ball any set B C X in which there exists some X and E R4 with:
= (= E X d(x, 2) 5)
For this broad family of base we can achieve the following speed-up, relying on a a sophisticated data structure based on binary trees.
Theorem 5.3. Let N == | Given any M E N we can implement CBA such that for any sequence of disjoint balls (By 1j E [M] with corresponding actions (by E [K]l] e [M]) we have:
EE(raa Elrra
ME Ix Bylre,,
In 1)T.
EE(T]
JE(M)
The per-trial time complexity of this implementation of CBA is in O(KNIn(N)
As there are at most ((N2) metric balls, this improves the runtime direct CBA implementation from O(KN3) to O(KN In(N)), that is almost linear per step. All the details are in Appendix B
6 Experiments
This section conducts preliminary experiments, the code available at GitHut We evaluate our method compare existing algorithms using graph data, since it is common consider graph structures under the confidence-rated expert setting (Cesa-Bianchi et al. 2013 Herbster et al.) 202T]. As mentioned above, the bases used in our algorithm can be constructed arbitrarily, allowing to encompass different inductive biases based on applications. Thus, we consider some representative bases used on learning tasks on graphs before, each leading different inductive priors on the contexts. We provide a short description of the bases here and refer to Appendix for more details.
Actually require weaker condition. We only use the fact that for each context X we have set B3 {Bf .... Bi) of monotonically increasing hasis elements, that is, B C B5 for i <, j. and the whole basis is formed by the union of these: U.ex B..

---

Effective p-resistance basis dy: Balls given by the metric
-1/0
dp(t,)) =
min MER Vic diy
Σ
|Ms - uel?
8,
We use d1, d2, and doo (Herbster and Lever
2009
Louvain method basis (LVC): Communities returned by the Louvain method [Blondel et al. 2008
processed by the greedy peeling algorithm [Lanciano et al. 2024].
Geodesic intervals basis (INT); All sets of the form / (z, y) == {= E X 2 is on shortest z-y path}
for all x; y E X' (Pelayo 2013
Thiessen and Gärtner 2021
Let N be the cardinality of |. For all three basis types, we immediately get an O(KN2) runtime per step of CBA there are (NV2) basis elements. Moreover, for dp balls and the LVC basis can use the more efficient O K In N) implementation through Theorem 5.3 We empirically evaluate our approach in the context of online multi-class node classification on given graph with bandit. feedhack. At each time step, the algorithm is presented with a node chosen uniformly at random and must either predict action from the set of possible actions [K] or abstain. The node can accept (resulting in a positive reward) or reject (resulting in a negative reward) the suggestion based on its preferred class with certain probability. In a real-world application, this models scenario where each user has a category preference (such as music genre or interest). When the item we decide to present matches their interest, there is a high probability of receiving reward.
We compare our approach CBA using each of these bases on real-world and artificial graphs against the following baselines: an implementation of CONTEXTUAL. BANDIT from [llikkins (2011). 1], the GABA BA-IT algorithm proposed by Herbster et al. 2021 and an EXP3 instance for each data point. We use the following graphs for evaluation.
Stochastic block model. We use an established synthetic graph, stochastic block model [Holland
al. 1983]. This graph is generated by spawning arbitrary number of disjoint cliques representing the foreground classes. Then an arbitrary number of background points are generated and connected to every possible point with low probability. Figure 2(a) are displayed the results for the case of F = 160 nodes for each foreground class and B = 480 nodes for the background class. Connecting each node of the background class with a probability of 1/VFB.
Gaussian graph. The points on this graph are generated in a two-dimensional space using five different Gaussian distributions with zero mean. Four of them are positioned the corners of the unit square, representing the foreground classes and having relatively low standard deviation. Meanwhile, the fifth distribution, representing the background class, is centered within the square and is characterized by a larger standard deviation. The points are linked in a k-nearest neighbors displayed the results for 160 nodes for each foreground class and a standard deviation of 0.2, 480 nodes for the background class with a standard deviation of 1.75, along with 7-nearest neighbors graph.
graph. In Figure 2(b) (
We tested our approach on the Cora dataset (Sen et al. 2008 and the LastFM Asia dataset [Leskovec and Krevi 2014). While both of these graphs contain both features and a graph, we exclusively utilized the largest connected component of each graph, resulting in 2485 nodes and 5069 edges for the Cora graph and 7624 nodes and 27806 edges for the LastFM Asia graph. Subsequently, we randomly chose a subset of three out of the original seven and eighteen classes, respectively, to serve as the background class. Additionally, we selected 15% of the nodes from the foreground classes randomly to represent noise points, and we averaged the results over multiple runs, varying the labels chosen for noise. Both in Figures [(c) and 2(d) we averaged over different label sets as noise. For the LastFM Asia graph, exclusively tested the LVC bases, it is the most efficient one to compute given the large size of the graph.
Real-world dataset.
The results from both synthetically generated tests (Figures 2(a) and 2(b) demonstrate the superiority of our method when compared to the baselines. In particular, d:s balls delivered exceptional results for both graphs, implying that do -blls effectively cover the foreground classes as expected. For the Cora dataset (Figure[(c)).. we observed that our method outperforms GA A- II only when employing the community detection basis. This similarity in performance is likely attributed to the dataset's inherent lack of noise. Worth noting that the method we employed to inject noise into the dataset may not have been the optimal choice for this specific context. However, it is
Results.

---

essential to highlight that our primary focus revolves around the abstention criteria, which plays central role in ensuring the robustness of our model in the presence of noise. For the LastFM Asia dataset, our objective was to assess the practical feasibility of the model on larger graph. We tested the LVC bases as they were the most promising and most efficient to compute. We outperform the baselines in our evaluation as shown in Figure 2(d) and further discussed in Appendix
In summary, our first results confirm what we expected: our approach excels when we choose basis functions that closely match the context's structure. However, it also encounters difficulties when the chosen basis functions are not good for the context. Appendix F the results for wide range of different parameters used to generate the previously described graphs are displayed.
A Acknowledgement
SP acknowledges the following funding. Research funded by Defence Science and Technology Laboratory (Dstl) which is executive agency of the UK Ministry of Defence providing world class expertise and delivering cutting-edge science and technology for the benefit of the nation and allies. The research supports the Autonomous Resilient Cyber Defence (ARCD) project within the Dstl Cyber Defence Enhancement programme. AR acknowledges the support from the NeurIPS 2024 Financial Assistance. MT acknowledges support from DOC fellowship of the Austrian academy of sciences (ÓAW). SS acknowledges the support by Huawei for his Ph.D study at UCL.
References
Morteza Alamgir and Ulrike von Luxburg. Phase transition in the family of p-resistances. In Proc. NIPS, pages 379-387, 2011.
Peter Auer and Philip M Long. Structural results about on-line learning models with and without queries. Mach. Learn,, 36: 36:147-181, 1999.
Peter Auer, Nicolò BisanBianchh, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48 77, 2002.
Amir Beck. First-Order Methods in Optimization. SIAM, 2017.
Vincent D) Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp., 2008(10):P10000S 2008.
Avrim Blum and Yishay Mansour. From external to internal regret. J. Mach. Learn. Res., 8(6), 2007.
Marco Bressan, Nicolè Cesa-Bianci Silvio Lattanzi, and Andrea Paudice. Exact recovery of clusters in finite metric spaces using oracle queries. Proc. COLT, 2021.
Nicolo Cesa- Bianchi, Claudio Gentile, and Giovanni Zappella. gang of bandits. In Proc. NIPS, volume 26, 2013.
C Chow. On optimum recognition error and reject tradeoff. IEEE Trans. Inf. Theory, 16(1):41-46, 1970.
Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Trans. Electron. Comput., EC-6(4):247-255 1957.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. In Proc. ICML, pages 1059-1067, 2018.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile. Mehryar Mohri, and Ningshan Zhang. Online learning with dependent stochastic feedback graphs. In Proc. ICML, pages 2154-2163, 2020.
Peter G Doyle and J Laurie Snell. Random Walks and Electric Networks, volume 22 of The Carus Mathematical Monographs. American Mathematical Society. 1984.
Robert W Floyd. Algorithm 97: shortest path. Commun. ACM, 5(6):345, 1962.
Santo Fortunato. Community detection in graphs. Phys. Rep., 486(3):75-174,2)
10

---

Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred K Warmuth. Using and combining predictors that specialize. In Proc. STOC, pages 334-343, 1997.
Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In Proc. COLT, pages 176-196, 2014.
Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Soc. Ind. Appl. Math., 9(): 551-570, 1961.
Kilian Hendrickx, Lorenzo Perini, Dries Van der Plas, Wannes Meert, and Jesse Davis. Machine learning with reject option: A survey, arXiv preprint urXiv:210..1127,, 2021.
Mark Herbster and Guy Lever. Predicting the labelling of graph via minimum p-seminorm interpolation. Proc. COLT, 2009.
Mark Herbster, Stephen Pasteris, Fabio Vitale, and Massimiliano Pontil. gang of adversarial bandits. In Proc. NeurlPS, pages 2265-2279, 2021.
Paul Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Soc. Netw., 1(2):109-137, 1983.
Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. A survey on the densest subgraph problem and its variants. ACM Comput. Surv., 56(8): 2024.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http:
waanap.stanfi ord edw/dataa edaaa//aaa June 2014.
Haipeng Luo and Robert E Schapire. Achieving all with parameters: Adanormalhedge. In Proc. COLT, pages 1304, 2015.
Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Proc. COLT, pages 5030-3048, 2020.
Mark E.J. Newman and Michelle Girvan. Finding and evaluating community structure in networks.
Phys. Rev. E, 69(2):026113 13, 2004.
Stephen Pasteris, Madeleine Dwyer, Chris Hicks, and Vasilios Mavroudis. A hierarchical nearest neighbour approach contextual bandits. arXiv preprint arXiv:2312.093322 2023a.
Stephen Pasteris, Chris Hicks, and Vasilios Mavroudis. Nearest neighbour with bandit feedback. In Proc. NeurIPS, 2023b.
Ignacio M. Pelayo. Geodesic Convexity Graphs. Springer, 2013.
Shota Saito and Mark Herbster. Multi-class graph clustering via approximated effective p-resistance. In Proc. ICML, pages 29697-29733, 2023.
Nicolas Schreuder and Evgenii Chzhen. Classification with abstention but without disparities. In Proc. UAI, pages 1227-1236, 2021.
Yevgeny Seldin and Gábor Lugosi. lower bound for multi-armed bandits with expert advice. In Proc. EWRL, volume 2, page 7, 2016.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Mag., 29(3):93-93, 2008
Aleksandrs Slivkins. Contextual bandits with similarity information. In Proc. COLT, pages 679-702, 2011.
Maximilian Thiessen and Thomas Gärtner. Active learning of convex halfspaces on graphs. In Proc. NeurIPS, 2021.
Vincent A Traag. Faster unfolding of communities: Speeding up the louvain algorithm. Phys. Rev. E. 92(3):03200, 2015.
Marcel LJ van De Vel. Theory of Convex Structures. Elsevier, 1993.

---

A CBA analysis
Here we prove Theorem 3.1 from the modification of mirror descent (and the specific construction of 9t) given in Section 4 Whenever we take expectations in this analysis they are over the draw of as from 8, for some E [T] As for mirror descent, our analysis hinges on the following classic lemma:
Lemma A.1. Given any convex set C C R _ with:
any convex function & R - R, any q C and any
= argmin DEC +(v,
then for all u E we have:
((u) + uu, 2) 2 E(g) +
Proof. Theorem 9.12 in Beck 2017 shows that the theorem holds if A is Bregman divergence. In our case A is indeed a Bregman divergence: that the convex function f: Rf + for all v E Rf defined by:
f(v) Σ In()), VE
which concludes the proof.
Proof of Theorem 3.7 Choose any u E V and E [T]. We immediately have V S V2 by definition, and therefore E V.. Hence, by setting such that [(v) == 0 for all R setting C V and setting& z = wt in Lemma A.1 we have w so that:
(uu w.) 2 A(u, w..)
Alternatively, by setting such that {(v) 19. (wt v) for all v E RR, setting C = R and
setting z = W. in Lemma A.I we have Wr+1 so that:
n9: (w, u. + (uu w 19: (w, - 11++1) + wi+1).
(4)
Since Egg, (vr(w: and pr linear have:
Elg. (w, u)] pe ((( (u)).
(5)
In what follows we use the fact that for all < we have:
x(1 - exp(x)) 2 2x.
(6)
For all E [b]. we have, by definition, that 9t, ei A; so by Equation we have:
9. (w: w1+1)
Σ si r. exp(nee f.)).
RE(E)
Since, for all E [K]. we have Pro < 1 and hence, as r and, for all E [b] we have ||ei|| S 1. we can invoke Equation (6), which gives us:
n9. (w, w(+1)
Σ xE(F)
wrs (ne) -f))
(7)
By definition of i, we have, for all E [L], that:
e) r, ||e|ll + ar (1 - -r, //.,0)/81.. S 01, + 20l /8,,
so that since, for all E [K]. we have Pr(a. = a) = 8t,a we also have:
Ei(e) +. ). of, + Σ (2, + 4(e),a) /
(8)
aE[K]
Since, for all E [E] and a E [K]. we have etaa < and ct, S 1 and hence also ef S Ct2 we then have:
El(e +,) < (2K + 1) + Σ caa/
(9)
KE
12

---

Note that since w E V. we have:
Σ EE
Br S 1.
(10)
Also, by definition 8 we have:
Σ
Wi. Σ
/
Σ
Σ
wr
Σ
1
St,a
=
K
(11)
$t,a
St,e
aE[K]
[E|K]
sE[B]
aE(K]
Multiplying Inequality by thes. summing over all i [E], and then substituting in Inequality I00 and Equation [II
gives us:
Wr Blee 9.) S (2K + 1) 4K 6K +
(12)
Taking expectations on Incquality and substituting in Inequality
(after taking expectations)
gives us:
E(ng. (it, w 2 (12K + 2)
(13)
Taking expectations (over the draw a, se) on Inequality 4 substituting in Inequalities (3). and and then rearranging gives us:
A uu, w,) E[ (u, W++1)] 2 n(p((u) Pe (,(w)) 1f2K +
Summing this inequality over all t E [T], taking expectations (over the entire sequence of action draws) and noting that Á (u, WT+1) > 0 gives us:
Auu w1) 2 21 Σ Elpi(u) pr( 17 (12K + 2)T
[E|T]
Substituting in Equation ① and rearranging then gives us, by definition of p and Pt, the required goal:
E[re,a. 2 E[p(u)] - A(u,ww)/m (12K + 2)T.
(E|T]
A.1 Unbounded precision case
We will now show how to handle the case in which our numerical precision is unbounded, incurring time complexity equal, up to a factor logarithmic in T, to that of Exp4 and adding only to the regret. This additive factor, however, can be made arbitrarily small.
Let restrict ourselves compare against with || S Z for this always has to be the case when each expert has confidence of at least 1/2 on some trial. Our time complexity will be logarithmic the unnormalised relative entropy) w, into the set {u E R | S 2 which simply requires clipping its components. Since the set {v E R ||> oc S Z) convex and contains our comparator this will not affect our regret bound.
arbitrary Z. Note that
Z. At the beginning of trial we will now project (via
For any 9 R let (g) be the set of all with v C2 q. We note that given, for all [T], value E [i 1/T, 1] we have that there exists ú E n. V:(g:) such that the cumulative reward of π (f) is less than that of π (u) minus This means that, any trial i. we can, instead of projecting into the set Ve, project into the set Vz(g:) for some E -1-11 1/7, and add no more than one to the regret (by considering as the comparator instead of u).
So the problem (for the projection step at time if necessary) is now to project into the set of all {v) v qe for some arbitrary qe [1 - 1/T, 1]. Following use of Lagrange multipliers, this means that we need to find À > 0 with Σ, C2,5 (cp()) E 111-1/1 1/T, So consider the function ff defined by f(X') == Σ; c, exp(-X'ct,).
Consider X' Ct < 1/ZE then W, exp( -Xx,)) < C,,Wi,
ZE Zn((EE) and take any
[E]. Since Wi,i S Z we have that when
1/E and that when Ct. > 1/2E then cxpp(XX/ZF) = 1/F.. This implies that s(X) S and hence (since W, exp( -X),,) &
monotonic decreasing) an acceptable À lies in [0, ZE In ())))).
13

---

Algorithm 2 QUERY(Q)
1. For all i E [n] U [0} let v/ be the ancestor of q at depth in
2. Set on <- (1%)))(%))
3. Climb D from 7n to %o- When at 7/s do as follows:
(a) 76+1 <(7)) then set + ((7))( + ((o())))(())))
(b) 7++1 ((%) then set o; t 0(7))0441
4. Return 0o
For general X we note that vf(() -, G.
wr, , exp(-Xe,) -f()). This means that T/T. 1] is 1/T this means that the length of the interval containing acceptable values of À is at least 1/T.
[V)()) I 1. Since the length of the interval
So have shown that either À ZE (ZE)) is acceptable or the range of acceptable values of is of length 1/T and lies in [0, ZE EnIn(2 ( E)] (which has length Z In( 2 E)). The ratio of these lengths is 7 ET (n(ZE) EE) interval bisection will find acceptable value of X in (lIn(Z ((][(TTTn(ZE))) (II(EZT)) steps.
So we have time complexity OEEK E E'n ElIn(EZT)) and we have only added 1 to the regret (although this additive factor can be made arbitrarily small).
B Efficient implementation proof
We here prove the time complexity of Theorem 5.3 The per-trial time complexity of a direct implementation of CBA for this set of experts would be (2K We now show how implement CBA in a per-trial time of only O(KN In(N)). To do this first note that of generality, that for all g, 2, X with + we have x(q,x) & d(g, z) since ties can be broken arbitrarily and balls can be duplicated.
assume, without loss
Given æ, 2 E X' a [K] and E [T] we let (1, == W1s and (2, 2) == Wt where i the index of the expert corresponding to the ball-action pair with ball: {q E X ddx,q) S d(x, 2)}, and action a. Given z, E let E(x, 2) == {q X d(x, q) 2 d(x,
] 2[x
is straightforward derive
the following equations for the quantities in CBA at trial & [T]. First we have:
||a/l|1 ΣΣ Σ
(1,0(1
#E SEX] =EE(z,a.)
For all x, X and E [K] we have the following:
If cc | 1 or E(x, then (1, (x. =)=
If [c and E (x,22) then Fr, (2, 2) = Vt.a (I, 2)/1
For all E [K] we have:
St.a = Σ Σ
Ve 2).
DE =EE(s,a.)
Finally, for all x E X' and E [K] we have the following:
Vrtaa (z, z) (r (æ, z) exp(ne) P.) if a E (x,
if & ((x,,1)
y(- 1(-11)a(2,
Hence, to implement CBA we need, for each I E X' and a E [K], data structure that implicitly maintains a function h IR+ and has the following two subroutines, that take parameters q E X and R..
1. QU) Compute Exe((eg) h(2).
2. UPDATE((,P)) P): Set h(2) + ph(z) for all = E E(x, q)-
Now fix E X' and [K]. Let h be as above. On each trial / E [T] and for all E X, h(z) will start equal to (r, 2) and change to ir. (ær, 2) and then ((41),a (ar, 2) by applying the UPDATE subroutine.
14

---

Algorithm 3 UPDATE(Q.P)
1. For all i E [n] u {0) let y be the ancestor of q at depth in
2. Descend D from 70 -n-1- When at Y set:
(a) ((4(%))
((7))((4()))
(b) ((p(n)) t ((%))(((()))
(c) ((%) +
3. For all [n- 1--11 U (0), if 741 = a(%) then set ((p(1))) + po(((T)))
4. Set 6(%) pp((7)
5. Climb D from 7n-1 to 7o. When at 7/s set:
v(*)) + ((<()))) + (P(())))((((1))
We now show how to implement these subroutines implicitly in a time of (In(NN) as required. Without loss of generality, assume that N 2n for some N. Our data structure based on balanced binary tree DD whose leaves are the elements of X' in order of increasing distance from r. X we have that (z, 2) is the 2. Given node v E D we let fr(v) be the set of ancestors of v and let (1) be the set of all 2 E X which are descendants of v. For any internal node v let <(v) and (()) be the left and right children of respectively.
This implies that for any
leaves that do not lie the left of
We maintain functions o D I such that for all 'D we have:
(v)
II <(v') En)(w)
Σ
h(2).
(14)
=EV(O)
The pseudo-code for the subroutines QUERY and UPDATE are given in AlgorithmsZand respectively We now prove their correctness. We first consider the QUERY subroutine with parameter & E X. From Equation (14) we see that, by (reverse) induction on E [n]] (0), we have:
II o(v') = Σ h(z).
J
V'EM
ZEV(TEINE(MM)
Since %o is the root of D, we have on == h(2) required. Now consider the UPDATE subroutine with parameters X and p E 14.. Let h be the implicitly maintained function before the subroutine is called. For Equation (14) to hold after the subroutine is called we need:
1v(v)
II
<(0')
Σ M(z).
(15)
(n))
=EU(O)
where for all E X have:
l()))= 1= & (x, ()]l(=)=))))))))))))()))))))(( + Ia E E(x, 4))pp(z))
We shall now show that Equation (15) does indeed hold after the subroutine is called, which will complete the proof. To show this consider each step of the subroutine in turn. After Step 2 have (via induction) that:
we
For all v E 1())) we have d(v) = 1.
For all e E D (q) we have:
(b)))
II 0(v)=
Σ h(z). =E((v)
eEf(()
So, since E(x, 9) is the set of all E X' that do not lie to the left of in D we have that, after Step 4 of the algorithm, the following holds:
For all v E (g) we have d(v) 1
For all v E D (1()) we have:
II ((v'= Σ M(z). SE((E)
v'Ef(())
Hence, by induction, have that, after Step of the algorithm, it the case that for all E (g())
have: vb()) = Exe(()) 1z((). So since Φ(v) for all E (g) and Step does not alter d(v) or
(b) for any D (g)) we have Equation 15
15

---

C Lower bound proof
Proposition C.1. Take any learning algorithm. Given any basis B and any M E N then for any sequence of disjoint basis elements (BN 1 (M]) there exists a sequence of corresponding actions (b, [K] (M) such that an adversary can force:
ΣΣ JE[M]
Ix E Byllr
Σ EE[T]
Brra ((VMKT)
Proof. In this scenario, at each time step, either single expert (i.e., the basis element containing the current context 2ạ) is active, making predictions based on its label, or no expert is active, prompting the learner to abstain and thus incur zero reward cost.
Therefore we define T' (t [T) Eje My [ E B,] 1} as the of timesteps in which the learner going to play. Since the concept of abstention that our algorithm not going to pay anything for the timesteps in which we abstain, we can see that:
ΣΣ Ioa B,lrr,b. (E(TJE[[M]
Σ LE12]
Blread
Σ TET
rt.by
Σ Blre,as) LET
For any ball j E [M], we define Tj (t [T E Bj]}. Following the ideas of Seldin and Lugosi [016]. for any of the sets T, we can create multi-armed bandit instance as the one described in the lower bound by Auer et al. [2002]. Note that in the lower bound construction, the abstention arm would be a forehand known suboptimal arm, which results a lower bound of the
V2-1 > O. Since the presented context 2G is chosen 32/333 adversarially at each time step, can ensure that each basis element is activated for /T' time steps, obtaining:
order c/ (K - 1)T, for the constant
El[r,a.]
Σ c (K 1)|Ty|
Ts
jEIM]
SETY
NETY
jEIM
Σ jE[M]
= MC - 11]7"
As we can choose |T'] be any fraction of T, we end up with the desired lower bound of the order Q(VMKT) which matches, up to logarithmic factors, the cumulative reward bound presented in Theorem 5.3
D Overlapping balls extension
In this section, we present the theorem that allows to present the results of overlapping balls as expressed in Section 5.2 Note that Theorem 5.3 the special case Theorem D.Iwwen the balls are disjoint and u, for all E [M].
Theorem D.I. Let M E N and {(B,, by, Ii E [M] be any sequence such that B, is a ball,
by E [K] is action, and uj E 00, 1] such that for all X we have:
Σ Ix B,lu, $ jEM
For all E [T] define:
=
Σ JE(M]
[r, E Byllureny
16

---

which represents the reward of the policy induced by {BB, by. uy)l E [M]] on trial t. The regret of CBA, with the set of experts given in Section 5.2 and with correctly tuned parameters, is then bounded by:
Σ EE(T]
Bl EO
[n(KKN)T
Σ Uj jE[M]
TE(T]
Its per-trial time complexity is:
O(KNIn(N)
Proof. Direct from Theorem 3.1
using the experts (with efficient implementation) given Section
5.2
E
The details of the graph bases
This section expands the definition and explanations for the bases we used in the Experiment. Remember that we refer to any set of experts that correspond to set-action pairs of the form (B, k) e 2 x []] as a basis elements, and a set of basis elements as basis.
E.1 p-seminorm balls on graphs
As we see in Sec. 5.2 the CBA seems to work only for vector data. However, in the following sections, we explore how our CBA algorithm can be applied to graph data by creating ball structure over the graph.
We first introduce the notations of graph. A graph is a pair of nodes V [N] and edges E. An edge connects two nodes, and we assume that our graph is undirected and weighted. For each edge {i,j} E, we denote its weight by Cij- For convenience, for each pair of nodes i with {i.j} E, we define Cij- O.
To form a ball over graph, family of metries particularly interested in is given by p-norms on a given graph G. Let
1/p
dpli.))== :
min MERN
Σ Coelus uel"
(16)
..VV
which is well-defined metric for p E oo) if the graph is connected and may be defined for p = do by taking the appropriate limits. When between nodes and j which comes from interpreting the graph as an electric circuit where the edges are unit resistors and the denominator of Equation (I6) is the power required to maintain unit voltage difference between u and [Doyle and Snell 1984]. More generally, dp (i, (i.)). is known as peefffective) resistance [Herbster and Lever 2009 Alamgir and von Luxburg 2011 Saito and Herbster 2023). When p E [1, 2, jo there are natural interpretation of the p-resistance. In the case of p= we have that the effective is equal to one over the number of edge-disjoint paths between i and j which is equivalently one over the minimal cut that separates from j. When p = 2 it the effective resistance discussed above. And finally when p do have that do is the geodesic distance (shortest path) between and j. Note that, interestingly, there are at most 2/V distinct balls for d1: as opposed to the general bound O on the number of metric balls. This follows since dj is an ultrametric. A nice feature of metric balls is that they are ordinal, i.c., we can take an increasing function of the distance and the distinct are unchanged. The time complexity for each ball is as follows. For di ball, we compute every pair of distance in (NV3) using the Gomory- -u tree [Gomory and Hu 1961]. For de ball, is actually enough to compute the pseudoinverse of graph Laplacian once, which costs O (NV) [Doyle and Snell 1984 For d ball, we can compute every pair of distance in ((N3) by Mlodd-Warhha algorithm Floyd 1962
this is the square root of the effective resistance circuit
E.2 Community detection bases
In this section, we consider only bases formed via set of subsets (a.k.a clusters) C C 2 Each of these subsets induces K basis elements: one for each action [K]. Specifically, the basis element
17

---

3: [M] + [Kn] corresponding to the pair (C, a) is such that ((x) is equal to whenever C' and equal D otherwise. Hence, in this section, we equate a basis with a set of subsets of [NT]
We can compute a basis for a given graph G = (V. E) using community detection algorithms. Community detection is one of the most well-studied operations for graphs, where the goal is to find a partition {Ci,.... Cg} of V (i.e., - C, = V and C, n C3 = Ú for i * j) so that each C, is densely connected internally but sparsely connected to the rest of the graph (Fortunato 2010 There are many community detection algorithms, all of which can be used here, but the most popular algorithm the Louvain method [Blondel et al.) 2008 We briefly describe how this algorithm works. The algorithm starts with an initial partition {10} v E V and aggregates the clusters iteratively: For each e E V. compute the gain when moving v from its current cluster to its neighbors' clusters and indeed move it to a cluster with the maximum gain (if the gain is positive). Note that the gain is evaluated using modularity, i.e., the most popular quality function for community detection [Newman and Girvan] 2004). The algorithm repeats this process until no movement is possible. Then the algorithm aggregates each cluster to a single super node (with appropriate addition of self-loops and change of edge weights) and repeats the above process on the coarse graph as long as the coarse graph is updated. Finally, the algorithm outputs the partition of V in which each cluster corresponds to each super node in the latest coarse graph. Note that it is widely recognized that the Louvain method works in O(N log N) in practice (Traag 2015).
To obtain a finer gneiner basis, we apply the so-called greedy peeling algorithm for each C2 in the output of the Louvain method. For C; C V and v E C,, we denote by dc, (v) the degree of v in the induced subgraph G(C)). For G[C;], the greedy peeling iteratively removes node with the smallest degree in the currently remaining graph and obtains sequence of node subsets from C, to a
singleton. Specifically, it works as follows: Set j + |C,] and cf + -Cs. For each j = C.ll..., 2, compute Umia E arg min(d data structure, this algorithm runs in linear time [Lanciano et al. 2024).
(v) V E C(O) } and c(i-1) c(U) {umin Using a sophisticated
In summary, our community detection basis is the collection of node subsets (c,0) | 1, ,,..,,9.. .4.
1, I...., } together with {{v} U e V} for completeness.
E.3 Graph convexity bases
alternative to metric balls and communities are, for example, (geodesically) convex sets in a graph. They correspond to the inductive bias that if two nodes prefer the same action, then also the nodes on a shortest path between the two tend to prefer the same action. Geodesically convex sets are well-studied [van De Vel 1993 Pelayo 2013) and have been recently used in various learning settings on graphs [Bressan et al. 2021, Thiessen and Gärtner 2021]. Similarly to convex sets in the Euclidean space, set C' of nodes is convex if the nodes of any shortest path with endpoints in C' are in C, as well. More formally, the (geodesic) interval I (u, v) = {ar E V : x is on a shortest path between u and v} of two nodes and contains all the nodes on shortest path between them. For set of node A define I (A) = La b) as a shorthand notation for the union of all pairwise intervals in A. A set A is (geodesically) convex iff I (A) = A and the convex hull conv (A) of set A is the (unique) smallest convex set containing A. Note that for u, E V, I(,, v) and conv ([u, u}) are typically different sets. Indeed, /(u,e) v) is in general non-convex, as nodes on shortest path between two nodes in 7u, v) (except for u. u) are not necessarily contained in [(,,,), As the total number of convex sets can be exponential in N, e.g., all subsets of a complete subgraph are convex, we consider the basis consisting of all intervals: 1 [u, v) for u, e E [N]. This involves O(N2) basis elements, each of size (NV). With a simple modification of the Floyd Warshall [Floyd] 1962] algorithm, computing the interval basis takes (N3)) time complexity.
F Additional experimental results
We thoroughly explored various configurations for the three graphs described in our experimental setup in Section [6) We run our experiments with an Intel Xeon Gold 6312U processor and 256 GB of RAM ECC 3200 MHz. displasss different settings for the number of nodes each clique and noise levels.
18

---

As we compare the computational complexity of each basis in Section E and the main results, the most intense computational load in the experiments will arise from the calculation of the basis, which can be seen as an initialization step in our algorithm. The proposed methods have varying computational complexities, and an arbitrarily complex function can be employed to compute the basis. Remark that, in the usual complexity comparison among online learning algorithms using experts, we compare the complexity given the experts. Practically, we use pre-computed bases or even human experts. Also note that due to the expensive complexity of the p-balls and the convex sets seen in Section
we only conduct the LVC for LastFM Asia.
In Figure 4 we present multiple settings for generating the Gaussian graph. Here the title of each plot "Foreground 2,y; Background x' y/; k-NN," which explained as follows: represents the number of nodes in each foreground class, x' represents the number of nodes in the background class, y represents the standard deviation of the Gaussians generating the foreground class, y represents the standard deviation of the Gaussian generating the background class, and & represents the number of nearest neighbors used to generate the graph.
In Figure [] we present the various labels chosen as noise for the Cora graph. In Figure 2cc) we presented the averages of all these different configurations. Here, we can see that the main behavior of the various bases is roughly maintained independently of the different labels chosen to be masked as background class.
we present the various labels chosen as noise for the LastEM Asia graph. This graph comprises nodes representing LastEM users in Asian countries and edges representing mutual follower connections. Vertex features are extracted based on the artists liked by the users. During this initial analysis, arbitrarily chose three out of eighteen possible labels to serve the background class. In Figure 2(d) we presented the averages of all these different configurations. Varying the chosen background classes also produces different results, this indeed due the inherent lack of noise in the dataset. It is nice to see that regardless of the noise labels chosen, the behavior of our algorithm is always good, showing, as expected, that based the amount of noise, we can just improve.
In Figure 6
19

---

nodes
Clouus nodas
D1
D-INF
LVC
2003
Mizakes
GARA
Wicakes
Mistakos
EXP3
2000
1000
10:0
nodes
rodes
800
0003
12000
Mictakes
Miczaess
60.00
1100
2103
6000
1200
100.0
12000 SHIES
Time
Time
Time
Figure 3: Stochastic Block Model results, dotted lines represent different baselines, while solid lines are used to represent various results.
20

---

Foregro.nnd 40,0.: Eground 120, 1.2:5-N
Foreground 40,0 Bec Background 120, 1.25:7-NN
Foregroand 40,02: Background 12:51.7
4003
4203
Mizlakss
J002
INT
Missakss
Mistakas
20.9
Casim
EXP3
1003
1009
1080
1005
2003
2003
4000
3900
1005
2003
2000
40000
5000
1005
2003
2000
4000
5000
Time
Tirme
Timee
Foreground 40,0.2; Background 120, 1.7/7-NN
Foreo ound 80,0.2; Background 240, 1.25:5NN
Foreground 80,0.2 Background 1.257725
2003
6000
5000
Mistakas
Mistakas
1000
2000
2003
6000
Forog 80.0.2. Background 1.7.5.N
Foroo Background
Faroground 160.0.2. Background 1.2.5.N
11500
15089
12590
Mitalas
Mistakes
00099
0200
11:33
11.03
2500
Time
Time
Time
Foreground 160.0. Background 1.25:7
160.0.2
480
Foreground 160.02 Background 4SC. 19751.75.77MM
9.00
10094
15250
2000
10299
19099
20000
9.0
10090
15290
2000
Time
Time
Time
Figure 4: Gaussian graph results, dotted lines represent different baselines, while solid lines are used to represent various results.
21

---

(0.
(0. 4)
D1
20099
20003
17589
17500
LYC
GABA
Mistakss
CaSim
Time
Time
Cora, labels (0. 4) noise
Cora. labels 3, nuise
2008
17500
17500
15003
15000
12982
12555
Mtstalees
10089
20.90
2240
5233
12400
Time
Time
Figure 5: Cora results, dotted lines represent different baselines, while solid lines are used to represent various results
22

---

LastrM, labels (2. 4, 6) noise
LastFM, labels (9, 15. 7) as noise
.6stFM, latels {0, 3) as noise
GABA
60000
EXP3
30080
30000
Mictakes
00000
40030
10000
20000
10000
30000
20000 30000 ibico 50630 50000 TOCC0 30000
50000 23303 s00ce aceez socce sccor 70000 00000
0 33000 20000 30000 ab0co 50000 e0000 75003 80000
Time
Time
Time
Las labels (16. 17. 103 as noise
LestFM, labels {16. 1. 15) as noise
70000
2000
60000
10030
50000
Mistales
63030
30900 2000 30000 aoto 33020 /00t2 50000 Time
2000 23302 st0te actet so0ce socce N000 20000
Time
Figure 6: LastFM Asia results, dotted lines represent different baselines, while solid lines used represent various results
23

---

Impact Statement
Given the theoretical nature of our work, we cannot foresee the shape of positive negative societal impacts which this work may have in future.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All the claims are supported in the main body.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
be expected to generalize other settings.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations and future work are discussed in the introduction and in the experimental results analysis.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well vell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We explicitly write the assumptions of all the theoretical claims.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provided the experimental codes.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
25

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We cited the datasets which use in the experiments. Also, these datasets are publicly available and widely used in the community.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cd
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
httpi///ggudeee/eeeuuuuuiaiiai gwwiessgguui//eeeeeeeeeo Cooeeeoodeeeeeeee iistiissionnn ssionnolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We provided the details in the main body as well as in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We provided error bars and did statistical tests in the main body.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We explicitly write the computing resources we used in the experiments the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have read and followed NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We provided the dedicated section for this.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We used the datasets that are widely used in the community.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, thcoe com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
28

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "9poFmVXe6a", "reviewer": "Reviewer_Edre", "summary": "This paper first considers the problem of bandits with expert advice, allowing the learner to abstain in any round. It introduces an algorithm, CBA, based on mirror descent, which can achieve a better cumulative regret bound in comparison with EXP4.\n\nThe algorithm is then applied to adversarial contextual bandits, where the learner abstains in rounds where the given context is not covered by any expert. The paper provides upper and lower bounds on the cumulative reward, and details a more computationally-efficient implementation for settings where the contexts have inherent structure.", "questions": "- Following Theorem 3.1, can you provide a concrete example where $|| u ||_1 = E$. The example given in the footnote seems to require all other experts to have confidence $0$ in the round where the expert has confidence $1$. What conditions need to be imposed on the set of experts?\n\n- In Corollary 5.1, can $M$ be any number in $\\mathbb{N}$ for the sequence of basis elements to be disjoint?\n\n- How are the corresponding actions $b_j$ chosen?\n\n- In Section 5, what are the specific benefits of allowing the learner to abstain?", "limitations": "It would be nice if the authors include a separate section/paragraph that discuss the limitations in detail.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Online learning with abstention is an interesting and relevant problem for the community, and the extension of CBA to adversarial contextual bandits with abstention seems novel. \n\n- The paper presents reward bounds for both the bandits with expert advice problem and the adversarial contextual bandit problem. These bounds can improve upon those of existing algorithms. A lower bound is also provided for the latter setting.\n\n- The experiments offer some insights into the construction of basis functions for contextual bandits with abstention.", "weaknesses": "- The paper can be quite difficult to follow at times. For instance, in Section 5, the discussion about covering foreground and background classes seems very abrupt. I understand this is mentioned in the introduction, but since the problem settings are formally introduced until later, the initial discussion is also confusing. In addition, the purpose of the experiments remains somewhat unclear to me -- they are not properly discussed, and there is this sudden change of theme from learning in bandits with abstentions to constructing basis functions for various graphs. I also find the contextualization relative to prior work somewhat inadequate -- there are not enough details about the SpecialistExp algorithm to make the comparison concrete (lines 215 - 223). See also questions below.\n\n- The improvement of CBA over EXP4 is somewhat vague and seems to largely depend on the set of experts. It would be nice if some concrete examples are provided.\n\n- There is an $\\mathcal{O}(\\ln |\\mathcal{B}|)$ gap between the upper and lower bounds in Section 5, which is substantial as $|\\mathcal{B}|$ can be exponential in the size of the set of contexts.\n\n- There seems to be a lack of discussion on the intuition behind why CBA should be applied for adversarial contextual bandits with abstention in this particular way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper.\n\n>[...] $\\log|B|$ gap and $|B|$ can be exponential in the number of contexts $N$. \n\nWhile the comment is true, $|B|$ can indeed be as large as $2^N$ in principle, such a large basis set would defy its purpose (as an inductive prior on the shape of the clusters). All the basis sets we consider have size $|N|^2$, thus, the $\\log|B|$ gap is just logarithmic in $N$. Generally, we think of $B$ as a set of “simple” stereotypical sets, which, for example, can be quantified by assuming $B$ has finite VC-dimension. In that case $\\log|B|=\\mathcal{O}(\\mathrm{vc}(B)\\log N)$ the dependence is still logarithmic in $N$ by the Sauer lemma. \n\n>[...] there is this sudden change of theme from learning in bandits with abstentions to constructing basis functions for various graphs [...] There seems to be a lack of discussion on the intuition behind why CBA should be applied for adversarial contextual bandits with abstention in this particular way.\n\nA natural application of experts, and therefore confidence-rated experts, is adversarial contextual bandits with a finite context space. In this setting, it is quite common in the literature (e.g., [1], [2]) to consider a graph structure over the contexts. Therefore, we decided to study a practical application of confidence-rated experts, where the experts, in our case, are the basis elements we introduce.  We will improve the exposition here in the final version.\n\n[1] Cesa-Bianchi et al. \"A gang of bandits.\" NeurIPS 2013.  \n\n[2] Wu,  Qingyun, et al. \"Contextual bandits in a collaborative environment.\" SIGIR 2016.\n\n> [...] there are not enough details about the SpecialistExp algorithm to make the comparison concrete (lines 215 - 223). See also questions below.\n\n We shall add the regret bound of SpecialistExp to the paper. The difference is that while our regret is $\\mathcal{O}(\\sqrt{MKT\\ln(N)})$ where $M$ is the number of disjoint basis elements that exactly cover each of the foreground (non-abstention) classes, the regret of SpecialistExp is $\\mathcal{O}(\\sqrt{M’KT\\ln(N)})$ where $M’$ is the number of disjoint basis elements that cover each of the classes (including the background/abstention class). As depicted in Figure 1, $M’$ can be much larger than $M$.\n\n> In Section 5, what are the specific benefits of allowing the learner to abstain?\n\nThe benefits of the abstention action are clear when dealing with contexts (and therefore nodes in graph-structured contexts) that do not have a behavior that reflects the inductive bias. In Figure 1 of the provided example, you can think of any point in white as being colored in any possible way, but we would need a ball that covers any of these points as in SpecialistsEXP. Therefore, abstaining avoids having to deal with points that present “unnatural” behavior with respect to our inductive bias.\n\n> Following Theorem 3.1, can you provide a concrete example where $||u||_1=|E|$. The example given in the footnote seems to require all other experts to have confidence 0 in the round where the expert has confidence 1. What conditions need to be imposed on the set of experts? \n\nAssuming each expert has confidence 1 on at least one trial (otherwise $||u||_1$ could be much higher) then $|E|$ is the maximum possible value of $||u||_1$. The condition for having such a value of $||u||_1$ is that the sum of the confidences of all experts are, on any trial, no greater than $1$. Such a $u$ is not that interesting - we place equal weight on each expert - but it was introduced in order to show just how high $||u||_1$ can be, so that the potential degree of improvement over Exp4 is huge. Things are much more interesting at slightly lower values of $||u||_1$.\n\n> In Corollary 5.1, $M$ can be any number $\\mathbb{N}$ in for the sequence of basis elements to be disjoint? \n\n$M$ corresponds to the number of basis elements in the comparator. Hence, as we assume the basis elements to be disjoint in Corollary 5.1., $M$ is only restricted by the size of the number of contexts $|\\mathcal{X}|$ and the size of the basis $|\\mathcal{B}|$. We will clarify this in the final version.\n\n> How are the corresponding actions $b_j$ chosen? \n\nThe $b_j$ are simply the actions in the comparator sequence. The result holds for an arbitrary such sequence.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PvVCGa3ebW", "reviewer": "Reviewer_BsH5", "summary": "The paper considers the problem of prediction advice under the bandit framework.\n\nThere are $K$ arms plus a special $(K+1)$0-th arm, which always incurs the gain of 0; this arm may be interpreted as the action of abstaining. The learner outputs a distribution over $K+1$ handles and earns the scalar product gain. In other terms, the learner outputs a vector of $K$ non-negative components summing to a number between 0 and 1; the sum can be though of as the measure of its confidence.\n\nFor this setup, the problem of prediction with expert advice is considered and a bound is obtained. There are two terms in the regret, one involves KL-divergence (there is a class of prediction with expert advice bounds of this kind) and the other has the form $O(\\eta KT)$. It is seemingly linear, but $\\eta$ can be tuned to get sublinear growth.\n\nThe result has been applied to the framework with side information $x_t$. Each expert is associated with a pair $(B,k)$. Whenever $x_t\\in B$, the expert bets everything on arm $k$ and is abstaining otherwise. \n\nThe main result of the paper is applied to this scenario with finitely many experts based on disjoint balls and a matching lower bound is obtained.\n\nThe case where $B$s are balls in a metric space is considered separately.", "questions": "None", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I think this is a very interesting result in prediction with expert advice.", "weaknesses": "No obvious weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the very encouraging feedback!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LclcVq3XTa", "reviewer": "Reviewer_3cAo", "summary": "This paper investigates the problem of prediction with expert advice in contextual adversarial bandits, introducing the CBA (Confidence-rated Bandits with Abstentions) algorithm, they apply CBA to adversarial contextual bandits and achieve near-optimal upper regret bound.", "questions": "Q1: Why not consider the reward of the abstention action to be non-negative instead of zero?\n\nQ2: What is the novelty in the proofs?", "limitations": "The algorithm is not as efficient as Exp4 and the upper bound does not include the approximation error of $\\lambda$.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The CBA in adversarial contextual bandits achieves near-optimal upper regret bound.", "weaknesses": "Weakness 1: This algorithm is not as efficient as Exp4.\n\nWeakness 2: In the algorithm, they mentioned using interval bisection to find $\\lambda$, but the regret upper bound does not include the approximating error of interval bisection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper.\n\n>Weakness 1: This algorithm is not as efficient as Exp4.\n\nGiven that the numerical precision of our machine is bounded, our algorithm has exactly the same $\\mathcal{O}(EK)$ efficiency as Exp4. See the additional result presented in the general rebuttal for our time complexity (equal to that of Exp4 up to logarithmic factors) when the precision is unbounded.\n\n>Weakness 2: In the algorithm, they mentioned using interval bisection to find $\\\\lambda$, but the regret upper bound does not include the approximating error of interval bisection.\n\nWe took the assumption that the degree of precision was bounded (the interval bisection method requires $\\mathcal{O}(\\ln(P))$ steps where $P$ is the precision. Thanks to your question, we attached a proof in the general rebuttal that removes this assumption. When the magnitudes of the components of the comparator u are bounded by some arbitrary value Z (which will typically be very small) we can achieve a time complexity of $\\mathcal{O}(EK+E\\ln(EZT))$ whilst only adding an additive factor of 1 (which can be made arbitrarily small) to the regret.\n\n>Q1: Why not consider the reward of the abstention action to be non-negative instead of zero?\n\nWe can have any range $[-a,b]$ with any $a,b > 0$ and the reward of the abstention action can be any fixed constant. This can be achieved by scaling and translating the reward (on any trial) when received - bringing it into the constraints of our paper (hence Thm 3.1 still applies but the regret term is scaled by some constant in $\\mathcal{O}(a+b)$). Such a scaling approach is standard in online learning.\n\n>Q2: What is the novelty in the proofs?\n\nOur proof borrows ideas from the analysis of mirror descent, EXP3, and the method of Lagrange multipliers (also with unbounded precision (see general comment)) . However, we note that the main novelty of our work was the realization that making such a modification to mirror descent would lead to true reward bounds for confidence-rated predictors. We note that mirror descent itself would not work as the constraint set is not known until after the last trial (and, even if it was known, computing the projections would be computationally hard).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xdgPabOtjb", "reviewer": "Reviewer_zGbq", "summary": "This paper considers the problem of prediction with expert advice in the bandit feedback setting with the possibility of abstention. The game is sequential: where in each round the each of $E$ experts gives a distribution over $K+1$ actions/arms. One of these actions represents abstention, yielding a reward of 0, while the remaining $K$ actions have rewards in $[-1,1]$ and are set by an oblivious adversary.\n\nThe contributions of this paper include a procedure called confidence-rated bandits with abstention (CBA), which is an adaptation of the well-known exponential weighted scheme. The authors present guarantees in the form of an upper bound on the expected cumulative regret. Additionally, they explore applications of the resulting algorithm in various other problems.", "questions": "How do your results compare to [1]?\n\n[1] Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Proc. COLT, pages 3030–3048, 2020.", "limitations": "See weaknesses section.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem under consideration is both interesting and practically relevant, as the ability for a prediction strategy to abstain is crucial in many scenarios, particularly when the risk of making poor decisions is high. Additionally, accounting for the context is a significant and pertinent feature of modern applications.", "weaknesses": "Overall, I find this paper unclear and difficult to read. The results obtained are not easily comparable to existing ones in the literature.\n\nFor instance, in the case of regret minimization with expert advice, such as the analysis of the EXP4 algorithm, regret is typically defined with respect to the best fixed expert in hindsight. The fact that the authors develop guarantees with respect to the best combination of experts (where this combination is not necessarily convex, since the set of vectors $u \\in \\mathcal{V}$, and $\\mathcal{V}$ as defined in line 123\nis not the set of convex weights) can be very confusing for the reader. The authors discuss comparisons with the guarantees of the EXP4 algorithm and state that \"The EXP4 bound essentially replaces the term $\\rho(u)$ in our bound by $\\rho(u)/u$\" in line 138. However, it is unclear how this translates in terms of worst-case guarantees. This part clearly needs a thorough discussion to be convincing.\n\nAdditionally, it is not clear how this work compares to previous research on online learning with abstention.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper.\n\n> The results obtained are not easily comparable to existing ones in the literature.\n\nOur results can be, for example, compared to EXP4 (see reply below) and SpecialistEXP (see e.g., our reply to reviewer Edre). In both cases we achieve at least the same bounds and in many cases achieve significantly better bounds. We will improve our exposition and a add a more thorough discussion and in the final version.\n\n>  For instance, in the case of regret minimization with expert advice, such as the analysis of the EXP4 algorithm, regret is typically defined with respect to the best fixed expert in hindsight. The fact that the authors develop guarantees with respect to the best combination of experts (where this combination is not necessarily convex, since the set of vectors , and as defined in line 123 is not the set of convex weights) can be very confusing for the reader. The authors discuss comparisons with the guarantees of the EXP4 algorithm and state that \"The EXP4 bound essentially replaces the term in our bound by $\\rho(u)/u$\" in line 138. However, it is unclear how this translates in terms of worst-case guarantees. This part clearly needs a thorough discussion to be convincing. \n\nYou are right in that both the reward of our algorithm and that of Exp4 are measured with respect to a linear combination of experts and for Exp4 that linear combination is required to be convex (i.e. the weights have to sum up to $1$). Typically the weights of our linear combination sum to some value $S$ far greater than $1$ (and never less than $1$). Hence (as the regret term limits to $0$) our reward is $S$ times that of Exp4. We will add this discussion to the paper for clarity.  \nThe fact that “Exp4 bound essentially replaces the term in our bound by $\\rho(u)/|u|_1$” is because Exp4 plays with the weight vector $u$ normalized at each time step and therefore operates in a stricter space.\n\n>The results obtained are not easily comparable to existing ones in the literature. [...] Additionally, it is not clear how this work compares to previous research on online learning with abstention. How do your results compare to [1]?\n\n> [1] Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Proc. COLT, pages 3030–3048, 2020.\n\nWe note that, to the best of our knowledge, there are no previous results on adversarial contextual bandits with the abstention option. The main novelty of the paper lies in merging the abstention action with confidence-rated predictors. This allows us to extend our result to (adversarial) contextual bandits with the abstention option. We introduce the first cumulative reward bounds on confidence-rated experts and we investigate contextual bandits as a potential application. Note that the cumulative reward bound we obtain is not achievable by previous work on confidence rated experts as they scale the regret by the confidence of the best expert in hindsight. We discuss previous results on online learning with abstention in the main body, but the previously considered settings are different from the ones we consider. Moreover, previous methods cannot be directly applied to confidence-rated predictors. Specifically, our results cannot be directly compared to [1], as their learning setting is different; it is a full information (in contrast to our bandit setting) binary classification problem.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their feedback. 

We are happy to provide an additional result that was prompted by a question from Reviewer 3cAo. The reviewer asked how the regret bound and efficiency are affected if $\lambda$ is not exactly determined but only approximated (we previously assumed bounded precision so we did not address this). We will now show that, even in this case, we incur a time complexity equal to that of Exp4, up to logarithmic factors, adding only 1 to the regret. This additive factor, however, can be made arbitrarily small. 

Let us restrict ourselves to compare against $\boldsymbol{u}$ with $u_i\leq Z$ for some arbitrary $Z$. Note that this always has to be the case when each expert has confidence of at least $1/Z$ on some trial. Due to this restriction, we can always project, at the beginning of trial $t$, $\boldsymbol{w}_t$ into the set {$\{ \boldsymbol{v} \mid v_i \leq Z \}$} which simply requires clipping its components.

For any $q\in\mathbb{R}$ let $\mathcal{V}_t(q)$ be the set of all $\boldsymbol{v}$ with $\boldsymbol{v}\cdot\boldsymbol{c}\leq q$. We note that given, for all $t\in[T]$, a value $q_t\in[1-1/T,1]$ we have that there exists $\hat{\boldsymbol{u}}\in\bigcap_t\mathcal{V}_t(q_t)$ such that the cumulative reward of $\boldsymbol{\pi}(\hat{\boldsymbol{u}})$ is no less than that of $\boldsymbol{\pi}(\boldsymbol{u})$ minus $1$. This means that as long as, on any trial $t$, we project into the set $\mathcal{V}_t(q_t)$ for some $q_t\in[1-1/T,1]$ then we will not add more than one to the regret.

So the problem (for the projection step at time $t$ if necessary) is now to project into the set of all {$\{\boldsymbol{v}\,|\,\boldsymbol{v}\cdot\boldsymbol{c}\leq q_t\}$} for some arbitrary $q_t\in[1-1/T,1]$. Following our use of Lagrange multipliers, this means that we need to find $\lambda^*>0$ with $\sum_{i}c_{t,i}w_{t,i}\exp(-\lambda^*c_{t,i})\in[1-1/T,1]$. So consider the function $f$ defined by $f(\lambda):=\sum_{i}c_{t,i}w_{t,i}\exp(-\lambda c_{t,i})$.

Consider $\lambda:=ZE\ln(ZE)$. Since $w_{t,i}\leq Z$ we have that when $c_{t,i}<1/ZE$ then $c_{t,i}w_{t,i}\exp(-\lambda c_{t,i})\leq c_{t,i}w_{t,i}<1/E$ and that when $c_{t,i}\geq 1/ZE$ then $c_{t,i}w_{t,i}\exp(-\lambda c_{t,i})\leq Z\exp(-\lambda/ZE)=1/E$. This implies that $f(\lambda)\leq 1$ and hence (since $f$ is monotonic decreasing) an acceptable $\lambda^*$ lies in $[0,ZE\ln(ZE)]$.

For general $\lambda$ we note that $\nabla f(\lambda)=-\sum_i c_{t,i}^2w_{t,i}\exp(-\lambda c_{t,i})\geq- f(\lambda)$. This means that $|\nabla f(\lambda^*)|\leq 1$. Since the length of the interval $[1-1/T,1]$ is $1/T$ this means that the length of the interval containing acceptable values of $\lambda^*$ is at least approximately $1/T$.

So we have shown that either $\lambda^*=ZE\ln(ZE)$ is acceptable or the range of acceptable values of $\lambda^*$ is of length approximately $1/T$ and lies in $[0,ZE\ln(ZE)]$ (which has length $ZE\ln(ZE)$). The ratio of these lengths is $ZET\ln(ZE)$ so interval bisection will find an acceptable value of $\lambda^*$ in $O(\ln(ZET\ln(ZE)))=O(\ln(EZT))$ steps.

So we have a time complexity $O(EK+E\ln(EZT))$ and we have only added $1$ to the regret (although this additive factor can be arbitrarily small).

Meta-review: This paper received a significant amount of attention from the reviewers, and we appreciate the authors for making a serious effort to address their concerns and answer questions. Overall, the paper was very borderline, but the most negative reviewer was largely concerned with the difficulty of comparing the method to previous methods, due to a distinction in how the comparator set is defined. I looked into this more carefully, and I don't believe the comparator class is a problem. Indeed, the problem formulation is unique and I think it's pretty cool. So I am inclined to accept this paper.

However, I would urge the authors to prepare their final revision for the camera-ready with an eye towards clarity. The question about the comparator set is important, but the reviewers raised other issues as well. Please read their feedback carefully when updating the manuscript.
Decision: Accept (poster)