{'fraction_non_alphanumeric': 0.04843791983194509, 'fraction_numerical': 0.014094140062043528, 'mean_word_length': 3.674583238182233, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The multi-armed bandit problem with covariates

We consider a multi-armed bandit problem in a setting where each arm produces a noisy reward realization which depends on an observable random covariate. As opposed to the traditional static multi-armed bandit problem, this setting allows for dynamically changing rewards that better describe applications where side information is available. We adopt a nonparametric model where the expected rewards are smooth functions of the covariate and where the hardness of the problem is captured by a margin parameter. To maximize the expected cumulative reward, we introduce a policy called Adaptively Binned Successive Elimination (abse) that adaptively decomposes the global problem into suitably"localized"static bandit problems. This policy constructs an adaptive partition using a variant of the Successive Elimination (se) policy. Our results include sharper regret bounds for the se policy in a static bandit problem and minimax optimal regret bounds for the abse policy in the dynamic problem.


INTRODUCTION
The seminal paper Robbins (1952) introduced an important class of sequential optimization problems, otherwise known as multi-armed bandits. These models have since been used extensively in such fields as statistics, operations research, engineering, computer science and economics. The traditional multi-armed bandit problem can be described as follows. Consider K ≥ 2 statistical populations (arms), where at each point in time it is possible to sample from (pull) only one of them and receive a random reward dictated by the properties of the sampled population. The objective is to devise a sampling policy that maximizes expected cumulative rewards over a finite time horizon. The difference between the performance of a given sampling policy and that of an oracle, that repeatedly samples from the population with the highest mean reward, is called the regret. Thus, one can re-phrase the objective as minimizing the regret.
When the populations being sampled are homogenous, i.e., when the sequential rewards are independent and identically distributed (iid) in each arm, the family of upper-confidence-bound (UCB) policies, introduced in Lai and Robbins (1985), incur a regret of order log n, where n is the length of the time horizon, and no other "good" policy can (asymptotically) achieve a smaller regret; see also Auer et al. (2002). The elegance of the theory and sharp results developed in Lai and Robbins (1985) hinge to a large extent on the assumption of homogenous populations and hence identically distributed rewards. This, however, is clearly too restrictive for many applications of interest. Often, the decision maker observes further information and based on that, a more customized allocation can be made. In such settings, rewards may still be assumed to be independent, but no longer identically distributed in each arm. A particular way to encode this is to allow for an exogenous variable (a covariate) that affects the rewards generated by each arm at each point in time when this arm is pulled.
Such a formulation was first introduced in Woodroofe (1979) under parametric assumptions and in a somewhat restricted setting; see Zeevi (2009, 2010) and Wang et al. (2005) for very different recent approaches to the study of such bandit problems, as well as references therein for further links to antecedent literature. The first work to venture outside the realm of parametric modeling assumptions appeared in Yang and Zhu (2002). In particular, the mean response in each arm, conditionally on the covariate value, was assumed to follow a general functional form, hence one can view their setting as a nonparametric bandit problem. They propose a variant of the ε-greedy policy, see, e.g., Auer et al. (2002) and show that the average regret tends to zero as the time horizon n grows to infinity. However, it is unclear whether this policy satisfy a more refined notion of optimality, insofar as the magnitude of the regret is concerned, as is the case for UCB-type policies in traditional bandit problems. Such questions were partially addressed in Rigollet and Zeevi (2010) where near-optimal bounds on the regret are proved in the case of a two-armed bandit problem under only two assumptions on the underlying functional form that governs the arms' responses. The first is a mild smoothness condition and the second is a so-called margin condition that involves a margin parameter which encodes the "separation" between the functions that describe the arms' responses.
The purpose of the present paper is to extend the setup of Rigollet and Zeevi (2010) to the K-armed bandit problem with covariates when K may be large. This involves a customized definition of the margin assumption. Moreover, the bounds proved in Rigollet and Zeevi (2010) suffered two deficiencies. First, they hold only for a limited range of values of the margin parameter and second, the upper bounds and the lower bounds mismatch by a logarithmic factor. Improving upon these results requires radically new ideas. To that end, we introduce three policies: 1. Successive Elimination (se) is dedicated to the static bandit case. It is the cornerstone of the others policies that deal with covariates. During a first phase, this policy explores the different arms, builds estimates and eliminates sequentially suboptimal arms; when only one arm remains, it is pulled until the horizon is reached. A variant of se was originally introduced in Even- Dar et al. (2006). However, it was not tuned to minimize the regret as other measures of performance were investigated in this paper. We prove new regret bounds for this policy that improve upon the canonical papers Lai and Robbins (1985) and Auer et al. (2002). 2. Binned Successive Elimination (bse) follows a simple principle to solve the problem with covariates. It consists in grouping similar covariates into bins and then look only at the average reward over each bin. These bins are viewed as indexing "local" bandit problems, solved by the aforementioned se policy. We prove optimal regret bounds, polynomial in the horizon but only for a restricted class of difficult problems. For the remaining class of easy problems, the bse policy is suboptimal. 3. Adaptively Binned Successive Elimination (abse) overcomes a severe limitation of the naive bse. Indeed, if the problem is globally easy (this is characterized by the margin condition), the bse policy employes a fixed and too fine discretization of the covariate space. Instead, the abse policy partitions the space of covariates in a fashion that adapts to the local difficulty of the problem: cells are smaller when different arms are hard to distinguish and bigger when one arm dominates the other. This adaptive partitioning allows us to prove optimal regrets bounds for the whole class of problems.
The optimal polynomial regret bounds that we prove are much larger than the logarithmic bounds proved in the static case. Nevertheless, it is important to keep in mind that they are valid for a much more flexible model that incorporates covariates. In the particular case where K = 2 and the problem is difficult, these bounds improve upon the results of Rigollet and Zeevi (2010) by removing a logarithmic factor that is idiosyncratic to the exploration vs. exploitation dilemma encountered in bandit problems. Moreover, it follows immediately from the previous minimax lower bounds of Audibert and Tsybakov (2007) and Rigollet and Zeevi (2010), that these bounds are optimal in a minimax sense and thus cannot be further improved. It reveals an interesting and somewhat surprising phenomenon: the price to pay for the partial information in the bandit problem is dominated by the price to pay for nonparametric estimation. Indeed the bound on the regret that we obtain in the bandit setup for K = 2 is of the same order as the best attainable bound in the full information case, where at each round, the operator receives the reward from only one arm but observes the rewards of both arms. An important example of the full information case is sequential binary classification. Our policies for the problem with covariates fall into the family of "plug-in" policies as opposed "minimum contrast" policies; a detailed account of the differences and similarities between these two setups in the full information case can be found in Audibert and Tsybakov (2007). Minimum contrast type policies have already received some attention in the bandit literature with side information, aka contextual bandits, in the papers Langford and Zhang (2008) and also Kakade et al. (2008). A related problem online convex optimization with side information was studied in Hazan and Megiddo (2007), where the authors use a discretization technique similar to the one employed in this paper. It is worth noting that the cumulative regret in these papers is defined in a weaker form compared to the traditional bandit literature, since the cumulative reward of a proposed policy is compared to that of the best policy in a certain restricted class of policies. Therefore, bounds on the regret depend, among other things, on the complexity of said class of policies. Plug-in type policies have received attention in the context of the continuum armed bandit problem, where as the name suggests there are uncountably many arms. Notable entries in that stream of work are Lu et al. (2010) and Slivkins (2011), who impose a smoothness condition both on the space of arms and the space of covariates, obtaining optimal regret bounds up to logarithmic terms.

IMPROVED REGRET BOUNDS FOR THE STATIC PROBLEM
In this section, it will be convenient for notational purposes, to consider a multi-armed bandit problem with K + 1 arms.
We revisit the Successive Elimination (se) policy introduced in Even- Dar et al. (2006) in the traditional setup of multi-armed bandit problems. As opposed to the more popular UCB policy (see, e.g., Lai and Robbins (1985); Auer et al. (2002)), it allows us in the next section, to construct an adaptive partition that is crucial to attain optimal rates on the regret for the dynamic case with covariates. In this section, we prove refined regret bounds for the se policy that exhibit a better dependence on the expected rewards of the arms compared to the bounds for UCB that were derived in Auer et al. (2002). Such an improvement was recently attempted in Auer and Ortner (2010) and also in Audibert and Bubeck (2010) for modified UCB policies and we compare these results to ours below.
Let us recall the traditional setup for the static multi-armed bandit problem (see, e.g., Auer et al. (2002)). Let I = {1, . . . , K + 1} be a given set of K + 1 ≥ 2 arms. Successive pulls of arm i ∈ I yield rewards Y Assume without loss of generality that f (1) ≤ · · · ≤ f (K+1) so that K + 1 is one of the best arms. For simplicity, we further assume that the best arm is unique since for the se policy, having multiple optimal arms only improves the regret bound. In the analysis, it is convenient to denote this optimal arm by ⋆ := K + 1 and to define the gaps traditionally denoted by ∆ 1 ≥ . . .
A policy π = {π t } is a sequence of random variables π t ∈ {1, . . . , K + 1} indicating which arm to pull at each time t = 1, . . . n, and such that π t depends only on observations strictly anterior to t.
The performance of a policy π is measured by its (cumulative) regret at time n defined by Note that for a data-driven policyπ, this quantity is random and, in the rest of the paper, we provide upper bounds on IER(π). Such bounds are referred to as regret bounds.
We begin with a high-level description of the se policy denoted byπ. It operates in rounds that are different from the decision times t = 1, . . . , n. At the beginning of each round τ , a subset of the arms has been eliminated and only a subset I τ remains. During round τ , each arm in I τ is pulled exactly once (Exploration). At the end of the round, for each remaining arm in I τ , we decide whether to eliminate it using a simple statistical hypothesis test: if we conclude that its mean is significantly smaller than the mean of any remaining arm, then we eliminate this arm and we keep it otherwise (Elimination). We repeat this procedure until n pulls have been made. The number of rounds is random but obviously smaller than n.
The se policy, which is parameterized by two quantities T ∈ IN and γ > 0 and described in Policy 1, outputs an infinite sequence of armsπ 1 ,π 2 , . . . without a prescribed horizon. Of course, it can be truncated at any horizon n. This description emphasizes the fact that the policy can be implemented without perfect knowledge of the horizon n and in particular, when the horizon is a random variable with expected value n (see Corollaries 2.1 and 2.3 used in Sections 4 and 5); Nevertheless, in the static case, it is manifest from our result that, when the horizon is known to be n, choosing T = n is always the best choice when possible and that other choices may lead to suboptimal results.
Note that after the exploration phase of each round τ = 1, 2, . . . , each remaining arm i ∈ I τ has been pulled exactly τ times, generating rewards Y where here and throughout this paper, we use the convention 1/0 = ∞. For any positive integer T , define also which is essentially a high probability upper bound on the magnitude of deviations The se policy for a K-armed bandit problem can be implemented according to the pseudo-code of Policy 1. Note that, to ease the presentation of Sections 4 and 5, the se policy also returns at each time t, the number of roundsτ t completed at time t and a subsetŜ t ∈ P(I) of arms that are active at time t, where P(I) denotes the power set of I.
Theorem 2.1. Consider a (K +1)-armed bandit problem. When implemented with parameters T = n, γ = 1, the se policyπ exhibits an expected regret bounded as Proof. Define ε τ = U (τ, n). Moreover, for any i in the set I τ of arms that remain active at the beginning of round τ , define ∆ i (τ ) : Since ∆ i (τ ) estimates ∆ i , the event in (i) happens approximately, when ε τ ≃ ∆ i , so we introduce the deterministic, but unknown, quantity τ * i (and its approximation τ i = ⌈τ * i ⌉) defined as the solution of: We are going to decompose the regret accumulated by a suboptimal arm i into three quantities: -the regret accumulated by pulling this arm at most until round τ i : this regret is smaller than τ i ∆ i ; -the regret accumulated by eliminating the optimal arm ⋆ between round τ i−1 + 1 and τ i , -the regret induced if arm i is still present at round τ i (and in particular, if it has not been eliminated by the optimal arm ⋆).
We prove that the second and third events happen with small probability, because of the choice of τ i . Formally, define the following good events: . . , i} has been eliminated before round τ j } .
Moreover, define C i = A i ∩ B i and observe that C 1 ⊇ C 2 ⊇ . . . . For any i = 1, . . . , K, the contribution to the regret incurred after time τ i on C i is at most n∆ i+1 since each pull of arm j ≥ i + 1 contributes to the regret by ∆ j ≤ ∆ i+1 . We decompose the underlying sample space denoted by C 0 into the disjoint union It implies the following decomposition of the expected regret: Define by A c the complement of an event A. Note that the first term on the right-hand side of the above inequality can be bounded as follows where the right-hand side was obtained using the decomposition On the event A i ∩ B i−1 , every suboptimal arm j ≤ i − 1 has been eliminated before round τ i−1 and the optimal arm ⋆ is present at round τ i ; so the probability . From Hoeffding's inequality, we have that for every ε ∈ (0, ∆) and every τ ≥ 1: It remains to bound the first term in the rhs of (2.4). On the event C i−1 , the optimal arm ⋆ has not been eliminated before the round τ i−1 but every suboptimal arm j ≤ i−1 has. So the probability that there exists an arm j ≥ i that eliminates ⋆ between τ i−1 and τ i can be bounded as where, using Lemma A.1, we get Φ j (τ ) := IP ∃s ≤ τ ; ∆ j (s) ≤ −ε s ≤ 4 τ n . Moreover, the above inequality implies that Using the facts that τ i ≤ 18 The previous two displays yield Putting together (2.3), (2.4), (2.6) and the above display yields Choosing now the value K 0 = K completes the proof of the first bound.
On the other hand, the specific value The right-hand side of (2.2) is the minimum of two terms. The first term is distribution-dependent and shows that the se policy adapts to the unknown distribution of the rewards. It is very much in the spirit of the original bound of Lai and Robbins (1985) and of the more recent finite sample result of Auer et al. (2002). Our bound for the se policy is smaller than the aforementioned bounds for the UCB policy by a logarithmic factor. Lai and Robbins (1985) did not provide the first bounds on the expected regret. Indeed, Vogel (1960) and Bather (1981) had previously derived what is often called gap-free bound as they hold uniformly over the ∆ i 's. The second term in our bound is such a gap-free bound. It is of secondary interest in this paper and arise as a byproduct of refined distribution dependent bound. Nevertheless, it allows us to recover near optimal bounds of the same order as Juditsky et al. (2008). They depart from optimal rates by a factor √ log K as proved in Audibert and Bubeck (2010). Actually, the result of Audibert and Bubeck (2010) is much stronger than our gap-free bounds since it holds for any sequence of bounded rewards, not necessarily drawn independently. None of the distribution-dependent bounds in Theorem 2.1 or the one provided in Audibert and Bubeck (2010) is stronger than the other. The superiority of one over the other depends on the set {∆ 1 , . . . , ∆ K }: in some cases (for example if all suboptimal arms have the same expectation) the latter is the best while in other cases (if the ∆ i are spread) our bounds are better.
The next corollaries follow from slight variations on the proof of Theorem 2.1. We only sketch their proof for brevity.
Corollary 2.1. When implemented with any parameter T and γ = 1 and run at horizon n, the se policyπ exhibits an expected regret bounded as Thus if the horizon is a random variable N of expectation n that is independent of the random rewards, the se policyπ implemented with T exhibits an expected regret bounded as Proof. In this setting, the regret induced by eliminating ⋆ (or not eliminating a suboptimal arm i before round τ i ) is still bounded above by n∆ i . However, one has to substitute T to n in the probability of making such mistakes.
The following corollaries are used in Sections 4 and 5.
Corollary 2.2. Let K 0 be an integer between 1 and K. When implemented with parameters T = n, γ = 1, the se policyπ exhibits an expected regret bounded as Proof. It was proved in (2.7).
This corollary is actually closer to the result of Auer and Ortner (2010). The additional second term in our bound comes from the fact that we had to take into account the probability that an optimal arm ⋆ can be eliminated by any arm, not just by some suboptimal arm with index lower than K 0 (see Auer and Ortner (2010), page 8). It is unclear why it is enough to look at the elimination by those arms, since if ⋆ is eliminated -no matter the arm that eliminated it -, the Hoeffding bound (2.5) no longer holds.
Corollary 2.3. If the horizon is a random variable N of expectation n that is independent of the random rewards, the se policyπ implemented with parameters T, γ ≥ 1 exhibits an expected regret bounded as Similarly, thus the proof of Theorem 2.1 holds except that the upper bound of τ i must be replaced by the one of τ ′ i .

