Batched Nonparametric Bandits via k-Nearest Neighbor UCB
Authors: Sakshi Arya
Venue: Accepted by TMLR ()

Abstract: We study sequential decision-making in batched nonparametric contextual bandits, where actions are selected over a finite horizon divided into a small number of batches. Motivated by constraints in domains such as medicine and marketing, where online feedback is limited, we propose a nonparametric algorithm that combines adaptive k-nearest neighbor (k-NN) regression with the upper confidence bound (UCB) principle. Our method, BaNk-UCB, is fully nonparametric, adapts to the context density, and is simple to implement. Unlike prior works relying on parametric or binning-based estimators, BaNk-UCB uses local geometry of the contexts to estimate rewards and adaptively balances exploration and exploitation. We provide near-optimal regret guarantees under standard Lipschitz smoothness and margin assumptions, using a theoretically motivated batch schedule that balances regret across batches and achieves minimax-optimal rates. Empirical evaluations on synthetic and real-world datasets demonstrate that BaNk-UCB consistently outperforms binning-based baselines.

Published in Transactions on Machine Learning Research (11/2025)
Batched Nonparametric Bandits via k-Nearest Neighbor UCB
Sakshi Arya Deportment of Mothematics, Applied Mathematics, and Statistics
sza 1351 Cease..cce...m edu
Case Western Reserve University
Reviewed on OpenReview: /tpp:://openrevveee net/ forum? id= 1d=9gB2Eu0PXt
Abstract
We study sequential decision-making in batched nonparametric contextual bandits, where actions selected over finite horizon divided into a small number of batches. Motivated by constraints in domains such medicine and marketing, where online feedback is limited, we propose a nonparametric algorithm that combines adaptive k-nearest neighbor (k-NN) regression with the upper confidence bound (UCB) principle. Our method, BaNk-UCB, is fully nonparametric, adapts to the context density, and is simple to implement. Unlike prior works relying on parametric or binning- based estimators, BaNk-UCB uses local geometry of the contexts to estimate rewards and adaptively balances exploration and exploitation. We provide near-optimal regret guarantees under standard Lipschitz smoothness and margin assumptions, using a theoretically motivated batch schedule that balances regret across batches and achieves minimax-optimg rates. Empirical evaluations on synthetic and real- world datasets demonstrate that BaNk-UCB consistently outperforms binning-baser baselines.
1 Introduction
Many real-world decision-making problems involve using feedback from past interactions to improve future outcomes, a hallmark of adaptive sequential learning. Contextual bandits are a standard framework for modeling these problems, especially in personalized decision-making, where side information helps tailor actions to individuals (Teaari & Murphy 2017 Li et al. 2010). In this framework, learner observes context, selects an action, and receives a reward, aiming to maximize cunulative reward over time through adaptive policy updates.
However, in many practical applications such as clinical trials (Kim et al. 2011 Lai et al. 1983) and marketing campaigns (Schwartz et al. 2017 Mao et al., 2018), adaptivity is limited due to logistical or cost constraints. Decisions are made batches, and feedback is only received the end of each batch. This structure permits limited adaptation and renders traditional online bandit algorithms ineffective, motivating new methods tailored for low-adaptivity regimes with few batches.
While parametric bandits have been extended to the batched setting, they often rely on strong modeling
assumptions. Nonparametric models offer greater flexibility and robustness (Rigollet & Zeevi 2010 Qian &
Yang 2016 Reeve et al. 2018a Zhou et al. 2020), but their use in batched bandits remains limited. Existing nouparametric batched bandit methods, such as BaSEDB (Jiang & Ma. 2025), rely on partitioning the context space into bins and treating each bin as a local static bandit instance. While maming-basoo approaches are effective under structured or uniformly distributed contexts, they rely on fixed spatial partitions that may not adapt well to local variations in context density geometry. In particular, low-density regions may receive few samples, leading to poor reward estimation and imbalanced exploration across the space. These limitations highlight the need for methods that adapt to the local geometry and data distribution, rather than imposing a fixed spatial discretization, especially in a data-limited setting such as that of batched bandits. To address this gap, we propose Batched Nonparametric k-nearest neighbor-Upper Confidence Bound (BaNk-UCB), nonparametric algorithm for batched contextual bandits that combines adaptive k-ncarest. neighbor regression with UCB-based exploration. BaNk-UCB adapts neighborhood radii local data density, eliminating the need for manual bin design. Our method adapts neighborhood sizes based the observed

---

