Nearest Neighbour with Bandit Feedback
Authors: Stephen Pasteris
Chris Hicks
Vasilios Mavroudis
Venue: NeurIPS 2023 poster (2023)
Keywords: Nearest Neighbours
Contextual Bandits

Abstract: In this paper we adapt the nearest neighbour rule to the contextual bandit problem. Our algorithm handles the fully adversarial setting in which no assumptions at all are made about the data-generation process. When combined with a sufficiently fast data-structure for (perhaps approximate) adaptive nearest neighbour search, such as a navigating net, our algorithm is extremely efficient - having a per trial running time polylogarithmic in both the number of trials and actions, and taking only quasi-linear space. We give generic regret bounds for our algorithm and further analyse them when applied to the stochastic bandit problem in euclidean space. A side result of this paper is that, when applied to the online classification problem with stochastic labels, our algorithm can, under certain conditions, have sublinear regret whilst only finding a single nearest neighbour per trial - in stark contrast to the k-nearest neighbours algorithm.

Nearest Neighbour with Bandit Feedback
Stephen Pasteris The Alan Turing Institute London UK spasteris@turing.. ac.
Chris Hicks The Alan Turing Institute London UK
Vasilios Mavroudis The Alan Turing Institute London UK
ymavroudis@turinng.eer uk
Abstract
In this paper adapt the nearest neighbour rule the contextual bandit problem. Our algorithm handles the fully adversarial setting in which no assumptions at all are made about the data-generatic process. When combined with sufficiently fast data-structure for (perhaps approximate) adaptive nearest neighbour search, such navigating net, algorithm is extremely efficient having a per trial running time polylogarithmic in both the number of trials and actions, and taking only quasi-linear space. We give generic regret bounds for our algorithm and further analyse them when applied to the stochastic bandit problem in euclidean space. We note that algorithm can also be applied to the online classification problem.
1 Introduction
In this paper we adapt the classic nearest neighbour rule to the contextual bandit problem and develop an extremely efficient algorithm. The problem proceeds in trials, where on trial t: (1) a context x; is revealed us, (2) we must select an action a,, and (3) the loss ft [0, 1] of action a, on trial is revealed to us. We assume that the contexts are points in a metric space and the distance between two contexts represents their similarity. A policy is mapping from contexts to actions and the inductive bias of our algorithm is towards learning policies that typically map similar contexts to similar actions. Our main result has absolutely no assumptions whatsoever about the generation of the context/loss sequence and has no restriction on what policies we can compare algorithm to.
subroutine, a data-structure that performs c-nearest neighbour search. This data-structure must be adaprive in that new contexts can be inserted into it over time. An example of such a data-structure is the Navigating net [17] which, given mild conditions on our metric and dataset, performs both search and insertion in polylogarithmic time. When utilising data-structure of this speed our algorithm is extremely efficient with a per-trial time complexity polylogarithiic in both the number of trials and actions, and requiring only quasi-linear space.
Our algorithm requires,
As example will apply our methodology to the special of the contextual bandit problem in which the context sequence is drawn i.i.d. from probability distribution over the d-dimensional hypercube. In this case, for any policy 9 with finite-volume decision boundary, our algorithm achieves Ô (<t(ddt))) regret
ÿ, where measures the magnitude of what is essentially the part of the decision boundary of ý that lies in the support of the probability distribution.
In the course of this paper develop some novel algorithmic techniques, including new algorith- mic framework CANPROP and efficient algorithms for searching in trees, which may find further application.
We now describe related works. The bandit problem 20 was first introduced in 28 but was originally studied in the stochastic setting in which all losses are drawn i.i.d. at random [1] [I] 3]. However, our world is very often not i.i.d. stochastic. The work of 4 introduced the seminal EXP3 algorithm which handled the case in which the losses were selected arbitrarily. This work also
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