BANDIT WITH COVARIATES
This section is dedicated to a detailed description of nonparametric bandit with covariates.

Machine and game
A K-armed bandit machine with covariates (with K an integer greater than 2) is characterized by a sequence of independent random vectors, where X t t≥1 , is a sequence of iid covariates in X = [0, 1] d with probability distribution P X , and Y (i) t denotes the random reward yielded by arm i at time t. Throughout the paper, we assume that P X has a density, with respect to the Lebesgue measure, bounded above and below by some c > 0 and c > 0 respectively. We denote by E X the expectation with respect to P X . We assume that, for each i ∈ I = {1, . . . , K}, rewards Y The game takes place sequentially on this machine, pulling one of the arms at each time t = 1, . . . , n. A policy π = {π t } is a sequence of random functions π t : X → {1, . . . , K} indicating to the operator which arm to pull at each time t, and such that π t depends only on observations strictly anterior to t. The oracle policy π ⋆ , refers to the strategy that would be run by an omniscient operator with complete knowledge of the functions f (i) , i = 1, . . . , K. Given side information X t , the oracle policy π ⋆ prescribes to pull any arm with the largest expected reward, i.e., with ties broken arbitrarily. Note that the function f (π ⋆ (x)) (x) is equal to the pointwise maximum of the functions f (i) , i = 1, . . . , K defined by The oracle rule is used to benchmark any proposed policy π and to measure the performance of the latter via its (cumulative) regret at time n defined by Without further assumptions on the machine, the game can be arbitrarily difficult and, as a result, expected regret can be arbitrarily close to n. In the following subsection, we describe natural regularity conditions under which it is possible to achieve sublinear growth rate of the expected regret, and characterize policies that perform in a near-optimal manner.

