A Hierarchical Nearest Neighbour Approach to Contextual Bandits
Authors: Stephen Pasteris
Madeleine Dwyer
Chris Hicks
Vasilios Mavroudis
Venue: Accepted by TMLR ()

Abstract: In this paper we consider the contextual bandit problem in metric spaces. We design and analyse an algorithm that can handle the fully adversarial problem in which no assumptions are made about the space itself, or the generation of contexts and losses. In addition to analysing our performance on general metric spaces, we further analyse the important special case in which the space is euclidean, and furthermore analyse the i.i.d. stochastic setting. Unlike previous work our algorithm is adaptive to the local density of contexts and the smoothness of the decision boundary of the comparator policy, as well as other quantities. Our algorithm is highly efficient - having a per-trial time polylogarithmic in both the number of trials and the number of actions when the dimensionality of the metric space is bounded. We also give the results of real world experiments, demonstrating the excellent performance of our algorithm.

Published in Transactions on Machine Learning Research (10/2025)
A Hierarchical Nearest Neighbour Approach to Contextual Bandits
Stephen Pasteris The Alan Turing Institute, London, UK
spasterisSturing.c..s uk
Madeleine Dwyer
mduyer&Surrngg.co uk
The Alan Turing Institute, London, UK
Chris Hicks
c.hicksSturing ac. uk
The Alan Turing Institute, London, UK
Vasilios Mavroudis
wmavroudis@turnnggcmmm
The Alan Turing Institute, London, UK
Reviewed on OpenReview: https: openrevie.. net/ forum? id- IbJ
Abstract
In this paper we consider the contextual bandit problem metric spaces of bounded di- ameler. We design and analyse an algorithun that can handle the fully adversarial problem in which no assumptions are made about the space itself, or the generation of contexts and general metric spaces, we further anal-
losses. In addition to analysing our performance yse the important special case in which the space is euclidean, and furthermore analyse the ii.d. stochastic setting. Unlike previons work our algorithm is adaptive to the local density of contexts and the smoothness of the decision boundary of the comparator policy, as well as other quantitics. Our algorithm is highly efficient having a per-trial time polylogarith- mie both the number of trials and the number of actions when the dimensionality of the metric space is bounded. We also give the results of real world experiments, empirically demonstrating the performance of our algorithm.
1 Introduction
We consider the contextual bandit problem in metric spaces. In this problem we have some (potentially unknown) metric space of bounded diameter. We assume that have access to oracle for computing distances between pairs of points. On each trial t we are given contert x; belonging to the space, and must choose an action a, before observing the loss/rewas generated by that action. In this paper the contexts are considered implicit and we define As,t to be the distance between I, and Iz.
This problem has been well-studied the i..d. stochastic case where contexts and losses are drawn i.id. from fixed distribution. Whilst some works (e.g. [Slivkins (2009), Reeve et al.) (2018), Perchet & Rigollet (2011) and references therein) solve the problem directly, others (e.g. Agarwal al. (2014) and Foster & Rakhlin (2020g reduce the stochastic bandit problem to supervised learning and hence utilise classification
regression oracle. Although Slivkins (2009) also study non-stochastic version, they place strong constraints on the generation of the contexts and losses and do not bound the regret with respect to an arbitrary policy, In this paper we consider the fully adversarial problem in which no assumptions are made at all about the metric space, context sequence, or loss sequence. As far as we are aware the first result for the fully adversarial problem was given by Pasteris al. (2023) who give an algorithm that we refer to as NN and bound the cumulative loss with respect to that of any policy (i.e any mapping of the trials/con /contexts actions). This regret bound is good when the contexts partition into well separated clusters and the policy

---

Published in Transactions on Machine Learning Research (10/2025)
is constant on each cluster. However, the bound is poor when there exist many contexts lying close to the decision boundary of the comparator policy. In order to (partially) rectify this, they proposed using binning as preprocessing step. The process of binning involves, at the start of each trial t, finding an approximate ncarest-neighbour x' of the current context 2₁ in the set of all contexts seen so far. If the distance from the By to x' no greater than some constant called the binning radius then 2f is replaced by x'. The paper gave no method to automatically tune the binning radius, whose optimal value depends on the context density and the smoothness of the decision boundary of the comparator policy. Even if one were to choose the optimal binning radius, it would be constant across the whole space, meaning that the algorithm does not locally adapt to the density and smoothness. This inability to adapt can result in an extreme loss of performance: as we show in Section 4.4 In this paper we fully rectify this problem, designing & new (but related) algorithm HNN which (implicitly) automatically adapts to the local densily, smoothness and other quantities. In Section 4.4 we give an example of how we dramatically improve over NN (when NN has the optimal binning radius).
As in NN, HNN utilises the algorithm CBNN of Pasteris et al. (0233 which receives, on each trial >>> 1, some previous trial Pt E [t [t-11 []] (which is similar trial and is denoted n(t) in Pasteris et al. (2023) ). For NN, Pt was chosen such that Tp, is an approximate nearest neighbour of 24 in the set {-r, s E t 1]} In this paper we use different choice of Pt which we call an approximate hierorchical nearest neighbour. For approximate hierarchical nearest neighbour we will construct, online, a partition of the trials seen so far into different levels. On each trial t the algorithm then finds an approximate nearest neighbour on each level. Pt will then be chosen, in a specific way, from these approximate nearest neighbours. As HNN is based on CBNN, it inherits its extreme computational efficiency: having a per trial time complexity poly holylogarithmic in both the number of trials and number of actions when the dataset has an aspect ratio polynomial in the nunber of trials (which is enforced by binning) and our metric space has bounded doubling dimension. Due to the extreme complexity of CBNN, its description is outside the scope of this paper. Instead, inspired by the use of standard belief propagation in Pasteris et al. (2023), we detail how the online belief propagation of Delcher et al. 1995) can be used instead, giving a slight decrease in efficiency.
We note that the process of inserting a given trial/context into our data-structure is very similar to the process of constructing a new bin in [Slivkins] (2009). However, the algorithms themselves are very different and they are analysed in very different ways (our analysis being far more involved than that of [Slikkins h) Nevertheless, we cite Slivkins (0099) as an inspiration for this paper.
1.1 Additional Related Work
The bandit problem Lattimore & Szepesvári (2020) was first studied by Robbins 1952) in the non-contextual case, where we receive no side information at the beginning of each trial we simply select an action and see it's loss. The first algorithms for this simple problem only worked in the stochastic case Lai & Robbins (1985); Agrawal (1995); Auer et al.) (2002a) in which, for cach action, the loss associated with that action any trial is drawn from fixed probability distribution. The constraint that this probability distribution is fixed is strong one, and for many applications is not satisfied. The first algorithm to work when this constraint is not satisfied was the ExP3 algorithm of Auer et al. (2002b), which is a modification of the classic HEDGE algorithm of Freund & Schapire (1997) for the full-information variant of the problem (where the losses associated with all actions are revealed after every trial). The ExP3 setting is fully adversarial, in which (apart from the losses being bounded) no assumptions are made on the generation of the loss voctors.
The paper Auer et al. 2002b) also introduced the ExP4 algorithm, which generalises the EXP3 algorithm to allow for expert advice (upon which action to take) to be given at the start of each trial. ExP4 gives bounds on the cumulative loss relative to that of following the advice of any particular expert. This experts framework can be viewed as contextual bandits with an implicit context. iee. the experts are functions mapping the context space to the action set - on each trial a context is observed and each expert gives to us the action that it associates with that context. However, given that we know all contexts a-priori, being able to bound the cumulative loss with respect to that of any mapping of contexts to actions requires an exponential number of experts: meaning that ExP4 takes a time exponential in the number of trials T.
2

---

Published in Transactions on Machine Learning Research (10/2025)
As noted in Herbster et al. (2021) when given a tree structure over the contexts and a specifically crafted initial weighting (defined by the tree) of the possible experts, can use belief propagation Pearl (1982) to implement ExP4 in a per trial time of O(KT)) where K is the number of actions. When a parameter known as the learning rate is tuned appropriately, the cumulative loss of this algorithm is bounded above by that of any mapping of contexts to actions plus ((VBKT) where & the cut-size of that mapping with respect to the tree-structure. Given any graph over the contexts, by first sampling random spanning-troe Herbster jet al. (2008); Cesa-Bianchi et al. (2010), we can utilise this tree-structured algorithm to obtain loss bounds with respect to labelings of the initial graph by actions. However, the per-trial time complexity of (KT)
can be prohibitive, so Herbster et al. (2021) utilised the methodology of specialists Freund et al. (1997)
Koolen et al. (2012) in order to develop efficient algorithms [called the GABA algorithms) for this problem: one based on belief propagatiion (with a time complexity of O(K In)))) and one based on the specialist set (with a per-trial time complexity of ((m(K) In(T)))
described in Herbster & Robinson 2018
The work Pasterris al. (2023) then considered the problem in which, instead of the contexts being vertices of known graph, they instead come from an arbitrary metric space of finite doubling dimension, and are not known to Learner a-priori. They noted that tree can be formed by connecting each context to an approximate ncarest neighbour in the set of all contexts seen previously: which can be found efficiently online with data-structures such as navigating nets Krauthgamer & Lee (2004). If this tree was known a-priori then either the GABA algorithms could be used. However, since the tree is not known a-priori, the GADA algorithms fail to work. Hence, Pasteris et al. (2023) introduced the CBNN algorithm which runs in per-trial time of Óln (K) In)))² and works with any tree constructed in an online fashion. Although CBNN, which utilises the rebalancing ternary tree of Matsuzaki & Morihata (2008) and the online belief propagation algorithm of Delcher et al. (1955), borrows elements from both of the GABA algorithms it is radically different, introdueing several new data-structturs, Pasteris et al. (2023) analysed the case in which the tree is constructed by the approximate nearest neighbour method given above. In this paper we utilise CBNN but construct the tree in a different way.
1.2 Notation
We define N to be the set of natural numbers, not including 0. Given N E N we define == (iEN N). Given a predicate P we define [P] == O if P is false and define [P] == 1 if P is true. Please see Appendix A for a table of the notation that will be introduced in this paper.
2 Problem Description
We consider the following game between Nature (our adversary) and Learner (our algorithm). We have T trials and K actions. Nature first chooses matrix A E [o, 1]TT satisfying the following conditions:
For all 8, E [T] we have Ds,t = A...-
For all t E [T] we have D =.
For all r,s, [T] we have Dr. S Dn.o Des. This property is called the triangle inequality.
For all s, E [T] we call Aut the distance between trials and l. This distance represents the similarity between trials and t: smaller distance indicating a greater degree of similarity. Intuitively, we implicitly have some metric space and every trial t E (T) is implicitly associated with context x, in the metric space. A., is then the distance from I, to oe in the metric space.
For all trials t E [T] and actions a E [K] Nature chooses a probability distribution 4n over [0, 1] and a loss l,a then drawn from hea- We note that Learner has knowledge of only T and K (although the requirement of knowledge of T can be removed by simple doubling trick).
The game then proceeds in T trials. On trial f the following happens:
1. For all E [t] the distance Agt is revealed to Learner.
3

