Optimal Algorithms for Range Searching over Multi-Armed Bandits

1 Introduction

Range searching is a fundamental problem in computational geometry and database theory; see, e.g., [Agarwal and Erickson, 1999; Agarwal, 2017; Gupta et al., 2018; Rahul and Tao, 2019]. This problem has been extensively studied over the past few decades, and applications of range searching (along with its variants) arise in numerous real-world domains, such as spatial databases [Samet, 1990], temporal databases [Agarwal et al., 2003], and networking [Li et al., 2003].

In its basic form, range searching considers as input a set of points in R-each with an associated weight-and a collection of (real) intervals. 1 The problem's objective is to efficiently find, for every given interval I, an input point within I with maximum weight.

∗Contact Author

1 The given intervals are not necessarily disjoint.

Note that this classic formulation of range searching addresses fixed (deterministic) weights, i.e., one assumes that the weight of each point is known a priori. By contrast, many modern applications require queries to be processed on uncertain (stochastic) data. As a stylized example of such a setting, consider a paid crowdsourcing platform wherein the competency of the participants (say, in performing a type of task) is not known beforehand. Here, each participant a can be represented as a point pa ∈ R-which denotes the fixed monetary payment for a-and the competency (weight) of a can be modeled as a stochastic quantity. In this setup, range searching corresponds to the natural problem of finding, for each queried price range (i.e., within each given interval), the most proficient crowdworker.

Motivated, in part, by such applications, we study range searching in the multi-armed bandit (MAB) framework. In particular, we address a natural formulation wherein each input point pa ∈ R is associated with a random variable (drawn from an unknown distribution) and the weight of the point corresponds to the (a priori unknown) mean, µa, of the random variable. That is, each given point is an arm and the objective is to identify an optimal (with respect to µa) arm within each given interval. Here, as is standard in the MAB literature, we assume sample access to the random variables associated with the arms/points. The current work develops novel, sample-efficient algorithms for this stochastic version of range searching.

We also design algorithms for a pertinent generalization wherein the weight of each point is a d-dimensional vector, i.e., the random variables associated with every arm/point and, hence, the means µas are d-dimensional vectors. For the crowdsourcing example mentioned above, this generalization models settings in which the proficiency of each crowdworker needs to be assessed across d different types of tasks. 2 In this multi-dimensional setting, the problem objective extends, from finding an optimal arm per interval, to computing a set of Pareto optimal arms within each input interval.

Our Contributions and Techniques. Given the MAB nature of the problems, we obtain PAC-style (probably approximately correct) results, i.e., the developed algorithms compute, with high probability, near-optimal arms for every given interval.

2 As before, the monetary payment for each crowdworker is a fixed and known number.

The sample complexities of our algorithms depend, in particular, on the size of the optimal hitting set of the given collection of intervals. Recall that a (finite) set of points, HS ⊂ R, 3 is said to be a hitting set for a collection of intervals I = {I1, I2, . . . , Iq} iff HS contains a point from the interior of each interval Ii ∈ I. Let τ be the size of a minimumcardinality hitting set for the queried collection of intervals I and n be the number of input points (arms). We show that 4

• (i) For range searching with single-dimensional weights (µa ∈ R), i.e., for finding (near) optimal arms for every interval, the number of samples required by our algorithm is O ( n ε2 log ( τ εδ )) (Theorem 1). Here, ε > 0 is the approximation parameter and δ > 0 is the confidence parameter in the PAC guarantee.
• (ii) For range searching with multi-dimensional weights (µa ∈ Rd ), i.e., for finding (near) Pareto optimal arms for every interval, the number of samples required by our algorithm is O ( nd ε2 log( τd εδ )) (Theorem 3).
• (iii) Finally, we establish lower bounds proving that the sample upper bounds obtained in our algorithms are essentially tight (Theorem 4). Specifically, these results show that a sample complexity dependence on log τ is unavoidable, in general.