Smoothness and margin conditions
As usual in nonparametric estimation we first impose some regularity on the functions f (i) , i = 1, . . . , K.
Here and in what follows we use · to denote the Euclidean norm on IR d .
Smoothness condition. We say that the machine satisfies the smoothness condition with parameters (β, for some β ∈ (0, 1] and L > 0. Now denote the second pointwise maximum of the functions f (i) , i = 1, . . . , K by f ♯ ; formally for every x ∈ X such that min Notice that a direct consequence of the smoothness condition is that the function f ⋆ is (β, L)-Hölder; however, f ♯ might not even be continuous. The behavior of the function ∆ := f ⋆ − f ♯ critically controls the complexity of the problem and the Hölder regularity gives a local upper bound on this quantity. The second condition gives a lower bound on this function though in a weaker global sense. It is closely related to the margin condition employed in classification Tsybakov (2004); Mammen and Tsybakov (1999), which drives the terminology employed here. It was originally imported to the bandit setup by Goldenshluger and Zeevi (2009).
Margin condition. We say that the machine satisfies the margin condition with parameter α > 0 if there exists δ 0 ∈ (0, 1), C 0 > 0 such that If the marginal P X has a density bounded above and below, the margin condition contains only information about the behavior of the function ∆ and not the marginal P X itself. This is in contrast with Goldenshluger and Zeevi (2009) where the margin assumption is used precisely to control the behavior of the marginal P X while that of the reward functions is fixed. A large value of the parameter α means that the function ∆ either takes value 0 or is bounded away from 0, except over a set of small P X -probability. Conversely, for values of α close to 0, the margin condition is essentially void and the two functions can be arbitrary close, making it difficult to distinguish them. This reflects in the bounds on the expected regret derived in the subsequent section.
Intuitively, the smoothness condition and the margin condition work in opposite directions. Indeed, the former ensures that the function ∆ does not "depart from zero" too fast whereas the latter warrants the opposite. The following proposition quantifies the extent of this conflict.
Proposition 3.1. Under the smoothness condition with parameters (β, L), and the margin condition with parameter α, the following holds -If αβ > d then a given arm is either always or never optimal; in the latter case, it is bounded away from f ⋆ and one can take α = ∞; -If αβ ≤ d then there exist machines with nontrivial oracle policies.
Proof. This proposition is a straightforward consequences of, respectively, the first two points of Proposition 3.4 in Audibert and Tsybakov (2005).
We denote by M K X (α, β, L) the class of K-armed bandit problems with covariates in X = [0, 1] d with a machine satisfying the margin condition with parameter α > 0, the smoothness condition with parameters (β, L) and such that P X has a density, with respect to the Lebesgue measure, bounded above and below by some c > 0 and c > 0 respectively.

Binning of the covariate space
To design a policy that solves the bandit problem with covariates described above, one has to inevitably find an estimate of the functions f (i) , i = 1, . . . , K at the current point X t . There exists a wide variety of nonparametric regression estimators ranging from local polynomials to wavelet estimators. Both of the policies introduced below are based on estimators of f (i) , i = 1, . . . , K that are P X almost surely piecewise constant over a particular collection of subsets, called bins of the covariate space X .
We define a partition of X in a measure theoretic sense as a collection of measurable sets, hereafter called bins, B 1 , B 2 , . . . such that P X (B j ) > 0, j≥1 B j = X and B j ∩ B k = ∅, j, k ≥ 1, up to sets of null P X probability. For any reward function f (i) on X , the average reward on bin B is defined by where p B = P X (B) . To define and analyze our policies, it is convenient to reindex our observations ) t≥1 as follows. Given a bin B, let t B (s) denote the sth time at which the sequence (X t ) t≥1 is in B and observe that it is a stopping time. Moreover, define the sequence of successive rewards obtained from arm i at times at which X t ∈ B by Y s ≥ 1 , t B (s) ≥ t 0 } is the set of chronological times t posterior to t 0 at which X t ∈ B. Fix I ′ ⊂ I and consider the static bandit problem with arms I ′ defined in Section 2 where successive pulls of arm i ∈ I ′ yield rewards Y The se policy with parameters T, γ on this static problem is called se policy on B initialized at time t 0 with initial set of arms I ′ and parameters T, γ.