---

Published in Transactions on Machine Learning Research (10/2025)
2. Learner stochastically chooses action de [K].
3. The loss lt,,, is revealed to Learner.
Our measurement of Learner's performance is by the following notion of regret. A policy is any vector y E [K] in which for all s, E [T] with A., = 0 we have ys+ = yh- That is: a policy y associates each trial with an action St, where trials with identical implicit contexts are associated with identical actions (as they are indistingishable). Given such a policy y, we define the regret of Learner, with respect to y, as:
R(y) = Σ Bllr, lavll EE[T]
which is the expected difference between the cumulative loss of Learner and that which would have been obtained by following policy y. A policy y is (informally) considered natural if typically ys = yr when As,a is small. The inductive bias is towards more natural policies: ie. more natural policy y should yield a smaller regret R(y).
Note that, since Nature has complete control over each distribution h,,, our problem generalises the fully adversarial problem (which the special case in which each distribution L, a delta function). We are considering this generalised problem in order for our bound to be better when there an element of stochasticity in Nature's choices.
3 The Algorithm
We describe our algorithm HNN. The algorithm takes parameters 2 1, e 0 and p > 0. Our performance is best when 1 and 0. However, we allow these parameters to take on higher values in order to make our algorithm more efficient. Specifically, whenever c> 1 and e is polynomial in 1/T our per (KIIn()) when the dimensionality is bounded. We will briefly describe how one
trial time complexity can use the methodology Pasteris et al. (2023) to speed up the algorithm to (In(K) In(T)²) time per trial, referring the interested reader to that paper.
3.1 The Tree
HNN works by maintaining a growing rooted tree T where, at the start each trial t 1, T contains, as vertices, the set [t (--1) 1]. The root of the tree is equal to 1, which its single vertex on trial 1. Given any E [T', once has been added to T define p: to be the parent of t. The difference between HNN and NN is the way in which T is constructed whereas NN chooses p: to be approximate nearest neighbour of t in [t- 1], HNN utilises more complex method (inspired by Slivkins (2009)) to find pt-
In order to grow T we will maintain a number h E NU{0} initialised equal to 0 as well as, for all d E [M] a set Har C (T) initialised so that Ho = 1. We now describe how the tree T is updated at the start each trial > To do this we first define, for any non-empty set C [T] and any trial t E [T], c- nearestt neighbour of t in H be any trial E in which:
Des < cmin H}.
At the start of each trial <> HNN does the following:
4

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm: First part of trial
1. For all d E [b] U {0} let be c-nearest neighbour of & in Ha.
If there exists d [h] U {0} with Asat S e then pt + sy for any such d.
3. If Asat >e for all d E [k] [0) then:
(a) < max(d E [h] A $ 1/2"}.
(b) If 8 h then:
i. + h+ 1.
ii Hr +
(c) Ho+1 Ho+1 Ut
(d) Pt t $6.
We note that step 2 of this subroutine is a binning step: Aesit S for some d then we treat trial if it had implicit context identical to that of trial sa- However, care must be taken that the tree T does not become too deep. This is achieved by setting pt sa and then excluding / from the sets Ha. It is crucial that t is not added to any such set since we have an identical trial sæ in the data-structure already, We note that the only effect that this binning will have on our bounds is by moving the implicit contexts by a distance of up to c. The purpose of binning is that it bounds the minimum distance between trials the data-structure by e/c: which required for the tree to be not too deep and also required in order find the approximate nearest neighbours efficiently, as we now describe.
Given that e 1, is polynomial in 1/T, and the metric A has bounded doubling dimension, the above subroutine in time (In(T)²) by maintaining the navigating net of Krauthgamer & Lee (2004) over each set Ha. Specifically, since the aspect ratio (ratio between the maximum and minimum inter-trial distances) of Ha is always at least e/c, and hence polynomial in 1/T, the navigating net allows us to find the o-nearest neighbour of t in Ha in time (In(T)). By the same argument, the navigating net can also update in time of (In(T)) whenever a trial added to Ha. Since, due the binning step, we always have h E Oln(T)) obtain the per-trial time complexity of (lI(TT))).
3.2 Belief Propagation
On any trial once has been added to the tree T we select a and then incorporate the loss li via the online belief propagation algorithm of Delcher et al. (1995) but incorporating the fact that T is growing, To do this we maintain, for each s E [T]. dynamic (in that it changes from trial to trial) vector e, E R2 initialised so that c,,a = for all a E [K]. For all a, E [K] we define the quantity:
Ta.b = [a =b] bl (1-T))
[a + bl
(K 1)T
We note that for any vector E IRK we can compute the vector o' E kK defined by 1/:== ==EE[[K] VaTa. in time O(K). Specifically, we have:
(1-1) -1-T) ub + [EEEKK] va) va)= Tb T
v/6
(K - 1)T
On any trial & E (T), once has been added to the tree T do as follows.
5

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm: Second part of trial (when using belief propagation).
1. For all a E [K] set:
Pl,a + 1.
2. Descend the tree T from 1 (i.e. the root) to t. When at a vertex 8 # 1 set, for all a E [K], the quantitics:
Ss,a
Σ bE[K]
i Ps,a
Σ
Pp,,bep,,
Tb.a
Oz.b
[E[K]
3. For all E [K] set:
Pi,a
Ta -
[ Pr,b
Sample at such that for all a E [K] we have az = a with probability ma-
5. Play
6. Receive the loss l,,0
7. For all a E [K] set:
(=la, = allec.r
ct t exp
exp
Piaa / VKT
8. Ascend the tree T from t to 1 (i.e. the root). When at a vertex 8 + 1 set, for all a E [K], the quantities:
Cp.0
0r 8,0
To
Cp.c
1 Pa,a
KE[K]
To aid the reader, we now give a brief verbal overview of online belief propagation. As explained above, we maintain a vector e, E R for each verlex/Lria 8. These vectors are initialised such that each component is equal to 1. For each trial there are two phases: the first phase selects the action de and the second phase updates some the vectors in {es | E [d] after receiving the loss le, The first phase proceeds by descending the tree along the path from vertex/trie 1 to vertex/trial t. For each partex/trial encountered during the descent, vector 9. RRK is computed. When the vector with all components equal to 1, and when s / (so that has parent P, and 4p, has already been computed) 9, is compuled from Pp,, and ep, (see Line 2). Once 4i; has been constructed, it is normalised to form a probability vector from which is then drawn. In the second phase, li,, is first received and used to update e (sce Line 7). The tree is then climbed up the path from t to 1. When at a non-root vertex/trial s on this path, Ep, updated based on its old value and the new and old values of e, (see Line 8, noting that 9, was constructed Line 2).
(i.e. is the root) 49 is defined to be
Note that running online belief propagation any trial takes time of O(hK) which is O(KIn(T) under the above conditions.
3.3 CBNN
In order to achieve, under the above conditions, a per-trial time complexity of (In(K) In(T)²), we can utilise the CBNN algorithm Passteris et al. (2023) instcad of belief propagation. CBNN solves the following problem. A-priori Nature chooses, for each trial & [T], a loss vector & E [0, 1] and, when L > 1, a trial n(t) [t - 1]. The idea is that the trial n(t) in some way similar the trial On each trial [T] the following happens:
1. I 1 then r((() is revealed to Learner.
2. Learner chooses action o [K].

---

Published in Transactions on Machine Learning Research (10/2025)
3. The loss a, is revealed to Learner.
CBNN an algorithm for Learner in this problem. takes parameter p > and, given any policy y [K]T, achicves:
Blca,: -m, E E 10((((++) {(v) ) VKT)
Σ (E[T]
where:
(ly) 1+
[ye Un(ei]
The time complexity of CBNN is only ((n(K)ln(TT)) per trial. We refer the reader to Pasteris et. al. (2023) for complete description of the mechanics of CBNN.
HNN utilises CBNN by setting n(t) == Pt for all t E [T] \ {1}. The losses revealed to CBNN are those received by HNN. The parameter p of CBNN is identical to that of HNN. The actions selected by HNN are those selected by CBNN.
We note that CBNN works on what it calls ternary search trees to improve efficiency when the tree deep. However, in HNN the tree T has depth of only (ln(c//)) don't need to use ternary search trees, instead maintaining contractions (as described in Pasteris et al. 2023 ) over the original tree instead.
3.4 Computational Complexity
The following theorem states the time complexities of the various versions of HNN.
Theorem 3.1. For metric spaces of bounded dimensionality and with polynomial in 1/T and c 1, the per-trial time complezities of HNN with belief propagation and CBNN (In(T)) + KIn(T)) and O(I((K) ((T))) respectively. For general metric spaces the per-trial time complerities of HNN with belief propagation and CBNN are OKKT) and (TT) respectively.
4 Performance in Euclidean Space
Before we give our general regret bound we will first give, as an illustration, a corollary it for the important special case in which our implicit contexts lie in euclidean space. We call this special case the euclidean bandit problem. We also give an almost matching lower bound, highlight our improvement bound for the i.i.d. stochastic special case. We note that our more general bound in Section improves on the bound of this section, as well as generalising it to arbitrary metrics.
NN, and give
4.1 The Euclidean Bandit Problem
In the euclidean bandit problem there exists some constant d which is the dimensionality of the dataset. For all E IRd let | be the euclidean norm of æ. Given æ E Rd and radius r as:
define the ball with centre and
B(x,r) = (x' Rd | - x' Sr}
We define X' := 1/00, Nature chooses, a-priori, a sequence of conterts:
(x, E [T] CX
unknown to Learner. The matrix A is then defined such that for all 8, [7] we have:
A s.t ||x. Jell

---

Published in Transactions on Machine Learning Research (10/2025)
Figure 1: An example with K = 2 and d = 2. Here we have N = 5. The black curve is decision boundary of y. The purple balls are those in the boundary cover (B(r, r.) i E [N]} and the green balls are those in (ra [N]]. The grey contexts are those in {ae E M), the red contexts are those in {are 1 E (T] \M y/ = 1}, and the blue contexts are those in {æt 1t E (T) \ A yt 2}. Note that the purple balls cover the decision boundary and the grey contexts are those covered by the green balls.
4.2 Regret
Our regret bound for the euclidean bandit problem is based on the following concept of a boundary cover which is (informally) any set of balls covering the decision boundary of the comparator policy. Formally, take some arbitrary policy y [K]T. An extension of y is any function ÿ X [K] such that ÿ(xx) = V for all & [T]. A decision boundary of y defined as set:
{x E X Vr 0, 3x's E B(x,r) nx x: 0(x') + ((x))
where ÿ is some arbitrary extension of y. Finally, we define boundary cover of as any set of balls which covers a decision boundary of y.
With the definition of boundary cover hand, we have the following bound on the regret of HNN.
Thcorem 4.1. Let > and > be arbitrary constants and assume HNN is run on the euclidean bandit problem with any e 2 1, any (E 1)T-c/ /2 and any p 0. Then given any policy y [K]² and ony boundary cover:
(((o,rs) [NT}
of y with:
min(ralie E [N]] T-C
we have:
R(v) S [M] ((+ N ) v KT
where:
M tE [T]
U B(us,Ers) kE[N]
Proof. A corollary of Theorem 5.1 See Appendix
Theorem 4.1 is illustrated in Figure 1. Note that N is the number of balls in the boundary cover and [ is the number of contexts lying inside the balls of the boundary cover when each is expanded by a factor &.
We note that Thcorem 4.1 is corollary of Thcorem 5.1 However, using Theorem 5.2 instcad can significantly reduce the term [ that appears in the regret. This improvement allows us exploit Holder continuity the i.i.d. stochastic bound coming up in Section 4.5
8

---

Published in Transactions on Machine Learning Research (10/2025)
4.3 Lower Bound
We note that we have the following regret lower bound which is extremely close to our upper bound in Theorem 4.1 when p= p=vN. VN.
Theorem 4.2. For any algorithm, given any & > 1 and r > 0 with 8&r < 1, and any N' E N less than the 2rr-packing number of X and any & T/, then if 2 2N' there crists:
A policy y E [K]T.
A boundary cover of y of cardinality N E O(N)) in which each ball has radius
A choice of conterts and losses by Nature such that, when M is defined from & and the bowndary cover in Theorem 4.1 have [M] M.
such thal:
R(y) 2
Proof. See Appendix
We also note that for any algorithm we require, for Theorem 4.1 to hold, the condition that & 1. Specifically, we have the following theorem:
Theorem 4.3. Given any algorithm there enists policy y, boundary cover of y with cordinalily 2, and a choice of conterts and losses by Nature, in which no context lies in either ball of the boundary cover and R(y) 2 T/2.
Proof. See Appendix
4.4 Comparison to Nearest Neighbour
We now compare the regret bound of HNN in euclidean space, as given in Theorem 4.1 to that of NN, which is, as far as we are aware, the only other algorithm that can handle the fully adversarial problem. We assume here that NN using the optimal binning radius (which it must know a-priori).
The regret bound of NN is like that in Theorem 4.1 except with the restriction that all the balls in the boundary cover must have the same radii (a constant multiple of the binning radius). This is essentially proved in the proof of Theorem 3.9 of Pasteris et al. (2023). The restriction of all balls having the same radii severely limits NN: meaning that, unlike HNN, it cannot adapt to the context density and decision boundary smoothness. We now give an illustrative example of its inability to adapt to context densily.
For simplicity let's assume that the parameter p. of NN and HNN, is set equal to a constant, although the argument casily extends to tuned parameter values as well. Consider two disjoint balls B, 5' in R² with radii equal to 1 and any constant). Assume that each ball has T/2 contexts distributed uniformly over it. Suppose we have two actions and a comparator policy such that the decision boundary (of the policy) on cach ball is a straight line going through the ball's centre. This is depicted in Figure 2.
respectively (noting that the diameter of the dataset in our problem
actually be
First. let's analyse NN when working on each ball as a seperate problem. Given a binning radius of yo, the regret of NN on B is OVTT/p + sf) and the regret NN on B' is Ö(rVT/ + vT/r). For both these problems the optimal value of ip leads a regret of O(T3/4).
However, things change when NN is working both balls at the same time. In this case, given binning radius of i,, the regret of NN is:
O(VTTpP PT) + P/TT/++/T//// - - (T/))
i.c. the sum of the regrets on both balls. This means that the optimal value of & leads to regret of OTT8/1 which be dramatically higher than if the balls learnt separately. In fact, when
9

---

Published in Transactions on Machine Learning Research (10/2025)
2
2r
Figure 2: An example of when NN performs poorly. The colour context represents the action assigned to it by the comparator policy.
r S 7-2 this bound is vacuous. Our algorithm HNN, however, has a regret Ō(T3/4) whenever 1/r is polynomial in T the same as if the balls were learnt seperately.
When working in D for D 2, the improvement of HNN over NN is even stronger. To this note that the regret of NN when working on both balls is:
O(VT//pD-1 + (T) + -V = +
that the optimal value of ip gives T-1/2DD2) HNN, on the other hand, achieves a regret of ((T(2D-1)/2D) whenever 1/r polynomial in T' the same if the balls were learnt seperately. Note that p is to constant here: when, instead, p (D)1/(2(D++) then HNN achieves regret of O(TD/(D+))
regret of Ô (1-00-1/D7(20-11/20) which becomes vacuous
4.5 Stochastic Bandits
Even though HNN is designed for the adversarial problem, we will now show that that in the i.i.d. stochastic special case it is competitive against algorithms designed purely for that special case, sometimes even out- performing. In fact, our experimental results in Section t show that HNN can outperform such algorithms in real world i.i.d. stochastic problems. For HNN the bound we give is crude, and we believe it can also be obtained by NN (with The optimal binning radius). Our bound improves on the stochastic bound of NN given in Pasteris et al. (2023) by allowing for the Bayes decision boundary to have fractal dimension greater than d and by becoming adaptive to Holder continuous mean losses.
We maintain the notation and problem description given at the start of this section. In the i.i.d. stochastic special case we have unknown probability density over the space X' x [0, 1]K and for every trial E [T] the pair (Iz, le) is drawn from v. We assume that v is bounded above by constant. Given x E X and a E [K] we define:
(z) = E B(r' x²==
which is the mean loss of action a when given context æ. We define the Bayes optimal classifier 1 X - [K] such that for all x E X' we have:
j(x) == argmin (a(x)
and define the Bayes decision boundary D the set:
X 3x' e B(a,r) 8(2') # ((z))
Furthermore, we define the decision boundary dimension 2 such that the exists d' > such that for all r > 0
we have that can be covered by d'r- balls radius r. Finally we define the Holder complezity such that there exists such that for all x E X we have:
max [T((x) - (a(x')) s c|p 2'1 <
10

---

Published in Transactions on Machine Learning Research (10/2025)
We now state the performance of HNN. Theorem 4.4. When HNN is run with S T/T and the oplimal value of p in the i..d. stochastic bandil problem described above then given the policy is such that yt ((xz) for all E [T], have:
B(R(y)) (T(K/T)
where the O suppresses a constant dependent on V.
Proof. A corollary of Theorem 5.2 See Appendix
G
We note that this bound is crude and does not account for the ability of HNN to adapt to varying density and varying values of yp and & (along with their corresponding constants c' and é) across the space. However, we believe it to be novel, in some cases improving over bounds attained by algorithms designed specifically for the i.i.d. stochastic problem. In particular, we now compare it to the bound of the ABSE algorithm of Perchet Rigollet (201I) which is, as far as we are aware, the state of the art for i.dd stochastic bandits euclidean space. Unlike our bound, the bound of ABSE depends upon a quantity a > defined as follows. First define, for all x E X, the gap as:
min g(x) = aE[K] (())
(Ta(2) DB(a) (I))
and then let a be equal to the minimum value of a' such that there exists et such that for all have:
P ((a.e))) S 8) S cl
Given a > 0, the bound obtained by ABSE is then:
E [(()] E ò (T(K/T)
Note that this is, in general, incomparable to our bound in Theorem 4.4. For example, as approaches 0 whilst and a stay constant, or when a approaches 0 whilst < and yp stay constant, our bound is an improvement.
5 Performance in General Metric Spaces
We now bound the expected regret of HNN for general matrices A. The final bound also improves on the bound in Theorem 4.1 when in euclidean space. We will assume here that the parameter is set equal to This is without loss of generality as for e >> 0 the result the same but such that distances have been shifted by up (which is typically negligible). In what follows, given e, we have universal constants À 1 and 0.
Theorem 4.1 involved set of trials M whose contexts lay near the decision boundary of the comparator
policy, In general, a margin is any set M C [T'] in which for all s E M and all & E [T] with A,, = 0 we have E M. Our general bound will hold for any possible margin M C [T]. So suppose we have any arbitrary policy y e [K] and margin M C [T]. Note that the algorithm has no knowledge of either or M.
5.1 Packing Complexity
Here we give our first, simpler, general regret bound. For all f [Z]] we define:
N = min s E [T] M A ys * v
which is the minimum distance from t to any trial & M with differing label. We also define:
A min [T]]-
11

---

Published in Transactions on Machine Learning Research (10/2025)
which can be viewed as the width of the margin.
We define the packing complexity V as the maximum cardinality of any set 8 S [2'] in which for all s, E 8 with s + we have:
D > 27/6-
Note that the packing complexity is the maximum cardinality of any packing of balls such that, if ball's centre is t, then its radius is 2-y- Here define packing to mcan that the centre of any ball is not contained inside any other ball.
With the definition of packing complexity in hand, we now present our first general regret bound.
Theorem 5.1. Given any policy E [K]T and any margin M C [T), then if vp and A are defined as above we have that HNN with = 0 has an expected regret of:
R(y) & M ((++ |In(1/A)2
KT
P
Proof. An immediate corollary of Theorem 5.2
When M 0 (and the aspect ratio polynomial in T) our bound is similar to that of Pastoris et al. (2023) (without binning) except that their equivalent of V covering number rather than packing number (the radii of the balls in the covering/ /prriingp being constant factor different in the two bounds). However, have big advantage over Pasteris et al. (2023) in that we can essentially hold out in the computation of the values "h. As the margin increases the values increase, meaning that V decreases. In return for the decrease in V the factor [M] is added to the regret. There is a sweet-spot: the optimal margin. The purpose of our margin is essentially the same purpose as using bimning in Pasteris et al. (2023). However, since our margin can be any set we have much more flexibility (compared to the constant binning radius of Pasteris al. (2023)) ), allowing us to adapt locally the density illustrated in Section 4.4
choose any margin M S [T] which we
of contexts and smoothness of decision boundary:
5.2 Excesses
We will now tighten the regret bound in Theorem 5.1 by reducing the term [M], which what allows exploit Holder continuity in Theorem 4.4 To do this we will now define, for all E M, a quantity pr. that call the ercess of trial t. First define:
0: = min (T) M}
which is the minimum distance from t to any trial not in the margin. Define:
V4 = (v. Iulsse e [T] A A.S S A6a}
which is the set of labels of trials within a distance of A0, from t. Finally define:
== max max(t - Ee. I 34}
which is the difference wetween maximum expected loss, on trial 1, of any action in Dh, and the expected loss, on trial f, of the action Ve-
We have now defined all the quantities needed present our second general regret bound: Theorem 5.2. Given any policy y E [K] and any margin M C [T), then if V, A and (ur l2 M) are defined as above then HNN with 0 has an expected regret of:
R(y) - Σ Me +Ö ((++ V WIn(T/A)2) 1EM
VKT
P
Proof- See Appendix
12

---

Published in Transactions on Machine Learning Research (10/2025)
124
Slivkins
Sliviins
UCB
KL_ .... KNN UCB
.... KNNN UCB
30%
NN with D.1 bt
NN with 0.05 br
25k
0.1 br
HNNN
HNNN
Cumulaaive Loss
Cumulative Loss
20k
6k
4k
5k
10k
15k
20k
10k
20k
30k
40k
50k
Time Steps
Time Steps
(a) Cumulative loss averaged over 10 runs for the UCI firewall dataset. The lines represent the average over 10 independent runs. Shaded regions indicate +1 standard deviation. For most methods, the stan- dard deviation is very small and, as such, not visually obvious in the plot.
(b) Cumulative loss for the CICIDS2017 intrusion dataset experiment.
Figure 3: Comparison of cumulative loss across two real-world datascts.
To compare against. Theorem 5.1 note that [M] has been replaced by ΣIEM 14- Typically ΣIEM Me is much less than [M] since, for any trial & E M, any action E }i is typically equal to ys for some close and Yt are good actions for s and t respectively. Hence, by the inductive bias and since is close to & we often have that Rf(t,g.] is similar to B( Hence, Pt is often close to 0. However, since the setting is fully adversarial, may not be.
to t. If y is good comparator policy then, typically,
We note that, unlike NN, our algorithm HNN is also adaptive to factors that influence the values of the excesses, such the local Holder complexity and its constant in i.i.d. stochastic bandits (as defined in Scction 4.5)
6 Experiments
In Figure 3 we give the results of two real-world experiments comparing the performance of HNN to that of NN and three state of the art algorithms for the i.i.d. stochastic problem (Figure 3a) and a real-world adversarial problem (Figure 3b It is important to note that the first of these experiments is on an i.idd. stochastic dataset, whereas HNN was built for the more general adversarial problem, yet both experiments HNN manages outperform the algorithms designed specifically for the i.id. stochastic problem.
The details of the experiments, which are both for problems in cyber-defence, note that in the first experiment, NN and NN with a binning radius of 0.1 achieve the best performance, HNN attains the next-best results, surpassing the other three bandits and NN with binning radius of 0.2. In the second experiment, HNN achieves the best performance, even when compared with NN with various binning radii.
given in Appendix We
7 Conclusion
Inspired by Pasteris al. (2023) and Slivkins (2009), we designed a novel algorithm for the adversarial bandit problem in metric spaces. Unlike the algorithm of Pasteris et al.) (2023). our algorithm is locally adaptive to
13

---

Published in Transactions on Machine Learning Research (10/2025)
the density of contexts and the smoothness of the decision boundary of the comparator policy. We analysed the regret of our algorithm with respect to any possible comparator policy, and analysed further the special case of Euclidean space, for both adversarial and stochastic bandits. We gave the results of real-world experiments that empirically demonstrate the performance of our algorithm.
References
Internet Firewall Data. UCI Machine Learning Repository, 2019. DOL:
C..
Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. ArXiu, 0bs/1402.0555, 2014. URL
https://api.. pammaatticccclla..or///oooooo
12549076
Rajeev Agrawal. Sample mean based index policies by o(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27:1054 - 1078, 1995.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finile-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-25 256, 2002a.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32:48 77, 2002b.
Nicolò Cesa- BasanBiannhh, Claudio Gentile, Fabio Vitale, and Giovanni Zappella. Random spanning trees and the prediction of weighted graphs. In International Conference on Machine Learning, 2010.
Arthur L. Delcher, Adam J. Grove, Simon Kasif, and Judea Pearl. Logarithmic-time updates and queries in probabilistic networks. J. Artif. Intell. Res., 4:37-59, 1995.
Dylan J. Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. ArXiv, /t////2022.22922 2020. URL
org/CorpusID D 211082940
Yoav Fround and Robert E. Schapire. A decision-theoreeic generalization of on-line learning and an appli- cation to boosting, In European Conference on Compulational Learning Theory, 1997.
Yoav Freund, Robert Schapire, Yoram Singer, and Manfred K. Warmuth. Using and combining prodictors that specialize. In Symposium the Theory of Compuling, 1997.
Mark Herbster and James Robinson. Online prediction of switching graph labelings with cluster specialists. In Neural Information Processing Systems, 2018.
Mark Herbster, Guy Lever, and Massimiliano Pontil. Online prediction on large diameter graphs. In Newral Information Processing Systems, 2008.
Mark Herbster, Stephen Pasteris, Fabio Vitale, and Massimiliano Pontil. A gang of adversarial bandits. In Newral Information Processing Systems, 2021.
Wouter M. Koolen, Dmitry Adamskiy, and Manfred K. Warmuth. Putting bayes to sleep. In NIPS, 2012.
Robert Krauthgamer and James R. Lee. Navigating nets: simple algorithuns for proximity search. In ACM- SIAM Symposium on Discrete Algorithms, 2004.
Tze Leung Lai and Herbert E. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. 2020.
Kiminori Matsuzaki and Akimasa Morihata. Mathematical engincering technical reports balanced ternary- tree representation of binary trees and balancing algorithms. 2008.
Stephen Pasteris, Chris Hicks, and Vasilios Mavroudis. Nearest neighbour with bandit foedback. In NeurIPS, 2023.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Judea Pearl. Reverend bayes inference engines: A distributed hierarchical approach. Probabilistic and Causal Inference, 1982.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. ArXiv, abs/1110.6084, 2011.
Henry W. J. Reeve, Joseph Charles Mellor, and Gavin Brown. The k-nearest neighbour ueb algorithm for multi-armed bandits with covariates. ArXiu, abs/1803.00816, 2018.
Herbert E. Robbins. Some aspects of the sequential design of experiments. Bullelin of the American Mathematical Society, 08:527-533, 1952.
Iman Sharafaldin, Arash Habibi Lashkari, and Ali A. Ghorbani. Toward generating a new intrusion detection dataset and intrusion traffic characterization. In Proceedings of the 4th TCISSP, 2018.
Aleksandrs Slivkins. Contextual bandits with similarity information. ArXiu, abs/ /05/00997.99990 2009.
A Notation Table
We now give a table of some the notation used in this paper.
Symbol
Meaning
R
Set of all real numbers
N
Set of all natural numbers excluding 0
[n]
{m E N m S n}
[P]
Equal to 1 if predicate P is true and equal to 0 otherwise Context at trial (usually considered implicit)
aa
Loss of action
trial /
Action selected by the algorithm trial t
As.t
Distance from v, to Tt.
Binning radius Approximation quality of nearest neighbour search algorithm Learning rate (parameter of the algorithm)
P
T
Number of trials
K
Number of actions
d
Dimensionality of Euclidean space
An arbitrary policy in [K]T, which associates action ye with each trial
y
R(y)
Regret of the algorithm with respect to policy y
T
Growing tree (with trials vertices) constructed by the algorithm
X
Euclidean ball centered at with radius 1/2
B
Experiment Details
We ran experiments on two real-life firewall datascts to empirically compare HNN with NN and with three other state of the art contextual bandit algorithms, K-Nearesl Neighbours with UCB (KNN UCB), K-Nearest Neighbours with KL divergence and UCB (KNN _L_ _CBB Reeve et al. (0018) and contertual bandits with similarity information (Slivkin's) Slivkins (2009). It important note that the first experiment is on an i.i.d. stochastic dataset, whereas HNN was built for the adversarial case, yet in both experiments HNN manages to outperform algorithms designed specifically for the i.i.d. stochastic problem.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Both sets of experiments involved using classification datasets. The loss was determined by whether the action chosen matched the label from the dataset, with loss of 1 if it did not, and 0 otherwise.
For our first experiment, we used the UCI ML Firewall dataset int (019)) which is internet firewall data. We randomly shuffled and ran the dataset multiple times to get the average cumulative loss of each algorithm. We used the Action column as the actions for the bandits. The dataset includes the actions Allow, Block, Drop and Reset-All, but we removed the Reset-All data due the extreme sparsity of this class (less than 1% of the dataset). We used the following features: SourcePort, DestinationPort, NATSourcePort, NATDestinationPort BytesSent, pkts_ _entt. We removed features that we believed would not be accessible at the point of decision for bandit if it was being utilised in the real-world for intrusion detection (c.g. features such as Elap
For the distance metric, we took the Euclidean difference of each of the non-categorical features. For the categorical features (the Port features) we used a distance mcasure of if the value was identical and 1 if it was not. For each feature, we independently scaled the pairwise differences to the 1/6] range (6 being the total number of features), to ensure that all features contributed equally to the overall distance computation (i.e. we had no weightings across the features). The final distances were constrained to the [0, 1] range.
We compared HNN with the other contextual bandits with no binning. We also compared against NN with binning radii of 0.1 and 0.2. The results are shown in Figure 3a noting that the standard deviation for all but KNN KL UCB are very minimal and as such not visible on the plot. NN with a bimning radius of 0.1 has the lowest cumulative loss, followed by NN and then closely by HNN. Both NN and HNN outperform the other state of the art bandits, even in this stochastic setting.
For the second experiment, we used another real-world dataset, using a subset of the CICIDS2017 intrusion dataset Sharafalddn et al.] (2018). For this experiment, we used the machine learning CVE data, which consisted of the network traffic flows. The CICIDS2017 dataset has multiple days of data, on each day, there is benign and attack traffic. We took a subset of the Wednesday data which contained multiple different DoS allacks, we maintained the temporal order from the original datasel so that the experiment was conducted in the adversarial setting.
We gave the bandits two actions, Allow Block, and we used the label from the dataset to determine which action was most appropriate (allow for benign, block for atlack). We used all 77 features of the dataset (dropping the duplicate column of "Fwd Header Length").
We used a similar distance mcasure as for the first datasct, where the categorical data (IP address) had a distance of 0 if it was the same or 1 otherwise, and for the non-categorical features, we took the Euclidean difference. We again independently scaled the pairwise differences to the [o, 1/77] range, so that all features contributed equally to the overall distance computation. The overall distances were again constrained to the [0, 1] range.
Figure 3D shows that HNN clearly outperforms all the other algorithms, including NN both without binning and also with binning radii of 0.1 and 0.05.
C Proof of Theorem 5.2
We now prove Theorem 5.2 We note that we use the results of Pasteris et al. (2023) as a black box in this analysis.
Without loss of generality assume that for all 8, E [T'] with + t we have Asr & 0 which, since 0, implies that the binning step in the construction of T is never invoked. This is without loss of generality as if there was to exist s > t with Art = 0 we simply define Ús == de in this proof. Also without loss of generality assume there exists s, t,t E [T] M with y, + y else the result is trivial (by choosing G to be the same for all I E (T))
Let & be an arbitrary number in (0. 1). We define:
f f= 1/2
B = 2/
16

---

Published in Transactions on Machine Learning Research (10/2025)
A: (63 (13 +))
and:
2 = = (1/12)/
In this analysis we will often use the fact that, for all E (7), we have dp. = de - and A.p. S fde-1.
Definition C.1. Consider the rooted tree with vertex set [2] such that, for all t e [T] \ {1), we have that pt the parent of t. Let be the set of leaves of this troe. Given t [T] we then define Dj to be the set of all descendants of and define A₃ to be the set of all ancestors of L.
Lemma C.2. For all r, 7, E [T] with r + and d, = de we have that Deg > /d./e.
Proof. Suppose, for contradiction, the converse: that Ar, S / /c. Without loss of generality assuine r < t. Let = max
[t - 1}} and for all E [h] let sa be as created by the algorithm on trial t. Let q == sd,- Since q is c-nearest neighbour of t in the set {s [t [t- 1]]dd d d (which contains r) must have that Ag.t S cAr, S fdr, But from the algorithm we have that d, is the maximum value of d E [h] such that Asg.t S ldt so since de = d, 1 < d, we have contradiction
Definition C.3. Define u to be the set of all trials t E [7] in which for all 8, E [2] \ M with A.e 334
and A,, & ffd we have Vr = yss Lemma C.4. Given s, [T] with u and t D, we have t U.
Proof. Noting that de 2 dg fix and prove by induction de When d, de have = so the result is immediate. Now suppose, for some d 2 d, that the inductive hypothesis holds for all t with d, = d. Now take with de = d + 1. Since & E D, and t + we have E D,, So since dp, = d we have, by the inductive hypothesis, that Ps E U. Now take any q,r r E M with 4q $ f and A,,, I ff,, From the algorithm we have that Aep. I fd and hence, by the triangle inequality, we have:
A Drp. Dr,t + A.p. S 3fh + fde- 1 = (3f + 1)fde s 3ph-11
Similarly we have Agp. I 8f4411 So since dp. = dg - and Ps E U we must have that yg = Yr. Hence, we must have that & E U so the result holds by induction.
Definition C.5. Let V be the set of all t E [T] such that either:
? U and Pt $ u
e and $
Definition C.6. Let W be the set of all t e V such that there does not exist E V with do > de and S (f -
-f=))/(2c)
Definition C.7. For any t E W let Qe be equal to the set of all E EVV W in which A.s S /(cc)
Lemma C.8. Given SE V W and d E N either have that there exists t E W with Q. or that there erists some E V W with d, 2 and Dr,a I (f - fd. ((cc)
Proof. If there exists t E W with Q, then we're done so assume otherwise. We prove by induction on d. We immediately have the result for d = 0 by choosing r == 8. Now suppose, for some d' E E (0), that the inductive hypothesis holds when d= d' and consider the case that = d' 1. By the inductive hypothesis choose g E V W with d, 2 d' and ag, S (fd. -2c))(2cc). Since q E V W we have, by definition of W, that there exists u V with du > dg and Du,g S (fth fd.)) (2cc). By the triangle inequality then have:
A Aug + Ag,a S (ou)) ((2)) (sa - ((2)) - -dd))(22))
If was the case that u E W we would have, from this incquality, that & E Qu which contradiction. Hence, we have E V W. Since d, > dg and dg 2 d' we have de 2 d' +1 d. By the above incquality we then have the result by choosing r This completes the inductive proof.
17

---

Published in Transactions on Machine Learning Research (10/2025)
Lemma C.9. Given E V W there erists E W with E Qc.
Proof. Suppose, for contradiction, the converse. By Lemma C.8 then have, for all E N, that there cxists
some E V \ W with d, 2 d. By choosing d == T we then have that there exists is impossible.
[T] with d, 2 T which
Lemma C.10. For all L W and E Q we have dg S de.
Proof. Suppose, for contradiction, that there exists t E W and 2r with dg > de. Then by definition of Qi we have E V and ss,t I fd. (2c). Since de S dg 1 we then have:
- ) 2
(2c) = (1/f 1)5 ((cc) 2 (1/f - 1)A..
So since f = 1/2 we have s,t S (fdee - (2c) which, since d, > de and E V, contradicts the fact that E W.
Lemma C.11. For all t E W we have 12 v dg +
Proof. By Lemma C.10 all we need to prove is that if q.r Qr are such that # r then dg * dr. We now prove this by considering the converse: that dg = dr. By definition of Q we have Agtt S f (2c) and Dry S fd- (2c) so by the triangle inequality we have:
/d: Arr S Ag,t + Ar. S ( /01//
which, since dg = d,, contradicts Lemma C.2
Lemma C.12. For all E V we have for 2 7hl /////11+1
Proof. By definition of we immediately have that either $ U or P: $ u. By Lemma C.4 we then have that Pt $ u. Hence, by definition uf and since dn. = de - 1, we can choose r, E [T] { with y, # ys and Drpp S ffdd11 and A.p. S _Bfdd- Since yr # ye we can, without loss of generality, assume that yo # ye which mcans, since & M, that As,t 7tt By the triangle incquality and the fact that Deps S fde-l then have:
# < A n I A.... + Aprt S 3f + fde-1 (1+
Rearranging then gives us the desired result.
Lemma C.13. For all 8, E W with 8 + t we have D,,t > 2 =max 71)-
Proof. Without loss of generality assume de 2 d. If dg = de then we have, from Lemma C.2 that As, > fds/c. On the other hand, if d, > d, then we have, from the definition of W and the fact that s E V, that:
A. > (frr pd. ((cc) 2 (f+e - / = (1 (1- f)- /(2c)
either case we have that A,t > (1 - fd (2c) and hence, since fdb - pdr, we also have that D.tt > - f) /(cc). From Lemma C.12 we then have that:
Agt > 11-fff (2c) 2 m(1 - fff/fff//221111 -B) 2%)t
and
A > (1- ((2) 2 7a f)5/(2((1 +B)) 27
required.
Lemma C.14. We have [W] <
Proof. Immediate from Lemma C.13 and the definition of V.
Lemma C.15. For all E V we have d, E OlI(11AA)
18

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. By Lemma C.12 and definition of A we have:
+ A//(1
Taking logarithms gives us the result.
Lemma C.16. We have M O(VIn(L/A)
Proof. By Lemma
C.9 we have:
V wu U a
tEW
that:
M S [W] + Σ 0
iEW
By lemmas C.11 and C.15 we have [ E (In(1/A) for all t E W. Substituting into the above inequality
gives us [V 2 O (W) (n) Lemma C.14 then gives us the result.
Lemma C.17. Suppose have some [T] such that for all As we have $ V. Then $ u.
Proof. We prove by induction on de If d2 then we have 1 that we immediately have t U (since there exists r, [7) \ M with y, * ys)- Given some d suppose that the inductive hypothesis holds for all t with d, d. Now consider any with de d + Note that for all E Ap, have E As that & V. Since dp. de - 1- d we then have, by the inductive hypothesis, that & U. If it was the case that E U we would then have, by definition of V, that I E V. But since & E A, this would be a contradiction. Hence, 1 & U. This completes the inductive proof.
Lemma C.18. For all E [T] there exists s E V such that t E D, U.A.
Proof. Assume, for contradiction, the converse: that there exists no V with t De U.. This means that for all E D, U A, we have & V. So choose some E DD n L. Since A, C D, Ar we have, for all E Ar, that $ V. By Lemma C.17 we hence have that & U. But since E L this would mean that r E V which, since E D, U Ar, , is a contradiction.
Definition C.19. Define the policy ~ E [K] such that:
If & U then 0. : Ve-
If t E U and there exists s E [T] \ M with As, S 8fds then dr yv- Note that by definition of U we have that dr is uniquely defined.
If / U and there does not exist s E [T] \ M with A., S Bpde, we have dr 9r. Since l this is defined.
Lemma C.20. Given t E [T] \ (1} with de + 9p, there enists s E with t E A..
Proof. By Lemma C.18 choose 8 E V such that t E D, U Ag. Assume, for contradiction, that L & A.. Then we must have t D, {s}. This means that & and hence, by definition of V, we have that s E U. So since we have both é D. and Pt E D2 we have, by Lemma C.4 that both t and Pt E U. Since ÿr # Oo we must then have, by definition of ÿ. that there exists 9 E [T] M with Ag,t I fd. Since Dt.p, I pd. we have, by the triangle inequality, that:
Dgp. S Sg + A...
f (Bf 1)fd.-1 3p
so since d,, d, and g & M we have, by definition of & and since P. U, that Op. = yy- We also have, by definition of and since both Ag. S fd. and E U, that di Vq. But this means that de 0p. which is contradiction. We have hence shown that i A.-
19

---

Published in Transactions on Machine Learning Research (10/2025)
Lemma C.21. We have:
Σ
[ū + Hp,l E (((WI((/A))
Proof. Given t E V/ we have, by Lemma C.15 that d, E ((I((1A)) and hence that |Ad E ((I((1A)). By
lemmas C.20 and C.16 we then have that:
Σ
1ee pp.1
U
S
Σ sEV
|Aa e O(I)) ((VI)(/))))
.EV
as required.
Lemma C.22. We have:
4. So (00 V (11/A)2)))))
Σ (E[T]
Ellt,a
VKT
Proof. From Pasteris et (202)). when using cither belief propagation or CBNN, we have, when taking expectations on their result, that:
Blb,,, l u (0-11
1+ E
EeerI + Hp.l
KT
P
AE(T]
Substituting in Lemma C.21 gives us the result.
Lemma C.23. For all [T] with ÿI + Y1 we have t Mnu.
Proof. Suppose, for contradiction, that there does exist t e [T] with t & Mn and år * yt. Since de # Y must have, by definition of Ú, that E U. Hence, we must also have t $ M. Since both t e u and $ M with A =0 f must have, by definition of 9, that dr yt which is a contradiction.
]
Lemma C.24. For all s,t E [T] with De we have Dest 6336.
Proof. We hold s fixed and prove by reverse induction on de (i.e. from de to 0). When de = d, we have ==t and hence A,, = 0 so the result holds trivially. Now suppose, for some d [d,], that the inductive hypothesis holds when de = d. We now show that it holds when d, d which will complete the inductive proof. So take with d, d - 1. Let be such that D, and p. t. Note that have d, d so by the inductive hypothesis we have Der I 68fd, Since Arp. S fd,-1 we then have, by the triangle inequality, that:
D.tt S Aer + Dr. = Der + Arp. S 0Bf fd- = (03f + 1)f 63
since 3 = 2/0 and f f= 1/2.
Lemma C.25. For all t e MnU we have d. E Vr-
Proof. Let S be the set of all [T] such that there exists g [T] \ J with 4gr Bfd.. Define:
= argmin nu dr
v:= asg
noting that these both exist since E A. nu and E Ar S. Since 1 g U (which comes directly from the fact that there exists q,r []] M with By # yr) we have that s + 1 and hence ps exists so let d := dp, Since Ps E As with dp, d,, have Ps & l by definition of li there exists [T] M with Arp. S 3fdd This means that Ps E S and hence that E Dp., Define:
argmin Age
20

---

Published in Transactions on Machine Learning Research (10/2025)
that Aw,t Dc.
We have two cases. First consider the case that v = t. In this case we have t E S so that there exists g [T') \ M such that Ag, S ffh, By definition of w we have that Awa S Ag,t so Aw,t S 3fgt and hence, by definition of y and since t E U and w & M, we have De = yw- Since Aw, < Xb, we have, by definition of Di, that you E V Hence, Dr 34 as required.
Next consider the case that
Choose u E [7] follows:
If Ps then since ps $ U, choosing u gives us, by definition of y, that De yu-
I & ps then, since v E Pp, and 8, u E Ar, we have o DD so, since U, we have, by Lemma C.4 that u. So 2 u and so, by definition of 9 and S, choose [2] such that Da. S fd and D. yu-
Either way, have Au, S ffd, and d. yu. Since E A, (et) let q A, be such that Po We have, by Lemma C.24 and the triangle inequality, that:
Am. I Am, + Dr, S 0, 63f4
Since q E Ar and dg > d, we must have, by definition of v, that q $ S since M we also have:
Degq ffd
Substituting this inequality into the previous and rearranging gives us:
0g Bf Bg
63f B(1 6)
so that:
n 011(3(1 x))
Since d, dg - 1 and 4N fdv (as v P₂) then have, from the triangle inequality and Lemma C.24 that:
D I Drg + Aq + Aun S 603 + fóu + fp
= ( + (1+ f) < (03 + (1 + ()/f1)//((((00000))))
100
So that Yu E V1. Since 0. = Yu, all that is left to do now to prove that û. d.- To prove this need only show that for all E (D, (A)
have G. 0p. To show this take any such E (D, nA. Since E Dp, and s, E A, we must have r E D. and hence, by Lemma C.4 and the fact that E U, we have r E U. Since d, > d, and E Ar we have, by definition of v, that S. So E U S and hence, by definition y and S, we have Or = Up. as required.
Lemma C.26. We have:
Σ EE(T]
Ellr, - lloll Σ ur IEM
Proof. By Lemma CP3 we have:
Σ
Blee,g
Leyyal Σ
Elle, Le 0
MM
AE(T]\M
By Lemin C.23 we have, for all E M U1, that di = v1 Dt. So by Lemma C.25 we have, for all E M, that Gr )/. Hence, we have:
Σ
Elees l Σ
max maxE Eler, Cepeel = Σ 14
aE)i
TEM
1eM
rEM
21

---

Published in Transactions on Machine Learning Research (10/2025)
Combining these two (in)equalities gives us:
Σ
gl L =
Eleg,0 - e + >
Ellr, - -. 50+ Σ1= Σ 1r.
AE(T]
ME(TIVM
REMM
rEM
LEM
required.
Lemma C.27. We have:
R(y)= S Σ Mr + ((p+ V Wln(1/A)2 VKT)
BEM
Proof. By linearity of expectations we have:
R(y) =
Σ
Elli,a. lx,ell = Σ
Elle,0. legell + Σ
Bibe.g - leyaal
[E[T]
ME[T]
LE(T]
Substituting lemmas C.22 and C.26 then gives us the result.
This completes the proof.
D Proof of Theorem 4.1
We first note that the only effect that has on the bound is that the contexts can be moved by distance of to Since c < (1 5) min.g[N] ri/2 and & > 1 is arbitrary when can hence assume, without loss of generality, that e = 0. We can hence apply Theorem 5.2 with our choice of margin M.
Let ÿ be an extension of y such that (B(u,.r:) decision boundary of y.
[N]] covers the decision boundary ÿ. Let be the
Definition D.1. For all t E [2'] let ae be the minimiser of A out of all E [T] M with ye # we Since
((xz) # (( choose b, E DD such that b, lies on the straight line from 2, to Eq.. Since b, E DD choose i, E [N] such that b, E B(v,, Definition D.2. Define = (T)) For all E [T] define je as the minimum number in [J] {0} such that I₁ ((v,, 2 (.,,). Note that since Tt, 2 T-G this is defined.
Lemma D.3. Given E [T] with je 0 we have n 2 2 - 1)rr.
Proof. By definition of je we have that & B(us, 2 (ri,, since b. E TT) we have, by the triangle inequality, that:
|| bull 2 1|ate vill - lbb Uia 2 gii- Ti 2 22h-1 1)ra.
Since be is on the straight line from Ie to Zye we have || x. 2 ||eee - b, By definition of ge we have
|| Zz = D.g. --- Putting together gives us:
ttt = 1|z,- x 2 || - bell 2 20 2 1)r;
as required.
Lemma D.4. For all t e [T] with je = O we have 7 > 2 - 1)ri.
Proof. Since qi & M we have & Blo ETa,) so since be E Blvi, ra)) we have, by the triangle inequality, that:
|| - b.ll 2 1| vi ll l|b, wi.ll 2 Eri Ti, = -(5-1)ra
Since is on the straight line from 2, to Zgg. we have || - Zzg. |l 2 || bell- By definition of qe we have || zz Drgu = Putting together gives us:
7t I Iqall 2 || b.ll 2 (E 1)rr, 2/--1 1)rs.
required.
22

---

Published in Transactions on Machine Learning Research (10/2025)
Definition D.5. Let S be subset of [T] of maximum cardinality subject to the condition that for all 8 8 with * t we have As,t 27t.
Definition D.6. For all E [N] and
E [J] U (0) define:
S/ = {t 8 Je =
Lemma D.7. For all [M] and j E [J] {0} we have اربك E ((1)
Proof. Let r' gr and w z(E - 12. By lemmas D.3 and D.4 we have, for all E St.j. that:
z 2 (5 1)ri, =23-1(6 1)r; wr'/2
s0, by definition of S, we have, for all 8, I E Sig with 8 + i, that ||x. xzll > wr'. Also, for all E Stg we
have, by definition of je, that:
Ft (1, 2 gr..) B( Er.) ((),,r))
So all the elements of Súg are contained in ball of radius r' and are all of distance at least wr' apart. Since w is positive constant and the dimensionality constant we have the result.
]
Lemma D.8. We have & E ON lT)))).
Proof. We have:
S
Stg iE(J(]E
U
U
so that by Lemma D.7 we have |S] E O(NJ). Since C a constant we have E ((I(T)) and hence
[S] E ((NIn()) By definition of and S we have that v = |S] which completes the proof.
Lemma D.9. We have In(1/) E ((n(T))
Proof. Let be the element of [T) that minimises 7t. so that = 7t- By lemmas D.3 and D.4 we have
A n 2 1)r,, 2 r5, 1)/2 M(ra) so since rú 2 T-C (where C is constant) we have the result.
Since the desired bound is vacuous when N > T we can assume otherwise so that by lemmas D.8 and
D.9
we have:
v In e O(N (nT)))
Substituting this into Theorem 5.2 whilst noting that μ4 for all t E M, then gives the result.
E Proof of Theorem 4.2
Choose set of N' disjoint balls of radius 2 whose union is subset of X. Let the centre of the k-th ball be denoted zę- Now partition [T/2] into N' sets each of size O(T/N'). Let the k-th such set be denoted Pt. For each & E [N'] and t E Pk let := 2k- By applying the lower bound on the multi-armed bandit problem (sec Lattimore & Szopesvári (2020) independently to each these scts of trials, Nature can choose some sequence losses and a sequence (D) 1 E [N')) C [K] such that for all [N') we have:
Elli,,. l Es (IVes((KKK)) ((]]))) -2 TEP
Σ
=2(VKT/N) (VKT/N)
For all & E [N'] and all & Pk. define Vt = Sr. Summing the above equation over all k: E [N'] gives us:
Σ Bllea, leme En (
23

---

Published in Transactions on Machine Learning Research (10/2025)
Let M 1, Mj. 8, E M. It is straightforward for Nature to choose losses and sequence (yr M) such that:
For all t E M choose 2t E B(2x++1:7) in such way that a, # for all
Σ
Eili,a - 4e 2 1MI/2
BEM
For all E [T/2+ - M 1.7] choose 21 == 21 and y/ := 91.
Note that now have:
R(y) 2
For all & [N') let De be the boundary of the k-th ball. i.c. Dr is the set of all x E X with || -2--2 2x 2 Note that DR can be covered by (11) balls of radius such that none of the centres in {ar K'' [N]] are contained in the union of these balls, when each is enlarged by a factor &.
Since ( r( rRUURE(NT)) Dx covers a decision boundary of y we have now shown the existence of a boundary cover of cardinality O(N') in which each ball in the cover has radius and the only trials & in which de is in the union of the balls in the cover, when each is enlarged by factor &. are those trials E M.. This completes the proof.
F Proof of Theorem 4.3
Without loss of generality assume that d = K = 2. Given any algorithm we will now devise strategy for Nature. On each trial & E [T] we shall maintain values Pt, qt E [-1/2, 1/2] with pt < ạ-- We initialise with P1 = 1/2 and Q1 == 1/2. On trial t we choose:
= ((p: + 9)),2
We then choose yr [2] that P(a: yol s 1/2. Next we choose 4,1 and E,2 follows. If y 1 then & and f are concentrated entirely on 0 and 1 respectively and if = 2 then l and 4,2 are concentrated entirely on and 0 respectively. Note that:
Ellr,0r - -e 1/2
If ye then we define Pe+1 = Te and l++1 = ge. On the other hand, if ye 2 we define Pr11 == Pe and g++1 = z1. Finally define:
Note that the {(T, [-122,11)) is decision boundary of y. Hence the pair of balls B((r, 1/4), 1/4) and B((T,- -144, 1/4) is boundary cover of y. Since neither of these balls contains any context in (x, (T]) we have the result.
G Proof of Theorem 4.4
The proof proceeds in that of Theorem 4.1 but using the sharper Theorem 5.2 instcad of Thcorem 5.1 Since < 1/T the binning step moves the contexts by such small amount that can, without loss of generality, assume = O. Define:
r: (K/T)avi2r
Note that by definition of we can choose some set C with |C| E Ö(r- such that the union of the set of balls of radius with centres in C covers D. Append C onto the end of the trial sequence (with associated losses drawn from v). Since [C] < T we ignore the increase in the time horizon caused by this appending.
24

---

Published in Transactions on Machine Learning Research (10/2025)
Now define the margin M to be the set of all E [T] such that ae & C. but 24 is within distance of 2r from element of C. Following the proof of Theorem we have:
V (((C) cor In(T))
(1)
Note that, since the density is bounded, have that for all the expected number of trials t [T] in which Ta is within distance 2r of x is in O(r"T). Hence, we have that:
|||M|| O(C]r"T) S 00 T))
(2)
Now take any E M. Since 2t is at distance at most 2r from element of C, we have Ds,t 2r for some E [T] \\ M. Hence, we have that:
Ne Elli,s L = B(le,0(r0) (e, P)((z) (o(())((1))
(3)
for some [T] with:
| x=ll = Aue ((A.,)) we have:
(4)
By Equation
Pi(a,) (xt) S (1g) + O(1 =+11 PB(x,) (xig) + O(rP)=
= min V/ (Zg) + O(PP) S Pi(a,) + O
KE[K]
which, upon substitution into Equation 3 and noting Equation
gives us:
Ne S (Ia)))(Iaa)) ()(a.)) (2x) + O(+*) E O(1 2r|1 + r O(r))
Substituting into Equation
(2 then gives us:
E
M4
0(pittd-T)
LEEM
So, by combining with Equation and hence, given the optimal tuning of P, we have:
I we have, by Theorem 5.2 that:
E [((y)) δ (rotd-OT + (o + r-r-0 /p) v KT
E [R()) Ö (1otd--0 Vr-OKT
which, noting the definition of gives us the result.
25


Reviews:
[{"review_id": "zQrhK1Udm0", "reviewer": "Reviewer_B2Rq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the contextual bandit problem in general metric spaces. The main contribution is to propose and analyze an algorithm (HNN) for the adversarial setting where no assumptions are made on the space, or how the losses and contexts are generated. When the space is Euclidean, the algorithm is shown to possess regret bounds which can be better than existing methods for the adversarial setting. Regret bounds are also obtained for the i.i.d stochastic setting where the losses and contexts are drawn in an i.i.d manner from an underlying distribution. Experiments are conducted on some real datasets which show that the proposed method can outperform existing methods designed especially for the i.i.d stochastic setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "--------------\nStrengths\t\n--------------\n1. The fully adversarial contextual problem for general metric spaces has been addressed in a very limited sense in the literature, as noted by the authors. Moreover, the existing work of Pasteris et al. (2023) is not adaptive to the density of the contexts. This limitation is overcome by the proposed HNN algorithm which is adaptive to the local density of the contexts, and other quantities. \n\n2. The experiments on two real datasets demonstrate that HNN can outperform existing methods which are designed especially for the i.i.d stochastic setting.\n\n---------------------\nWeaknesses\n--------------------\n\n1. The proposed algorithm and framework seem to rely heavily on the work of Pateris et al. (2023). In particular, the HNN algorithm is a modification of the CBNN algorithm of Pasteris et al.  which does reduce the novelty somewhat. While some effort is made to explain this, I think the main conceptual difference between the two methods could be explained cleanly somewhere to make the difference more transparent for the reader.\n\n2. In terms of the proof techniques themselves, it is unclear how much of it relies on the mechanism developed in Pasteris et al., and what is the new component/difficulty-in-analysis, in the present paper? This could be explained more clearly in the main text, after the statement of the theorems, to make the ideas more transparent.", "audience_yn": "Yes", "audience_explanation": "The bandit problem has a long history by now, and is of considerable interest to researchers working in statistical learning theory. So this work could potentially be of interest for this community.", "requested_changes": "1. From the plots provided for the experiments section, it is very hard to distinguish between the different methods due to similar colour schemes, small font sizes and thin line styles. This can be improved substantially in order to help the reader check the plots in an easy manner. \n\n2. For the stochastic i.i.d bandit problem, isn’t it a bit pessimistic to apply the HHN method – which is developed for the adversarial setting – to an easier setup? \n\n3. In terms of the writing, and the further to the points raised earlier, I think some parts of the introduction section could be improved. For e.g., in para 2 – explain what is meant by the “i.i.d stochastic” setting. On page 2 (top), what is $p_t$? In Section 1.1, instead of having a single long paragraph which is quite hard to parse, it would be better to structure the writing into smaller paragraphs so that the reader can follow the story more easily.\n\n4. A minor comment – the language could be toned down at certain places in the text, e.g., “…regret bound is fantastic…” on pg. 1, “…brilliant performance of our algorithm…” on pg. 7.", "broader_impact_concerns": "No such concerns since the work is theoretical in nature.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "N92SdxSTkA", "reviewer": "Reviewer_usNK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the Contextual Bandit problem in metric spaces and proposes a new computationally efficient algorithm called Hierarchical Nearest Neighbour (HNN). The authors highlight that HNN is designed to address the \"fully adversarial problem,\" where no assumptions are made about the metric space itself or the generation of contexts and losses. They contrast HNN with previous work, including Slivkins (2009) and Nearest Neighbour (NN) (Pasteris et al., 2023).\nThe major difference from the NN is that HNN introduces a hierarchical tree structure on the nearest neighbor classes and utilizes such a tree structure to reduce the computation complexity per trial.\n\nIn the bounded metric space's dimensionality setting, the author claims HNN is highly efficient, with a per-trial time complexity that is polylogarithmic in both the number of trials and the number of actions.\nThe author first introduces a tree updating algorithm based on the belief propagation (Delcher et al., 1995) and achieves the per-trial time complexity of $O(K\\ln(T))$.\nThe author also mentions that HNN can be further optimized by using the CBNN algorithm (Pasteris et al., 2023) for a per-trial time complexity of \n$O(\\ln(K)\\ln(T)^2)$.\n\n\nThe performance of HNN is analyzed in various settings. For the Euclidean bandit problem, the authors provide a regret bound that is based on the concept of a \"boundary cover\" of the comparator policy's decision boundary.\nThe author proves the regret upper bound of HNN in the Euclidean space is $O(N\\sqrt{KT})$ (Theorem 4.1) while the regret lower bound is $\\Omega(N\\sqrt{KT})$.\nThe author compares HNN to the NN algorithm, arguing that NN can be arbitrarily bad in the mixture metric space case while HNN can still maintain a good regret guarantee.\nThe author analyzes HNN's performance in the i.i.d. stochastic setting, showing that it is competitive with and can sometimes outperform algorithms specifically designed for that case. \nFinally, a more general regret bound is provided for arbitrary metric spaces and shows that the regret upper bound is $O(\\sqrt{KT})$ (Theorems 5.1 \\&5.2).\n\nThe paper includes experimental results on two real-world cyber-defence datasets: the UCI firewall dataset (int, 2019) and the CICIDS2017 intrusion dataset (Sharafaldin et al., 2018).\nThese two datasets are stochastic experiments.\nOn the UCI dataset, HNN was closely behind NN with a binning radius of 0.1, while on the CICIDS2017 dataset, HNN achieved the best performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims made in the submission are well-supported by both theoretical and empirical evidence. The paper uses mathematical proofs to back its theoretical claims about the algorithm's performance and efficiency. It also presents compelling experimental results from real-world datasets that demonstrate its practical effectiveness.\n\n1. **Regret Bounds**: The author provides several regret bounds for HNN under various conditions.\n    For the Euclidean bandit problem, the author presents Theorem 4.1 to prove that HNN achieves a regret bound $\\|\\mathcal{M}\\| + O(N\\sqrt{KT})$, where $|\\mathcal{M}|$ is the number of history data located in the expanded boundary set. For general metric spaces, the author presents Theorem 5.1 by generalizing the covering in the Euclidean space to the packing number. Furthermore, the author gives an even more refined bound to drop the dependency on $\\|\\mathcal{M}\\|$ in Theorem 5.2.\n\n2. **Computational Efficiency**: HNN's efficiency has been discussed in Section 3. The author explains that HNN can achieve a per-trial time complexity of $\\mathcal{O}(K \\ln(T))$ in updating the posterior distribution on the action via online belief propagation. \n    The above step can be improved by utilizing the CBNN algorithm to achieve a $\\mathcal{O}(\\ln(K)\\ln(T)^2)$.\n\n3. **Comparison to NN**: The author makes a convincing argument for HNN's superiority over the NN algorithm by using an example where the metric space is two-disjoint. The author demonstrates that NN, which uses a single binning radius, cannot adapt to variations in context density. This limitation causes a significant increase in regret, whereas HNN's adaptive nature allows it to maintain better performance.\n\n4. **Empirical Claims and Evidence**: The paper includes empirical evidence from two experiments on real-world, i.i.d. stochastic datasets to support its claims about HNN's practical performance and show that HNN can achieve a comparable performance to NN.", "audience_yn": "Yes", "audience_explanation": "I believe some individuals in the TMLR audience would be interested in the findings of this paper, particularly due to its dual focus on theoretical guarantees and practical efficiency.\n\nFor researchers and theorists in the TMLR community, the paper's main appeal lies in its rigorous theoretical analysis of the HNN algorithm. The authors introduce a novel approach to the contextual bandit problem in metric spaces, specifically addressing the setting where no assumptions are made about the context or loss sequences. The author provides comprehensive regret bounds for HNN, first for the important special case of Euclidean spaces (Theorem 4.1) and then for general metric spaces (Theorems 5.1 and 5.2). This theoretical work is significant because it shows that HNN's performance is adaptive to the local density of contexts and the smoothness of the comparator policy's decision boundary, addressing a key shortcoming of prior work like the NN algorithm. The inclusion of an almost matching lower bound (Theorem 4.2) further strengthens the theoretical contribution.\n\nFor practitioners and engineers, the paper's findings are valuable due to HNN's computational efficiency and strong empirical performance. The algorithm is highly efficient, boasting a per-trial time complexity that is polylogarithmic in both the number of trials and the number of actions when the dimensionality of the metric space is bounded. This efficiency is crucial for real-world applications with large datasets. Furthermore, the paper provides compelling evidence of HNN's effectiveness through experiments on real-world cyber-defense datasets. The results show that HNN not only performs well but can even outperform other state-of-the-art algorithms designed specifically for the i.i.d. stochastic setting, despite being built for the more general adversarial case. This demonstrates that HNN is a robust and powerful tool that can be applied effectively in practice.", "requested_changes": "The author claims that the HNN algorithm is designed for the adversarial problem, where no assumptions are made about the generation of contexts or losses. The experiments presented were, in fact, on datasets that are primarily i.i.d. stochastic.\nWhile the paper does not include experiments on a purely adversarial setting, the theoretical analysis and regret bounds provided (Theorems 4.1, 5.1, and 5.2) might lack empirical evidence.\nThe author should include more empirical evidence to support their claim to show the performance of HNN in the adversarial contextual bandit setting.\n\nThe related work section has been expanded to include more recent and relevant contextual bandit work.\nIn the contextual bandit area, many existing works have both theoretical analysis and empirical evidence, such as SquareCB [1] and ILOVETOCONBANDITS [2].\nIt would be better to include more discussion about the position of this paper in the related work section.\n\nTo provide a clearer and more formal statement on the computational complexity, a dedicated theorem statement could be added. In this theorem statement, the author can formally state the per-trial time complexity for HNN under different implementations: When using the described belief propagation, the per-trial time complexity is $O(K\\ln(T))$ under the conditions outlined in the paper.\nWhen using the CBNN algorithm, the per-trial time complexity is $O(\\ln(K)\\ln(T)^2)$.\n\nWhile the paper provides a detailed description of the HNN algorithm, including its core components, it would be better to give a formal algorithm block, detailing the inputs, outputs, and the step-by-step process.\nAn explicit algorithm block would greatly enhance clarity and reproducibility. \n\n\n*[1] Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles*\n\n*[2] Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits*", "broader_impact_concerns": "The Broader Impact section of the paper raises some concerns about the comparison of the HNN algorithm to existing works, both theoretically and empirically. The main point is that the submission might not have included a sufficient number of comparisons. However, the authors do compare HNN to several other algorithms, including NN, but I would like to see the author includes more popular existing works, such as SquareCB, and various classification-based methods.\n\nA second concern revolves around the experimental evidence for HNN's performance in the adversarial setting. The paper claims that HNN is designed for this setting, but all the provided experimental results are from i.i.d. stochastic datasets. While the authors do provide theoretical proofs for HNN's effectiveness in the adversarial setting, the lack of empirical support for this specific claim could be seen as a weakness.", "additional_comments": "I have several questions and hope the author can resolve them in the revision:\n\n\n1. For steps 1 and 2 of HNN, is it possible that we can find multiple $s_d$ satisfying the \\textit{c}-nearest neighbour criteria? If so, how to break the tie?\n\n2. For the lower bound in the contextual bandit with a metric setting. Is it possible to include a lower bound in the general metric setting?", "extra_scores": {}, "extra_text": {}}, {"review_id": "mqElIakMvM", "reviewer": "Reviewer_SCsi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an algorithm called HNN for adversarial contextual bandits, which leverages metric information across different trials to improve upon the existing HH algorithm in certain regions. The authors also demonstrate the adaptivity and low complexity of their algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides rigorous theoretical proofs and experimental studies, although some arguments raise questions. Please refer to the following issues.", "audience_yn": "Yes", "audience_explanation": "The analysis of similarities across different trials in the study of contextual bandits offers valuable insights for real-world decision-making.", "requested_changes": "I have some questions as follows.\n\n1. Can $\\mathcal{M}$ be linear to $T$? If so, can you provide some cases when it's sublinear? Otherwise, the bound becomes relatively weak. Similar to $\\sum \\mu_t$.\n\n2. $N$ in Thm 4.1 actually contains some assumptions on the space implicitly. For general space, $N$ is not finite. So, the statement \"no assumptions are made about the space itself\" is not very accurate. I advise giving some examples, or classes, when $N$ is bounded.\n\n3. On page 10, \"We believe that typically we will have\". Could you give some explanation or intuition on why this statement is right?\n\n4. Since the algorithm is designed for adversarial cases, why don't you conduct some experiments to see the advantages of HNN in this situation?\n\n5. On page 12, the statement \"but are followed closely by HNN\" is not accurate. The loss of HNN is almost twice the loss of NN 0.1. This result shows that the performance of HNN is not comparable to that of NN. Could you add some discussion on it?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)