Notably the above-mentioned upper bounds do not explicitly depend on the number of input intervals, q. Indeed, the size of an optimal hitting set, τ, can be significantly smaller than q, e.g., τ = 1 for a collection of intervals with a common intersection. Even in the worst case (with pairwise-disjoint intervals), we have τ = q; one can always select the midpoint of each given interval to obtain a hitting set. Notably, a guarantee in terms of τ provides refined (and matching) upper and lower bounds. It also highlights a novel application of this geometric parameter in the current MAB setting.

At a high level, our algorithm for single-dimensional weights proceeds by using the τ points in the optimal hitting set to construct τ +1 pairwise-disjoint intervals (referred to as slabs) that cover all the input intervals (which themselves might have multiple intersections). A key idea then is to identify-through relevant subroutines-a candidate set of arms within each of the τ + 1 constructed slabs and judiciously combine them to find the desired set of near-optimal arms for the input intervals. The subroutines employed to populate the candidate set of arms are based on variations of a result of Cheu et al. [2018] that addresses the skyline problem (with scalar weights).

We build upon this design template, with additional technical insights, to obtain an algorithm for d-dimensional weights. Towards a subroutine, we develop a PAC algorithm for the d-dimensional version of the skyline problem (see Subsection 4.1 for details). Note that the algorithm provided in [Cheu et al., 2018] solely address the single-dimensional version of the skyline problem. Furthermore, even the scalar instantiation (obtained by setting d = 1) of our skyline algorithm is distinct from that of Cheu et al. [2018].

3 The hitting set is not required to be a subset of the input points.

4 Note that, even though the single-dimensional-weights setting (d = 1) is a special case of the multi-dimensional one, we present the settings separately to highlight the layered development of the algorithmic ideas.

Related Work. For a broad survey of MAB literature see, e.g., [Slivkins, 2019]. Even-Dar et al. [2006] develop a PAC algorithm for the problem of identifying a best arm among all the n given ones; see also [Domingo et al., 2002]. The algorithm of Even-Dar et al. has a sample complexity of O ( n ε2 log 1δ ) and a matching lower bound was obtained in [Mannor and Tsitsiklis, 2004]. Multiple variants of best arm identification have also been studied in the literature; see, e.g., [Audibert and Bubeck, 2010; Bubeck et al., 2013; Kalyanakrishnan and Stone, 2010; Garivier and Kaufmann, 2016; Russo, 2016; Yu et al., 2018]. Note that best arm identification can be viewed as a special case of bandit range searching (by considering a single input interval that contains all the arms).

Addressing settings in which each arm is associated with a d-dimensional random variable, the work of Auer et al. [2016] provides a PAC algorithm-with sample complexity O ( n ε2 log nd δ )-for finding Pareto optimal arms. This setting is generalized in our range-searching framework with ddimensional weights.

Cheu et al. [2018] study a setup wherein the arms are positioned on the real line and they provide a PAC algorithm to find a skyline. Bandit range searching generalizes this skyline problem as well. Complementarily, in the case of singledimensional weights, one can use the algorithm of Cheu et al. [2018] as a subroutine for range searching. For multidimensional weights, we in fact develop a novel algorithm for computing skylines. This result generalizes the work of Cheu et al. [2018] (to multi-dimensional weights) and is potentially interesting in its own right. The technical connections between range searching and skylines are detailed in subsequent sections.

Multiple recent results in computational geometry have addressed the (classic) range searching problem over uncertain data [Tao et al., 2007; Agarwal et al., 2009; Agarwal et al., 2018; Li and Wang, 2016]. These works primarily address uncertainty in the point locations. By contrast, the current setting studies fixed point locations, but stochastic weights. Naive Algorithms: A direct approach for the problem at hand is to first compute the empirical estimates of the weights (means) by sampling each arm O ( 1 ε2 log nδ ) times and then report the optimal arms with respect to the estimates. This method requires O ( n ε2 log nδ ) samples overall; see, e.g., the NAIVE algorithm in [Even-Dar et al., 2006] for a PAC analysis. One can also show (by considering a union bound over the intervals, instead of the arms) that O ( n ε2 log qδ ) samples suffice; here q is the number of input intervals. Notably, the current work goes beyond these generic approaches and invokes problem-specific insights (e.g., the use of hitting sets) to develop refined upper bounds. Our tight lower bounds further substantiate the relevance of the obtained refinement.