introduced the ExP4 algorithm for contextual bandits. In general this algorithm is exponential time but in some situations can be implemented in polynomial time- such as their ExP3.S algorithm. which was bandit version of the classic FIXEDSHARE algorithm [14]. In [2 the ExP3.S setting was greatly generalised to the situation which the contexts where vertices of graph. They utilised the methodology of [8], [T6] and [13] in order to develop extremely efficient algorithms. Although inspiring this work, these algorithms cannot be utilised in our situation as they inherently require the set of queried contexts to be known a-priori. In the stochastic case another class of contextual bandit problems are linear bandits [21], [5] in which the contexts are mappings from the actions into R.. Here the queried contexts need not be known in advance but the losses must be drawn i.i.d.
from a distribution that has mean linear in the respective context. The k nearest neighbour algorithm was first analysed in [6]. The work 26) utilised the k nearest neighbour methodology and the works [9] and 18] to handle a stochastic contextual bandit problem. However, their setting is extremely more restricted than ours. In particular, the context/loss pairs must be drawn i.i.d. at random and the probability distribution they are sampled from must obey certain striet conditions. In addition, on each trial the contexts seen so far must be ordered in increasing distance from the current context and operations must be performed on this sequence, making their algorithm exponentially slower than ours. Our algorithm utilises the works of [22] and 7 as subroutines. It should be noted that the later work, which was based on [33], was improved on in ||| we leave it as an open problem as to whether we can utilise their work in our algorithm.
30 BIJ 2 [6]] but as far we know ours is the first work to give non-trivial bound for our problem in general (with no additional assumptions). As far as we are aware our above example bound for the fully stochastic case in euclidean space (with finite decision boundary) is also novel the works
Algorithms for contextual bandits in metric spaces have been studied in [3
30 24 26 scale as ((T((4)))(4+) in general (and [24]]]]] 26 also require additional assumptions). As far as we are aware we are also the first work, stochastic or otherwise, to give a regret scaling as O(T1/2) when the contexts are drawn from well-separated clusters (i.e. there is a positive distance between all pairs of clusters) in fnite-dimensional metric space, and the comparator policy is constant on each cluster (we do, however, conjecture that in the stochastic case (26] can obtain such a regret scaling here- but, as stated above, is exponentially slower).
2
Notation
Let N be the set of natural numbers not including O. Given natural number m E N define [m] := Lij E N | S. m). Given a predicate p we define [p] := 1 if p is true and [p] == 0 otherwise. We define log(-) and In(-) to be the logarithms with base 2 and e respectively. Given sets A and B we denote by B the set of all functions f A + B and by 2 the set of all subsets of A. We write [0, 1] to mean that the value x is drawn from the uniform distribution on [0, 1].
All trees in this paper are considered rooted. Given a tree I we denote its root by r(J), its vertex set by J. its leaves by J and its internal vertices by Jt. Given a vertex e in a tree J we denote its parent by (v) and the subtree of all its descendants by ( Given an internal node v in (full) binary tree J we denote its left and right children by {)( and (-((t) respectively. Internal nodes in a (full) ternary tree J have an additional child V ( called the centre child. Given vertices v and of in a tree I we denote by y (v, v') the least common ancestor of v and v/: i.e. the vertex of maximum depth which is an ancestor of both and v'. We will drop the subscript J in all these functions when unambiguous. Given a tree J, a subtree of J is a tree whose edge set is a subset of that of J.
3 Results
3.1 The General Result
We consider the following game between Learner (us) and Nature (our adversary). We call this game the similarity bandül problem. We have K actions. Learning proceeds in trials. A-priori Nature chooses a sequence (n(()] E (T) \ (1)) where for all 1 E [T] (1) we have n(l) E [t - 1]. A-priori Nature also chooses a sequence of loss vectors (Le I E [T]) C [0, 1 but does not reveal them to Learner. On the t-th trial the following happens:
2

---

1. If >> then Nature reveals n(t) to Learner.
2. Learner chooses some action de E [K].
3. Nature reveals L,a, to Learner.
Intuitively, given a trial t E [T] \. (1), n(tt) is similar trial to t. Our inductive bias is that if an action E [K] is good for trial then likely that a will also be good for the similar trial nt)). We will measure our performance with respect to any policy y. where policy is defined as a vector in [K]*. Specifically, we wish to minimise the y-regret, which is defined as the difference between the total cumulative loss suffered by Learner and that which Learner would have suffered if it had instead chosen az equal to yr for all trials I. Formally, this quantity defined as follows:
Definition 3.1. Given policy y E [K] we define the y y-regret of Learner as:
R(y)= = Σen
lea Σ rE[T]
AE(T]
The following quantity quantifies how much a policy agrees with our inductive bias.
Definition 3.2. Given policy y E [K]T we define the complexity of y by:
( 1+
Lye # *y(et]l-
We now state main result:
Theorem 3.3. Consider the similarity bandit problem described above. Our algorithm CBNN takes a single parameter p > and, for all policies y [K]² simultaneously, obtains an expected y-regret bounded by:
E(R(y)) E E ((++010))
VKT
P
where the expectation taken over the randomisation of the algorithm. CBNN needs no initialisation time and has per-trial time complexity of:
((n(T))
3.2 Bandits in Metric Space
We consider the following game between Learner (us) and Nature (our adversary). We call this game the metric bandit problem. We have K actions and metric space (C, A) where C is (possibly infinite) set of contexts and for all x, x' E C we have that A(x, x²) is the distance from æ to a'. We assume that Learner does not necessarily know (C, A) a-priori but has access an oracle for computing A(x, 2') for any x, x' E C. Learning proceeds in T' trials. A-priori Nature chooses and sequence of loss vectors (l, t E [T]) [o, 1] but
sequence of contexts (x, |t E [T]) does not reveal them to Learner. On the f-th trial the following happens:
1. Nature reveals F, Learner.
2. Learner chooses some action 0₃ E [K].
3. Nature reveals fi,,, to Learner.
Here, our inductive bias is that if an action a e [K] is good for a context then it is likely also good for contexts that are near to a with respect to the metric A. Our algorithm for this problem will be based on the concept of c-nearest neighbour which is defined as follows.
Definition 3.4. Given some 2 1, finite set S C C, and a context C we have that some & E S a c-nearest neighbour of x in the set S if and only if:
Axx, < min A(r,²') xr
In order to utilise CBNN for this problem we need a data-structure for aduptive nearest neighbour search. This problem as follows. We maintain a finite set S C At any point time we must either:

---

Insert a new context C. into the set S and update the sata-structure.
Given a context C, utilise the data-structure to find c-nearest neighbour of x in the set
An efficient example of such data-structure is the navigating net [17].
We can now reduce the metric bandit problem to the similarity bandit problem as follows. On any trial & E [7] {1) choose itz to be a c-nearest neighbour of zı in the set (xt E 1]}. Then choose (t) E i - 1] such that Tn(t) = ft.
We will utilise the following definition in order to bound the complexity of policies when n(-) is chosen this way.
Definition 3.5. Given a function ÿ C + [K] and a set X C then for all define:
(1. ú. X) ( [r, x²) of E X ((x') # ú(x)}.
We can now bound the complexity of policies as follows, noting that by Theorem 3.3 this leads directly to a regret bound.
Theorem 3.6. Assume we have a sequence (xt It E [T]) S C and a function 9 : C [K]. Define X : {xa t [T]} and for all E [T] define yt ((x1). Assume that for all [T] {1} have that Øn(t) a c-nearest neighbour of It in the set {αę I - 1]]. Then byy) is no greater than the minimum cardinality of any set S C C in which for all X there exists x E with (zz x²) < xxx D, ///3c.
strength of our algorithm is that can be combined with binning algorithms, where the contexts Tr are partitioned into sets called bins and, for each bin, all contexts in that bin are replaced by single context called the centre of the bin. The advantage of binning is that ((x V, X)) can increase, so that by Theorem 3.6 may have that (yy) decreases. However, when context 25 is binned (i.e.
replaced by its bin centre) its label ((2,) can change, increasing the final regret by ( In Section 3.3 we give an example of the utilisation of binning.
3.3 Stochastic Bandits in Euclidean Space
As an example we now consider the utilisation of the above algorithms for the problem of stochastic bandits in [0, 1] for some arbitrary E N which we view as constant in our bounds. Here we will only focus what happens in the limit T -> oo. We focus on stochastic bandits for simplicity, but the same methodology can be used to study the limiting behaviour of adversarial bandits. In this problem we have unknown probability density Ø [0, 1 x [0, 1] - R. We have T trials. On trial & the following happens:
1. Nature draws (Ze, Ex) from j.
2. Nature reveals 2, to Learner.
3. Learner chooses some action 0₂ E [K].
4. Nature reveals l,,,; to Learner.
To aid us in this problem we will first quantise the contexts 2, to grid. Note that this is an example of binning. The grid defined as follows:
Definition 3.7. Given q N define Og be the set of vectors in [0, 1]d in which each component is an integer multiple of 1/q.
On each trial t we will first quantise the vector 2, by defining to be its nearest neighbour (w.rt. the euclidean metric) in Gd. where q == (T'K))1/(4))) 1/d+1), Note that this can be done in constant time per trial. As in Section 3.2 we then use CBNN to solve the problem by defining ru(t) such that zn(() is
c-nearest neighbour (w.r.t the euclidean metric) of x, in the set {xx I E [t 1]}. We consider as constant in our bounds.
As before, we will compare our cumulative loss to that policy that follows function ý [0, 1]d K]. Our regret bound will be based on the following quantities:

---

Definition 3.8. Let be the marginal of ji with respect to its first argument and let A be the euclidean metric on [0, 17a. For all > define:
E(u,e) {o E [0, 11th 3x's E 1] u(xa) + (xx S Se}
which is the set of contexts that are within distance of the support of μs. Given y [0. 1] [K] we
make the following definitions. For any ò > 0 define:
Míÿ. p. 6) = {o E [o, 1)dh 3x' E(u,e) A(x,x) S A ((x) + 5(2))}
which is the set of contexts that are at distance no more than from the intersection of the decision boundary of i and E(H,,) c). We then define:
a(û. p)) = litn lim [
c-+06-0 5 22M((......)
1
ā(ū, = = lim lim
c- 5-+0
SZEM(G.....))
p(x)
which are essentially the volumes of the part of the decision boundary of ú that lies in the support of μA, with respect to the uniform density and the density μ respectively.
With these definitions in hand we now present our regret bound, which utilises Theorem 3.6 in its proof:
Theorem 3.9. Let q ==
For all t E [T] let ot be the nearest neighbour of z in the set 9g. For all (T) \ (1) ler n(t) be such that Fa(t) is a e-nearest neighbour of xa in the
set (xe |t' E [L - 1]}. Given some ÿ [0, 1] + [K] let == ((z,) for all E [T]. Then when
q CBNN gives
B[R(v)) E : (1+ + ā(0, A)) Kalt
as T cc.
We note that varying q and p in Theorem 3.9 will allow us to trade off the values 1, ag μd) and ā(ū, (4) in different ways.
The Algorithm
In this section we describe our algorithm CBNN, for solving the similarity bandit problem, and give the pseudocode for the novel subroutines. In the appendix we give more detailed description of how CBNN works and prove our theorems.
Instead of working directly with trial numbers we create a sequence of distinct nodes (xy E [T]) and define, for all E [T] \ (1), the node n((:;)) Fn(()- Let X' = (ax, 1 [T]]- We represent policies as functions from X into [K]. Hence, given some y X - [K]. we define the y-regret and the complexity of y as:
R(y) Σ le.0 Σ (egin)
(vv) = 1+
Σ 2EA'(Z1>
[b(2) + v(n(z))]
EE[T]
(E(T]
respectively.
4.1 A Simple but Inefficient Algorithm
To give the reader intuition we first describe our initial idea simple algorithm which attains our desired regret bound but is exponentially slower taking a per-trial time of ê(KT). The algorithm is based on ExP4 4 which we now describe. On every trial we maintain weighting De [K] + [0, 1]. We are free to choose the initial weighting wi to be any probability distribution. each trial the following happens:
1. For all a E [K] set Pt.a < EyeRK [u(a,) = a] (v)
2. Set a, with probability proportional to Pt.a
3. Receive lr
5

---

4. For all a E [K] set l,, [a ael 1aa ll//
5. For all y E [K] set 1 t wz (v) expl - (())()))))
For us we choose, for all y X' + [K] an initial weight of:
w1 (w) == (1/K) - 1)) +(() (1 (T-
Of course, we don't know (3y) a-priori, and hence we cannot implement ExP4 explicitly (and would take exponential time even if we did know (y) a-priori). Our crucial insight is the following. For any & E [T]] let Xr ;= {æy | E [t]] and for any y: X + [K] let y be the restriction of y onto X2 Then for any E [7] and for any 3/ Ar + [K] we have:
(n(()) [z))
T(K- + ((((()) - v'(']] (1 (1- (1)
wi (3) & II
yE[K] =y
REAiMfu
Note that, for all E (T] and a E [K], we can write Pt,a as follows:
Pr.a = Σ
[u(xt)= = a]ri (v) II KE(t-1]
exp(-nll,xze))
DE(K]*
Σ (1xx)) aa al *
exp(- exp(-nfles(aa))) NER-I1
II
E
wi (v).
DE[K] yy'=y'
By substituting in Equation ① have now brought Pt.a into a form that can be solved via Belief propagation [23] over the tree with vertex set X, and in which, for all t' E [t] (1), the parent xy n((r).
It is well known that for any : X - [K] EXP4 attains a y-regret at most (n(
By setting 7 == p/v KT and noting our choice of tे we obtain our desired regret bound.
4.2 Cancellation Propagation
In the remainder of this section we describe our algorithm CBNN, which is based the same idea as the simple algorithm of Section 4.1
In this subsection we describe novel algorithmic framework CANPROP for designing contextual bandit algorithms with a running time logarithmic K. is inspired by EXP3 [4], specialist algo-
rithms [ and online decision-tree pruning algorithms [TO] but is certainly not simple combination of these works. CBNN will be an efficient implementation an instance of CANPROP. Although in general CANPROP requires a-priori knowledge, CBNN is designed in way that, crucially, does not need it to be known.
We assume, without loss of generality, that K and T are integer powers of two. CANPROP, which takes a parameter 77 > O, works on full, balanced binary tree B with leaves B* = [K]. On every trial & each pair (V B x 2xx has weight w. (v, E [0, 1]. These weights induce a function
0, B + [0, 1] defined by:
0c(u) = El= E ST]w,v,SS.
SE2*
On each trial t root-to-leaf path {er. 1 [log(K) (0}) is sampled such that vr,o == r(B) and, given Ut. we have that vr,(++1) is sampled from {d((),s), (v)r,)) with probability proportional to the value of 0, when applied each of these vertices. The action a, then chosen equal to (og() Once the loss has been observed we climb back up the root-to-leaf path, updating the function w, to Wt+1-
CANPROP (at trial t) is given in Algorithm [ then it is defined to be equal to wy (v.
We note that wi-1 (v,S) is not set in the pseudocode
In Appendix we give a general regret bound for CANPROP. For CBNN we set:
1) I/(n(() ITT)/KT

---

Algorithm CANPROP at trial /
1: 2r,0 f- rBB)
17: at t (t,log(K)
2: for j j= ==0,,, 0.1,...... (log(K) 1) do
18: oe < [) (T(t)))))
3: for (((e)))) do 0e(v) + Esez (Tx E (v, end for
19: V'.log(K) t exp( hap(-166,,, / / [5))
4:
20: for j = ( (log( 1), ,)............. do
5:
21:
V1,6-11 +
6:
21, + B((((v)))) + (c((()))))
22:
Ví.5 t /t.l /
7:
for u E (<(vrs), do
8:
TT(1) + 2.. end for
23:
Vt. = ( then
24:
0t + ((1,,-1))
9:
10:
SL. [0,1]
25:
else
if SEu S (((((1)))) then
26:
0t t <(vr,j-1)
12:
Wa++1 t <(Eas)
27:
end if
else
28:
for S E 2* It E do
14:
1h.j11 t D(vts)
29:
W1+1 S) + wi(v,,,
end if
30:
Wi+1 (ūzj, ( + (i( 5)/4/r.8-1
16:
end for
31:
end for
32: end for
and for all (v,S) E 2* we set:
8) + (1 ((x (1-
(v, :=
II
(m1)
where:
(xx S) = x[ E ES]
+ [[((x) E S]].
This choice gives us the regret bound in Theorem such a way that n need not be known a-priori.
3.3 We note that CBNN will be implemented in
4.3 Ternary Search Trees
As we shall see, CBNN works by storing a binary tree A(e) at each vertex u E B. In order to perform efficient operations these trees will utilise the rebalancing data-structure defined in [22] which here we shall call ternary search tree (TST) due to the fact that it a generalisation of the classic binary search tree and, trees, the applications of TSTss are more than just searching: we shall also utilise them for online belief propagation.
shall show, has searching applications. However, for binary search
We now define what is meant by a TST. Suppose we have a full binary tree J. TST of is a full ternary tree D which satisfies the following, The vertex set of D is partitioned into two sets D and D where each vertex 8 E D is associated with a vertex (u() E I and every s E D is also associated with a vertex p² (s) E (u(s))+ In addition, each internal vertex s DT associated with vertex E(s) E J. For all E I there exists an unique leaf (D) E DD' in which ju( ((D(u)) =
Essentially, each vertex s E D corresponds to subtree (s) of I where (r(D)) J. Such vertex is leaf of D if and only if [5)] = 1. For each internal vertex E Di the subtree (s) is split the vertex {(s) into the subtrees J (4(s)), (V(s)), and (D(ss) corresponding to the children of 8. The process continues recursively.
For completeness now describe the rules that TST D of J must satisfy. We have that r(D) D and p(r(D)) = r(J). Each vertex (s)) = ((((s) and otherwise (ss is the set of all descendants of p(s) which are not proper descendants of ps(s). Given that DD this subtree is split the vertex {(s) where if s D
D represents a subtree ((s) of J. If E D then
have that E()) lies on the path from (us)) to (s)).. The children of are then defined so that J (<(s)) = (s) (4((((())))) and (p(s)) = (s) (((()(()))) and (v((s) = [(s) ((()))) iee. {(s) partitions the subtree (ss into the subtrees F((()), (p(s),, and (V(()). This process
continues recursively until [s)] = 1 in which case is leaf of D.
7

---

For all binary trees J in our algorithm we shall maintain a TST H([ of I with height (In(([D Such trees I are dynamic in that on any trial is possible that two vertices, u and u', are added to the tree I such that u' is inserted between a non-root vertex of J and its parent, and u is designated as child of u'. We define the subroutine REBALANCE(HH()) u) as one which rebalances the TST H(T) after this insertion, so that the height of H(T) always remains in (In(()D) The work of [22] describes how this subroutine can be implemented in a time of (In(IT)) and we refer the reader to this work for details (noting that they use different notation).
4.4 Contractions
Define the quantity @u == 0 and for all j NU {0} inductively define:
0j+1 (1- 7) Φj + 7 (1-b))
At any trial the contexts in fz, [t]] naturally form a tree by designating n(x,) as the parent of v.. However, to utilise the TST data-structure we must only have binary trees. Hence, we will work with a (dynamic) full binary tree 2 which, on trial I, is a binarisation of the above tree. The relationship between these two trees is given by a map y : 2, - (ix 8 E [4] where 2, is the tree 2 on trial f. For all E {xr, E [4] we will always have an unique leaf (xx) E Z in which (((()) = x. We also maintain a balanced TST 2z) of Z.
Algorithm 2 gives the subroutine GROW, which updates Z at the start of trial t. Note that GrOW,
also defines function d + such that d((u) the number of times the function n must be applied to (u) to reach ø1.
Algorithm 2 GROW, which works on Z
1: u + ((((x))
10: else
2: u* < 1(u)
11: >(u") t u
3: u' + NEWVERTER
12: end if
4: u" + NEWVERTEX
13: <(u') + u"
5: 7('') < n(x1)
14: D(u') +-
6: (u") & Ft.
15: d(u') +- d(u)
7: (xx) t ud
16: d(u") +- d(u)+ +1
8: i du") then
17: REBALANCE(H(2)).)) u²)
9: <(u") + u'
A contraction (of Z) is defined a full binary tree J in which the following holds. (1) The vertices of J are a subset of those of Z. (2) r(T) = r(2). (3) Given a vertex u E J we have 4g (u) E (2)4 and p E (zz(z(()) (4) Any leaf of I is a leaf of Z.
CBNN will maintain, on every vertex V B, a contraction A(v) as well as a TST H(A(v)) of A(v). Given I is one of these contractions, we also maintain, for all i, /' E {0, 1} and all E J. value Tr (J, u) E R.. Technically these quantities, which depend on the above function d, define a buyesian network on I which is explained in Appendix C.3 For all i E (0, 1) and all u E I we also maintain a value ny (J u) initialised equal to 1.
On each of our contractions J we will define, on trial f, a subroutine INSERT((T) that simply modifies J so that (2x,) is added to its leaves. This subroutine only called on certain trials t. Specifically, it is called on the contraction A(e) only when v is involved in CANPROP on trial t. Although the effect of this subroutine is simple to describe, its polylogarithmic-ing time implementation is quite complex. A function that is used many times during this subroutine is i 2 Z + which v(u, u') is equal to
or A if u' is contained #z(4z(u)) (u)), in (Dz() or in neither, respectively. Algorithm 3 shows how to compute this function. Now that we have subroutine for computing u we can turn to the pseudocode for the subroutine INSERT, in Algorithm 4 In the appendix we give full description of how and why this subroutine works.
8

---

Algorithm 3 Computing v(u, u') for u, v' E Z
1: 3 + H((2)
20: return
2: if uu=u =u u
then
21: else ((*) A 8 =D(s") then return
3:
return
22:
4: end if
23: end if
5: š -- Tg(u)
24: <- &
6: 5' + Tz(u')
25: while TRUE do
7: s* + lT((3,3)
26: if E 0" then
8: for E (<(s*) v(s") do
27:
return A 28: else if [(s) <(s) g then
9:
if 5 E (s)) then
10:
29:
return
11:
end if
30: else if {(s) (D()) g then
12:
3' E (s)
then
31:
return
8-8
32:
end if
14:
end
33:
for s' E f((s) v(+), ps)) do
15: end for
34:
E then
16: if' 8 o (s*)) then
35:
8 5
return
36:
end if
18: end if
37: end for
if ((s)) u & <(s*) then
38:
end while
Algorithm 4 The operation INSERT,(F) on contraction J of Z at trial
1: & H(22
29: u" pus)
2: D < H(T)
30: u' < (ū)
3: + r(D)
31: if ú 4, (w') then
4: ny + 7(xx)
32:
43(4²) ) < u²
5: while 8 Dt do
33: else
6: if (E((), ug) then
34:
DJ("') f
fu" u²
7:
8 <(s)
35: end if
8:
else if v(((s), u,) then
36: if vf"" i) then
9:
8 8 (s))
37: 4z("") + û
else if ((((s), u.) then
38: py("") +
11:
+ (s)
39: else
end if 13: end while
40: po("") ú
41: 4g("") f- Ut
á (u((s
42: end if
15: 8 *+r(E)
43: for {0, 1) do
16: while s E do
44: Ki[J, u² <
if v(g(s) u.) vE(s), ú) then
45: (r +
18:
if (E((s) w.) = then
46: end for
<((s)
47: for u {u", û, uz} do
20:
else if v (E((), uz) then
48: 5(u) d(u) d(t d
p(s)
49: end for
22:
else if v (g(s), uz) then
50: for (i, {0, (0.1) do
$ V(s)
51: if then
24:
end if
52:
T (J, u) 1 (b((w)
25:
else
53: else
26:
5- (s)
54: Ti (J, u) )B(())
27:
end
55: end if
28:
end while
56: end for
57: REBALANCE(?((T)).)

---

4.5 Online Belief Propagation
In this subsection we utilise the work of 7 in order to be able to efficiently compute the function 8, that appears in CANPROP.
Given vertex in one of our contractions I define F(J, u)) (f {0, [f()) 1} and then define:
A(J = E
II
feJ(J,N) ('EI(((()))
As stated in the previous subsection, when vertex becomes involved in CANPROP on trial t, CBNN will add (xx)) to the leaves of A(v) via the operation INSERT, INSERT,AA()), In the appendix we shall show that for each such we then have:
(z(v) ((:()))
We now outline how to compute this efficiently, deferring a full description for Appendix D.3 First note that for all contractions I and all u E J we have that A u) is of the exact form to be solved by the classic Belief propagation algorithm (23] The work of 7 shows how compute this term in logarithmic time by maintaining a data-structure based on a balanced TST of J in our case the TST H(J). Whenever, for some i {0, 1} and u' E J. the value (T, uu) changes, the data-structure updated in logarithmic time. We define the subroutine EVIDENCE(J. u') as that which updates this data-structure after (J, u') changes. We also make sure that the data-structure is updated whenever (EBALANCE(H[[]] is called. We then define the subroutine MARGINAL (J, u) as that which computes AJJ, u)/4. Hence, the output of MARGINAL(A(v), (x+)) is equal to (v).
4.6 CBNN
Now that we have defined all our subroutines we give, in Algorithm the algorithm CBNN which is an efficient implementation of CANPROP with initial weighting given in Equation
Algorithm 5 CBNN at trial f
1: GROW,
18: end if
2: "y +- 7(x2)
19: end for
3: 2r,0 f- r(B)
20: at + (t,log(R)
4: for jorj= j=0==,,...
(log(K) 1) do
21: म. < []jE[bg(K)] (e()).))
5:
for E (s(ei,),, do
22: Vellog(K) exp(- [t)
6:
(N(E))((A(U))
23: for j = log( (log K) 1)..... do
7:
(e(w) + MARGINAL(A(O)..MM me)
24: (1,6-11
V (1
8:
end for
9:
Zei + (.(((1))))) + (x((ss)))
25:
Vtj = ((v, then
26:
Ut + ((1
10:
for E ((((,,,),((U,,)))) do
27:
else
11:
TV(U) t 0z(v)/213) end for
28:
Ōt,f + <(v1,1)1)
12:
29:
end if
13:
Soy [0.
30:
(I((()))) ) 21) + W
14:
if Ses S ne( (<(())) then
15:
Des11 t 4(va.)
31:
(1((,,,)))) ). ut) s 1/
32: EVIDENCE (A(,)) Ut)
16:
else
17:
Meit1 t- D(vas)
33:
EVIDENCE A A(0t,)),
34: end for
Acknowledgments
We would like to thank Mark Herbster (University College London) for valuable discussions.
Research funded by the Defence Science and Technology Laboratory (Dstl) which is an executive ageney 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.
10

---

References
[1] R. Agrawal. Sample mean based index policies by ollog n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27:1054 1078, 1995.
[2] Arya and Yang. Randomized allocation with nonparametric estimation for contextual multi-armed bandits with delayed rewards. Statistics & Probability Letters, 2020.
[3] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-255 226,,55,2222 2002.
[4] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32:48-77, 2002.
[5] W. Chu, L. Li, L. Reyzin, and R. E. Schapire. Contextual bandits with linear payoff functions. In International Conference Artificial Intelligence and Statistics, 2011.
[6] T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Trans. Inf. Theory, 13:21-27, 1967.
[7] A. L. Delcher, A. J. Grove, S. Kasif, and J. Pearl. Logarithmic-time updates and queries in probabilistic networks. J. Artif. Intell. Res., 4:37-59, 1995.
[8] Y. Freund, R. E. Schapire, Y. Singer, and M. K. Warmuth. Using and combining predictors that specialize. In Symposium the Theory of Computing, 1997.
[9] A. Garivier and O. Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Annual Conference Computational Learning Theory, 2011.
[10] D. P. Helmbold and R. E. Schapire. Predicting nearly well as the best pruning of a decision tree. Machine Learning, 27:51-68, 1995.
[11] M. Herbster, S. Pasteris, and F. Vitale. Online sum-product computation over trees. In NIPS, 2012.
[12] M. Herbster, Pasteris, F. Vitale, and M. Pontil, gang of adversarial bandits. In Neural Information Processing Systems, 2021.
[13] M. Herbster and J. Robinson. Online prediction of switching graph labelings with cluster specialists. In Neural Information Processing Systems, 2018.
[14] M. Herbster and M. K. Warmuth. Tracking the best expert. Machine Learning, 32:151-178, 1995.
[15] M. Kakade, S. Shalev-Shwartz, and A. Tewari. Efficient bandit algorithms for online
multiclass prediction. In International Conference Machine Learning. 2008.
[16] W. M. Koolen, D. Adamskiy, and M. K. Warmuth. Putting bayes to sleep. In NIPS, 2012.
[17] R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In ACM-SIAM Symposium on Discrete Algorithms, 2004.
[18] T. L. Lai and H. F. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4-22, 1985.
[19] J. Langford and T. Zhang. The NIPS 2007, 2007.
algorithm for contextual multi- aamted bandits, In
[20] Lattimore and C. Szepesvári. Bandit algorithms. 2020.
[21] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandi approach to personalized news article recommendation. The Web Conference, 2010.
[22] K. Matsuzaki and A. Morihata. Balanced ternary-tree representation of binary trees and balancing algorithms. In Mathematical Engineering Technical Reports, 2008.

---

[23] J. Pearl. Reverend bayes on inference engines: A distributed hierarchical approach. Probabilistic and Causal Inference. 1982.
[24] V. Perchet and Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 2013.
[25] W. Qian and Y. Yang. Kernel estimation and model combination in bandit problem with covariates. J. Mach. Learn. Res., 17:149:1-149:37, 2016.
[26] H. W. Reeve, J. C. Mellor, and G. Brown. The k-nearest neighbour ueb algorithm for multi-armest bandits with covariates. Algorithmic Learning Theory, 2018.
[27] Rigollet and A. J. Zeevi. Nonparametric bandits with covariates. Annual Conference Computational Learning Theory, 2010.
[28] H. E. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527-535, 1952.
[29] Y. Seldin, P. Auer, F. Laviolette, J. Shawe-Taylor and R. Ortner. Pac-bayesian analysis of contextual bandits. In NIPS, 2011.
[30] A. Slivkins. Contextual bandits with similarity information. Journal of Machine Learning Research, 2014.
[31] C.-C. Wang, S. R. Kulkarni, and H. V. Poor. Arbitrary side observations in bandit problems. Adv. Appl. Math., 34:903-936 2005.
12

---

A Introduction to the Appendix
We now turn the full description and analysis of our algorithm CBNN. In Appendix we describe our novel algorithmic framework CANPROP. In Appendix C we describe contractions and bayesian networks on them, showing how CANPROP can be implemented with them. Finally, Appendix D we describe TSTs and how they are used to perform our required operations efficiently. In Appendix we prove, in order, all of the theorems stated in this paper.
Recall that we created a sequence of distinct nodes (3x, E (T]) and defined, for all / E [TT) (1), the node nxx4) Tn(())- Let X' (3x 1 [T]]. Given some X [K], we defined the y-regret and the complexity of as:
R(y)= Σ l,
P(y) := :
Iu(x) # v(((2))]
EE[2]
[E[T]
ZEA
respectively.
B Cancellation Propagation
B.1
The General CANPROP Algorithm
We now introduce a general algorithmic framework CANPROP for handling contextual bandit problems with per-trial time logarithmic in K. Without loss of generality assume that K is an integer power of two. Let be a full, balanced binary tree whose leaves are the set actions [K]. Let B' == B {r(B)}. CANPROP takes parameter R4 called the learning rate. On each trial t CANPROP maintains a function:
Wy B' 2 - [0, 1).
The function wy is free to be defined how one likes, as long as it satisfies the constraint that for all internal vertices B have:
Σ (w1(4()) + wi (i()))), = =1 SE2*
We now describe how CANPROP acts trial t. For all B' we define:
(e(v)= = Σ I E S]w((v,S)
SE2*
and for all Bt define:
(<(<(v)) me T<(c()))== = 0. ((())))) + (D()))
(c(D(v) T((p()) = 0.(4(v)) + (o()))
As we shall see CANPROP needs only compute these values for (In(K)) vertices v. CANPROP samples root-to-leaf path {urj l E [log(K)] U (0)) as follows. 0r,0 is defined equal to rB).. For all [log(K) K) 1] U {0}, once Vt,y has been sampled we sample 12,(++) from the probability distribution defined by: P(e,01)) = oj = [N(v) = (.)]T((() Vo wue B
noting that 01,0+1) is child of Vt.j- We define:
P. = (ve, i [log( K)] U (0))-
CANPROP then selects:
ae == Ut (og(()
and then receives the loss l The function wa is then updated to w as follows. Firstly we define,
W1+1(v,S) (v V),,S) (u' e B (T0') & P.) x xx
We then define:
nle,r
(er,log(()) = exp
[I Te Te(
13

---

Once we have defined t't,y for some E [log( []) we then define:
Vr.0-1) = (1 -
Be(v) = [V E P.lvv + 1 Pt]
Ve E (a(m,6-))))0000000)))
Vr.(i-1)
We++ (v, 5) (I E S]3((v) + [ & ( S) A(u, S) E ( ( x 2*
The regret bound of CANPROP is given by the following theorem.
Theorem B.1. Suppose we have function y X [K]. For all v E B define:
2),,e = {- X' y(z) E 4(0}}.
Then the expected y-regret of CANPROP is bounded by:
KTT
E[R(y)] -
Σ
(Q),.0) * In] Q(y, e))).
2
7
VE
B.2 Our Parameter Tuning
We now describe and analyse the initial weighting wi and the learning rate that we will use. Define
X' X' {x1}. For all (x, E 2 define:
oez I|
S] In(x) s]].
For all (v, E B 2 we define:
= (1-o(x, (1-1)
wi (),
II
xEX"
Given our parameter we choose our learning rate as:
(n(K) IT)
7: :V
KT
Given this initial weighting and learning rate, Theorem B. implies the following regret bound.
Theorem B.2. Given w, and n are defined as above, then for any y X - [K] the expected y-regret of CANPROP is bounded by:
E[R(v)] E O (((+ H(1) ((++ Vn(K) (n(()lnn(T))))
C Implementation with Contractions
C.1 A Sequence of Binary Trees
For any trial we have natural tree-structure on the set {xr | E [1] formed by making n((ze) ) the parent of Fy for all L' E [1]. However, in order to utilise the methodology of [22) we need to work
with binary trees. Hence, we now inductively define a sequence of binary trees (Z, |t E [T] {1}) where the vertices of Z, are subset of those of Z,+1. We also define function 7 Zr + X. This
function y has the property that for any t [I'] and for any distinct leaves u, E 2 we have that (u) # 7u'', and that:
fı(1") u" E 21, (xv It's [t]}
We define 2g to contain three vertices (r(22), <(r(22)), (r((2))) where:
((r(22) (4((((())
> 22
Now consider trial / E (7). We have that ž is constructed from Z, via the following algorithm GROW
1. Let u be the unique leaf in Z in which 7(u) = r2(241) and let n" = =u)).
14

---

2. Create two new vertices u' and u".
3. Set 7(u') + n(x++1) and 7(u") + 2++1-
4. If и = <((") then set <((") t u'. Else set ((")) t u'.
5. Set <((') + u" and D(u') f u.
We also define a function d 2q - N NUNUNN {0} as follows. Define d' (2(1) == 0 and for all t E [T] {1) inductively define d' (xxz d' (n(z:)) - Finally define d(u) d' ("(()) for all u Zr. Since for E [T] we have that the vertices Z, are a subset of those of Zr we have that d also defines function over 2, for all / [T].
For all E [T] we define de to the unique leaf of 2, for which ((4)) Zt.
C.2 Contractions
Our efficient implementation of CANPROP will have data-structure every vertex E B'. However, to achieve polylogarithmic time per trial we can only update a polylogarithmic number of these data-structures per trial. This necessitates the use of contractions of our trees {2 [T] (1)) which are defined as follows. A contraction full binary tree Q is another full binary tree J which satisfies the following:
The vertices of J are a subset of those of Q.
r(J)= = r()).
Given an internal vertex It have 47(u) E Ue(so(u)) and (u) Uo(Po(u)).
Any leaf of I is leaf of Q.
Note that any contraction of 2, is also contraction of 2 and hence, by induction, contraction of 3 for all l' 2 Given a trial and a contraction I of 2,-1 we now define the operation INSERT,([) which acts on I by the following algorithm:
Let à be the unique vertex J {r(TT) such that u, is in the maximal subtree of 2, with á and (ū) leaves.
2. Let u² : 22, (wI; ú)
3. Add the vertices u" and un the tree J.
4. Let u' (ū)
5. If û (1') then set 4z("²) u². Else set set ( u².
6. If â 22 (4z, (u")) then 4z("") á and p &- ue. Else set oet")" â and
45 (u") - ut.
Later in this paper we will show how this operation can done in polylogarithmic time. Note that after the operation we have that J is contraction of 2, and has been added to it's leaves. From now on when we use the term contraction we mean any contraction of Zr-
C.3 Contraction-Bate Bayesian Networks
Here shall define bayesian network over any contraction J and show how it can be utilised to compute certain quantities required by CANPROP. First define the quantity do := 0 and for all j E NU (0) inductively define:
0J+1 = (1 (1- Φ5 + ( (1-b))
The algorithm must compute these quantities for all j E [T]. However, for all E [T] we have that di doesn't 't have to be computed until trial i computing these quantities is constant time per trial. Given a contraction J, a vertex u E J r(T) and indices i, E (0, 1) define:
Ti. (J, u) [i * ( + e'l (1 ((d())
15

---

which defines the transition matrix from (,((2) to u in bayesian network over J. We shall now show how belief propagation over such bayesian networks can be used to compute the quantities we need in CANPROP. Suppose we have contraction I and function À J + R This function À induces function X' X -> 1 defined as follows. Given x E X, if there exists a leaf a E T with
((u) = x then X ((x) A(u). Otherwise (ar 1. For all S E 2 define:
i (J, (J = II X((r)
II
(c.
(1 (x) (1- )1-7))
xE8
ZEX"
For the CANPROP algorithm will need to compute
(i) E (
SE2
for some leaf i I and some function À T R+. We shall now show how compute this quantity via belief propagation on the bayesian network. particular, we shall construct quantity A(J, A, u) equal to the quantity in Equation (3). To this, first define the function A I + R so that for all u E J we have X (u) X(u) and for all It we have X (u) For all vertices E J and all indices i E {0, }) define:
Rx X, u) = 0] + (u))
For all J define:
:-
1S( = -
and then define:
A(J,A, = E II
(, u.).
(EF(J.a) wE](r(()
The equality of this quantity and that given in Equation
3 is given by the following theorem.
Theorem C.I. Given a contraction J, function x I - R and some leaf â E T we have:
A(J, A, i)
Σ ((() E @S SE2*
Note that Á(J, A, û) is of the exact form be solved via belief propagation over J. However, belief propagation is too slow (taking O([J)) time) we will remedy this later.
C.4 Cancelation Propagation with Contractions
We now describe how to implement CANPROP with contractions. For each v E B' we maintain
contraction A(v) and function X, : A(r))* - R4. We initialise with A(v) identical to Zg and (u) 1 for both leaves u Zz. Via induction over t will have that at the start of each trial we have, for all sets S E xx that:
w)(u,S) = =(A()) Av. S)/4.
(4)
On trial do follows. First update - Z, using the algorithm GROW, We will perform the necessary modifications to our contractions as we sample the path P.. In particular, we first set 01,0 = r(B) and then for each E [log(Kt K) - 1] J {0} in turn do as follows. For each w E (((w).)), (w(s)} run (A(v)) and set (we) <- 1. Since (m()) = Equation (4) still have:
holds and hence, by Theorem C.I
0,(v) = ((A(e), u:)
After (v) has been computed for both v (<(vv.s), (v..)))
now sample Urj+1.
Once we have selected the action a, we then update the functions (Ap (g(v) E P.) by setting Xo (u,) + (r(v) for all B' with (a(e) P,. It is clear now that Equation (4) holds inductively.
16

---

C,5 Notational Relationship to the Main Body
We now point out how the notation in this section relates to that of the main body. particular, we have, for all E B", all E A(v) and all i, E {0, 1), that:
(,(A()), u) R,(A()), Au, u)- A(A(v), () = A(A(v), Ar,
We note that the function Xo does not explicity appear in our pseudocode since it can be inferred from Ka (A)))..).
D Utilising Ternary Search Trees
There are now only things left to do in order to achieve polylogarithmic time per trial make an efficient online implementation of the INSERT,(-) operation and an efficient online algorithm to perform belief propagation over our contractions. In order do this we will utilise the methodology of [22] which we now describe. However, we do not give the full details of the rebalancing technique and refer the reader to [2 for these details (noting that [2 uses different notation).
D.1 Ternary Search Trees
In this section we will consider a full binary tree J. A (full) ternary free 'D is a rooted tree in which each internal vertex s DDT has three children denoted by <(s), v(s), D(s) and called the left, centre, and right children respectively. We now define what it means for a ternary tree ' to be a ternary search tree (TST) of J. Firstly, the vertex set of D partitioned into two sets D and D Every vertex s E D is associated with a vertex pls) E J and every E D is also associated with a vertex (s(s) E 4 (f(s))² The root r(D) is contained in D and ((r(D) == r(T). Each internal vertex s E Dt is associated with a vertex E(s) E J. If 8 E Do then E(s) E (m(s))) and if s E D then
{(s) lies on the path (in J] from uus) 1(x (s)). For all E DP have:
(s) E D ((V(s)) = uus) and μ (V)) = E(s).
<(s) satisfies:
If E Do then <(s) E D and p(<(s)) <({(s)).
If E D and (s(s) E ((p(((s)) then <(s) E Do and p(<(s)) = <((()))
- Else <(s) E D .(((()) = <(E(s) and μl (<(s)) = (s)).
(s))
satisfies:
If E 'D' then (s) D and ((((s)) D({(s)).
If E D and (s) E ((4({(s)) then (ss) E Do and p(>(s)) = (E(s))
Else (s) D (s)(s)) = (E(s)) and pl(>(s) = ps)).
Finally, for each leaf E DD we have:
If 8 D then u(s) a leaf of J.
If D then there exists u E Jt such that uus) = y²(s) = u.
Intuitively, each vertex & E D is associated with a subtree (s) of J. If E D' then (s) K(s(s) and if E D* then I (s) is the subtree of all descendants of pus) which are not proper descendants of (s). For every E D such that [ss) contains only single vertex, we have that is leaf of D. Otherwise
an internal vertex of D and its children are follows. We say that I is split the vertex {(s) E fs)t,. If E DD we require that {(s) is on the path in J from p(s) to μ (s). The action of splitting (s) at E(s) partitions (s) into the subtrees {(((s)) I (v(s)) and J (p((s) defined as follows:
-(((s)) = (()((s))))((()))
. (((ss) (o((())))
17

---

F(v(s) ((s) \ (F((()) U (s(s))).
Utilising the methodology of [22] we will maintain TSTs of Z, (at each trial t) and the trees in {A(c) v E J'), each with height (In()), Note that these trees are dynamic, in that vertices are inserted into them over time. (22 shows how, after such an insertion, the corresponding TST can be rebalanced, in time (In(T), so that its height is still in (In(T)). This rebalancing is performed via a sequence of (In(T) tree rotations, which generalise the concept of tree rotations in binary search trees.
D.2 Searching
In this section we show how we can use our TSTs to implement the operation INSERT,(J) on any trial l and contraction J of Zz-1. To do this we need to perform the following two search operations:
1. Find the unique vertex E J (r(J) such that ut is in the maximal subtree of 2, with and 1, (ū) as leaves.
2. Find un == 1zz, (u,, a).
To perform these tasks in polylogarithmic time we will utilise TSTs & and D of 2, and J respectively, Both the searching tasks utilise function u: 2
4. } defined, for all u, u' Z, as follows. If u' E 22 (<(u)) or u' E 22, (D(u)) then v(u, w') = or v(u, w/) = respectively. Otherwise u(u,u')=
Otherwise let 8 and u'. Let s ;= (" 3¹) and let á and s' be the children of s* which are ancestors of s and 5' respectively. I o vs*)) then
This can be computed as follows. If u u' then v(u, ut)
s' be the unique leaves of & such that u(3) = u and u(3")
have <(s") or 3' = D(s)) respectively. If = V(**) and E(s*) + then we perform the following process. Start with equal to 8. At any point in the process we do as follows. If E then the process terminates with v(u, u') =
p(u, = A. If E(*")
) u then we have v(u, u') = or u(, - if ((),u")=*
or v(u, u') = if (()) E g or (s)) E E respectively. If E E and u + E(s) then we reset as equal to the child of s which an ancestor of é and continue the process.
If E E and u E(s) then the process terminates with v(u, u')
The vertex û can be found as follows. We construct a root-to-leaf path in D such that, given a vertex in the path, the next vertex in the path is <(s), ((s) or v(s) if (E(()), u1) is equal 4, or respectively. Given that s' is the leaf of DD that is in this path we have û = (ss)).
The vertex u" can then be found follows. We construct root-to-leaf path in & such that, given vertex s in the path, the next vertex in the path is found as follows. If v({(s), u.) = v(E(s), a) then given v()(s), Ue) is equal to Otherwise, the next vertex is 7 (s). Given that is the leaf of that is in this path we have u = p(s)).
the next vertex is equal to <( D(s) 7(s) respectively.
The fact that these algorithms find the correct vertices is given in the following theorem:
Theorem D.I. The above algorithms are correct.
D.3 Belief Propagation
Here we utilise the methodology of (7] in order to efficiently compute the function À that appears
in the CANPROP implementation. i.e. given contraction J. function À :: J - R.4 and some leaf à E J* we need to compute Á(J, X, i). For brevity let us define, for all i, i' e {0, 1}. and all
vertices u E I (r(T)), the quantities: ( = (T,
:
Re(u) = u))
For simplicity of presentation we will utilise tree J' which is defined as identical to I except with a single vertex added as the parent of r(J). For all i, E {0, 1} we define Rx(r(3") := and (r(J)) = [i = i']. For all u E J will define t(u) == fz (u)
We will utilise a TST of J by maintaining potentials on the vertices of defined as follows. First, as in Section D.1 for any vertex s E D we define the subtree J(s) of J to be equal to 4 (u(s)) E DD and equal to the subtree in I of all descendants of (u(s) which are not proper descendants of (s(s) if E D= For all & E De and i E 1) we define:
vs(s):=
[S(t((())) II (w) Je(0.1)ooluttuunn)
Σ
(x)
18

---

and for all s E D and i E {0, 1) we define:
(g =
Σ
[f(((((s))) - =IIf((((s)) = II (4)))))
mEf(s)
We have the following recurrence relations for these potentials. Suppose we have an internal vertex E Dt and i, {0, 13. If E D we have:
(.(s)=
E (EE(0,1)
If, instead, E D then, by letting 8' == ((s), 8" == (()) if d() E D and = otherwise, we have:
= D()), 8" == (())
(s) =
Σ
2i (z(s))
#'E(0.1)
If, on a trial I, we perform the operation INSERT, (J) or change the value of X(u,) these recurrence relations can be used (in conjunction with the tree rotations) update the potentials in logarithmic time.
Now that we have defined our potentials we will show how to use them to compute Á(J, A, û) in logarithmic time. To do this we recursively define the following quantities for i E 10. Let (r()))) = 1. Given internal vertex Do we define:
wi(V(s)) = (1)) ; wV(((s)) = (.(c(s))W
wx(<(()) = (+((())
Σ #E(0,1)
wy (s) ; wi(D(s)) = vi()(+))
Σ wy wy (+)2g;(((s))
#E(0.1)
Given an internal vertex & E D define == 4(8), s" = (s)) if a(s) E D and = o(s).
s" = <(s) otherwise. Then:
w:(V(s)) = wi(s) wf(v(s)) = vi(s") Σ Dur((')w((()
vE(0.1)
wi(s')== = Σ (s)
wi(ss) = (s)
('(0,1
wi(s") = Σ
wp (1) (V (s.)))
(,,1((0.1)
For s E D (s) is not required and hence is arbitrary. We inductively compute the values (wi(s), (s(ss) i 1), for all in the path from r(D) the unique leaf á E D in which m($) û. We then have Á(J, a) wi (8).
Since this is known methodology we do not include a proof in this paper and direct the reader to 77.
E
Proofs
E.1 Theorem
3.
This theorem is proved in appendices B Doo and the theorems therein.
E.2 Theorem 3.6
For all C define (xx) : (xx X').
Choose a S C in which for all E [2'] there exists x E S with A(x, xx) fxx//3, For all trials let S, be the set of all contexts E S in which there exists s E [t] with (x, < /3)/33c
Now consider trial t [T] \ {1) in which ((x.) # ((Zn()) and choose S with A ( 21) < /xc/3c.
19

---

Assume, for contradiction, that x E St-1. Then there exists E [t 1] with ((x,r,) < /2) so that by the triangle inequality we have:
(zr, x.) & (x, (ax æx) (x))
which implies that A (o()) ) (x) /3 By the triangle inequality then have that:
(xx, (n(t)) E A (1 F (1)) 2 x,) 27 (x)) /3)2/33 ((x)
Since (xx, 24) < (x) we have ((z) = ((x4) and hence that y(z) # (()n())) But this contradicts
fact that A (x, (z))
We have hence shown that & St Since St we then have that |& | Since [&1] 2 this implies that:
+ (3y) =1+
Σ
(7(x)) + ((x(())] = Sr S |S
1E(TM)
required.
E.3
Theorem 3.9
Let e be such that:
[ lim 8-2 5
lim / 5-+0 SZEM(G.n.220)) (xx) S 20(0,11)
JEEM(U..2..)) S 20)
(5)
Since only interested in the behaviour as q assume, without loss of generality, that vd/q e/3. Choose À > and X' 0 sufficiently small for this proof to work. For all g let H(x)) be the of points x' E [0, 1] such that is the nearest neighbour (or one of them if the nearest neighbour is unique) of æ' in Gg. Let be the set of all E 94 for which there exists x', x, H(x) n E(),e) with ÿ(x') & û(x"). Note that for all x' E L we have H(x') M(D. H4, 2c, vd/g) so:
9 Vd JEE.
12 Σ
9
q Vd
g Vd (
Vd.
x'eC NEH((*)
By considering the limit this inequality as + co, and noting that d being treated as a constant, we then have, by Equation (). that:
[C] E (((())))00))
(6)
Now define:
Σ
u(z)
r'EC. xEH(W()
Since H(xx) M(ū 2c, vd/g) for all x' L, we have:
vd VJ [
JeEM( m(x)
By considering the limit this inequality as - co, and noting that d being treated as a constant, we then have, by Equation ( that:
E ((((0)))/))
(7)
Let D be the set of all 0 such that there exists x' E H(x) with ((x) * 0. Now define
[0, 1jdt + [K] such that for all x E [0, 1jd we have:
If D L then (z) is the unique E [K] such that there exists x' E H(z) with u(xa) * and a = (zx). Note that if there existed more than one such a then we would have L which is a contradiction.
If x & D \ L then q' (x) g'()) where à is the nearest neighbour of z in D L
20

---

Let A be finite set of points in R such that for all r E R with (xx, 0) - there exists x' E A
with (xx, x²) X. Define:
A'
U iε([og(ad)]]
(2'0/g/0E E
Note that:
|4 E ((l(()))
(8)
now show that for all x E Id with 1/4 S (xx, 0) there exists x" E A' with:
(9) To show this choose any such and let E N such that 2 S A(x, 21/g. By the assumption on we have that i E [[og(gd)]] ]. Since A(rq2 0) < choose x' E A such that A ( x²) < X. Then we have:
(ar,"") (3x
(zz, 2'x /q) = (2g/4) < (2 - (2xz,0)
so, since 2'x'/9 E A', we have proved that Equation (9) is true.
We now S' finite set of points in Rd such that for all x E [0, 1] there exists some x' E S with A(x, x') Xe. Now define:
::=LUS U Us''+ + E
DEC
Let X' = {xz I [T}. Take any E X. We now show that there exists xf E S with A(rxx)) < 7xx J' ///c. We have three cases:
First consider the case that A(x, > e/3. Let x' be the nearest neighbour of a in [0, 1jd with j' (x) * D' (z'). Choose E such that A Axx,x)) < Xe. Since A (xx, x²) < c/3 we
must have ÿ (axt) = (x().. Let x" be the nearest neighbour of in X' with D/ (x") # (x Since ø' (x(x) = (1() we must have that f'(x") + ('(x) so that A(x,²") e/3. By the triangle inequality we then have:
c/3 A(x,x") A(x,x!) + A(x!, x²)) Xc A(x) x²) 2x) N' ,
Hence ,',,, > (1/3 - M)e so that:
X
A (x, < <e
1/3 N (1)) (1,, < 2())8822)/33
as required.
Now consider the case that & E L. In this case we trivially have the result with of == x.
Finally consider the case that x & L and A(x, x') < e/3. Let x' be the nearest neighbour in [o, 1]d with (z) # ((()). Let & and be the nearest neighbours of æ and in D \ C respectively. Note that by definition of g' we have g'(ā) ('(x and ('(')) ÿ/ (x'). By definition of 'D we must have x E DD so since x & L we have á = x. Noting that A(x', 8') < A(x', .)) must then have that A(x' (x', .') A(x', x)) which means, by the triangle inequality, that A(x, E') < 2A x'). Since x' E choose 2 E H(x) and
z' H('') such that ((2). # O. Since x, 2' E we have:
0(>) (2) (x) + =' 00())) ((=')
By the triangle inequality and above have:
A(z, z') < A(2,x) + A 8') + A ; 2A(x, + vd/q5e
(10)
so since
* 0 we must have that the straight line from 2 to z' is entirely contained
in E(4, c/2). Since ((z) + 8(2') we can then choose some zt in the line from 2 to z that is on the decision boundary of ÿ (i.e. any open set around 2t contains some ž with ((2) # ()))). Since there exists open set around 2t that is entirely contained in (v,,) e)
21

---

we must now have, by definition of L, that there exists & E L such that 2 E H((2). By the triangle inequality and Equation 10
we have:
(ar, 2) S (xx, (2,, 21) = vd/q ((z + vd/g
S 2A x') + 2vd/2
(11)
Since D we have ('(2) 0' (x)) for all H(x) and hence we must have x' & H(x)
so that A 2 vd/ (2q). By Equation (1T) this means that:
A(r, 2 (a,, 2)/6
(12)
By Equation choose z" A' such that:
A(x - 3, =") < 2 - 2, 0)
(13)
and define x 2 z". Since we have æt E S as required. Note that by equations
12 and (13 we have:
2,2") 21 2)A & 12A(z,x')
(14)
Since 2A- < 1/6 now have, from equations 12) and (4). that A(z, x1) < A (xx x') so
that j'(x) (((x). Let x" be the nearest neighbour of x² in X' with (2(x") + if (((x)).
Since ('(x) (z) we must have that j'("") & (z) so that A(xxx") 2 Axx, x'). By
the triangle inequality and Equation (14) we then have:
A(x,x') A(x,x") A(x, A(x' x²) 12A A(x x²)
12A(xx (z. x') A + 7 (x X))
Hence (xt, > (1 12X) (z, x')
so that by Equation (4p we have:
12x
A(r,x1) < 12A (x, )
(x x' < 700 1 x))3
1 12X
as required.
Let v' E [K] be such that v/2 = (xx) for all E [T]. We have shown that for all x E X there
exists of E S with A(z, xt) < 7xx, V/. //33c. By equations o and 8 we have that:
|S| E O(1 S ((((0.)) In(g)) S ()
Invoking Theorem 3.6 then gives us:
4(y') O(a(i.
so by Theorem 3.3 we have:
B[R(I')) ((p+ E 0(0'1)
VKT) 5ō
(1+ (0((14(00 2 VKT)
(15)
We also have:
R(y) - R(v)) = Σ (le.r - -(x))=
Σ (le,(2))) ((s) 1 [b(e) + ('()))
KE[2]
1ET2
KE[T]
But ((x) # g (zx) implies that H, D \ L so since I, D we must have x L which happens
with probability and hence, by Equation 7. we have:
E(R(y) R(y')l pf E O(Ta(i,))/))
(16)
Combining equations
15 and 16 gives us:
E [[(()) E ((( + a() 1)14 - VTT + Tā(ū,))/4)
Since q = [(T/) we have now shown that:
[[[(y)] E Ô ((1 a() u) + ā(), x) K k4t1)
required.
22

---

E,4
Theorem B.1
For every trial t [T] define:
A :=
Σ EIQ(..)) + 0] (n(w,(1, Q(y, 2)))
WEB
Choose some arbitrary trial /. [T]. From here until we say otherwise all probabilities and expecta- tions (i.e. whenever we use IP[:] or El-)) are implicitly conditional on the state of the algorithm the start of trial t. Note first that we have:
(1 Q u))
A A El)(y + 0] In
(17)
we(r, 2(y, v))
VEB
For all j [log(K)] {0) let Yt, be the ancestor (in B3 of ((x) at depth j. Note that for all " E X' \. (7t. E [log(K)] {0]} we have y(x;) E (()) so that 22 & 2(y, v) and hence, directly have (4, 2(y, v)) (v, Q u)). By Equation (17 and
from the CANPROP algorithm, the fact that Q v) * 0 for all ancestors v of y(vx) this implies that:
In [0141(70.5 Q3y 7(.)) We( (y, 7t,5))
A
Σ
(18)
jEllog(A))
For all [log(K)) [ define:
Arj = In [Wi+1(70.5 Q(y. (.,))
Wo(Te. 2(y, (t.))
and:
c.j = ((n(())))) Th. P.l Now choose some arbitrary j E []og((K]. If 7, E Pe then (t,j-11 11.(-1) so t(n6)) = Vr)(-11 and hence, since 2t E ()). we have Anj = (n()(())))) By definition of (e((t))) this
means that:
EiAr, Tes E Pe, 7,,-11 E Pi] = En - -(ln((i.. The E Pr, 7,0-1) E P.]
and that:
E[Ac Yho & Pc, 7t.(-1) P:] -B[InBB[l..li-l Ths & Pe, m.(j-1) E Pr]
Multiplying these two equations by P(r.jj E Pe 700111 E P.] and P(ms $ Pe n1,1-11 E P.]
respectively, and summing them together, then gives
E[ (..-11 E Pd] = PP[n, E Pe 11,011) E Pile, - E[n((V (.6-11 E Pd]
Since Pl E P 70.0-1) E P.] = T. (T(.)) we then have:
E | 1t,6-11 E Pd] me(H,))e Et(5-1)
(19)
If, on the other hand, 1).--1) $ P. then 1(7..)) $ Pr so Ao.j = 0. This means that:
EE = PP E P.IBBArs 7t,(111 E Pt]
(20)
Since the probability that 1, E P, is equal y Te (T(.)) we then have, by combining equations (19) and (20). that:
[ = 6
II
T m((w)) 41(1-1)
II Te(T))))
J'ELy
J'E--1)
By substituting into Equation (8) (after taking expectations) then have that:
E E|A, A411] = =6D + (t,lo((K)
II jE(log(K)]
ne (T(.).))
--[(n(( El === (())
II m((u)) jE(lo((K)
(21)
23

---

Note that if a, log)) then Ye. = Vi,j for all j E [log(K)]. By definition of (K)) and the fact that (K)) = y(xe), Equation (1) then gives us:
E|A, A = -[lln())))) - n)lvv()))
(22)
For all (v,a) E EBE x [K] define:
(t, = Pla, = a v E P.l
noting that this is non-zero only when E ((v). Suppose we have some E B {r(B)} and some E (()) n [K] Then, since Pla, = a v Φ Pa we have:
Pr.a (1w)) = Pla, a t(v) E Pr] = P(a.- - a E P:Jplo E Pe E P.] ==(()(aa(aa))
Since (v) = whenever a & ((v). this implies that for all (v, E B [K] we have:
(t.a(v) ni (1 a (<(1)) + (((())))raa((((()
(23)
For all [K] define:
[a = alfe,
Pla+
We now take the inductive hypothesis that for all E [log( K)) U {0} we have:
Σ aE(K]
Pi,a (11,)
and prove this via reverse induction (i.e. from j = log(K) to = 0). Note that given d' == de we have Pla, = a'] [[sE[og(K)) (V).)) and hence:
(r)) = -xp((-nlr.a)
so the inductive hypothesis holds for j = log(K), (). Now suppose that we have some j' E [log [)) and that the inductive hypothesis holds for jr. We shall now show that it holds also for j = j 10--. 1. Let of be the child of 11) that is not equal ft Note that as & 4'o') and hence exp(- exp(-nfi.a) = 1 for all 4(+') (i.e. whenever (t,) * 0) which implies:
Σ RE[R]
Pra((') exp( (xx((nnlea))-
(24)
For all E [K], Equation 23 gives us:
Pt.o (v. exp(-1) (xx..rrr-)))xppp7pppe = n ((,')))),(('))) exp(- + ne (ve. (t,,(ve..)) exp( exp(exppppaepe
Substituting Equation [4 and the inductive hypothesis into this equation (when summed over all E [K]) then gives us:
Σ Pt.a (r.a(ve,(-1)) Dna((t.y--))exppppp. exp(-n((,a) =e('') Te(Ve. Wes [
Since (1²) + Te (e())))) = we have, direct from the algorithm, that me (v0) + (e( )er. = 11))"' so the inductive hypothesis holds for j = j 1. We have hence shown that the inductive hypothesis holds for all E [ {0} and in particular for = O. Since (Vr,0))))) IP(a: a) we then have:
v1.0
Σ
Pla: a]
(25)
KE
Since exp(-z) 51 = 22/2 for all z E R4 we have, from Equation 25 that:
2/1.0 & Σ
Pla: = a] 1 [I-néra + 2
2
=1 7 Σ
Play = a alc,aat
Σ
Plat = aje2.
2
<E[K]
aE[K]
aE(K]
so since In(1 + 2) < z for all 2 E IR we have:
In(Ve.)) -1 Σ
Pla = ale,,
+ 2
Σ
Plaa = 2)
(26)
K
[E[K]
24

---

Noting that Pa/a. = =ale,a = I0 = alke,a for all E [K], we have:
E
Σ [E[A]]
pla = allea
= =Ellear
and:
aa = a L
E
Σ
Pla: = a)
E
Σ
Gr S
Pla. a)
[E[K]
[E(K]
aE(K]
Substituting these equations into Equation (26) (after taking expectations) gives us:
E[In(1),,))) S [S.B( + +/2///
which, upon substitution into Equation gives us:
E|A: A++1] 2 [B[[r,a,] - (.p((r))) (4, 1/²
(27)
Note that this equation implies that the same equation also holds when the expectation is not implicitly conditional on the state of the algorithm at the start of trial t. Hence, we now drop the assumption that the expectation is conditional on the state of the algorithm the start of trial Summing Equation (27 over all trials / E [T] and then rearranging gives us:
R[R(U)] (E[Ai) E[Ar+1))) nkT
(28)
1
Now consider trial I. For all E B let:
Vi(u)= = Σ
I S]ww++/<(v).))) (4(u).
Σ Se2*
1a STwe+1 (D(v),
SE2*
Now take any j [log(K) - lI U (0) and let u v Ur.- Note that:
Vi(v) = (((((()))((((()))) (((()))))))
so that by definition of ग. (<()) and ग. (>())) we have:
Vi(v) = (0.(4(v)) + 0g (D (<m + +
Without loss of generality assume that <(v) E P.. Then the above equation implies that:
Vi(e)= = (0.(<(v)) + 0 (b())) Te (<(((v)) + (P()))
Vt.
so by definition of tt, we have:
(i(e) = (0.(4(v)) + 0 (+()))) Σ Ina E ()))) + Σ [a E (Tlu)((()),S) Se2x
Se2*
Note that this equation trivially holds for v E Bt P. and hence holds for all v E Bt. Since for all such u and all S with xe & S we have (s = (w((((), and w++1 (>()), S) = we (a(u), S) we then have:
Σ W+tr (4)))
Σ (1()) = Σ wr(4(v),S) + Σ wx(p(v),S) SE2x
SE28
SE28
SE2x
so, by induction on we have, for all / E [T + 1], that:
Σ ((()(,)
Σ () =1
SE24
SE2*
and S 2x we have (v, E [0, 1). We have now shown that Ar+1 2 so that Equation 28 gives us:
Hence, for all E BY (BB)
r(B)
I E[R()) < E[
KTT 2
1)
which, by definition of A1, gives us the desired result.
25

---

E,5 Theorem B.2
The fact that the weighting wi valid given by the following lemma: Lemma E.1. For all u E we have:
Σ
(wi(<(v),)) w -
SE24
Proof. We will show that for all v E we have:
Σ
1 wi (v, 2
SE2*
which directly implies the result. So take some arbitrary v E 5'. Define, for E [T]. the sets:
X = (2s E [4] (m) and Fr : {0, 1)
and for all x E X2 and f E Fe define the quantity:
8(x, f) = [f * f(n(=))) + [f(x) f(m(=))(1-11T)
which is defined since n=x) E XY U {x1}. For all t [T 1] we have:
Σ II EEJ TE
B(x, f
Σ fer,
II
((x,
Σ
3(1++1,f)
(29)
((111)E(0.1)
Given any Fe have:
Σ
((Ht,5)=(1-17T))
(0.1))
and hence by Equation 29 have:
Σ
II B(x Σ II B(x,f)
JEF TEX
JEF FEX
Since X7. X' this implies, by induction, that:
Σ II flz, Σ II f(x
EI
B(x,f) 1
(30)
JEFr
JEF
JEFl
Note that we have bijection g Fr x defined by:
g(f) = (z x Vf
and that for all (f,z) Fr x X' we have:
3(x, f ol,
Hence, Equation 30 shows us that:
II II SE2x xEX
( +1
(xx (1-2)
This implies that:
Σ SE2x
(v, 1
2
which implies the result.
26

---

Now that we have shown that the weighting wi is valid we can utilise Theorem B.1 regret bound. For any set S 2 define:
to prove our
((S) = Σ
(I,
REA
Note that for all Bt and S 2 we have:
wi (1(vv))==
1 1
4
((S)
(1-7)
1
1
T- - ((S)
4 T
((S)
(1-T)
1
T
1 T
so since T1n - 1/T) E (1) we have:
- -nn(w1 (v, 8)) In(4) + (n()) - - 1/T)) e ((o(S) +
1/T)
(31)
As in the statement of Theorem B.1 define, for all v E B, the set:
Qy v) == {a e X' v(x) 4(v)3
First note that the graph (with vertex set X)) formed by linking to n(x) for every X is tree so
that (vy) 2 Hv(œ) x E X - 1. So since for all E B' we have Q(y, v) + if and only if v has
a descendent in (v) x E }} and each element of {v(x) ) a E X has log( () ancestors in B' we
have:
E v) * 0] log (g((K))((()) x X3 log(() +
(32)
"EB'
Now suppose we have some x X" If y(x) v(((x)) then for all v E B' we have x, n(x)
Q(y, v) or z, n(x)) Q(v, v) and hence air Q(v. = 0. On the other hand, if v()) & v(n(x)) then for any E B' with (I, v))
we must have that either
Q(y, v) n(x) E @(y.))
so u is an ancestor of either or n(x) and hence there can be at most 2 log( K) such v. So in any case we have:
Σ orz 2(v,))) S [v(x) + ((2(=))]2log((3 BEB
Hence we have:
Σ ((Q(,,))) = Σ Σ
oi, u),, = log ()
(33)
MEB'
xEX! BEB
Equation
31
gives us:
10(y v) + 0] In(w)(u (v. Qyy, v))) E O In(T) Σ ((((y,)) v) + 01) )
vEB'
VEB'
WEB'
Substituting in equations
32 and 33 then gives us:
IQ v) + 08 In (v. ((v,,))) ((I(()
so by Theorem B.I we have:
E[R(y)] e [KK
In(K) (nT)))()))()))
2 +
7
Since 7 P/////KKnnnn (T)) we obtain the result.
E.6 Theorem
Recall our sequence of trees (2, f E [T] \ (1)) noting that each of these trees is contraction so
that T5. (2,,)) -) is defined for all i, E (0, Let c := 1/T. Define X' X' + R__ as follows. Given x E X. there exists a leaf u E J with 7(u) = x then X(x) = X(u). Otherwise ((x) = Given
I E [T] define d 2, + R2 such that for all u E 2, we have that (x( = (((())) if u is a leaf
of 2, and de(u) = 1 otherwise. For all t E [T] and f {ze I E [t] + {0, 1] define:
N(() = (f' 10, Vuue z ff()) = f(r(w))
27

---

and:
((f)==
=
II
X(xx)
II (I(())) * (((xx)))e++ ((n(z))1(11e))
('
and:
D(f)= = E II
Tf (1)) (w) (2,
('ENI) wE2.(r(2.))
We now have the following lemma:
Lemma E.2. For all I. E (T) and f: tre I [4] + {0, 1] we have: w(f = x(f)
Proof. We prove by induction on t. Suppose the result holds for / - (for some 2 2). We now show that it holds for t = s + as well. Let f be the restriction of f onto the set {σy t' E [s]]- Let u² and v' be the unique leaves in 2 of which y(u') n((x=-1) and 7("") Ts+1. By the construction of Zo+1 these vertices are siblings. Let u" be the parent (in 2.+1) of both u² and u'. First note that:
[f(x,+)) = 0] + (f(+++1) = =
((()))1) (2 Ast1,
(34)
Since, by the construction of Zs+1, we have ((1
Z.4: (u*)) = 7(u") = n(xx+11 we also have that d(tz,, (u*)) = d(ux) - so that, since Φ1 = we have:
[f(+++1) (f(n)/(((aaaa (((((1(+1))))))) + [f(+++1)) ((n(x -6)
(Zot1,,
(35)
Equations 334 and (35) give us:
w(f) = w(f (((a(s () f( "i )s+1,
(36)
Now suppose we have some f E N(f). We have r(u") = (2u)) and hence d(tz,4s (u())
=
d(u') = d(u') since f'(') f(n(Is+1) and Φ0 =0 we have:
( (2 (w) (2st1,,, [ f(n(xx+1)) (37)
Since, by the construction of Z we have 1 tz (u") 12, (w') and (as above) we have d(u")
d(u'), we also have:
Tf(t,, (a (1n)), "
(38)
Since s'(u*) = (xx+1) and tz (u*) = n² we have:
"((t,,,,('))) (a-))) (Zo+1, = (14t)
(39)
Now let:
=
; 5' (itttt
Define:
o(f':= = II
(o)
WEZ, (E(,))
and:
d(("):= == II
TP(T2,,, (w))
Combining equations 37 338 and 39 gives us:
II
TP (wi).. (30+1, (2441, =If=("(u"") =))
(40)
[M4 w²))
For all u Zo41 \ fu", u,, uu" we have 12,4, (u) = 1z, (u) so that:
TP(t2,n)))) (w)) (2) (Z,+1, = (f, (w))
28

---

and hence, since f(n(xs+1)) = (u'),, we have:
g'(f)) 9(f")
II
T (w)), (w))))()) (2)+1
" (w
Substituting in Equation 40) gives us:
g'(f) 100=0((('((("" f(((x+))]]]
(41)
We have K (rarn(22+1 xd) w²) = 1 and for all a E 2a we have R )0t1, u) = (y(w)) Zz de, u). Substituting into Equation 41 gives
(
g((f)) II
ME2++1
[ff("')
(Zet1, 2'
""" II (2) u)
NEZ.
Summing over all f' (f)) and noting that f'(x)) = f(x++1) and that:
(r(r(2.)))) (2++1 :, (( = = R)(((())) (Z,, So, r r(2))
gives us:
{(f) = =R= (( (2 io+1, 4² 20
By the inductive hypothesis we then have:
(f) = ()) (
which, by Equation 36
is equal to (f) We have hence shown that if the inductive hypothesis holds for = s then it holds for s + also. An identical argument shows that the inductive hypothesis holds for = 2. We have hence shown that the inductive hypothesis holds for all t E [T] \ (1}. O
We now define a bijection g: {0, 11 + 2 by:
((f) = (a X f(x)= = AA (0,1)
Note that for all f: 10, and all r e X { we have:
[f(x)) & f(n(x))]l++ +f(x)) f(n(=))[(1-é
and:
II X(x) =
II
X(x1)
=E9())
so that:
w(J,A, =(ff
and hence, by Lemma
E.2 we have:
MJ,A, = =())
so that:
Σ Ix( e &T Σ If((()) 1I0(f) Se2*
(42)
SE(0,1}
Since:
UNO If If [0, f(+(a)( = 1) 1) f(() 1}
and all sets in this union disjoint, the right hand side of Equation (42 is equal to:
Σ (+) =1
II
(1)),)))))))) u) U) )2,
(43)
(r2r((((2r)
Given vertex u E Zr \ (r(Zr)) define:
H(u) = 2z, ( (t)
and for all f: H(u)) + {0, define:
{(,,))= := II
Titte (e
a' a'Ellzy (w)
29

---

Lemma E.3. Given a vertex u' E Zr (r(Zr)) and an index i E {0,1) we have:
Σ
- =]]((
refo,1)8(0)
Proof. We prove by induction on the height 2 (u'). this height equal to zero then H(u') =
{u', (2, (u')} and for all f H(u) {0,1} have:
Č(u', f) Tf(tz (w))), ())
Since:
(r, u²) + T.
(44)
we immediately have the result for the case that the height of 2z (u') zero. Now suppose that the result holds whenever the height of Uz (u') is equal to j (for some j E N). We will now show that it holds whenever the height of 2, (u/) is equal to j + which will prove that the result holds always. By the inductive hypothesis we have, for all i' {0, 1]. that:
Σ
[S(4') = ((((<()))))
and
Σ
[S()) {(((o(u'),))
(E(0.1)M0(('))
80:
Σ
Uf(t,,
= (1') = ((C(())))) =1
fE(0,1)M(w))
and hence:
Σ
If(tz, -(f(())))))))) =/t((//)>='((((("" I'Ii(u'
(ZT, u)
fE(0,138(u))
Summing over i' E (0, 1} and noting Equation then shows us the result holds for this case and hence, by induction, holds always.
Given u/, u" Zr with u" 122, (u') define H(l'', u²" be the maximal subtree of 2, which has ul and u² as leaves. Given, addition, f Hll' u²) + {0, 1) we define:
II We NEAi(u' (MM(
Tf(tz, (w)). (2)))
and:
8(u',u")= = d(u')) d(ul)
We now have the following lemma.
Lemma E.4. Given u', u" Zr with x" (1') ful) and indices i', 1" E {0, 1} have that:
Σ
If(u') = l'llf(u') = ='Tī(ul ,u".
is equal to
F + ""Jos 17' = db
Proof. We prove by induction on the distance from x' to v" in Zr. this distance one then we have w' = 1t (w") and H(u,, u²) = (u', w"] so we have:
Σ ((u
"' d" u. TV (Zr, u")
=
which immediately implies that the inductive hypothesis holds in this case. Now suppose that the inductive hypothesis holds whenever the distance from u' to u" is j. We now consider the case
30

---

that the distance from u' to u" is + 1. Let u" be the child of u' that lies in H()',u"). Without loss of generality assume that u" descendant of <(u"). Now choose any 1 E {0, 13. Given f: H((u'u") + {0, 1 let:
h(i" (ft) = i"]
and let f" and I be the restriction of f onto the sets H("", u") and ((((u))) respectively. Note that Č(tl uu, f) T(a)) (("" u", ,f, ("(((""))
By Lemma E.3 and the inductive hypothesis then have that the quantity:
Σ
1(6" ()i(u,
/E/O,1)
is equal to the quantity:
(2), u² ([ + "'Joss(a wn) + [i- = =I'[(1 @s(m",""))
Summing over i E (0. 1) gives us the result. We have hence proved the result in general.
Suppose we have some : {0, 13. Let:
=( := (f' E [0, Vu J, f(u)=
Given u E J we have that:
[f(tz(u)) + fu + [f(t>(u))
f(w] (b((t(()),)) -())
equal to ((W) (J u) and hence Lemma E.4 implies that:
Σ [f()a(4) = (w) = (w))) u.) (1)) u)
so since, by the definition of contraction, the edge sets of the subtrees in (H)t,(u), |u I (r(J)}} partition the edge set of 2T we have, by definition of Ç, that:
Σ
II
Ty (w)). (w)) (Z),
II
F'EF(N ('EFIJEEZ (EZTA(ER1)
VEI((r())
Since for all I' E FJ) and for all u E Zr \ I we have have (2T, AT, u) 1 we have now shown that the quantity:
Σ
II
Ar,,
r'f(f (EZr((r(2z))
equal the quantity:
II
(J) ST,
NE (ET)((())
Summing over all e F(J, (,, () and noting Equations and 443 gives us the result.
E.7 Theorem D.1
Lemma F.5. Given uf Z, the algorithm for computing v(u, u') is correct.
Proof. If u = ue then the proof is trivial. Otherwise we consider the following cases:
Consider first the case that & A v(*)). Without loss of generality assume 8= a(*)) Then we have u E (+<a(((s*) ))) and since 8 + a(s*) we have w' (<<(E()*)). Hence u' (()) vlu, u') required.
31

---

If u E(s") then 8 = v(*)) so either 8' = =<(s)) ) or 8' = =>(s"). In the former case we have u' E (<<((()))) = (<(()) so that v(u, u') and similarly in the later case have v(u, as required.
If = v(*)) and u + E(s*) then we invoke the process. Consider the vertex at any stage in the process. By induction we have that if 8 then u' (((((s)) This is because if E Ex then (s) is an ancestor of p (s)) This further implies that when s & á we have u' E (u (fe()))) Now suppose that 8 E Ed and without loss of generality assume s (()g()).. Then a E ((a(((te())) (s)))) and p (()))s)) E ((o(5((
that, since as required. Suppose now {(s). If <(s) E E" then we have p (s(s) ((<((s))) = (<(()) so that, by above, v' E U(<()) and hence v(u, u') = as required. Similarly, if (f) E
u' E (fe((te
we have u E (u) and hence v(u u²)
that Ex and that
then v(u, u') as required. This completes the proof.
Lemma E.6. The algorithm correctly finds u.
Proof. By induction on the depth of we have, for all vertices in the constructed path, that:
If s Do then un lies in the maximal subtree of Z, containing p(s) and having to (u(s)) as leaf.
If D then in lies in the maximal subtree of Z, with 1o (u(s)) and p'(s) as leaves.
Let s' be the unique leaf of D that is on the constructed path. If s' E D then p(s') is a leaf of J and hence also leaf of Z₁ So by above we have that u, lies in the maximal subtree of Z, with to (u(s') and jus') as leaves. If, on the other hand, E D then since s' a leaf of we have that pls') (s'')) and hence, by above, we have that u, lies in the maximal subtree of Z, with to (M(s")) and jus') as leaves. In either case we have à = p(s') as required.
Lemma E.7. The algorithum correctly finds u².
Proof. By induction on the depth of we have, for all vertices in the constructed path, that:
If s 0 then I (ue, ú) lies in 2z (u(s)).
If E then Tz, (u4, ú) lies in the maximal subtree of Z, with ju()) and p²(s) leaves.
Let s' be the unique leaf that is on the constructed path. If s' E then ju(') a leaf of Z, and hence, by above, Tz, (ue, i) pus') as required. If s E E then jus) = ye' (s) and hence, by above, I 2, (ut, ú) pls') required.
32


Reviews:
[{"review_id": "DZbazpnwoL", "reviewer": "Reviewer_j5Qr", "summary": "This paper considers non-stochastic contextual bandit problems in which the regret is defined with an arbitrary decision policy that maps contexts to arms.\nFor this problem,\na framework of algorithms based on the nearest neighbor rule is developed.\nThe paper provides generic regret bounds for this framework and show regret bounds for semi-stochastic settings in which contexts consist of $d$-dimensional vectors.", "questions": "- Are there any regret lower bounds that can be compared to the results of this paper?\n- This paper uses a general result (Theorem 3.2) to construct a bound for one specific example (Theorem 3.4). Theorem 3.2 appears to be so general that I expect to be able to derive nontrivial results for other specific examples examples as well (e.g., when the context is discrete). \nCan you think of any such examples?", "limitations": "I have no concerns about the limitations and potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A general framework applicable to a wide range of contextual bandits is proposed.\n- The proposed algorithm is superior in terms of computational efficiency due to the use of sophisticated data structures.\n- The algorithmic procedures and theoretical results are clearly explained.", "weaknesses": "- Comparisons with existing studies (both in terms of approach and results) are limited.\n- ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review - we have the following comments and responses (to the phrases in quotation marks).\n\n\"Comparisons with existing studies are limited.\"\n- As far as we are aware our work is the first to achieve any of the results given in our paper. In the case of Theorem 3.4 (and the new modification given in the general response) there are (worse or incomparable) results in the literature (see [21] and the citations therein), often limited to the fully-stochastic special case, that we can compare against and we commit to doing so. In the case of the more general theorems we know of no other non-trivial results to compare against. As far as we know this is the first time a nearest-neighbour approach has been applied to adversarial bandits and the first time a 1NN approach has been applied to any bandit problem. We commit to expanding our related work section.\n\n\"Are there any regret lower bounds that can be compared to the results of this paper?\"\n- Yes - we can show that (when the parameter $\\rho$ is tuned correctly) our bound is almost optimal. To prove this first note that the non-contextual bandit problem with $S$ trials and $K$ arms has a regret lower bound of $\\Theta(\\sqrt{KS})$. Now consider any $\\Phi$ and let $T=S\\Phi$ for some arbitrary $S\\in\\mathbb{N}$. Let our sequence of contexts $\\{x_1, x_2, … x_T\\}$ be such that $x_t$ is the nearest neighbour (seen so far) of $x_{t+1}$. Now divide the sequence into $\\Phi$ contiguous segments, all of length $S$, and in any particular segment let each context in that segment have the same associated action. With this knowledge we now have $\\Phi$ independent problems each with $S$ trials. Each problem has a regret lower bound of order $\\sqrt{KS}=\\sqrt{KT/\\Phi}$. The total regret must hence be lower bounded by $\\Theta(\\sqrt{KT\\Phi})$ which is a logarithmic factor different from our upper bound.\n\n\"This paper uses a general result (Theorem 3.2) to construct a bound for one specific example\"\n- Theorem 3.4 is just an example. Our main results are theorems 3.2 and 3.3. These bounds can be applied to any metric space (Theorem 3.3) or anything (Theorem 3.2). Note also that with Theorem 3.3 we don’t need to know the metric space itself - we need only be able to compute the distance between any pair of contexts. This allows our results to be applied to many more applications than Theorem 3.4 allows. For example, the contexts could be machines connected to the internet and the distance could be how many links between two machines - or the contexts could be complex user profiles and the distance given by some algorithm which computes how similar two user profiles are. Also, our main results allow for any sequence of contexts whilst in Theorem 3.4 they must be drawn i.i.d. at random (which is unrealistic in many applications)."}, {"review_id": "aaSD7zMYox", "reviewer": "Reviewer_PH3Q", "summary": "This work studies adversarial contextual bandits. The approach to solving this problem considered in this work is to use the nearest neighbor (NN)search sub-routine algorithm, and the regret bound depends on a term that characterizes the efficiency of the NN oracle. The main advantage of using an NN-based algorithm is that the per-trial computation time can be improved exponentially, compared with previous EXP-4 based algorithms. ", "questions": "Is it possible to provide some hardness results to show that the per-trial computational time (polylog) is actually optimal?", "limitations": "This work is a theoretical work. It does need to address the societal impact issue. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proof is technically sound as far as I know. \n\nThe improvement of the algorithm running time is significant, if the exponential improvement is provided firstly by this work. \n\nThe presentation is clear. ", "weaknesses": "Some typos. For example: \n- line 212, $a_t$ equal to $z_{t, \\log K}$-> $v_{t, \\log K}$\n\nNo experiments. The authors could provide some simulation results to suggest their CBNN approach indeed works in practice. I am particularly interested in the comparison between CBNN and EXP-4, from both the computation time comparison and regret comparison. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review - we have the following comments and responses (to the phrases in quotation marks).\n\n\"the per-trial computation time can be improved exponentially, compared with previous EXP-4 based algorithms.\"\n- By Exp4 do you mean our “initial idea” of combining Exp4 and Belief propagation on a dynamic tree (mentioned in Line 197)? We would like to stress that this algorithm is (as far as we are aware) novel so can be viewed as part of our contribution. \n\n\"if the exponential improvement is provided firstly by this work.\"\n- The slower algorithm is also our invention so the exponential improvement is also novel.\n\n\"No experiments.\"\n- The running time of our Exp4 based algorithm is (in the worst case) strictly $\\Theta(TK)$ per trial so CBNN is certainly an exponential improvement (we note that the Exp4 based algorithm is in itself part of our contribution). You are right, however, that the two algorithms are not exactly equivalent so there will, empirically, be a slight difference in the regret. If time allows we will endeavour to do some experiments.\n\n\"Is it possible to provide some hardness results…\"\n- We will think about this question\n\n\"It does need to address the societal impact issue.\"\n- We will address this, but don't foresee any negative societal impact."}, {"review_id": "eOtwxOudW5", "reviewer": "Reviewer_UgjS", "summary": "This paper studies the contextual multi-armed bandit problem in the adversarial setting. The authors propose an algorithm, CanProp, which utilizes an adaptive approximate nearest neighbor data structure to select the arm to pull for a given context.", "questions": "How central is computational efficiency to the novelty claims of this work? If exact nearest neighbors are trivially computed at each time step (resulting in $O(t)$ complexity in round $t$) is the regret guarantee trivial? That is to say, is the result in Appendix B already known and the benefit of this paper is in a computational speed up, or was the regret guarantee itself not previously known?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors provide a novel algorithm for the contextual multi-armed bandit problem in the adversarial setting. The algorithm appears to be theoretically sound, and the authors provide regret guarantees, which they specialize to the stochastic case.", "weaknesses": "1. Practicality and implementability: The algorithm relies heavily on data structures which do not seem practically feasible. The authors do not provide any empirical results to support their claims that this can be faster than existing methods\n\n2. Notation: the authors use significant notation, some of which may be required, but some of which is unnecessarily difficult to follow. For example, line 75, using $x$ to indicate a random element instead of $X$. This is confusing, as in the condition stated in line 128, the requirement is that the function of $x$, $P[y(X)=a|X=x]$, is Lipschitz in $x$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review - we have the following comments and responses (to the phrases in quotation marks).\n\n\" The algorithm relies heavily on data-structures that do not seem practically feasible\"\n- Could you please elaborate on the phrase \"do not appear to be practically feasible\"? While these algorithms are complex, they are indeed implementable and exhibit remarkable speed. It's worth mentioning that we have detailed a slower but novel algorithm in Appendix B (referenced in Line 197) that achieves essentially the same level of regret and is straightforward to implement.\n\n\"The authors do not provide any empirical results to support their claims that this can be faster than existing methods\"\n- The alternative algorithm we present in Appendix B operates with a running time of $\\Theta(NK)$ in worst-case scenarios, highlighting the exponential speedup of our main algorithm. Given the mathematical underpinning of this fact, we believe that there exists no imperative necessity to provide empirical validation for this assertion.\n\n\"Notation: the authors use significant notation...\"\n- We are sorry if the notation is difficult to follow and will attempt to make things clearer. $P[y(x)=a|x]$ is meant to be read as “the probability that $y(x)$ is equal to $a$, given $x$”.\n\n\"How central is the computational efficiency to the novelty claims of this work?\"\n- As far as we are aware our regret bound itself is completely novel, irrespective of the computational efficiency. Our “initial idea” in Appendix B is indeed novel. We commit to clarifying this. The regret guarantee for exact nearest neighbour is not at all trivial."}, {"review_id": "Kg4tnAPaPG", "reviewer": "Reviewer_nfmq", "summary": "The paper under review investigates the novel application of nearest neighbor search in the context of contextual bandit problems, which I find both new and intriguing. The main contribution lies in the derived result that bounds the regret using \\Phi(y), a metric that quantifies the likelihood of disparate optimal choices among closely related contexts. I appreciate the generality and applicability of this metric, as it encapsulates contextual dependencies and has the potential for broad practical use. I am not familiar with the techniques used in the analysis part, but they look good to me.", "questions": "Just to make sure that there is no hidden assumption on the relationship between context and loss vector? (compared with linear bandits)\nIs it the case that if each context has completely different loss vectors, then \\phi(y) will be very large and the bound becomes vacuous?", "limitations": "n/a", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies the application of nearest neighbor search in contextual bandits, which is new and practical. And it gets some interesting theoretical results.\nThe paper is written very clearly and has a good structure.", "weaknesses": "Some notations in the second part of section 2 (those related to trees) are not very intuitive and hard to interpret, but perhaps it is not easy to design symbols for them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review - we have the following comments and responses (to the phrases in quotation marks).\n\n\"a metric that quantifies the likelihood of disparate optimal choices among closely related contexts.\"\n- $y$ can be anything. i.e. $y(x)$ needs not be the optimal choice for $x$ (see below). Typically though we are only interested in policies $y$ where $y(x)$ is often a good choice for $x$.\n\n\"Some notations in the second part of section 2 (those related to trees) are not very intuitive and hard to interpret…\"\n- we are sorry for the confusing symbols - we have tried to make them fit the definition where possible.\n\n\"Just to make sure that there is no hidden assumption on the relationship between context and loss vector?\"\n- There is no assumption whatsoever on the relationship between context and loss vector. There is also no restriction whatsoever on our comparator policy $y$ (i.e. we can choose $y$ to be anything - $y(x)$ does not need to be the best action for $x$). Choosing a smoother comparator policy (lower $\\Phi(y)$) gives a lower regret but choosing a more complex comparator policy (high $\\Phi(y)$) may fit the data better (and so have a lower inherent loss). If the contexts all have completely different loss vectors then yes - the bound will be vacuous (but no algorithm can achieve a non-vacuous bound in this case)."}, {"review_id": "y9jFjzbPH0", "reviewer": "Reviewer_WneD", "summary": "This paper considers contextual bandits in a nearest-neighbor paradigm. In this paradigm, the contexts exist in a metric space, such that contexts that are close in the metric space are also likely to admit the same \"correct\" action. \nIn other words, the decision boundary of the optimal mapping from context to action is assumed to be small. \nIntuitively, in such a setting, a nearest-neighbor type strategy is reasonable, in which one decides on an action for the current context based on past history on nearby contexts. \n\nFirst, the paper considers contextual bandits in the adversarial setting, with the added property that at any time step t, one of the contexts for a previous time step is \"flagged\". Intuitively, this flag corresponds to it being similar to the current context, providing some advice to the algorithm. The paper presents an algorithm for this model, and analyzes its regret in terms of the similarity between the current context and the flagged past context (as measured in terms of the optimal policy's assignment for these contexts). Next, the paper hones in on the case in which the flagged context is a (c-approximate) nearest neighbor of the current context, and simplifies the regret bound to be a function of the parameter c as well as the distance of the input from the decision boundary of the optimal policy. \n\n\nThe algorithm presented in the paper seems to be a very intricate construction of search trees over the given action space, to support the given regret bounds as well as efficient calculation. \n\n\nComments:\n\nSection 4.2: I found the definition of the ternary tree to be technical and hard to understand. Perhaps give an intuitive explanation of the construction before delving into notation and formal definitions. \n", "questions": "none", "limitations": "yes", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The assumption that contexts exhibit closeness-based similarity is natural, and allows for meaningful bounds even when the space of possible contexts is infinite. \nThe algorithm itself is interesting and very nontrivial.\nThe paper is generally well-written.", "weaknesses": "The paper is somewhat pseudocode and notation heavy. I would personally rather have more intuition about the various components and their role in the algorithm, even at the cost of not having a full description of every procedure in the main body of the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review - we have the following comments and responses (to the phrases in quotation marks).\n\n\"In other words, the decision boundary of the optimal mapping from context to action is assumed to be small\"\n- We note that our comparator policy $y$ can be anything - it does not need to be the exact optimal mapping (which could have a large decision boundary). Choosing a smoother comparator policy (lower $\\Phi(y)$) gives a lower regret but choosing a more complex comparator policy (high $\\Phi(y)$) may fit the data better (and so have a lower inherent loss). \n\n\"Section 4.2: I found the definition of the ternary tree to be technical and hard to understand.\"\n- We understand it is very complex and we commit to writing an intuitive explanation.\n\n\"The paper is somewhat pseudocode and notation heavy.\"\n- We wanted the main body to be complete in that all novel pseudocode is given. We do have an extra page if accepted so we can provide an “overview” subsection at the beginning of Section 4 where we can describe how the different components will fit together."}]

Author rebuttal:
We thank the reviewers for their time spent in reviewing our paper.

We would like to note that for our example problem (that of Theorem 3.4) we can reduce the asymptotic dependance on $T$ and $K$ to $\tilde{O}(T^{d/(d+1)}K^{1/(d+1)})$ by first quantising the contexts (a.k.a. binning) as a pre-processing step. Although it reduces the asymptotic dependence on $T$ and $K$, utilising this pre-processing step can lead to a regret much worse than without using it (due to the other terms in the regret) - hence, we would like to keep Theorem 3.4 whist adding this new result (if we have the reviewers' permission). We will now sketch the proof:

Choose some even natural number $q$ which will be tuned later. Let $D$ be the set of all vectors in $[0,1]^d$ such that each component is equal to $z/q$ for some natural number $z$. For each context $x_t$ first map it to the nearest point in $D$. For simplicity here we assume that the decision boundary is the set of vectors in $[0,1]^d$ in which all components except for the first are $1/2$ and the distribution $\mu$ is the uniform distribution (but this proof can be easily extended to capture any possibility). Now, given our policy y, define a new policy $y’$ on $D$ such that:
(1) if $x$ is not on the decision boundary then $y’(x)=y(x)$
(2) if $x$ is on the decision boundary then $y’(x)=1$.
Note that the expected loss of policy $y’$ is no more than that of $y$ plus $O(T/q)$. By applying Theorem 3.3 to the metric space $D$ with policy $y’$ we see that the expected regret of the algorithm w.r.t policy $y’$ is $\tilde{O}(\sqrt{q^{d-1}KT})$.
Hence, the expected regret of the algorithm w.r.t. policy $y$ is $\tilde{O}(\sqrt{q^{d-1}KT}+T/q)$. Setting $q=(T/K)^{1/(d+1)}$ gives us the result. 

Note that by treating each bin independently we would get an expected regret of $\tilde{O}(\sqrt{q^{d}KT}+T/q)$ meaning that our nearest neighbour methodology saves us a whole dimension. 

We note that, whilst utilising binning as a pre-processing step can sometimes help, it destroys our more general bounds.

Meta-review: Reviewers were unanimous in their support for this paper, and I concur.
Decision: Accept (poster)