BINNED SUCCESSIVE ELIMINATION
We first outline a naive policy to operate the bandit machine described in section 3. It consists in fixing a partition of X and for each set B in this partition, to run the se policy on B initialized at time t 0 = 1 with initial set of arms I and parameters to be defined below.
The Binned Successive Elimination (bse) policyπ relies on a specific partition of X . Let B M := {B 1 , . . . , B M d } be the regular partition of X = [0, 1] d , i.e., the reindexed collection of hypercubes defined for k = (k 1 , . . . , k d ) ∈ {1, . . . , M } d by In this paper, all sets are defined up to sets of null Lebesgue measure. As mentioned in subsection 3.3, the problem can be decomposed into M d independent static bandit problems, one for each B ∈ B M . Denote byπ B the se policy on bin B with initial set of arms I and parameters T = nM −d , γ = 1. For any x ∈ X , let B(x) ∈ B M denote the bin such that x ∈ B(x). The bse policyπ is a sequence of functionsπ t :

). end for
The following theorem gives an upper bound on the expected regret of the bse policy in the case where the problem is difficult, that is, when the margin parameter α satisfies 0 < α < 1. ⌋ has a an expected regret at time n bounded as follows, where C > 0 is a positive constant that does not depend on K.
The case K = 2 was studied in Rigollet and Zeevi (2010) using a similar policy called UCBogram. The bound in Theorem 4.1 improves upon the rate for the UCBogram by a logarithmic term in n. This comes from the fact that, unlike in Rigollet and Zeevi (2010) where suboptimal bounds for the UCB policy are used, we use here the sharper regret bounds of Corollary 2.3 and the se policy as a running horse for our policy. Optimality of this bound in the case of K = 2 arms is discussed after Theorem 5.1.
Proof. We assume that B M = {B 1 , . . . , B M d } where the indexing will be made clearer later in the proof. Moreover, to keep track of positive constants, we number them c 1 , c 2 , . . .. For any real valued function f on X and any measurable A ⊆ X , we use the notation P X (f ∈ A) = P X (f (X) ∈ A). Moreover, for any i ∈ {⋆, 1, . . . , K}, we use the notationf Define c 1 = 2Ld β/2 + 1, and let n 0 ≥ 2 be the largest integer such that n β/(2β+d) 0 ≤ 2c 1 /δ 0 , where δ 0 is the constant appearing in the margin condition. If n ≤ n 0 , we have R n (π) ≤ n 0 so that the result of the theorem holds when C is chosen large enough, depending on the constant n 0 . In the rest of the proof, we assume that n > n 0 so that c 1 M −β < δ 0 .
Recall that the bse policyπ is a collection of functionsπ t =π B,t B (t) that are constant on each B j . Therefore, the regret ofπ can be decomposed as R n (π) = Consider the set of well behaved bins on which the expected reward functions of the arms are well separated. These are the bins B j with indices in J defined by A bin B that is not well behaved is called strongly ill behaved if there is some , for all i ∈ I, and weakly ill behaved otherwise. Respectively, the sets of strongly or weakly ill behaved bins have indices in Note that for any i ∈ I, the function f ⋆ − f (i) is (β, 2L)-Hölder. It implies that for any j ∈ J c s and any i = 1, . . . , K, First part: Strongly ill behaved bins in J c s . Recall that for any j ∈ J c s , any arm i ∈ I, and any where we used the fact that the set {x ∈ X : f ⋆ (x) = f ♯ (x)} does not contribute to the regret.
Second part: Weakly ill behaved bins in J c w . The numbers of weakly ill behaved bins can be bounded using the fact that f ⋆ (x) − f ♯ (x) > 0 on such a bin; indeed, the margin condition implies that We bound the expected regret on each weakly ill behaved bins using Corollary 2.3 and the specific values ∆ K 0 := K log K nM −d , γ = 1 and T = nM −d . It implies that there exists a positive constant c 2 > 0 such that: Third part: Well behaved bins in J . This part is decomposed into two steps. In the first step, we bound the expected regret in a given bin B j , j ∈ J ; in the second step we use the margin condition to control the sum of all these expected regrets.
Step 1. Fix j ∈ J and recall that there exists We call I ⋆ j the set of (almost) optimal arms over B j and I 0 j the set of suboptimal arms over B j . Note that I 0 j = ∅ for any j ∈ J . The smoothness condition implies that for any i ∈ I 0 j , x ∈ B j , Therefore, f ⋆ −f ♯ > 0 on B j . Moreover, for any arm i ∈ I ⋆ j that is not the best arm at some x = x j , then necessarily 0 So for any x ∈ B j and any i ∈ I ⋆ j , it holds that either Thus, for any optimal arm i ∈ I ⋆ j , the reward functions averaged over For any suboptimal arms i ∈ I 0 j , (4.11) implies that ∆ Assume now without loss of generality that the average gaps ∆ and observe that if i ∈ J is such that ∆ (i) j < ∆ j , then i ∈ I ⋆ j . Therefore, it follows from (4.12) that ∆ (i) j ≤ c 1 M −β q j for such i. Recall that the bse runs a se policy on B j initialized at time t 0 = 1 so that it has a random horizon N j (n) = n i=1 1I(X t ∈ B j ). Since the density of P X is bounded above, we get IE[N j (n)] ≤cnM −d . Applying Corollary 2.3 with K 0 as above and γ = 1, we find that there exists a constant c 3 > 0 such that, for any j ∈ J , Step 2. We now use the margin condition to provide lower bounds on ∆ j for each j ∈ J . Assume without loss of generality that the indexing of the bins is such that J = {1, . . . , j 1 } and that the gaps are ordered 0 < ∆ 1 ≤ ∆ 2 ≤ . . . ≤ ∆ j 1 . For any j ∈ J , from the definition of ∆ j , there exists a suboptimal arm i ∈ I 0 But since the function f ⋆ − f (i) satisfies the smoothness condition with parameters (β, 2L), we find that if ∆ j ≤ δ for some δ > 0, then Together with the fact that f ⋆ − f ♯ > 0 over B j for any j ∈ J (see Step 1 above), it yields where we used the fact that p k = P X (B k ) ≥ c/M d . Define j 2 ∈ J to be the largest integer such that ∆ j 2 ≤ δ 0 /c 1 . Since for any j ∈ J , we have ∆ j > M −β , the margin condition yields for any j ∈ {1, . . . , j 2 } that, where we have used the fact that ∆ j + 2Ld β/2 M −β ≤ c 1 ∆ j ≤ δ 0 , for any j ∈ {1, . . . , j 2 }. The previous two inequalities, together with the fact that ∆ j > M −β for any j ∈ J , yield Therefore, using the fact that ∆ j ≥ δ 0 /c 1 for j ≥ j 2 , we get from (4.13) that (4.14) Fourth part: Putting things together.
imsart-sts ver. 2009/08/13 file: PerRig11_arxiv_rev.tex date: June 12, 2012 some light on a significant limitation of the bse which surfaces in this parameter regime: for n large enough, it requires the operator to pull each arm at least once in each bin and therefore to incur an expected regret of at least order M d . In other words, the bse splits the space X in "too many" bins when α ≥ 1. Intuitively this can be understood as follows. When α ≥ 1, the gap function f ⋆ (x) − f ♯ (x) is bounded away from zero on a large subset of X . Hence there is no need to carefully estimate it since the optimal arm is the same across the region. As a result, one could use larger bins in such regions reducing the overall number of bins and therefore removing the extra logarithmic term alluded to above.