2 Notation and Preliminaries

The paper studies settings in which one has access to independent draws from n unknown distributions, each supported on [0, 1], i.e., we have sample access to n arms. Throughout, µa ∈ [0, 1] will be used to denote the (unknown) mean under the ath distribution and we will refer to µa as the weight of arm a ∈ [n] := {1, 2, . . . , n}.

Furthermore, in our framework, each arm a ∈ [n] is associated with a (fixed) point pa ∈ R. The set of points P := {p1, . . . , pn} is given to us as input, along with a collection of q real intervals I := {Ii = [ℓi, ri]}qi=1 . Without loss of generality, we will assume that each given interval has a non-empty interior, i.e., for each interval Ii = [ℓi, ri] we have ℓi < ri. For any interval J = [ℓ, r], write A(J) to denote the set of arms belonging to J, i.e., A(J) := {a ∈ [n] | ℓ ≤ pa ≤ r}.

The current work studies the bandit range searching problem: given a set of points P = {pa}na=1 , a collection of intervals I = {Ii}qi=1 , and sample-access to n arms, find-for each given interval Ii-an arm a ∈ A(Ii) with maximum weight µa.

Given the multi-armed bandit nature of this problem, we obtain PAC (probably approximately correct) guarantees; in particular, we develop sample-efficient algorithms that find, with high-probability, near-optimal arms for each given interval. We next define the PAC constructs, with approximation parameter ε > 0 and confidence parameter δ > 0.

Definition 1 (ε-optimality). For any interval I and parameter ε > 0, an arm a ∈ A(I) is said to be ε-optimal for I iff µa ≥ µb - ε for all b ∈ A(I).

Definition 2 ((ε, δ)-PAC guarantee). An algorithm ALG is said to achieve the (ε, δ)-PAC guarantee for the bandit range searching problem, iff-given any problem instance (P, I)- ALG finds, with probability at least (1-δ), an ε-optimal arm for every interval I ∈ I.

Range Searching with Multi-Dimensional Weights. We will also develop algorithms for a generalization of bandit range searching wherein the weights are multi-dimensional vectors. In this generalization, for every arm, the underlying random variable is d-dimensional and component-wise supported on [0, 1]. That is, for each arm a ∈ [n] the (unknown) weight µa ∈ [0, 1]d . The range aspects of the problem remain unchanged: each arm a is associated with a (given) point pa ∈ R and, as before, we are given a collection of intervals I = {Ii = [ℓi, ri]}qi=1 . In this setup, since the weights are d-dimensional vectors (instead of scalars), the problem objective extends to finding ε-Pareto optimal arms (instead of ε-optimal arms).

Note that in the single-dimensional case, if a was an εoptimal arm in set A, then (hypothetically) adding ε to the weight µa, and keeping the weight of all the other arms unchanged, ensured proper optimality of a. The notion of εPareto optimality (defined next) essentially builds upon this perspective. It deems a set of arms T to be ε-Pareto optimal if (hypothetically) adding ε1 to the d-dimensional weight of each arm in T (and keeping the weight of the other arms unchanged) gives us a legitimately Pareto optimal set. Formally,

Definition 3 (ε-Pareto optimality). For any interval I and parameter ε > 0, a subset T ⊆ A(I) is said to be ε-Pareto optimal for interval I iff (a) for all arms b ∈ A(I) there exists an arm a ∈ T such that µa ≥ µb - ε1, and (b) for all arms a ∈ T there does not exist an arm b ∈ A(I) such that µb ≥ µa + ε1.

Here, the inequalities between weights are enforced component-wise and 1 denotes the all-ones vector. We note that, up to pruning, a set T that satisfies Definition 3 also upholds the approximate-optimality criterion (specifically, Success Condition 2) studied in [Auer et al., 2016].

Analogous to the single-dimensional case, we define the PAC guarantee under d-dimensional weights: an algorithm ALG is said to be (ε, δ)-correct for bandit range searching with multi-dimensional weights, iff-given any problem instance (P, I)-ALG finds, with probability at least (1 - δ), an ε-Pareto optimal set of arms for every interval I ∈ I.

