Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension Yasong Feng
arXiv:2609.05214v1 [cs.LG] 4 Sep 2026
Abstract The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension dz . This note removes that dependence. The next edge length is selected from the number of cubes that survive the preceding elimination. The resulting Count-Adaptive BLiN algorithm does not ed (T (dz +1)/(dz +2) ) regret with Od (log log T ) batches. use dz or the zooming constant Cz , yet it attains O Together with the adaptive-grid lower bound in Theorem 10 of the original paper, the optimal batch complexity remains Θd (log log T ) when dz is unknown.
1
Setup and relation to the original results
We retain the notation and model of [1]. The arm space is A = [0, 1]d equipped with ∥ · ∥∞ , the mean reward µ : A → R is 1-Lipschitz, and ∆x = µ⋆ − µ(x). Recall r , S(r) = {x ∈ A : ∆x ≤ r}, Nr = N S(16r), 2 and Nr ≤ Cz r−dz ,
0 < r < 1.
As in Algorithm 1 of [1], Am denotes the active standard cubes in batch m, all having edge length rm ; A+ m denotes the cubes surviving the elimination in that batch; and µ bm (C) =
nm 1 X yC,i , nm i=1
bm (C). µ bmax = max µ m C∈Am
Theorem 4 of [1] shows that D-BLiN does not require dz and attains the optimal regret exponent using O(log T ) batches. Definition 3 and Theorem 5 use the dz -dependent ACE sequence to reduce this to O(log log T ) batches. Theorem 6 handles the rounding of the ACE sequence. The algorithm below instead makes the edge length data-dependent and dyadic from the outset. Let H := 16 log T,
a0 :=
d+1 , d+2
and, for T ≥ 3, let ( &
log log T B0 := max 1, log d+2 d+1
') .
(1)
For s ∈ (0, 1], define dyad(s) := 2−⌈log2 (1/s)⌉ , the largest dyadic number not exceeding s. For a collection C of cubes and a time t, the instruction Cleanup(C, t) means: play arbitrary arms in for the remaining T − t rounds, without an intermediate feedback round, and then terminate.
1
S
C∈C C
Algorithm 1 Count-Adaptive Batched Lipschitz Narrowing (CA-BLiN) 1: Input: arm set A = [0, 1]d and time horizon T . + 2: Initialize r0 = 1, A0 = {A}, and t0 = 0. 3: for m = 1, 2, . . . , B0 do 4:
Set Km−1 = |A+ m−1 | and γm−1 =
5: 6:
if γm−1 ≥ 1 then Cleanup(A+ m−1 , tm−1 ). return end if
7: 8:
HKm−1 . 2 T rm−1
H . 9: 2 rm d 10: Partition every C ∈ A+ m−1 into (rm−1 /rm ) standard cubes of edge length rm ; denote their collection by Am . 11: Set Lm = |Am |nm . 12: if tm−1 + Lm > T then 13: Cleanup(A+ m−1 , tm−1 ). 14: return 15: end if 16: Play every C ∈ Am exactly nm times and collect the rewards at tm = tm−1 + Lm . 17: Compute µ bm (C) and µ bmax = maxC∈Am µ bm (C). m max 18: Eliminate C if µ bm − µ bm (C) > 4rm ; let A+ m be the surviving cubes. 19: end for + 20: Cleanup(AB0 , tB0 ). 1/[2(d+2)] Set r̄m = rm−1 γm−1 , rm = dyad(r̄m ), and nm =
Neither dz nor Cz is an input to Algorithm 1. Moreover, rm , Am , and tm are measurable with respect to the observations available at time tm−1 , so the resulting batch grid is adaptive in exactly the sense used in [1].
2
Regret and batch complexity
Theorem 1 (Dimension-adaptive regret and batch complexity). Assume the model of [1], with T ≥ 3 and fixed ambient dimension d. Let dz and Cz be the zooming dimension and zooming constant of the instance, and define the analysis-only critical radius ρ :=
HCz T
1/(dz +2) .
(2)
R(T ) ≤ 2d+6 (B0 + 1)T ρ.
(3)
Then, with probability at least 1 − 2T −7 , Algorithm 1 satisfies
Equivalently, dz +1
R(T ) ≤ 2d+6 (B0 + 1)Cz1/(dz +2) T dz +2 (16 log T )1/(dz +2) .
(4)
The total number of batches is at most B0 + 1 = Od (log log T ). Consequently, a single policy that does not know dz or Cz attains the optimal T -regret exponent of Theorem 5 of [1] with the optimal batch-complexity order. Proof. To prove the theorem, we first show that the concentration and elimination properties in Lemmas 1–3 of [1] continue to hold for the data-dependent edge lengths. Based on these results, we bound the regret of each completed refinement batch and the Cleanup step. Finally, we show that B0 refinement batches are sufficient. 2
First suppose that ρ ≥ 1. Since diam∞ ([0, 1]d ) = 1, the Lipschitzness of µ gives ∆x ≤ 1 for every arm x. Hence, R(T ) ≤ T ≤ T ρ, and the regret bound follows directly. The batch bound follows from the construction of the algorithm. In the following, we assume ρ < 1. Adaptive-scale concentration.
For each executed C ∈ Am , define µ̄m (C) :=
nm 1 X µ(xC,i ). nm i=1
Fix an executed cube C ∈ Am . Conditional on the history Ftm−1 available at the beginning of batch m (and on any fresh private randomization used to choose the sampling locations), rm , Am , nm , and all sampling locations in this batch are fixed. Therefore, the same Gaussian tail inequality as in Lemma 1 of [1] gives P |b µm (C) − µ̄m (C)| > rm | Ftm−1 2 nm rm ≤ 2 exp − ≤ 2 exp(−H/2) = 2T −8 . (5) 2 On the other hand, by the Lipschitzness of µ, for every x ∈ C, |µ̄m (C) − µ(x)| ≤ rm . Let E := {|b µm (C) − µ(x)| ≤ 2rm for every executed (m, C) and every x ∈ C} .
(6)
Every estimated cube is played at least once. Therefore, X X |Am | ≤ |Am |nm ≤ T. m
m
From here, applying the above conditional probability bound whenever a cube is executed and then taking a union bound over at most T executed cubes gives " # X c −8 P(E ) ≤ 2T E |Am | ≤ 2T −7 . (7) m
This proves that the conclusion of Lemma 1 of [1] remains valid for the data-dependent edge lengths used by CA-BLiN. Elimination invariants. In the following, we work under event E. We first show that an optimal arm ⋆ survives all eliminations. Let Cm ∈ Am be the cube containing an optimal arm x⋆ . Under event E, for any cube C ∈ Am and any x ∈ C, we have ⋆ µ bm (C) − µ bm (Cm ) ≤ µ(x) + 2rm − µ(x⋆ ) + 2rm ≤ 4rm . ⋆ Then from the strict elimination rule, Cm is not eliminated. This is the same argument as in Lemma 2 of [1].
Based on this result, we show that the cubes surviving elimination are of high reward. Fix C ∈ A+ m and x ∈ C. Since C is not eliminated, µ bmax bm (C) ≤ 4rm . Under event E, it holds that m −µ ∆x = µ⋆ − µ(x) ⋆ ≤µ bm (Cm ) + 2rm − µ bm (C) + 2rm
≤µ bmax bm (C) + 4rm ≤ 8rm . m −µ
(8)
Hence, we conclude that ∆x ≤ 8rm . This is the survivor form of Lemma 3 of [1]. In particular, every survivor cube is contained in S(8rm ). Moreover, the centers of the survivor cubes form an rm /2-packing of 3
a subset of S(8rm ) ⊆ S(16rm ). Therefore, by the same argument used to obtain inequality (4) in the proof of Theorem 5 of [1], −dz Km := |A+ (9) m | ≤ Nrm ≤ Cz rm . The same two bounds also hold for the virtual initial state m = 0. Indeed, diam∞ ([0, 1]d ) = 1 gives ∆x ≤ 1 ≤ 8r0 for every x ∈ A+ 0 . Moreover, K0 = 1 ≤ Cz , because Nr ≥ 1 for every 0 < r < 1, and the inequality Nr ≤ Cz r−dz in Definition 2 of [1], together with r ↑ 1, implies Cz ≥ 1. Thus, for every state m ≥ 0 reached by the algorithm, [ −dz ∆x ≤ 8rm x ∈ C , Km ≤ Cz rm . C∈A+ m
Finally, every arm played in batch m + 1 belongs to a cube in A+ m . Hence, Rm+1 ≤ 8rm Lm+1 .
(10)
Note that this bound involves the parent edge length rm , rather than the new edge length rm+1 . Length and regret of one refinement batch. We are now ready to bound the regret of one completed refinement batch. Fix a state with survivor edge length rm , survivor count Km , and γm < 1. By the definition of r̄m+1 , r HKm d+2 d+2 √ d+1 r̄m+1 = rm . (11) γm = rm T 2 2 Moreover, r̄m+1 /2 < rm+1 ≤ r̄m+1 . Since H/rm+1 ≥ 1, the definition of nm+1 gives nm+1 ≤ 2H/rm+1 . Therefore, the length of batch m + 1 satisfies
Lm+1 = Km ≤
rm
d
rm+1
nm+1
d 2HKm rm d+2 rm+1
d 2d+3 HKm rm d+2 r̄m+1 √ T HKm √ = 2d+3 T γm . = 2d+3 rm
<
(12)
Combining (10) and (12) gives Rm+1 < 2d+6
p T HKm .
(13)
Equality HCz = T ρdz +2 , together with inequality (9), gives dz /2 p ρ T HKm ≤ T ρ . rm
(14)
If rm ≥ ρ, the right-hand side is at most T ρ. If rm < ρ, then γm < 1 gives p √ T HKm = T rm γm < T rm < T ρ. Consequently, whether rm ≥ ρ or rm < ρ, every completed refinement batch satisfies Rm+1 ≤ 2d+6 T ρ.
4
(15)
The two early-cleanup cases. We next bound the regret in the two cases where the algorithm enters the Cleanup step before reaching the hard cap. First suppose that γm ≥ 1. By inequality (9) and the definition of ρ, dz +2 ρ HCz = , 1 ≤ γm ≤ dz +2 r T rm m and hence rm ≤ ρ. Inequality (8) gives Rcleanup ≤ 8rm (T − tm ) ≤ 8T ρ.
(16)
Next suppose that γm < 1, but the planned batch does not fit in the remaining horizon, so that Lm+1 > T −tm . The algorithm then cleans up in the old survivor region. From (8) and (12), we have Rcleanup ≤ 8rm (T − tm ) < 8rm Lm+1 p < 2d+6 T HKm ≤ 2d+6 T ρ. The last inequality follows from (14) when rm ≥ ρ, and from
(17) √
√
T HKm = T rm γm < T ρ when rm < ρ.
Scale contraction and the hard cap. It remains to show that the Cleanup step after B0 completed refinements also has small regret. Suppose that the refinement from rm to rm+1 is completed. When rm ≥ ρ, inequality (9) and equality (2) give dz +2 ρ γm ≤ . rm Consequently, dz + 2 az ≤ a0 . (18) rm+1 ≤ r̄m+1 ≤ ρ1−az rm , az := 1 − 2(d + 2) If rj < ρ for some j ≤ B0 , then every subsequent completed refinement satisfies rk+1 < rk < ρ for k ≥ j, and the desired conclusion already holds. Otherwise, rm ≥ ρ before every completed refinement. Iterating (18) and using r0 = 1 gives rB 1 0 log 0 ≤ aB (19) 0 log . ρ ρ 0 By the definition of B0 , we have aB 0 ≤ 1/ log T . Moreover, H ≥ 1 and Definition 2 of [1] gives Cz ≥ 1. Hence, 1 log(T /(HCz )) log T ≤ . log = ρ dz + 2 dz + 2 Consequently, √ rB0 ≤ e1/(dz +2) ρ ≤ e ρ. (20)
Thus the regret of the hard-cap Cleanup batch is at most √ 8T rB0 ≤ 8 e T ρ < 2d+6 T ρ.
(21)
Summation. There are at most B0 completed refinement batches. By (15), their total regret is at most 2d+6 B0 T ρ. After these batches, the algorithm uses at most one Cleanup batch. Its regret is bounded by (16), (17), or (21), according to the stopping rule. Therefore, R(T ) ≤ 2d+6 (B0 + 1)T ρ. This proves (3). Substituting the definition of ρ into this inequality gives (4). The same counting argument shows that the total number of batches is at most B0 + 1. Since R(T ) ≤ T , (7) also gives E[R(T )] ≤ 2d+6 (B0 + 1)T ρ + 2T −6 . Together with Theorem 10 (Theorem 3 in the introduction) and Corollary 1 of [1], this proves the optimal Θd (log log T ) batch-complexity order and finishes the proof. 5
References [1] Yasong Feng, Zengfeng Huang, and Tianyu Wang. Lipschitz bandits with batched feedback. In Advances in Neural Information Processing Systems, 2022. arXiv:2110.09722.
6