ADAPTIVELY BINNED SUCCESSIVE ELIMINATION
We need the following definitions. Assume that n ≥ K log(K) and let k 0 be the smallest integer such that For any bin B ∈ k≥0 B 2 k , let ℓ B be the smallest integer such that where U is defined in (2.1) and c 0 = 2Ld β/2 . This definition implies that for some positive constant C ℓ . The abse policy operates in a manner similar to the bse except that instead of fixing a partition B M , it relies on an adaptive partition that is refined over time. This partition is better understood using the notion of rooted tree.
Let T * be a tree with root X and maximum depth k 0 . A node B of T * with depth k = 0, . . . , k 0 − 1 is a set from the regular partition B 2 k . The children of node B ∈ B 2 k are given by burst(B), defined to be the collection of 2 d bins in B 2 k+1 that forms a partition of B.
Note that the set L of leaves of each subtree T of T * forms a partition of X . The abse policy constructs a sequence of partitions L 1 , . . . , L n that are leaves of subtrees of T * . At a given time t = 1, . . . , n, we refer to the elements of the current partition L t as live bins. The sequence of partitions is nested in the sense that if B ∈ L t , then either B ∈ L t+1 or burst(B) ⊂ L t+1 . The sequence L 1 , . . . , L n is constructed as follows.
In the initialization step, set L 0 = ∅, L 1 = X , and the initial set of arms I X = {1, . . . , K}. Let t ≤ n be a time such that L t = L t−1 and let B t be the collection of sets B such that B ∈ L t \ L t−1 . We say that the bins B ∈ B t are born at time t. For each set B ∈ B t , assume that we are given a set of active arms I B . Note that t = 1 is such a time with B 1 = {X } and active arms I X . For each born bin B ∈ B t , we run a se policyπ B initialized at time t with initial set of arms I B and parameters T B = n|B| −d , γ = 2. Such a policy is defined in section 3.3. Let t(B) denote the time at whichπ B has reached ℓ B rounds and record the set of armsŜ B that are active at this time. At time t(B) + 1, we replace the node B by its children burst(B) in the current partition. Namely, L t(B)+1 = (L t(B) \ B) ∪ burst(B). Moreover, to each bin B ′ ∈ burst(B), we assign the set of active arms I B ′ =Ŝ B . This procedure is repeated until the horizon n is reached.
The intuition behind this policy is the following. The parameters of the se policyπ B run at the birth of bin B are chosen exactly such that arms i with average gap |f ⋆ B −f (i) B | ≥ C|B| β are eliminated by the end of ℓ B rounds with high probability. The smoothness condition ensures that these eliminated arms satisfy f ⋆ (x) > f (i) (x) for all x ∈ B so that such arms are uniformly suboptimal on bin B. Among the kept arms, none is uniformly better than another so bin B is burst and the process is repeated on the children of B where other arms may be uniformly suboptimal. The formal definition of the abse is given in Policy 3.
Note that the bounds given in Theorem 5.1 are optimal in a minimax sense when K = 2. Indeed, the lower bounds of Audibert and Tsybakov (2007) and Rigollet and Zeevi (2010) imply that the bound on the expected regret cannot be improved as a function of n expect for a constant multiplicative term. Note that the lower bound proved in Audibert and Tsybakov (2007) implies that any policy that received information from both arms at each round has a regret bound at least as large as the one from Theorem 5.1, up to a multiplicative constant. As a result, there is no price to pay for being in a partial information setup and one could say that the problem of nonparametric estimation dominates the problem associated to making decisions sequentially.
Note also that when α = ∞, Proposition 3.1 implies that there exists a unique optimal arm over X and that all other arms have reward bounded away from that of the optimal arm. As a result, given this information, one could operate as if the problem was static by simply discarding the covariates. Theorem 5.1 implies that in this case, one recovers the traditional regret bound of the static case without the knowledge that α = ∞.
Proof. We first consider the case where α < ∞, which implies that αβ ≤ d; see Proposition 3.1.
We keep track of positive constants by numbering them c 1 , c 2 , . . . On each newly created bin B, a new se policy is initialized and we denote by Y Denote by r live n (B) the regret generated by the abse policyπ when covariate X t fell in a live bin B ∈ L t , where we recall that L t denotes the current partition at time t. It is defined by We also define B t := s≤t L s to be the sets of bins that were born at some time s ≤ t. We denote by r born n (B) the regret generated when covariate X t fell in such a bin. It is defined by Observe that if we definer n := r born n (X ), we have IER n (π) = IEr n since X ∈ B t and X t ∈ X for all t. Note that for any B ∈ T * , Denote by I B =Ŝ B,t B the set of arms left active by the se policyπ B on B at the end of ℓ B rounds. Moreover, define the following reference sets of arms: Let L * denote the set of leaves of T * , that is the set of bins B such that |B| = 2 −k 0 . As a result, the quantity we are interested in can be decomposed asr n =r n (T * \ L * ) +r n (L * ) wherẽ