Hitting Set and Slabs. A finite set of points HS ⊂ R is said to be a hitting set for a collection of intervals I = {Ii = [ℓi, ri]}qi=1 iff for each Ii = [ℓi, ri] ∈ I there exists a point e ∈ HS such that ℓi < e < ri.

Let HS∗ denote a minimum-cardinality hitting set for the given collection of intervals I and write τ := |HS∗ |. 5 Note that the size of an optimal hitting set, τ , is at most the number of intervals in I, i.e., τ ≤ q.

Our algorithms use the τ points in an optimal hitting set HS∗ and construct τ + 1 intervals that intersect only at their endpoints and partition the real line. In particular, with e1 < e2 < . . . < eτ denoting the set of points in HS∗ , define the following collection of τ + 1 intervals: S0 := (-∞, e1], Sτ := [eτ ,∞), and Sj := [ej, ej+1] for 1 ≤ j < τ.

We will refer to these τ + 1 intervals as slabs. Note that, by construction, the slabs are indexed in increasing order of their left (or, equivalently, right) endpoints. Furthermore, the slabs have pairwise-disjoint interiors and their union covers all the input intervals, ∪I∈II ⊆ ∪τj=0Sj. We will also utilize the following property of slabs, which follows from the fact that their endpoints constitute a hitting set: for every input interval I ∈ I there exists a sequence of at least two slabs, Sx, Sx+1, . . . , Sy, that intersect with I, i.e.,

Property (P) implies that every input interval gets partitioned among two or more slabs.

3 Single-Dimensional Weights

We next state our main result for bandit range searching under single-dimensional weights. Since the following theorem can be obtained by instantiating the multi-dimensional generalization (Theorem 3 with d = 1); a detailed description of this scalar setting is deferred to the full version of this paper.

Theorem 1. Given any problem instance (P, I) with n arms, algorithm ALG-RS draws O ( n ε2 log( τ εδ )) samples and achieves the (ε, δ)-PAC guarantee for bandit range searching (with single-dimensional weights); here τ denotes the size of the minimum-cardinality hitting set for I.

5 Given a collection of intervals I, an optimal hitting set HS∗ (and, hence, τ) can be computed in polynomial-time, via a greedy algorithm.

4 Multi-Dimensional Weights

This subsection develops our PAC algorithm for rangesearching with d-dimensional weights. Specifically, for each arm a ∈ [n], the (unknown) weight/mean is a d-dimensional vector, µa ∈ [0, 1]d , and the problem objective is to find εPareto optimal arms (Definition 3) within each input interval.

The range aspects of the setup are as mentioned previously: each arm a ∈ [n] is associated with a (given) point pa ∈ R and we are also given a collection of intervals I = {Ii = [ℓi, ri]}qi=1 .

Our algorithm, ALG-D-RS (Algorithm 2 in Section 4.2), begins by constructing slabs {Sj}j from an optimal hitting set of the input collection intervals I. Then, ALG-D-RS executes the following two subroutines for each slab Sj: D-LSKY(·) and D-RSKY(·). The subset of arms collected through these executions serve as a candidate set C and the algorithm computes the desired set of arms by selecting Pareto optimal (with respect to the empirically estimated weights) candidate arms within each input interval Ii.

The subroutines D-LSKY and D-RSKY solve the skyline problem, which in fact can be viewed as a special case of bandit range searching. Specifically, in the skyline problem the points associated with the arms, {pa ∈ R}a, themselves generate the collection of query intervals I: in the left-skyline problems we have I = {[pa, p∞]}a and in the right-skyline problems I = {[p-∞, pa]}a, where p∞ := maxa pa and p-∞ :=mina pa.

Prior work has only focused on the single-dimensional version of the skyline problem (see [Cheu et al., 2018]). Hence, towards implementations of the subroutines D-LSKY and D-RSKY, in Section 4.1 we develop a novel algorithm for computing ε-skylines with d-dimensional weights.

4.1 Skyline withMulti-Dimensional Weights