Published in Transactions on Machine Learning Research (11/2025)
data distribution, allowing for more flexible and data-driven reward estimation, particularly useful in high- dimensional or heterogeneous settings, even when the global context density is uniformly lower bounded. Under Lipschitz continuity and margin conditions, we prove minimax-optimal regret rates up to logarithmic factors. Empirical results on syuthetic and real data show consistent improvements over binning-basee methods. Our main contributions are:
We propose BaNk-UCB, a novel nonparametric algorithm for batched contextual bandits that integrates adaptive k-nearest neighbor (k-NN) regression with upper confidence bound (UCB) exploration. The method is simple to implement and avoids biases introduced by coarse partitioning of the context space.
We design a theoretically grounded batch schedule and establish minimaz-oplimal regret bound under standard Lipschitz smoothness and margin conditions. This is, to our knowledge, the first such result for a k-NN-based reward function estimation method in the batched non-parametric setting.
We highlight how BaNk-UCB automatically adapts to the local geometry of the context distribution without requiring explicit modeling assumption, due to the adaptive neighborhood choice in k-NN regression.
We demonstrate through extensive experiments on both synthetic and real-world datasets that BaNk-UCB consistently outperforms binning-ban based basclines, particularly in high-dimensional or heterogeneous contexts.
1.1 Related Work
Batched contextual bandits have received growing attention due to their relevance in settings with limited adaptivity, such as clinical trials and campaign-base based interventions (Perchet
2016 Gao et al.] 2019
Prior work has explored both non-contextual bandits with fixed or adaptive batch schedules (Esfandiari et al.,
2021 Kalkanli & Ozgur 2021 Jin et al. 2021), and contextual bandits, often under parametric assumptions. In particular, linear (Han et al. 2020) and generalized linear models (Ren et al. 2022 have been popular due to their analytical tractability, though such models may fail to generalize when the reward function is nonlinear or misspecified.
Nonparametric bandits have been extensively studied in the fully sequential setting. Early work by Yang & Zhu (2002) employed e-greedy strategies with nonparametrie reward estimation. Subsequent methods include
the Adaptively Binned Successive Flimination (ABSE) algorithm (Rigollet & Zeevi 2010 Perchet & Rigollet,
2013 which partitions the context space adaptively and uses olimination-basee
strategies (Even-Dar et al. Hu et al. 2020), nearest
2006 Other approaches include kernel regression methods (Qian & Yang 2016
neighbor algorithms (Reeve et al.
2018a Guan & Jiang 2018 Zhao et al. 2024]. : and Gaussian process or
kernelized modols (Krause & Ong 2011 Valko et al. 2013 Arya & Sriperumbudur 2023)
In the batched nonparametric setting, Jiang& & Ma (2025) introduced BaSEDB, a batched variant of ABSE with
dynamic binning and minimax-optimal regret guarantees. Other recent directions include neural network- based estimators (Gu et al.] 2024), Lipschitz-connstranned models (Feng et al., (0022), and semi-parametin frameworks (Arya & Song 2025). though each makes different structural assumptions.
Our work departs from these approaches by employing adaptive k-nearest neighbor regression to estimate both reward functions and confidence bounds under batch constraints. Unlike binning-base methods which bin the context space into bins of equal width at each batch, BaNk-UCB avoids discretization and instead adapts to the local geometry of the context distribution through data-driven neighborhood selection. To our knowledge, this is the first batched nonparametric algorithm based on locally adaptive method like K-NN to achieve near-optimal regret guarantees. Empirically, we show that BaNk-UCB outperforms the baseline BaSEDB across different scenarios, leveraging the well-known ability of K-NN to adapt to local geometry of the context space [Kpotufe] 2011).
Our algorithm adapts ideas from the adaptive A-NN UCB framework of Zhao et al. 2024), originally designed for online contexl ual bandits, to the batched setting with delayed leedback, where actions for an entire batch are chosen before any rewards are observed. While both methods use data-dependent k-NN regression for reward estimation and confidence bounds, our estimator is batch-aware and tailored this restricted feedback regime. In particular, our confidence intervals, selection rule, and regret analysis are shaped by the batch structure. We also develop new technical lemmas that clarify and extend key steps from Zhao et. al.
2

---

Published in Transactions on Machine Learning Research (11/2025)
2024 to handle delayed, batch-specific updates, which crucial for establishing uniform higb-probability guarantees and minimax-optimal regret bounds.
2 Setup
We consider batched contextual bandit problem over finite time horizon T, where decisions are grouped into M batches to reflect limited adaptivity. At each round & E {I...., I") context Xx E X' C. R is observed, and the learner selects an action at EA= (1,..., K}. receives a noisy reward:
The learner selects an action O₃ E A based on X, and
Y, = fx,( + ct,
(1)
where fa) is an unknown mean reward function for a E A and x E X. The model noise is given by q. We make the following assumptions on the noise and context space.
Assumption 1 Suub-Gaussian noise). We assume that the noise terms { are independent and 0² sub- Gaussian; that is, for all E R and all t,
E [eecrc] S e2200²
(2)
Assumption 2 (Bounded context density). The contert vectors X, are drawn i.i.d. from a distribution with density px, which is supported on X C RR. We assume that px (x(x)) 2 & for some g > O.
Unlike many existing nonparametric bandit algorithms, such as ABSE (Perchet & Rigollet, 2013 and its batched variant BaSEDB (Jiang & Ma 2025), which rely on uniform binning of the context space (typically , our proposed method accommodates arbilrary bounded domains X C Rdd with densities bounded away from zero. For instance, X' may be spherical or manifold-shaped domain where uniform partitioning is either ill-defined or computationally inefficient. In contrast to binning- based methods that depend on rigid geometric structure to define partitions and control coverage, our k-NN based approach naturally adapts to the local data geometry, climinating the need for explicit grid design and enabling applicability to more general, heterogeneous settings. This adaptivity particularly crucial in data-limited regimes such as batched bandits, where learning can only occur al a small number decision points.
assuming hypercube domain such 1)),,
A policy Ne X + A for = 1...., T determines an action a E A at Based on the chosen action a; reward Y, is obtained. In the sequential setling without batch constraints, the policy can depend on all the observations (X,, Y,) for < t. In contrast, in a batched setting with M batches, where 0 0=6 to < f1 < ... < tM-1 < tM = T, for & [ts, 11),,, the policy Te can depend on observations from the previous batches, but not on any observations within the same batch. In other words, policy updates can occur only at the predetermined batch boundaries IM...., This reflects the constraint that feedback is only revealed at the end of each batch.
Let = (fo.t1..... }ar} represent a partition of time f0, I,...,T) T) into M intervals, and π (m.). be the sequence of policies applied at each time step. We define the cumulative regret of policy as:
T (T) = -Ex()))(1aaa)) t=1
where f.(z) max.EA fa( is the expected reward from the optimal choice of arms given context The expected cumulative regret, denoted by (T) = E[]r(T)], averages over the randomness in (X,, 0z) under the policy æ. We focus on designing batched policies that minimize Rr(m). The cumulative regret serves as a pivotal metric, quantifying the difference between the cumulative reward attained by л and that achieved by an optimal policy, assuming perfect foreknowledge of the optimal action at each time step.
We make the following assumptions on the reward functions.
Assumption 3 (Lipschitz Smoothness). We assume that the link function Sa Rdd R for each arm is Lipschitz smooth, that is, there erists L > O such that for E A,
(f(()) fa(x') < TAIl x'||.
holds for x, x. E X.
3

---

Published in Transactions on Machine Learning Research (11/2025)
Assumption 4 (Margin). For some 0 < a S d and for all A, there caists do E (0.1) and Da > 0 such that
- Px < - 50) D00"
holds for all E 6o]
For K = 2, our margin condition reduces exactly to that of Rigollet & Zeevi 2010p, which bounds the probability mass where the two arms are nearly indistinguishable. For K > 2, we extend this condition to hold for each suboptimal arm relative to the best arm. The margin condition implies that the regions where the reward gap small, i.e. where it is hard to distinguish the best arm are not too large. The exponent a controls the rate at which the mcasure of such regions shrinks 8 - O. When is small, suboptimal arms can be frequently indistinguishable from the best arm, leading to slower learning; larger implies faster decay and enables faster convergence.
Remark 1. Throughout this paper, we assume that a S d. This follows the result of Perchet & Rigolled (2013), who show that under Hölder smoothness with exponent B, nontrivial oracle policies exist only when aB dd while the oracle becomes trivial when o. > d. In the trivial regime, the optimal policy x² always pulls the same orm at every time step, almost surely under Ix. In such cases, conteztual information becomes irrelevant for recisiin-making. In our Lipschitz setting (3 = 1), this reduces to the condition a S d, ensuring that conterts play mearingful role in learning and regret minimizzttion.
The margin condition plays a crucial role in determining the minimax rate of regret in nonparametric bandit problems, similar to its role in classification (Mammen & Tsybakov 1999: Tsybakov & Audibert 2007).
Notation: We use ||. || to denote the Euclidean norm in Rd. We denote B(z,r) to denote Euclidean ball with center E Rd and radius r. We denole I and Z to denote inequalities uplo constants. The notation f(n) (g(()) indicates an asymptotic tight bound. Formally, there exist positive constants C,, and no such that for all n 2 no, g(n) S f(n) S 02 (n).. The notation Ö(g(n) denotes an asymptotic upper bound up to logarithmic factors. For a, E R, a V b denotes the maximum a and b, and a A denotes minimum of a and b. For any batch m, let Ft.., be the filtration encoding the history up to batch m.
3 Batched Nonparametric k-Nearest Neighbor-UCB (BaNk-UCB) Algorithm
Recall that in the batched bandits setting, the decision at time in batch m only depends on the information observed up to the end of the (m - 1)th batch. We propose BaNk-UCB (Batched Nonparametric k-Ncarest Neighbors Upper Confidence Bound), described in Algorithm [ The algorithm is based on an adaptive k-nearest neighbor poliey that tunes the neighborhood size k based on the local sub-optimality gap (margin) and context density. This approach extends the adaptive K-NN UCB algorithm of Zhao et al (2024) for the online sctting to the batched nonparametric bandit setting. Let us first define some useful notation. For x E X' and some fixed k < 1m- let. Ne.. (,, a) be the set of k nearest neighbors of x where arm a was chosen, i.e.,
(z, a) = (s S 4m : a, = a and X, is among the k nearest to x}. N
(4)
For simplicity, we denote (2, Nim-,, a) for all times within the batch interval (lm-1, bm] Then we define for t E (tm-1, fm],
(x), max
|X, æ²Il
(5)
sEN.m-1 (zza)
to be the radius of the k-NN ball around x for arm We adaptively select the number of neighbors, denoted (z), based solely on observations available up to the end of batch (m 1n-1) 1) and specifically associated with arm a. This ka,s is then used in the proposed BaNk-UCB algorithm as described in Algorithm [
ka,((z) max {1 [da.))())
In Intm-1
(6)
Note that, the left hand side Lda.t.()) (x) controls the bias in the estimation of fa and the right-hand side /intm-1/j controls the variance in the estimation, i.e,, it ensures that use large k if previous samples
4

---

Published in Transactions on Machine Learning Research (11/2025)
are relatively dense around Xt, and vice versa. The adaptive selection of l in equation 6 requires that the nearest observed context be sufficiently close. Specifically, we enforce I. S VIn 1mmi otherwise, reliable estimation not feasible, and we conservatively set the UCB to infinity: fa,((x) = co. Otherwise, for E (m)) we calculate the upper confidence bound (UCB) follows:
Sa,(2)) (a)
Σ
Y, + Ea,( + Lda
(7)
sEN (x,a)
where da is as defined in equation 5 and Ca,t is defined as:
(a,((x) = / 20²
-V 1(),(
In (dtm==llA))
(8)
Algorithm BaNk-UCB for Batched Nonparametric Bandits
1: Input: Partition fo, f,.,.,,,a tas, with to = 0 and tM T.
2: for m = ,....,,,, do for = m-11 + Im do Receive context Xx; for E A do
if (da, v /lttm11 then
7: else
Set (Xi( f- +o0;
Compute (Xi) according to equation
10:
Compute fa,((x) according to equation
11:
end if
12:
end for
13:
Choose action a, arg m fa. (Xi);
14:
Pull arm de:
15:
end for
16:
Observe rewards (Y,, E 4m-1 + 1y...,bm))
17:
end for
Here, (a,((x) provides a high-probability bound for stochastic noise of the nearest-noighbor averaging, while (x) controls the estimation bias from finite-sample approximation. Both terms depend explicitly on prior- data, highlighting the critical role batch design plays in balancing estimation accuracy and cumulative regret. Finally, the algorithm selects a, with the maximum UCB value,
arg max (X.).
aEAA
Note that in equation g tics are broken arbitrarily at each time step t. The adaptive choice of (x) equation 0 simultaneously balances the bias-variance and exploration- exploitation trade-offs in estimating fa- Specifically, the bias-variance trade-off managed by selecting a larger k when previously observed contexts are densely sampled around X,, thereby reducing variance, and choosing smaller I otherwise, controlling bias. Moreover, due to the Lipschitz smoothness assumption, contexts with larger optimality gaps (f+ (x)) naturally correspond to larger radii (z,),(z), leading to smaller chosen values of I and promoting targeted exploration in regions with high uncertainty.
Note that, key distinction from Jiang & Ma 2025 lies in how structural assumptions influence the algorithm. In their method, the design the partition grid explicitly depends on the unknown margin parameter a. In contrast, our adaptive choice of l equation in the k-NN estimator does not require direct knowledge of a, making our approach more robust unknown margin condition.
Remark (Tuning hyperparameters) Assuning known sub- Gaussian voriance prozy o² in Assumption is slandard in the lâterature. For example, Reeve et al. 20187) assume unit. variance, and Perchel t

---

Published in Transactions on Machine Learning Research (11/2025)
Rägollet 2013) assume bounded rewards, which imply sub- Gabusiass tails. We make this dependence explicit for trunspurency in regret scaling. In practice, since o² enters the UCB width in equation & it can be conservatively overestimated, tuned, or estimated from early residuals. Similarly, the Lipschitz constant L, which also appears in the confidence bound, can be treated as a tunable hoperparameter or heuristically chosen based on preliminary runs.
4 Minimax Analysis on the Expected Regret
In this section, we demonstrate that the BaNk-UCB algorithm achieves a minimax optimal rate on the expected cumulative regret under appropriately designed partition of grid points. Specifically, the rate matches known minimax lower bound up to logarithmic factors. First describe the choice of the batch grid points and then state the upper and lower bounds on the expected regret.
4.1 Batch sizes
The choice of batch sizes plays crucial role in the performance of the batched bandit algorithms. We partition the time horizon into M batches, denoted by grid points G = (,,..,,,, with to = 0. The special case M T recovers the fully sequential bandit setting, where policy updates occur at every step. Conversely, popputaatiooalppratttiinn
smaller M imposes fewer policy updates, introducing a trade-off between key challenge in the batched setting is selecting the grid G. Intuitively, minimize total regret, no single batch should dominate the cumulative error, suggesting that the grid should balance regret across batches. If one batch incurs higher regret, reassigning time steps can improve the overall rate. This motivates grid choice that equalizes regret across batches, up to order in T and d, as formalize below. We choose:
complexity
and regret accumulation.
ad, tm Latm
(10)
where y = 1te and a = O(Ti-)) is chosen so that tm = T. 2+d
4.2 Regret bounds
In order to establish the regret rates, we first define the batch-wise expected sample density, motivated by the formulation of Zhao et al. (2024). Let pa (m)
X - R is defined such that for all A C X,
- p(th (x))dx.
E
Σ
1(X. A,a
(11)
First let's consider the cumulative regret relate it to the batch-wise expected sample density. Lemma 1. The expected cumulative regret in equation is given by Rr = EnEA Em R!m) (T), where R(m²)( (T) is defined as:
((() [ - (o))
(12)
Proof. Consider,
RT(T)) EE
- fxx faxx)))
E
(f(()) (x.
m= 1=bm-1
M
(f.(X)) - (x))))
REAmE m=1
E=tm-1
M
Σ
(f-(x) (x)( pm (x)
REAM=L
6

---

Published in Transactions on Machine Learning Research (11/2025)
Note that, in the third equation rewrite the expectation over dr ~ T(. Xx) deterministic sum over all arms a E A, using the indicator I(a = a) to isolate regret contributions from each arm. This facilitates the integral form in the final step of the proof. Using the fact that the batch sizes are chosen to control for the regret to be balanced across batches, the idea is to construct an upper bound on the batch-wise arm specific regret, R(."(( (T.. Then, using Lemma we can bound the expected cumulative regret. Note that unless otherwise stated, the covariate dimension d is treated as fixed. Constants hidden in the asymptotic notation may depend on d (potontially exponentially).
Theorem 1. Under Assumptions 74 and with the batch sizes as defined in equation 70 in Section regret of the proposed BaNk-UCB algorithm (T) is bounded by,
1
the
RT(N) S |AMM 3 (In7)",
(13)
where
I 2+d'
Proof. For O, split R(m)) into two terms:
[ (al)))
R!m)
fa(x) e)dr
+ f((10)) - fa(C)) (x) - fa(x)= S e)dz.
(14)
The idea is to bound these two terms separately, where the second one be bounded using the margin assumption (i.e., Assumption
The e is determined theoretically based on the bound on R!m) From
Lemmas and 10 in the Appendix B we get that:
J fa()))
(z)1 fa(x) E) dr a-- In 1 + tmel+a
(15)
Furthermore, we can bound the second term in equation 14 by
/ (f.(x) fa(x))p! (x) fa))) S 5 dx
I fm / (f.(() - fa(x) S da
(16)
where (t) follows from Lemma 2 and (i) follows from the Margin condition. Now combining equation 15 and
equation 16 we get from equation 14
R(m) S aan-d- In-1Innt intm-1 + tm T4a
(17)
By the choice of our batch end points tm = |at? |att-1/ then it is casy to see using goometric sum in the 1 3 with y = get == [tml In fm-1] 1]= žंत. Therefore, we have:
exponent, tm = O(Ti
Lte. Now, balancing the two terms in equation 17 and solving for e, we 24d
m-1
R(m) $ bm [___ In 4m-11 $ Ti-a T Now, using Lemma [
1-7
(In km 1m = --- (mn (18)
Line
M
Ry(x) =
p(m) R(m)(T)
aEA m=1
TT (In 1mm
REA
A (In

---

Published in Transactions on Machine Learning Research (11/2025)
]
Next, we state the minimax lower bound the regret achievable by any M-batch policy (G, established
by Jiang & Ma (0225) and show that it matches the upper bound in Theorem
I up to logarithm factors.
Remark 3 (Comparison with Previous Work). Since Jiang & Ma (2025) is the only prior work that addresses the batched nonparametric bandit setting, it is important to emphasize that our proof techniques differ substantially from theirs. While their analysis builds on the binning-baser framework Perchet & Rigollet (2013), our regret analysis requires non-trivial extensions of the adaptive k-NN UCB algorithm of Zhao et al. (0244) to the batched selling. In parlácular, our analysis is fundomentally batch-aware:: all supporting lemmas and the fonal regret bound are developed by carefully balancing the batch endpoints and are first established in batch-wise fashion. Moreover, our supporting lemmas refine the analysis in Zhao el al. (2024) by clarifying implicil assumplions and exlending the orgament to handle the balch-consttaineed feedback setfing. These technical developments are essential to handling the delayed feedback and restricted policy updates that characterize the batched regime.
Our main contribution lies in achieving the same minimax-optimal regret rate as Jiang & Ma 2025); while introducing a conceptually simpler and data-adaptive algorithm that consistently outperforms binning-bas based methods in practice. In order to establish this, we present the fundamental limits of the batched nonparametric bandit problem as characterized by Jiang Ma (2025).
Thcorem (Minimax lower bound for nonparametric batched bandits; adapted from Jiang Ma (2025) Let F(L,a) denole the class of functions satisfying the Lipschilz smoothness condition (Assumplion 3 with constant L and the margin condition (Assumption 4). For any M -btchhh policy π deployed over T rounds in 2-armed setting with reward functions f1 E F(), the minimax expected cumulative regret satisfies:
inf sup (T(T)) 2 T where 7 2 2 fL.EFF(L
a +1
This result characterizes the fundamental difficulty of learning in nouparametric batched bandits under the class F(L,a), a), and shows that our BaNk-UCB algorithm matches this lower bound up to logarithmic factors. Note that, when M 2 In 7) and the number of arms |A| S In T, the cumulative regret simplifies to Rr(r) = Ö(T2-7), recovering the known minimax optimal rate for fully sequential (non-batched) nonparametric bandits (Perchet & Rigollet, 2013). This condition implies that, surprisingly, only a relatively modest increase in the number of batches logarttgtii in the horizon T) is sufficient to achieve the fully sequential optimal rate. Additionally, the mild logarithmic restriction on the number of actions |A| reficcts practical scenarios where the action set is moderately large but not excessively growing with T, highlighting the efficiency of the BaNk-UCB algorithm in nearly matching fully adaptive performance despite batching constraints.
5 Experiments
In this sention, we present numerical simulations and real-data experiments to illustrate the performance of the proposed Batched Nonparametric k-NN UCB algorithm (BaNk-UCB) in comparison to the nonparametric analogue: Batched Successive Elimination with Dynamic Binning (BaSEDB) algorithm of Jiang & Ma (025))
5.1 Simulated Data
We evaluate BaNk-UCB under two simulation settings. Setting 1 deliberately violates the Lipschitz smoothness assumption and features a discontinuous, piccewise-constant reward structure to assess robustness under model misspecification. In contrast, Setting satisfies the smoothness assumptions and serves as a benchmark under well-specified conditions. We describe both settings below.
Sctting 1: We consider a piccewise-constant reward structure with localized high-roward rogions, designed to challenge algorithunic adaplivity in non-smooth settings. Specifically, we define
[(x) Ligh 1xx E Bj}, f2(x) 0, DEX,
where By E (-1,1) are Rademacher variables and each B, is a ball of radius r centered at cy. In Figure [ we set X = =-11, 1jd (with d == 2 and uniform Px), r 0.6, and D 6, with randomly chosen centers and signs
8

---

Published in Transactions on Machine Learning Research (11/2025)
Setting 1: F,(x) and F((x)
Setting 2: F((X) and E(O)
1,00
0.5
7,00
0.5
-1
-1
-0.
0.5
Setting 1: d =
Setting 2, d =2
2000
3000
Curralativve Regret
Curulattiv Regrot
1500
2000
1000
1000
500
0-
2500
5000 Time
7500
10000
0
2500
5000 Time
7500
10000
Algorithm
BaNk-UCB
BaSEDB
Algorithm
BaNk-UCB
BaSEDB
Figure 1: Top row (left to right): Reward functions for the two arms in Setting and 2, respectively. Bottom row: Cumulative regret comparison for BaSEDB and BaNk-UCB algorithms over 30 runs.
for the balls. Similar function classes (typically in smoothed form) with sharp transitions and varying best arms across regions have appeared in related work, often as part of lower bound constructions in Perchet &
Rigollet (2013), Jiang & Ma (2025). and Zhao et al. (202 While this construction does not satisly Lipschitz continuity, we include to examine the robustness of BaNk-UCB under model misspecification.
Setting 2: As illustrated in Figure consider the following choice of mean reward functions: fi(x) ||x
and fz( 0.5 ||1||,, where X is sampled uniformly from [-1, 1] with d 2.
We set 7 = 10000, T. = for the Lipschitz constant in Assumption 3 We fix the number of batches to M 5 to balance between frequent updates and computational efficiency, but the results remain consistent across different choices of M. For the BaSEDB algorithm, we follow the specifications described in Jiang & Ma (025) for choosing grid points and bin-wite width.. For our proposed BaNk-UCB algorithm, we choose the same batch grid for a fair comparison.
In Figure [ we plot the cumulative regret averaged over 30 independent runs. In order to present an empirical assessment of the variability inherent in simulations, the shaded regions represent empirical confidence intervals computed as +1 times the standard error across these runs. The vertical dotted blue lines denote the grid choices for the batches.
BaNk-UCB consistently outperforms BaSEDB across all experimental settings. Although our batch sizes were selected based on empirical performance, they align closely with the theoretically motivated schedule Scction 4.1 Importantly, as illustrated Appendix [.II. BaNk-UCB demonstrates robust performance across different batch schedules. provided the endpoints follow the prescribed growth pattern. This suggests that the algorithm does not require fine-tuned batch timing to perform effectively.

---

Published in Transactions on Machine Learning Research (11/2025)
extend the comparison to nigher-dimensional contexts (d = 3, 5,), where both methods degrade in performance, yet BaNk-UCB maintains consistent advantage over BaSEDB. A key practical benefit of BaNk-UCB is its minimal tuning overhead. Unlike binning-basee algorithms such as BaSEDB, which depend on careful calibration of bin widths, refinement rates, and arm climination thresholds often requiring knowledge of problem-specific parameters BaNk-UCB relies on a fully data-driven nearest neighbor strategy. Its adaptively chosen automatically balances bias and variance based on local data density, without needing explicit smoothness or margin parameters. This makes BaNk-UCB both more robust to misspecification and easier to implement in practice.
In Appendix B.1
5.2 Real Data
We evaluate the performance of BaNk-UCB and BaSEDB algorithm on three publicly available classification datasets: (a) Rice (Cammeo Osmancik 2020), consisting of 3810 samples with 7 morphological features used to classify two rice varieties; (b) Occuponcy Detection (Candancdo & Feldheim, 2016), with 8143 samples and 5 environmental sensor features used to predict room occupancy; and (c) EEG Eye State (Biermann) 2014 with 14980 samples and 14 EEG measurements used to classify eye state. In all cases, we treat the
RicaClassiffcant
occupancy
EEG
0.8-
9.5-
Frection incornec pullis
0.5-
9.5-
FracSion
1900
2000
2000
4000
6000
6000
5000
10600
1900
Time
Algorithm
BaNL-UCA
RaGEDR
Algorithm
RaME-UCa
RaGEOn
Algorithm
RaMe--UCa
BaSEOR
Figure/ 2: Rolling average fraction of incorrect decisions across three real datasets. BaNk-UCB achieves lower error and faster learning than BaSEDB.
true label as the optimal action and assign a binary reward of 1 if the selected action matches the label, and 0 otherwise. We simulate a contextual bandit setting where the context Ie is observed, the learner selects an arm a, E {l....,K] and observes only the reward for the chosen arm. We set the number of arms K equal to the number of classes (which K = for the three datasets considered) and choose 3, 4, and 6 batches respectively, aiming for sufficient granularity to allow adaptation without making individual batches too small. While the total number of batches M reflects practical deployment constraints, the batch endpoints g = {tm J.M are set to approximately follow the geometric schedule in Section 4.3, which balances regret across batches and aligns with our theoretical guarantees. The rolling fraction of incorrect docisions is computed using a windowed average over 30 independent random permutations of each datasct. In Figure 2 we plot the rolling fraction of incorrect decisions with shaded regions 1+1.96x standard errors) for uncertainty quantification as function of the number of observed instances. BaNk-UCB consistently outperforms BaSEDB across all datasets. For the EEG dataset, which has the highest context dimensionality, BaNk-UCB exhibits faster convergence and consistently lower error, suggesting its advantage in capturing local structure in high-ddmenssonal spaces. Batch sizes are chosen according to theoretical guidelines and are identical for both algorithms.
6 Conclusion
We introduced BaNk-UCB, nonparametric algorithm for batched contextual bandits that combines adaptive k-ncarest neighbor regression with the UCB principle. Unlike binning- based methods, BaNk-UCB leverages the local geometry of the context space and naturally adapts to heterogeneous data distributions. We established near-optimal regret guarantees under standard Lipschitz smoothness and margin conditions and proposed a thcoretically grounded batch schedule that balances regret across batches. In addition its theoretical robustness, empirically we illustrate that BaNk-UCB is resilient to batch scheduling choices and requires minimal parameter tuning, making it suitable for practical deployment in real-world systems. Empirical
10

---

Published in Transactions on Machine Learning Research (11/2025)
evaluations on both syuthetic and real-world classification datasets demonstrate that BaNk-UCB consistently outperforms existing nonparametric baselines, particularly in high-dimensional or irregular context, spaces.
Despite these advantages, several open challenges remain. Although our regret guarantoes show that k-NN performs well in moderate dimensions, its statistical accuracy may deteriorate in very high-dimensional regimes due to the regret bound's dependence on the ambient context dimension d. However, prior work k-NN regression suggests that it can adapt to the intrinsic dimension of the context distribution, which may mitigate this issue. Formalizing this adaptation in the batched bandit setting remains exciting direction for future work. Additionally, while our algorithm uses theoretically motivated batch schedule, real-world systems may impose scheduling constraints that deviate from the idealized setting. Although our method performs well empirically under various batch schedules, deriving theoretical guaranlees under arbitrary batch schedules is another important extension. Future work may also explore adaptive strategies for estimating smoothness and margin parameters, climinating extrancous logarithmic factors in regret bounds, and generalizing the framework to infinite structured action spaces.
Broader Impact Statement
This work develops a theoretically grounded algorithm for sequential decision-making in batched settings, with applications in domains such as personalized medicine, online education, and adaptive experimentation. By improving statistical efficiency under limited foedback, our approach could contribute to safer and more effective drcision-making in resource-constranned or high-stakes environments. However, care should be taken when applying such methods in sensitive domains, particularly in ensuring that fairness, transparency, and domain-specific constraints are accounted for. Our analysis does not directly consider fairness or robustness under distribution shift, and these remain important directions for future work.
References
Sakshi Arya and Hyebin Song. Semi-parametric batched global multi-armed bandits with covariates. arXiv preprint arXiv:2503. 00565, 2025.
Sakshi Arya and Bharath K Sriperumbudur. Kernel e-greedy for contextual bandits. ar preprint 2rv: 1 17329, 2023.
H. Biermann. Eeg eye state datasel. httt:///waaaheeeee.......eeaaa/r
2014.
G. Cammeo and T. Osmancik. Rice (cammeo and osmancik).
http:s//aacchiie..eee.ddddddd//d
Ricet (Cammeo+and-Dsmmncikk) 2020.
Luis M. Candanedo and Véronique Feldheim. Occupancy detection data set. https://archive.ic ict.er........ icc.uci
edu/ edu/dataset/ /ttpa/asst/////occppprrttttttttt 2016.
Hossein Esfandiari, Amin Karbasi, Abbas Mchrabian, and Vahab Mirrokni. Regret bounds for batched bandits. Proceedings of the AAAT Conference on Artificial Intelligence, 35(8):7340-7344 73448, May 2021.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Yasong Feng, ZZngfeng Huang, and Tianyu Wang. Lipschitz bandits with batched feedback. In Alice H. Oh, Alckh Agarwal, Danielle Bolgrave, and Kyunghyun Cho (ods.), Advances in Neural Information Processing Systems, 2022.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. ACM / IMS J. Data Sci., 1(1), Jamuary 2024.
Melody Guan and Heinrich Jiang. Nonparametric stochastic contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
11

---

Published in Transactions on Machine Learning Research (11/2025)
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glymn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprial or Xic:2004.06322 2020.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes. In Conference on Learning Theory, pp. 2007-2010. PMLR, 2020.
Rong Jiang and Cong Ma. Batched nonparametric contextual bandits. IEEE Transactions Information Theory, 2025.
Tianyuan Jin, Jing Tang, Pan Xu, Keke Huang, Xiaokui Xiao, and Quanquan Gu. Almost optimal anytime algorithm for batched multi-armed bandits. In International Conference on Machine Learning, pp. 5065- 5073. PMLR, 2021.
Cem Kalkanli and Ayfer Ozgur. Batched thompson sampling, In Advances in Newral Information Processing Systems, volume 34, pp. 29984-29994. Curran Associates, Inc., 2021.
Edward S Kim, Roy S Herbst, Ignacio Wistuba, Jack Lee, George R Blumenschein Jr, Anne Tsao, David J Stewart, Marshall Hicks, Jeremy Erasmus Jr, Sanjay Gupla, et al. The battle trial: personalizing therapy for lung cancer. Cancer discovery, 1(1):44 53, 2011.
Samory Kpotufe. k-nn regression adapts to local intrinsic dimension. Advances in neural information processing systems, 24, 2011.
Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011.
Tze Leung Lai, Herbert Robbins, and David Siegmund. Sequential design of comparative clinical trials. In Recent Advonces in Slatistics, pp. 51 11-68 Flsevier, 1983.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6): 1808-1829, 1999. doi: 10.1214/aos ///////00////99////// 1017939240.
Yizhi Mao, Miao Chen, Abhinav Wagle, Junwei Pan, Michael Natkovich, and Don Matheson. batched multi-armed bandit approach to news headline testing. In 2018 IEEE International Conference on Big Data (Big Data), pp. 1966 1973. IEEE, 2018.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 2013.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660 681, 2016.
Wei Qian and Yuhong Yang. Kernel estimation and model combination in bandit problem with covariates. Journal of Machine Learning Research, 17(149), 2016.
Henry Reeve, Joe Mellor, and Gavin Brown. The k-nearest neighbour ueb algorithm for multi-armed bandits with covariates. In Firdaus Janoos, Mchryar Mohri, and Karthik Sridharan (eds.), Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pp. PMLR, 07-09 Apr 2018a.
Henry Reeve, Joe Mellor, and Gavin Brown. The k-nearest neighbour ueb algorithm for multi-armed bandits with covariates. In Algorithmic Learning Theory, pp. 725-752. PMLR, 2018b.
Zhimei Ren, Zhengyuan Zhou, and Jayant R. Kalagnanam. Batched learning in generalized linear contextual bandits with general decision sets. IEFE Control Systems Letters, 6:37-42, 2022.
12

---

Published in Transactions on Machine Learning Research (11/2025)
Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. Conference on Learning Theory (COLT), pp. 54, 2010.
Eric M. Schwartz, Fric T. Bradlow, and Peter S. Fader. Customer acquisition via display advertising using multi-armed bandits. Marketing Science, 36(4):500 522, 2017.
Ambuj Tewari and Susan A Murphy. From ads interventions: Contextual bandits in mobile health. Mobile health: sensors, analytic methods, and applications, pp. 495-517, 2017.
AB Tsybakov and J-Y Audibert. Fast learning rates for plug-in classifiers. Annals of Statistics, 35(2):608-66 633, 2007.
Michal Valko, Nathan Korda, Rémi Munos, This Flaounas, and Nello Cristianini. Finite-time analysis of kernelisod contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pp. 654 663, 2013.
Yuhong Yang and Dan Zhu. Randomized allocation with nomparametric estimation for multi-armed bandil problem with covariates. The Annals of Statistics, 30(1):1000 121, 2002.
Puning Zhao, Jiafei Wu, Zhe Liu, and Huiwen Wu. Contextual bandits for unbounded context distributions. arXiv preprint Xix::22406 00.02555, 2024.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ueb-based exploration. In International Conference on Machine Learning, pp. 11492 11502. PMLR, 2020.
A
Appendix
In this section, we provide the detailed proof for the regret upper bound for BaNk-UCB algorithm in Theorem First. we present the supporting lemmas for establishing the upper bound for the expected regret Section
B Proof for the Regret Upper Bound
Recall, the batch-wise expected sample density, p(()) (x), from equation
Lemma 2 we first construct an (m)) (x) in terms of the context density px (z).
upper bound for Pa
Lemma 2. The batch-wise erpected sample density satisfies:
(mm)( (x) S (tm tm tm-11pp2 1)
P
for almost all æ E X.
Proof. Note, since the event (X, E A) C (X, A, a),
1(x, 1(X, A,
(I -m- pxxxxx) (2)dda.
(19)
From equation 11 and equation 19
get that,
(x)dx S (tm - tm-1) / Px (2)(x)
for all AE X. Therefore, pam) (x) S - -tm tm-mmmx-pp (z) for almost all x E &.
Next, we build a concentration bound on the average model noise for the k-nearest neighbors around a point z. Here, we will use the sub-Gaussianity of noise (Assumption [ and the fact that we only observe data until the last batch, i.e., for E [1m-1 + 1, 1m], we can only utilize data until time ln-1 for estimation.
13

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 3. Let Nt.. I. 1, a) denote the set of k nearest neighbors among {X,: : < 1m a). Then, for all x E X, E A, and k 2 1, we have Bhat,
sup 2,a.
Σ
Ci > u
S |di22t||Ale 1Ale- 200
(20)
Vk
iENom-11
where Q are independent sub- Gaussian noise terms with variance prozy d².
Proof. From Lemma 4 of Zhao et al. 2024 we have that of a fixed A:
P
sup 2,a
Vk
Σ
Ei
> u
S 2d
|Ale 207
(21)
iEN
m.. (2,0)
Then we apply union bound over all m-11 to gel,
1
2 < d12a-11Ale-
P
sup z.a,k
Ei > u
Vk
(ENi,
Note, that Lemma 3 is for any batch m and we will use to bound the batch-wise regret.
Definition 1. Define the event Em
{/1
Σ Er S 20 (n(d12tt()))) x, sakk
Em =
(22)
VT iENim-1,
Then, from Lemma
3 it follows that P(Em) 2 1-tmm
Lemma 4. Under Em, we have that the following point- wise estimation error bound for x X and
E [tm-1 1, tm]:
fa(x) s Pa,()) S fa(x) 25a,(z) + 2L),
(23)
where (x) and (x) are as defined equation g and equation respeclively.
Proof. Observe that for & [4m-1 + 1, km], under event. &m and X:
Fa,(()) - (fa(()) (x) [d),
(24)
Σ
(Y- fa(x))
ko,((x) (EAi(z,a)
Σ Va-fa(Xi)) + kz))(x) sEN)(a.))
Σ (fa(X)) - fa()))
1ir)( (E.)(a.a)
Ea,t()) (2:) (x),
(25)
where the last line uses the definition of En in equation 22 and the Lipschitz (smoothness) property (Assumption 3 of fa-
14

---

Published in Transactions on Machine Learning Research (11/2025)
Quantities of interest: We define some important quantities of interest which are central to the proof.
This includes two population quantities:
1 (f((z) - (x)x)),
ra(z)
(26)
2LVC1
Ci 1iln-mm1 1m-1
na (mm)
(x) (x)
(27)
(f+(x) fa(x)))
in which
C = max (2d log( M Md)AA)))
(28)
((m))) (x) can be interpreted as a local sample complerity prozy, capturing the number of samples required near x to estimate the reward function fa(x) with sufficient precision. Then, another quantity
The quantity na
of interest is a data-dependent quantity that measures the total number of observations until time fm-1
corresponding to arm in radius ball around x. For any X,a A define,
fm 1
(I,
Σ 1(|x, - =|| r, a a).
(29)
Next in Lemma 5 under the event Em, we show that the adaptive choice of ka,t from equation t in our k-NN estimator is in fact upper bounded by ná (x). Then, in Lemma 6 we show that n!m)) a, I (x),
which then leads to the relationship between na ((m) (x) and (1, in Lemma
Lemma Under event Em for [1m-11 + 1, 1,4m)
kar( S n (x).
Proof. We prove this by contradiction. Let (x)( > (m) (x). By definition of ka,t in equation 6
In(tm-1)
In lntm-1 2Lra(x))
Lda,c(x)= Ld (=))
I
(30)
(x,)
(m) (x)
From Lemma 4 under Em:
202
Fa.((x) S (x) +2
In + (Lra(2)
(x))(x))
20
fo) +2
In (nd
(- 2Lr (z).
(31)
(m))
Na.
(x)
Since action a, is selected at time t, from the proposed UCB algorithm (Algorithm D i.e. the choice of ag = arg max fa. (X,) and from Lemma
fal(()) 2 2 2t) fc(x).
(32)
Combining equation 31 and equation
32
gives:
20
2
In(d)2d+3)
2d+3 m-1
[Al) + 2Lra, (1) 2 fx(x)= - Sa, (x).
(33)
Náx
(x)
We now derive an inequality that contradicts with equation
33
From equation 27 and equation 28
202
202
2
In In(d)2d+3 [A) 2/ C 4m--1
In Ind 2d (f)(((()) for (x))2
na, (x)
(m)
In(di2d
5 V (2d 3 (n][AA)) In(tm-1) (fa(z) (x))
/ (f((z) -Sa (x)).
(34)
15

---

Published in Transactions on Machine Learning Research (11/2025)
From the definition of (z) in equation 26
fa. - -)(())))))())((()()(())))))))( f(r
2Lr (2)
(35)
VCI
From equation 34 and equation 35
2x²
2
In 23 [A]) 2Lr (x) < fx))) Sa. (2).
(36)
(m)
Naa
Note that equation 33 contradicts equation 36 Hence, the desired conclusion follows.
0
Lemma 6. Under Em, let ra(x)) 2
2LC, vCI-2
and (x)) 2 In then, we get
n (I, S ka,(
(1, defined in equation 29 and ha, as defined in where (x) is defined in equation 26 equation 0
Proof. We also prove Lemma by contradiction. If ( ar (o()) > (x), let
= max(T < 1m-1 12, x1| S ra (x) A, =}.
(37)
the last step falling in B(x, ra (z)) with action a. Then B(x, (x))) C (ra,,,r((z)) (r)())), and thus there are at least kar) points B(x, 2r (z)). Therefore, for any x X, by the definition of da, ie., the distance of to its wth nearest-neighhors in equation
da,)(x) 2ra(a))
(38)
Denote a" a=x) = arg max, fa (z) as the best action at context Again, note that = a is selected only if the UCB of action a is not less than the UCB of action a=(x), i.e.
fa,(X,) 2 (xx()))(X.)..
(39)
From Lemma
(o,((X)) S fa(x)) 25,, + 2Ldo,
(40)
and
fx)( 2 fa. =f((.).
(41)
From equation
39
equation
40
and equation
fa(X,) + (X,, + 2Lda, ) 2 fx(X.).
(42)
which yields,
(X,) 2 (.(x,) (a(X.) (X,)
2L
f((X)) fa(,))
-2
20 In (dMd722+3) [A)
(.,)(a))
2L
f((x,) fa(x))
2/
20 In (dMT22d33)
In
2L.
2x In (dMM2243 AA)
Viira(X.) V
In
2 Vira(Xi) VCI
L
(X.),
(43)
using the fact that rx(x) 2 JC,-2 and ko,( 2 In Note that equation
21C₁
contradicts equation
38
Therefore (m)) (x, a, ra(x)) < (z) That completes the proof of Lemma
16

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 7. For na( defined in equation 27 and n (m)) a.). defined in equation 29 under &m:
nm (x, a, (x)) S (x).
Proof. Combining the results of Lemma 5 and 6 proves Lemma
Bounding the batch-wise regret R!T"; From Lemma and from Lemma we know that P(EE)) S 1/tm and (r,r), < mm on Em gives:
B n mm) (2,
Fim-i]
(P Fmmm DB (x, Ems Fim-i Em Ftm-
+ FF (m) ax, (m,
< naa (m)) (x) +11
(44)
From the definition of pa (m²) in equation 11
Pa (mm) (u)du S na (x) + 1.
(45)
Recall (m)) from equation 12 We first bound (m) for given to get bound on the expected regret using Lemma 1 To bound R!m!! we introduce new random variable Z follow a distribution with probability density function (pdf) 6:
o(=) Oz (a
(46)
where Cz is the normalizing constant. As discussed Section we split R!m) into two regions: one where the suboptimality gap is large (where concentration bounds dominate) and another where the margin condition helps control the measure of near-optimal points,
p(m) ( (f.(x) (1,(t)
(z)1(f(()) (((()))) fa(x) > c)dr
(a)))
fa(x) S E)dd..
The idea is to bound these two terms separately, where the second one can be bounded using the margin assumption (i.e., Assumption 4). The is determined theoretically based on the bound on R(("). We tackle
the first integral term in the following Lemma
Lemma 8. There exists constont C2 > 0 such that for any a e A,
/ ((()))fa(x))))) (x)1 (f.(x) fa(x) > e) dr
C
pb (m) (f=(u) fa(u)) du Fem-n
where Z is density function defined over X. Here Cg is constant that may depend exponentially the covariale dimension d which we treal as fixed.
Lemmas and 6 refine the argument used Lemma Zhao 2024h, clarifying implicit assumptions and adapting the result accommodate batched feedback.
17