Define the event
is the regret on the non-terminal nodes and is the regret on the leaves. Our proof relies on the events G B := B ′ ∈P(B) A B ′ .
First part: control of the regret on the non-terminal nodes Fix B ∈ T * \L * . On G B , we have I p(B) ⊆ I p(B) so that any active arm i ∈ I p(B) satisfies sup x∈p(B) |f ⋆ (x) − f (i) (x)| ≤ 8c 0 |p(B)| β . Defining c 1 := 2 3+β c 0 , it yields We can always assume that n is greater than n 0 ∈ IN, the integer defined by and let k 1 ≤ k 0 be the smallest integer such that c 1 2 −k 1 β ≤ δ 0 . Indeed, if n ≤ n 0 , the result is true with a constant large enough.
Indeed, for k ≥ k 1 one can define c 2 = c α 1 c , and the same equation holds with c 2 = 2 dk 1 if k ≤ k 1 . Summing over all depths k ≤ k 0 − 1, we obtain (5.23) On the other hand, for every bin B ∈ T * \ L * , one also has (5.24) IE r born It remains to control the probability of G B ∩ A c B ; we define IP G B (·) := IP( · ∩ G B ). On G B , the event A c B can occur in two ways: (i) By eliminating an arm i ∈ I B at the end of the at most ℓ B rounds played on bin B. These arms satisfy sup x∈B f ⋆ (x) − f (i) (x) < c 0 |B| β ; this event is denoted by D 1 B . (ii) By not eliminating an arm i / ∈ I B within the at most ℓ B rounds played on bin B. These arms satisfy sup x∈B f ⋆ (x) − f (i) (x) ≥ 8c 0 |B| β ; this event is denoted by D 2 B . We use the following decomposition We first control the probability of making error (i). Note that for any s ≤ ℓ B and any arms i ∈ I B , i ′ ∈ I p(B) , it holds where in the second inequality, we used Lemma A.1.
Next, we treat error (ii). For any i / ∈ I B , there exists x (i) such that f ⋆ (x (i) ) − f (i) (x (i) ) > 8c 0 |B| β . Letǐ =ǐ(i) ∈ I be any arm such that f ⋆ (x (i) ) = f (ǐ) (x (i) ); the smoothness condition implies that On the event (D 1 B ) c , no arm in I B , and in particular any of the armsǐ(i), i ∈ I p(B) \ I B has been eliminated until round ℓ B . Therefore, the event Hence, the probability of error (ii) can be bounded by where the second inequality is a consequence of the Hoeffding-Azuma inequality (A.1).