In this section we develop a PAC algorithm for the skyline problem with weights in [0, 1]d .

Definition 4 (ε-skyline for d-dimensional weights). For an interval J = [ℓ, r] and parameter ε > 0, a set of arms L ⊆ A(J) is said to be an ε-left-skyline within interval J iff (i) for each arm b ∈ A(J), the set L contains an ε-Pareto optimal set T for the interval [pb, r], and (ii) each arm in L is ε-Pareto optimal for some interval [pb, r], with b ∈ A(J).

Analogously, an ε-right-skyline, R, is defined considering intervals {[ℓ, pb]}b∈A(J). The following characterization of ε-skylines will be used in the analysis; all the missing proofs appear in the full version of this paper.

Proposition 1. A set of arms L ⊆ A(J) is an ε-left-skyline within interval J = [ℓ, r] iff (i) for every arm b ∈ A(J), there exists an arm β ∈ L that satisfies pβ ≥ pb and µβ ≥ µb -ε1, and (ii) for each arm β ∈ L, there does not exist an arm x ∈ A(J) such that px ≥ pβ and µx ≥ µβ + ε1.

In Proposition 1-and in the remainder of this section-the inequalities are enforced component-wise. At a high level, the first condition of the proposition requires that for each arm b in the given interval, L contains a dominating (componentwise and within a factor of ε) point to the right of b. The second condition mandates that any arm in L is itself not dominated (componentwise and beyond a factor of ε) by arms to its right.

Our algorithm, D-LSKY (Algorithm 1), starts by setting A1 as the set of all arms within the given interval and ε1 as an initial approximation parameter. The algorithm then considers a partition of [0, 1]d into hypercubes of side length ε1/4. Drawing a conservative number of samples, the algorithm finds an estimate ̂ µa ∈ [0, 1]d for each arm a ∈ A1 and partitions the set of arms A1 itself based on how the estimates fall across different hypercubes.

For any hypercube B, let B(A1) be the set of arms (in A1) whose estimates are within B. We will establish that, if the cardinality of B(A1) is sufficiently large, then we can drop half of the arms in B(A1) from consideration, and still not loose ε-Pareto dominating arms. In particular, from every large-sized set B(A1), the algorithm removes from consideration half of the arms x ∈ B(A1) whose px value is less than the median of {py}y∈B(A1). This update ensures that the number of arms under consideration decreases geometrically, and at the same time, the set of arms that remain, say A2, continues to include an approximate skyline. The algorithm repeats analogous steps over A2, with an updated approximation parameter ε2 = 3ε1/4. Iteratively, the algorithm continues until the number of remaining arms is sufficiently small. At this point, the algorithm concludes by sampling the final set of arms AT (to obtain accurate-enough estimates of their weights) and returning a skyline (based on the final estimates) within AT .

We will now define constructs that will be useful in the design and analysis of our algorithm. For η ∈ (0, 1], define a lattice L(η) as the set of vectors in [0, 1]d whose components are integer multiples of η, i.e., L(η) := {(κ1η, κ2η, . . . , κdη) ∈ [0, 1]d | κ1, . . . , κd ∈ Z}. For each vector g ∈ L(η), define a (hyper) cube around it as B(η, g) := {ν ∈ [0, 1]d | ‖ν - g‖∞ ≤ η2 }. Note that the collection of cubes {B(η, g)}g∈L(η) forms a cover of [0, 1]d . Faces of these cubes can intersect. However, for ease of presentation and given that the interiors of the cubes are pairwise disjoint, we will consider them to constitute a partition of [0, 1]d ; in particular, by breaking ties arbitrarily, we will assume that each ν ∈ [0, 1]d belongs to exactly one cube in {B(η, g)}g∈L(η).

In each iteration t, with approximation parameter εt > 0, the algorithm considers the collection of cubes obtained by setting η = εt/4, i.e., it considers Bt := {B ( εt 4 , g)}g∈L( εt 4 ) .

In the analysis, we will consider a representative arm r(B) for each cube B ∈ Bt: among all arms b whose weight µb is in B, arm r(B) is the one with the maximum pr(B) value.

