Contextual Bandits for Unbounded Context Distributions
Authors: Puning Zhao
Rongfei Fan
Shaowei Wang
Li Shen
Qixin Zhang
ZongKe
Tianhang Zheng
Venue: ICML 2025 poster (2025)
Keywords: Contextual bandits
nonparametric statistics
Primary area: theory->online_learning_and_bandits
TL;DR: Analyze nonparametric contextual bandits

Abstract: Nonparametric contextual bandit is an important model of sequential decision making problems. Under $\alpha$-Tsybakov margin condition, existing research has established a regret bound of $\tilde{O}\left(T^{1-\frac{\alpha+1}{d+2}}\right)$ for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving contextual bandit problems with unbounded support is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. In this paper, we solve the nonparametric contextual bandit problem with unbounded contexts. We propose two nearest neighbor methods combined with UCB exploration. The first method uses a fixed $k$. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive $k$. By a proper data-driven selection of $k$, this method achieves an expected regret of $\tilde{O}\left(T^{1-\frac{(\alpha+1)\beta}{\alpha+(d+2)\beta}}+T^{1-\beta}\right)$, in which $\beta$ is a parameter describing the tail strength. This bound matches the minimax lower bound up to logarithm factors, indicating that the second method is approximately optimal.

Contextual Bandits for Unbounded Context Distributions
Puning Zhao 12 Rongfei Fan
Shaowei Wang"
Li Shen
Qixin Zhang Zong Ke Tianhang Zheng'
Abstract
and finance (Bouneffouf al., 2020), decision problems are usually modeled contextual bandits (Woodroofe, 1979), in which the reward depends on some side information, called contexts. At the 1-th iteration, the decision maker ob- serves the context X,, and then pulls an arm A, E A based on X, and the previous trajectory (X,, A.), = I...., (- Many research assume linear rewards (Abbasi- Yadkori et al., 2011; Bastani Bayati, 2020; Bastani al., 2021; Qian et al., 2023; Langford & Zhang, 2007: Dudik al., 201 I; Chu al., 2011; Li et al., 2010), which is restrictive and may not fit well into practical scenarios. Consequently, in re- cent years, nonparametrie contextual bandits have received significant attention, which does not make any parametric assumption about the reward functions (Perchet & Rigollet, 2013; Guan Jiang, 2018; Gur et al., 2022; Blanchard et al., 2023; Suk & Kpotufe, 2023; Suk, 2024; Cai al., 2024).
Nonparametric contextual bandit is an impor- tant model of sequential decision making prob- lems. Under a-Tsybakov margin condition, ex- isting research has established a regret bound of for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving con- textual bandit problems with unbounded support is to achieve both exploration-exploittiio trade- off and varianer tradcoff simultancously. In this paper, we solve the nonparametric contex- tual bandit problem with unbounded contexts. We propose two nearest neighbor methods com- bined with UCB exploration. The first method uses a fixed k. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive By a proper data-driven selection of k. this method achieves expected regret of (a-1)á δ T -+14+2)7 T -)) in which & is a pa- rameter describing the tail strength. This bound matches the minimax lower bound up to loga- rithm factors, indicating that the second method is approximately optimal.
ò (T-
Despite significant progress nonparametric contextual bandits, existing studies focus only on the case with bounded contexts, and the probability density functions (pdf) of the contexts are required to be bounded away from zero. How- ever, many practical applications often involve unbounded contexts, such as healthcare (Durand et al., 2018), dynamic pricing (Misra al., 2019) and recommender systems (Zhou et al., 2017). In particular, the contexts may follow a heavy- tailed distribution (Zangerle & Bauer, 2022), which is sig- nificantly different from bounded contexts. Therefore, to bridge the gap between theoretical studies and practical applications of contextual bandits, an in-depth theoretical study of unbounded contexts is crucially needed. Com- pared with bounded contexts, heavy-tailed context distri- bution requires the learning method be adaptive to the pdf of contexts, in order to balance the bias and variance of the estimation of reward functions. On the other hand, compared with existing works on nonparametric classifi- cation and regression with identically and independently distributed (i.i.d) data, bandit problems require us to achieve good balance between exploration and exploitation, thus the learning method needs to be adaptive to the subopti- mality gap of reward functions. Therefore, the main chal- lenge of solving nonparametric contextual bandit problems with unbounded contexts is to achieve both Mtasinariance tradeoff and exploration-exploiatiii tradeoff using single algorithm.
1. Introduction
multi-armed bandit (Robbins, 1952; Lai & Robbins, 1985)
an important sequential decision problem that has been ex- tensively studied (Agrawal, 1995; Auer al., 2002; Garivier & Cappé, 1). In many practical applications such rec- ommender systems and information retrieval in healthcare
'Shenzhen Campus of Sun Yat-sen University, Shenzhen, China "Guangming Laboratory, Shenzhen, China 'Beijing In- stitute of Technology, Beijing, China "Guangzhou University, Guangzhou, China Nanyang Technological University, Singa- pore 'National University of Singapore. Singapore 'Zhejiang University, Hangzhou, China. Correspondence to: Shen <shenlió
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this paper, we solve the nonparametric contextual ban-

---

Contextual Bandits for Unbounded Context Distributions
Bound of expected regret
Method
Bounded context
Heavy-tailed context
(Rigollet & Zeevi, 2010)
UCBogram
T min
None
(Perchet & Rigollet, 2013)
ABSE
0
T
None
(Gur et al., 2022)
SACB
0
T T
None
1+1 T
(Guan & Jiang. 2018)
KNN-UCB
T
None
(Reeve et al., 2018)
KNN-UCB
T Ö(T
Ô
dT2
None
This work
KNN-UCB
Tmax
(1 2T2 2
T min(d- +max 400
# min(d.a+1)
This work
Adaptive KNN-UCB
a1l (T' dfz
((T 1 11-min a ++(+)])
(0+1)
Minimax lower bound
Ω
T
Ω
T min
or (41
Table 1. Comparison of the 7' step expected cumulative regrets of learning algorithms for nonparametric contextual bandits with Lipschitz reward function under a- a-Tsybakov margin condition and tail parameter 3 (Assumption ((a) and (b)).
dit problem with heave-tailed contexts. To begin with, we derive a minimax lower bound that characterizes the theo- retical limits of contextual bandit learning. We then propose relatively simple method that uses fixed it combined with upper confidence bound (UCB) exploration and derive the bound of expected regret. Even for bounded contexts, our method improves over an existing nearest neighbor method (Guan & Jiang, 2018) for large margin parameter a, since our method uses an improved UCB calculation which is more adaptive the suboptimality gap of reward functions. Despite such progress, there is still some gap between the regret bound and the minimax lower bound, indicating room for further improvement. To close such gap, we further propose new adaptive nearest neighbor approach, which selects h adaptively based on the density of samples and the suboptimality gap of reward functions, Our analysis shows that the regret bound of this new method nearly matches the minimax lower bound up to logarithmic factors, indicating that this method is approximately minimax optimal.
suboptimality gap are unknown to the learner. Therefore, we design a method, such that the value of k is selected by data-driven manner, based on the density of existing samples.
1.1. Contribution
The contributions of this paper are summarized as follows.
We derive the minimax lower bound of nonparametric contextual bandits with heavy-tailed context distribu- tions.
We propose a simple KNN method with UCB explo- ration. The regret bound matches the minimax lower bound with small and large B.
We propose an adaptive kNN method, such that is selected based on previous steps. The regret bound matches the minimax lower bound under all parameter regimes.
The general guidelines of our adaptive kNN method are summarized as follows. Firstly, with higher context pdf, we use larger k, and vice versa. Secondly, given a specific context, if the value of an action is far away from optimal (i.e. large suboptimality gap), then we use smaller k, and vice versa. Such a choice of i achieves good tradeoff between estimation bias and variance. With lower pdf or larger suboptimality gap, the samples are relatively more sparse. As a result, a large bias may happen due to large KNN distances. Therefore, we use smaller k to control the bias. On the contrary, with a higher pdf or smaller suboptimality gap, the samples are dense and thus we can use larger to reduce the variance. Note that the pdf and the
Our results and the comparison with related works are sum- marized in Table 1. In general, the best of our knowledge, our work is the first attempt to handle heavy-tailed context distribution in contextual bandit problems. In particular, our new proposed adaptive kNN method achieves the minimax lower bound for the first time. The proofs of all theoretical results in the paper are shown in the supplementary material.
2. Related Work
In this section, we briefly review the related works about contextual bandits and nearest neighbor methods.
'Despite that the name KNN-UCB is the same as (Guan & Jiang, 2018) and (Reeve et al., 2018), the calculations of UCB are different between these methods. See details in the "Nearest neighbor method with fixed An section.
Nonparametric contextual bandits with bounded con- texts. (Yang & Zhu, 2002) first introduced the nonpara- metric contextual bandit problem, proposed an e-greddy ap-
2

---

Contextual Bandits for Unbounded Context Distributions
proach and proved the consistency. (Rigollet & Zeevi, 2010) derived minimax lower bound on the regret, and showed that this bound is achievable by a UCB method. (Perchet & Rigollet, 2013) proposed Adaptively Binned Successive Elimination (A (ABSE), which adapts to the unknown margin parameter. (Qian & Yang. 2016) proposed a kernel estima- tion method. (Hu et al., 2020) analyzed nonparametric ban- dit problem under general Hölder smoothness assumption. (Gur al., 2022) proposed amoothhesssAdaative Adaptive Contex- tual Bandits (SACB). which is adaptive to the smoothness parameter. (Slivkins, 2014; Suk & Kpotufe, 2023; Akhavan et al., 2024; Ghosh et al., 2024; Komiyama et al., 2024; Suk, 2024) analyzed the problem of dynamic regret. Furthermore, (Wanigasekara & Yu, 2019; Locatelli & Carpentier, 2018; 8; Krishnamurthy et al.. 2020; Zhu et al., 2022) discussed the case with continuous actions.
as the maximum expected reward of context x. For any suboptimal action a, [x)x)) (x). Correspondingly, 17" (xx no (x) is called suboptimality gap.
The performance of an algorithm is evaluated by the ex- pected regret
R E (x)) -1A
We then present the assumptions needed for the analysis. To begin with, we state some basic conditions in Assumption I. Assumption 1. There exists some constants Cao 0, L, such that
(a) (Tsybakov margin condition) For some a S d, for all a E A and u > 0, P(O < "1" (X) - Ta (a(X) (X) < u) S Cau
Nearest neighbor methods. Nearest neighbor classification has been analyzed in (Chaudhuri& & Dasgupta, 2014; Döring et al., 2018) for bounded support of features. (Gadat et al., 2016; Kpotufe, 2011; I; Cannings et al., 2020; Zhao & Lai, 2021b;a) proposed adaptive nearest neighbor methods for heavy-tailed feature distributions. (Guan & Jiang, 2018) pro- posed KNN-UCB method for contextual bandits and proved Lid
(b) We is subgaussian with parameter o², i.e. Ele S e
(c) For all a, na is Lipschitz with constant L, i.e. for any x and x', [na (x()x S L|x - x'II.
a regret bound )
Now we comment on these assumptions. (a) is the Tsybakov margin condition, which was first introduced in (Audibert & Tsybakov, 2007) for classification problems, and then used in contextual bandit problems (Perchet & Rigollet, 2013). Note that P(O < 17" (X) - (X) < t) S 1 al- ways hold, thus for any Ya- (a) holds with C. = =1 and a = O. Therefore, this assumption is nontrivial only if it holds with some a > O. Moreover, we only consider the case with a S d here. If a > d. then an arm is either always never optimal, thus it is easy to achieve loga- rithmic regret (see (Perchet & Rigollet, 2013), Proposition 3.1). An additional remark is that in (Perchet & Rigol- let, 2013; Reeve et al., 2018) the margin assumption is P(O < (X) - Th (X) < <t) S ta, in which 71 (x)) is the sec- ond largest one among (x)(xa E A]. Our assumption (a) is slightly weaker than existing ones since we only impose margin conditions the suboptimality gap 17" (x() na (x) for each separately, instead of on the minimum subopti- mality gap. In (b), following existing works (Reeve et al., 2018), we assume that the noise has light tails. (c) is a com- mon assumption for various literatures on nonparametric estimation (Mai & Johansson, 2021). is possible to extend this work to a more general Hölder smoothness assump- tion by adaptive nearest neighbor weights (Cannings et al., 2020). In this paper, we focus only on Lipschitz continuity for convenience.
Compared with existing methods on nonparametric contex- tual bandits, for unbounded contexts, the methods need to adapt to different density levels of contexts and achieve better bias and variance tradeoff in the estimation of reward functions. Moreover, existing works on nonparametric clas- sification can not be easily extended here, since the samples are no longer i.i.d and we now need to bound the regret instead of the estimation error. These factors introduce new technical difficulties in theoretical analysis. In this work, to address these challenges, we design new algorithms that are adaptive to both the pdf and the suboptimality of reward functions and provide a corresponding theoretical analysis.
3. Preliminaries
Denote X' as the space of contexts, and A as the space of actions. Throughout this paper. we discuss the case with infinite X' and finite A. At the i-th step. the context X, is random variable drawn from a distribution with probability density function (pdf) f. Then the agent takes action A E A and receive reward Y;:
(1) in which (x)) for a E A and x E X is an unknown expected reward function, and W, denotes the noise, with B[W,|X 12, Ana] = O.
Y = nA, (X.) + We,
Assumption 2 is designed for the case that the contexts have bounded support.
Throughout this paper, define
Assumption 2. f(x) 2 e corrr all x E X. in which f is the pdf of contexts.
'7* (x) = max 7a (x)
(2)
3

---

Contextual Bandits for Unbounded Context Distributions
In Assumption 2, the pdf J' is required to be bounded away from zero, which is also made in (Perchet & Rigollet, 2013; Guan & Jiang, 2018; Reeve al., 2018). Note that even for estimation with i.idd data, this assumption is common (Audibert & Tsybakov, 2007; Döring et al., 2018; Gao et al., 2018).
bandits. Throughout this section, denote : X' x X R - A as the policy, such that each action is selected according to policy л. To be more precise,
A xX, X 11 Y1:-1),
(4)
which indicates that the action A, at time t depends on the current context and the records of contexts and rewards in previous steps.
We then show some assumptions for heavy-tailed distribu- tions.
Assumption 3. (a) For any u > O, P(f(X)= u) S CBu for some constants O3 and B:
The minimax lower bound for the case with bounded support has been shown in Theorem 4.1 in (Rigollet & Zeevi, 2010). For completeness and notation consistency, we state the results below and provide simplified proof.
(b) The difference of regret function 1) among all actions are bounded, i.e, supxex (x) -mina na [x)) S M for some constant M.
Theorem 1. ((Rigollet & Zeevi, 2010), Theorem 4.1) Denote
FA the set of pairs (J, n) that satisfy Assumption I and (which means that the contexts have bounded support). Then
(a) is common tail assumption for nonparametric statis- tics, which has been made in (Gadat et al., 2016; Zhao & Lai, 2021b). 3 describes the tail strength. Smaller 3 indi- cates that the context distribution has heavy tails, and vice versa. To further illustrate this assumption, we show several examples.
inf sup
RN T (FiIEFA
T 013
(5)
If f has bounded support X. then Assumption 3(a) holds with Cş = V(X) and 3 = 1, which (XX) is the volume of the support set X.
Example 1.
We then show the minimax regret bounds for unbounded support, which a new result that has not been obtained before.
Example 2. If f has p-th bounded moment, i.e. [||]||]
<
Theorem 2. Denote FB as the set of pairs (f, n) that satisfy Assumption I and 3 (which means that the contexts have unbounded support). Then
oo, then for all B < pp + d), there exists a constant C3 such that Assumption 3(a) holds. In particular, for subgaus- sian or subexponential random variables, Assumption 3(a)
holds for all B <) 1.
inf sup R R (fn)FF
1a+ a+1d+2)
+ +
(6)
Proof. The analysis of these examples and other related discussions are shown in the supplementary material. IT
From the results above, with 3 - oc, (6) reduces to (5).
It worths mentioning that although the growth rate of the regret is affected by the value of 3, our proposed algorithms including both fixed and adaptive methods do not require knowing 3.
Proof. (Outline) For bounded support, we just derive the lower bound of regret by analyzing the minimax optimal number of suboptimal actions first. Define
T
(b) restricts the suboptimality gap of each action. This is not necessary if the support is bounded. However, with unbounded support, without assumption (b), 17" (x) (x) can increase appropriately with the decrease of f fxx), such that the regret of suboptimal action is large, and the identifi- cation of best action is hard.
= Σ
1(TA, < < <x)()))
(7)
S can be lower bounded using standard tools in nonparamet- ric statistics (Tsybakov, 2009), which constructs multiple hypotheses and bounds the minimum error probability. As shown in (Rigollet & Zeevi, 2010), the lower bound of S can then be transformed to the lower bound of R.
Finally, we clarify notations as follows. Throughout this paper, |I-I| denotes & norm. S denotes a I Cb for some constant C, which may depend the constants in Assumption 2. The notation 2 is defined conversely.
The minimax analysis becomes more complex with un- bounded support. Firstly, the heavy-tailed context distri- bution requires different hypotheses construction. Secondly, the transformation from the lower bound of S to R does not yield tight lower bounds. We design new approaches to construct set of candidate functions and derive lower bounds of R directly.
4. Minimax Analysis
In this section, we show the minimax lower bound, which characterizes the theoretical limit of regrets of contextual
4