---

Published in Transactions on Machine Learning Research (11/2025)
Proof. Consider,
S DiZzraZ)) po (w) (f+(u) - fa(u)) du Fim-1
E
(47)
1xx I I (=)W(T((u) (Sa(u) - sa(u)) dzdu
B(u,2ra()//3)
/
(
(12 (())
2
(alu)) (m)) (f-())) - (J-(u))-a(u)) du
inf
x
3
(
2
3
(()) ( (S.(u) - sa(u)) du
3
4
1
[(f((u) fa(u)) v (()
(Tm) (u) (J-(w) fa(u)) du
2ºC2
1
(fa(u) fa(u)) fal)))
1(f-(u) fa(u)= > (fa(u) - fa(u)) x Pa (m) (u) (f. - -a(u)) du
2dCz
(4L)²
/
po (w) (f.(w) - fa(u)) 1(f.(u) - fa(u)) > c)du.
(48)
2dd L
For (a), if ||u 2|l S (z), then from the definition of Ta in equation 26 and using the Lipschitz assumption
(Assumption 3) we get that:
Ta
fu(u)- fa(u)
Ta (2)
f.(z) - ff(()
f.(u) -f((=) fa(=) fu(u) + f.(=) fa(2)
fz(z) fa(2)
f.(z) - fa(2) (z)
f.(x) - (a())
+ VC1
3
(49)
2
For (b), we have that ||> u/1 1 (r)(w) 3
therefore we have that:
(u) f.(2)) S 2
2 3 ra((u), and [fa(u) fa(z)) gra(u).
Therefore,
1f(()) - ( -a(z)=((((()) - -a(u))] 4 gra(u) - = - vo()) (1F((N)- - -falu) + 4
(ra(ll)) Vc.
Therefore, we get that,
((z) = ((A(1)) - fa(w)) vd" )(u) (U.(2)) - fa(=)) v
(f.(u) - fa(u)) dd
(ff(w) fo(w)) + (r)
3
(50)
18

---

Published in Transactions on Machine Learning Research (11/2025)
where equation 50 follows because,
I.(u) (a(u) + (ra((u)= f.(u)- - sa(u) + z/. 1
(f(()-
- (u())
2
2
= (fa(u)- - (a())) (1 3/G
Since vC1 2 2, then equation 50 holds.
Next, we prove an inequality that plays key role in bounding the regret contribution from contexts where the reward gap is large.
Lemma
ctldd idd>+t, (51)
J - (.06)0)--60000001000-0--)0------ 2) x
log ( =fd=
1 f
Proof. Consider
J (410)))) fa(z) =c) c)
(52)
2
/ - - - fa(z) e))
x
E [(X(X) -(A(())) fx(x)) 1(f fa(X) > c)
/ P p((<)(()) (a(X) < <( dt
(d-1)
P (f.(x)- - Ja(x) <t 2ي dt
(53)
(a) comess from Assumption 2, which requires that px (x) 2 over the support. In (b), the random variable X follows a distribution with pdf px.
If d a + 1, then from Assumption
Do (d--1)
Da - 1) a+lld
equation
53
(54)
Ju
c(d - a)
If d a + 1, then
(d-1)
1 ( dt +
Da
1
Da (d 1)
!
equation
53
t- شー dt
log
(55)
co
c
If d < a + 1, then
Da (d-11
1 (
1 Da(d-1) - dl
equation
53
di
+
(56)
6 c(a: + d)
Therefore, combining results from equation
53 equation
equation
55 and equation 56 obtain:
a+lldd if
/ (1(()) (((2)) (- - fa()) > dz
log (?)
ifd=
(57)
ifd
This proves equation
51
19

---

Published in Transactions on Machine Learning Research (11/2025)
Lemma 10. Suppose Assumptions 1 and 2 hold. Then, for any batch [M], and for all orms a A, have:
E [ Pa (w)( - na (u)) du Fim-1 2 Cz
(ea-d=1 log tm-1 + Im ctta
Here Cz is the density lower bound constant from equalion 46 and Fi. 1 is the history unlil the (m - 1)th batch.
Proof. Consider:
S
P/ (w) - fa(u)) du Fim-1
Pa U
((((f((()-f(())))) du Fm
2
(6)
3
E
(2) + (() (tmp))))) - fa(z)) Frmm-]]
((nfm)
2
3
/ ((n(m) (z) +
^ (1 (1m (J+(2)- - fa(())
qade d2
2
(2)(f())- ce
3
/ ( (2) 1) ^ (lmmp((3) (f+(2)- - fa(3))
1
2
(2)(f(())- - ffa())]
- c)dz
/
3
+ ((nxm)())+1) (
((())) 1
+ 2
1(f((=) fa(=) S e)dz,
(58)
2zEd
For (a):
f.(u) (00)-faloe fa(u) s f.(=) fa(=) + 2Lra(z)
s f-()) fa(z) + Va (f=
3
2 (f()))
(59)
Wc get (b) from Lemma 2 and equation 44 In equation
58 we split the domain based on whether (fa(2)-fa(2))
is large or small, and use the margin assumption (Assumption 4 for the latter. Note that, If (c())-
then (mm) (Z) (log 1m-1) (I)(()(( fa( -2 is smaller, otherwise the bias dominates.
3
+ fx(2) (=(===((())) (f+(2) fa())) - > <)dz (fa(2) fa(2)) (
Cr In tm-1
equation
58
2Cz
/
- ((())) fa(z)= s c)dz)
+
E [F.((Z) (T.(Z))((()))))))))))))))))))))) fa())) (0+1)(ff(2) -
> >o] Infm-11
Cz
Im cd
E (ff(2)- Ja(2)) (((2))(((((((())) 1(f((Z) - fa(2) {a(2)s+)) se]]
+
(c) 1 (n fin + tm clta)
Cz
where the first term in (c) comes from the dominating term in Lemma 9 and for the second term we use the Margin assumption as follows:
/
- -a(()) < c)dz < 1
- [[X((()-1(0))))) fx(X) < <()
Tn a+1
<
(60)
20

---

Published in Transactions on Machine Learning Research (11/2025)
This concludes the proof.
B.1 Additional Experiments in Higher Dimensions
We extend the numerical experiments from Section 5.1 evaluate algorithm performance in higher-dimensional contexts. Specifically, we consider d E {3, 4,5) while keeping the underlying daaa-generatinng mechanisms for both experimental settings unchanged. As expected, the performance of both BaSEDB and BaNk-UCB deteriorates with increasing dimension, consistent with the theoretical prediction from Theorem and Theorem 2 that regret decays more slowly when d is large due to the corresponding decrease in the parameter 7.
Despite the increased difficulty, BaNk-UCB continues to outperform BaSEDB across all settings, including the more challenging Sctting These results highlight the robustness of BaNk-UCE in moderate high- dimensional settings, where the benefits of adapting local geometry become even more pronounced.
Setting
3
Setting d
Setting 1: 5
2008
1900
800-
500
Curruootive
Camutation
800
200-
200-
300e
500e Time
7600
10600
2500
sdce Time
7500
10600
2500
5000 Time
hice
30000
Algorithm
Setting 2, =3
Setting 2, =44
Setting 2, 5
2000
Cunsdatee Regest
Camadatton Reggest
Camulathem Rangret
6000
2000
2300
2000
5000
7500
10000
2500
1000
7500
10000
2500
5000
7000
30000
Algorithm
DaNt-UCD
DiSEDS
Algorithm
BaNc-UCC
DuSEDO
Algorithm
Balk-UUE
Bactoo
Figure 3: Average cumulative regret 30 runs for BaSEDB and BaNk-UCB under Settings 1 and with d E (3, 4,5). Vertical dashed lines denote batch boundaries.
Appendix D: Batch Scheduling Strategies for Robustness Evaluation
To assess the robustness of BaNk-UCB the choice of batch timing, we evaluate its performance under three distinct scheduling strategies. Each scheme partitions the total time horizon T into M non-overlapping batches of varying lengths, subject to the constraint MM fm T.
Uniform Schedule. All batches have equal length:
T
fm
for m 1, M.
MM
This bascline distributes samples evenly across time.
Linearly Increasing Schedule. Batch lengths grow linearly with index:
fm
T
for m L, I.....M4 M.
This emphasizes early exploration and later exploitation.
21

---

Published in Transactions on Machine Learning Research (11/2025)
3. Normalized Exponential Schedule, Batch sizes grow exponentially:
Wm =1- base with base 1,
Wm
mm
T
Wj
This accelerates sample allocation later stages; we set base in our experiments.
The resulting breakpoints { :2....,,T) T determine when policy updates occur in the batched setting.
Empirical Findings. Figure compares cumulative regret under all three scheduling schemes for both simulation settings. BaNk-UCB consistently achioves lower regret than BaSEDB, regardless of batch timing strategy. These results underscore the robustness of BaNk-UCB to the choice of batch schedule.
Setting 1: 2, Uniforrm grld
Setting 2, Linear grid
Setting =2, Exponential grid
3000
Cunuulativs Rogeet
3000
1200
2000
2000
Cuarubativv
5000
3000
5000
7600
10l0e
3000
sobe Time
T500
10600
2000
5000 Time
1500
30000
Algorithm
RANk--UC
Rascoa
Algorithi
RaMe-uCh
RaSEDa
Algorithm
BaMk-uch
BASEDO
Setting 2, d =2, Uniform grid
Setting 2, d =2, Linear grid
Setting 2, d = Exponential grid
Cunuudtvve Rogeet
Cumndaabue Regeest
2000
2000
Cumudatvve
2000
3000
1000
3390
5000
7500
10000
2900
1000
7500
10000
2500
5030
1990
39000
Algerithe
DaNL-UCD
DiSEDS
Algorithu
BaNc-UCE
DUSEDO
Algorithm
Batk-UCE
Bactoo
Figure 4: Average cumulative regret over 30 runs for BaSEDB and BaNk-UCB under Settings 1 and with d = 2 across three batch scheduling strategies. Vertical dashed lines denote the corresponding batch boundaries.
22


Reviews:
[{"review_id": "QnXpcagtCk", "reviewer": "Reviewer_tmYZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the nonparametric contextual bandit problem under a batch constraint. The authors propose an algorithm that combines k-nearest neighbor regression with the UCB idea, and establish an upper bound on its regret. The effectiveness of the proposed algorithm is also validated by numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "From my reading, all theoretical claims are either proven in the paper or supported by references, and I did not find any obvious mistakes. The numerical experiments also appear sufficiently reproducible and provide solid support for the claims. However, some parts of the appendix could be better organized.\n\nI do have a few questions regarding the technical details:\n\n* **Assumption 4 vs. prior work**: Assumption 4 seems to differ from the setting in Rigollet & Zeevi (2010). Is this assumption a natural extension, and is the description in Remark 1 accurate?\n  In the prior work, the assumption appears to correspond to the probability that, for $a \\neq a'$, we have $0 < |f\\_a(X) - f\\_{a'}(X)| \\le \\delta$.\n\n* **On Assumption 4 and Remark 1**: Why is it that $\\alpha \\le d$ in Assumption 4, while in Remark 1 we have $\\alpha \\le 1$?\n\n* **Theorem 1 regret bound**: In the special case $M=T$, the batch constraint disappears and the problem reduces to the standard setting, which should be easier. However, Theorem 1’s upper bound then becomes $O(T)$, which seems somewhat counterintuitive. Could the authors clarify this point?\n\n* **Lemma 8 constant $C\\_2$**: According to the proof, the constant \\$C\\_2\\$ grows exponentially with the dimension \\$d\\$. Is it still acceptable to call this a “constant”? If the analysis treats \\$d\\$ as fixed, it would be better to state this explicitly. Note that this exponential dependence also appears in the upper bound of Theorem 1.", "audience_yn": "Yes", "audience_explanation": "Overall, the paper proposes a novel approach to a natural problem setting, and I believe it will attract attention from the machine learning community for both its applications and techniques. That said, I have a couple of further concerns:\n\n* The paper assumes that the batch size can be chosen by the learner. In what applications is such an assumption justified?\n* The batch size proposed in Equation (10) leads to very unbalanced batch sizes. This seems unrealistic for the motivating applications and practical constraints described in the Introduction. Could the authors address this concern? (I note that similar issues could also apply to other batched bandit approaches.)\n\nI would appreciate the authors’ responses to the above questions.", "requested_changes": "I would appreciate the authors’ responses to the above questions.\n\n**Minor comments**:\n\n* Please make the notation of the indicator function consistent (use either $\\mathbf{1}$ or $1$ throughout).\n* In some places where the proof follows immediately after a lemma (e.g., Lemma 3, Lemma 6), the heading still reads *“Proof of Lemma \\*\\*”*. This could be simplified for consistency.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iVrNPvczxb", "reviewer": "Reviewer_7TbF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies decision-making in batched contextual bandits under limited feedback settings. It proposed a new method, called BaNk-UCB, that combines adaptive k-NN regression with the UCB principle to guide actions without parametric assumptions. It adapts to context density, achieves near-optimal regret guarantees, and balances exploration and exploitation across batches. Experiments show BaNk-UCB outperforms binning-based baselines in synthetic and read datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The overall presentation is good, and the theoretical proof can support the claims. However, here are some issues to be resolved.\n\n1. (A minor issue about the problem setting) In the regret definition Equation (3), $X_t$ is a random variable. Do you think there should be an expectation over $X_t$?\n\n2. It’s better to include a detailed discussion of Remark 1, instead of directly referring to some previous works.\n\n3. In equation 8, it requires the preknowledge of the subGaussian variance $\\sigma^2$. This assumption is unusual, and do you think it can be relaxed? I’m also curious about the $\\log (t^{2d+3})$ term. Could you provide an intuitive explanation for it?\n\n\n4. In the proof of Lemma 1, first, there are some typos. The $f_{a_t}$ should be $f_a$ in the third and fourth equations. Second, the notation here is weird, as the right side of equation 12 does not depend on $\\pi$. I guess it’s because the expectation on the left is taken over both $X_t$ and $a_t$, and $a_t$ depends on $\\pi$ (maybe $\\pi_m$. This notation on dependence should be revised to be clearer. \n\n5. Proof of Theorem 1: Typos: $f^*$ should be $f_ *$ in equation (15)(16).\n\n6. Presentation of Theorem 2: There is a $\\sup_{f_1,f_2}$. However, the objective does not explicitly depend on $f_1,f_2$. The notation should be further polished. A similar issue occurs in the presentation of experiments. It should be made clear what $f_1,f_2$ are. I guess it represents that the action set contains only 2 elements, and $f_1,f_2$ are the reward functions for them, is it correct?", "audience_yn": "Yes", "audience_explanation": "The batched nonparametric bandit is a relatively new setting.  This paper proposes a new method that connects k-nearest neighbor analysis with the classical UCB algorithm. This could be interesting to researchers of the bandit community.", "requested_changes": "See the Weaknesses part. I think most issues could be fixed, but the current notations can be somewhat confusing.", "broader_impact_concerns": "The paper has included a well-written broader impact statement. I think it has been well addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xGtrI83lJe", "reviewer": "Reviewer_bLYY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a nonparametric approach to the batched contextual bandit problem. The upper confidence bound (UCB) is evaluated through the adaptive k-nearest neighbor (k-NN) regression, in which the number of neighbors k can be adaptively determined. The authors shows regret guarantees under standard assumptions such as Lipschitz smoothness and margin assumption. Empirical evaluation is provided for synthetic and real-world datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "Strengths:\n\n- The problem setting, batched nonparametric contextual bandit, is a topic worth investigating. \n\n- Detailed theoretical analysis for the regret bound is provided (though I couldn't follow the entire proof). \n\nWeaknesses:\n\n- I currently do not fully understand if the relation with an existing study is property described.\n\n- Several technical details are not clear to me, as questioned below.", "audience_yn": "Yes", "audience_explanation": "k-NN is easy to use in practice, and so, providing a theoretical justification should be informative.", "requested_changes": "I think that the connection with (Zhao et al., 2024) is stronger than what is stated in the main text. While the Intro and Related Work sections do not emphasize this relationship, the proposed method essentially appears to be a batch extension of (Zhao et al., 2024). If that is the case, it should be clearly stated in the Intro and Related Work in more detail. For example, the adaptive k-NN seems directly from (Zhao et al., 2024), but the way it is described in the Intro could lead to the misunderstanding that it is original to this paper.\n\nIn the experiments, what is the idea behind the settings of \\cal{G} and t_m? I do not fully understand typical settings of t_m and M. Are they given by the problem setting or can they be determined by the user? In the later case, under the what criterion, the user selects them? Are they kind of tuning parameters?\n\nIn Sec 5.2, the authors mentioned 'The number of batches was selected based on the total number of samples to ensure reasonable granularity while maintaining batch sizes that approximately align with our theoretically motivated geometric schedule'. What is 'reasonable granularity'? What does 'approximately align with our theoretically motivated geometric schedule' mean?\n\nAlthough the authors claim that the required parameter tuning of the proposed method is minimal, the following (possibly) tuning issues are not clear to me.\n- In practice, how is L chosen? Further, while L = 1 in simulation data, what value was used in real-data and how is that value justified?\n- How is \\sigma in (8) determined?\n\nFor setting 1, \n- What does description 'Setting 1 is derived from the regret lower bound construction' mean?\n- Setting 1 does not satisfy the Lipschitz smoothness assumption. What is the purpose for using a function that does not meet required assumption in the first experiment of the paper?\n\nThe authors claim that it is empirically shown the proposed method is resilient wrt scheduling. However, in my understanding, a result with only one scheduling is shown for each one of settings. To claim robustness wrt scheduling, different results with different schedulings should be shown for one fixed setting.\n\nIn the right bottom plot of Figure 1, the blue line breaks different locations from the dashed vertical line while other results seemingly break at the dashed vertical lines. Is it correct?\n\nWhy do the lines in Figure 2 change between vertical dashed lines. In my current understanding, the lines here should be piece-wise constant if we have sufficient amount of results (although it seems moving average, the window size of the average is small (30), so I guessed the result should become almost piece-wise constant. Do I misunderstand something?).", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)