Definition 5 (Representative Arms). In any iteration t-with set of arms At under consideration-an arm r(B) ∈ At is said to be the representative of cube B ∈ Bt iff µr(B) ∈ B and pr(B) ≥ pb for all arms b ∈ At whose weight µb ∈ B.

6 The number of hypercubes is actually (⌈ 4 εi ⌉)d , but we assume 4 εi is an integer for ease of analysis.

Algorithm 1 D-LSKY: finds ε-left-skyline with probability at least 1- δ

Input: Interval J, with sample access to arms in A(J), points {pa}a∈A(J), and parameters ε, δ > 0. Output: Set of arms S ⊆ A(J)

• 1: Initialize set A1 = A(J), parameters ε1 = ε/5, δ1 = δ/2, and iteration count t = 1
• 2: while |At| > 120 ( 4 εt )d do
• 3: For each arm a ∈ At, find an empirical estimate, ̂ µa ∈ [0, 1]d , of its weight, by sampling the arm 8 ε2t log (( 4 εt )d 50d δt ) times
• 4: Initialize the set of arms to drop, Dt = ∅
• 5: for all cubes B ∈ Bt do
• 6: Write B(At) := {x ∈ At | ̂ µx ∈ B} {B(At) is defined using the estimated weights}
• 7: If |B(At)| > |At| 10 ( εt 4 )d , then Dt ← Dt ∪ {x ∈ B(At) : px < the median of {py}y∈B(At)}
• 8: end for
• 9: Set At+1 = At \ Dt, εt+1 = 3εt/4, δt+1 = δt/2, and update t ←- t + 1
• 10: end while
• 11: For each arm a ∈ At, find an estimate, ̂ µa ∈ [0, 1]d , of its weight, by sampling the arm 1 ε2t log ( |At|d δt ) times
• 12: Set ˜D := {z ∈ At | pz ≤ px and ̂ µz < ̂ µx for some x ∈ At} {With respect to the estimates, condition (ii) of Proposition 1 does not hold for arms in ˜D}
• 13: return At \ ˜D

Write Rt := {r(B)}B∈Bt to denote the set of all representatives in iteration t. Note that representative arms are defined considering the exact (but unknown) weights µb ∈ [0, 1]d . Still the definition is relevant, since we use these arms solely for the purposes of analysis, and not in the algorithm (which only has access to estimated weights ̂ µbs). Also, note that the

The next lemma (Lemma 2) highlights a significance of representative arms-it asserts that R1 (the set of representative arms in the first iteration) satisfies condition (i) of Proposition 1, with an (absolute) approximation factor of ε/20. Then, Lemma 3 (stated below) guarantees that, with high probability, the algorithm essentially maintains condition (i) between consecutive Rts.

Lemma 2. For every arm b ∈ A(J), there exists an arm r ∈ R1 that satisfies pr ≥ pb and µr ≥ µb - ε 20 1.

Lemma 3. In any iteration t, with probability 1-δt, for every representative arm r ∈ Rt, there exists an arm γ ∈ Rt+1 such that µγ ≥ µr - εt1 and pγ ≥ pr.

The following lemma bounds the number of samples required by D-LSKY.

Lemma 4. For any given interval J with m arms (m = |A(J)|), D-LSKY draws O ( md ε2 log d εδ ) samples.

We next state and establish the main result of this section. Theorem 2. Given any interval J with m arms, D-LSKY draws O ( md ε2 log d εδ ) samples and returns an ε-left-skyline within J with probability at least 1 - δ.

Proof Sketch. In the interest of space, we defer the technical details to the full version of this paper and provide a proof sketch here. The stated sample complexity of D-LSKY follows directly from Lemma 4. Hence, we establish the theorem by showing that the returned set AT \ ˜D satisfies both the conditions in Proposition 1 and, hence, is an ε-left-skyline; here T denotes the total number of iteration of the while loop in D-LSKY.