---

Contextual Bandits for Unbounded Context Distributions
For bounded context support, regret comes mainly from the region with 77" (xx) na (x) & T-1/(d+2) (which is the clas- sical rate for nonparametric estimation (Tsybakov, 2009)), in which the identification of best action is not guaranteed to be correct. However, with heavy-tailed contexts, regret may also come from the tail, i.c. the region with small fxx, where the number of samples around x is not enough to yield reliable best action identification. For heavy-tailed cases, i.e. B is small, the regret caused by the tail region may dominate. This also explains why we need to use dif- ferent techniques to derive the minimax lower bound for heavy-tailed contexts.
bounds the estimation bias, while is an upper bound of the error caused by random noise that holds with high probabil- ity. In Lemma 5 in Appendix E, we show that c is valid UCB estimate of na. (x, i.e. fi. 2 na, (x) holds with high probability. If (t) < k. then it is impossible to give a UCB estimate. In this case, we just let faa to be infinite.
Finally, the algorithm selects the action As with the maxi- mum UCB value:
A = arg maxffo,
(12)
In the remainder of this paper, we claim that a method is nearly minimax optimal if the dependence of expected regret on T matches (5) or (6). Following conventions in existing works (Rigollet& & Zeevi, 2010; Perchet & Rigollet, 2013; Hu et al., 2020; Gur et al., 2022), currently, the minimax lower bounds are derived for contextual bandit problems with only two actions, thus we do not consider the minimax optimality of regrets with respect to the number of actions |.A]
According to (11), as long as an action has not been taken for at least & times, the UCB estimate 1/ will be infinite. Note that the selection rule (12) ensures that the actions with infinite UCB values will be taken first. Therefore, the first k k|A|| steps are used for pure exploration. In this stage, the agent takes each action for k times. After k|AA] steps, the UCB values for all x E X' and a E A become finite. Since then, at each step, the action is selected with the maximum UCB value specified (9).
5. Nearest Neighbor Method with Fixed k
Algorithm 1 Adaptive nearest neighbor with UCB explo- ration
To begin with, we propose and analyze a simple nearest neighbor method with fixed k. We make the following definitions first.
for ( == 1,..,,, T do
Receive context X,; for a E A do Calculate na(()= = Iii < f|A, = a}; if na(() k then
Denote n., (1)= = Iii < 1/A, = a)l as the number of steps with action before time step t. Let M a) be the set of l nearest neighbors among {i < t A. a). Define
Calculate (x, using (9); else
(x)
max (x,a
X
x||
Let (Xe) = oc; end if
as the k nearest neighbor distance, i.e. the distance from x to its k-th nearest neighbor among all previous steps with action a.
end for
A, = arg max, Ma (X.): Pull Ar; end for
With the above notations, we describe the fixed k nearest neighbor method follows. If no (t) 2 k. then
The procedures above are summarized in Algorithm 1. Com- pared with (Guan & Jiang, 2018), our method constructs the UCB differently. In (Guan & Jiang, 2018), the UCB is 1 Σ Y, + (T, - 1)), in which (Ta - 1)) is
(x. = Σ
+++++ b+ (x):
(EN((x.a)
in which b has fixed value
(x.a(
uniform among all with fixed action a.
20²
b = V k
In In(dT2d+2|
(10) Therefore, the method (Guan & Jiang, 2018) is not adaptive to the suboptimality gap 1)" (x) na (x). On the contrary, our method has a term (x)) that varies for different x, and thus adapts better to the suboptimality gap. The bound of regret is shown in Theorem 3.
If (t) < k then
[x) = oc.
(1))
Theorem 3. Under Assumption I and 2, the regret of the simple nearest neighbor method with UCB exploration is bounded as follows:
Here we explain our design. If (aa()) 2 k. then it is possible to give a UCB estimate of na (x), shown in (9). e
5

---

Contextual Bandits for Unbounded Context Distributions
(1) > a+ 1, then with l- TT
or the suboptimality gap (x) 1/a (x) is large, the samples with action a are relatively sparse. In this case, with fixed k, the nearest neighbor distances are too large, resulting in a large estimation bias, On the contrary, if fx) is high or v7" (x) - na (x) is small, then samples with action a are relatively dense, thus the bias is small, and we can increase & to achieve a better bias and variance tradeoff. Therefore, if is fixed throughout the support set, then the algorithm estimates the reward function na (x) in an inefficient way, resulting in suboptimal regrets. Apart from suboptimal re- gret, another drawback is that with d S + 1, the optimal selection of k depends on the margin parameter a, which is usually unknown in practice. In the next section, we propose an adaptive nearest neighbor method to address these issues mentioned above.
R R A In (dT Al);
(13)
lfd 5 a + 1, then with is ~ T Tots,
R RS A 2 (dT2d+2|Al).
(14)
We compare our result with (Guan& & Jiang, 2018), which proposes similar nearest neighbor method. The analysis in (Guan& & Jiang, 2018) does not make Tsybakov mar- gin assumption (Assumption ((a),, and the regret bound is ÖTT ). Without any restriction on 7, Assumption (() holds with C. = 1 and = 0, under which (13) reduces to Ö(T aid ). Therefore, our result matches (Guan & Jiang, 2018) with a O. If O, which indicates that a small optimality gap only happens with small probability, then the regret of the method in (Guan & Jiang, 2018) is still Ö(T)F) ) while our result improves it to Ö * ). As discussed earlier, compared with (Guan & Jiang, 2018),
6. Nearest Neighbor Method with Adaptive k
In the previous section, we have shown that the standard KNN method with fixed l is suboptimal with d S a + 1 or 8 < 1/d. The intuition is that the standard nearest neighbor method does not adjust & based on the pdf and the suboptimality gap. In this section, we propose an adaptive nearest neighbor approach. To achieve good exploration- exploitation tradeoff and bias-variance tradeoff, k needs to be smaller for small pdf fx) or large suboptimality gap ry" (x) Ta (z). and vice versa. However, as both f'xx and ry" (x) na (x) are unknown to the learner, we need to decide & based entirely on existing samples. The guideline of our design is that given a context X, at time t, we use large k if previous samples are relatively dense around X,, and vice versa. To be more precise, for all x E X,, let
our method improves the UCB calculation in (17), and is
thus more adaptive to the suboptimalilty gap 1)" (x) na (x)-
With > 0, our method achieves smaller regret due to better tradeoff between exploration and exploitation.
Compared with the minimax lower bound shown in The- orem 1, it can be found that the KNN method with fixed k is not completely optimal. With d > a + 1, the upper bound matches the lower bound derived in Theorem How- ever, with d I a + 1, the regret is significantly higher than the minimax lower bound, indicating that there is room for further improvement.
We then analyze the performance for heavy-tailed context distribution. The result is shown in the following theorem.
k,(x) = max jilpaes(x) S
In j
(16)
Theorem 4. Under Assumption and 3, the regret of the simple nearest neighbor method with UCB exploration is bounded as follows:
in which (x. is the distance from x to its j-th near- est neighbors among existing samples with action a, i.c. {i < f/4, a). Such selection of k makes the bias term Lpo.t.j (x) matches the variance term VlnT thus (16) achieves good tradeoff between bias and variance. The exploration-exploitaiie
mminld. R S T min(d-1 (1 28)+28
AA|
In max(d,a+)) 2442 LA).
(15)
tradeoff is also desirable as (x.),((x) is large with large 17" (x) (x)), which yields smaller k. Note that (16) can be calculated only if I.pa,s, S Vin which means that the 1-nearest neighbor distance can not be too large. At some time step t, for some action a, if there is no existing samples, or X, is more than vhn T far away from any existing samples X,...., X,-,, then we can let let the UCB estimate to be infinite, i.e. fx) = co. Otherwise, we calculate the upper confidence bound as fol- lows:
From (15). there are two phase transitions. The first one is at d = a + 1, while the second one is at d3 = 1. In- tuitively, the phase transition occurs because the regret is dominated by different regions depending on the settings a and B. Compared with the minimax lower bound shown in Theorem 2, it can be found that the kNN method with fixed k achieves nearly minimax optimal regret up to logarithm factors if d > a + 1 and 3 > 1/d, otherwise the regret bound is suboptimal. Here we provide an intuition of the reason why the kNN method with fixed & achieves subopti- mal regrets. In the region where the context pdf f' f(x low,
Σ (x,) (x) (x..(xx.a)
Y,+ (x, Ixp,((x), (17)
6

---

Contextual Bandits for Unbounded Context Distributions
in which Nx, a) is the set of (x) neighbors of a among {i t|A, = a), (x) is the corresponding (x)) neigh-
We then analyze the performance of the adaptive nearest neighbor method for heavy-tailed distribution. The result is shown in the following theorem.
bor distance of x, i.. (x, (x (x), and
Theorem 6. Under Assumption 1 and Assumption 3, the regret of the adaptive nearest neighbor method with UCB (18)
20²
In(d[2a43|AI) (x) V (x)
exploration is bounded by
Similar to the fixed nearest neighbor method, the last two terms in (17) cover the uncertainty of reward function esti- mation. The term (x) gives a high probability bound of random error, and L.,,.(e (x) bounds the bias. With the UCB calculation in (17), the f is an upper bound of r7(x) that holds with high probability, that the exploration and exploitation can be balanced well. The complete description of the newly proposed adaptive nearest neighhor method is shown in Algorithm 2.
{
T pl-miuf
A
if
8 a+2
R S
(20)
T T
T AA
if
3 242'
Compared with the minimax lower bound shown in The- orem 2, it can be found that our method achieves nearly minimax optimal regret up to logarithm factor. Regarding this result, we have some additional remarks.
Remark 1. It can be found that with 3 - oc, the regret bound in (20) reduces to (19). As discussed earlier, the case that contexts have bounded support and f is bounded away from zero can be viewed as a special case with 3 -> 0o.
Algorithm 2 Adaptive nearest neighbor with UCB explo- ration
for t 1,..., T.. do
Remark 2. In (Zhao & Lai, 2021b), it is shown that the op- timal rate of the excess risk of nonparametric classification is Ô N
Receive context Xx; for E do if (X,,,.(XX)) > VIn then
) From (20), the average regret over (ााा
(a-ne
all T steps is Ô (T a-(2-2)6 which has the same rate as the nonparametric classification problem.
Na. (X,) = 00:
else
Calculate (x,), using (16);
Calculate (X,, using (17);
7. Numerical Experiments
end if
end for
To begin with, to validate our theoretical analysis, we run experiments using some synthesized data. We then move on to experiments with the MNIST dataset (LeCun, 1998).
A, = arg max Na (Xt):
Pull Ac; end for
7.1. Synthesized Data
We then analyze the regret of the adaptive method for both bounded and unbounded supports of contexts.
To begin with, we conduct experiments with d = In each experiment, we run T 1, 000 steps and compare the performance of the adaptive nearest neighbor method with the UCBogram (Rigollet & Zeevi, 2010), ABSE (Perchet & Rigollet, 2013) and fixed & nearest neighbor method. For fair comparison, for UCBogram and ABSE, we try different numbers of bins and only pick the one with the best perfor- mance. The results are shown in Figure 1. In (a), (b), (c), and (d), the contexts follow uniform distribution in [-1, 1]. standard Gaussian distribution. t, distribution, and Cauchy distribution, respectively. The uniform distribution is an example of distributions with bounded support. The Gaus- sian, t4 and Cauchy distribution satisfy the tail assumption (Assumption 3(a)) with 3 = 1, 0.8 and 0.5, respectively. In each experiment, there are two actions. For uniform and Gaussian distribution, we have 7/1 (x) = x and ()r(a) = -x.
Theorem 5. Under Assumption and 2, the regret of the adaptive nearest neighbor method with UCB exploration is bounded by
T In T
243
RSTII
(19)
By comparing Theorem 5 with Theorem 3, it can be found that for the case with bounded support, the adaptive method improves over the fixed & nearest neighbor method. From the minimax bound in Theorem 1, the fixed & method is only optimal for d 2 a + 1, while the adaptive method is 1, up to logarithm factors. An intuitive explanation is that with large the suboptimality gap 17" (x) na (x) is small only in small region, and tradeoff becomes harder, thus the advantage of the adaptive method over the fixed one becomes more obvious.
also optimal for d <
"The analysis in (Zhao & Lai, 2021b) is under general smooth- ness assumption with parameter p. p = corresponds to the Lips- chitz assumption (Assumption 1(c) in this paper). Therefore, here we replace the bounds (Zhao & Lai, 2021b) with p = 1.
the exploration-exploitaae
7

---

Contextual Bandits for Unbounded Context Distributions
250
50.
170
200-
330
20
200
22
Toes, 20
ABSE
Red <e10
ABSE
20
AB22
fead t-
Toes, ko1k
ABGE
adapiie
acuptive
adeprie
Stape
Strpe
Stepe
Stnps
(a) Uniform distribution.
(b) Gaussian distribution.
(a) Uniform distribution.
(b) Gaussian distribution.
172
500-
10
350
400-
2300
102-
200
25-
1t0
LOlggran
UCOog
UCDogrem sdiptte
ABS2
100
ad3pthu
200
69
620
1000
255
055
6in
1050
500
1250
1.50
2500
503
1003
3500
2003
(c) tu distribution.
(d) Cauchy distribution.
(c) 44 distribution.
(d) Cauchy distribution.
Figure 1. Comparison of cumulative regrets different methods for one dimensional distributions.
Figure 2. Comparison of cumulative regrets of different methods for one dimensional distributions.
6000
For t4 and Cauchy distribution, since they are heavy-tailed, to ensure that Assumption 3(b) is satisfied, we do not use the linear reward function. Instead, we let 7/1 (z) = sin(x) and (2(2)) = cos(2), - To make the comparison more reliable, the values in each curve in Figure are averaged over m = 100 random and independent trials.
2500
2000
1500
(weil km Fooed lon
adaptiee
Steps
We then experiments for two dimensional distributions. In these experiments, the context distributions are just Carte- sian products of two one dimensional distributions. The two dimensional Gaussian distribution still satisfies Assumption 3(a) with 3 = 1, and the two dimensional 44 and Cauchy distribution satisfy Assumption 3(a) with = 2/3 and 1/3, respectively, which are lower than the one dimensional case.
Figure 3. Cumulative regrets for MNIST dataset.
From Figure the adaptive kNN method performs better than the standard kNN method with various values of k.
8. Conclusion
This paper analyzes the contextual bandit problem that al- lows the context distribution to be heavy-tailed. To begin with, we have derived the minimax lower bound of the ex- pected cumulative regret. We then show that the expected cumulative regret of the fixed ic nearest neighbor method is suboptimal compared with the minimax lower bound. To close the gap, we have proposed an adaptive nearest neigh- bor approach, which significantly improves the performance, and the bound of expected regret matches the minimax lower bound up to logarithm factors. Finally, we have conducted numerical experiments to validate our results.
The results are shown in Figure 2.
From these experiments, it can be observed that the adaptive nearest neighbor method significantly outperforms the other
baselines.
7.2. Real Data
Now we run experiments using the MNIST dataset (LeCun, 1998), which contains 60, 000 images of handwritten digits with size 28 x 28. Following the settings in (Guan & Jiang, 2018), the images are regarded as contexts, and there are 10 actions from 0 9. The reward is if the selected action equals the true label, and 0 otherwise. The results are shown in Figure 3. Image data have high dimensionality but low intrinsic dimensionality. Compared with bin splitting based methods (Rigollet& & Zeevi, 2010; Perchet & Rigollet, 2013), nearest neighbor methods are more adaptive to local intrinsic dimension (Kpotufe, 2011). Therefore, in this experiment, we do not compare with the bin splitting based methods.
In the future, this work can be extended in the following ways. Firstly, following existing analysis in (Gur al., 2022), it may be meaningful to design smoothness adap- tive method that can handle any Hölder smoothness parame- ters. Secondly, it is worth extending current work to handle dynamic regret functions. Finally, the theories developed in this paper can be extended to more complicated tasks, such as reinforcement learning (Zhao & Lai, 2024).
8

---

Contextual Bandits for Unbounded Context Distributions
Impact Statement
Bouneffouf, D., Rish, I., and Aggarwal, C. Survey on appli-
cations of multi-armed and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8, 2020.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Cai, C., Cai, T. T., and Li, H. Transfer learning for contex- tual multi-armed bandits. The Annals of Statistics, 52(1):
Acknowledgements
207-232, 2024.
Cannings, T. L., Berrett, T. B., and Samworth, R. J. Local nearest neighbour classification with applications to semi- supervised learning, The Annals of Statistics, 48(3):1789- 1814, 2020.
This work supported by STI 2030-02::00 MMjor Projects (No.
20217D0201 405), Shenzhen Basic Research Project (Natu- ral Science Foundation) Basic Research Key Project (NO. 272120241122124430000
2025 Open Project of the Key Laboratory of Blockchain Technology and Data Security of the Ministry of Industry and Information Technology, Open Research Fund from Guangdong Laboratory of Arti- ficial Intelligence and Digital Economy (SZ.) (NO. GML- KF-24-23), National Natural Science Foundation of China (No.62372120, 62102108), GuangDong Basic and Ap- plied Basic Research Foundation (No.2022A151501006 and Science and Technology Projects in Guangzhou (N0.2025A0311188).
Chaudhuri, K. and Dasgupta, S. Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems, volume 27, 2014.
Chu, W., Li. L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Döring, M., Györfi, L., and Walk, H. Rate of convergence of k-nearest-neighhor classification rule. Journal of Ma- chine Learning Research, 18(227):1-16, 2018.
References
Abbasi-Yadkonk Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
Dudik, M., Hsu, D., Kale, S., Karampatziakis, N., Langford, J., Reyzin, L.., and Zhang. T. Efficient optimal learning for contextual bandits. arXiv preprint arXiv: 106.2369, 2011.
Agrawal, R. Sample mean based index policies by o (log n) regret for the multi-armed bandit problem. Advances in applied probability,
Durand, A., Achilleos, C., Iacovides, D., Strati, K., Mitsis, G. D., and Pineau, J. Contextual bandits for adapting treatment in mouse model of de novo carcinogenesis. In Machine learning for healthcare conference, pp. 67-82, 2018.
1995.
Akhavan, A., Lounici, K., Pontil, M., and Tsybakov, A. B. Contextual continuum bandits: Static versus dynamic regret. arXiv preprint arXhv:2406.05714 2024.
Fedotov, A. A., Harremoës, P., and Topsoe, F. Refinements of pinsker's 's inequality. IEEE Transactions on Information Theory, 49(6):1491-1498 2003.
Audibert, J.-Y. and Tsybakov, A. B. Fast learning rates for plug-in classifiers. The Annals of Statistics, pp. 608-633, 2007.
Gadat, S., Klein, T., and Marteau, C. Classification in gen- eral finite dimensional spaces with the k nearest neighbor rule. The Annals of Statistics, pp. 982-1009, 2016.
Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
Gao, W. Oh. S., and Viswanath, P. Demystifying fixed k-nearest neighbor information estimators. IEEE Trans- actions on Information Theory, 64(8):5629-566.. 2018.
Bastani, H. and Bayati, M. Online decision making with high-dimensional covariates. Operations Research, 68 (1):276-294, 2020.
Garivier, A. and Cappé. O.
The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 359-376, 2011.
Bastani, H., Bayati, M., and Khosravi, K. Mostly exploration-free algorithms for contextual bandits. Man- agement Science, (7(3):1329-1399 2021.
Ghosh, A., Sankararaman, A., Ramchandran, K., Javidi, T., and Mazumdar, A. Competing bandits in non-stationary matching markets. IEEE Transactions on Information Theory, 2024.
Blanchard, M., Hanneke, S., and Jaillet, P. Adversarial rewards in universal learning for contextual bandits. arXiv preprint arXiv:2302.00 0860001866660 2023.

---

Contextual Bandits for Unbounded Context Distributions
Guan, M. and Jiang, H. Nonparametric stochastic contex- tual bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Locatelli, A. and Carpentier, A. Adaptivity to smoothness in x-armed bandits. In Conference Learning Theory, pp. 1463-1492, 2018.
Gur, Y., Momeni, A., and Wager, S. amoothness-adaptive contextual bandits. Operations Research, 70(6):1198 3216, 2022.
Mai, V. V. and Johansson, M. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pp. 7325-7335, 2021.
Hu, Y. Kallus, N., and Mao, X. Smooth contextual ban- dits: Bridging the parametric and non -on-differentiable re- gret regimes. In Conference on Learning Theory, pp- 2007-2010, 2020.
Misra, K., Schwartz, E. M., and Abernethy, J. Dynamic online pricing with incomplete information using mul- tiarmed bandit experiments. Marketing Science, 38(2): 226-252, 2019.
Huo, M., Lu, K., Li, Y., and Zhu, Q. Ct-patchtst: Channel -ime patch time-series transformer for long- term renewable energy forecasting. arXiv preprint wrXiv:2501.08620 2025a. URL https://arxiv: org/ abs/ 2501. 08620.
Perchet, V. and Rigollet, P. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):693 2013.
Qian, W. and Yang, Y. Kernel estimation and model com- bination in bandit problem with covariates. Journal of Machine Learning Research, 17(149):1-31) 2016.
Huo, M., Lu, K., Zhu, Q. and Chen, Z. Enhancing cus- tomer contact efficiency with graph neural networks in credit card fraud detection workflow. arXiv preprint 0227, 2025b. URL https: //rxiv//arxv.. hTrg/bb//5044.00
Qian, W., Ing, C.-K.,, and Liu, J. Adaptive algorithm for multi-armed bandit problem with high-dimensional co- variates. Journal of the American Statistical Association, pp. 1-13, 2023.
Jiang, H. Non-asymplotic uniform rates of consistency for k- nn regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3999 4009, 2019.
Reeve, H., Mellor, J., and Brown, G. The k-nearest neigh- bour ucb algorithm for multi-armed bandits with covari- ates. In Algorithmic Learning Theory, pp. 755-752, 2018.
Komiyama, J., Fouché, E.,, and Honda, Finite-time analy- sis of globally nonstationary multi-armed bandits. Jour- nal of Machine Learning Research, 25(1 12):1-56, 2024.
Rigollet, P. and Zeevi, A. Nonparametric bandits with co- variates. 23th Annual Conference on Learning Theory, pp. 54, 2010.
Kpotufe, S.
k-nn regression adapts to local intrinsic di- mension. In Advances in Neural Information Processing Systems, pp. 729-737, 200-737,,1111 2011.
Robbins, H. Some aspects of the sequential design of exper- iments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
Krishnamurthy, A., Langford, J., Slivkins, A., and Zhang, C. Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Journal of Machine Learning Research, 21(137):1-45, 2020.
Slivkins, A. Contextual bandits with similarity information. Journal of Machine Learning Research, 15:2533 2014.
Suk, J. Adaptive smooth non-stationary bandits. arXiv
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1): 4-22, 1985.
preprint arXiv:2407.08654 2024.
Suk, J. and Kpotufe, S. Tracking most significant shifts in nonparametric contextual bandits. Advances in Neural Information Processing Systems, 36:6202-6244 (200022621,20000 2023.
Langford, J. and Zhang. T. The epoch-greedy algorithm for multi-armed bandits with side information. Advances in Neural Information Processing Systems, 20, 2007.
Tsybakov, A. B. Introduction to Nonparametric Estimation. 2009.
LeCun, Y. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/, 1998.
Wanigasekara, N. and Yu, C. L. Nonparametric contextual bandits in an unknown metric space. Advances in Neural Information Processing Systems, 32: 1464-146994 2019.
Li, L., Chu, W., Langford, J., and Schapire, E. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th interna- tional conference on World wide web, pp. 661-670, 2010.
Woodroofe, M. A one-armed bandit problem with con- comitant variable. Journal of the American Statistical Association, 74(368):799 806, 1979.
10

---

Contextual Bandits for Unbounded Context Distributions
Yang, Y. and Zhu, D. Randomized allocation with parametric estimation for a multi-armed bandit problem with covariates. The Annals of Statistics, 30(1):100-121, 2002.
Zangerle, E. and Bauer, C. Evaluating recommender sys- tems: survey and framework. ACM Computing Surveys, 55(8):1-38, 2022.
Zhang. Q., Deng. Z., Chen, Z.., Hu, H., and Yang. Stochas- tic continuous submodular maximization: Boosting via non-oblivious function. In International Conference on Machine Learning, pp. 26116-26134 PMLR, 2022.
Zhang. Q. Deng, Z., Chen, Z., Zhou, K., Hu, H., and Yang, Y. Online learning for non-monotone dr-su dt-submmduula max- imization: From full information bandit feedback. In International Conference Artificial Intelligence and Statistics, pp. 3515-3537. PMLR, 2023.
Zhao. P. and Lai, L. Efficient classification with adaptive knn. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11007-11014, 2021a.
Zhao, P. and Lai, L. Minimax rate optimal adaptive nearest neighbor classification and regression. IEEE Transactions on Information Theory, 67(5):3155-3188 2021b.
Zhao, P. and Lai, L. Analysis of knn density estimation. IEEE Transactions on Information Theory, 68( 12717 7995, 2022.
Zhao, P. and Lai, L. Minimax optimal q learning with nearest neighbors. IEEE Transactions on Information Theory, 2024.
Zhao, P. and Wan, Z. Robust nonparametric regression under poisoning attack. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17007-17015, 2024.
Zhou, Q. Zhang, X., Xu, J., and Liang, B. Large-scale bandit approaches for recommender systems. In Neu- ral Information Processing: 24th International Confer- ence, ICONIP 2017, Guangzhou, China, November 14- 18, 2017, Proceedings, Part 24, pp. 811-821. Springer, 2017.
Zhu, Y., Foster, D. J., Langford, J., and Minciro, P. Con- textual bandits with large action spaces: Made practical. In International Conference on Machine Learning, pp. 77428-27553, PMLR, 2022.

---

Contextual Bandits for Unbounded Context Distributions
A. Examples of Heavy-tailed Distributions
This section explains Example and 2 in the paper. For Example I,
P((() <1) | [(x)1([(x){ < <1)xx51V(2)) (2).
(21)
For Example 2, from Hölder's inequality,
/ (x) = / (x)+ 1 ||x||
1
(1 [
|I
1-3
(f(++1811))+
(22)
Let = p(1 - 8), then (xx( 11x11)) 1-9
< 0c.
If B < p/(p + d), then 7/8 > d. thus
(J(1+ [ &xxx) @ < co. Hence f -1 (x))xx < 00, and
P((() < = P(S x ( = / (1-0(x)
(23)
Therefore for all 8 < p/(p + d), Assumption 3(a) holds with some finite Cj.
For subgaussian or subexponential random variables, [|I] < co holds for any p. thus Assumption 3(a) holds for B arbitrarily close to 1.
B. Expected Sample Density
In this section, we define expected sample density, which is then used in the later analysis. Throughout this section, denote =(j) the value of j-th component of vector x.
Definition 1. (expected sample density) qu : X defined as the function such that for all S C X.
T
1X, E A, ai) = la (x)
E
Σ
(24)
To show the existence of la. define
Qa(x) E
Σ 1(x, E (u/u(1) s((1,,..., m(d) S x(d)), A. =a)
(25)
Then let
8dQ..
(x(x) dx(1) ... dx (d
(26)
and then (24) satisfied for all C
Then we show the following basic lemmas.
Lemma 1. Regardless of n,, Ja satisfies
(x)x) (x)))
(27)
for almost all x X.
12

---

Contextual Bandits for Unbounded Context Distributions
Proof. Note that P(X; S) Ss (x)dxx Therefore for all set S
1x, E S, A. - ST / [xx)xx.
E
(28)
From (24) and (28), Ss (x)xxx S T SS dx) for all S. Therefore (x(x) S Tx)) for almost all x E X.
Lemma 2. R. = EaEd Rai in which Ra is defined as
Rg = / (1)(xx) "aa (a(x))qo (x)))xxx)xxx
(29)
Proof.
T
R
E
(n' (X.) mx.)x
T
Σ aEA
E
Σ
(1i - na ( a)
[=]
Σ
/
(n)((x) - TT (x)) gu (x)
(30)
aEd
The proof is complete.
C. Proof of Theorem 1
Recall that
T - (nx
R E
(31)
Now we define
=
Σ (nA. < (Xi)))
(32)
as the expected number of steps with suboptimal actions.
The following lemma characterizes the relationship between S and R.
Lemma 3. There exists constant Co, such that
R2 CoS at T-
(33)
Proof. The proof of Lemma 3 follows the proof of I Lemma 3.1 in (Rigollet & Zeevi, 2010). For completeness and consistency of notations, we show the proof in Appendix I.10.
From now on, we only discuss the case with only two actions, such that A = {1, - 1}. Construct B disjoint balls with centers CI,..., Cg and radius h. Let
f(x)
Σ 1(x Bj),
(34)
1=1
in which B, [x'] |X' - ccyll S h) is the j-th ball. To ensure that the pdf defined above is normalized (i.e. f(x)dx 1).
B and h need to satisfy
Bugh d =1 1,
(35)
13

---

Contextual Bandits for Unbounded Context Distributions
in which va is the volume of d dimensional unit ball.
Let (x) r7(x) and m22 (x) 0, with
7xx)
Σ (x B)),
(36)
which vi E {-1, for I,..., K. To satisfy the margin assumption (Assumption I(a)), note that
Keah t t2 h if << h.
P(O < $1) S
(37)
Note that for any suboptimal action a, 7x(x (x(x)) = |n(x)]. Assumption ((a) requires that P(O < |n(X) St) S Cata.
Therefore, suffices to ensure that
Kugh C.
(38)
Then
K T
ΣΣ
P(G, E &
ΣΣ
f(x)
x)dx
/= B,
K
ΣΣЛ
f(x)P(A
= ΣΣ E
T
Jo ((x)1(((2;Xxxe Y1se-) + uz)dx
(39)
B
==
Define
ey(t) sign ( ((x) 11a-1) 1)xx
(40)
Then
J (xx))(((( -0,()))) 0,(1)) / f(x) (1x --o(()) dx.
13
(41)
n3
Since
1 (Tx: -0,(t)) dx + / f(x)1 (1 11a-; Vi-11 11 -ty(t) dx
B,
= - [(x)dx,
(42)
B,
we have
/ B,
/ f(x)dx.
(y()) dx N 2 B,
(43)
If (1) o Uj then
1 B,
1 [xx] 11 1;) dx 2 2 B,
f(x)dxx
(44)
14

---

Contextual Bandits for Unbounded Context Distributions
Therefore, from (39).
K
P(o,(t) # #2²)) / B, f(x)
S 2
j=l ==1 K j=1
Uah (t)) + 1z).
(45)
Note that the error probability of hypothesis testing between distance p and is at least (1 - TV(p, g))/2, in which TV denotes the total variation distance. Let (V,...., Vx) be a vector of K random variables taking values from {-1, randomly. In other words, P(V, = 1) P(V, -1 1/2, and Vj for different, j are i.i.d. Denote Pxyı,== as the distribution of X and Y conditional on V = ey. Moreover, P XYIV== means the distribution of X and Y of the first 1 samples conditional on V Vj. Then
P(0,(t) 0z) 2 1 TV
pt-1 X X ))
1- V 2
P
(46)
2
in which the second step uses Pinsker's 's inequality (Fedotov et al., 2003), and D(pllg) denotes the Kullback-Leibler (KL) divergence between distributions and Note that the KL divergence between the conditional distribution is bounded by
DB
1 7x)(x) (x)) (xx mx(x))² s 2 2 (m
- h2
(47)
for x E By. Therefore
D D(PxI,=-1IPxx11 / (
S
2 h²dxx
B3
1
=
2
uahh+2
(48)
Hence, from (46).
1
P(),(t) * 2z)
2
(t 1)ahha2
2
1
1
/Tuahdtz)
IV
(49)
2
2
Recall (45),
T
vah (1 ( (Tughd+2
S
>
j=1
1
KTeah
1
v Toghd+2
2
CaTHa
[
VTughd+2
(50)
4
in which the last step comes from (38).
Let T 2ेz then
S 127--
(51)
15

---

Contextual Bandits for Unbounded Context Distributions
From Lemma 3,
R 2 T(1-aiz) T T1-212
T2-312 212.
(52)
D. Proof of Theorem 2
In this section, we derive the minimax lower bound of the expected regret with unbounded support. Recall that in the case with bounded support of contexts (Proof of Theorem I in Appendix C), we construct B disjoint balls with pdf [(x) 1 for all X. Now for the case with unbounded support, the distribution of context has tails, on which the pdf f(x is small. Therefore, modify the construction of balls as follows. We now construct B + disjoint balls with center Co..... CB. such that
Bo = (x'l ||x - coll S ro),
(53)
B₁ fx'l |Ix cyll s h}.
(54)
Let
K
n1xx)
Σ j=1
eyhl(x B(c,,h))
(55)
in which vy {0, 13 is unknown, and
f(x) 1(x E Bo) + Σ m1(x B,).
(56)
in which m < 1 will be determined later. Here we construct one ball that denotes the center region which has the most of probability mass, as well as B balls that denotes the tail region. For simplicity, we let n7(x) = O at the largest ball By, and only
To satisfy the margin condition (i.e. Assumption I(a),, note that now
mKuah if t h
P(O
[ < t)
(57)
if 1 < h.
The right hand side of (57) can not exceed Cata, which requires
mKosh" Caha.
(58)
Moreover, to satisfy the tail assumption (Assumption 3(a)), note that
mKuah
if m
P((()) <t)
(59)
0 if < m.
The right hand side of (59) can not exceed Cat9, which requires mKuah' Z C.m²
(60)
Following (45), can be lower bounded by
l P(o,(t) + &0)) J Jn, f(x)dx
s
j=1
K
Σ
moah ( (1))
K meah d'
2
11
4
2
j=l
K
ΣΣ
maahh
1
5 v /Tmuaht+2
1
(61)
4
t=1
16

---

Contextual Bandits for Unbounded Context Distributions
From (61), we pick and h to ensure that
Tmeah d22
(62)
2
Then under three conditions (58), (60) and (62),
2 KTmh
(63)
remains to determine the value of m, and K based on these three conditions. Let
h ~ (Tm)
(64)
T a+
(65)
and
K ha-a
amm m.
(66)
then
82 Th - a+
(67)
Based on Lemma 3,
R 2 S T- T---lal a+0(1)3))
(x+1))
(68)
It remains to show that R 2 T1-8, Let h 1, K T1-8 and 1/T, the conditions (58), (60) and (62) still satisfied. In this case,
S S2T1-8
(69)
Direct transformation using Lemma 3 yields suboptimal bound. Intuitively, for the case with heavy tails (i.e. 3 is small), the regret mainly occur at the tail of the context distribution. Therefore, bound the expected regret again.
R
E
Σ
(X.) (X.))
E
Σ h1 (1A. < (Xxi))
(
-
(70)
(a) comes from the construction of 1 in (55). (b) holds since we set h = here.
Combine (68) and (70),
2 T
+ +1-3
(71)
E. Proof of Theorem 3
To begin with we show the following lemma. Lemma 4, For all >
P
sup 2.a
Σ
W
>
I
dI
|Ale
(72)
k
(x.)
17

---

Contextual Bandits for Unbounded Context Distributions
Proof.
The proof is shown in Appendix I.1.
From Lemma 4, recall the definition of in (10),
sup (x,a(
Σ
Wi
>
S T
(73)
Therefore, with probability 1 1/T, for all E X, a E and 1, l,.... T. EiEN(( Wil/k b. Denote E as the
event such that Σ (x,,( Wil/k & b, Vx, a, f, then
Wi Ib 1)
P(E) P
(=1
sup
Σ
h
(xNi(
0))
0
1-P P
0==
T
sup
Σ (xNa(X,,)
W3
1
2 1- T
21
(74)
T
Recall the calculation of UCB in (9). Based on Lemma 4, we then show some properties of the UCB in (9).
Lemma 5, Under E, if Ki t|A, a}} 2 k, then
na (t) S (x)) S (x())) 2b + 2Lp,,
(75)
Proof. The proof shown in Appendix I.2.
We then bound the number of steps with suboptimal action a. Define
n (x,,,r))
Σ 1 ( x|| <r, = a).
(76)
Then the following lemma holds.
Lemma 6. Under E, for any x E X, E A. if -xaax)) > 2b, define
ra(x) 17" (xaxx) 2b
(77)
69
then
a(x,a,ra(x)) k.
(78)
Proof. The proof shown in Appendix I.3.
From Lemma 6, the expectation of nlzz a, (x))) can be bounded as follows.
E(n(z,a,raxx)) k ++1,
(79)
in which the first step holds since even if E does not hold, the number of steps in nıæ, Tx(x) is more than the total sample size T. The second step uses (74). From (79) and the definition of expected sample density in (24).
S S (u)du kk + 1.
(80)
18

---

Contextual Bandits for Unbounded Context Distributions
bounds the average value of Ya over the neighborhood of However, it does not bound qa (x) directly. To bound Rg introduce random variable Z, with pdf
g(z)
(81)
Mz 1(7" - To [z) Vel"
in which 4b, with b defined in (10). Mz is the constant for normalization. We then bound Rg defined in (29). R. can be split into two terms:
(F((x) (xx)))))(()))
Ra
(x(x) > c)dx
f - To (x)) (x)))))))))))) (x) 7a(x)) S e)dx.
(82)
To begin with, bound the first term in (82). We show the following lemma.
Lemma 7. There exists a constant C1, such that
1x (17(())) na (x)(()xxxxxx))((( No (x) > e)dx CiMZB (AIZ.. (a(u)(17(u)) na (u(u))du
(83)
in which e = 4b.
Proof.
The proof of Lemma is shown in Appendix I.4.
Now we bound the right hand side of (83). We show the following lemma. Lemma 8.
cotlld d> a+1
{ Unvenne go (a(u)(n" na (u))du S
Mae Mzc k
E
$
In
if a= if d d<all,
(84)
Mzc
in which e is the lower bound of pdf of contexts, which comes from Assumption 2.
Proof. The proof of Lemma is shown in Appendix I.5.
From Lemma 7 and 8,
kea+l-d if d > a if d = a +1
/ (11 (x) - (x()))))() - nx(x) > e)dx S
kln
(85)
if
d < +1
Now we bound the second term in (82), From Lemma 1, (x) S fxx) for almost all x E X. Thus
/ (x) (xx)) (x(x)= S c)dx
< / f (n7(()) (x) (x 1x)
na(x) S c)dx
< (n' (X) $c)
x C, ae
(86)
Therefore, from (82), (85) and (86),
Teatl + --a-l-d
if d>at1
R. <
Teatl + klnd if d=a+1
(87)
Tea +
if d<t+1.
19

---

Contextual Bandits for Unbounded Context Distributions
Recall that
20 In(dT24+2[A).
4b = VV k
(88)
Id adda+llee T4t2, then
C~ T पोड [m(dT2++2|A))
(89)
and
Rs x T 243 In #اب (dT ( (A).
(90)
fdda+1, T then
e T (n(d)2d+21A)),
(91)
and
Ra S Tais In (d - 2) (A)).
(92)
Theorem can then proved using by EvEA Ro stated Lemma
F. Proof of Theorem
Recall the expression of regret shown in Lemma 2. We decompose Ra follows.
J (n"((x) (x) (x())) S e)dx
Ra
/ (v((x) n) (x))a.xx
k
11" 11((x) (x) [(x)
dx
Ted
+ / (x7(xx - no (x)xx,x,,x) (x)1
k
k Ted
11((x) (x(x) > T
<
f(x)) S
dx
+ / (x) - "xa(x))a.(x))
x
(1((x) (x) > [xx) s r
dx
xx
11 + 12 + I3 + I4,
(93)
in which is the same as the proof of Theorem 3 in Appendix 5, i.e. 4b.
Bound of I,. From Lemma 1, (x) - fxx for almost all x E X. Hence
h < T 1 (x7(x) nh (x)) na(x) S e)dx
8x
< TeP(n((X) nh (X) c)
CaTetta
(94)
Bound of Iz. The regret of the high density region can be bounded similarly as the regret for pdf bounded away from zero Follow the proof of Theorem in Appendix 5, define
k [(())
g(2)
(95)
M2 (() - no (z))
Ted
Similar to Lemma 5,
12 S Mz
(a(u)(7'(u) na (u))dd..
(96)
B(Z.ra(Z))
20

---

Contextual Bandits for Unbounded Context Distributions
Similar to Lemma 6, now we replace with k/ (Te"). Then
Tel Te eatl-d My Tea
if d> a+l d=atl if d<a+l.
Jerznnace) (a(u)(17(1) Ta (u)))dd
In !
(97)
Mz
Te
Mz
Therefore
Telati-d
if d>at] In if d= Ted if d<a+l.
1 2
(98)
Bound of Iz. Here we introduce the following lemma.
Lemma 9. (Restated from Lemma 6 in (Zhuo & Lai, 2021b)) For any 0 <
< b
8 if > 3 h b
<b)
if = 3 if
(99)
g-p
p < B
Proof. The proof of Lemma 9 can follow that of Lemma 6 in (Zhao Lai, 2021b). For completeness, we show the proof in Appendix 1.9.
Based on Lemma 9, I3 can bounded by
Is f (T - (x)))))a(xx)) (n((x)) (x(x))
h
k
c, T
f(x)
dx
ed
k
T((x)1
(1((x) no (xxxx) c, T
h
f(x)
-
k
dx
x
T
Tea
k
Ted }
h.
T
E2
f 3 (X)1
T f(x) <
T' 4/ 3
if 8< 1
VA
T k In
if =
T
k
1-48
if B >
Bound of 4.
R ) dx TM / f(x) (((x)
4
S k
TMP(f(X)
T
k T
(100)
T
Now we bound R2 by selecting to minimize the sum of I, Iz, Iz. Ia. Recall that c = 4b, which is defined (10), thus /ln(dT2422 Al)/k.
If) a+1 and 8 1/d, then with ls To+(42277
k
R S T 1ta +
1-
T
glat1) 1) -1- a+id+2) In 27222+2(A1)
(101)
21

---

Contextual Bandits for Unbounded Context Distributions
2 + and B > 1/d, then with k ~ T 1ootar2y
R S T
c
c1-d0
T
T - (1+2)8 In
od
(102)
28
(3) If > a + 1 and B S 1/d, then with k ~ TTinl23,
k
8
R S Te +T
N
Blo+11 T 11a:23
In (dT (,A)).
a+1
(103)
28
If a 1 and B & 1/d, then with k ~ T2123
R S Te" T
N
dd T 242s In (dT 2d 2
(104)
Combine all these cases, conclude that
+ mmma-11)) 1,00 moxt (00)) 27 [A] In max(d,a+1) (dT (AA))
R
(105)
The proof of Theorem is complete.
G. Proof of Theorem
To begin with, similar to Lemma 4 and Lemma 5, we show the following lemmas. Lemma 10.
1
22 EdT2d+ LAle 20?
sup a.0.k
W, >
(106)
Vk (ENe,u(x.a)
with Ni, a) being the set of le neighbors among (X,li st, A=
Proof. From Lemma 4,
P
sup Z,a
1
Σ
W >
S 2d LAle =
(107)
(x.,)
Lemma 10 can then be proved by taking a union bound over all k.
Lemma 11. Define event E, such that E if
1
Σ
W, (((T
(108)
Vi
(eN,.(xxa))
for all x, a. K,,, then P(E) 21 1/T. Moreover, under E,
na (x) S na, (x) S Tx(xx) + 2b),((x) (x),,.
(109)
22

---

Contextual Bandits for Unbounded Context Distributions
Proof. The proof is similar the proof of Lemma 5.
(xx)(x)) (x) + bo,((x) + LPa,((x))]
1
Σ
(Y₁ na (x))
(x,((x)
(xN)(xx,a)
1
(Y₁ no (X())))
+ (x) (ENi(x.,)
Ma (X())) (x
(x,)(x) (x..(x..)
[x),((x) + (x))
(110)
With these preparations, we then bound the number of steps around each x in the next lemma, which is crucially different with Lemma 6. Here we keep the definition n(x, r) == Σx X| x|| < r. A, = a) to be the same as (76), but change the definition of ra and na as follows.
Lemma 12. Define
(x(x)= 2LV01
(1)( na (x)),
(111)
and
C₁ In
nx(x) = (1) 77 (x))
(112)
in which
C = m2x Indd)
(113)
Then under E,
n(x, a, ra(x)) S (x(x))
(114)
Proof. The proof of Lemma 12 is shown in Appendix 1.6.
From Lemma 12,
(l(x),),a(x))
na(x)+ +1.
(115)
From the definition of 9a in (24),
J J ga (u(udd na(xx) +
(116)
Now we bound Rg. Similar to (81), let random variable Z follows a distribution with pdf g:
g(z) Mz 7o (z)) Ve
(117)
The difference with the case with fixed l is that in (81), 4b. However, now (x) varies among thus we do not determine based on 6. Instead, for the adaptive nearest neighbor method, will be determined after we get the final bound of R..
We show the following lemma.
23

---

Contextual Bandits for Unbounded Context Distributions
Lemma 13. There exists constant C2. such that
Jx - -
( (
(x)3)) - 7x(xx) > c)dx S C2M2B
(a(u)(n"(u) na(u))du
(118)
Proof. The proof of Lemma 13 is shown in Appendix 1.7.
We then bound the right hand side of (118).
Lemma 14.
Umirnnue (a(u((n"(u) - no (u))du E Mz (ca-d-1ln InT + +Tel)))
E
(119)
Proof. The proof of Lemma shown in Appendix 1.8.
From Lemma 13 and 14,
[ (n" (x) - (x()))))) - nx(x) > c)dx S c- In + Tel+a
(120)
Moreover,
I (15" -x(())()((()(())))())) na(x)= S c)dx
S Te f(x)1(1)(xx) - -na(x) S c)dx
X Tetto
(121)
Therefore
Rs S 5 InT Tel+a
(122)
Note that we have not specified the value of earlier. Therefore, in (122), can take any values. We can then select to minimize the right hand side (122). Therefore, let
In T
(123)
then
1+a 442
T I
R₂ S T
(124)
The overall regret then be bounded by summation
140
T
R R TIA
(125)
In
H. Proof of Theorem 6
Define
Mz(11(2) na(2) 1 (1iz) (z) - (2) > e(x))
g(2)
(126)
which
(T)=(((((x)) #
(127)
24

---

Contextual Bandits for Unbounded Context Distributions
and M2 is the normalization constant, which ensures that f g()ddz 1. Let Z be random variable with pdf g. We then bound Ra for the case with unbounded support the contexts, under Assumption 2 and 3.
Ra = Ix (x)(x)) - (axx))
= J (n" (xc) - (xx(x)) (1xxx) - 7a(x)) > c(x), f(x) 2 T
1 1 dx
+ S (nn - -xx (7((x) 77(x)) S f(x),,(x)) 2 / ) dx
1
+ / (1)" (x) - (x)
f(x) < ) dx
x
1 I2 I3-
(128)
Now bound three terms in (128) separately.
Bound of 1T. Following Lemma 7 and 13, it can be shown that for some constant C3, such that
J (x - nx(x) > <(x))dxx & CzMzE
Unvenniee) (a(u)(r" (u) - no (u))ddu
(129)
The right hand side (129) can be bounded as follows.
E
(a(u)(r((u) T/a Vuauu)dd du
(()...(Z)
1 ( (a(1)(1((Z) 77a (Z)(Z)) )du
E
IN 1
B (Z) + 1)(1)) (Z) - na (2)]
2
(na(z) + 1)(1) - (z)2)
2M2
3
/(r(6)_ (z) + +z² -
C1 In T
Ta(2)) (r)(2) na (z)
1
((z))c(z).f(e) 2 1 dz
2Mz
IT
/ (n7(z) (z)) (d+1)] 7(2)) 2 (z)) 2 T dz.
1
27 Mz
(130)
Hence
1 S In (aaT/(r (n((x) (x))))
(((x) 2 ((xx), 2 1) dx.
(131)
Let c. E R that will be determined later.
/ (1) (x) (x())) (d+1)) - (x) 2 ((xx, c)dx
s / (xx(x) na (x())) (d++1) (17(x) (x) (Te)  / f(x)
= E [ir(x (X) - na (X)) (d+1)] (1'(X)) - (x) 2 (Te) (Tc)-
S (Te) (1
T(TC) #
(132)
To bound the integration of the other side, i.e. 1/T S f(x) < c, we use Lemma 9.
25

---

Contextual Bandits for Unbounded Context Distributions
1 / (17 na (x)) (1+1)) (7(x)= 2 c(x), - - f(x) < <c)aa dx
< / (x))
T {x(x) <c) dx
1
= Tul / ( (x)1
T S f(x)) <c) dx
7 7ar E
4+1
f - पাं [x]
T ((x) <c)]
dil T T44
(T= + --
if B 242
(133)
T In(c)
if 3
From (132) and (133),
ThnT (Tc)- 241 + +T ( - T
if B オेद
I
(134)
TlnT (To) at2 + T ato In(TT)
if 8 전..
To minimize (134), let
c= T 0+(
(135)
then
11 T 22
In + T In if 8 742
11 S
(136)
T 2
if B = d+2'
Bound of 12. We still discuss f(x) 2 cand 1/T S f(x) < c separately, For f(x) 2 c.
[ - no (x()))
- nx(x) S c(x), 2 c)dx
T / (1T'(x) (xx - (x))1 (xx(x) na(x) - (Tc) uोअ ) f f(x)dx (Tc)-atz) xtz)
< T(Tc)-ata) ( (x)) - (X) s (Tc)
2 -(Tc)-a1z
(137)
For 1/T S f(x) < c,
- (1)(0)) (1((x)- - (x)xx) S sx(x), - S [xx) < <c) dx
1
S T f (((x))(0)1 (+ s f(x)= < <c) dx
= # ( ( (x)1 - s s(x) < c dx
T (T 8 + )
) if
8 8 442
(138)
T (Tc))
if
3= 842
Similar to J, pick e aaa((a(()+2)))
26

---

Contextual Bandits for Unbounded Context Distributions
Bound of 13. From Assumption 3(b), 1f" (x) "/a (x) < M. Moreover, from Lemma 1.(x)) Tf(() for almost all X.
Hence
( ( (f(x)= +) dx MT s(x) (I(X) < dx TT
[(x) <
(139)
Combine 4, 1e and 1z.
T In T
if 3 1
Ra ~
d+2
(140)
T 2
if 3 ヒ
Theorem can then proved by R = EaEA Ra.
Proof of Lemmas
L1. Proof of Lemma 4 From Assumption 2(c), W; is subgaussian with parameter o², Therefore for any fixed set 7 C (1,..., 7} with |7| k.
E
exp
A
W:
)
S exp
k
x2302
(141)
2
sEI
and
P
W,
> w
s inf e Auy
exp
Σ
W:
k
k
LET
12002
$ inf E
exp
2k
kuz
exp
(142)
20
Now we need to give a union bound Let At dimensional hyperplane that bisects X,, X,. Then the number of planes is at most N, T(T 1)/2. Note that N, planes divide d dimensional space into most N, Eソ (?)) regions. Therefore
N,
d
2
T(T 11)
(1)
s d (TT
2T <dT2d
(143)
j=0
The & nearest neighbors for all within region should be the same. Combining with the action space A, there most
Nr|AA regions. Hence
KM
& 24
(144)
Therefore
Wi > " 1) s 2d Ale k.?
UxEx UnEA
Σ HENi(x.))
(145)
The proof is complete.
TThe construction of hyperplanes follows the proof Lemma (Jiang, 2019) and Appendix H.5 (Zhao & Wan, 2024).
27

---

Contextual Bandits for Unbounded Context Distributions
1.2. Proof of Lemma 5 From (9), with Ki < t|A, - =a 2
(x,c(x)
E
E
Y + b Lxa,t(x)
=
iEN((xxa)
Σ
(x(X))
1
Σ iENi(x.a)
Wi+ (p,,
(146)
k
(ENa(x;a)
Hence
(xx - (Ma(x) + b+ L
K k sEN:(xx.)
Σ (X()) - (x)]+
Σ W
h (x.a)
(x,,((x) + b,
(147)
which comes from Assumption 2(d) and Lemma 4. Lemma then be proved using (147).
I.3. Proof of Lemma
We prove Lemma 6 by contradiction.
(2, a, (x())) k, then let
t == max IX, x|| ST((x), Ar a}
(148)
be the last step falling in B(x, (x()) with action a. Then (xx)) S B(X, 2ra (x)). and thus there are at least k points (X,, (x)). Therefore,
Pa,((x) < (x)
(149)
Denote
a" a"(x) = arg maxia
(150)
as the best action at context x. A, a is selected only if the UCB of action a is not less than the UCB of action a (x), i.e.
Na (X,) 2 (xe,
(151)
From Lemma 5,
(X,) S (a(a( + 26 2X.,),(
(152)
and
(x), 2 (x)()) = 17" (X,).
(153)
From (151), (152) and (153),
Na (X,)) + 2LPa, 2 17" (X,,,
(154)
which yields
(X,) - 1a (X,) 2h
(X.)
2L
17 (x) - (x)
2b (x)
2L
(x..
(155)
in which the last step comes from the definition of r. in (77). Note that (155) contradicts (149). Therefore n(æ, a, (x)) $
The proof of Lemma 6 complete.
28

---

Contextual Bandits for Unbounded Context Distributions
1.4. Proof of Lemma 7
UANAAIL (a(1)()(()) du
B
/ g(z) ga(u)(n" (u) no (u))ddy dz
JaJarns ((a,gra(u)) (())ga(u((()(() (u) - ( (u))ddzz
IV
inf g(Z) ru(w) Ya (a(u)(n"(u) -n dz))d
||
S3
IV
3
d Sx (() (u) - (a(u))du
4
5)
16
3
Mz l (u))(() na (u)) vela
("( ma(u))
)
2h d
(a(u)(r((u) na (u())ddu
6L
M
3
Mz / 1()((n) na(u)) c)
1
1) (T( (7(u)-mu) ma(l)) (T)()) (a(u)(()(u) Ta (u))dd
(n)* (u(ja
12L
3
( J
- (1)) (u)))) -na(u) > c)du.
(156)
5
Based (156), Lemma 7 holds with
5 d
Ci
3 (12L)*.
(157)
Now we explain some key steps in (156).
In (a), the order integration is swapped. Note that u E (2z,ra(z)) then ||u - =|| S ra(z). From Assumption 2(d),
na (u) no (z)l Lra(z). Then from (77),
ra( = 17" (1"(u) - 17 (u) - -2b
6I.
77
na (z) + 2Lrr (z) 2b
6L
1
ra(z) + (ra(24)
4
3 (z).
(158)
thus ||z u|l 3r. 3r.(u)/4 (u)/4 implies ||u =1| S Ta (z). Therefore (a) holds.
For (b) in (156), note that for ||z - u|l < 3r. 3r)(u)/4. using Assumption 2(d) again,
n" (z) (z) (u) (u) 3ra(u) 3ra (u) ni (u) - (na(u) + Lrr(u) (u).
(159)
Then
g(z)
(n) (u)) V vddd
guu)
(177 no (z)) V Veld
[11" (u) nh (u)) V veld
(u) (u) Lra (u)) vc
4
(160)
5
29

---

Contextual Bandits for Unbounded Context Distributions
in which the last step comes from the definition of in (77).
(c) uses (77) and the definition of g in (81).
For (d), recall the statement of Lemma 7, c = 46. Therefore, if nf - na(u) > then r7((w) - na(u)) 2b >
(17( - Tia (2))/2.
L.5. Proof of Lemma 8
E
(n(u)(r(()) na (u))du
(()))a(2))
IV
( (a(u)(11(2) - nd(
E
3
(0)
4.
(A: + 1) 167" (Z) 7o (Z))
(k: 1++11 1) / (z) - -T(z)))
x
4(k + 1)
/ (17(x) - (z)) (1)' - (2)) v cjd² dz
3Mz
4(k (1++1) 1)
[// (1)* (2) (2(2)) (d- 1d (z) - na(2) > c)dz
3M2
+ 1
/
- na
< e)dz
(161)
6d x
For (a), from Assumption 2(d),
17" (u) na (u)
nz(z) (z) + 2Lr (z)
11" (z) - 1/ (z(z) + 21 1/" (z) - 1/a (z) 26
67.
4 3(n (z) - no (z)).
(162)
(b) comes from (80).
The first term in the bracket in (161) can be bounded by
/ (z) - na (z))))(((11))) 177 - (z) > e)dz
(dd))
/ (1)(2) - na (2)) (d 1) (2) - na(2) > e)f(z)dz
C .x
E (17 n (X)) (d-1)) (17 (X) (X) > s)
P(e < <x)(() - (X) < < dd
(d-1)
P() (X) < t )dl.
(163)
(a) comes from Assumption 2, which requires that f(x) 2 c all over the support. In (b), the random variable X follows a distribution with pdf f.
If d > a + then from Assumption 2(b),
Co (1--)) f
(163) < c 0
Edid
Ca(d-1)
-
a+l-d
(164)
cld a)
30

---

Contextual Bandits for Unbounded Context Distributions
If = then
(163) - c [ dt + Co c (d-1)
fr I - Cold-1 1)
In
(165)
c
If < + then
- . dt Ca (
a 1 Ca(d-1)
(163)
(166)
c
ca d)
Now remains to bound the second term (161):
J (nj (z) (a()))1(1"(2) - (z))) < c)dz
v (x())))) - nx(X) < <c]
Ca ct!
(167)
Therefore, from (161), (164), (165), (166) and (167),
eattld
if d d>a+1
I (2)) (n( (u) - na du))duu
Mzc
Mze In a if d<atl.
(168)
Mze
I.6. Proof Lemma 12
We prove Lemma 12 by contradiction. Suppose now that n(x, n(I,a,ra(x))) > nx(x). Let be the last sample falling in (xx, (x)),, i.e.
t max Xi x|1 S ra (x) =a}
(169)
We first show that (x) S 2ra (x). From (169) and the condition n(xx, a, To (x)) > nx(x), before time step 4, there are already at least na(x steps in B(x, ra (x)). Note that || x|| I (x),,, thus B(x, rx()) C B(,, 2r 2 (x)). Therefore, there are already at least (x) samples with action a in B BX, 2r (x)). Recall that Pa,t (x) (x) (x). Px,(x) > (x), then (x)) (x)).. From (16),
IT (x) (x) S kx,)(x)
In
(xra(xx,
(170)
V
na(x)
then contradiction occurs. Therefore px,(()= < (xx()).
From Lemma 11, under E,
202 In(dT2a+3]A)) + (x).
(x) S na(x)) + 2/ na(x)
(171)
Since action is selected at time f, from Lemma 11,
(x)) 2 na (x) (x).
2
(172)
Combining (171) and (172) yields
20² In(dTad+([A) + 2Ira(x) 2 17" 1x()x) (x)).)
V (x()
(173)
We now derive an inequality that contradicts with (173). From (112) and (113),
202
20²
2/ (x))
In(dT2d+([A))
2/
Ci T In(d22d+3 (A)(1' (x) (x)))
1
In(d72d+3 (A)
< 2
(2d + - (() In (17 - (x)))
1
(17 (x) na (x)).
(174)
2
31

---

Contextual Bandits for Unbounded Context Distributions
From (111),
1
1 (1(((x - (x)).)) (x)(x) [a(x)) S
2xxa(x)
(175)
VC1
From (174) and (175),
2
2
In(dI2a+([A) + 2Lra(x) <x)((x (x).
(176)
na
(176) contradicts (173). Hence
n(x,a,r,xx)) n,(x))
(177)
L7. Proof of Lemma 13
J ( (u(u)(n(u) (u))du (Z))).(Z))
E
S J.Juwartt g(z)ga(u)()) (u) na (u))
(22) ( (w)r(i - na (u))duu
WV
inf
Jx
|| 52r
W3
2
3
(w)) (u) (u(u)duu
3
4
fx 1( nu) ed) ((())a(u)(()"() (u) na (u))duu
1
Md
1
/ (())(u) (u) (7 (u) na (u))d
1
(1) (u) na (u))
(4L)a qo (n) (u) na (u))dd
Mz
Ld / ( (u) (u e)du.
nh
(178)
For (a), if ||u - 2|1 s Ta (z). then from the definition of ra in (111).
(u) (u) Ta (u)
s (2)) Na (2(2)
2 (z)
S
(179)
Na (z) (z) 7a (z)
(z) - 7a (z)
VCI
For (b),
g(z)
(1*(1) (u)) v
g(u)
(77 (z) (z)) V Veld
(11" (u) na (u)) vej
(1) (u) g (Lrr(w)) vc
3
(180)
4
32

---

Contextual Bandits for Unbounded Context Distributions
I.8. Proof of Lemma 14
J I (a(u)(r((u) na du
E
(2))
Wn
3
Verennze (a())(1(()) maa
2
3
<
E [[(no())+]))) +1))++++))((((())))0((( (Z) No (Z(2))]
2
3
/ (mna(z)+ + (1 (a(z))) M2((1( - 17 (z)) V eje vja d2
1
2
3
// (() +z)
( -no(z)) (n)(z) 17 (z))))
CihnT
(1) -a((z) > e)dz
(x)z)
2M,
+
TT())) na (z)) 111 (z) -a(2)) S c)dz
E
[1'' na (z) (11 (Z) - (Z( > o) lnT
Mz
T
+
E ((7((z) - na( (z) (Z) (1) (Z) (Z) sd]
ed
( I + Tt).
(181)
Mz
For (a),
("((u (u)
< (1(2) - na(2) + 2Lra(z)
1
S (z) (z))) + vC (1((1) na (2)))
3 (z) - (na
s 2
(182)
1.9. Proof of Lemma 9
[ P((()) < < b)dt
0
(X) S(X) <b) =
Io" P(f(X) < <
S J P(f(X) +
< Cabs- CCp ( 3dd
-P
(183)
6-P
p > B,i.e. 8/p < then
(183) S C2b3-P+
C3
(a 1)- 1 (00))--~a0 8-P
(184)
1- 3/p
p < B, then
(183) < Cob PCC
J
000
t t Caba- +
B/p -
C3
3 p ~ 8-P
(185)
If p = 3, then
(183) < Czb x + Cg In p
~ In
(186)
b-
33

---

Contextual Bandits for Unbounded Context Distributions
1.10. Proof of Lemma Our proof follows the proof of Lemma 3.1 in (Rigollet & Zeevi, 2010).
T
U (1) (X.) 71, (X.)),
Σ
(187)
and
T
V = Σ (x)
(188)
Then R = [R(U and S = =. For any 8> 0,
U
2 8
1AA (3)
(x)()))>>> 6)
t=1
8 V
1 (A: a'x,) (X,)) 50)
(189)
Take expectations, we have
R 2 65 - -C
(190)
Now minimize the right hand side of (190). By making the derivative be zero, let
+/
S
8 (a+1)TC 1)TCa
(191)
Then
S (a+ 1)TC,
R 2 S
(a+ (Ta+IITC.
TCa
as
S
a+1
1ITC
CoS 21l T =
(192)
The proof is complete.
34


Reviews:
[{"review_id": "kXJcoxwVgJ", "reviewer": "Reviewer_syqz", "summary": "The paper studies the setting of contextual bandits for unbounded context set. The paper then proposed an idea of algorithm design based on k-nearest neighbor, with a special design of the optimism term. With an adaptive choice of $k$, the algorithm achieves the minimal-optimal regret.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for acknowledging the writing of this paper. We respond to questions and weaknesses as follows.\n\n**1. Importance of unbounded context distribution**\n\nThe bounded action space can be easily generalized to unbounded action space (assuming continuous action space). Unbounded action space does not involve too much additional technical difficulties.\n\nHowever, generalizing bounded context distribution to unbounded one is significantly different. We strongly agree with your comment **\" I think the setting of unbounded context set would be of special importance either if the bounded setting and the unbounded setting are fundamentally different by some obvious intuitions, or if the practical results of unbounded context set departs too much from the theory about bounded context set.\"** We think that these two reasons both hold. \n\n**(1) Fundamental difference by intuition.** In bounded context space, we only need to achieve a tradeoff between exploration and exploitation. However, with unbounded context space, since the sample density is crucially different in different regions, we need to also achieve a better tradeoff between bias and variance. As emphasized in the abstract and introduction, the challenge is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. This problem does not exist for bounded context space.\n\n**(2) Difference in practical results.** We refer to Theorem 6. The bounded context case corresponds to Theorem 6 with $\\beta \\rightarrow \\infty$, which yields a $O(T^{1-\\frac{\\alpha+1}{d+2}})$ regret. As long as $\\beta$ is not infinite, the regret bound is clearly different from the bounded context case. In particular, with $\\beta<1/(d+2)$, the difference is more significant as the main cause of regret comes from the tail, instead of exploration.\n\n\n**2. Whether the size of action set is treated as constant**\n\nIt is common to treat size of action set in related works. See the following results as examples:\n\nShah, Devavrat, and Qiaomin Xie. \"Q-learning with nearest neighbors.\" Advances in Neural Information Processing Systems 31 (2018).\n\nZhao, Puning, and Lifeng Lai. \"Minimax optimal q learning with nearest neighbors.\" IEEE Transactions on Information Theory (2024).\n\n**3. Interpretation of phase transition in Theorem 3**\n\nAs discussed in the response of weaknesses 1, in unbounded state space, we need to achieve both exploration-exploitation tradeoff and bias-variance tradeoff. Fixed $k$ method fails to achieve the latter one, as in heavy-tailed contexts, bias-variance tradeoff is more complicated and smaller $k$ may be necessary. \n\n**This result further explains the importance of studying unbounded context supports.** At first glance, one may think that it is simple to generalize fixed k method to unbounded context, but our analysis show that such method is no longer optimal. We need to find new method to achieve minimax optimal regret.", "claims_and_evidence": "All claims are well supported by evidence.", "methods_and_evaluation_criteria": "The proposed methods are solid.", "theoretical_claims": "I did not check the proof.", "experimental_designs_or_analyses": "I checked the experiment, which is well-designed.", "relation_to_broader_scientific_literature": "This work is closely related to the literature studying nonparametric contextual bandits and using nearest neighbors (especially Guan and Jiang 2018), which is discussed in great detail in Section 2. The idea of using an adaptive $k$ is a new idea.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. This paper is well written, with sufficient discussions on assumptions and main theorems.\n\nWeaknesses:\n1. My major concern is whether unbounded context distribution is an important objective to study. In our works about contextual bandits, the assumption of bounded **action space** is often made, but the theoretical results usually apply to the practical settings where the action space is unbounded. I think the setting of unbounded context set would be of special importance either if the bounded setting and the unbounded setting are fundamentally different by some obvious intuitions, or if the practical results of unbounded context set departs too much from the theory about bounded context set. I would raise my score if this question is well addressed by the authors.\n2. It is questionable whether the size of the action set, which is the major gap between the lower bound and the upper bound in Theorem 6, can be treated as a constant.", "other_comments_or_suggestions": "In the discussion after Theorem 6, the case where $\\beta$ goes to infinity reduces to Theorem 5 is interesting. It looks like the same relationship holds for Theorem 4 and Theorem 3.", "questions_for_authors": "1. How can we interpret the phase transition around $\\alpha=d+1$ in Theorem 3?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QShv3Rhbc4", "reviewer": "Reviewer_c4Ni", "summary": "In this paper, the authors study contextual bandit problems under the Tsybakov margin condition. They consider settings where the context distribution is either bounded or unbounded but heavy-tailed. Compared to the literature, they work under a weaker version of the Tsybakov margin condition, allowing them to establish a stronger lower bound. They propose an approach equipped with $k$-nearest neighbor methods and UCB exploration. By incorporating an adaptable $k$ in the nearest neighbor methods, they show that their algorithm achieves a regret upper bound that matches their strengthened lower bound up to logarithmic factors under both the bounded and heavy-tailed context assumptions. Finally, experiments on both synthesized and real data are presented to demonstrate the practical performance of their algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review. We are encouraged that you agree that our claims are all clear and proved.\n\nRegarding the novelty of algorithm. **We disagree that \"the authors merely restate how the parameter $k$ is chosen\"**. For our adaptive method, we select $k$ according to eq.(16). For Reeve et al. (2018), $k$ is selected in Algorithm 1, in particular, in step 2(b). The UCB is defined in the page before Algorithm 1, with $\\phi(t)$ not fully determined. As can be observed from our paper and Reeve et al.'s paper, the selection rule is quite different: we select $k$ as the maximum one that satisfies $L\\rho_{a,t,j}(x)\\leq \\sqrt{\\ln T/j}$, while Reeve et al.'s paper select $k$ by minimizing a new defined UCB. The UCB calculations are also different: we calculate UCB in eq.(17) in our paper, which is also different from Reeve et al.'s paper, in the equation before Algorithm 1.\n\nHowever, we do think that the question (about anything that prevents the algorithm in Reeve et al. from being used in unbounded context) raised by the reviewer is very valuable. Actually, if we only consider implementation, without considering the theoretical bounds, then the algorithm can indeed be applied into unbounded contexts. However, the convergence rate is not analyzed right now, and we believe that it will be much more complex than our method. It is unknown whether the method proposed in Reeve et al. will match the lower bound. **Therefore, to the best of our knowledge, our work is still the first one to establish the minimax lower bound of contextual bandits with unbounded contexts, and provide algorithms with matching upper bounds.**\n\nIn addition, although less important, we would like to mention that our selection of $k$ requires $O(\\ln T)$ time, while Reeve et al's method requires $O(T)$ time. Therefore we also have advantages in time complexity.", "claims_and_evidence": "All the claims are clear and proved.", "methods_and_evaluation_criteria": "They achieve minimax regret bounds.", "theoretical_claims": "All the claims are clear and proved.", "experimental_designs_or_analyses": "They apply their algorithm to both synthesized and real data.", "relation_to_broader_scientific_literature": "They extended previous approach", "essential_references_not_discussed": "They have cited all relevant papers to my knowledge.", "other_strengths_and_weaknesses": "The main weakness of the paper is that the algorithm itself may not be a novel contribution. Throughout the paper, the authors compare their work only with Guan & Jiang (2018) but do not compare it with Reeve et al. (2018). However, I do not see a clear difference between the method proposed in this paper and the approach taken by Reeve et al. (2018) in the bounded context setting. It seems to me that the authors merely restate how the parameter $k$ is chosen. Additionally, the generalization to the unbounded but heavy-tailed distribution appears to be a natural extension that incorporates the tail bounds from the previous analysis. Thus, I am somewhat concerned about the technical contribution of the paper. It would be helpful to highlight the technical challenges or obstacles involved in extending the approach to the unbounded setting.", "other_comments_or_suggestions": "See strengths and weaknesses", "questions_for_authors": "- Is there anything prevents the algorithm proposed by Reeve et al. (2018) from being applied to this setting of unbounded context?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZpmTOY5cXW", "reviewer": "Reviewer_nDm2", "summary": "Contextual bandit is important in recommendation systems, healthcare, etc. Existing works focus primarily on linear bandits (or other parametric bandits). While some papers study nonparametric bandits, they assume that the support is bounded. In this work, the authors study nonparametric contextual bandit with unbounded context support. The paper proposes two methods: fixed k and adaptive k. For the latter approach, k is adaptively selected to balance the bound of bias and variance. According to the theoretical analysis, the fixed k method achieves minimax optimal rate under some parameter regimes. The adaptive k method achieves minimax optimal rate for all regimes.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback on the importance and novelty of this paper. We reply to questions as follows.\n\n1. $C_\\alpha$ is a constant. In eq.(38), $K$ has $h^{d-\\alpha}$ dependence. Throughout the paper, $C_\\alpha$ remains a constant.\n\n2. Thanks for the suggestion. We think that **all our results hold for intrinsic dimension $d$**. This means that even though the overall dimensionality is significantly larger than $d$, the result in all theorems in the paper still hold.\n\nIn our revised paper, we will polish the proof further and provide more necessary intuition and explanation.", "claims_and_evidence": "I think that the claims are clear. The authors provide sufficient theoretical analysis to validate their claims.", "methods_and_evaluation_criteria": "The proposed methods and evaluation make sense for the problem at hand. This paper discusses nonparametric bandits, therefore knn method is natural. The problem is how to determine the UCB, as well as the selection of k. I think that the authors did a great job in figuring out a proper way, such that k is selected adaptively based on the bias and variance bounds. Based on my understanding, I think that the proposed method makes sense.", "theoretical_claims": "The proofs of all theoretical claims are shown in the Appendix. I have briefly reviewed the proofs. It seems that the proof is correct. \n\nA concern is that I do not fully understand why Lemma 3 can not be used in the proof of lower bound for unbounded case. My intuition is that Lemma 3 is quite general. So I am not sure why Lemma 3 can not be directly used to get the lower bound of regret with unbounded support.", "experimental_designs_or_analyses": "The experiments in this paper mainly use synthesized data. I think that for evaluating nonparametric statistics, it is reasonable to use synthesized data, for the convenience of analysis. In general, I think that the the experiments are sound enough.", "relation_to_broader_scientific_literature": "There are some scientific literatures on nonparametric contextual bandits. Previous works focus primarily on bounded context supports. This paper solves the problem of unbounded context supports. I think that this paper is an important extension to previous works.", "essential_references_not_discussed": "This paper has all essential references.", "other_strengths_and_weaknesses": "[Strengths]\n\n1. Importance: This paper addresses an important problem. Existing analysis on contextual bandits focus on bounded support. However, unbounded supports are more common in practice. \n\n2. Novelty: The adaptive method is novel. It achieves two tradeoffs simultaneously: exploration-exploitation tradeoff and bias-variance tradeoff.\n\n[Weaknesses]\n\nSome points in the proof are not clear to me. $C_\\alpha$ is considered to be constant in eq.(50). However, In eq.(38), it seems that C_\\alpha has a dependence $h^{d-\\alpha}$. \n\nMoreover, it would be interesting to consider the case if contexts lie in a manifold. While bandit algorithms can not overcome curse of dimensionality in general, if the contexts have low intrinsic dimensionality, then the regret may still be controlled even if the overall dimensionality is high. Hope that authors can provide some ideas.", "other_comments_or_suggestions": "In general, I think that this paper is well written. However, I think that the proof needs to be polished, and more intuition need to be provided. Hope that authors can respond to my concerns raised above. I will consider improving my score if authors provide a good response.", "questions_for_authors": "See weakness", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HmEyEs5qol", "reviewer": "Reviewer_DUvP", "summary": "Stochastic contextual bandits, where there is a set of K actions, and at each round $t$ the learner observes the current context $X_t$ generated from the fixed distribution. This paper considers the nonparametric setting with the standard assumption of zero-mean noise and Lipsthiz reward function. The authors investigate the min-max lower bound for unbounded supports by extending the result of (Rigollet & Zeevi, 2010).\nThen, as a simple method, they proposed the k-NN UCB with fixed k and analyzed both cases of bounded and unbounded support. \nThey further devised the k-NN UCB with adaptive k to improve the regret bound matching the lower bound up to log factors. Experimental evidence was provided using the synthetic setting and MNIST dataset.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks the reviewer for your careful reading of this paper!\n\nWe respond to your comments as follows.\n\n1. We have read the paper you have mentioned: Self-Tuning Bandits over Unknown Covariate-Shifts. In ICALT. We think that this paper is indeed highly relevant, so we will compare it with our paper in our revised version.\n\n2. Assumption 1(a): here $X$ is a random variable, instead of a fixed value. The randomness in probability $P(0<\\eta^*(X)-\\eta_a(X)<u)$ also comes from the randomness in X,  Therefore, we do not need \"for all x\\in \\mathcal{X}\".\n\n3. Assumption 1(b)：Thanks for these two comments. $W_i$ should be $W_t$, and $\\lambda \\in \\mathbb{R}$ needs to be mentioned.\n\n4. Line 158: $c$ is some constant. We will clarify it.\n\n5. Line 296 right: Yes, $x$ should be bold\n\n6. Line 259 right: This notation comes from Guan et al. 2018. We will clarify the meaning of this notation.\n\n7. Remark 2: $N$ is the number of samples for nonparametric classification with i.i.d samples. We will clarify it.\n\n8. (92): Yes, it should be $T^{2d+2}$, instead of $T(2d+2)$.\n\n9. Lemma 5,6 and 12: Thanks. We will clarify them.\n\n**Question 1: About assumption 3(b)**\n\nThis is not common in previous literatures, since existing works only discuss bounded context support. We think you have raised a very good question. It is indeed a bit counterintuitive that we need small suboptimal gap $\\Delta_a$. For unbounded context support, there exists some region with very low density $f(\\mathbf{x})$, such that even if the suboptimal gap is large, we still can not identify the optimal action. Therefore, noting that the regret is upper bounded by the suboptimal gap, instead of trying to identify the optimal action, now we give an upper bound of the suboptimal gap, so that the regret (with unidentified optimal action) can be controlled. This is an important distinction between bounded and unbounded context support. For bounded support, since the density is lower bounded (Assumption 2: $f(\\mathbf{x})\\geq c$), we hope that suboptimal gap is as large as possible. However, for unbounded case, things become more complex and large suboptimal gap does not always make the problem easier.\n\n**Question2: Novelty**\n\nThe main novelty is the treatment of tails. The proof of theorem 2 is novel, as it requires treatment of heavy tails.\n\nIn Appendix B, the \"expected sample density\" has not been proposed by existing analysis.\n\nLemma 5,6,7,8 and Appendix E are entirely new. \n\nWe guess that some lemmas (such as Lemma 4) appears to be similar to existing works, which leaves an impression that the proof is simple and standard. However, these lemmas are tools that are required for the completeness of analysis. For all other parts of our theoretical analysis, different techniques are used. \n\nThe main technical challenge is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff. In bounded context space, one only needs to achieve the former one.", "claims_and_evidence": "Strength\n- Theorem 3 ( k-NN UCB with fixed k for bounded support)\nrecovers the result of (Guan & Jiang, 2018) when $\\alpha=0$  and improve the result when $\\alpha>0$.\n- Theorem  5 ( k-NN UCB with adaptive  k for bounded support) is nearly optimal in both regimes with $d > \\alpha+1$ or $d \\leq \\alpha+1$\n- Theorem  4 ( k-NN UCB with fixed k for unbounded support) and Theorem  6 ( k-NN UCB with adaptive k for unbounded support) are the novel results for unbounded support.", "methods_and_evaluation_criteria": "k-NN UCB is a simple and general method to deal with contextual bandits in non-parametric case. The main proposed method with adaptive choice of k is still simple but it is reasonable to deal with variance-bias trade-off adaptively.", "theoretical_claims": "The following are minor concerns, and I appreciate any feedback in rebuttal:\n\n- More discussion of Theorem 4, e.g., comparison with Theorem 3 could be added in the revised version.\n- The lower bound analysis does not capture the dependence of $|\\mathcal{A}|$, although existing work only discusses the case of two actions. The regret bounds depend on the linear dependence of $|\\mathcal{A}|$, which encourages us to investigate the optimality of the number of actions.\n- (Just a comment) Proof Sketch of Theorem 2 is a higher-level idea and could be more detailed.", "experimental_designs_or_analyses": "Experimental evidence was provided using the synthetic setting with two actions and subgaussian context distribution and real-world dataset where MNIST figure corresponds to the context and there are 10 actions.", "relation_to_broader_scientific_literature": "The heavy-tailed context distribution in nonparametric contextual bandits was discussed in the paper.", "essential_references_not_discussed": "The following paper could be cited in the revised version.\n\n\nSUK, J. and KPOTUFE, S. (2021). Self-Tuning Bandits over Unknown Covariate-Shifts. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory", "other_strengths_and_weaknesses": "Writing Quality:\n\nAlthough critical issues have not been found, the writing quality is not the best. Some definitions are missing, and there are typos.\n\n- (just a comment): p.1 right 053: Instead of “simple method”, you could specify that the method is a $k$-NN.\n- Assumption 1 (a), you need “for all $X \\in \\mathcal{X}$”\n- Assumption 1 (b), you need “for all $\\lambda  \\in \\mathbb{R}$”\n- Assumption 1 (b), what is $W_i$? It should be $W_t$.\n- p.3. line 135, you are mixing $t$ and $u$; $t$ is undefined, I guess you want to use $\\forall u>0$ here.\n- line 158 right: $c$ is undefined.\n- line 296 right: $x$ should be bold.\n- Ling 259 right: $T_a(t-1)$ is undefined. I guess you mean $n_a(t-1)$.\n- In (16): $k_t(x)$ depends on action $a$. It should be $k_{a,t}(x)$.\n- In Remark 2: $N$ is undefined.\n- In (92): you have a typo.\n- In Lemmas 5,6, and 12: You need to specify or refer to the definition of event $E$.", "other_comments_or_suggestions": "See Other Strengths And Weaknesses", "questions_for_authors": "1. Is Assumption 3(b) common in the literature for unbounded support in contextual bandits?\nWhen the suboptimal gap $\\Delta_\\min$ or $\\Delta_a$ is large, the problem becomes easier to identify the optimal action as the regret bound usually depends on $1/\\Delta$. But it seems that we need the opposite condition.\n\n\n2. The reviewer is not familiar with non-parametric bandits, but I found that the proof techniques are very simple and standard as used in UCB algorithms. What is the main technical challenge compared with standard linear contextual bandits? Since here the Lipshitz reward function is only considered, the proof technique is essentially similar to the case of the linear reward function. When we deal with heavy-tailed distribution, which lemmas are novel and crucial in the analysis of non-parametric bandits?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: This paper studies the nonparametric bandit problem with a specific focus on unbounded contexts. The setting of unbounded contexts turns out to be fundamentally different from the bounded ones because 1) unbounded contexts involve an additional bias-variance tradeoff on top of the exploration-exploitation tradeoff; 2) the resulting regret bounds are very different and could be dominated by the tail strength of the context distribution. This paper establishes the tight upper (based on k-NN algorithms) and lower bounds (up to log factors) for this problem. 

All reviewers unanimously appreciate this paper: it studies a clear problem, proposes a sound algorithm, and establishes matching upper and lower bounds. The main concern is on the additional algorithmic and analytical novelty compared to the existing work on bounded contexts. Based on my own reading and the authors' rebuttal, the reviewers think the merits outweigh the weaknesses, which I concur and recommend (weak) acceptance.
Decision: Accept (poster)