Towards this, first note that the representative set RT ⊆ AT satisfies condition (i) of Proposition 1, with probability at least 1 - ∑T-1 t=1 δt. This follows from Lemma 2 and a repeated application of Lemma 3. Furthermore, the sampling in Line 11 ensures that, with probability 1 - δT , we have ‖̂ µa - µa‖∞ ≤ εT ≤ ε/5 for every arm a ∈ AT . For the rest of the proof we will assume that these bounds hold and AT satisfies condition (i). It suffices to prove the stated claim under this assumption, since it holds with probability at least

We note that AT \ ˜D continues to satisfy condition (i) and it also bears conditions (ii) of Proposition 1. Condition (i) holds (with an additional approximation loss of at most ε/20), since in ˜D we are only removing arms that are themselves Pareto dominated, under accurate-enough estimates. Similarly, conditions (ii) follows from the fact that in AT \ ˜D we are retaining arms that are not Pareto dominated with respect to sufficiently-accurate estimates ̂ µas, i.e., the retained arms could not have been Pareto dominated under µas beyond an absolute approximation factor of ε. Overall, we get that the returned set AT \ ˜D bears both the conditions and, hence, it is an ε-left-skyline.

Analogous to Theorem 2, one can achieve a PAC guarantee for ε-right-skylines by executing D-LSKY on negated pa values.

4.2 Algorithm for Multi-Dimensional Weights

This subsection develops an algorithm for bandit range searching with d-dimensional weights. As mentioned previously, this result is obtained by reducing range searching to finding ε-skylines over slabs.

In particular, given interval J and parameters ε′ , δ′ > 0, the subroutine D-LSKY(J, ϵ′ , δ′ ) finds, with probability at least 1 - δ′ , an ε′ -left-skyline within J. Similarly, D-RSKY(J, ϵ′ , δ′ ) finds, with probability at least 1 - δ′ , an ε′ -right-skyline within J. These subroutines-in addition to identifying the desired set of arms-provide an empirical estimate ̂ µa ∈ [0, 1]d of the true weight (mean) µa ∈ [0, 1]d of each returned arm a. Specifically, subsumed within the same success probability as before, for every returned arm a we have an empirical estimate ̂ µa which satisfies ‖µa - ̂ µa‖∞ ≤ ε′ . This property is satisfied by the algorithms in Section 4.1.

By executing these two subroutines over each slab, ALG-D-RS populates a set of candidate arms C along with Algorithm 2 ALG-D-RS: (ε, δ)-PAC algorithm for range searching d-dimensional weights Input: Set of points P = {pa ∈ R}na=1 , collection of intervals I = {Ii = [ℓi, ri]}qi=1 , and sample access to the n arms, along with parameters ε > 0 and δ > 0.

• 1: Let e1 < e2 < . . . < eτ constitute a minimum-size hitting set for I, and write e0 = -∞ and eτ+1 = +∞
• 2: Define slabs Sj := [ej, ej+1], for 0 ≤ j ≤ τ
• 3: For every slab Sj, with 0 ≤ j ≤ τ, set left skyline Lj = D-LSKY (Sj, ε3 , δ 2(τ+1) ) and right skyline Rj = D-RSKY (Sj, ε3 , δ 2(τ+1) )
• 4: Set of candidate arms C = ⋃τj=0 (Lj ∪Rj)
• 5: For each interval Ii ∈ I, set Di = {x ∈ C ∩A(Ii) | ̂ µx < ̂ µy for some y ∈ C ∩A(Ii)} and Ti = (C ∩A(Ii)) \ Di {With respect to the estimates, Di is the set of Pareto dominated arms}
• 6: return {T1, . . . , Tq}

their weight estimates. Finally, for each input interval Ii, the algorithm considers the set of candidate arms within Ii and returns the ones that form a Pareto optimal set with respect to the estimates.

The following theorem asserts that ALG-D-RS achieves the desired PAC guarantee in a sample-efficient manner.

Theorem 3. Given a problem instance (P, I) with n arms, algorithm ALG-D-RS draws O ( nd ε2 log( τd εδ )) samples and achieves the (ε, δ)-PAC guarantee for bandit range searching with d-dimensional weights; here τ denotes the size of the minimum cardinality hitting set for I.

Proof Sketch. In the interest of space, we defer the technical details to the full version of this paper and provide a proof sketch here. For any slab Sj = [ej, ej+1], the subroutines D-LSKY (Sj, ε3 , δ 2(τ+1) ) and D-RSKY (Sj, ε3 , δ 2(τ+1) ) require O ( nj d ε2 log 2d(τ+1) εδ ) samples each; here, nj := A(Sj). Note that ∑τj=0 nj ≤ 2n; this inequality follows from the fact that any arm can be a part of at most two successive slabs. Now, summing over the sample complexities of the subroutines, across all the slabs, we get that O ( nd ε2 log( τd εδ )) samples are drawn in the algorithm.

Next, we complete the proof by showing that the ALG-D-RS achieves the (ε, δ)-PAC guarantee. Write E to denote the event that, for all the slabs, the subroutines find the desired set of arms along with accurate-enough estimates. Given that the success probability of each subroutine is at least (1- δ 2(τ+1) ) and there are 2(τ + 1) subroutine instan-

tiations, we get (via the union bound) that P{E} ≥ 1 - δ. We will prove that, under event E, for every input interval Ii ∈ I, the set of arms Ti ⊆ A(Ii) (selected in Line 5) satisfies both part (a) and (b) of Definition 3, i.e., Ti is ε-Pareto optimal for Ii. Hence, the desired PAC guarantee holds.

Fix an interval Ii ∈ I and consider any arm b ∈ A(Ii). We will first note the that there necessarily exists an arm a ∈ Ti that satisfies condition (a) (of Definition 3) for arm b. Towards this, note that Property (P) of our slab construction (see Section 2) ensures that interval Ii is partitioned among two or more slabs, Sx, Sx+1, . . . , Sy; in particular, x < y. We will perform a case analysis based on whether arm b is contained in Sx and one of the intermediate slabs, or in Sy.

Case I: b ∈ A(St) with x ≤ t < y. Here, under event E, the set of arms Lt (obtained by executing D-LSKY on St) is an (ε/3)-left-skyline. Therefore, using condition (i) in Proposition 1, one can show that there exists a candidate arm in C ⊇ Lt and, hence, an arm in Ti that satisfies condition (a) with respect to b. Case II: b ∈ A(Sy). The analysis here relies on the (ε/3)-right-skyline, Ry, of slab Sy and is otherwise identical to the previous case.

It only remains to prove that Ti satisfies part (b) of Definition 3. This follows from the observation that Ti retains arms that are not Pareto dominated with respect to sufficientlyaccurate estimates ̂ µas, i.e., the retained arms could not have been Pareto dominated under µas beyond an absolute approximation factor of ε. Therefore, parts (a) and (b) of Definition 3 hold for Ti, proving that Ti is indeed ε-Pareto optimal for Ii. This completes the proof.

5 Lower Bound

This section presents a lower bound which shows that our algorithms are essentially optimal in terms of sample complexity. The following result is obtained via a nontrivial reduction from a problem studied in [Cheu et al., 2018]; details of the reduction are deferred to the full version of this paper.

Theorem 4. For each τ ∈ Z+, there exists a bandit range searching instance, with n arms and interval collection I, such that the size of optimal hitting set for I is τ, and any algorithm that achieves the (ε, δ)-PAC guarantee for the instance necessarily draws Ω ( n ε2 log ( τ εd δ )) samples. Here, d is the ambient dimension of the weights.

6 Conclusion and FutureWork

This work establishes essentially tight sample-complexity bounds for the problem of identifying optimal arms within a given collection of intervals. Complementing the current focus on sample-efficient algorithms, one can also consider a regret version of the range searching.

Extending the range aspects to higher dimensions (e.g., finding optimal arms within rectangles) would also be interesting. More generally, the interplay of computational geometry and multi-armed bandits stands as a rich source of geometric problems over uncertain data.

Acknowledgements

Siddharth Barman gratefully acknowledges the support of a Ramanujan Fellowship (SERB - SB/S2/RJN-128/2015). Saladi Rahul's research is generously supported by an IISc Startup Grant.